Thomas Bonald
Abstract
The performance of input-queued packet switches critically depends on the scheduling scheme that connects the input ports to the output ports. We show that, when packets are switched asynchronously, simple scheduling schemes where contention is solved locally at each input or output can achieve rate optimality, without any speed-up of the internal transmission rate.
- T. Anderson, S. Owicki, J. Saxe, and C. Thacker. High-speed switch scheduling for local-area networks. ACM Transactions on Computer Systems, 11(4):319--352, Nov. 1993. Google Scholar
Digital Library
- A. Bianco, D. Cuda, P. Giaccone, and F. Neri. Asynchronous vs synchronous input-queued switches. In IEEE GLOBECOM, 2010.Google ScholarCross Ref
- A. Brzezinski and E. Modiano. Greedy weighted matching for scheduling the input-queued switch. In CISS, 2006.Google ScholarCross Ref
- J. Dai. On positive Harris recurrence of multiclass queueing networks: a unified approach via uid limit models. Annals of Applied Probabilities, 5:49--77, 1995.Google ScholarCross Ref
- J. Dai and B. Prabhakar. The throughput of data switches with and without speedup. In IEEE INFOCOM, 2000.Google ScholarCross Ref
- A. Dimakis and J. Walrand. Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using uid limits. Advances in Applied Probability, 38, 2006.Google Scholar
- M. Feuillet, A. Proutiére, and P. Robert. Random capture algorithms: Fluid limits and stability. In Information Theory and Applications Workshop, 2010.Google ScholarCross Ref
- Y. Ganjali, A. Keshavarzian, and D. Shah. Cell switching versus packet switching in input-queued switches. IEEE/ACM Transactions on Networking, 13(4):782--789, 2005. Google ScholarDigital Library
- L. Jiang, D. Shah, J. Shin, and J. Walrand. Distributed random access algorithm: Scheduling and congestion control. IEEE Transactions on Information Theory, 56(12):6182--6207, 2010. Google ScholarDigital Library
- L. Lovász and M. Plummer. Matching theory. North-Holland: Elsevier Science Publishers, 1986.Google Scholar
- S. T. Maguluri, B. Hajek, and R. Srikant. The stability of longest-queue-first scheduling with variable packet sizes. In IEEE CDC, 2011.Google ScholarCross Ref
- N. McKeown. The iSLIP scheduling algorithm for input-queued switches. IEEE/ACM Transactions on Networking, 7(2):188--201, 1999. Google ScholarDigital Library
- N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. IEEE Transactions on bCommunications, 47(8):1260--1267, Aug 1999.Google ScholarCross Ref
- P. Robert. Stochastic networks and queues. Springer, 2003.Google ScholarCross Ref
- L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37:1936--1948, 1992.Google ScholarCross Ref
Index Terms
- RateOptimal scheduling schemes for asynchronous InputQueued packet switches
Recommendations
Localized asynchronous packet scheduling for buffered crossbar switches
ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systemsBuffered crossbar switches are a special type of crossbar switches. In such a switch, besides normal input queues and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crosspoint buffers, output and input ...
Online Packet Scheduling for CIOQ and Buffered Crossbar Switches
SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and ArchitecturesWe consider the problem of online packet scheduling in Combined Input and Output Queued (CIOQ) and buffered crossbar switches. In the widely used CIOQ switches, packet buffers (queues) are placed at both input and output ports. An N x N CIOQ switch has ...
Comments