• DocumentCode
    1257304
  • Title

    Efficient randomized algorithms for input-queued switch scheduling

  • Author

    Shah, Devavrat ; Giaccone, Paolo ; Prabhakar, Balaji

  • Author_Institution
    Dept. of Comput. Sci., Stanford Univ., CA, USA
  • Volume
    22
  • Issue
    1
  • fYear
    2002
  • Firstpage
    10
  • Lastpage
    18
  • Abstract
    High-performance schedulers for input-queued (IQ) switches must find, for each time slot, a good matching between inputs and outputs to transfer packets. At high line rates or for large switches, finding good matchings is complicated. A suite of randomized algorithms for switch scheduling provides performance comparable to that of well-known, effective matching algorithms, yet is simple to implement
  • Keywords
    distributed algorithms; packet switching; queueing theory; randomised algorithms; scheduling; high-performance schedulers; input-queued switch scheduling; input-queued switches; large switches; matching algorithms; randomized algorithms; switch scheduling; time slot; transfer packets; Bipartite graph; Delay; Fabrics; Load management; Packet switching; Scalability; Scheduling algorithm; Spine; Switches; Throughput;
  • fLanguage
    English
  • Journal_Title
    Micro, IEEE
  • Publisher
    ieee
  • ISSN
    0272-1732
  • Type

    jour

  • DOI
    10.1109/40.988685
  • Filename
    988685
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1257304