2004 · 22 citations · 12 references
ComputingComputer ScienceComputer SystemsComputer NetworksQueuing TheorySchedulingCommunication OverheadCongestion ControlDistributed SchedulingQueueing NetworksQueueing SystemsQueueing TheoryBandwidthBandwidth OverheadBandwidth UtilizationCommunication Overhead ReductionReallocationSwitch Fabric ArchitectureSwitch Fabric DesignSwitch Scheduling
This paper presents and evaluates distributed queueing algorithms for regulating the flow of traffic through large, high performance routers. Distributed queueing has a similar objective to crossbar-scheduling mechanisms used in routers with relatively small port counts, and shares some common high level characteristics. However, the need to minimize communication overhead rules out the iterative methods that are typically used for crossbar scheduling, while the ability to sub-divide the available bandwidth among different ports provides a degree of freedom that is absent in the crossbar scheduling context, where inputs must be matched to outputs. Our algorithms are based on four ideas (1) backlog-proportional-allocation of output bandwidth, (2) urgency-proportional-allocation of input bandwidth, (3) dynamic reallocation of bandwidth and (4) deferred underflow. Our algorithms guarantee congestion-free operation of the switch fabric. Our performance results show that for uniform random traffic, even a very modest speedup is sufficient to reduce the loss of output link bandwidth due to sub-optimal rate allocation to negligible levels, and that even under extreme conditions, a speedup of two is sufficient to eliminate such bandwidth loss.
12
WF/sup 2/Q: worst-case fair weighted fair queueing
J.C.R. Bennett, Hui Zhang · 2002 · 1.1K citations
High-speed switch scheduling for local-area networks
Thomas E. Anderson, Susan Owicki, James B. Saxe et al. · ACM Transactions on Computer Systems · 1993 · 896 citations · Full text
Achieving 100% throughput in an input-queued switch
Nick McKeown, V. Anantharam, Jean Walrand · 2002 · 512 citations