Learning-Augmented Online Packet Scheduling with Deadlines
This work addresses buffer management in networks to prevent loss of critical traffic, but it appears incremental as it builds on existing online scheduling methods by incorporating predictions.
The paper tackles the problem of online packet scheduling with deadlines in networks, aiming to prioritize critical traffic and manage buffer usage effectively. The authors propose a learning-augmented algorithmic framework that improves the competitive ratio when prediction errors are small while maintaining bounded performance regardless of error.
The modern network aims to prioritize critical traffic over non-critical traffic and effectively manage traffic flow. This necessitates proper buffer management to prevent the loss of crucial traffic while minimizing the impact on non-critical traffic. Therefore, the algorithm's objective is to control which packets to transmit and which to discard at each step. In this study, we initiate the learning-augmented online packet scheduling with deadlines and provide a novel algorithmic framework to cope with the prediction. We show that when the prediction error is small, our algorithm improves the competitive ratio while still maintaining a bounded competitive ratio, regardless of the prediction error.