Load-balanced switch design and data center networking

Abstract

High-speed routers and high-performance data centers share a common system-level architecture in which multiple processing nodes are connected by an interconnection network for high-speed communications. Load balancing is an important technique for maximizing throughput and minimizing delay of the interconnection network. In this thesis, efficient load balancing schemes are designed and analyzed for next-generation routers and data centers.

In high-speed router design, two preferred switch architectures are input-queued switch and load-balanced switch. In an input-queued switch, time-domain load balancing can be carried out by an iterative algorithm that schedules packets for sending in different time slots. The complexity of an iterative algorithm increases rapidly with the number of scheduling iterations. To address this problem, a single-iteration scheduling algorithm called D-LQF is designed, in which exhaustive service policy is adopted for reusing the matched input-output pairs in the previous time slots to grow the match size.

Unlike an input-queued switch, a load-balanced switch consists of two stages of crossbar switch fabrics, where load balancing is carried out in both time and space domains. Among various load-balanced switches, the feedback-based switch gives the best delay-throughput performance. In this thesis, the feedback-based switch is enhanced in three aspects. Firstly, we focus on reducing its switch fabric complexity. Instead of using crossbars, a dual-banyan network is proposed. The complexity of dual-banyan can be further reduced by merging the two banyans to form a Clos network, resulting in a Clos-banyan network. Secondly, we target at improving the delay performance of the feedback-based switch. A Clos-feedback switch architecture is devised where each switch module in the Clos network is a small feedback-based switch. With application-flow based load balancing, packet order is ensured and the average packet delay is reduced from O(N) to O(n), where N and n are the switch and switch module sizes, respectively. Thirdly, we extend the feedback-based switch to support multicast traffic. Based on the notion of pointer-based multicast VOQ, an efficient multicast scheduling algorithm with packet replication at the middle-stage ports only is proposed. In order to provide close-to-100% throughput for any admissible multicast traffic patterns, a three-stage implementation of feedback-based switch is also designed.

In designing load balancing schemes for data centers, we focus on the most popular fat-tree based data centers. Notably, packet-based load balancing is widely considered infeasible for data centers. This is because the associated packet out-of-order problem will cause unnecessary TCP fast retransmits, and as a result, severely undermine TCP performance. In this thesis, we show that if packet-based load balancing is performed properly, the packet out-of-order problem can be easily addressed by slightly increasing the number of duplicate ACKs required for triggering fast retransmit. Admittedly, in case of a real packet loss, the loss recovery time will be increased. But our simulation results show that such an increase is far less than the reduction in the network queueing delay (due to a better load-balanced network). As compared to a flow-based load balancing scheme, our packet-based scheme consistently provides significantly higher goodput and noticeably smaller delay.