EFLoW: End-to-end Fairness using Local Weights

Ananth Rao and Ion Stoica

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2007-107
August 23, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-107.pdf

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 paper, we 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 WFLoW 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.


BibTeX citation:

@techreport{Rao:EECS-2007-107,
    Author = {Rao, Ananth and Stoica, Ion},
    Title = {EFLoW: End-to-end Fairness using Local Weights},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2007},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-107.html},
    Number = {UCB/EECS-2007-107},
    Abstract = {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 paper, we 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 WFLoW 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.}
}

EndNote citation:

%0 Report
%A Rao, Ananth
%A Stoica, Ion
%T EFLoW: End-to-end Fairness using Local Weights
%I EECS Department, University of California, Berkeley
%D 2007
%8 August 23
%@ UCB/EECS-2007-107
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-107.html
%F Rao:EECS-2007-107