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.

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. 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