15-12-2012, 04:14 PM
Wardrop Routing in Wireless Networks
1Wardrop Routing.pdf (Size: 6.25 MB / Downloads: 165)
Abstract
Routing protocols for multihop wireless networks have traditionally used shortest path routing to obtain paths to
destinations and do not consider traffic load or delay as an explicit factor in the choice of routes. We focus on static mesh networks and
formally establish that if the number of sources is not too large, then it is possible to construct a perfect flow-avoiding routing, which can
boost the throughput provided to each user over that of the shortest path routing by a factor of four when carrier sensing can be
disabled or a factor of 3.2 otherwise. So motivated, we address the issue of designing a multipath, load adaptive routing protocol that is
generally applicable even when there are more sources. We develop a protocol that adaptively equalizes the mean delay along all
utilized routes from a source to destination and does not utilize any routes that have greater mean delay. This is the property satisfied
by a system in Wardrop equilibrium. We also address the architectural challenges confronted in the software implementation of a
multipath, delay-feedback-based, probabilistic routing algorithm. Our routing protocol is 1) completely distributed, 2) automatically load
balances flows, 3) uses multiple paths whenever beneficial, 4) guarantees loop-free paths at every time instant even while the
algorithm is suntil converging, and 5) amenable to clean implementation. An ns-2 simulation study indicates that the protocol is able to
automatically route flows to “avoid” each other, consistently out-performing shortest path protocols in a variety of scenarios. The
protocol has been implemented in user space with a small amount of forwarding mechanism in a modified Linux 2.4.20 kernel. Finally,
we discuss a proof-of-concept measurement study of the implementation on a six node testbed.
INTRODUCTION
ROUTING research in wireless multihop networks has
traditionally focused on shortest path routing protocols.
A lot of effort has gone into designing protocols that route
packets efficiently in mobile networks with minimal overhead,
e.g., [1], [2], [3], [4], and [5].
This paper is addressed toward static or at best networks
with slow mobility, for example, mesh networks or ad hoc
networks in office environments where users do not move
around with their laptops. Our focus is on wireless
networks, e.g., mesh networks, where the focus is on
boosting the throughput-delay performance, and energy
limitations are not a constraining factor. Looking ahead to
the next generation of wireless routing protocols for such
quasi-static networks, users may want their routing to be
adaptive to the load on the network. For example, users
may want to improve their throughput-delay performance
by intelligently routing flows in a manner to avoid
interference from other paths as far as possible. Users
may also want to utilize multiple paths so that they obtain
more throughput. In addition, looking from a network
standpoint, one may want the routing algorithms implemented
at each node to combine together to balance load
across the network.
RELATED WORK
The problem of finding loop-free routes to destinations in
mobile environments has been well studied [1], [2], [3], [4],
[5], [10], [11]. Proactive protocols [1], [4], [10] maintain
routes to all destinations and incur a large routing
overhead. Reactive protocols, on the other hand, construct
routes on an on-demand basis [2], [3] using a route
discovery procedure.
Multipath extensions of existing on-demand protocols
can provide recovery from route failures. For example,
CHAMP [12], built on top of DSR, uses cooperative packet
caching and shortest multipath routing to reduce packet
loss due to frequent link breakdowns. AOMDV [13], built
on top of AODV, computes multiple link-disjoint paths to a
destination by using an advertised hop count. Nasipuri and
Das [14] propose an extension to DSR, where they provide
sources and intermediate nodes with alternate paths during
the route discovery phase. A technique to allow AODV to
install backup routes at the neighbor nodes of a primary
route is investigated in [15].
Multipath routing can also alleviate congestion in
wireless networks. The hotspot mitigation protocol (HMP)
[16] can be integrated with AODV and DSR and attempts to
disperse new flows from being routed through hot spots
and congestion-prone areas. The Dynamic Load Aware
Routing protocol (DLAR) [17] carries congestion information
forward in ROUTE REQUEST packets, allowing
destinations to choose the least congested path.
THE ROUTING ALGORITHM
The theoretical result in the previous section indicates that
traffic-aware routing can provide considerable benefits.
However, the scheme used to prove the result is centralized
and should only be taken as proof of existence. Instead, we
examine a more general adaptive approach. For every SD
pair, we will attempt to drive routes toward an equilibrium,
where the mean delay along all utilized paths is equalized,
and all unutilized paths have greater or equal potential
mean delay. In a communication network, such an equilibrium
has attractive properties vis-a-vis multipath routing:
1. When packets have to be resequenced at the receiver
and delivered in-order to the application, equalizing
the average delay along utilized paths reduces
receiver socket buffer space requirements and
receiver socket buffer resequencing delays.
2. Equalizing the average delay along utilized paths
mitigates TCP congestion misbehavior that results
from TCP’s adverse reaction to multiple paths and
reordered packets.
3. Route adaptation using delay feedback allows rerouting
of flows around traffic bottlenecks in wireless
environments. This allows flows to automatically
“avoid” each other and minimize interference.
Controlling Paths and Eliminating Loops
Our first objective is to control paths so that the algorithm
does not have to investigate all possible paths from source
to destination, which would render the convergence very
slow. The basic idea that we use is to modify the definition
of the neighborhood Nði; dÞ, the set of neighbors to which
node i is allowed to forward packets destined for node d.
Controlling Paths with M-STARA
Let Sði; dÞ denote the shortest path distance in hops from
node i to destination d. Set N0ði; dÞ :¼ fj 2 Nði; dÞ : Sðj; dÞ
Sði; dÞg.We call this algorithm, which only allows the nodes
in N0ði; dÞ to be used for forwarding packets at i destined
for d, M-STARA. (The reason for the name, denoting
Multiplicative-STARA, is that with one additional modification,
it can be used to strongly control path lengths. For
brevity, we omit discussion on this, referring the reader to
[28].) The advantage of M-STARA is that it can be easily
built on top of STARA by running a distance vector protocol
to produce distances to all destinations. One other important
property is that by merely suitably defining the
notion of “neighborhood,” we can prove convergence to a
suitably defined Wardrop equilibrium; see Theorem 2.
SIMULATION STUDY
In order to understand the protocol behavior, we have
carried out an extensive simulation analysis for wireless
environments using the ns-2 simulator with the Monarch
wireless extensions [23]. In all our simulations, we use the
two ray ground propagation mode, the IEEE 802.11 DCF
MAC, a radio model based on the Lucent WaveLAN
2 megabits per second (Mbps) radio with a radio range of
250 m. We have implemented the Wardrop routing
protocols in ns-2 using DSDV [10] as a base protocol to
obtain distance information. All of our simulations (except
in the section on topology impact) were carried out with
N2 nodes on the intersections of a N N grid. The
interface queue length is set to 50 packets, and the retry
parameters of the MAC are left at their default values
MAC ShortRetryLimit ¼ 7 and MAC LongRetryLimit ¼ 4.
We use CBR sources with a constant size of 210 bytes
running on top of UDP to stress the network. The
simulations are run for times between 100 and 3,000 seconds.
Performance Data
The topologies used are shown in Fig. 23. The throughput
performance of DSDV and Wardrop routing for the
topologies is summarized in Tables 4 and 5. Each data
point is an average over ten runs of nttcp, and in each run, a
UDP connection transfers 8 Mbytes of data from source s to
destination d. The performance results in this section should
be treated as a proof of concept; further large scale testing is
suntil needed.
Both protocols see an (expected) drop in throughput
performance as the number of hops along a path increases
(see Table 4) due to increased self-interference. Even if we
attribute all the difference in performance to our protocol’s
additional routing overhead, (in practice, heating effects
and in-building wireless interference also matter), the worst
case impact of overhead on performance is approximately
12.3 percent.
CONCLUSION
In this paper, we have formally established a few sources
regime where flow-avoiding routing provides a four-fold
improvement over the throughput of shortest path routing
when carrier sensing can be disabled and a 3.2 factor
improvement otherwise. Focusing on static wireless networks,
we have developed a multipath load adaptive
routing protocol that
1. is completely distributed,
2. does load balancing,
3. can produce loop-free paths, and
4. is elegantly implementable in the operating system
kernel.
We propose mechanisms to control the lengths of paths and
provide loop freedom at all times. We also propose a
completely distributed delay estimation procedure that
eliminates the need for ACK-based delay estimation.
Simulations indicate that the protocol appears to be
effective in obtaining improved throughput-delay performance
gains over shortest path routing in static networks.
We have implemented the protocol in user space on a
modified Linux 2.4.20 kernel based on an architecture that
separates probabilistic multipath routing from delay estimation.
A proof-of-concept measurement study indicates
the effectiveness of Wardrop route adaptation.