Wireless Networking Lab 112: Back-Pressure Scheduling.


This lab has only been tested on NS2 version 2.29.3 using the Miracle framework installed. You can find the Miracle framework here. This lab is a work in progress. The code and scripts are not available yet.


In this lab, we will take a look at a scheduling algorithm which takes into account the queue sizes of nodes. The basic idea of this algorithm is to give priority to the node with the largest backpressure. By giving priority to the node with the largest backpressure, we are attempting to equalize the queue-lengths of neighboring nodes as fast as possible [3].

Assume there is a flow F that follows the route A-B-C. Let q(A,C)[t] be the queue length for flow F at node A at time t. The differential backlog for destination C over link A-B is then defined as w(A,B),C[t] = q(A,C)[t] - q(B,C)[t]. Now, for example, if w(A,B),C[t] = 5 and w(B,C),C[t] = 10, we would want to give priority to link B-C, thus letting B transmit to C. By doing so, we are trying to normalize neighboring queue lengths.


Now, we will discuss the algorithm used, which is a distributed implementation of the algorithm discussed in reference 3. First, the nodes send broadcast packets out which contain their queue information. (In this lab, we are only looking at the case where each node has one queue for one flow.) On reception of a neighbor's broadcast packet, the node can then calculate the differential backlog. In the next broadcast packet, the packet includes the nodes own differential backlog information. Now, the nodes have their neighbor's backlog information and can use that prioritize access to the channel.

The prioritization is a simple adaptation of 802.11. We will adjust the contention window values to correspond to priority values. A given node, say node NA, will have its own backlog information as well as its neighbors. Let Bmin and Bmax be the minimum and maximum backlog values at a given node - these will either be backlog values from a neighbor or may be from its own flow. Let B be the maximum backlog for source NA. Also let CWUmin and CWUmax be the user-defined min and max for the backoff value. CWmin/CWmax are the 802.11 contention window min and max values. Now, the node NA's backoff value is chosen according to the following equation: CWmin = CWmax = (CWUmax - CWUmin)(1 - (B - Bmin)/(Bmax - Bmin)) + CWUmin

So, what does this do? It is easiest to understand by looking at the extreme cases. If B = Bmin, then this equation will map CWmin = CWmax = CWUmax. Also, if B = Bmax, then this equation will map CWmin = CWmax = CWUmin. Remember, if a node has a low backoff value, it can be looked upon as having a "higher priority" than other nodes with large backoff values. So, we are thus mapping the backlog (B) to a priority value (CWmin/CWmax). Thus, nodes with large backlog values will have a higher priority than their neighbors.

NS2 Instructions

Turn In

Turn in a writeup with the plots and answers to the analysis questions. Expected plots are the (i) Queue length vs. time for flow-generating nodes for all cases (ii) Throughput vs. time for destination-nodes for all cases. Once again, completeness and neatness are stressed.


1. Is setting CWmin = CWmax a good way to choose the priority value? Please explain why yes or no?
2. Can you suggest a better way to choose the backoff value?
3. Why would one want to keep the queue lengths of neighboring nodes uniform?


1. Know ns2
2. Schiller, Joschen. "Mobile Communications"
3. Eryilmaz and Srikant, "Joint Congestion Control, Routing, and MAC for Stability and Fairness in Wireless Networks"