Fast and noniterative scheduling in input-queued switches: Supporting QoS

Kevin F. Chen; Edwin H.M. Sha; S. Q. Zheng

doi:10.1016/j.comcom.2008.12.008

Fast and noniterative scheduling in input-queued switches: Supporting QoS

Kevin F. Chen^*, Edwin H.M. Sha, S. Q. Zheng

^*Corresponding author for this work

University of Texas at Dallas

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

We report three fast and scalable scheduling algorithms that provide exact bandwidth guarantee, low delay bound, and reasonable jitter in input-queued switches. The three schedulers find a maximum input/output matching in a single iteration. They sustain 100% throughput under both uniform and bursty traffic. They work many times faster than existing scheduling schemes and their speed does not degrade with increased switch size. SRA and SRA+ algorithms are of O(1) time complexity and can be implemented in simple hardware. SRA tends to incur different delays to flows of different classes of service due to their different subscribed portions of the total bandwidth. SRA+, a weighted version of SRA, operates on cells that arrive uniformly and on cells of packets such that the cells of whole packets are switched contiguously. SRA+ improves over SRA in that all flows undergo the same delays regardless of their bandwidth shares. The schedulers operate on queue groups at the crossbar arbiters in a distributed manner.

Original language	English
Pages (from-to)	834-846
Number of pages	13
Journal	Computer Communications
Volume	32
Issue number	5
DOIs	https://doi.org/10.1016/j.comcom.2008.12.008
State	Published - 27 Mar 2009
Externally published	Yes

Keywords

Fabric scheduler
Quality of service
Switch architecture

Access to Document

10.1016/j.comcom.2008.12.008

Cite this

@article{903c25d3f095455880f887d18d720d4a,

title = "Fast and noniterative scheduling in input-queued switches: Supporting QoS",

abstract = "We report three fast and scalable scheduling algorithms that provide exact bandwidth guarantee, low delay bound, and reasonable jitter in input-queued switches. The three schedulers find a maximum input/output matching in a single iteration. They sustain 100\% throughput under both uniform and bursty traffic. They work many times faster than existing scheduling schemes and their speed does not degrade with increased switch size. SRA and SRA+ algorithms are of O(1) time complexity and can be implemented in simple hardware. SRA tends to incur different delays to flows of different classes of service due to their different subscribed portions of the total bandwidth. SRA+, a weighted version of SRA, operates on cells that arrive uniformly and on cells of packets such that the cells of whole packets are switched contiguously. SRA+ improves over SRA in that all flows undergo the same delays regardless of their bandwidth shares. The schedulers operate on queue groups at the crossbar arbiters in a distributed manner.",

keywords = "Fabric scheduler, Quality of service, Switch architecture",

author = "Chen, \{Kevin F.\} and Sha, \{Edwin H.M.\} and Zheng, \{S. Q.\}",

year = "2009",

month = mar,

day = "27",

doi = "10.1016/j.comcom.2008.12.008",

language = "英语",

volume = "32",

pages = "834--846",

journal = "Computer Communications",

issn = "0140-3664",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Fast and noniterative scheduling in input-queued switches

T2 - Supporting QoS

AU - Chen, Kevin F.

AU - Sha, Edwin H.M.

AU - Zheng, S. Q.

PY - 2009/3/27

Y1 - 2009/3/27

N2 - We report three fast and scalable scheduling algorithms that provide exact bandwidth guarantee, low delay bound, and reasonable jitter in input-queued switches. The three schedulers find a maximum input/output matching in a single iteration. They sustain 100% throughput under both uniform and bursty traffic. They work many times faster than existing scheduling schemes and their speed does not degrade with increased switch size. SRA and SRA+ algorithms are of O(1) time complexity and can be implemented in simple hardware. SRA tends to incur different delays to flows of different classes of service due to their different subscribed portions of the total bandwidth. SRA+, a weighted version of SRA, operates on cells that arrive uniformly and on cells of packets such that the cells of whole packets are switched contiguously. SRA+ improves over SRA in that all flows undergo the same delays regardless of their bandwidth shares. The schedulers operate on queue groups at the crossbar arbiters in a distributed manner.

AB - We report three fast and scalable scheduling algorithms that provide exact bandwidth guarantee, low delay bound, and reasonable jitter in input-queued switches. The three schedulers find a maximum input/output matching in a single iteration. They sustain 100% throughput under both uniform and bursty traffic. They work many times faster than existing scheduling schemes and their speed does not degrade with increased switch size. SRA and SRA+ algorithms are of O(1) time complexity and can be implemented in simple hardware. SRA tends to incur different delays to flows of different classes of service due to their different subscribed portions of the total bandwidth. SRA+, a weighted version of SRA, operates on cells that arrive uniformly and on cells of packets such that the cells of whole packets are switched contiguously. SRA+ improves over SRA in that all flows undergo the same delays regardless of their bandwidth shares. The schedulers operate on queue groups at the crossbar arbiters in a distributed manner.

KW - Fabric scheduler

KW - Quality of service

KW - Switch architecture

UR - https://www.scopus.com/pages/publications/61349088567

U2 - 10.1016/j.comcom.2008.12.008

DO - 10.1016/j.comcom.2008.12.008

M3 - 文章

AN - SCOPUS:61349088567

SN - 0140-3664

VL - 32

SP - 834

EP - 846

JO - Computer Communications

JF - Computer Communications

IS - 5

ER -

Fast and noniterative scheduling in input-queued switches: Supporting QoS

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this