Optimal delay scheduling in networks with arbitrary constraints

Srikanth Jagabathula, Devavrat Shah

TL;DR

This paper introduces a novel online scheduling scheme for wireless packet networks that simultaneously guarantees near-optimal throughput and low per-flow end-to-end delay, even with arbitrary network topology and interference constraints. The key innovation is a two-stage approach: first, a "less-constrained" network is optimized, and then an "emulation" technique is used to adapt this solution to the real-world constraints, achieving a delay bound proportional to the path length (number of hops).

What Problem Does This Paper Address?

Designing efficient scheduling algorithms for wireless networks is a significant challenge. Two critical performance metrics are throughput (how much data can be transmitted) and delay (how long packets take to reach their destination). Ideally, we want to maximize throughput while minimizing delay. However, real-world wireless networks have inherent constraints, such as interference, which limit which transmissions can happen simultaneously. These constraints complicate scheduling and often force a trade-off: optimizing for throughput might increase delay, and vice-versa.

Previous work often focused on optimizing one metric at the expense of the other, or made simplifying assumptions about network topology, traffic patterns, or constraints. For instance, some schemes achieved good delay bounds but had poor throughput, while others assumed simpler interference models. This paper tackles the problem of achieving both high throughput and low delay simultaneously in a general wireless network setting, without requiring prior knowledge of traffic arrival rates. Specifically, they aim for a per-flow delay bound of O(number of hops) with only a small, constant loss in throughput.

Methods

The authors employ a clever, layered approach to tackle this complex problem:

  1. Decomposition into Global and Local Scheduling: The problem is broken down into two sub-problems:
  2. Global Scheduling: Determining which links can be active simultaneously without violating network constraints.
  3. Local Scheduling: Deciding which specific packets to transmit across the active links.
  4. Adapting a Known Scheme (PL Policy): They adapt the Preemptive Last-In-First-Out (PL) scheduling scheme, known to perform well in continuous-time, quasi-reversible networks, to a discrete-time setting. This adaptation is applied to a "less-constrained" network ($N_0$) where nodes can transmit at most one packet per slot, but receive multiple.
  5. Emulation Technique: The core innovation is using an "emulation" technique to bridge the gap between the less-constrained network ($N_0$) and the actual, constrained wireless network ($N_2$). This involves designing a mechanism where the constrained network ($N_2$) behaves like the less-constrained network ($N_0$). This is achieved by running $N_2$ at a higher "speedup" (i.e., performing more scheduling operations per unit of time).
  6. Stable Marriage Algorithms: For the global scheduling problem in the constrained network, they leverage stable marriage algorithms. These algorithms are used to find a stable matching between potential transmitters and receivers, effectively determining the set of active links in each scheduling phase.
  7. Speedup and Throughput Loss: The emulation process requires a speedup. For networks with primary interference constraints (where a node can only transmit or receive, not both, at most one packet per slot), a speedup of 5 is shown to be sufficient. This speedup, however, comes at the cost of a throughput loss, which is also a factor of 5. The paper proves an equivalence between running a network at a higher speedup and a lower throughput at speedup 1.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithm design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Simultaneous Throughput and Delay Optimization: The paper demonstrates that it's possible to achieve near-optimal bounds for both throughput and delay simultaneously, challenging the notion that a significant trade-off is always necessary.
  • The Power of Emulation: The concept of "emulating" a simpler, unconstrained system within a more complex, constrained one is a powerful abstraction. It allows leveraging existing results for simpler systems and adapting them to real-world complexities.
  • Decoupling Complex Problems: Breaking down the scheduling problem into global and local components, and then further into less-constrained and constrained versions, makes the problem tractable.
  • Speedup as a Mechanism for Constraint Handling: Using network speedup is a novel way to manage interference constraints. By performing more operations in a given time, the network can effectively "wait" for constraints to clear or schedule more complex interactions.
  • Per-Flow Guarantees are Crucial: The emphasis on per-flow delay bounds, rather than aggregate bounds, is important for practical network performance, as it prevents a few "bad" flows from dictating the overall performance.

Key Results

  • Optimal Delay Bound: The proposed scheduling scheme guarantees a per-flow end-to-end packet delay bound of $O(d_j / (1 - \rho_j))$, where $d_j$ is the path length of flow $j$ and $\rho_j$ is its effective loading. This is shown to be essentially optimal, as $d_j$ is a fundamental lower bound on delay.
  • Constant Throughput Loss: The scheme achieves this delay bound with a throughput loss of at most a factor of 5 for networks with primary interference constraints.
  • Generality: The approach is shown to extend to networks with arbitrary scheduling constraints, with the throughput loss depending on a "sub-graph covering" property of the constraints.
  • Necessity of Speedup: The paper proves that a speedup of at least 4 is necessary for emulation in certain network configurations, highlighting the fundamental limits and the optimality of their proposed speedup factor.

Limitations and Future Work

  • Constant Factors: While the delay bound is asymptotically optimal, the constant factors (e.g., the factor of 5 for speedup and throughput loss) might be improvable for specific network structures or constraints.
  • Practical Implementation: The authors acknowledge that their scheme is a "proof of concept" and not necessarily practically implementable in its current form due to the complexity of the control layer and emulation.
  • Arbitrary Constraints: While the framework is general, determining the exact speedup and throughput loss for arbitrary constraint sets remains an open problem, relying on the "sub-graph covering" property.
  • Optimality for General Constraints: Establishing the optimality of their approach for arbitrary constraint sets is a natural direction for future work.

Summary updated

Abstract

We consider the problem of designing an online scheduling scheme for a multi-hop wireless packet network with arbitrary topology and operating under arbitrary scheduling constraints. The objective is to design a scheme that achieves high throughput and low delay simultaneously. We propose a scheduling scheme that - for networks operating under primary interference constraints - guarantees a per-flow end-to-end packet delay bound of 5 d j /(1- ρ j ), at a factor 5 loss of throughput, where d j is the path length (number of hops) of flow j and ρ j is the effective loading along the route of flow j . Clearly, d j is a universal lower bound on end-to-end packet delay for flow j . Thus, our result is essentially optimal. To the best of our knowledge, our result is the first one to show that it is possible to achieve a per-flow end-to-end delay bound of O (# of hops) in a constrained network. Designing such a scheme comprises two related subproblems: Global Scheduling and Local Scheduling. Global Scheduling involves determining the set of links that will be simultaneously active, without violating the scheduling constraints. While local scheduling involves determining the packets that will be transferred across active edges. We design a local scheduling scheme by adapting the Preemptive Last-In-First-Out (PL) scheme, applied for quasi-reversible continuous time networks, to an unconstrained discrete-time network. A global scheduling scheme will be obtained by using stable marriage algorithms to emulate the unconstrained network with the constrained wireless network. Our scheme can be easily extended to a network operating under general scheduling constraints, such as secondary interference constraints, with the same delay bound and a loss of throughput that depends on scheduling constraints through an intriguing "sub-graph covering" property.
BibTeX
@inproceedings{jagabathula2008optimal,
  author = {Srikanth Jagabathula and Devavrat Shah},
  title = {{Optimal delay scheduling in networks with arbitrary constraints}},
  booktitle = {SIGMETRICS},
  year = {2008},
  doi = {10.1145/1375457.1375502},
}
Figure