PaperlayerView exact revision on arXiv

Source-linked AI summary

Delay-Based Back-Pressure Scheduling in Multihop Wireless Networks

Bo Ji, Changhee Joo, Ness B. Shroff

arXiv:1011.5674v3cs.NIcs.PF

TL;DR

Multihop delay-based scheduling lacked a general throughput-optimality characterization, while queue-length methods could leave finite-data flows excessively delayed by the last packet problem. The paper introduces D-BP with a new multihop delay metric and proves throughput-optimality, with simulations showing reduced excessive delays and no throughput loss relative to queue-based scheduling.

  • Problem

    Throughput-optimality of delay-based scheduling remained largely open for fixed-route multihop wireless networks, despite its potential to address the last packet problem.

  • Method

    The paper develops D-BP using a delay metric defined as the sojourn-time difference between a queue's head-of-line packet and that of its previous hop.

  • Results

    D-BP achieves optimal throughput performance, while simulations show that excessive delays under queue-based scheduling are eliminated without throughput loss.

  • Takeaways & Limitations

    Delay-based scheduling provides a way around the last packet problem and avoids flow starvation in fixed-route multihop networks.

Abstract

from arXiv · show

Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput-optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop.) In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric, and show that the proposed scheme achieves optimal throughput performance. Further, we conduct simulations to support our analytical results, and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme.

I. INTRODUCTION

Queue-length scheduling can achieve high throughput but may excessively delay or starve finite-data flows through the last packet problem. The paper develops D-BP for fixed-route multihop networks and shows that it is throughput-optimal while reducing such delays.

  • I. INTRODUCTION: Queue-length schedulers can starve a flow's last packet because its queue remains small when no subsequent packets arrive.This last packet problem can produce excessive delays and may prevent throughput-optimality under flow-level dynamics.
  • I. INTRODUCTION: Delay-based scheduling raises a link's priority as its head-of-line delay grows, providing an intuitive response to the last packet problem.The approach had established throughput guarantees mainly for single-hop traffic before this work.
  • I. INTRODUCTION: The proposed delay metric is the sojourn-time difference between a queue's head-of-line packet and the head-of-line packet at its previous hop.This metric establishes a linear relation between queue lengths and delays in fluid limits, supporting the optimality proof.
  • I. INTRODUCTION: D-BP is throughput-optimal for multihop wireless networks with fixed routes.The scheme uses a new delay metric and a fluid-limit analysis.
  • I. INTRODUCTION: Simulations show that D-BP eliminates excessive delays under the last packet problem, improves fairness, and prevents starving flows.The delay-based greedy approximation has a throughput region no smaller than its queue-based counterpart.

II. SYSTEM MODEL

The system models multihop wireless networks as directed graphs with fixed, loop-free routes, flow-specific queues, interference-constrained schedules, and stochastic source arrivals.

  • Network and traffic model: Flows use single, fixed, loop-free routes with finite hop counts, while unit link capacity is adopted for exposition and broader rates are noted as extensible.Each flow's route has H(s) hops, with Hmax finite; the single-route and unit-capacity assumptions are for ease of exposition.
  • Wireless interference and scheduling: Schedules activate link-flow pairs subject to interference, and feasible schedules form a set whose convex hull characterizes admissible service mixtures.A schedule is represented by a binary vector, and feasibility excludes simultaneously active interfering pairs.
  • Arrivals and queues: Source arrivals are modeled as stationary, ergodic Markov chains satisfying the Strong Law of Large Numbers, with mean rates collected in an arrival-rate vector.The model assumes countable state spaces and defines λ_s as each flow's mean arrival rate.
  • Arrivals and queues: Each link-flow queue tracks packets, service, and actual transmissions, with queue evolution driven by source arrivals and forwarding across successive hops.The model distinguishes scheduled service from actual packet transmission and defines cumulative upstream queue lengths for each flow.
  • Stability and throughput: The throughput region consists of arrival rates yielding stability under a policy, while the optimal region is the union of regions achievable by all scheduling policies.Stability is defined through positive recurrence of the underlying Markov chain.

III. QUEUE-LENGTH-BASED BACK-PRESSURE ALGORITHM

The queue-length-based back-pressure algorithm selects schedules using queue differentials and is analyzed with fluid-limit methods to establish throughput optimality.

  • Throughput analysis: Q-BP is stated to stabilize the network for every feasible arrival-rate vector, providing the baseline for the delay-based analysis.The subsequent proof uses fluid limits and standard Lyapunov techniques.
  • Algorithm definition: Q-BP schedules link-flow pairs through a MaxWeight problem whose weights are queue differentials, with arbitrary tie-breaking among maximizers.The paper revisits Q-BP throughput optimality using fluid-limit techniques before extending the analysis to delay-based back-pressure.

A. Fluid Limits

The fluid-limit construction rescales stochastic network processes into deterministic limits and establishes structural queue-differential properties needed for stability analysis.

  • Fluid-limit construction: Fluid limits are obtained from subsequential, uniformly-on-compactly convergent scalings of the network processes under SLLN and boundedness assumptions.The limiting functions are absolutely continuous, so derivatives exist at almost all regular times.
  • Fluid model: Fluid model solutions satisfy deterministic flow equations, and every fluid limit is a solution of those equations.The fluid network is described as the deterministic equivalent of the original stochastic network.
  • Queue-differential structure: Under Q-BP, queue differentials remain nonnegative when initially so, and with the stated initial condition cumulative differential quantities remain nonnegative over time.The argument uses unit-capacity bounds on queue changes and induction across hops.
  • Queue-differential structure: For every flow, after a finite time all hop-wise queue-differential inequalities hold, established inductively from upstream to downstream queues.The proof uses source arrivals, stability of scheduled subsystems, and forwarding into downstream queues.

B. Throughput-Optimality of Q-BP

The Q-BP throughput proof combines a linear queue-length/delay relation in fluid limits with Lyapunov drift arguments to establish stability inside the optimal region.

  • Throughput-optimality: Q-BP supports every arrival-rate vector strictly inside the optimal throughput region Λ∗.This is stated as Proposition 2 and proved using fluid limits and standard Lyapunov techniques.
  • Queue-delay relation: The analysis establishes a linear relation between cumulative queue lengths and waiting times, which is used to prove Q-BP stability.The relation connects fluid-limit queue and delay variables in the throughput-optimality argument.
  • Lyapunov stability proof: For sufficiently large fluid-model Lyapunov values, the upper right derivative is negative, yielding eventual contraction of fluid states toward the origin.The contraction argument implies that fluid limits become arbitrarily small after a finite time.
  • Lyapunov stability proof: The proof completes by combining fluid-limit convergence, uniform integrability, and the required lemma condition to establish positive recurrence.The final step uses convergence in the mean and concludes the stability result.

A. Algorithm Description

D-BP uses a new delay metric based on packet sojourn times and schedules non-interfering link-flow-pairs by maximizing delay differential weight. This metric preserves a queue-length–delay relationship while addressing the last packet problem.

  • Delay metric: D-BP defines packet delay as network sojourn time, measured from arrival at the source, and uses the HOL packet’s sojourn time for each queue.The delay metric tracks time in the network rather than only waiting time at the current queue.
  • Scheduling rule: D-BP assigns each link-flow-pair a delay-differential weight and solves a MaxWeight problem over non-interfering schedules.Ties between schedules with equal maximum weight may be broken arbitrarily.
  • Queue-length connection: The new delay metric is designed so that large delay differentials correspond, in the fluid-limit analysis, to large queue-length differentials.The paper establishes a linear relation between queue lengths and delays for multihop traffic.
  • Last packet problem: When packets stop arriving, the source-link delay differential grows for waiting packets, eventually pushing them hop by hop toward the destination.The argument repeats after each hop becomes empty, so all waiting packets are ultimately pushed to the destination.

B. Throughput-Optimality

The throughput analysis establishes a finite-time linear relation between queue lengths and delays in fluid limits. Using this relation, D-BP is shown to support every arrival-rate vector strictly inside the optimal region Λ∗.

  • Fluid-limit relation: The fluid-limit analysis establishes a finite-time linear relation between queue lengths and delays for all link-flow-pairs.This relation is the key property used in the throughput-optimality proof.
  • Stability argument: After a finite time, D-BP schedules links similarly to Q-BP in the generalized system and stabilizes that system when the arrival vector is strictly inside Λ∗.The argument relies on the queue-length–delay relation within the generalized system.
  • Proof structure: The proof uses induction over subsets of link-flow-pairs, exploiting hop-by-hop packet travel to extend service from earlier hops to later ones.The inductive construction repeatedly enlarges the subset of link-flow-pairs whose initial fluid has been served.
  • Throughput result: D-BP can support any traffic with an arrival-rate vector strictly inside Λ∗.The paper identifies this as the throughput-optimality proposition for D-BP.

V. GREEDY ALGORITHMS

The paper extends delay-based scheduling to greedy maximal scheduling, motivated by the implementation complexity of exact MaxWeight. D-GMS achieves an achievable throughput region no smaller than Q-GMS’s.

  • Motivation: D-GMS is motivated as a simpler approximation because exact MaxWeight scheduling can be difficult to implement and involves an NP-hard computation.The paper presents D-GMS as a candidate approximation for D-BP.
  • GMS procedure: Greedy maximal scheduling repeatedly selects the maximum-weight remaining link, disables interfering links, and continues until all links are selected or disabled.Every schedule produced by GMS is maximal.
  • D-GMS algorithm: D-GMS uses delay differentials as link-flow-pair weights and applies greedy maximal scheduling in decreasing weight order under interference constraints.This provides a delay-based greedy counterpart to queue-length-based Q-GMS.
  • Throughput result: The achievable throughput region of D-GMS is no smaller than that of Q-GMS.The result follows by adapting the D-BP fluid-limit argument to establish a queue-length–delay relation.

VI. NUMERICAL RESULTS

The simulations show that delay-based scheduling removes excessive delays caused by the last packet problem while preserving throughput performance. Across multihop scenarios, D-BP matches Q-BP's throughput region and improves delay fairness, whereas D-GMS remains incompletely characterized.

  • Last packet problem: Under Q-BP, short-flow packets can become stuck and their delay can increase linearly because later arrivals do not increase the queue length.D-BP instead serves the short flow while keeping its delay close to zero.
  • Throughput comparison: D-BP achieves the same throughput region as Q-BP in the grid-network simulations, supporting the theoretical throughput result.The comparison uses average total queue length under scaled offered loads.
  • Delay performance: Q-BP and D-BP can have similar average network queue lengths even when Q-BP has a much longer delay tail and poorer fairness for some flows.The bursty flow contributes little data, so its excessive delay may not noticeably change the overall average.
  • Delay performance: D-BP substantially reduces mean and percentile delays for the bursty flow compared with Q-BP, eliminating excessive packet delays.The delay distribution tail under D-BP vanishes faster, and its mean, 1st-percentile, and 5th-percentile delays are lower.
  • GMS comparison: In the ring-network experiment, Q-GMS is not throughput-optimal, while D-GMS supports larger throughput for ε < 0.04 but remains incompletely characterized.The average queue length increases from ε = 0 for Q-GMS and from ε = 0.04 for D-GMS; the paper identifies full characterization of D-GMS limits as an open problem.

VII. CONCLUSION

The paper develops a throughput-optimal delay-based back-pressure scheduler for multihop wireless networks with fixed routes. Its delay metric addresses excessive delays associated with queue-based scheduling, while dynamic-routing optimality remains open.

  • The proposed delay-based back-pressure scheme achieves throughput-optimality for multihop wireless networks with fixed routes.The scheme introduces a delay metric suitable for multihop traffic.
  • A linear relation between queue lengths and delays in fluid limits supports the performance analysis and throughput-optimality proof.
  • Delay-based scheduling addresses the last packet problem and avoids flow starvation without sacrificing throughput.
  • The study is limited to multihop flows with fixed routes; throughput-optimality under dynamic routing remains unresolved.

APPENDIX B

The appendix proves a finite-time progression result for link-flow-pairs under the delay-based back-pressure analysis. The argument uses induction and bounded unavailable time to extend the result across link-flow-pairs.

  • Inductive proof: The proof proceeds by induction, extending a finite-time property from one link-flow-pair to additional pairs until the lemma follows.The inductive step adds a new link-flow-pair to the established subset.
  • Inductive extension: The proof selects sufficiently large finite times so that the inductive condition extends to another link-flow-pair outside the current subset.
  • Scheduling argument: Positive-weight feasible schedules force the scheduler to serve packets, because an idle schedule cannot maximize summed weight.
  • Generalized system: As time grows, bounded unavailable time makes schedules concentrate on the established subset, rendering weights outside it negligible.
  • Stability step: The established link-flow-pairs are stable under D-BP because the queue-length–delay linear relation applies to the corresponding generalized system.

APPENDIX C LEMMA 8

Lemma 8 establishes that under Q-BP, a fluid-limit condition eventually holds for every link-flow-pair. The proof propagates the condition hop by hop and across flows using induction and subsystem stability.

  • Lemma statement: For arrival rates strictly inside the capacity region, there is a finite time after which the fluid limits satisfy the lemma’s condition for all link-flow-pairs.
  • Hop-by-hop induction: The proof establishes the condition first at a flow’s initial hop and then propagates it to successive hops by induction.
  • Subsystem stability: If the set of pairs satisfying the condition stops expanding, Q-BP schedules only that set and the resulting subsystem is stable.
  • Expansion argument: Stability bounds the relevant fluid queues, enabling the argument to show that another link-flow-pair eventually satisfies the condition.
  • Completion: Because the system contains finitely many link-flow-pairs, recursive application yields a finite time at which the condition holds throughout the network.
Loading 1011.5674v3…