Online Scheduling of Packets with Agreeable Deadlines
This article concerns an online packet scheduling problem that arises as a natural model for buffer management at a network router. Packets arrive at a router at integer time steps, and are buffered upon arrival. Packets have non-negative weights and integer deadlines that are (weakly) increasing in their arrival times. In each integer time step, at most one packet can be sent. The objective is to maximize the sum of the weights of the packets that are sent by their deadlines. The main results include an optimal (phi := (1+root 5)/2 approximate to 1.618)-competitive deterministic online algorithm, a (4/3 approximate to 1.33)-competitive randomized online algorithm against an oblivious adversary, and a 2- speed 1-competitive deterministic online algorithm. The analysis does not use a potential function explicitly, but instead modifies the adversary's buffer and credits the adversary to account for these modifications.
packet scheduling buffer management management online algorithm algorithms theory competitive analysis