End-to-end Fairness using Local Weights (EFLoW)

 bar

Overview

Recent research indicates that multihop wireless networks can suffer from extreme imbalances in the throughput achieved by simultaneous competing flows. However, even with global knowledge of the topology and traffic patterns, computing the fair allocation is know to be an NP complete problem for most definitions of fairness. Previous work has either (a) focused on the MAC layer which only provides fairness guarantees within a single contention neighborhood or (b) used a centralized coordinator to compute the global allocation of throughput to flows. While the former approach does not address the problem in its entirety, the latter is very hard to implement under dynamic channel and traffic conditions. In this work, we try to bridge this gap by augmenting approach (a) with a simple distributed transport layer algorithm called EFLoW. EFLoW assumes that the MAC layer supports weighted fair allocation among nodes that directly compete with each other. We refer to the weights at this layer as the local weights since they have significance only within a single contention neighborhood.

EFLoW computes the local weights using an iterative increase-decrease algorithm which guarantees convergence to an end-to-end max-min fair allocation under certain assumptions. In each iteration, EFLoW only uses state obtained from within a given node’s contention region. We have implemented EFLoW in both a simulator and a real system on top of the Overlay MAC Layer (OML). Our results show that EFLoW can avoid starvation of flows and improve fairness by about 90% with only a 15% reduction in total network throughput when compared to standard 802.11.

bar

People

  1. Ananth Rajagopala Rao (ananthar <at> cs <dot> berkeley <dot> edu)
  2. Ion Stoica (istoica <at> cs <dot> berkeley <dot> edu)

bar

Publications

bullet Ananth Rao and Ion Stoica, EFLoW: End-to-end Fairness using Local Weights, Technical Report EECS-2007-107, University of California - Berkeley, August 2007.

 

bar

Links

 
bullet  The Click Modular Router (Documentation) - OML is implemented by adding a few new elements to Click.
bullet  The Madwifi Project - Provides linux drivers for network adapters based on the Atheros chipset.
bullet  MIT Roofnet - A testbed of 802.11-based nodes at the Massachusetts Institute of Technology.