Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. In recent work, Kesselman et al. [6] propose a model, called buffer management with bounded delay, which can be thought of as an online scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If B = ∞, this is the online version of the scheduling problem 1| pj = 1, rj, dj |Σ wj Uj. (We assume that rj and dj are integers.)

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: Y. Bartal, F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, R. Lavi, J. Sgall, and T. Tichy, Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs, 21st Annual Symposium on Theoretical Aspects of Computer Science, pp.190 -- 210, 2004.
• 3: M. Chrobak, W. Jawor, J. Sgall, and T. Tichy, Improved Online Algorithms for Buffer Management in QoS Switches, ESA 2004.
• 4: F. Y. L. Chin and S. P. Y. Fung, Online Scheduling with Partial Job Values: Does Timesharing or Randomization Help?, Algorithmica, 2003.
• 5: B. Hajek, On the Competitiveness of Online Scheduling of Unit-Length Packets with Hard Deadlines in Slotted Time, Proceedings of 2001 Conference on Information Sciences and Systems, The John Hopkins U., 2001.
• 6: 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]