Backpressure routing

Backpressure routing considers the situation where each job can visit multiple service nodes in the network.

[2][3] Backpressure principles can also be applied to other areas, such as to the study of product assembly systems and processing networks.

[4] This article focuses on communication networks, where packets from multiple data streams arrive and must be delivered to appropriate destinations.

Every time slot it seeks to route data in directions that maximize the differential backlog between neighboring nodes.

An algorithm related to backpressure, designed for computing multi-commodity network flows, was developed in Awerbuch and Leighton.

[8] The backpressure algorithm was later extended by Neely, Modiano, and Rohrs to treat scheduling for mobile networks.

[9] Backpressure is mathematically analyzed via the theory of Lyapunov drift, and can be used jointly with flow control mechanisms to provide network utility maximization.

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.

Specifically, the network may have time-varying channels and node mobility, and this can affect its transmission capabilities every slot.

[9] 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.

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.

that maximizes the following differential backlog quantity: Any ties in choosing the optimal commodity are broken arbitrarily.

The example assumes each queue currently has only 3 commodities: red, green, and blue, and these are measured in integer units of packets.

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

This packet may take a loopy walk through the network and never arrive at its destination because no pressure gradients build up.

Another way to improve delay, without affecting the capacity region, is to use an enhanced version that biases link weights towards desirable directions.

It has been observed that Last-in-First-Out (LIFO) service can dramatically improve delay for the vast majority of packets, without affecting throughput.

can be computed in a simple distributed manner, where each node only requires knowledge of queue backlog differentials between itself and its neighbors.

In the special case when channels are orthogonal, the algorithm has a natural distributed implementation and reduces to separate decisions at each node.

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.

On the second step, all potential receiver nodes measure the resulting interference and send that information back to the transmitters.

Hence, the resulting throughput of this distributed implementation is optimal over the class of all routing and scheduling algorithms that use such randomized transmissions.

Algorithms in this second class seem to require static channel conditions and longer (often non-polynomial) convergence times, although they can provably achieve maximum throughput under appropriate assumptions.

[15][4][13] Additive approximations are often useful for proving optimality of backpressure when implemented with out-of-date queue backlog information (see Exercise 4.10 of the Neely text).

[13] This section shows how the backpressure algorithm arises as a natural consequence of greedily minimizing a bound on the change in the sum of squares of queue backlogs from one slot to the next.

subject to the following constraints: Once these routing variables are determined, transmissions are made (using idle fill if necessary), and the resulting queue backlogs satisfy the following: where

may be more than the amount of commodity c data that is actually transmitted on link (a,b) on slot t. This is because there may not be enough backlog in node n. For this same reason, Eq.

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

[9] More generally, using a universal scheduling approach, it has been shown to offer stability and optimality properties for arbitrary (possibly non-ergodic) sample paths.

Similar properties can be shown for average power minimization[18] and for optimization of more general network attributes.