An O(1) scheduling algorithm for variable-size packet switching systems

Shunyuan Ye, Yanming Shen, Shivendra Panwar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Internet traffic has increased at a very fast pace in recent years. The traffic demand requires that future packet switching systems should be able to switch packets in a very short time, i.e., just a few nanoseconds. Algorithms with lower computation complexity are more desirable for this high-speed switching design. Among the existing algorithms that can achieve 100% throughut for input-queued switches for any admissible Bernoulli traffic, ALGO3 [1] and EMHW [2] have the lowest computation complexity, which is O(logN), where N is the number of ports in the switch. In this paper, we propose a randomized scheduling algorithm, which can also stabilize the system for any admissible traffic that satisfies the strong law of large number. The algorithm has a complexity of O(1). Since the complexity does not increase with the size of a switch, the algorithm is highly scalable and a good choice for future high-speed switch designs. We also show that the algorithm can be implemented in a distributed way by using a low-rate control channel. Simulation results show that the algorithm can provide a good delay performance as compared to algorithms with higher computation complexity.

Original languageEnglish (US)
Title of host publication2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
Pages1683-1690
Number of pages8
DOIs
StatePublished - 2010
Event48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 - Monticello, IL, United States
Duration: Sep 29 2010Oct 1 2010

Publication series

Name2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010

Other

Other48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010
CountryUnited States
CityMonticello, IL
Period9/29/1010/1/10

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'An O(1) scheduling algorithm for variable-size packet switching systems'. Together they form a unique fingerprint.

  • Cite this

    Ye, S., Shen, Y., & Panwar, S. (2010). An O(1) scheduling algorithm for variable-size packet switching systems. In 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 (pp. 1683-1690). [5707119] (2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010). https://doi.org/10.1109/ALLERTON.2010.5707119