A -competitive algorithm for scheduling packets with deadlines

DOI10.1137/1.9781611975482.9MaRDI QIDQ5236190zbMATH OpenOpenAlexFDO

Authors Pavel Veselý, Łukasz Jeż, Jiří Sgall, Marek Chrobak

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.07177

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35)

Abstract: In the online packet scheduling problem with deadlines (PacketSchD, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets that are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketSchD, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a $phi$-competitive online algorithm for PacketSchD (where $phiapprox1.618$ is the golden ratio), matching the previously established lower bound.

Recommendations

• Online scheduling of packets with agreeable deadlines
• A -competitive algorithm for collecting items with increasing weights from a dynamic queue
• Online packet scheduling with bounded delay and lookahead
• An optimal online algorithm for packet scheduling with agreeable deadlines
• Online packet scheduling with bounded delay and lookahead

Cited in

(8)

• A -competitive algorithm for collecting items with increasing weights from a dynamic queue
• Randomized two-valued bounded delay online buffer management
• Scheduling weighted packets with deadlines over a fading channel
• An optimal online algorithm for packet scheduling with agreeable deadlines
• Randomized algorithm for agreeable deadlines packet scheduling
• A Constant Approximation Algorithm for Scheduling Packets on Line Networks
• A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with Deadlines
• Breaking the barrier of 2 for the competitiveness of longest queue drop

This page was built for publication: A \(\phi\)-competitive algorithm for scheduling packets with deadlines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236190)