Online Packet Scheduling with Bounded Delay and Lookahead

Authors Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, Pavel Veselý



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.21.pdf
  • Filesize: 0.57 MB
  • 13 pages

Document Identifiers

Author Details

Martin Böhm
Marek Chrobak
Lukasz Jez
Fei Li
Jirí Sgall
Pavel Veselý

Cite AsGet BibTex

Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, and Pavel Veselý. Online Packet Scheduling with Bounded Delay and Lookahead. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.21

Abstract

We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is 1.828 [Englert and Westermann, SODA 2007], still quite far from the best lower bound of phi approx 1.618 [Hajek, CISS 2001; Andelman et al, SODA 2003; Chin and Fung, Algorithmica, 2003]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [Chin et al, JDA, 2006]. Improving that result, and addressing a question posed by Goldwasser [SIGACT News, 2010], we present a phi-competitive algorithm for 4-bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio frac{1}{2}(sqrt{13} - 1) approx 1.303 and we prove a nearly tight lower bound of frac{1}{4}(1 + sqrt{17}) approx 1.281.
Keywords
  • buffer management
  • online scheduling
  • online algorithm
  • lookahead

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Susanne Albers. On the influence of lookahead in competitive paging algorithms. Algorithmica, 18(3):283-305, 1997. URL: http://dx.doi.org/10.1007/PL00009158.
  2. Nir Andelman, Yishay Mansour, and An Zhu. Competitive queueing policies for QoS switches. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pages 761-770, 2003. Google Scholar
  3. Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Jiří Sgall, and Tomáš Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. J. of Discrete Algorithms, 4(2):255-276, 2006. Google Scholar
  4. Francis Y. L. Chin and Stanley P. Y. Fung. Online scheduling with partial job values: Does timesharing or randomization help? Algorithmica, 37(3):149-164, 2003. Google Scholar
  5. Marek Chrobak, Wojciech Jawor, Jiří Sgall, and Tomáš Tichý. Improved online algorithms for buffer management in QoS switches. In Proc. 12th Annual European Symposium (ESA'04), pages 204-215, 2004. Google Scholar
  6. Matthias Englert and Matthias Westermann. Considering suppressed packets improves buffer management in QoS switches. In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07), pages 209-218, 2007. Google Scholar
  7. Matthias Englert and Matthias Westermann. Lower and upper bounds on FIFO buffer management in QoS switches. Algorithmica, 53(4):523-548, 2009. Google Scholar
  8. Michael H. Goldwasser. A survey of buffer management policies for packet switches. SIGACT News, 41(1):100-128, 2010. Google Scholar
  9. Edward F. Grove. Online bin packing with lookahead. In Proc. 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'95), pages 430-436, 1995. Google Scholar
  10. Bruce Hajek. On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time. In Proc. Conference on Information Sciences and Systems, pages 434-438, 2001. Google Scholar
  11. Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, and Maxim Sviridenko. Buffer overflow management in QoS switches. SIAM Journal on Computing, 33(3):563-583, 2004. Google Scholar
  12. Fei Li, Jay Sethuraman, and Clifford Stein. An optimal online algorithm for packet scheduling with agreeable deadlines. In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'05), pages 801-802, 2005. Google Scholar
  13. Rajeev Motwani, Vijay Saraswat, and Eric Torng. Online scheduling with lookahead: Multipass assembly lines. INFORMS J. on Computing, 10(3):331-340, 1998. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail