Bounds on delays and queue lengths in input-queued cell switches

ABSTRACT

In this article, we develop a general methodology, mainly based upon Lyapunov functions, to derive bounds on average delays, and on averages and variances of queue lengths in complex systems of queues. We apply this methodology to cell-based switches and routers, considering first output-queued (OQ) architectures, in order to provide a simple example of our methodology, and then both input-queued (IQ), and combined input/output queued (CIOQ) architectures. These latter switching architectures require a scheduling algorithm to select at each slot a subset of input-buffered cells that can be transferred toward output ports. Although the stability properties (i.e., the limit throughput) of IQ and CIOQ cell-based switches were already studied for several classes of scheduling algorithms, very few analytical results concerning cell delays or queue lengths are available in the technical literature. We concentrate on Maximum Weight Matching (MWM) and Maximal Size Matching (mSM) scheduling algorithms; while the former was proved to maximize throughput, the latter allows simpler implementation. The derived bounds are shown to be rather tight when compared to simulation results.

REFERENCES

• 1: Ajmone Marsan, M., Bianco, A., Filippi, E., Giaccone, P., Leonardi, E., and Neri, F. 1999a. On the behavior of input queuing switch architectures. Europ. Trans. Telecommun. (ETT) 10, 2 (Mar.), 111--124.
• 2: Ajmone Marsan, M., Bianco, A., Leonardi, E., and Milia, L. 1999b. RPA: A flexible scheduling algorithm for input buffered switches. IEEE Trans. Commun. 47, 12 (Dec.), 1921--1933.
• 3: Chen, H., Lambert, J., and Pitsilledes, A. 1995. RC-BB switch. A high performance switching network for B-ISDN. In Procedings of IEEE Globecom (Singapore). IEEE Communication Society Press, Piscataway, NJ, pp. 275--279.
• 4: Chuang, S. T., Goel, A., Mckeown, N., and Prabhakar, B. 1999. Matching output queuing with combined input and output queuing. IEEE J. Select. Areas Commun. 17, 6 (Dec.), 1030--1039.
• 5: Dai, J. G., and Prabhakar, B. 2000. The throughput of data switches with and without speedup. In Procedings of IEEE Infocom (Tel Aviv, Israel, Mar.). IEEE Communication Society Press, Piscataway, NJ, pp. 556--564.
• 6: Duan, H., Lockwood, J. W., and Mo Kang, S. 1998. Matrix Unit Cell Scheduler (MUCS) for input-buffered ATM switches. IEEE Commun. Lett. 2, 1 (Jan.), 20--23.
• 7: Guy Fayolle, On random walks arising in queueing systems: ergodicity and transience via quadratic forms as Lyapunov functions—Part I, Queueing Systems: Theory and Applications, v.5 n.1-3, p.167-184, November 1989
• 8: Karol, M., Hluchyj, M., and Morgan, S. 1987. Input versus output queuing on a space division switch. IEEE Trans. Commun. 35, 12 (Dec.), 1347--1356.
• 9: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 10: Kushner, H. J. 1967. Stochastic Stability and Control, Academic Press, Orlando, FL.
• 11: Richard O. LaMaire , Dimitrios N. Serpanos, Two-dimensional round-robin schedulers for packet switches with multiple input queues, IEEE/ACM Transactions on Networking (TON), v.2 n.5, p.471-482, Oct. 1994 [doi>10.1109/90.336324]
• 12: Emilio Leonardi , Marco Mellia , Fabio Neri , Marco Ajmone Marsan, On the stability of input-queued switches with speed-up, IEEE/ACM Transactions on Networking (TON), v.9 n.1, p.104-118, Feb., 2001 [doi>10.1109/90.909028]
• 13: Leonardi, E., Mellia, M., Neri, F., and Ajmone Marsan, M. 2001b. Bounds on average delays and queue size averages and variances in input queued cell-based switches. In Procedings of IEEE Infocom (Anchorage, AK., Apr.). IEEE Communication Society Press, Piscataway, NJ, pp. 1095--1103.
• 14: Nicholas William McKeown, Scheduling algorithms for input-queued cell switches, University of California at Berkeley, Berkeley, CA, 1996
• 15: Nick McKeown, The iSLIP scheduling algorithm for input-queued switches, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.188-201, April 1999 [doi>10.1109/90.769767]
• 16: McKeown, N., and Mekkittikul, A. 1998. A pratical scheduling algorithm to achieve 100% throughput in input-queued switches. In Procedings of IEEE Infocom (San Francisco, Calif., Apr.). IEEE Communication Society Press, Piscataway, NJ, pp. 792--799.
• 17: McKeown, N., Mekkittikul, A., Anantharam, V., and Walrand, J. 1999. Achieving 100% throughput in an input-queued switch, IEEE Trans. Commun. 47, 8 (Aug.), 1260--1272.
• 18: Schoenen, R., Post, G., and Sander, G. 1999. Weighted arbitration algorithms with priorities for input-queued switches with 100% throughput. In Procedings of 3rd IEEE International Workshop on Broadband Switching Systems (Kingston, Ontario, Canada, Jun.). IEEE Communication Society Press, Piscataway, NJ.
• 19: Shah, D., and Kopikare, M. 2002. Delay bounds for approximate maximum weight matching algorithms for input queued switches. In Procedings of IEEE Infocom (New York, Jun). IEEE Communication Society Press, Piscataway, NJ, pp. 1024--1031.
• 20: D. Stiliadis , A. Varma, Providing bandwidth guarantees in an input-buffered crossbar switch, Proceedings of the Fourteenth Annual Joint Conference of the IEEE Computer and Communication Societies (Vol. 3)-Volume, p.960, April 02-06, 1995
• 21: Y. Tamir , H. C. Chi, Symmetric Crossbar Arbiters for VLSI Communication Switches, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.13-27, January 1993 [doi>10.1109/71.205650]
• 22: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 23: Tassiulas, L., and Ephremides, A. 1992. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automat. Cont. 37, 12 (Dec.), 1936--1948.
• 24: Zhang, H. 1995. Service disciplines for guaranteed performance service in packet-switching networks. Proc. IEEE 83, 10 (Oct.), 1374--1399.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Performance, Theory

Keywords:
Performance evaluation, delay bounds, input queued switches, scheduling