Scheduling policies for CIOQ switches

ABSTRACT

Combined input and output queued (CIOQ) architectures with a moderate fabric speedup S>1 have come to play a major role in the design of high performance switches. The switch policy that controls such switches must consist of two components. A buffer management policy that controls admission to buffers, and a scheduling policy that schedules the transfer of packets from input buffers to output buffers. The goal of the switch policy is to maximize the throughput of the switch. When all packets have a uniform value (or importance), this corresponds to the number of packets sent from the switch. When packets have variable values, this corresponds to the total value of the packets sent.We mainly consider switches with virtual output queuing (VOQ) at the inputs. For the case of packets with uniform values we present a switch policy that is 3-competitive for any speedup. For the case of packets with variable values we propose two preemptive switch policies. One achieves a competitive ratio of 4S, and the other achieves a competitive ratio of 8min(k, 2log α), where k is the number of distinct packet values and α is the ratio between the largest and smallest values.

REFERENCES

• 1: William Aiello , Rafail Ostrovsky , Eyal Kushilevitz , Adi Rosén, Dynamic routing on networks with fixed-size buffers, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: W. A. Aiello, Y. Mansour, S. Rajagopolan and A. Rosén, "Competitive Queue Policies for Differentiated Services," Proceedings of INFOCOM 2000, pp. 431--440.
• 3: Nir Andelman , Yishay Mansour , An Zhu, Competitive queueing policies for QoS switches, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 4: 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]
• 5: M. Arpaci and J. A. Copeland, "Buffer Management for Shared-Memory ATM Switches," IEEE Communications Surveys, First Quarter 2000.
• 6: Yossi Azar , Yossi Richter, Management of multi-queue switches in QoS networks, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780556]
• 7: D. Black, S. Blake, M. Carlson, E. Davies, Z. Wang and W. Weiss, "An Architecture for Differentiated Services," Internet RFC 2475, December 1998.
• 8: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 9: Anna Charny , David D. Clark, Providing qos guarantees in input-buffered crossbar switches with speedup, 1998
• 10: S. T. Chuang, A. Goel, N. McKeown and B. Prabhakar, "Matching Output Queueing with a Combined Input Output Queued Switch," IEEE Journal on Selected Areas in Communications, pp. 1030--1039, vol. 17, Dec. 1999.
• 11: J. G. Dai and B. Prabhakar, "The Throughput of Data Switches with and without Speedup," Proceedings of INFOCOM 2000.
• 12: Shlomi Dolev , Alexander Kesselman, Bounded latency scheduling scheme for ATM cells, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.32 n.3, p.325-331, March 2000 [doi>10.1016/S1389-1286(00)00002-5]
• 13: P. Giaccone, E. Leonardi, B. Prabhakar and D. Shah, "Delay Performance of High-speed Packet Switches with Low Speedup," Proceedings of the IEEE GLOBECOM 2002, Taipei, Taiwan, November 2002.
• 14: Ellen L. Hahne , Alexander Kesselman , Yishay Mansour, Competitve buffer management for shared-memory switches, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.53-58, July 2001, Crete Island, Greece [doi>10.1145/378580.378589]
• 15: M. Karol, M. Hluchyj and S. Morgan, "Input versus Output Queuing an a Space Division Switch", IEEE Trans. Communications, Vol. 35, pp. 1347--1356, 1987.
• 16: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer overflow management in QoS switches, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.520-529, July 2001, Hersonissos, Greece [doi>10.1145/380752.380847]
• 17: Alexander Kesselman , Yishay Mansour, Loss-bounded analysis for differentiated services, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.591-600, January 07-09, 2001, Washington, D.C., United States
• 18: A. Kesselman and Y. Mansour, "Harmonic Buffer Management Policy for Shared Memory Switches," Proceedings of INFOCOM 2002.
• 19: M. A. Marsan, A. Bianco, E. Filippi, P. Giaccone, E. Leonardi and F. Neri, "A Comparison of Input Queuing Cell Switch Architectures," IEEE BSS'99, 3rd International Workshop on Broadband Switching Systems, Kingston, Canada, June 1999.
• 20: M. A. Marsan, A. Bianco, E. Leonardi and L. Milia, "RPA: A Flexible Scheduling Algorithm for Input Buffered Switches," IEEE Transactions on Communications, Vol.47, No.12, pp.1921--1933, December 1999.
• 21: Yishay Mansour , Boaz Patt-Shamir , Ofer Lapid, Optimal smoothing schedules for real-time streams (extended abstract), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.21-29, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343511]
• 22: Nicholas William McKeown, Scheduling algorithms for input-queued cell switches, University of California at Berkeley, Berkeley, CA, 1996
• 23: N. Mckeown and A. Mekkittikul, "A Starvation Free Algorithm for Achieving 100% Throughput in an Input Queued Switch," ICCCN 96, Washington, DC, Oct. 1996.
• 24: N. McKeown, P. Varaiya and J. Walrand, "Scheduling Cells in an Input-Queued Switch", IEEE Electronics Letters, pp. 2174--2175, Dec. 9th, 1993.
• 25: Vern Paxson , Sally Floyd, Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking (TON), v.3 n.3, p.226-244, June 1995 [doi>10.1109/90.392383]
• 26: B. Prabhakar and N. McKeown, "On the Speedup Required for Combined Input and Output Queued Switching," Automatica, Vol. 35, December 1999.
• 27: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 28: A. Veres and M. Boda, "The Chaotic Nature of TCP Congestion Control," Proceedings of INFOCOM 2000, pp. 1715--1723, March 2000.
• 29: J. Xie and C. T. Lea, "Speedup and buffer division in input/output queuing ATM switches," Proc. IEEE Global Telecommunications Conference, vol. 1a, pp. 49--53, 1999.
• 30: M. Yang and S. Q. Zheng, "Efficient Scheduling for CIOQ Switches with Space-division Multiplexing Speedup", to appear in INFOCOM 2003.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Performance

Keywords:
CIOQ switches, buffer management, competitive analysis, scheduling policies