### 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 language | English (US) |
---|---|

Title of host publication | 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 |

Pages | 1683-1690 |

Number of pages | 8 |

DOIs | |

State | Published - 2010 |

Event | 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 - Monticello, IL, United States Duration: Sep 29 2010 → Oct 1 2010 |

### Publication series

Name | 2010 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 |
---|

### Other

Other | 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2010 |
---|---|

Country | United States |

City | Monticello, IL |

Period | 9/29/10 → 10/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

*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