Considering suppressed packets improves buffer management in QoS switches

ABSTRACT

The following buffer management problem arises in network switches providing differentiated services: At the beginning of each time step, one packet can be sent, and afterwards an arbitrary number of new packets arrive. Packets that are not sent can be stored in a buffer. Each packet is attributed by a deadline, and a packet is automatically deleted from the buffer if it is still stored in the buffer by the end of its deadline. The differentiated service model is abstracted by attributing each packet with a value according to its service level. A buffer management strategy determines the packet to be sent in each time step. The goal of a buffer management strategy is to maximize the sum of the values of sent packets.

We introduce the concept of suppressed packets and present a deterministic strategy that is based on this concept. We show that this strategy achieves a competitive ratio of 2√2--1 ≈ 1.828, which is the best known competitive ratio in the deterministic case. Further, we present a memoryless version of this strategy that achieves a competitive ratio of ≈ 1.893. This is the first memoryless strategy that achieves a competitive ratio less than 2, and the competitive ratio of this strategy is even better than the ratios of all previously known deterministic strategies. This demonstrates the potential of the concept of suppressed packets. In addition, we present a simple strategy that achieves the optimal competitive ratio of min{(1 + α)/α, 2α/(α+1)} ≤ √2, if only two packet values 1 and α > 1 are possible.

REFERENCES

• 1: 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
• 2: Ee-Chien Chang , Chee Yap, Competitive on-line scheduling with level of service, Journal of Scheduling, v.6 n.3, p.251-267, May/June 2003 [doi>10.1023/A:1022904408360]
• 3: F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, J. Sgall, and T. Tichý. Online competitivee algorithms for maximizing weighted throughput of unit jobs. Journal of Discrete Algorithms, 4(2):255--276, 2006.
• 4: 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.
• 5: M. Chrobak, W. Jawor, J. Sgall, and T. Tichý. Improved online algorithms for buffer management in QoS switches. In Proceedings of the 12th European Symposium on Algorithms (ESA), pages 204--215, 2004.
• 6: Matthias Englert , Matthias Westermann, Lower and upper bounds on FIFO buffer management in QoS switches, Proceedings of the 14th conference on Annual European Symposium, p.352-363, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_33]
• 7: B. Hajek. On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time. In Proceedings of the 2001 Conference on Information Sciences and Systems (CISS), pages 434--438, 2001.
• 8: 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]
• 9: A. Kesselman, Y. Mansour, and R. van Stee. Improved competitive guarantees for QoS buffering. Algorithmica, 43(1--2):63--80, 2005.
• 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