Back-Pressure-Based Packet-by-Packet Adaptive Routing in Communication Networks

Back-Pressure-Based Packet-by-Packet Adaptive Routing in Communication Networks



Back-pressure-based adaptive routing algorithms where each packet is routed along a possibly different path have been extensively studied in the literature. However, such algorithms typically result in poor delay performance and involve high implementation complexity. In this paper, we develop a new adaptive routing algorithm built upon the widely studied back-pressure algorithm. We decouple the routing and scheduling components of the algorithm by designing a probabilistic routing table that is used to route packets to per-destination queues. The scheduling decisions in the case of wireless networks are made using counters called shadow queues. The results are also extended to the case of networks that employ simple forms of network coding. In that case, our algorithm provides a low-complexity solution to optimally exploit the routing–coding tradeoff.


The back-pressure algorithm introduced has been widely studied in the literature. While the ideas behind scheduling using the weights suggested in that paper have been successful in practice in base stations and routers, the adaptive routing algorithm is rarely used. The main reason for this is that the routing algorithm can lead to poor delay performance due to routing loops. Additionally, the implementation of the back-pressure algorithm requires each node to maintain per-destination queues that can be burdensome for a wire line or wireless router.


In an existing algorithms typically result in poor delay performance and involve high implementation complexity.


The main purpose of this paper is to study if the shadow queue approach extends to the case of scheduling and routing. The first contribution is to come up with a formulation where the number of hops is minimized. It is interesting to contrast this contribution. The formulation has the same objective as ours, but their solution involves per-hop queues, which dramatically increases the number of queues, even compared to the back-pressure algorithm. Our solution is significantly different: We use the same number of shadow queues as the back-pressure algorithm, but the number of real queues is very small (per neighbor). The new idea here is to perform routing via probabilistic splitting, which allows the dramatic reduction in the number of real queues. Finally, an important observation in this paper, not found is that the partial ”decoupling” of shadow back-pressure and real packet transmission allows us to activate more links than a regular back-pressure algorithm would. This idea appears to be essential to reduce delays in the routing case, as shown in the simulations.


Our adaptive routing algorithm can be modified to automatically realize this tradeoff with good delay performance.

The routing algorithm is designed to minimize the average number of hops used by packets in the network. This idea, along with the scheduling/routing decoupling, leads to delay reduction compared with the traditional back-pressure algorithm.



ü Processor             –        Pentium –III

ü Speed                             –         1.1 Ghz

ü RAM                    –        256 MB(min)

ü Hard Disk            –        20 GB

ü Key Board            –        Standard Windows Keyboard

ü Mouse                  –        Two or Three Button Mouse

ü Monitor                –        SVGA


v   Operating System          : LINUX

v   Tool                               : Network Simulator-2

v   Front End                      : OTCL (Object Oriented Tool Command  Language)



Eleftheria Athanasopoulou, Member, IEEE,LocX.Bui, Associate Member, IEEE, Tianxiong Ji, Member, IEEE, R. Srikant, Fellow, IEEE, and Alexander Stolyar “Back-Pressure-Based Packet-by-Packet Adaptive Routing in Communication Networks”- IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 21, NO. 1, FEBRUARY 2013.


About the Author