# Delay-aware Backpressure Routing Using Graph Neural Networks

arXiv: https://arxiv.org/abs/2211.10748 · HTML: https://mlsanity.com/paper/2211.10748/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 34 references that are in the map.
- First posted on arXiv 19 Nov 2022.

## Builds on (most cited first, 9 of 9)

- [Distributed Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2011.09430/) (2020)
- [Link Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2109.05536/) (2021)
- [Massive Access for 5G and Beyond](https://mlsanity.com/paper/2002.03491/) (2020)
- [The Internet of Battle Things](https://mlsanity.com/paper/1712.08980/) (2017)
- [Distributed Link Sparsification for Scalable Scheduling Using Graph Neural Networks](https://mlsanity.com/paper/2203.14339/) (2022)
- [Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time](https://mlsanity.com/paper/1811.03337/) (2018)
- [Delay-Oriented Distributed Scheduling Using Graph Neural Networks](https://mlsanity.com/paper/2111.07017/) (2021)
- [Enhancing the Delay Performance of Dynamic Backpressure Algorithms](https://mlsanity.com/paper/1502.03276/) (2015)
- [Loop-Free Backpressure Routing Using Link-Reversal Algorithms](https://mlsanity.com/paper/1503.06857/) (2015)

## Built on by (most cited first, 3 of 3)

- [Congestion-aware Distributed Task Offloading in Wireless Multi-hop Networks Using Graph Neural Networks](https://mlsanity.com/paper/2312.02471/) (2023)
- [Biased Backpressure Routing Using Link Features and Graph Neural Networks](https://mlsanity.com/paper/2407.09753/) (2024)
- [A Differentiable Digital Twin of Distributed Link Scheduling for Contention-Aware Networking](https://mlsanity.com/paper/2512.10874/) (2025)

## Abstract (arXiv)

We propose a throughput-optimal biased backpressure (BP) algorithm for routing, where the bias is learned through a graph neural network that seeks to minimize end-to-end delay. Classical BP routing provides a simple yet powerful distributed solution for resource allocation in wireless multi-hop networks but has poor delay performance. A low-cost approach to improve this delay performance is to favor shorter paths by incorporating pre-defined biases in the BP computation, such as a bias based on the shortest path (hop) distance to the destination. In this work, we improve upon the widely-used metric of hop distance (and its variants) for the shortest path bias by introducing a bias based on the link duty cycle, which we predict using a graph convolutional neural network. Numerical results show that our approach can improve the delay performance compared to classical BP and existing BP alternatives based on pre-defined bias while being adaptive to interference density. In terms of complexity, our distributed implementation only introduces a one-time overhead (linear in the number of devices in the network) compared to classical BP, and a constant overhead compared to the lowest-complexity existing bias-based BP algorithms.