FIFO Queueing Policies for Packets With Heterogeneous Processing

The authors consider the problem of managing a bounded size First-In-First-Out (FIFO) queue buffer, where each incoming unit-sized packet requires several rounds of processing before it can be transmitted out. Their objective is to maximize the total number of successfully transmitted packets. They consider both push-out (when the policy is permitted to drop already admitted packets) and non-push-out cases. In particular, they provide analytical guarantees for the throughput performance of their algorithms. They further conduct a comprehensive simulation study which experimentally validates the predicted theoretical behavior.