On-Line Multicast Scheduling with Bounded Congestion in Fat-Tree Data Center Networks

• Published in: IEEE journal on selected areas in communications 2014-01, Vol.32 (1), p.102-115
• Main Authors: Guo, Zhiyang, Duan, Jun, Yang, Yuanyuan
• Format: Article
• Language: English
• Subjects: Algorithm design and analysis; Algorithms; Bandwidth; Computer centers; Congestion; Data center networks; Data centers; fat-tree; flow scheduling; hose model; Hoses; load balance; Multicast; Network interface cards; Networks; on-line; Ports (Computers); predictability; Prediction algorithms; Scheduling; Scheduling algorithms; Servers; Traffic congestion; Traffic engineering; Traffic flow
• ISSN: 0733-8716; 1558-0008
• DOI: 10.1109/JSAC.2014.140110

Multicast benefits numerous data center applications that require group communication by eliminating sending unnecessary duplicated packets in the network, thus significantly reduces network traffic and improves application throughput. Meanwhile, most data center networks (DCNs) today adopt a multi-rooted tree structure called fat-tree, which utilizes rich path multiplicity to deliver high bisection bandwidth. However, without an efficient flow scheduling algorithm that appropriately routes multicast flows to achieve traffic load balance, heavy congestion may occur throughout the network, which prevents full utilization of such high degree of link parallelism and causes unpredictable network performance. Hence, in this paper we study multicast flow scheduling in fat-tree DCNs, where multicast flow requests arrive one by one without a priori knowledge of future traffic. To address the drastic traffic fluctuation in data centers, we consider a very general traffic model called hose traffic model, where the only assumption is that the total bandwidth demand of traffic that enters (leaves) an ingress (egress) link of each server at any time is bounded by the capacity of its network interface card. We present a low-complexity on-line multicast flow scheduling algorithm for fat-tree DCNs. The algorithm can achieve bounded congestion and efficient bandwidth utilization under any arbitrary sequence of multicast flow requests that satisfy the hose model. We also derive the bound on congestion that the algorithm can achieve in a fat-tree DCN. Finally, we evaluate the algorithm by an event-driven DCN simulator under various types of traffic patterns, and show that the algorithm achieves superior performance in terms of network throughput and evenness of traffic load distribution.