Online Packet Scheduling with Deadlines and Learning

Network routers that enforce Quality-of-Service (QoS) guarantees must decide, at every clock cycle, which expiring packet of information to transmit, even when the value of the packet is unknown until it is processed. We frame this problem as the Online Packet Scheduling with Deadlines (OPSD) problem under Partial Feedback: packets arrive at every clock cycle, with different deadlines, but the weights are only observed after execution. Under a stochastic assumption on the unknown weights, we explore different variants of the OPSD problem with bandit feedback. We establish a connection between our setting and the sleeping bandits problem, and set our learning goal to $\alpha$-regret minimization. We provide algorithms with provable $\alpha$-regret guarantees under different spans of slackness, distinguishing systems allowing for randomization and systems that do not. In every scenario, our algorithms achieve an $\alpha$-regret upper bound of $\widetilde{\mathcal{O}}\left(\sqrt{KT}\right)$, matching the lower bound for the standard bandit setting. In the practically relevant case of $2$-bounded deadline instances, where the deadline is set at most one clock cycle away from the arrival, our deterministic algorithm achieves the provably tightest possible competitive ratio. Remarkably, when the number of distinct packet types $K\ge 2$ is finite, it is possible to break the well-established $\Phi = \frac{1+\sqrt{5}}{2}$ competitive ratio barrier and attain a tighter competitive ratio $\theta_K$ ranging in $[\sqrt{2}, \Phi)$.

Modern communication systems often have to make very fast decisions about which pieces of information to process first. For example, a network router, an online advertising platform, or a real-time computing system may receive many requests at once, but only some of them can be handled before they expire. The difficulty is that the system may not know in advance which requests are the most valuable; it only learns this after choosing to process them. This paper studies how to make good decisions in this setting. We consider packets that arrive over time, have deadlines, and belong to different types. The value of each type is initially unknown, so the scheduler must learn from experience while still meeting deadlines. This creates a trade-off between exploring uncertain packet types and exploiting the ones that currently seem most valuable. We design algorithms that provably learn efficiently while staying competitive with an ideal scheduler that already knows the average value of every packet type. Our results show that learning can be added to packet scheduling without significantly worsening performance. In some important cases with short deadlines and finitely many packet types, we also improve over a long-standing performance barrier from classical packet scheduling theory.