Management of multi-queue switches in QoS networks

ABSTRACT

The concept of Quality of Service (QoS) networks has gained growing attention recently, as the traffic volume in the Internet constantly increases, and QoS guarantees are essential to ensure proper operation of most communication based applications. A QoS switch serves m incoming queues by transmitting packets arriving at these queues through one output port, one packet per time unit. Each packet is marked with a value indicating its guaranteed quality of service. Since the queues have bounded capacity and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. The goal is to maximize the total value of transmitted packets. This problem encapsulates two dependent questions: admission control, namely which packets to discard in case of queue overflow, and scheduling, i.e. which queue to use for transmission in each time unit. We use competitive analysis to study online switch performance in QoS based networks. Specifically, we provide a novel generic technique that decouples the admission control and scheduling problems. Our technique transforms any single queue admission control strategy (preemptive or nonpreemptive) to a scheduling and admission control algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given admission control strategy. We use our technique to derive concrete algorithms for the general preemptive and nonpreemptive cases, as well as for the interesting special cases of the 2-value model and the unit value model. To the best of our knowledge this is the first result combining both scheduling and admission control decisions for arbitrary packets sequences in multi-queue switches. We also provide a 1.58-competitive randomized algorithm for the unit value case. This case is interesting by itself since most current networks (e.g. IP networks) only support a best-effort service in which all packets streams are treated equally.

REFERENCES

• 1: W. A. Aiello, Y. Mansour, S. Rajagopolan, and A. Rosen. Competitive queue policies for differentiated services. In Proceedings of the IEEE INFOCOM 2000, pages 431--440.
• 2: 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
• 3: Amotz Bar-Noy , Ari Freund , Shimon Landa , Joseph (Seffi) Naor, Competitive on-line switching policies, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.525-534, January 06-08, 2002, San Francisco, California
• 4: 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]
• 5: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 6: Marek Chrobak , János Csirik , Csanád Imreh , John Noga , Jiri Sgall , Gerhard J. Woeginger, The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.862-874, July 08-12, 2001
• 7: 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]
• 8: R. M. Karp , U. V. Vazirani , V. V. Vazirani, An optimal algorithm for on-line bipartite matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.352-358, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100262]
• 9: 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]
• 10: 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
• 11: Hisashi Koga, Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness, Proceedings of the 12th International Symposium on Algorithms and Computation, p.61-73, December 19-21, 2001
• 12: Zvi Lotker , Boaz Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571851]
• 13: M. May, J. C. Bolot, A. Jean-Marie, and C. Diot. Simple performance models of differentiated services for the internet. In Proceedings of the IEEE INFOCOM 1999, pages 1385--1394.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

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:
QoS, competitive, on-line, switch