Buffer Management for Colored Packets With Deadlines

The paper considers buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated Earliest-Deadline-First (EDF) strategy is optimal 1- competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. The paper designs an online algorithm that achieves a competitive ratio of 1 ? o(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity.