Moran Feldman (CS, Technion)
Wednesday, 10.3.2010, 12:30
The delivery of latency sensitive packets is a crucial issue in real time applications of communication
networks. Such packets often have a firm deadline and a packet becomes useless if it arrives after its
deadline. The deadline, however, applies only to the packet's journey through the entire network;
individual routers along the packet's route face a more flexible deadline.
We consider policies for admitting latency sensitive packets at a router. Each packet is tagged with a
value and a packet waiting at a router loses value over time as its probability of arriving at its destination
decreases. The router is modeled as a non-preemptive queue, and its objective is to maximize the total
value of the forwarded packets. When a router receives a packet, it must either accept it (and possibly
delay future packets), or reject it immediately. The best policy depends on the set of values that a packet
can take. We consider three natural settings: unrestricted model, real-valued model, where any value
above $1$ is allowed, and an integral-valued model.
We obtain the following results. For the unrestricted model, we prove that there is no constant
competitive ratio algorithm. The real valued model has a randomized 4-competitive algorithm and a
matching lower bound. We also give for the last model a deterministic lower bound of ~4.236, almost
matching the previously known 4.24-competitive algorithm. For the integral-valued model, we show a
deterministic 4-competitive algorithm, and prove that this is tight even for randomized algorithms.