Achieving End-to-End fairness in wireless networks with randomized TDMA schedules
Slides
:
Abstract
The MAC layer plays a very important role in the performance and
fairness of multi-hop wireless networks. MAC protocols can be classified
into either contention-based or timeslot-based approaches. Both
simulations and deployed test-beds show that contention-based MACs can
lead to poor-fairness in a multi-hop network due to hidden terminal
problems and other asymmetric interactions. Time-division mutliplexed
(TDMA) approaches can potentially solve such issues because they
explicity disallow competing stations from transmitting at the same
time. However, TDMA schemes suffer from two important drawbacks which
have slowed their adoption. Firstly, they require an explicit setup and
teardown phase for each flow in the system. This overhead can be very
significant for web-traffic like workloads with many TCP arrivals and
departures. Secondly, TDMA schedules have to be recomputed when link
quality changes. The allocation at each hop of a multi-hop flow must be
the same, and hence the change in the data rate of any intermediate link
will result in the entire schedule being recomputed. In this paper we
propose a simple distributed algorithm that addresses these two
drawbacks by using an increase-decrease algorithm to assign weights.
These weights have local singnificance only, and the algorithm uses
information only from directly competing queues to guarantee convergance
to a fair allocation. Almost all control messages are piggy-backed on
existing traffic to keep the overhead low. We evaulate our algorithm
though both simulations in ns2, and an implementation on top of the
Overlay MAC Layer (OML) in a small 802.11-based testbed.