PaperlayerView exact revision on arXiv

Source-linked AI summary

Biased Backpressure Routing for Multihop Wireless Networks with Heterogeneous Interfaces

Yujun Ming, Zhongyuan Zhao, Fikadu Dagefu, Justin Kong, Terrence Moore, Kevin Chan, Ananthram Swami, Santiago Segarra

arXiv:2609.05844v1cs.NIcs.SYeess.SPeess.SY

TL;DR

In Het-MuNets, interface assignment determines the topology used for routing and scheduling, making their joint optimization challenging. The paper models interface choices as virtual routing within a multi-layer SP-BP framework; numerical results report better goodput, latency, and packet delivery than BP and non-BP baselines.

  • Problem

    In Het-MuNets, interface assignment determines routing and scheduling topology, and extending homogeneous SP-BP to these heterogeneous networks remains an open challenge.

    Source: §I · p. 1

  • Method

    A multi-layer graph represents interfaces as subnodes connected by virtual links, turning interface assignment into intra-device routing jointly optimized with physical routing and scheduling.

    Source: §I · p. 2

  • Results

    The proposed framework reduces latency and improves packet delivery and goodput compared with BP and non-BP baselines.

    Source: §I · p. 2

  • Takeaways & Limitations

    In interference-constrained environments, joint optimization improves resource utilization and manages inter-flow interference.

    Source: §V · p. 6

Abstract

from arXiv · show

Heterogeneous-interface multihop wireless networks (Het-MuNets) are emerging as a promising paradigm for tactical networks and for infrastructure-light applications such as vehicular communications, wireless backhaul, and non-terrestrial connectivity. To exploit the diverse profiles of heterogeneous communication technologies in penetration, interference, and bandwidth, packet-to-interface assignment must be determined on a per-hop basis, making routing and scheduling highly complex. In this work, we develop a unified framework for joint packet routing, link scheduling, and interface assignment in Het-MuNets with multiple concurrent flows. By modeling packet-to-interface assignment as transmission between virtual subnodes, we transform interface assignment into intra-device virtual routing, which is solved jointly with physical routing and scheduling under a unified multi-layer shortest path-biased Backpressure (SP-BP) scheme. Numerical results demonstrate that the proposed framework outperforms SP-BP operating on other baseline graph models and non-backpressure routing schemes in goodput, latency, and packet delivery rate.

I. INTRODUCTION

Het-MuNets make joint routing and scheduling complex because interface assignment determines their topology, while extending homogeneous SP-BP to these networks remains challenging. The paper proposes multi-layer SP-BP, which treats interface assignment as virtual routing and jointly optimizes it with physical routing and scheduling.

  • Interface assignment shapes routing and scheduling topology in Het-MuNets, while single-path schemes can face congestion and heterogeneous SP-BP remains a challenge.Classical single-path approaches can also be vulnerable to link failures, multiflow contention, and real-time congestion dynamics.Source: §I · p. 1
  • The multi-layer graph represents device interfaces as subnodes connected by virtual links, turning packet-to-interface assignment into intra-device routing.Each communication technology is represented as a graph layer, enabling joint interface assignment, packet routing, and link scheduling.Source: §I · pp. 1–2
  • Virtual routing uses an exactly solvable polynomial-time minimum-cost flow formulation, while physical routing and scheduling use SP-BP coupled through virtual queues.The scheme is presented as fully distributed and jointly optimizes interface assignment, routing, and scheduling.Source: §I · p. 2
  • The proposed multi-layer routing reduces latency and improves packet delivery and goodput compared with BP and non-BP baselines.Source: §I · p. 2

II. SYSTEM MODEL

The system model represents devices and communication modalities in a multi-layer graph, with virtual links for within-device interface switching and physical links for transmission. It also models per-commodity queues and link conflicts to support joint routing and scheduling.

  • A Het-MuNet is modeled as a directed multigraph whose devices are nodes and whose modality-specific transmissions are edges; multiple edges may connect the same devices.Available modalities can differ by device.Source: §II · p. 2
  • The multi-layer graph places devices in a base layer and modality subnodes in technology layers, using virtual links for within-device packet-interface switching.Physical links belong to their corresponding modality layer; the base node injects exogenous arrivals and has only outgoing virtual links.Source: §II · p. 2
  • A conflict graph represents transceiver and interference conflicts between physical links, and each link needs information only about its conflicting neighbors.Source: §II · pp. 2–3
  • The model uses time-slotted orthogonal multiple access, where valid schedules contain nonconflicting links and link rates are measured in packets per slot.Source: §II · p. 3
  • Each device maintains physical queues by destination commodity, while modality subnodes maintain virtual queues that track packets assigned to each modality.The virtual queues partition physical packets before new arrivals are assigned; virtual assignment changes do not create or remove packets.Source: §II · p. 3

III. BIASED BACKPRESSURE FOR HET-MUNETS

The multi-layer SP-BP procedure alternates virtual modality assignment with physical routing and scheduling, followed by transmission. It uses shortest-path bias and virtual queues to coordinate these operations across interface layers.

III. BIASED BACKPRESSURE FOR HET-MUNETS

  • Each subnode makes distributed decisions using its own and neighboring virtual queues plus instantaneous rates of incident links.Intra-device computation precedes inter-device routing, scheduling, and transmission in each slot.Source: §III · p. 3
  • Stage V assigns packets to modalities through MCF, then Stage P performs SP-BP routing and scheduling within each conflict-graph layer before scheduled transmission.Data transmission is pipelined with the next slot’s intra-device computation.Source: §III · p. 3
  • Shortest-path bias is computed from each subnode to a destination over the multi-layer graph, while virtual-link rates use the receiving subnode’s average outgoing physical-link rate.The virtual-link rate limits packet transfers across modalities.Source: §III · p. 3

A. Coupled Virtual and Physical Stages

The joint MaxWeight problem couples conflict-free virtual links with conflict-aware physical links. The paper approximates it in two stages: virtual modality assignment, then physical routing and scheduling.

A. Coupled Virtual and Physical Stages

  • The MaxWeight formulation uses a feasible joint-action set defined by link-rate, backlog-availability, and conflict-graph constraints.The formulation includes virtual and physical link weights.Source: A. Coupled Virtual and Physical Stages · p. 4
  • The coupled optimization is challenging because it combines conflict-free virtual links with conflict-aware physical links, so the method splits it into two stages.The feasible joint-action set is constrained by link rates, backlog availability, and conflict graphs.Source: A. Coupled Virtual and Physical Stages · p. 4
  • Stage V jointly assigns exogenous and endogenous packets to modalities by solving a virtual-link optimization.Stage P updates intermediate pressure and solves an MWIS problem for joint physical routing and scheduling.Source: A. Coupled Virtual and Physical Stages · p. 4

B. Intra-device Virtual Routing

Stage V carries out modality assignment independently at each device as a minimum-cost flow problem on a directed acyclic graph. Its flow construction encodes packet injection, retention, and modality switching under capacity constraints.

B. Intra-device Virtual Routing

  • Each device independently formulates Stage V as an MCF problem on a DAG, with virtual commodity queues on modality-nodes serving as flow sources.The construction includes transfer nodes for modality changes.Source: B. Intra-device Virtual Routing · p. 4
  • Injection and retention arcs have zero cost, while switching-arc capacities enforce virtual-link rate limits and the one-switch-per-slot structure.Minimizing total flow cost maximizes the Stage-V objective, subject to backlog availability.Source: B. Intra-device Virtual Routing · p. 4
  • A network-simplex MCF solver determines the injection flows for new arrivals and switching flows for packets assigned to another modality.These flows implement packet assignment within the virtual queues.Source: B. Intra-device Virtual Routing · p. 4

C. Stage P and Data Transmission

Stage P runs SP-BP across modality layers using updated virtual queues, then data transmission dequeues packets according to the final rates. Scheduling may use distributed heuristics to approximate the MWIS problem.

C. Stage P and Data Transmission

  • Stage P runs SP-BP in parallel on disjoint graph layers, with separate layers for modalities without cross-modality conflicts and joint layers for mutually conflicting modalities.The procedure includes commodity selection, preliminary rate allocation, MaxWeight scheduling, and final rate assignment.Source: C. Stage P and Data Transmission · p. 4
  • MWIS scheduling is NP-hard, and distributed heuristics such as LGS and GCN-LGS can approximate it.The heuristics are options for the MaxWeight scheduling step.Source: C. Stage P and Data Transmission · p. 4
  • Stages V and P manipulate virtual queues without moving physical-queue packets; packets are dequeued for transmission only after Stage P, avoiding intra-device looping.The final transmission rates determine which packets are dequeued.Source: C. Stage P and Data Transmission · p. 4

D. Complexity Analysis

The analysis gives per-slot computational, signaling, and message-size costs for the distributed routing and scheduling components.

D. Complexity Analysis

  • SP-BP routing takes O(|V0|Dn) operations per slot, while LGS scheduling takes O(Dc) operations per round.Source: D. Complexity Analysis · p. 5
  • SP-BP exchanges neighbor queue states once per slot, giving O(1) signaling rounds; LGS coordination takes O(log |Ep|) rounds.The bias matrix is reused until topology changes; distributed APSP has amortized ˜O(|V|/τB) rounds.Source: D. Complexity Analysis · p. 5
  • SP-BP sends O(|V0|c M) per-modality queue counters per neighbor exchange, while LGS sends O(c M) link weights and scheduling states.Differential updates send only changed SP-BP counters; APSP propagates O(|V0|) bias values per round.Source: D. Complexity Analysis · p. 5

IV. SIMULATION RESULTS

The simulations evaluate routing schemes across generated network sizes, modality layers, traffic settings, and flow configurations, using a common scheduler for the baselines.

IV. SIMULATION RESULTS

  • Ten random topologies are generated for each network size from 20 to 100 nodes, with three communication modalities over the same physical nodes.Each modality induces a distinct connected layer; its interference radius determines its modality-specific conflict graph.Source: §IV · p. 5
  • Each test instance simulates 10 flow configurations for 1000 slots, with source-destination pairs sampled between 30% and 50% of network size.The flow configurations use the modality rates and fading setup described for the generated topologies.Source: §IV · p. 5
  • The comparison includes seven baselines in two categories, and all baselines use the same local greedy scheduler to approximate MWIS scheduling.The categories distinguish SP-BP on baseline graph models from non-BP routing with decoupled MaxWeight scheduling.Source: §IV · p. 5
  • Graph-model baselines include single-modality routing, aggregated link rates, and Siloed layers, which keep each packet on its injection-time layer.The unimodal alternatives include 5G, 2.4G, and UHF; Aggregation combines rates across modalities.Source: §IV · p. 5
  • SP-only uses delay-weighted shortest paths on a collapsed graph, while MCF-Prob uses static probabilistic forwarding from an offline multi-commodity flow solution.MCF-Prob sets each link capacity to its rate divided by conflict degree.Source: §IV · p. 5

A. Network Goodput Analysis

Multi-layer SP-BP achieves the highest mean goodput across the tested streaming injection rates, with its advantage widening at higher load.

A. Network Goodput Analysis

  • Multi-layer SP-BP achieves the highest mean goodput across tested streaming injection rates, and its advantage widens under higher load.Source: A. Network Goodput Analysis · p. 5
  • Siloed layers also improves at higher load but remains below multi-layer SP-BP, while SP-only and MCF-Prob rise more slowly and unimodal baselines saturate lower.The passage attributes unimodal saturation under excessive load to source-near links being prioritized while destination-near links are starved; Aggregation peaks near λ = 3 and then declines.Source: A. Network Goodput Analysis · p. 5

B. Performance under Mixed Traffic

Under mixed streaming and bursty traffic, multi-layer SP-BP maintains strong delivery and delay performance across network sizes, while baseline rankings vary with traffic type.

B. Performance under Mixed Traffic

  • Streaming flows use Poisson arrivals at rates drawn from 0.2 to 1.0, while bursty flows arrive at rates drawn from 6.6 to 33.0 for t < 30 and then stop.The mixed-traffic experiment assigns streaming and bursty flows independently with equal probability.Source: B. Performance under Mixed Traffic · pp. 5–6
  • Under streaming traffic, multi-layer SP-BP keeps delivery above 0.99 across tested network sizes and achieves the lowest end-to-end delay.MCF-Prob approaches it in small networks but delivery falls to approximately 0.86 at 100 nodes as the network grows.Source: B. Performance under Mixed Traffic · p. 6, Figure 5 · p. 6
  • Under bursty traffic, multi-layer SP-BP maintains robust performance across network sizes, while Siloed layers and Aggregation reverse their relative ordering across traffic types.Source: B. Performance under Mixed Traffic · p. 6, Figure 5 · p. 6

V. CONCLUSIONS

The fully distributed multi-layer SP-BP scheme jointly optimizes packet-to-interface assignment, routing, and link scheduling in Het-MuNets. In interference-constrained environments, it improves goodput, latency, and packet delivery rates over static forwarding policies or siloed SP-BP baselines.

  • In interference-constrained environments, the scheme yields superior goodput, latency, and packet delivery rates versus static forwarding policies or siloed SP-BP baselines.Source: §V · p. 6
  • The fully distributed multi-layer SP-BP scheme couples dynamic packet-to-interface assignment with packet routing and link scheduling in Het-MuNets.Source: §V · p. 6
  • Future work will explore advanced bias formulations for energy efficiency, reduced radio footprints, and resilience to mobility and link failures.Source: §V · p. 6
Loading 2609.05844v1…