Distributed adaptive routing convergence to non-blocking DCN routing assignments

Eitan Zahavi, Isaac Keslassy, Avinoam Kolodny

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


With the growing popularity of big-data applications, Data Center Networks (DCN) increasingly carry larger and longer traffic flows. As a result of this increased flow granularity, static routing cannot efficiently load-balance traffic, resulting in an increased network contention and a reduced throughput. Unfortunately, while adaptive routing can solve this load-balancing problem, DCN designers refrain from using it, because it also creates out-of-order packet delivery that can significantly degrade the reliable transport performance of the longer flows. In this paper, we show that by throttling each flow bandwidth to half of the network link capacity, a distributed adaptive routing algorithm is able to converge to a non-blocking routing assignment within a few iterations, causing minimal out-of-order packet delivery. We present a Markov chain model for distributed adaptive routing in the context of Clos networks that provides an approximation for the expected convergence time. This model predicts that for full-link-bandwidth traffic, the convergence time is exponential with the network size, so out-of-order packet delivery is unavoidable for long messages. However, with half-rate traffic, the algorithm converges within a few iterations and exhibits weak dependency on the network size. Therefore, we show that distributed adaptive routing may be used to provide scalable and non-blocking routing even for long flows in a rearrangeably-non-blocking Clos network under half-rate conditions. The proposed model is evaluated and approximately fits the abstract system simulation model. Hardware implementation guidelines are provided and evaluated using a detailed flit-level InfiniBand simulation model. These results, providing fast convergence to non-blocking routing assignment, directly apply to adaptive-routing systems designed and deployed in various DCNs.

اللغة الأصليةالإنجليزيّة
رقم المقال140109
الصفحات (من إلى)88-101
عدد الصفحات14
دوريةIEEE Journal on Selected Areas in Communications
مستوى الصوت32
رقم الإصدار1
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يناير 2014

All Science Journal Classification (ASJC) codes

  • !!Computer Networks and Communications
  • !!Electrical and Electronic Engineering


أدرس بدقة موضوعات البحث “Distributed adaptive routing convergence to non-blocking DCN routing assignments'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا