# Near-Optimal Packet Scheduling in Multihop Networks with End-to-End Deadline Constraints

**Authors:** Christos Tsanikidis, Javad Ghaderi  
**arXiv:** [2310.19077](https://arxiv.org/abs/2310.19077)  
**Date:** 2023-10-29  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2310.19077v1/

## Key points

- The paper addresses the problem of scheduling packets with end-to-end deadline constraints in multihop networks.
- Previous work focused on worst-case traffic scenarios and achieved suboptimal results based on minimum link capacity.
- This study explores near-optimal solutions under stochastic traffic conditions, demonstrating that near-optimal $(1-\epsilon)$-approximation algorithms can be designed for i.i.d. packet arrivals with sufficiently high minimum link capacity.
- Extended simulations using real network traces show that the proposed algorithms outperform traditional worst-case-based approaches in practical settings.
- The research provides valuable insights into designing efficient packet scheduling algorithms for multihop networks by considering more realistic stochastic traffic scenarios.
- Detailed proofs of main theorems are included to support the theoretical foundations of the proposed algorithms.
- Overall, this work significantly advances packet scheduling techniques in multihop networks by optimizing performance under varying conditions and considering real-world traffic dynamics.

## Summary

The paper "Near-Optimal Packet Scheduling in Multihop Networks with End-to-End Deadline Constraints" by Christos Tsanikidis and Javad Ghaderi addresses the challenging problem of scheduling packets with end-to-end deadline constraints in multihop networks. Previous work focused on worst-case traffic scenarios and achieved suboptimal results based on minimum link capacity. In contrast, this study explores near-optimal solutions under stochastic traffic conditions. The authors demonstrate that near-optimal $(1-\epsilon)$-approximation algorithms can be designed for i.i.d. packet arrivals when the minimum link capacity is sufficiently high. This marks a significant advancement in solving this complex problem under nontrivial assumptions. Through extended simulations using real network traces with non-stationary traffic patterns, the proposed algorithms outperform traditional worst-case-based approaches in practical settings. By considering more realistic stochastic traffic scenarios, this research provides valuable insights into designing efficient packet scheduling algorithms for multihop networks with end-to-end deadline constraints. The paper also includes detailed proofs of main theorems to support the theoretical foundations of their proposed algorithms. Overall, this work contributes significantly to advancing packet scheduling techniques in multihop networks by considering real-world traffic dynamics and optimizing performance under varying conditions.