A near optimal scheduler for switch-memory-switch routers

ABSTRACT

We present a simple and near optimal randomized parallel scheduling algorithm for scheduling packets in routers based on the Switch-Memory-Switch (SMS)architecture, which emulates 'output queuing' by using a collection of small memories within the switch to buffer packets, and which forms the basis of the fastest routers in use today. For a router with N inputs and N outputs, our algorithm computes the schedule in O(log* N) rounds, where a round is a communication of a few bits between input ports and memory together with simple local computation at the inputs and memory. Furthermore, by using an O(log* N) deep pipeline at each input, our algorithm computes the schedule in a constant number of rounds. Our pipelined algorithm is quite simple and achieves optimal (i.e.,constant) throughput with a tiny O(log* N) delay.We show that the total amount of buffer memory required by our algorithm is close to the minimum required. We also show that the number of buffer memories is within an εN additive term of 2N -- 1, for any positive constant ù>0 (and is within an additive term of o(N)for the basic scheduler), where 2N -- 1 is the minimum number of memories needed under adversarial placement of packets. Furthermore we show that the number of extra memories that we use over the minimum of N that is required in the offline version, is within a constant factor of the minimum required by any on-line scheduler, even if that scheduler is allowed to fail occasionally.Our scheduling algorithm is randomized and works with high probability in N. We also prove that it has the 'self-stabilizing' property, i.e., it resumes its normal behavior if occasional lapses occur due to the probabilistic nature of the algorithm.

REFERENCES

• 1: Noga Alon and Joel H. Spencer. The Probabilistic Method. Wiley, John & Sons, Incorporated, 2000.
• 2: Thomas E. Anderson , Susan S. Owicki , James B. Saxe , Charles P. Thacker, High-speed switch scheduling for local-area networks, ACM Transactions on Computer Systems (TOCS), v.11 n.4, p.319-352, Nov. 1993 [doi>10.1145/161541.161736]
• 3: A. Aziz, A. Prakash, and V. Ramachandran. A log log N stage pipelined scheduler for SMS architecture. manuscript, November 2002.
• 4: R. Barker, P. Massiglia, and L. Krantz. Storage Area Networking Essentials. McGraw-Hill, 2001.
• 5: C.-S. Chang, D.-S. Lee, and Y.-S. Jou. Load balanced Birkhoff-von Neumann switches, part I: one-stage buffering. Computer Communications, 2001.
• 6: C.-S. Chang, D.-S. Lee, and C.-M. Lien. Load balanced Birkhoff-von Neumann switches, part II: multi-stage buffering. Computer Communications, 2001.
• 7: S.-T. Chuang, A. Goel, N. McKeown, and B. Prabhakar. Matching output queueing with a combined input output queued switch. In IEEE Infocom, 1999.
• 8: Artur Czumaj , Friedhelm Meyerauf der, Contention Resolution in Hashing Based Shared Memory Simulations, SIAM Journal on Computing, v.29 n.5, p.1703-1739, March 2000 [doi>10.1137/S009753979529564X]
• 9: J. Duato. Interconnection Networks. Morgan-Kaufmann, 2002.
• 10: A. E. Eckberg and T. C. Hou. Effects of output buffer sharing on buffer requirements in an atdm packet switch. In IEEE Infocom, 1988.
• 11: M. Farley. Building storage area networks. McGraw-Hill, 2001.
• 12: W. Futral. InfiniBand Architecture: Development and Deployment--A Strategic Guide to Server I/O Solutions. Intel Press, 2001.
• 13: John L. Hennessy , David A. Patterson, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 02
• 14: M. Hluchyj and M. Karol. Queueing in high-performance packet switches. IEEE Journal on Selected Areas in Communications, 6(9), December 1988.
• 15: S. Keshav, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 16: S. Keshav and R. Sharma. Issues and Trends in Router Design. IEEE Communication Magazine, 1998.
• 17: G. Lev, N. Pippenger, and L. Valiant. A fast parallel algorithm for routing in permutation networks. IEEE Transactions on Computers, 30(2), February 1981.
• 18: Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
• 19: 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]
• 20: N. McKeown, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. In IEEE Infocom, 1996.
• 21: Nick McKeown , Martin Izzard , Adisak Mekkittikul , William Ellersick , Mark Horowitz, Tiny Tera: A Packet Switch Core, IEEE Micro, v.17 n.1, p.26-33, January 1997 [doi>10.1109/40.566194]
• 22: Juniper Networks. High speed switching device. US Patent 5,905,726, 1999.
• 23: A. Pattavina. Switching Theory. Wiley, John & Sons, Incorporated, 2000.
• 24: Larry L. Peterson , Bruce S. Davie, Computer networks: a systems approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 25: A. Prakash, S. Sharif, and A. Aziz. An O(lg2n) algorithm for output queuing. In IEEE Infocom, 2002.
• 26: Rajiv Ramaswami , Kumar N. Sivarajan, Optical networks: a practical perspective, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 27: Thomas E. Stern , Krishna Bala, Multiwavelength Optical Networks: A Layered Approach, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 28: J. van Lint and R. Wilson. A Course in Combinatorics. Cambridge University Press, 1992.
• 29: A. Wilson, J. Schade, and R. Thornburg. Introduction to PCI Express. Intel Press, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.6 Internetworking
          Subjects: Routers

General Terms:
Algorithms, Design, Performance

Keywords:
matching, parallelism, randomization, routers, schedulers