Minimizing Delay by Multi-Hop Routing and Scheduling in Clos Networks for DCNs

We study traffic scheduling in optical-electrical switching fabrics in Data Center Networks (DCNs) based on multi-stage Clos networks to minimize data transmission delay and ensure 100% throughput. The existing classical ADAPT scheduling algorithm can minimize the speedup (the radio of the internal transmission rate inside the optical switch to the external line-rate), but still has some idle time-slots (i.e., not-yet-utilized slots), especially for uneven traffic distribution. To solve this issue, we propose a Multi-Hop Routing and Scheduling (MHRS) algorithm by utilizing idle bandwidths without increasing the speedup in multi-stage Clos networks for DCNs. Similar to ADAPT, MHRS divides traffic matrix into quotient and residual matrices. It includes two steps: single-hop scheduling as the first and multi-hop scheduling as the second. The first step is to schedule packets in the residual matrix to the idle time-slots of configuration matrices generated from the quotient matrix. When those packets cannot be directly scheduled in the first step, the second step invokes multi-hop scheduling process by making a detour for transmission. Simulation results confirm that MHRS can achieve a better performance in multi-stage Clos networks as compared with ADAPT.