Wireless Networking Lab 112: Back-Pressure Scheduling.

NOTES

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.

Introduction

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.

Algorithm

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

• 1. Get the tcl file backpressure2flow.tcl XXhereXX.
• 2. The tcl file accepts inputs as follows:

  	backpressure2flow.tcl -cwumax -cwumin -flow1rate -flow2rate

  The restrictions on the inputs above are: cwumax > cwumin > 0; flow1rate, flow2rate > 0

• 3. Please run the following cases: (cwumin,cwumax) = (32,64), (32,128), (32,256), (32,512), (32,1024) and (flow1rate,flow2rate) = (1,1), (1,1.5), (1,2), (1,2.5), (1,3)
• 4. Get the results. We are interested in the queue length and throughput vs time. The following grep commands will obtain the needed stats from the output trace file.

  	XXX

• 5. Plot the results.

Turn In

Analysis

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?

References

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"