Backpressure routing

In queueing theory, a discipline within the mathematical theory of probability, the backpressure routing algorithm is a method for directing traffic around a queueing network that achieves maximum network throughput, which is established using concepts of Lyapunov drift. Backpressure routing considers the situation where each job can visit multiple service nodes in the network. It is an extension of max-weight scheduling where each job visits only a single service node. In queueing theory, a discipline within the mathematical theory of probability, the backpressure routing algorithm is a method for directing traffic around a queueing network that achieves maximum network throughput, which is established using concepts of Lyapunov drift. Backpressure routing considers the situation where each job can visit multiple service nodes in the network. It is an extension of max-weight scheduling where each job visits only a single service node. Backpressure routing is an algorithm for dynamically routing traffic over a multi-hop network by using congestion gradients. The algorithm can be applied to wireless communication networks, including sensor networks, mobile ad hoc networks (MANETS), and heterogeneous networks with wireless and wireline components. Backpressure principles can also be applied to other areas, such as to the study ofproduct assembly systems and processing networks.This article focuses on communication networks,where packets from multiple data streams arrive andmust be delivered to appropriate destinations. The backpressurealgorithm operates in slotted time. Every time slot it seeks to route data in directions thatmaximize the differential backlog between neighboring nodes. This is similar to how waterflows through a network of pipes via pressure gradients. However, the backpressure algorithmcan be applied to multi-commodity networks (where different packets may have different destinations),and to networks where transmission rates can be selectedfrom a set of (possibly time-varying) options. Attractive featuresof the backpressure algorithm are: (i) it leads to maximum network throughput, (ii)it is provably robust to time-varying network conditions, (iii) itcan be implemented without knowing traffic arrival rates or channel stateprobabilities. However, the algorithm may introduce large delays, and maybe difficult to implement exactly in networks with interference. Modifications ofbackpressure that reduce delay and simplify implementation are described belowunder Improving delay and Distributed backpressure. Backpressure routing has mainly been studied in a theoreticalcontext. In practice, ad hoc wireless networks have typicallyimplemented alternative routing methods based on shortestpath computations or network flooding, such asAd Hoc on-Demand Distance Vector Routing (AODV),geographic routing, and extremely opportunistic routing (ExOR).However, the mathematical optimality properties of backpressurehave motivated recent experimental demonstrations of its useon wireless testbeds at the University of Southern Californiaand at North Carolina State University. The original backpressure algorithm was developed by Tassiulas and Ephremides. They considered a multi-hop packet radio network with random packet arrivals and a fixed set of link selection options. Their algorithm consisted of a max-weight link selection stage and a differential backlog routing stage.An algorithm related to backpressure,designed for computing multi-commoditynetwork flows, was developed in Awerbuch and Leighton.The backpressure algorithm was later extended by Neely, Modiano, and Rohrs to treat scheduling for mobile networks.Backpressure is mathematically analyzed via the theory of Lyapunov drift, and can be used jointly with flow control mechanisms to provide network utility maximization.(see also Backpressure with utility optimization and penalty minimization).