Cooperative Token-Ring Scheduling For Input-Queued Switches

We present a novel distributed scheduling paradigm for Internet routers with input-queued (IQ) switches, called cooperative token-ring (CTR) that provides significant performance improvement over existing scheduling schemes with comparable complexity. Many classical schedulers for IQ switches employ...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2009-03, Vol.58 (3), p.351-364
Main Authors: Gourgy, A., Szymanski, T.H.
Format: Article
Language:English
Subjects:
Algorithms
Arbiters
Complexity
Complexity theory
Hardware
Impedance matching
input-queued switch
parallel prefix
Ports
Processor scheduling
quality of service
Resource management
Scheduling
Studies
Switch scheduling
Switches
Throughput
Traffic engineering
Traffic flow
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a novel distributed scheduling paradigm for Internet routers with input-queued (IQ) switches, called cooperative token-ring (CTR) that provides significant performance improvement over existing scheduling schemes with comparable complexity. Many classical schedulers for IQ switches employ round-robin arbiters, which can be viewed as non-cooperative token-rings, where a separate token is used to resolve contention for each shared resource (e.g., an output port) and each input port acquires a token oblivious of the state of other input ports. Although classical round-robin scheduling schemes achieve fairness and high throughput for uniform traffic, under non-uniform traffic the performance degrades significantly. We show that by using a simple cooperative mechanism between the otherwise non-cooperative arbiters, the performance can be significantly improved. The CTR scheduler dynamically adapts to non-uniform traffic patterns and achieves essentially 100% throughput. The proposed cooperative mechanism is conceptually simple and is supported by experimental results. To provide adequate support for rate guarantees in IQ switches, we present a weighted cooperative token-ring, a simple hierarchical scheduling mechanism. Finally, we analyze the hardware complexity introduced by the cooperative mechanism and describe an optimal hardware implementation for an N times N switch with time complexity of Theta(log N) and circuit size of Theta(N log N) per port.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2008.178