Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

A Distributed Max-Min Fairness Rate Allocation Algorithm For Unreliable Communication Networks

Jingyi Shao and Jean Walrand

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-73
May 19, 2006

http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-73.pdf

In recent years, wireless ad hoc networks have generated great interest in the research community, driven partly by the more advanced technology that can produce wireless communication nodes cheaply and by new applications in military as well as environmental sensor networks. An ad hoc network is one without a pre-established infrastructure, as opposed to a cellular network, and that configures itself automatically as the nodes join or leave the network via a wireless medium. In addition to the challenges faced by wireless communication at the physical layer, there are new challenges at the higher layers. These challenges mostly arise because of the physical layer unreliability and interference of the wireless medium. While communication engineers design better modulation and coding schemes to make wireless links more reliable, the unreliability is a fundamental characteristic of wireless medium. Recently, new techniques such as opportunistic beam forming take advantage of this characteristic instead of trying to suppress it. In this project, we assume an unreliable network, such as a wireless ad hoc network, and study the transport layer of such a network. Specifically, we argue that for a unreliable network, a hop-by-hop transport protocol is more desirable than an end-to-end transport protocol such as TCP (Transmission Control Protocol) used by Internet. We then propose a hop-by-hop rate allocation algorithm. We prove that the algorithm achieves max-min fairness when the network is reliable, and use simulation to show that the algorithm also works well for unreliable networks.

Advisor: Jean Walrand


BibTeX citation:

@mastersthesis{Shao:EECS-2006-73,
    Author = {Shao, Jingyi and Walrand, Jean},
    Title = {A Distributed Max-Min Fairness Rate Allocation Algorithm For Unreliable Communication Networks},
    School = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {May},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-73.html},
    Number = {UCB/EECS-2006-73},
    Abstract = {In recent years, wireless ad hoc networks have generated great
interest in the research community, driven partly by the more
advanced technology that can produce wireless communication nodes
cheaply and by new applications in military as well as environmental
sensor networks.  An ad hoc network is one without a pre-established
infrastructure, as opposed to a cellular network, and that
configures itself automatically as the nodes join or leave the
network via a wireless medium.

In addition to the challenges faced by wireless communication at the
physical layer, there are new challenges at the higher layers. These
challenges mostly arise because of the physical layer unreliability
and interference of the wireless medium.  While communication
engineers design better modulation and coding schemes to make
wireless links more reliable, the unreliability is a fundamental
characteristic of wireless medium. Recently, new techniques such as
opportunistic beam forming take advantage of this characteristic
instead of trying to suppress it.

In this project, we assume an unreliable network, such as a wireless
ad hoc network, and study the transport layer of such a network.
Specifically, we argue that for a unreliable network, a hop-by-hop
transport protocol is more desirable than an end-to-end transport
protocol such as TCP (Transmission Control Protocol) used by
Internet. We then propose a hop-by-hop rate allocation algorithm. We
prove that the algorithm achieves max-min fairness when the network
is reliable, and use simulation to show that the algorithm also
works well for unreliable networks.}
}

EndNote citation:

%0 Thesis
%A Shao, Jingyi
%A Walrand, Jean
%T A Distributed Max-Min Fairness Rate Allocation Algorithm For Unreliable Communication Networks
%I EECS Department, University of California, Berkeley
%D 2006
%8 May 19
%@ UCB/EECS-2006-73
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-73.html
%F Shao:EECS-2006-73