Source-linked AI summary
Novel Architectures and Algorithms for Delay Reduction in Back-pressure Scheduling and Routing
Loc Bui, R. Srikant, Alexander Stolyar
TL;DR
The paper addresses poor delay in throughput-optimal back-pressure caused by queueing structure and unnecessarily long routes. It introduces shadow-queue architectures and a minimum-resource routing modification to reduce delay while retaining throughput optimality. The shadow architecture also reduces physical queueing complexity, although its adaptive-routing use cannot rely on just one per-neighbor queue.
Problem
Back-pressure can have poor delay because it uses separate queues and may route packets along unnecessarily long paths.
Method
The paper proposes shadow queues with per-neighbor physical FIFO queues and a routing algorithm that forces use of minimum network resources.
Results
The proposed architectures reduce queue backlog and physical queues, while the routing algorithm maintains throughput optimality and improves delay performance.
Takeaways & Limitations
Back-pressure can be modified to pay attention to delay while preserving throughput optimality and reducing queueing-data-structure complexity.
Takeaways & Limitations
For adaptive routing, the shadow algorithm cannot use just one per-neighbor queue at a node.
Abstract
from arXiv · showhide
The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its delay performance may be quite poor even when the traffic load is not close to network capacity due to the following two reasons. First, each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. Second, the back-pressure routing algorithm may route some packets along very long routes. In this paper, we present solutions to address both of the above issues, and hence, improve the delay performance of the back-pressure algorithm. One of the suggested solutions also decreases the complexity of the queueing data structures to be maintained at each node.
I. INTRODUCTION
The paper targets poor delay performance in throughput-optimal back-pressure scheduling, addressing long route selection and excessive queueing complexity. It proposes shadow queues for adaptive per-flow service and per-neighbor physical queues, plus routing that favors short paths while preserving throughput optimality.
- Motivation: Back-pressure can have poor delay because it maintains separate commodity queues, serves one queue at a time, and may select very long routes.The paper separates fixed-routing queueing problems from adaptive-routing path-length problems.
- Fixed routing: Θ(K2) total backlog is expected on a K-hop path under back-pressure, versus linear end-to-end backlog under fixed per-flow service rates.The quadratic intuition follows increasing queue lengths toward the source, while fixed service keeps each hop roughly O(1).
- Shadow queues: Shadow queues allocate service rates adaptively without knowing packet arrival rates and can reduce the number of real queues maintained at each node.For fixed routing, the proposed architecture uses per-neighbor rather than per-flow physical queues.
- Shadow queues: Per-neighbor queues can significantly reduce implementation complexity because large networks typically have more flows than neighbors per node.The paper also identifies delay reduction as an additional benefit of the shadow-queue implementation.
- Adaptive routing: The adaptive-routing modification explores short paths first and uses long paths only when needed, while continuing to maintain throughput optimality.This changes the routing objective to account for delay rather than maximizing throughput without QoS considerations alone.
II. SYSTEM MODEL
The system model represents wireless networks as graph-based, slotted systems with fixed or adaptive routes, valid schedules, flow rates, and capacity regions. It distinguishes stability for inelastic traffic from utility-based resource allocation for elastic traffic, then introduces the fixed-routing shadow architecture.
- Network model: The network is modeled as a graph G = (N, L) with slotted time and link transmissions constrained by wireless interference.Valid schedules form Γ, and co(Γ) denotes their convex hull.
- Flows and routing: Flows enter at begin nodes, traverse multiple hops, and exit at end nodes; routes may be predetermined or adaptive.For each flow f, b(f) and e(f) denote its entering and exiting nodes.
- Capacity region: With adaptive routing, the capacity region contains flow rates supportable by the network; with fixed routing, it depends on the specified routes.Fixed-routing feasibility is expressed through link-rate allocations in co(Γ).
- Traffic models: Inelastic traffic has fixed rates and requires stable queues, whereas elastic traffic requires fair resource allocation according to concave, nondecreasing flow utilities.The elastic objective allocates rates within the network capacity region.
- Shadow architecture: The paper introduces a shadow queueing system for fixed routing that performs flow control and resource allocation while using one physical FIFO queue per outgoing link.This per-neighbor architecture is presented as a delay-reduction mechanism and a reduction in maintained queues.
A. Description
The shadow algorithm replaces per-flow physical queues with shadow counters for scheduling while storing real packets in per-link FIFO queues. Shadow permits coordinate transmissions, and thinning real traffic below shadow traffic supports queue stability and can reduce delay.
- Queues and Counters: Traditional back-pressure requires the queue length of every flow passing through a node, whereas the shadow design decouples storage from scheduling.The design uses counters for flow-specific scheduling information and separate FIFO queues for stored packets.
- Queues and Counters: Each node maintains one shadow counter per flow, but real packets are stored in a FIFO queue for each outgoing link.Packets are forwarded to the FIFO queue of their next-hop link based on the packet header.
- Back-pressure scheduling: Each link selects the flow with the maximum shadow differential backlog and transmits corresponding shadow and real packets under the scheduled allocation.Shadow-packet transmission updates counters, while the real FIFO queue supplies up to the same number of packets.
- Back-pressure scheduling: Shadow packets act as link-associated permits rather than link-and-flow-associated permits, simplifying the queueing data structure.A counter update subtracts permits from the upstream shadow queue and adds them to the downstream shadow queue.
- Congestion control: For elastic traffic, real traffic is generated at βxf[t] with β<1, and simulations report smaller network backlog for smaller β.The factor β keeps real arrivals slightly below shadow arrivals to support stability.
- Inelastic traffic: For inelastic traffic, shadow arrivals must exceed real arrivals for stability; an alternative β-scaled implementation can overflow its edge buffer and lose packets.The text states that packet loss is unavoidable unless the arrival rate is below the capacity allocated to the flow.
B. Stability of the shadow algorithm
The paper establishes that shadow-queue congestion control and scheduling asymptotically achieve optimal rate allocation while keeping shadow and real queues stable. In a linear-network analysis, traditional back-pressure can produce queueing growth that is quadratic in route length, motivating the shadow approach.
- Shadow-queue stability: The shadow congestion-control and scheduling algorithms asymptotically achieve the optimal rate allocation x∗.The shadow queues are also positive recurrent with bounded steady-state expected lengths.
- Real-queue stability: The joint process of shadow and real queues is an irreducible, aperiodic, positive recurrent Markov chain, so the real FIFO queues are stable.The proof uses fluid limits and stability results for FIFO queueing networks with load strictly below capacity.
- Real-queue stability: Shadow scheduling provides each link an average service rate strictly greater than its nominal real-traffic load because actual traffic is thinned.The resulting fluid model has constant link capacities equal to the shadow algorithm’s average service rates.
- Rate allocation: The real traffic throughput is slightly below the optimal solution, but the gap can be made arbitrarily small by adjusting β.This trade-off follows from generating real traffic at a fraction of the shadow rate.
- Delay analysis: For a linear network with N links, traditional back-pressure with congestion control can yield quadratic end-to-end queueing delay in the number of hops.The paper’s calculations and simulations associate this behavior with quadratic growth of total queue length along a flow route.
- Delay analysis: When a fixed rate larger than the arrival rate is allocated to each flow, the total queue length is expected to grow as order N rather than N^2.This comparison is stated for the analyzed linear-network setting.
B. Inelastic traffic under the traditional back-pressure algorithm
Under inelastic traffic and fixed routes, the paper analyzes traditional back-pressure’s end-to-end backlog growth and compares it with the shadow algorithm in a linear-network simulation. The simulation reports substantially lower real FIFO queue lengths with only 1% traffic thinning.
- Backlog bound: Theorem 3 gives an upper bound on end-to-end queue backlog for fixed-route flows in a general topology under load strictly inside the capacity region.The assumptions include a maximum route length Kmax, an interior-load slack condition, and independent arrival processes.
- Backlog growth: The derived bound suggests quadratic growth of total flow queue length with route length, and simulations validate this growth for traditional back-pressure.The analysis concerns inelastic traffic with fixed flow rates.
- Simulation results: For flow 0, shadow queue lengths increase nearly linearly from the end node toward the beginning of the 40-link network, producing quadratic backlog growth.This pattern is reported for λ0=5, λ1=2.5, and β=0.99.
- Simulation results: 1% traffic thinning significantly reduces real FIFO queue lengths relative to the unthinned setting.The simulation sends real traffic at βλi with β∈(0,1), and the reported reduction occurs even for a small amount of thinning.
D. Simulation results for elastic traffic
The simulations evaluate shadow queues in linear and grid networks, showing substantially smaller real queues than traditional back-pressure while introducing a throughput trade-off. They also examine min-resource routing, which favors shorter paths but requires balancing the parameter M.
- Simulation setup: The simulations use a 16-node, 24-link grid with 48 flows, logarithmic utilities, one-hop interference, and link capacity 10.A matching represents a valid schedule, and each scheduled link can transmit up to 10 packets per time slot.
- Shadow-queue results: Shadow queues dramatically reduce total real queue length compared with traditional back-pressure.The traditional algorithm’s queue length corresponds to the shadow queue length, making the real-queue comparison explicit.
- Shadow-queue results: After 500,000 time slots, total shadow queue length is about 82,000, while total real queues are about 2,000, 800, and 500 for β=0.99, 0.97, and 0.95.The reported real-queue values decrease as β decreases across these simulations.
- Shadow-queue results: These gains are obtained at the expense of a small throughput loss represented by 1−β.The passage characterizes the performance improvement and throughput reduction as a trade-off.
- Min-resource routing: Min-resource routing adds total link traffic as a cost, thereby preferring shorter-hop paths in equal-capacity networks.The approach targets unnecessarily long or looping routes and differs from traditional back-pressure through an M adjustment to link weights.
- Min-resource routing: The parameter M requires balancing optimality, queue size, and convergence: larger M gives O(M) queues and slower convergence, whereas small M can move the stationary regime too far from optimal.The authors conclude that a practical M should be neither too large nor too small, consistent with the simulations.
B. Simulation results
Simulations compare modified back-pressure variants with the traditional algorithm under fixed-rate traffic and node-exclusive interference. The modified algorithm uses shorter, minimum-resource routes and generally lowers queue backlog, although increasing M can slightly worsen delay.
- Simulation setup: The simulation uses an 8-node, 10-link, 2-flow network with link capacity 10 under node-exclusive spectrum sharing.Flows enter at nodes 3 and 1 and exit at nodes 4 and 6; routes are not prespecified.
- Simulation setup: The network is stabilized by back-pressure when λ < 10, with Poisson arrivals and 1-million-slot simulation runs averaged over 40 trials.
- Rate allocation: The traditional algorithm uses all network links, whereas modified back-pressure with M = 10 or M = 20 essentially uses the minimum-resource routes.For flow 0, this is link (3, 4); for flow 1, link (1, 6).
- Queue backlog: The modified algorithm with M = 10 has significantly smaller queue backlog than traditional back-pressure across the evaluated λ values.
- Queue backlog: Increasing M to 20 makes delay performance slightly worse, confirming a trade-off in selecting M.
- Architecture: The shadow architecture reduces queue backlog and physical queue count by using FIFO queues per outgoing link rather than per-flow queues.The paper relates lower backlog to lower delay through Little’s law.
- Architecture: The proposed algorithm forces minimum network-resource use while retaining throughput optimality, improving delay relative to traditional back-pressure.
- Adaptive routing: For adaptive routing, the shadow algorithm cannot use only one FIFO queue per neighbor; separate destination queues make the extension straightforward.Maintaining a single per-neighbor FIFO queue under adaptive routing remains future work.
APPENDIX A
The appendix formalizes the fixed-routing shadow-queue system through packet-class, arrival, service, workload, and queue processes. It derives fluid-model equations and convergence properties used to establish stability and throughput support.
- Stability analysis: A scheduling outcome converges to link rates capable of supporting the given flow arrival rates.
- Model definitions: Each fixed-route flow is decomposed into packet classes, with one class corresponding to each link on the flow’s route.
- Model definitions: The appendix defines constituency and routing matrices, external and total arrivals, departures, packet-class queues, link FIFO queues, service time, idle time, and workload.
- System equations: Vector equations describe system evolution, while FIFO and service constraints provide the queueing relationships used in the analysis.
- Technical assumptions: The analysis assumes right-continuous processes with left limits for queueing quantities and continuous service and idle-time processes.
- Stability analysis: The shadow-queue process is Markov and positive recurrent, and time-average real packet arrivals converge to the optimal solution.
A. Preliminaries
The preliminaries introduce convergence and stability results for scaled shadow-queue processes. These results provide the probabilistic framework for proving positive recurrence of the original queueing system.
- Fluid-model criteria: Theorem 5 states that scaled queue norms converge in expectation to zero after some finite time T.
- Stability results: Positive recurrence of the joint real-and-shadow queue process establishes stability of the queueing system.
- Fluid-model criteria: The fluid-limit argument requires subsequential convergence, eventual fluid-state contraction, and uniform integrability.
- Fluid-model criteria: Under those conditions, the original process is positive recurrent.
B. Proof’s details
The proof details establish compactness and continuity of scaled processes, identify their fluid limits, and show that these limits satisfy stable fluid-model equations with vanishing shadow queues.
- Scaled-process convergence: The limiting process is continuous with probability one, making Skorohod and uniform convergence compatible for the proof.
- Technical definitions: The appendix defines Skorohod and uniform-on-compact convergence for functions in Dd[0, ∞).
- Scaled-process convergence: Scaled processes are shown to be asymptotically Lipschitz, yielding relative compactness and weakly convergent subsequences.
- Fluid-limit identification: Fluid limits satisfy the fluid-model equations, and their shadow-queue component is zero for all t.
- Fluid-limit identification: The proof transfers queueing relations to the fluid limit using convergence, continuity, and the flatness of idle time whenever workload is positive.
- Stability conclusion: Stability of every fluid-model solution follows from Bramson’s result, completing the proof of Theorem 2.
APPENDIX B
Appendix B defines route-related node notation, formulates queue dynamics and a Lyapunov-drift argument, and concludes stability from a bounded auxiliary quantity and positive recurrence. The proof assumes arrival rates strictly inside the capacity region and uses positive minimum route-link rates.
- Route notation: R(f) contains the nodes on flow f's route, so |R(f)| = |L(f)| + 1.
- Route notation: For nodes on a flow route, n + 1 and n −1 denote the next and previous route nodes, excluding the route's endpoint nodes.
- Stability proof: The appendix specifies queue dynamics, rewrites them, and evaluates the drift of a Lyapunov function.
- Stability proof: Because λ lies strictly inside Λ, the proof introduces a positive ǫ and a vector of link rates µ ∈ co(Γ).
- Stability proof: The minimum link rate µL(f) is positive for every flow route and is defined by the smallest rate among links on that route.
- Stability proof: B1[t] is bounded by b|F|Kmax for all t, and this bound together with positive recurrence of Q[t] yields the desired result.