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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2014

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1705???
  • ???subjectarea.asjc.2200.2208???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Distributed adaptive routing convergence to non-blocking DCN routing assignments'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי