2023/10/29 by Christos Tsanikidis, Tsanikidis, Christos, Javad Ghaderi +1
Computer Science · Engineering · #Advanced Wireless Network Optimization #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI) #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2310.19077
openalex publication_date 2023/10/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Scheduling packets with end-to-end deadline constraints in multihop networks is an important problem that has been notoriously difficult to tackle. Recently, there has been progress on this problem in the worst-case traffic setting, with the objective of maximizing the number of packets delivered within their deadlines. Specifically, the proposed algorithms were shown to achieve Ω(1/log(L)) fraction of the optimal objective value if the minimum link capacity in the network is Cmin=Ω(log (L)), where L is the maximum length of a packet's route in the network (which is bounded by the packet's maximum deadline). However, such guarantees can be quite pessimistic due to the strict worst-case traffic assumption and may not accurately reflect real-world settings. In this work, we aim to address this limitation by exploring whether it is possible to design algorithms that achieve a constant fraction of the optimal value while relaxing the worst-case traffic assumption. We provide a positive answer by demonstrating that in stochastic traffic settings, such as i.i.d. packet arrivals, near-optimal, (1-ε)-approximation algorithms can be designed if Cmin = Ω(\fraclog (L/ε) ε2). To the best of our knowledge, this is the first result that shows this problem can be solved near-optimally under nontrivial assumptions on traffic and link capacity. We further present extended simulations using real network traces with non-stationary traffic, which demonstrate that our algorithms outperform worst-case-based algorithms in practical settings.