Abstract: This paper studies the flow scheduling algorithm based on the optical-electrical switching fabric in the data center networks featured with multi-stage Clos to reduce the data transmission delay while causing no packet loss. The traditional ADAPT scheduling algorithm can minimize speedup, but there are still some idle time slots, resulting in the underutilization of bandwidth. In order to solve this problem, this paper proposes a Multi-Hop Routing and Scheduling （MHRS） algorithm, which can make full use of the idle bandwidth without increasing the speedup. Similar to the ADAPT algorithm, the MHRS first decomposes the traffic matrix into a quotient matrix and a residual matrix, and then implements two-step scheduling. The single hop is the first step and the multi-hop is the second step. In the first step, some packets in the residual matrix are scheduled to the idle time slot of the configuration matrix formed by the quotient matrix. When these data packets cannot be directly scheduled in the first step, a multi-hop scheduling process will be adopted by making a detour to transmit the data packets in the second step. The simulation results show that the MHRS algorithm performs better than the ADAPT algorithm in the multi-stage Clos networks.

Key words: data center network（DCN）, optical-electrical switching fabric, multi-hop routing and scheduling

摘要： 研究了基于多级Clos数据中心网络的光电交换架构下的流量调度算法，以减少数据传输时延，同时也保证无丢包。传统ADAPT调度算法能实现加速比最小化，但仍然有一些空闲时间槽，而造成带宽未被充分利用。为了解决该问题，在多级Clos网络中，提出了一个多跳路由和调度（Multi-Hop Routing and Scheduling，MHRS）算法，该算法可以在不增加加速比的同时充分利用空闲的带宽。与ADAPT算法类似，MHRS算法先将流量矩阵分解为商矩阵和余矩阵，然后实现两步调度，即将单跳作为第一步，将多跳作为第二步。第一步将余矩阵中的一些数据包调度到商矩阵所形成的配置矩阵的空闲时间槽中，而当这些数据包不能在第一步中被直接调度时，则采用第二步绕道的多跳调度过程传输数据包。仿真结果证明，在多级Clos网络中MHRS算法比ADAPT算法性能更好。

关键词: 数据中心网络（DCN）, 光电交换架构, 多跳路由和调度