Randomized qeue management for DiffServ

ABSTRACT

We focus on the online problem of queue management in networks providing differentiated services. As in DiffServ, packets are divided into two priority groups. Low priority packets are assigned the value of 1 and high priority packets are assigned the value of α > 1. The goal is to maximize the total value of packets that are sent. Restricted to FIFO queues, the packets must be sent by the order of their arrival, however we are allowed to preempt packets from the queue.Several deterministic online algorithms for this model have been presented in previous papers. Currently, the best online algorithm known for this problem has a competitive ratio of 1.304 for the worst case α [17]. In this work we consider randomized online algorithms. Our main result is an online policy that outperforms any deterministic policy and achieves a competitive ratio of 1.25, by using a single random bit. This result is lower than the deterministic lower bound of 1.281 [19]. We then derive a general lower bound for randomized algorithms of 1.197.A natural extension of this model is to assign arbitrary packet values to the input packets. Currently, the best competitive ratio achieved for a deterministic policy is 1.75 [7]. We present a randomized comparison based online policy with the same competitive ratio. Since no deterministic comparison based policy is known to have a competitive ratio better than 2, we believe that this result demonstrates the potential of using randomization to outperform deterministic policies, as in the two value model.

REFERENCES

• 1: W. Aiello, Y. Mansour, S. Rajagopolan, and A. Rosén. Competitive queue policies for differentiated services. In INFOCOM, pages 431--440, 2000.
• 2: N. Andelman and Y. Mansour. Competitive management of non-preemptive queues with multiple values. In DISC, pages 166--180, 2003.
• 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: 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]
• 5: Y. Azar and Y. Richter. An improved algorithm for cioq switches. In ESA, pages 65--76, 2004.
• 6: 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]
• 7: N. Bansal, L. Fleischer, T. Kimbrel, M. Mahdian, B. Schieber, and M. Sviridenko. Further improvements in competitive guarantees for qos buffering. In ICALP, pages 196--207, 2004.
• 8: S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss. An architecture for differentiated services. RFC 2475, IETF, December 1998.
• 9: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 10: D. Clark and J. Wroclawski. An approach to service allocation in the internet. Internet-Draft Version 00, IETF, July 1997.
• 11: 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]
• 12: A. Kesselman, Z. Lotker, Y. Mansour, and B. Patt-Shamir. Buffer overflows of merging streams. In ESA, pages 349--360, 2003.
• 13: 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]
• 14: 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
• 15: A. Kesselman and Y. Mansour. Harmonic buffer management policy for shared memory switches. In INFOCOM, 2002.
• 16: A. Kesselman, Y. Mansour, and R. van Stee. Improved competitive guarantees for qos buffering. In ESA, pages 361--372, 2003.
• 17: 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]
• 18: M. Schmidt. Packet buffering: Randomization beats deterministic algorithms. In STACS, pages 293--304, 2005.
• 19: M. Sviridenko. A lower bound for on-line algorithms in the fifo model. Unpublished Manuscript, 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms

Keywords:
active queue management, competitive analysis, online algorithms, randomized algorithms