An improved algorithm for CIOQ switches

ABSTRACT

The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, the most general model that has been investigated is the standard CIOQ (Combined Input and Output Queued) switch architecture with internal fabric speedup S ≥ 1. CIOQ switches, that comprise the backbone of packet routing networks, are N × N switches controlled by a switching policy that incorporates two components: Admission control and scheduling. An admission control strategy is essential to determine the packets stored in the FIFO queues in input and output ports, while the scheduling policy conducts the transfer of packets through the internal fabric, from input ports to output ports. The online problem of maximizing the total weighted throughput of CIOQ switches was recently investigated by Kesselman and Rosén [2003]. They presented two different online algorithms for the general problem that achieve non-constant competitive ratios (linear in either the speedup or the number of distinct values, or logarithmic in the value range). We introduce the first constant-competitive algorithm for the general case of the problem, with arbitrary speedup and packet values. Specifically, our algorithm is 8-competitive, and is also simple and easy to implement.

REFERENCES

• 1: Aiello, W., Mansour, Y., Rajagopolan, S., and Rosén, A. 2000. Competitive queue policies for differentiated services. In Proceedings of IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA, 431--440.
• 2: Susanne Albers , Markus Schmidt, On the performance of greedy algorithms in packet buffering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007366]
• 3: Nir Andelman, Randomized qeue management for DiffServ, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073972]
• 4: Andelman, N., and Mansour, Y. 2003. Competitive management of non-preemptive queues with multiple values. In Proceedings of the 17th International Symposium on Distributed Computing (DISC). ACM, New York, 166--180.
• 5: 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
• 6: Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001 [doi>10.1145/363647.363677]
• 7: Azar, Y., and Litichevskey, M. 2004. Maximizing throughput in multi-queue switches. In Proceedings of the 12th Annual European Symposium on Algorithms (ESA). 53--64.
• 8: Yossi Azar , Yossi Richter, The zero-one principle for switching networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007369]
• 9: Azar, Y., and Richter, Y. 2005. Management of multi-queue switches in Qos networks. Algorithmica 43, 1--2, 81--96.
• 10: Bansal, N., Fleischer, L., Kimbrel, T., Mahdian, M., Schieber, B., and Sviridenko, M. 2004. Further improvements in competitive guarantees for QoS buffering. In Proceedings of the 31st International Colloquium on Automata, Languages, and Programming (ICALP). 196--207.
• 11: Alexander Birman , H. Richard Gail , Sidney L. Hantler , Zvi Rosberg , Moshe Sidi, An optimal service policy for buffer systems, Journal of the ACM (JACM), v.42 n.3, p.641-657, May 1995 [doi>10.1145/210346.210422]
• 12: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001 [doi>10.1145/363647.363659]
• 13: 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]
• 14: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer Overflow Management in QoS Switches, SIAM Journal on Computing, v.33 n.3, p.563-583, 2004 [doi>10.1137/S0097539701399666]
• 15: Alexander Kesselman , Yishay Mansour, Loss-bounded analysis for differentiated services, Journal of Algorithms, v.46 n.1, p.79-95, January 2003 [doi>10.1016/S0196-6774(02)00270-5]
• 16: Alexander Kesselman , Yishay Mansour, Harmonic buffer management policy for shared memory switches, Theoretical Computer Science, v.324 n.2-3, p.161-182, 20 September 2004 [doi>10.1016/j.tcs.2004.05.014]
• 17: Kesselman, A., Mansour, Y., and van Stee, R. 2003. Improved competitive guarantees for QoS buffering. In Proceedings of the 11th Annual European Symposium on Algorithms (ESA). 361--372.
• 18: Alex Kesselman , Adi Rosén, Scheduling policies for CIOQ switches, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777473]
• 19: Zvi Lotker , Boaz Patt-Shamir, Nearly optimal FIFO buffer management for two packet classes, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.42 n.4, p.481-492, 15 July 2003 [doi>10.1016/S1389-1286(03)00197-X]
• 20: May, M., Bolot, J. C., Jean-Marie, A., and Diot, C. 1999. Simple performance models of differentiated services for the internet. In Proceedings of IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA, 1385--1394.
• 21: Schmidt, M. 2005. Packet buffering---randomization beats deterministic algorithms. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS). ACM, New York, 293--304.

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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
CIOQ, Qos, competitive, on-line, switch