Competitive queue management for latency sensitive packets

ABSTRACT

We consider the online problem of non-preemptive queue management. An online sequence of packets arrive, each of which has an associated intrinsic value. Packets can be accepted to a FIFO queue, or discarded. The profit gained by transmitting a packet diminishes over time and is equal to its value minus the delay. This corresponds to the well known and strongly motivated Naor's model in operations research.

We give a queue management algorithm with a competitive ratio equal to the golden ratio (φ ≈ 1.618) in the case that all packets have the same value, along with a matching lower bound. We also derive Θ(1) upper and lower bounds on the competitive ratio when packets have different intrinsic values (in the case of differentiated services). We can extend our results to deal with more general models for loss of value over time.

Finally, we re-interpret our online algorithms in the context of selfish agents, producing an online mechanism that approximates the optimal social welfare to within a constant factor.

REFERENCES

• 1: William A. Aiello , Yishay Mansour , S. Rajagopolan , Adi Rosén, Competitive queue policies for differentiated services, Journal of Algorithms, v.55 n.2, p.113-141, May 2005 [doi>10.1016/j.jalgor.2004.04.004]
• 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: F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, J. Sgall, and T. Tichy. Online competitive algorithms for maximizing weighted throughput of unit jobs. Journal of Discrete Algorithms, 4(2):255--276, 2006.
• 5: F. Y. L. Chin and S. P. Y. Fung. Online scheduling with partial job values: Does timesharing or randomization help? Algorithmica, 37(3):149--164, 2003.
• 6: Matthias Englert , Matthias Westermann, Considering suppressed packets improves buffer management in QoS switches, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.209-218, January 07-09, 2007, New Orleans, Louisiana
• 7: R. Hassin. On the optimality of first come last served queues. Econometrica, 53(1):201--202, 1985.
• 8: R. Hassin and M. Haviv. To Queue or not to Queue: Equilibrium Behavior in Queueing Systems. Kluwer Apademic Publishers, 2003.
• 9: 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]
• 10: Fei Li , Jay Sethuraman , Clifford Stein, An optimal online algorithm for packet scheduling with agreeable deadlines, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 11: Fei Li , Jay Sethuraman , Clifford Stein, Better online buffer management, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.199-208, January 07-09, 2007, New Orleans, Louisiana
• 12: P. Naor. The regulation of queue size by levying tolls. Econometrica, 37(1):15--24, 1969.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

General Terms:
Algorithms, Design, Theory