Rate Guarantees and Overload Protection in Input-Queued Switches

Hari Balakrishnan, Srinivas Devadas, Douglas Ehlert, Arvind
IEEE Infocom 2004, Hong Kong, China, March 2004

Despite increasing bandwidth demand and the significant research and commercial activity in large-scale Terabit routers for multi-gigabit/s links, many current switch designs do not provide adequate support for rate guarantees. In particular, designs based on the popular combined-input/output-queueing (CIOQ) paradigm have unpredictable performance despite implementing sophisticated scheduling schemes on egress links, because the crossbar arbitration between ingress and egress links is done without regard to desired rate guarantees or prevailing traffic conditions. This paper describes the design of an inputqueued switch system and its associated arbitration and rate allocation algorithms that achieve both absolute rate guarantees and proportional bandwidth sharing even under overloaded or adversarial traffic. Our algorithms are simple and scalable and require a switch speedup of two to provide rate guarantees; we give the theoretical justification and report on simulation results that justify our claims. A semiconductor chipset based on variants of these algorithms for routers with an aggregate capacity of 160 Gbps with links up to 10 Gbps is now commercially available, and a second-generation chipset supporting 640 Gbps will be available soon.

[PDF (239KB)]

Bibtex Entry:

   author =       "Hari Balakrishnan and Srinivas Devadas and Douglas Ehlert and Arvind ",
   title =        "{Rate Guarantees and Overload Protection in Input-Queued Switches}",
   booktitle =    {IEEE Infocom 2004},
   year =         {2004},
   month =        {March},
   address =      {Hong Kong, China}