The algorithms described in this thesis are designed to schedule cells in a very high-speed, parallel, input-queued crossbar switch. We present several novel scheduling algorithms that we have devised, each aims to match the set of inputs of an input queued switch to the set of outputs more efficiently, fairly and quickly than existing techniques.
In Chapter 2 we present the simplest and fastest of these algorithms: SLIP--a parallel algorithm that uses rotating priority ("round-robin") arbitration. SLIP is simple: it is readily implemented in hardware and can operate at high speed. SLIP has high performance: for uniform i.i.d. Bernoulli arrivals, SLIP is stable for any admissible load, because the arbiters tend to desynchronize. We present analytical results to model this behavior. However, SLIP is not always stable and is not always monotonic: adding more traffic can actually make the algorithm operate more efficiently. We present an approximate analytical model of this behavior. SLIP prevents starvation: all contending inputs are eventually served. We present simulation results, indicating SLIP's performance. We argue that SLIP can be readily implemented for a 32 x 32 switch on a single chip.
In Chapter 3 we present i-SLIP, an iterative algorithm that improves upon SLIP by converging on a maximal size match. The performance of i-SLIP improves with up to log$\sb2N$ iterations. We show that although it has a longer running time than SLIP, an i-SLIP scheduler is little more complex to implement.
In Chapter 4 we describe maximum or maximal weight matching algorithms based on the occupancy of queues, or waiting times of cells. These algorithms are stable over a wider range of traffic loads. We describe two algorithms, longest queue first (LQF) and oldest cell first (OCF) and consider their performance. We prove that LQ although too complex to implement in hardware, is stable under all admissible i.i.d. offered loads. We consider two implementable, iterative algorithms i-LQF and i-OCF which converge on a maximal weight matching. Finally, we present two interesting implementations of the Gale-Shapley algorithm, designed to solve the stable marriage problem.
Cited By
- Liang C, Song X, Cheng J, Wang M, Liu Y, Liu Z, Zhao S and Cui Y NegotiaToR: Towards A Simple Yet Effective On-demand Reconfigurable Datacenter Network Proceedings of the ACM SIGCOMM 2024 Conference, (415-432)
- Song J, Han K, Kim D, Park C and Kim K (2018). Priority-based grant-aware scheduling for low-latency switching, Photonic Network Communications, 36:2, (175-186), Online publication date: 1-Oct-2018.
- Du Y and Veciana G (2018). Efficiency and Optimality of Largest Deficit First Prioritization, ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 3:3, (1-29), Online publication date: 30-Sep-2018.
- Gao Y An Adaptive Scheduling Algorithm for Multi-Priority Traffic in Load-Balanced Switch Proceedings of the 1st International Conference on Information Science and Systems, (200-203)
- Gong L, Tune P, Liu L, Yang S and Xu J (2017). Queue-Proportional Sampling, ACM SIGMETRICS Performance Evaluation Review, 45:1, (4-4), Online publication date: 18-Sep-2017.
- Hui X, Xue S, Su-zhi C and Yue-ying Z Implementation of Multi-Priority Variable-Length iSLIP Algorithm Based on FPGA Proceedings of the 2017 2nd International Conference on Multimedia Systems and Signal Processing, (26-30)
- Gong L, Tune P, Liu L, Yang S and Xu J (2017). Queue-Proportional Sampling, Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1:1, (1-33), Online publication date: 13-Jun-2017.
- Gong L, Tune P, Liu L, Yang S and Xu J Queue-Proportional Sampling Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, (4-4)
- Jeloka S, Das R, Dreslinski R, Mudge T and Blaauw D Hi-Rise Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture, (471-483)
- Gabale V, Chebrolu K, Raman B and Bijwe S (2012). PIP, ACM Transactions on Sensor Networks, 8:4, (1-34), Online publication date: 1-Sep-2012.
- Dai Z and Zhu J Saturating the transceiver bandwidth Proceedings of the ACM/SIGDA international symposium on Field Programmable Gate Arrays, (67-76)
- Sharma G, Joo C, Shroff N and Mazumdar R (2010). Joint congestion control and distributed scheduling for throughput guarantees in wireless networks, ACM Transactions on Modeling and Computer Simulation, 21:1, (1-25), Online publication date: 1-Dec-2010.
- Raman B, Chebrolu K, Bijwe S and Gabale V PIP Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems, (15-28)
- Ryu J, Joo C, Kwon T, Shroff N and Choi Y Distributed SINR based scheduling algorithm for multi-hop wireless networks Proceedings of the 13th ACM international conference on Modeling, analysis, and simulation of wireless and mobile systems, (376-380)
- Lin B and Keslassy I (2010). The concurrent matching switch architecture, IEEE/ACM Transactions on Networking (TON), 18:4, (1330-1343), Online publication date: 1-Aug-2010.
- Hu B and Yeung K (2010). Feedback-based scheduling for load-balanced two-stage switches, IEEE/ACM Transactions on Networking (TON), 18:4, (1077-1090), Online publication date: 1-Aug-2010.
- Chin K A new integrated unicast/multicast scheduler for input-queued switches Proceedings of the Eighth Australasian Symposium on Parallel and Distributed Computing - Volume 107, (13-20)
- Yang F, Wang Z, Chen J and Liu Y A parallel packet switch supporting differentiated QoS based on weighted layer assignment Proceedings of the 5th International Conference on Wireless communications, networking and mobile computing, (4286-4289)
- Joo C, Lin X and Shroff N (2009). Understanding the capacity region of the Greedy maximal scheduling algorithm in multihop wireless networks, IEEE/ACM Transactions on Networking (TON), 17:4, (1132-1145), Online publication date: 1-Aug-2009.
- Leconte M, Ni J and Srikant R Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computing, (165-174)
- Suryaputra S, Touch J and Bannister J The case of a precognition optical packet switch Proceedings of the 28th IEEE international conference on Computer Communications Workshops, (157-162)
- Yoshigoe K (2009). Trends in highly scalable crossbar-based packet switch architecture, Computer Communications, 32:4, (740-749), Online publication date: 1-Mar-2009.
- Guan H, Zhao Y, Wu J, Zhang X and Liu Z Packetized smooth switching for buffered crossbar switches Proceedings of the 19th IASTED International Conference on Parallel and Distributed Computing and Systems, (130-135)
- Mortensen B Combining aggregation and scheduling using an iterative maximal weight matching switch scheduler Proceedings of the 11th Conference on 11th WSEAS International Conference on Communications - Volume 11, (108-114)
- Fang L and Jing Z An immune clonal selection scheduling algorithm for input-queued switches Proceedings of the 6th international conference on Simulated Evolution And Learning, (790-797)
- Pan D and Yang Y Hardware Efficient Two Step Iterative Matching Algorithms for VOQ Switches Proceedings of the 12th International Conference on Parallel and Distributed Systems - Volume 1, (431-438)
- Nachiondo T, Flich J and Duato J Destination-Based HoL Blocking Elimination Proceedings of the 12th International Conference on Parallel and Distributed Systems - Volume 1, (213-222)
- Kesselman A and Rosén A (2006). Scheduling policies for CIOQ switches, Journal of Algorithms, 60:1, (60-83), Online publication date: 1-Jul-2006.
- Chang C, Lee D and Yue C (2006). Providing guaranteed rate services in the load balanced Birkhoff-von Neumann switches, IEEE/ACM Transactions on Networking (TON), 14:3, (644-656), Online publication date: 1-Jun-2006.
- Mhamdi L, Kachris C and Vassiliadis S A reconfigurable hardware based embedded scheduler for buffered crossbar switches Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, (143-149)
- Tsaur D, Cheng H, Liu C and Lin W A study of matching output queueing with a 3D-VOQ switch Proceedings of the 2006 international conference on Information Networking: advances in Data Communications and Wireless Networks, (429-439)
- Pan D and Yang Y Pipelined two step iterative matching algorithms for CIOQ crossbar switches Proceedings of the 2005 ACM symposium on Architecture for networking and communications systems, (41-50)
- Hoare R, Ding Z, Tung S, Melhem R and Jones A (2005). A framework for the design, synthesis and cycle-accurate simulation of multiprocessor networks, Journal of Parallel and Distributed Computing, 65:10, (1237-1252), Online publication date: 1-Oct-2005.
- Song Y and Pinkston T (2005). Distributed Resolution of Network Congestion and Potential Deadlock Using Reservation-Based Scheduling, IEEE Transactions on Parallel and Distributed Systems, 16:8, (686-701), Online publication date: 1-Aug-2005.
- Bonuccelli M and Urpi A (2005). Mesh of Trees Topology for Output Queued Switches, Cluster Computing, 8:1, (7-14), Online publication date: 1-Jan-2005.
- Guez D, Kesselman A and Rosén A Packet-mode policies for input-queued switches Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, (93-102)
- Kesselman A and Rosén A Scheduling policies for CIOQ switches Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, (353-362)
- Kim M and Park H An integrated scheduling for multiple loss priority traffic in E-PON OLT switches Proceedings of the 2003 international conference on Architectures for quality of service in the internet, (265-275)
- Rijpkema E, Goossens K, Radulescu A, Dielissen J, van Meerbergen J, Wielage P and Waterlander E Trade Offs in the Design of a Router with Both Guaranteed and Best-Effort Services for Networks on Chip Proceedings of the conference on Design, Automation and Test in Europe - Volume 1
- Mukherjee S, Silla F, Bannon P, Emer J, Lang S and Webb D (2002). A comparative study of arbitration algorithms for the Alpha 21364 pipelined router, ACM SIGOPS Operating Systems Review, 36:5, (223-234), Online publication date: 1-Dec-2002.
- Mukherjee S, Silla F, Bannon P, Emer J, Lang S and Webb D (2002). A comparative study of arbitration algorithms for the Alpha 21364 pipelined router, ACM SIGARCH Computer Architecture News, 30:5, (223-234), Online publication date: 1-Dec-2002.
- Oki E, Jing Z, Rojas-Cessa R and Chao H (2002). Concurrent round-robin-based dispatching schemes for Clos-network switches, IEEE/ACM Transactions on Networking (TON), 10:6, (830-844), Online publication date: 1-Dec-2002.
- Mukherjee S, Silla F, Bannon P, Emer J, Lang S and Webb D A comparative study of arbitration algorithms for the Alpha 21364 pipelined router Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, (223-234)
- Mukherjee S, Silla F, Bannon P, Emer J, Lang S and Webb D (2002). A comparative study of arbitration algorithms for the Alpha 21364 pipelined router, ACM SIGPLAN Notices, 37:10, (223-234), Online publication date: 1-Oct-2002.
- Chamberlain R, Franklin M and Baw C (2002). Gemini, IEEE Transactions on Parallel and Distributed Systems, 13:10, (1038-1055), Online publication date: 1-Oct-2002.
- Gura N and Eberle H The Least Choice First Scheduling Method for High-Speed Network Switche Proceedings of the 16th International Parallel and Distributed Processing Symposium
- Giaccone P, Shah D and Prabhakar B (2018). An Implementable Parallel Scheduler for Input-Queued Switches, IEEE Micro, 22:1, (19-25), Online publication date: 1-Jan-2002.
- Shah D, Giaccone P and Prabhakar B (2018). Efficient Randomized Algorithms for Input-Queued Switch Scheduling, IEEE Micro, 22:1, (10-18), Online publication date: 1-Jan-2002.
- Yun K (2018). A Terabit Multiservice Switch, IEEE Micro, 21:1, (58-70), Online publication date: 1-Jan-2001.
- Andrews M and Zhang L Stability results for networks with input and output blocking Proceedings of the thirtieth annual ACM symposium on Theory of computing, (369-377)
- McKeown N, Izzard M, Mekkittikul A, Ellersick W and Horowitz M (1997). Tiny Tera, IEEE Micro, 17:1, (26-33), Online publication date: 1-Jan-1997.
Index Terms
- Scheduling algorithms for input-queued cell switches
Recommendations
The Combined Input-Output Queued Crossbar Architecture for High-Radix On-Chip Switches
High-radix, single-chip routers have emerged as efficient building blocks for interconnection networks. Researchers believe that hierarchical switch architectures are needed at high radices as crossbars scale with the square of the router radix. This ...
Input-queued switches with logarithmic delay: necessary conditions and a reconfigurable scheduling algorithm
ANCS '08: Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications SystemsTypically, a scheduling algorithm for an n x n packet switch with a crossbar as the data fabric divides time into slots, each of duration tp sufficient to transmit a packet. If a scheduling round requires tr > tp time, then the switch can transmit ...