Load-balanced three-stage switch

Abstract

A load-balanced two-stage switch is scalable and can provide close to 100% throughput. Its major problem is that packets can be mis-sequenced when they arrive at outputs. In a recent work, the packet mis-sequencing problem is elegantly solved by a feedback-based switch architecture. In this paper, we extend the feedback-based switch from two-stage to three-stage for further cutting down average packet delay while still ensuring in-order packet delivery and close to 100% throughput. The basic idea is to use the third stage switch to map heavy flows to experience less middle-stage delays. To identity heavy flows, an adaptive traffic estimation algorithm is proposed. To ensure maxmin fairness in bandwidth allocation under any inadmissible traffic pattern, an efficient fair scheduler is devised. © 2011 Elsevier Ltd. All rights reserved.