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.[1] [2]
Backpressure principles can also be applied to other areas, such as to the study ofproduct assembly systems and processing networks.[3] 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.[4] [5]
The original backpressure algorithm was developed by Tassiulas and Ephremides.[1] 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.[6] The backpressure algorithm was later extended by Neely, Modiano, and Rohrs to treat scheduling for mobile networks.[7] Backpressure is mathematically analyzed via the theory of Lyapunov drift, and can be used jointly with flow control mechanisms to provide network utility maximization.[8] [9] [2] [10] [11] (see also Backpressure with utility optimization and penalty minimization).
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 inlater sections. This section describes the general network model and the operation of backpressure routing with respectto this model.
Consider a multi-hop network with N nodes (see Fig. 1 for an example with N = 6).The network operates inslotted time
t\in\{0,1,2,\ldots\}
c\in\{1,...,N\}
n\in\{1,\ldots,N\}
c\in\{1,\ldots,N\}
(c) | |
Q | |
n |
(t)
(c) | |
Q | |
n |
(t)
(c) | |
Q | |
c |
(t)=0
c\in\{1,\ldots,N\}
(c) | |
A | |
n |
(t)
Let
\muab(t)
(\muab(t))
\GammaS(t)
(\muab(t))
\GammaS(t)
(\muab(t))
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.[7] 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.[12]
Every slot t the backpressure controller observes S(t) and performs the following 3 steps:
opt | |
c | |
ab |
(t)
(\muab(t))
\GammaS(t)
opt | |
c | |
ab |
(t)
\muab(t)
Each node a observes its own queue backlogs and the backlogs in its currentneighbors. A current neighbor of node a is a node b such that it is possible to choosea non-zero transmission rate
\muab(t)
\GammaS(t)
\GammaS(t)
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
opt | |
c | |
ab |
(t)
c\in\{1,\ldots,N\}
(c) | |
Q | |
a |
(t)-
(c) | |
Q | |
b |
(t)
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, andblue, and these are measured in integer units of packets. Focusing on the directed link (1,2), the differential backlogs are:
(red) | |
Q | |
1 |
(t)-
(red) | |
Q | |
2 |
(t)=1
(green) | |
Q | |
1 |
(t)-
(green) | |
Q | |
2 |
(t)=2
(blue) | |
Q | |
1 |
(t)-
(blue) | |
Q | |
2 |
(t)=-1
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.
Once the optimal commodities have been determined for each link (a,b), the network controller computes the following weights
Wab(t)
Wab(t)=
| |||||||
max\left[Q | |||||||
a |
(t)-
| ||||||||||
Q | ||||||||||
b |
(t),0\right]
The weight
Wab(t)
(Eq.1) Maximize:
N\mu | |
\sum | |
ab |
(t)Wab(t)
(Eq.2) Subjectto:(\muab(t))\in\GammaS(t)
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
Wab(t)
(Wab(t))=\left[\begin{array}{cccccc} 0&2&1&1&6&0\\ 1&0&1&2&5&6\\ 0&7&0&0&0&0\\ 1&0&1&0&0&0\\ 1&0&7&5&0&0\\ 0&0&0&0&5&0 \end{array} \right]
While the set
\GammaS(t)
\GammaS(t)=\{\boldsymbol{\mu}a,\boldsymbol{\mu}b,\boldsymbol{\mu}c,\boldsymbol{\mu}d\}
illustration of the 4 possible transmission rate selections under the current topology state S(t). Option (a) activatesthe single link (1,5) with a transmission rate of
\mu15=2
These four possibilities are represented in matrix form by:
\boldsymbol{\mu}a=\left[\begin{array}{cccccc} 0&0&0&0&2&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0 \end{array} \right], \boldsymbol{\mu}b=\left[\begin{array}{cccccc} 0&0&0&0&0&0\\ 0&0&1&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0 \end{array} \right]
\boldsymbol{\mu}c=\left[\begin{array}{cccccc} 0&0&0&0&0&0\\ 1&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&1&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0 \end{array} \right], \boldsymbol{\mu}d=\left[\begin{array}{cccccc} 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&1&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&0&0 \end{array} \right]
Observe that node 6 can neither send nor receive under any of these possibilities.This might arise because node 6 is currently out of communication range.The weighted sum of rates for each of the 4 possibilities are:
\sumabWab(t)\muab(t)=12
\sumabWab(t)\muab(t)=1
\sumabWab(t)\muab(t)=1
\sumabWab(t)\muab(t)=12
Because there is a tie for the maximum weight of 12, the network controller can break the tie arbitrarily bychoosing either option
\boldsymbol{\mu}a
\boldsymbol{\mu}d
Suppose now that the optimal commodities
opt | |
c | |
ab |
(t)
(\muab(t))
\muab(t)
opt(t) | |
c | |
ab |
(c) | |
\mu | |
ab |
(t)
(c) | |
\mu | |
ab |
(t)=\begin{cases} \muab(t)&ifc=
opt | |
c | |
ab |
(t)and
| ||||||||||
Q | ||||||||||
a |
| ||||||||||
(t)-Q | ||||||||||
b |
(t)\geq0\\ 0&otherwise \end{cases}
The value of
(c) | |
\mu | |
ab |
(t)
(c) | |
Q | |
n |
(t)<
(c) | |
\sum | |
nb |
(t)
In this case, all of the
(c) | |
Q | |
n |
(t)
The backpressure algorithm does not use any pre-specified paths. Paths are learneddynamically, and may be different for different packets. Delay can be very large, particularly when the system is lightlyloaded so that there is not enough pressure to push data towards the destination. As an example, suppose one packetenters the network, and nothing else ever enters. This packet may take a loopy walk through the network and never arriveat its destination because no pressure gradients build up. This does not contradict the throughput optimality or stabilityproperties of backpressure because the network has at most one packet at any time and hence is trivially stable (achieving a delivery rate of 0, equal to the arrival rate).
It is also possible to implement backpressure on a set of pre-specified paths. This can restrict the capacity region, but might improve in-orderdelivery and delay. Another way to improve delay, without affecting the capacity region, is to use an enhancedversion that biases link weights towards desirable directions.[7] Simulations of such biasing have shown significant delay improvements.[12] [2] Note that backpressure does not require First-in-First-Out (FIFO) service at the queues. It has been observedthat Last-in-First-Out (LIFO) service can dramatically improve delay for the vast majority of packets,without affecting throughput.[13] [14]
Note that once the transmission rates
(\muab(t))
(c) | |
\mu | |
ab |
(t)
A distributed approach for interference networks with link rates that are determined by the signal-to-noise-plus-interference ratio (SINR) can be carried out using randomization.[7] Each node randomly decides to transmit every slot t (transmitting a "null" packet if it currently does nothave a packet to send). The actual transmission rates, and the corresponding actual packets to send,are determined by a 2-step handshake:On the first step, the randomly selected transmitter nodes send a pilot signal with signal strength proportionalto that of an actual transmission. On the second step,all potential receiver nodes measure the resulting interference and send that information back to thetransmitters. The SINR levels for all outgoing links (n,b) are then known to all nodes n,and each node n can decideits
\munb(t)
(c) | |
(\mu | |
nb |
(t))
Alternative distributed implementations can roughly be grouped into two classes:The first class of algorithms consider constant multiplicative factor approximations to the max-weight problem,and yield constant-factor throughput results. The second class of algorithms consider additive approximations to the max-weightproblem, based on updating solutions to the max-weight problem over time. Algorithms in this second class seem to require static channelconditions and longer (often non-polynomial) convergence times, although they can provably achieve maximum throughputunder appropriate assumptions.[15] [3] [11] Additive approximations are often usefulfor proving optimality of backpressure when implemented with out-of-date queue backlog information (see Exercise 4.10 of the Neely text).[11]
This section shows how the backpressure algorithm arises as a natural consequence ofgreedily minimizing a bound on the change in the sum of squares of queue backlogs from one slot to the next.[7] [2]
Consider a multi-hop network with N nodes, as described in the above section.Every slot t, the network controller observes the topology state S(t) and choosestransmission rates
(\muab(t))
(c) | |
(\mu | |
ab |
(t))
(Eq.3) (\muab(t))\in\GammaS(t)
(Eq.4) 0\leq
(c) | |
\mu | |
ab |
(t) \foralla,b,c,\forallt
(Eq.5)
(c) | |
\sum | |
ab |
(t)\leq\muab(t) \forall(a,b),\forallt
Once these routing variables are determined, transmissions are made (using idle fill if necessary), and the resulting queuebacklogs satisfy the following:
(Eq.6)
(c) | |
Q | |
n |
(t+1)\leq
(c) | |
max\left[Q | |
n |
(t)-
(c) | |
\sum | |
nb |
(t),0\right]+
(c) | |
\sum | |
an |
(t)+
(c) | |
A | |
n |
(t)
where
(c) | |
A | |
n |
(t)
(c) | |
\mu | |
nb |
(t)
(c) | |
\mu | |
nb |
(t)
(c) | |
\sum | |
an |
(t)
(c) | |
\mu | |
ab |
(t)
It is assumed that
(c) | |
Q | |
c |
(t)=0
c\in\{1,\ldots,N\}
Define
\boldsymbol{Q}(t)=
(c) | |
(Q | |
n |
(t))
L(t)=
1 | |
2 |
N | |
\sum | |
c=1 |
(c) | |
Q | |
n |
(t)2
This is a sum of the squares of queue backlogs (multiplied by 1/2 only for convenience in later analysis). The above sum is the same as summing over all n, c such that
n ≠ c
(c) | |
Q | |
c |
(t)=0
c\in\{1,\ldots,N\}
The conditional Lyapunov drift
\Delta(t)
\Delta(t)=E\left[L(t+1)-L(t)\mid\boldsymbol{Q}(t)\right]
Note that the following inequality holds for all
q\geq0
a\geq0
b\geq0
(max[q-b,0]+a)2\leqq2+b2+a2+2q(a-b)
By squaring the queue update equation (Eq. (6)) and using the above inequality, it is not difficultto show that for all slots t and under any algorithm for choosing transmission and routing variables
(\muab(t))
(c) | |
(\mu | |
ab |
(t))
(Eq.7) \Delta(t)\leqB+
(c) | |
\sum | |
n |
(c) | |
(t)E\left[λ | |
n |
(t)+
(c) | |
\sum | |
an |
(t)-
(c) | |
\sum | |
nb |
(t)|\boldsymbol{Q}(t)\right]
where B is a finite constant that depends on the second moments of arrivals and the maximum possible second moments of transmission rates.
The backpressure algorithm is designed to observe
\boldsymbol{Q}(t)
(\muab(t))
(c) | |
(\mu | |
ab |
(t))
(c) | |
λ | |
n |
(c) | |
E\left[\sum | |
n |
(t)\left[
(c) | |
\sum | |
nb |
(t)-
(c) | |
\sum | |
an |
(t)\right]|\boldsymbol{Q}(t)\right]
where the finite sums have been pushed through the expectations to illuminate the maximizing decision.By the principle of opportunistically maximizing an expectation, the above expectation is maximized bymaximizing the function inside of it (given the observed
\boldsymbol{Q}(t)
S(t)
(\muab(t))
(c) | |
(\mu | |
ab |
(t))
(c) | |
\sum | |
n |
(t)\left[
(c) | |
\sum | |
nb |
(t)-
(c) | |
\sum | |
an |
(t)\right]
It is not immediately obvious what decisions maximize the above. This can be illuminated by switching the sums.Indeed, the above expression is the same as below:
(c) | |
\sum | |
ab |
(c) | |
(t)[Q | |
a |
(t)-
(c) | |
Q | |
b |
(t)]
The weight
(c) | |
Q | |
a |
(t)-
(c) | |
Q | |
b |
(t)
(c) | |
(\mu | |
ab |
(t))
Clearly one should choose
(c) | |
\mu | |
ab |
(t)=0
(c) | |
Q | |
a |
(t)-
(c) | |
Q | |
b |
(t)<0
\muab(t)
(a,b)
(c) | |
\mu | |
ab |
(t)
opt | |
c | |
ab |
(t)\in\{1,\ldots,N\}
(c) | |
\mu | |
ab |
(t)=0
c\in\{1,\ldots,N\}
\muab(t)
opt | |
c | |
ab |
(t)
(c) | |
\sum | |
ab |
(c) | |
(t)[Q | |
a |
(t)-
(c) | |
Q | |
b |
(t)]=\muab(t)Wab(t)
where
Wab(t)
Wab(t)=max[
| ||||||||||
Q | ||||||||||
a |
(t)-
| ||||||||||
Q | ||||||||||
b |
(t),0]
It remains only to choose
(\muab(t))\in\GammaS(t)
Maximize:
N\mu | |
\sum | |
ab |
(t)Wab(t)
Subjectto:(\muab(t))\in\GammaS(t)
The above problem is identical to the max-weight problem in Eqs. (1)-(2).The backpressure algorithm uses the max-weight decisions for
(\muab(t))
(c) | |
(\mu | |
ab |
(t))
A remarkable property of the backpressure algorithm is that it acts greedily every slot t based only on the observed topology state S(t) and queue backlogs
\boldsymbol{Q}(t)
(c) | |
(λ | |
n |
)
\piS=Pr[S(t)=S]
This section proves throughput optimality of the backpressure algorithm.[2] [11] For simplicity, the scenario where events are independent and identicallydistributed (i.i.d.) over slots is considered, although the same algorithm can be shown to work in non-i.i.d. scenarios (seebelow under Non-i.i.d. operation and universal scheduling).
Let
(c) | |
(A | |
n |
(t))
(c) | |
λ | |
n |
=
(c) | |
E\left[A | |
n |
(t)\right]
It is assumed that
(c) | |
λ | |
c |
=0
c\in\{1,\ldots,N\}
(c) | |
(λ | |
n |
)
N x N
Assume the topology state S(t) is i.i.d. over slots with probabilities
\piS=Pr[S(t)=S]
\piS
(\muab(t))
(c) | |
(\mu | |
ab |
(t))
Λ
(c) | |
(λ | |
n |
)
(c) | |
(λ | |
n |
)
Λ
*(t)) | |
(\mu | |
ab |
*(c) | |
(\mu | |
ab |
(t))
n ≠ c
(Eq.8)
(c) | |
E\left[λ | |
n |
+
*(c) | |
\sum | |
an |
(t)-
*(c) | |
\sum | |
nb |
(t)\right]\leq0
Such a stationary and randomized algorithm that bases decisions only on S(t) is called an S-only algorithm. It is often useful to assume that
(c) | |
(λ | |
n |
)
Λ
\epsilon>0
(c) | |
(λ | |
n |
+\epsilon
(c) | |
1 | |
n |
)\inΛ
(c) | |
1 | |
n |
n ≠ c
n ≠ c
(Eq.9)
(c) | |
E\left[λ | |
n |
+
*(c) | |
\sum | |
an |
(t)-
*(c) | |
\sum | |
nb |
(t)\right]\leq-\epsilon
As a technical requirement, it is assumed that the second moments of transmission rates
\muab(t)
\mumax
Because the backpressure algorithm observes
\boldsymbol{Q}(t)
(\muab(t))
(c) | |
(\mu | |
ab |
(t))
(Eq.10) \Delta(t)\leqB+
(c) | |
\sum | |
n |
(c) | |
(t)E\left[λ | |
n |
(t)+
*(c) | |
\sum | |
an |
(t)-
*(c) | |
\sum | |
nb |
(t)|\boldsymbol{Q}(t)\right]
where
*(t)) | |
(\mu | |
ab |
*(c) | |
(\mu | |
ab |
(t))
Now assume
(c) | |
(λ | |
n |
)\inΛ
\boldsymbol{Q}(t)
\Delta(t)\leqB
Thus, the drift of a quadratic Lyapunov function is less than or equal to a constant B for all slots t. This fact, together with the assumption that queue arrivals have bounded second moments, imply the following for all network queues:[16]
\limt → infty
| ||||||||||
t |
=0withprobability1
For a stronger understanding of average queue size, one can assume the arrival rates
(c) | |
(λ | |
n |
)
Λ
\epsilon>0
\Delta(t)\leqB-
(c) | |
\epsilon\sum | |
n |
(t)
from which one immediately obtains (see[2] [11]):
\limsupt → infty
1 | |
t |
t-1 | |
\sum | |
\tau=0 |
N | |
\sum | |
n=1 |
N | |
\sum | |
c=1 |
E\left[
(c) | |
Q | |
n |
(\tau)\right]\leq
B | |
\epsilon |
This average queue size bound increases as the distance
\epsilon
Λ
λ
\mu
1/\epsilon
\epsilon=\mu-λ
The above analysis assumes i.i.d. properties for simplicity. However, the same backpressure algorithm can be shown to operate robustly in non-i.i.d. situations. When arrival processes and topology states are ergodic but not necessarily i.i.d., backpressure still stabilizes the system whenever
(c) | |
(λ | |
n |
)\inΛ
Backpressure has been shown to work in conjunction with flow control via a drift-plus-penalty technique.[8] [9] [2] This technique greedily maximizes a sum of drift and a weighted penalty expression. The penalty is weighted by a parameter V that determines a performance tradeoff.This technique ensures throughput utility is within O(1/V) of optimality while average delay is O(V). Thus, utility can be pushed arbitrarily close to optimality, with a corresponding tradeoff in average delay. Similar properties can be shown for average power minimization[18] and for optimization of more general network attributes.[11]
Alternative algorithms for stabilizing queues while maximizing a network utility have been developedusing fluid model analysis,[10] joint fluid analysis and Lagrange multiplier analysis,[19] convex optimization,[20] and stochastic gradients.[21] These approaches do not provide the O(1/V), O(V) utility-delay results.