Logarithmic Delay for $N \times N$ Packet Switches Under the Crossbar Constraint
Authors:
- Eytan ModianoEMEytan Modiano
- 18 June 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 15 (3) , 657-668
Abstract
We consider the fundamental delay bounds for scheduling packets In an N times N packet switch operating under the crossbar constraint. Algorithms that make scheduling decisions without considering queue backlog are shown to incur an average delay of at least O(N). We then prove that O(log(N)) delay is achievable with a simple frame based algorithm that uses queue backlog information. This is the best known delay bound for packet switches, and is the first analytical proof that sublinear delay is achievable in a packet switch with random inputs.Keywords
This publication has 19 references indexed in Scilit:
- Multicast schedulers for ATM switches with multiple input queues2005
- Scheduling reserved traffic in input-queued switches: new delay bounds via probabilistic techniques2004
- Providing guaranteed rate services in the load balanced Birkhoff-von Neumann switches2004
- Multicast traffic in input-queued switches: Optimal scheduling and maximum throughputIEEE/ACM Transactions on Networking, 2003
- Optimum scheduling and memory management in input queued switches with finite buffer space2003
- Achieving stability in networks of input-queued switches2002
- On the stability of input-queued switches with speed-upIEEE/ACM Transactions on Networking, 2001
- Scheduling nonuniform traffic in a packet-switching system with small propagation delayIEEE/ACM Transactions on Networking, 1997
- Incremental time-slot assignment in SS/TDMA satellite systemsIEEE Transactions on Communications, 1991
- Minimizing Packet Waiting Time in a Multibeam Satellite SystemIEEE Transactions on Communications, 1982