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

Christos Tsanikidis, Javad Ghaderi

TL;DR

This paper introduces the first algorithms to achieve near-optimal performance for scheduling packets with strict end-to-end deadlines in multihop networks under stochastic traffic. By moving away from pessimistic "worst-case" assumptions, the authors demonstrate that a $(1-\epsilon)$ approximation of the optimal delivery rate is possible even with finite link capacities and non-stationary traffic.

What Problem Does This Paper Address?

In modern networks—think video conferencing, vehicular swarms, or industrial IoT—packets aren't just trying to get to their destination; they need to get there on time. If a packet misses its end-to-end deadline, it’s often useless and discarded.

Scheduling these packets in a multihop environment is a nightmare. Decisions are coupled: a choice to send a packet on Link A at Time 1 affects what can be sent on Link B at Time 2. Traditional algorithms like "MaxWeight" or "Backpressure" are great for maximizing total throughput over long periods, but they offer no guarantees for individual packet deadlines.

Until now, theoretical guarantees for this problem were either very pessimistic (based on "worst-case" traffic that rarely happens) or required "asymptotic" regimes where link capacities and arrival rates scale to infinity. This paper fills the gap: how do we design practical, near-optimal algorithms for real-world networks with finite capacities and stochastic (random) traffic?

Methods

The authors propose two primary algorithms based on a novel flow-based relaxation of the problem:

  1. Flow-Based Probabilistic Forwarding (FBPF): This is a "static" algorithm used when packet arrival rates are known. It solves a single Linear Program (LP) to find optimal "forwarding probabilities." These probabilities are based on a packet’s age (how long it has been in the system), its type, and its current node. Instead of complex global coordination, each node simply tosses a coin to decide where to send a packet next.
  2. Dynamic Learning with Probabilistic Forwarding (DLPF): In the real world, we rarely know arrival rates in advance. DLPF divides time into phases of geometrically increasing length. It uses the traffic data from previous phases to estimate arrival rates and updates its forwarding probabilities on the fly.

The "secret sauce" is the reduction of an exponentially large integer program (tracking every possible route and time slot) into a polynomial-sized LP by focusing on the "Expected Instance" of the traffic.

Datasets

The researchers evaluated their algorithms using both synthetic and real-world data:

  • Synthetic Topologies: They tested on a $4 \times 4$ Grid network, a Circle network with shortcuts, and a 18-node IBM backbone network ($G_{IBM}$).
  • Real Traffic Traces: They used IP traffic traces collected at the University of Cauca. These traces are particularly challenging because they feature "bursty," non-stationary traffic that doesn't follow simple statistical distributions.

Key Insights and Ideas

  • The "Worst-Case" Tax: Prior work showed that in the worst-case traffic scenario, you can only guarantee a $1/\log(L)$ fraction of the optimal (where $L$ is the path length). This paper shows that if traffic is even slightly predictable (stochastic), that "tax" disappears, and you can get nearly 100% of the optimal.
  • Age-Based Scheduling: By making forwarding decisions dependent on the "age" of a packet, the authors effectively encode the deadline constraint directly into the flow equations. This allows a complex temporal problem to be solved as a static flow problem.
  • Logarithmic Capacity is Enough: You don't need infinite bandwidth for these guarantees to hold. The authors prove that as long as the minimum link capacity is logarithmic relative to the path length and the desired error ($\epsilon$), near-optimality is guaranteed.

Key Results

  • Near-Optimality: The FBPF algorithm provides a $(1-3\epsilon)$ approximation to the optimal delivery objective.
  • Outperforming the State-of-the-Art: In simulations, the proposed algorithms significantly outperformed "GLS-FP" (a leading worst-case-based algorithm). While GLS-FP's performance stagnated as network capacity increased, the authors' algorithms approached the theoretical optimal.
  • Robustness to Bursts: Even when tested against real-world traces with sudden bursts and non-stationary patterns, the dynamic (DLPF) algorithm maintained a significant lead over traditional greedy approaches, proving its practical utility.

Limitations and Future Work

The primary limitation is the requirement for a minimum link capacity ($C_{min}$). While it only needs to be logarithmic, in extremely constrained or highly congested "bottleneck" links where $C_{min}$ is very small (e.g., 1 or 2 packets per slot), the theoretical guarantees weaken.

The authors suggest that future work could explore distributed primal-dual implementations. Currently, the LP is solved centrally; a fully decentralized version where nodes coordinate through local message passing would be the "holy grail" for massive, ad-hoc mesh 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 Ω(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 = Ω((over (logL/ε) Ω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.
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},
}

Loading related content...

Figure