DiffQ: Hop by hop congestion control protocol for mesh networks

Introduction

Congestion control in wireless multi-hop networks is challenging because of two reasons. First, broadcast is an inherent feature of wireless networks and motivates many creative protocols including opportunistic routing and network coding. These protocols enable the use of many diverse, yet dynamically changing routing paths. Congestion control for these protocols using traditional end-to-end protocols such as TCP may result in too conservative rate control. Second, the wireless medium is shared among neighboring nodes; thus bandwidth must be allocated fairly among neighboring flows that do not necessarily share the same link. There have been no practical solutions for congestion control for these networks. Inspired by existing theoretical solutions of cross-layer optimization, we develop a protocol, called DiffQ, for congestion control in wireless multi-hop networks. DiffQ can support congestion control for network flows that use either single-path or opportunistic multi-path routing. The protocol is currently implemented in Linux 2.6 series and tested in a network of 46 IEEE 802.11 wireless nodes. It is observed that DiffQ greatly improves the efficiency and fairness of existing transport protocols that use application-level multi-path routing and single-path routing.

Research Highlights

* Congestion Control for Multi-hop Wireless Networks (putting differential backpressure into practice).

Checkout out our Youtube Videos for more information :

Starvation in Wireless Multihop Networks An Analysis

This experiment tries to find out the dominant cause for starvation in the flow in the middle problem
using TFRC.

A TFRC flow is started from nodes sn2e19 to sn2e10. Two more flows are introduced later. As the
traffic starts from these flows, sn2e19 - sn2e10 degrades to a throughput of 0.

The cause for the starvation of this flow is queue overflow as the intermediate nodes that are forwarding
packets of sn2e19 - sn2e10 are now unable to flush packets fast enough. We obtain the proportion of
packet drops due to hidden terminals and queue overflows. It can be seen that queue overflow is the
dominant cause for packet loss and hence starvation.

Unfair Contention in the medium results in a queue buildup and this leads to the eventual starvation of
the flow as the congested node is never able to flush packets fast enough.

The video shows the testbed with 3 flows. The long red line in the middle is the flow sn2e19 - sn2e10.
The graph on bottom left shows the instantaneous throughput of the flows. It can be seen that as the
new flows are introduced, the throughput of sn2e19 - sn2e10 drops to zero.

The graph on the right shows the statistics about hidden terminal errors (green bars) and queue overflows
(red bars). It can be seen that queue overflow error spikes indicating unfair medium sharing at the intermediate nodes.

Starvation in Wireless Multihop Networks A Soluion
We repeat the experiment with a flow in the middle scenario but this time using DiffQ TCP. DiffQ TCP is the
new congestion control algorithm that we have developed.

DiffQ is a generic congestion control framework which is based on differential backlog based backpressure.
Differential Backlog based backpressure was proposed in the context of utility maximization by Tassiulas
and Ephremides. DiffQ TCP is the direct application of these concepts in practice.

DiffQ TCP relies on source rate control, flow scheduling and MAC prioritisation. Source rate control is done
using backpressure. The flow scheduling at each node selects the flow with the maximum queue differential
and schedules it for transmission. MAC priority is assigned based on the differential backlog.

In this scenario, the flow sn2e19 - sn2e10 gets lesser access to the medium as before. This results in a
queue build up at intermediate nodes. While TFRC suffered starvation because of queue build up, DiffQ TCP
flushes the queues quickly due to flow scheduling and MAC prioritisation. MAC prioitisation ensures that the
flow which is suffering unfairness gets preferential access to the medium.

We do not observe queue overflows with DiffQ TCP which points to the effectiveness of the differential
backlog scheme in practice.

DiffQ Design

DiffQ is a hop-by-hop congestion control algorithm. Intermediate nodes maintain per-destination queues and disseminate these queue sizes to neighbors via piggybacking. The DiffQ scheduler schedules flows with the maximum "queue differential". The queue differential () at a node i for destination d and next-hop node j is calculated w.r.t queue sizes for destination d at i and j, i.e. and as follows:

Queue differential is translated proportionally to a packet priority -- higher the queue differential, higher the priority. The 802.11e MAC is then responsible for honoring this priority among neighbor nodes by means of differential backoffs. The intuitive idea of scheduling based on queue differential is as follows: a higher queue differential indicates that the flow is backlogged. By scheduling such flows and assigning MAC priority we allow local (hop-by-hop) congestion alleviation. If this does not work, then back-pressure takes over and ultimately source reduces its rate.

Above figure presents the concept of back-pressure. High queue differential at node C is alleviated by scheduling and higher MAC priority. If congestion persists, A's queue will build-up, since C grabs most of the channel, causing its own queue differential to increase. Again, if A is not able to flush its own queue, ultimately the source queue size increases, and finally the source controls the rate by only looking at its own local queue size.

Architecture and Implementation

DiffQ Architecture

DiffQ Integration with TCP

DiffQ sits above the IP layer and provides congestion control as a "service" to transport layer applications like TCP, UDP, TFRC, MORE. We have implemented DiffQ as a Linux kernel module (version 2.6.16). The MAC is 802.11 with Madwifi driver for the Atheros chipset. The DiffQ implementation has been tested over the WiSeNet testbed consisting of 60 Soekris nodes. Please refer to: Details of DiffQ implementation in Linux for a more detailed look at the DiffQ kernel implementation. DiffQ also takes care of converting outbound and incoming vanilla-TCP connections to a "DiffQ friendly" version of TCP using a TCP proxy, as shown above. For more details please refer to: Details of DiffQ TCP Proxy implementation.

Experimental Results - DiffQ + Opportunistic Routing (MORE)

Below figures show the performance of MORE and MORE+DiffQ with varying number of concurrent flows on our testbed. Figure (A) shows that MORE alone suffers significant starvation with almost 50% flows getting 0 throughput with 32 concurrent flows. Figure (B) shows the improvement in performance with the addition of DiffQ congestion control. Figure (C) shows that the improvement is not limited to fairness; the average throughput improves by 3x with DiffQ.

(A) MORE performance without congestion control	(B) MORE+DiffQ performance	(C) Average Throughput of MORE and MORE+DiffQ

Experimental Results - DiffQ + Single Path Routing (TCP/UDP/TFRC ...)

For video demos of DiffQ over single path protocols, please refer to: DiffQ Single-Path Demos.

Publications

• A. Warrier, S. Janakiraman, S. Ha and I. Rhee, DiffQ: Differential Backlog Congestion Control for Multi-hop Wireless Networks, INFOCOM 2009. PDF
• A. Warrier, S. Ha, P. Wason and I. Rhee, DiffQ: Differential Backlog Congestion Control for Multi-hop Wireless Networks, NCSU Technical Report. PDF
• A. Warrier, S. Ha and I. Rhee, Starvation in Wireless End-to-end Congestion Controlled Networks: A Different Perspective, submitted PDF
• A. Warrier, S. Ha, P. Wason, I. Rhee and J. H. Kim, DiffQ: Differential Backlog Congestion Control for Multi-hop Wireless Networks, Demo, SECON 2008. PDF
• A. Warrier, S. Ha, and I. Rhee, TCP performance problems in wireless multi-hop networks, Demo, The Future of TCP: Train-wreck or Evolution? Stanford Clean Slate Program, 2008. http://yuba.stanford.edu/trainwreck/

Presentations (PPT)

• Cisco, San Francisco, Nerdlunch Talk (Dr. Injong Rhee).

Documentation

• Details of DiffQ implementation in Linux
• Details of DiffQ TCP Proxy implementation
• Details on DiffQ Scripts
• Details on DiffQ+MORE Scripts
• Details on DiffQ+MORE Implementation in Linux