File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

postgraduate thesis: Load-balanced switch design and data center networking

TitleLoad-balanced switch design and data center networking
Authors
Advisors
Advisor(s):Yeung, LK
Issue Date2014
PublisherThe University of Hong Kong (Pokfulam, Hong Kong)
Citation
He, C. [何春志]. (2014). Load-balanced switch design and data center networking. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5204908
AbstractHigh-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.
DegreeDoctor of Philosophy
SubjectComputer networks
Dept/ProgramElectrical and Electronic Engineering
Persistent Identifierhttp://hdl.handle.net/10722/198826

 

DC FieldValueLanguage
dc.contributor.advisorYeung, LK-
dc.contributor.authorHe, Chunzhi-
dc.contributor.author何春志-
dc.date.accessioned2014-07-10T04:10:18Z-
dc.date.available2014-07-10T04:10:18Z-
dc.date.issued2014-
dc.identifier.citationHe, C. [何春志]. (2014). Load-balanced switch design and data center networking. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b5204908-
dc.identifier.urihttp://hdl.handle.net/10722/198826-
dc.description.abstractHigh-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.-
dc.languageeng-
dc.publisherThe University of Hong Kong (Pokfulam, Hong Kong)-
dc.relation.ispartofHKU Theses Online (HKUTO)-
dc.rightsThe author retains all proprietary rights, (such as patent rights) and the right to use in future works.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subject.lcshComputer networks-
dc.titleLoad-balanced switch design and data center networking-
dc.typePG_Thesis-
dc.identifier.hkulb5204908-
dc.description.thesisnameDoctor of Philosophy-
dc.description.thesislevelDoctoral-
dc.description.thesisdisciplineElectrical and Electronic Engineering-
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.5353/th_b5204908-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats