Backpressure Routing背压路由算法

Backpressure Routing From Wikipedia, the free encyclopedia Jump to: navigation, search For the term "back pressure" in describing fluid flow in piping and air vent systems, see Back pressure. This article describes backpressure routing (also written "back-pressure routing" or "back pressure routing") for queueing networks. It shows how the algorithm is derived and how its optimality is established using concepts of Lyapunov drift. Contents  [hide]  · 1 Introduction to Backpressure Routing · 1.1 Origins · 2 How it Works · 2.1 The Multi-Hop Queueing Network Model · 2.2 The Backpressure Control Decisions · 2.2.1 Choosing the optimal commodity · 2.2.2 Choosing the (μab(t)) matrix · 2.2.3 Finalizing the routing variables · 2.3 Improving Delay · 2.4 Distributed Backpressure · 3 Mathematical Construction via Lyapunov Drift · 3.1 Control Decision Constraints and the Queue Update Equation · 3.2 Lyapunov Drift · 3.3 Minimizing the Drift Bound by Switching the Sums · 4 Performance Analysis · 4.1 Dynamic Arrivals · 4.2 Network Capacity Region · 4.3 Comparing to S-Only Algorithms · 5 Extensions of the above formulation · 5.1 Non-I.I.D. Operation and Universal Scheduling · 5.2 Backpressure with Utility Optimization and Penalty Minimization · 6 Related Links · 7 References · 8 Primary Sources Introduction to Backpressure Routing Backpressure routing refers to 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 of product assembly systems and processing networks [3] . 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, and every 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 back- pressure 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(算法特点): (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 [4] [5] [6] . Origins 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. They did not call their algorithm "backpressure," as, at the time of the Tassiulas-Ephremides work, the term "backpressure" had a different meaning in the area of data networks (it referred to a class of congestion-based flow control techniques[7] [8]). The Tassiulas-Ephremides algorithm was first called "backpressure" in [9] and [10] where the algorithm was extended to treat networks with mobility, including ad-hoc mobile networks. An algorithm related to backpressure, designed for computing multi-commodity network flows, was developed in [11] . Backpressure is mathematically analyzed via the theory of Lyapunov drift, and has been unified with utility optimization techniques in [9] [12] [13] [2] [14] (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 Fig. 1: A 6-node multihop network. Arrows between nodes illustrate current neighbors. 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 represent 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 μab(t) 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 (μab(t)) 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 ΓS(t) 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 (μab(t)) within the set ΓS(t). The choice of which (μab(t)) matrix to select on each slot t is described in the next subsection. This network model was developed in [10], where the set of transmission rate options was described as a general function of S(t) and the current transmission power allocation. It was refined in [2] using transmission rates as general functions of S(t) and a control input I(t), which could represent power allocation, server allocation, sub-band selection, coding type, and so on. The model fits a variety of networks, including ad-hoc mobile networks, networks with orthogonal channels, as well as networks with inter-channel interference. It assumes the supportable transmission rates are known and there are no transmission errors. Backpressure methods with probabilistic channel errors are considered in [15] . 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 (μab(t)) matrix in ΓS(t) to use. · Finally, it determines the amount of commodity it will transmit over link (a,b) (being at most μab(t), 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 μab(t) on the current slot. Thus, neighbors are determined by the set ΓS(t). In the general case, a node can have all N-1 other nodes as neighbors. However, it is common to use sets ΓS(t) 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 determine the set of outgoing links it can possibly 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. Fig. 2: A closeup of nodes 1 and 2. The optimal commodity to send over link (1,2) is the green commodity. The optimal commodity to send in the other direction (over link (2,1)) is the blue commodity. 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 Wab(t): The weight Wab(t) 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 Wab(t) given by: While the set ΓS(t) might contain an uncountably infinite number of possible transmission rate matrices, assume for simplicity that the current topology state admits only 4 possible choices: Fig. 3: An illustration of the 4 possible transmission rate selections under the current topology state S(t). Option (a) activates the single link (1,5) with a transmission rate of μ15 = 2. All other options use 2 links, with transmission rates of 1 on each of the activated links. These four possibilities are illustrated in Fig. 3. The options in Fig. 3 are represented in matrix form by: 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: · Choice (a): ∑ Wab(t)μab(t) = 12 ab . · Choice (b): ∑ Wab(t)μab(t) = 1 ab . · Choice (c): ∑ Wab(t)μab(t) = 1 ab . · Choice (d): ∑ Wab(t)μab(t) = 12 ab .Because there is a tie for the maximum weight of 12, the network controller can break the tie arbitrarily by choosing either option or option . Finalizing the routing variables Suppose now that the optimal commodities have been determined for each link, and the transmission rates (μab(t)) have also been determined. If the differential backlog for the optimal commodity on a given link (a,b) is negative, then no data is transferred over this link on the current slot. Else, the network offers to send μab(t) units of commodity data over this link. This is done by defining routing variables for each link (a,b) and each commodity c, where: The value of represents the transmission rate offered to commodity c data over link (a,b) on slot t. However, it may be the case a node does not have enough of a certain commodity to support transmission at the offered rates on all of its outgoing links. This arises on slot t for node n and commodity c if: In this case, all of the data is sent, and null data is used to fill the unused portions of the offered rates, allocating the actual data and null data arbitrarily over the corresponding outgoing links (according to the offered rates). This is called a queue underflow situation. Such underflows do not affect the throughput or stability properties of the network. Intuitively, this is because underflows only arise when the transmitting node has a low amount of backlog, which means the node is not in danger of instability. Improving Delay It is important to note that the backpressure algorithm does not use any pre-specified paths. Paths are learned dynamically, and may be different for different packets. Delay can be very large, particularly when the system is lightly loaded so that there is not enough pressure to push data towards the destination. As an example, suppose one packet enters the network, and nothing else ever enters. This packet may take a loopy walk through the network and never arrive at its destination because no pressure gradients build up. This does not contradict the throughput optimality or stability properties 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 that can be used. This can restrict the capacity region, but might improve in-order delivery and delay. Another way to improve delay, without affecting the capacity region, is to use the enhanced version of backpressure developed in [10], which adds a "differential progress-to-destination" term to the backpressure weight Wab(t). Simulations of this are given in [2] HYPERLINK "http://en.wikipedia.org/wiki/Backpressure_Routing" \l "cite_note-neely-divbar-journal-14#cite_note-neely-divbar-journal-14" [15]. Note that backpressure does not require First-in-First-Out (FIFO) service at the queues. It has been observed in implementations and analysis in [6] [16] that using Last-in-First-Out (LIFO) service can dramatically improve delay for the vast majority of packets, without affecting throughput. Distributed Backpressure Note that once the transmission rates (μab(t)) have been selected, the routing decision variables can be computed in a simple distributed manner, where each node only requires knowledge of queue backlog differentials between itself and its neighbors. However, the max-weight problem in Eqs. (1)-(2) can be very difficult to solve in networks with inter-channel interference, even if centralized computation is allowed. A distributed approach to backpressure for ad-hoc mobile networks is given in [10], using a signal-to-interference ratio model. There, each node randomly decides to transmit every slot t (transmitting a "null" packet if it currently does not have 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 proportional to that of an actual transmission. On the second step, all potential receiver nodes measure the resulting interference and send that information back to the transmitters. The signal-to-interference levels for all outgoing links (n,b) are then known to all nodes n, and each node n can decide its μnb(t) and variables based on this information. The resulting throughput is not necessarily optimal because of the random transmission decisions. However, the random transmission process can be viewed as a part of the channel state process (provided that null packets are sent in cases of underflow, so that the channel state process does not depend on past decisions). Hence, the resulting throughput of this distributed implementation is optimal over the class of all routing and scheduling algorithms that use such randomized transmissions. 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-weight problem, based on updating solutions to the max-weight problem over time. 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. See [3] and Chapter 6 of [14], and references therein, for more details on this. Additive approximations are often useful for proving optimality of backpressure when implemented with out-of-date queue backlog information, see Exercise 4.10 of [14]. Mathematical Construction via Lyapunov Drift 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. Results in this section are based largely on work in [2]. Control Decision Constraints and the Queue Update Equation 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 chooses transmission rates (μab(t)) and routing variables 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 is the random amount of new commodity c data that exogenously arrives to node n on slot t, and is the transmission rate allocated to commodity c traffic on link (a,b) on slot t. Note that may be more than the amount of commodity c data that is actually transmitted on link (a,b) on slot t (otherwise, there would be no need for the operation in Eq. (6)). This is because there may not be enough backlog in node a. For this same reason, Eq. (6) is an inequality, rather than an equality, because may be more than the actual endogenous arrivals of commodity c to node n on slot t. An important feature of Eq. (6) is that it holds even if the decision variables are chosen independently of queue backlogs. It is assumed that for all slots t and all , as no queue stores data destined for itself. Lyapunov Drift Define as the matrix of current queue backlogs. Define the following non-negative function, called a Lyapunov function: This is just 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 , because for all and all slots t. The Lyapunov drift Δ(t) is defined: Note that the following inequality holds for all , , : By squaring the queue update equation (Eq. (