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

Christos Tsanikidis, Javad Ghaderi

Abstract

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 $\Omega(1/\log(L))$ fraction of the optimal objective value if the minimum link capacity in the network is $C_{\min}=\Omega(\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-\epsilon)$-approximation algorithms can be designed if $C_{\min} = \Omega\big(\frac{\log (L/\epsilon) } {\epsilon^2}\big)$. 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.

Introduction

In modern networking environments—ranging from industrial IoT and vehicular swarms to real-time video conferencing—the utility of a packet is often binary: it must arrive at its destination before a strict end-to-end deadline, or it is considered useless. While maximizing total throughput is a well-studied objective, scheduling with individual packet deadlines in a multihop environment presents a significant challenge. Decisions are inherently coupled across space and time; a scheduling choice made at a source node in the first time slot dictates the availability and congestion levels of downstream links in subsequent slots.

Historically, theoretical guarantees for this problem have been bifurcated between two extremes. On one hand, "worst-case" traffic analysis provides robust but pessimistic guarantees, often achieving only a $1/\log(L)$ fraction of the optimal delivery rate. On the other hand, "asymptotic" regimes assume infinite link capacities or arrival rates, which do not reflect the constraints of real-world hardware. This paper bridges this gap by demonstrating that near-optimal performance is achievable under stochastic traffic assumptions with finite, logarithmic link capacities.

The Challenge of Multihop Deadlines

Traditional scheduling algorithms like MaxWeight or Backpressure are designed for long-term stability and throughput maximization. However, they lack the temporal awareness required to prioritize packets nearing their expiration. In a multihop network, the "age" of a packet—the time elapsed since its arrival—is a critical state variable.

Previous research focused on adversarial traffic, where an adversary chooses packet arrivals to minimize the scheduler's performance. In such scenarios, the "worst-case tax" is high. This work shifts the focus to stochastic traffic (e.g., i.i.d. arrivals), which more accurately models the statistical regularity found in most communication networks. By leveraging this regularity, the authors show it is possible to move from a logarithmic approximation to a $(1-\epsilon)$ near-optimal approximation.

Proposed Algorithms

The researchers introduce two primary algorithms that utilize a flow-based relaxation of the scheduling problem, effectively turning a complex integer programming problem into a manageable linear program (LP).

1. Flow-Based Probabilistic Forwarding (FBPF)

FBPF is designed for environments where packet arrival rates are known. The algorithm solves a central LP to determine optimal "forwarding probabilities" for each packet type based on its current node and its current age.

  • Age-Based Logic: By incorporating the packet's age into the flow equations, the algorithm naturally encodes the deadline constraint.
  • Decentralized Execution: Although the probabilities are calculated via a central LP, the actual forwarding is simple: each node tosses a weighted coin to decide the next hop for a packet, requiring no global coordination during the transmission phase.

2. Dynamic Learning with Probabilistic Forwarding (DLPF)

Recognizing that arrival rates are rarely known a priori in dynamic networks, DLPF introduces a learning component. The algorithm divides time into phases of geometrically increasing length. During each phase, the system collects traffic statistics to estimate arrival rates, which are then used to update the forwarding probabilities for the subsequent phase. This allows the network to adapt to the underlying traffic distribution without manual tuning.

Theoretical Guarantees and Empirical Results

The authors prove that the FBPF algorithm achieves a $(1-3\epsilon)$ approximation of the optimal delivery objective, provided that the minimum link capacity $C_{\min}$ satisfies a logarithmic relationship with the path length $L$ and the error tolerance $\epsilon$. This confirms that near-optimality does not require infinite bandwidth, but rather a capacity that scales gracefully with network size.

Simulation Performance

The algorithms were evaluated against synthetic topologies (including a $4 \times 4$ Grid, a Circle network with shortcuts, and the 18-node IBM backbone network) and real-world IP traffic traces from the University of Cauca.

  • Comparison with State-of-the-Art: The proposed algorithms significantly outperformed GLS-FP, a leading algorithm designed for worst-case traffic. While GLS-FP's performance tended to plateau as capacity increased, FBPF and DLPF converged toward the theoretical optimum.
  • Robustness: In tests using real-world traces characterized by non-stationary and bursty traffic, DLPF maintained a substantial performance lead over traditional greedy scheduling heuristics. This suggests that the "stochastic" assumption is robust enough to handle the irregularities of actual network data.

Conclusion

This work provides a new theoretical foundation for deadline-constrained scheduling. By demonstrating that the gap between worst-case and near-optimal performance can be closed under stochastic assumptions, the authors offer a practical path forward for high-reliability, low-latency networking. Future research directions include the development of fully distributed primal-dual implementations, which would allow nodes to solve the underlying linear programs through local message passing, further increasing the scalability of the approach for massive ad-hoc networks.

Summary updated

Abstract

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 $\Omega(1/\log(L))$ fraction of the optimal objective value if the minimum link capacity in the network is $C_{\min}=\Omega(\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-\epsilon)$-approximation algorithms can be designed if $C_{\min} = \Omega\big(\frac{\log (L/\epsilon) } {\epsilon^2}\big)$. 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.
BibTeX
@inproceedings{tsanikidis2024near,
  author = {Christos Tsanikidis and Javad Ghaderi},
  title = {{Near-Optimal Packet Scheduling in Multihop Networks with End-to-End Deadline Constraints}},
  booktitle = {SIGMETRICS/Performance (Abstracts)},
  year = {2024},
  url = {https://openreview.net/forum?id=J1xyNFoetd},
}
Figure