page_title: Backpressure routing
section_title: Choosing the optimal commodity
hierarchical_section_title: Backpressure routing / How it works / The backpressure control decisions / Choosing the optimal commodity
caption_attribution_description: English: A closeup of 2 nodes in a multi-hop network that uses backpressure routing, showing the internal queues. The optimal commodity to send over the link is illustrated.
context_page_description: 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.
context_section_description: 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.
caption: 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.
exif: {"Image Orientation": "Horizontal (normal)", "Image XResolution": "72", "Image YResolution": "72", "Image ResolutionUnit": "Pixels/Inch", "Image ExifOffset": "90", "EXIF ExifImageWidth": "525", "EXIF ExifImageLength": "207"}