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.
Introduction
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.L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks, IEEE Transactions on Automatic Control, vol. 37, no. 12, pp. 1936-1948, Dec. 1992.L. Georgiadis, M. J. Neely, and L. Tassiulas, "Resource Allocation and Cross-Layer Control in Wireless Networks," Foundations and Trends in Networking, vol. 1, no. 1, pp. 1-149, 2006.
Backpressure principles can also be applied to other areas, such as to the study of product assembly systems and processing networks.L. Jiang and J. Walrand. Scheduling and Congestion Control for Wireless and Processing Networks, Morgan & Claypool, 2010. This article focuses on communication networks, where packets from multiple data streams arrive and must be delivered to appropriate destinations. The backpressure algorithm operates in slotted time. Every time slot it seeks to route data in directions that maximize the differential backlog between neighboring nodes. This is similar to how water flows through a network of pipes via pressure gradients. However, the backpressure algorithm can be applied to multi-commodity networks (where different packets may have different destinations), and to networks where transmission rates can be selected from a set of (possibly time-varying) options. Attractive features of the backpressure algorithm are: (i) it leads to maximum network throughput, (ii) it is provably robust to time-varying network conditions, (iii) it can be implemented without knowing traffic arrival rates or channel state probabilities. However, the algorithm may introduce large delays, and may be difficult to implement exactly in networks with interference. Modifications of backpressure that reduce delay and simplify implementation are described below under Improving delay and Distributed backpressure.
Backpressure routing has mainly been studied in a theoretical context. In practice, ad hoc wireless networks have typically implemented alternative routing methods based on shortest path computations or network flooding, such as Ad Hoc on-Demand Distance Vector Routing (AODV), geographic routing, and extremely opportunistic routing (ExOR). However, the mathematical optimality properties of backpressure have motivated recent experimental demonstrations of its use on wireless testbeds at the University of Southern California and at North Carolina State University.A. Sridharan, S. Moeller, and B. Krishnamachari, "Making Distributed Rate Control using Lyapunov Drifts a Reality in Wireless Sensor Networks," 6th Intl. Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), April 2008.A. Warrier, S. Janakiraman, S. Ha, and I. Rhee, "DiffQ: Practical Differential Backlog Congestion Control for Wireless Networks," Proc. IEEE INFOCOM, Rio de Janeiro, Brazil, 2009.
Origins
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-commodity network flows, was developed in Awerbuch and Leighton.B. Awerbuch and T. Leighton, "A Simple Local-Control Approximation Algorithm for Multicommodity Flow," Proc. 34th IEEE Conf. on Foundations of Computer Science, Oct. 1993. The backpressure algorithm was later extended by Neely, Modiano, and Rohrs to treat scheduling for mobile networks.M. J. Neely, E. Modiano, and C. E. Rohrs, "Dynamic Power Allocation and Routing for Time Varying Wireless Networks," IEEE Journal on Selected Areas in Communications, vol. 23, no. 1, pp. 89-103, January 2005. Backpressure is mathematically analyzed via the theory of Lyapunov drift, and can be used jointly with flow control mechanisms to provide network utility maximization.M. J. Neely. Dynamic Power Allocation and Routing for Satellite and Wireless Networks with Time Varying Channels. Ph.D. Dissertation, Massachusetts Institute of Technology, LIDS. November 2003.M. J. Neely, E. Modiano, and C. Li, "Fairness and Optimal Stochastic Control for Heterogeneous Networks," Proc. IEEE INFOCOM, March 2005.A. Stolyar, "Maximizing Queueing Network Utility subject to Stability: Greedy Primal-Dual Algorithm," Queueing Systems, vol. 50, no. 4, pp. 401-457, 2005.M. J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems, Morgan & Claypool, 2010. (see also Backpressure with utility optimization and penalty minimization).
How it works
Backpressure routing is designed to make decisions that (roughly) minimize the sum of squares of queue backlogs in the network from one timeslot to the next. The precise mathematical development of this technique is described in later sections. This section describes the general network model and the operation of backpressure routing with respect to this model.
The multi-hop queueing network model
Consider a multi-hop network with N nodes (see Fig. 1 for an example with N = 6). The network operates in slotted time . On each slot, new data can arrive to the network, and routing and transmission scheduling decisions are made in an effort to deliver all data to its proper destination. Let data that is destined for node be labeled as commodity c data. Data in each node is stored according to its commodity. For and , let be the current amount of commodity c data in node n, also called the queue backlog. A closeup of the queue backlogs inside a node is shown in Fig. 2. The units of depend on the context of the problem. For example, backlog can take integer units of packets, which is useful in cases when data is segmented into fixed length packets. Alternatively, it can take real valued units of bits. It is assumed that for all and all timeslots t, because no node stores data destined for itself. Every timeslot, nodes can transmit data to others. Data that is transmitted from one node to another node is removed from the queue of the first node and added to the queue of the second. Data that is transmitted to its destination is removed from the network. Data can also arrive exogenously to the network, and is defined as the amount of new data that arrives to node n on slot t that must eventually be delivered to node c.
Let be the transmission rate used by the network over link (a,b) on slot t, representing the amount of data it can transfer from node a to node b on the current slot. Let be the transmission rate matrix. These transmission rates must be selected within a set of possibly time-varying options. Specifically, the network may have time-varying channels and node mobility, and this can affect its transmission capabilities every slot. To model this, let S(t) represent the topology state of the network, which captures properties of the network on slot t that affect transmission. Let represent the set of transmission rate matrix options available under topology state S(t). Every slot t, the network controller observes S(t) and chooses transmission rates within the set . The choice of which matrix to select on each slot t is described in the next subsection.
This time-varying network model was first developed for the case when transmission rates every slot t were determined by general functions of a channel state matrix and a power allocation matrix. The model can also be used when rates are determined by other control decisions, such as server allocation, sub-band selection, coding type, and so on. It assumes the supportable transmission rates are known and there are no transmission errors. Extended formulations of backpressure routing can be used for networks with probabilistic channel errors, including networks that exploit the wireless broadcast advantage via multi-receiver diversity.M. J. Neely and R. Urgaonkar, "Optimal Backpressure Routing in Wireless Networks with Multi-Receiver Diversity," Ad Hoc Networks (Elsevier), vol. 7, no. 5, pp. 862-881, July 2009.
The backpressure control decisions
Every slot t the backpressure controller observes S(t) and performs the following 3 steps: First, for each link (a,b), it selects an optimal commodity to use. Next, it determines what matrix in to use. Finally, it determines the amount of commodity it will transmit over link (a,b) (being at most , but possibly being less in some cases).
Choosing the optimal commodity
Each node a observes its own queue backlogs and the backlogs in its current neighbors. A current neighbor of node a is a node b such that it is possible to choose a non-zero transmission rate on the current slot. Thus, neighbors are determined by the set . In the extreme case, a node can have all N − 1 other nodes as neighbors. However, it is common to use sets that preclude transmissions between nodes that are separated by more than a certain geographic distance, or that would have a propagated signal strength below a certain threshold. Thus, it is typical for the number of neighbors to be much less than N − 1. The example in Fig. 1 illustrates neighbors by link connections, so that node 5 has neighbors 4 and 6. The example suggests a symmetric relationship between neighbors (so that if 5 is a neighbor of 4, then 4 is a neighbor of 5), but this need not be the case in general.
The set of neighbors of a given node determines the set of outgoing links it can use for transmission on the current slot. For each outgoing link (a,b), the optimal commodity is defined as the commodity that maximizes the following differential backlog quantity:
Any ties in choosing the optimal commodity are broken arbitrarily.
An example is shown in Fig. 2. The example assumes each queue currently has only 3 commodities: red, green, and blue, and these are measured in integer units of packets. Focusing on the directed link (1,2), the differential backlogs are:
Hence, the optimal commodity to send over link (1,2) on slot t is the green commodity. On the other hand, the optimal commodity to send over the reverse link (2,1) on slot t is the blue commodity.
Choosing the μab(t) matrix
Once the optimal commodities have been determined for each link (a,b), the network controller computes the following weights :
The weight is the value of the differential backlog associated with the optimal commodity for link (a,b), maxed with 0. The controller then chooses transmission rates as the solution to the following max-weight problem (breaking ties arbitrarily):
As an example of the max-weight decision, suppose that on the current slot t, the differential backlogs on each link of the 6 node network lead to link weights given by:
While the set might contain an uncountably infinite number of possible transmission rate matrices, assume for simplicity that the current topology state admits only 4 possible choices:
illustration of the 4 possible transmission rate selections under the current topology state S(t). Option (a) activates