14-06-2009, 01:01 AM
SEMINAR REPORT
on
Adaptive Routing in Adhoc Networks
Submitted in partial fulfillment for the award of the degree of
Master of Technology
in
Computer and Information Science
By
M.VENGATACHALAM
Department of Computer Science
Cochin University of Science and Technology
Cochin-22, Kerala
2008 Page 2
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
2
COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY
DEPARTMENT OF COMPUTER SCIENCE
CERTIFICATE
This is to certify that the report entitled
Adaptive Routing in Adhoc
Networks
is a bonafide record of the seminar presented by
Mr.M.VENGATACHALAM. in partial fulfillment of the requirements for the award
of M.Tech Degree in Computer and Information Science of Cochin University of
Science & Technology, during the academic year 2008.
G. Santhosh Kumar
Prof. Dr. K. Poulose Jacob
Lecturer
Head of the Department
Seminar Guide
Dept of Computer Science
Dept of Computer Science
CUSAT
CUSAT
Kochi-22
11-07-2008 Page 3
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
3
ACKNOWLEDGEMENT
First of all, I thank GOD ALMIGHTY, for showering his grace upon me to
successfully carry out this work, everything in time.
I take this opportunity to thank Prof. Dr. K. Poulose Jacob, Head of the Dept. of
Computer Science, CUAST for providing me with the necessary facilities to do this
work.
I am deeply indebted to Shri.G. Santhosh Kumar, Lecturer, Dept. of Computer
Science, CUSAT for the excellent guidance and timely suggestions.
Finally, I express my deepest gratitude to all my family members for their
encouragement, which helped me to keep my spirit alive and complete this work
successfully.
M.VENGATACHALAM Page 4
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
4
ABSTRACT
The dynamics of an ad hoc network are a challenge to protocol design because
mobility inevitably leads to unstable routing, and consequently flows encounter
fluctuations in resource availability on various paths during the lifetime of a session. This
has become serious, especially for those protocols based on single-path reservation, as
frequent reservation and restoration of reservation-based flows increase the instability of
connections.
Advances in wireless research are focusing more and more on the adaptation
capability of routing protocols due to the interrelationship among various performance
measures such as those related to topological changes (link breakages, node mobility,
etc.) and quality of service (QoS) parameters (load, delay, etc).
After giving a more detailed discussion of the existing work in adaptive routing,
we propose a new routing protocol for adhoc wireless networks - Multipath Source
Routing (MSR), which is an extension of DSR(Dynamic Source Routing) that
incorporates the multipath mechanism into DSR. Based on the measurement of
RTT(Round Trip Time), we propose a scheme to distribute load among multiple paths.
MSR is an adaptive routing for ad hoc networks. It considers the two fundamental
issues in its design. MSR may adapt to topology changes by retaining the route discovery
and route maintenance mechanism of DSR. In addition, MSR employs a probing-based
load-balancing mechanism. Simulation results show that MSR can improve the packet
delivery ratio and the throughput of TCP and UDP, and it reduces the end-to-end delay
and the average queue size while adding little overhead.
As a result, MSR decreases network congestion and increases the path fault
tolerance quite well. Page 5
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
5
TABLE OF CONTENTS
Page No.
CHAPTER 1 : INTRODUCTION
7
1.1 Introduction
7
1.2 Adaptive Routing
7
1.3 Adhoc Networks
8
CHAPTER 2 : NETWORK ARCHITECTURES
10
2.1 Infrastructure Based Networks
10
2.2 Rapidly Deployable Network
11
2.3 Hybrid Networks
12
CHAPTER 3 : ROUTING PROTOCOLS
13
3.1
Introduction
13
3.2
Proactive routing protocols(Table Driven)
13
3.3
Reactive routing protocols(On demand protocols)
13
3.4
Hybrid routing protocols
13
CHAPTER 4 : DYNAMIC SOURCE ROUTING
CHAPTER 5 : MSR (MULTIPLE SOURCE ROUTING)
14
5.1
Introduction
14
5.2
Route Discovery
14
5.3
Route Maintenance
19
5.4
Path finding
19
5.5
Packet forwarding and load balancing
19
5.6
Toward gratuitous mode
21
CHAPTER 6 : PERFORMANCE EVALUATION
22
6.1
Simulation environment
22
6.2
Performance Metrics
22
6.3 Simulation Results
22
6.3.1 UDP traffic (max moving speed of 20 m/s)
22
6.3.2 TCP traffic (max- moving speed 20m/s)
26 Page 6
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
6
CHAPTER 7 : DISCUSSIONS
27
CHAPTER 8 : CONCLUSIONS
30
APPENDIX (LIST OF FIGURES & TABLES)
31
REFERENCES
33Page 7
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
7
CHAPTER 1
INTRODUCTION
1.1 Introduction
Congestion at the links and in the routers is the main cause of large delays in the
Internet; the same is true in ad hoc networks where bandwidths are always very limited.
Routing protocols used in conventional wired networks (e.g., Bellman-Ford and page link
state) are not well suited for the mobile environment due to the considerable overhead
produced by periodic route update messages, and to their slow convergence to
topological changes.
In addition, all the Internet routing protocols in use today rely on single-path
routing algorithms, which not only under-utilize resources, but also cannot cope with
congestion and page link breakage. This can be attributed to the fact that all traffic for a
destination is required to be routed through a single successor. So when a page link becomes
congested or broken, its entire carried traffic has to be rerouted; this becomes more time
consuming in mobile networks. If page link costs are made functions of congestion or delays,
routing table entries can become unstable in single-path routing protocols.
Before get in to details we will discuss about the Adaptive routing and Adhoc
networks.
1.2 Adaptive routing
Adaptive routing describes the capability of a system, through which routes are
characterised by their destination, to alter the path that the route takes through the system
in response to a change in conditions. The adaptation is intended to allow as many routes
as possible to remain valid (that is, have destinations that can be reached) in response to
the change.
The term is commonly used in data networking to describe the capability of a network
to 'route around' damage, such as loss of a node or a connection between nodes, so long
as other path choices are available. There are several protocols used to achieve this.
Systems that do not implement adaptive routing are described as using static routing,
where routes through a network are described by fixed paths (statically). A change, such
as the loss of a node, or loss of a connection between nodes, is not compensated for. This
means that anything that wishes to take an affected path will either have to wait for the
failure to be repaired before restarting its journey, or will have to fail to reach its
destination and give up the journey. Page 8
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
8
1.3 Adhoc Networks
An ad-hoc (or "spontaneous") network is a local area network or other small
network, especially one with wireless or temporary plug-in connections, in which some
of the network devices are part of the network only for the duration of a communications
session or, in the case of mobile or portable devices, while in some close proximity to the
rest of the network. In Latin, ad hoc literally means "for this," further meaning "for this
purpose only," and thus usually temporary and does not require a router or a wireless
base station. Fig 1.1 represent the Adhoc networks.
.
Multipath routing can overcome the above problem discussed in 1.1. In addition,
it can provide load balancing and route failure protection by distributing traffic among a
set of diverse paths. These benefits make multipath routing a good candidate for
bandwidth limited and mobile ad hoc networks. However, maintaining alternative paths
requires much more routing table space and computation, especially for table-driven
routing algorithms in large networks.
Fig 1.1 Adhoc networks
Many adhoc routing protocols have been proposed recently, such as AODV,
DSDV, DSR, and TORA. However, they are all single-path basedâ„¢. DSR (DynamicPage 9
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
9
Source Routing) is capable of reducing communication and computation overhead. In this
work, the analytical models have been developed to demonstrate how the frequency of
query floods is reduced with their multipath extensions, and presented some numerical
data obtained from the analytic models. They also did some simple and preliminary
simulations; there are still a lot of work regarding multipath routing in wireline networks.
In this paper, we propose a new approach called the Multipath Source Routing
(MSR) for multipath routing in ad hoc wireless networks. This is an extension of DSR
(Dynamic Source Routing).â„¢ Our work focuses on the adaptively distributing load among
several paths, according to the measurement of the round-trip time of every path,
whereby a heuristic load balancing equation is given. To the best of our knowledge, this
is the first trial to introduce probing-based feedback control to multipath routing. An RTT
measurement tool for DSR and MSR in simulation, SRping is developed to get the RTT
between two arbitrary nodes.
It is also the first attempt to analyze the TCP dynamics in ad hoc networks and
multipath routing context. Our results show that MSR can reduce the traffic burst ness
seen by individual paths, adapt to frequently topology changes and consequently achieve
inherent robustness to channel errors and page link failures. We also analyze and compare the
packet dynamics of MSR and DSR in depth. Page 10
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
10
CHAPTER 2
NETWORK ARCHITECTURES
There are different types of wireless networks are being used across for various
communication. They are
1. Infrastructure based networks
2. Rapidly deployable networks
3. Hybrid Networks
2.1 Infrastructure Based Networks
Infrastructure networks contain special nodes called access points(APs), which
are connected via existing networks. APs are special in the sense that they can interact
with wireless nodes as well as with the existing wired network. The other wireless nodes,
also known as mobile stations(STAs), communicate via APs. The APs also act as bridges
with other networks. Fig 2.1 shows the infrastructure networks. Example for
infrastructure network is Cellular network and Sattelite network. Page 11
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
11
Fig.2.1 Infrastructure network
2.2 Rapidly deployable network
In Ad Hoc Mode, chains of computers will connect to pass your data, if your
computer is not directly in range. On the other hand, you do not have control over the
path your data takes. The automatic configuration routines may send your data through
several computers, causing significant network delays.
¢
changes regularly, system resources are taken just to maintain connectivity.
Because Ad Hoc Mode does not require an access point, it's easier to set up,
especially in a small or temporary network.
¢
Infrastructure takes advantage of the high power of an access point to cover wide
areas. Ad Hoc Mode connections are limited, for example between two laptops, to
the power available in the laptops.
¢
Because the network layout (the network topology) in Ad Hoc Mode
¢
As the Ad Hoc topology changes, throughput and range will change, sometimes in
unanticipated ways. New users will have an easier time learning wireless
strengths and weaknesses with Infrastructure Mode, and therefore the NETGEAR
Installation Guides focus on it.
¢
In an Ad Hoc network with many computers, the amount of interference for all
computers will go up, since each is trying to use the same frequency channel. Page 12
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
12
Fig 2.2 shows the scenario.
The example for Rapidly deployable networks are
a) Adhoc wireless networks
b) Wireless sensor networks
c) Heterogeneous networks
Fig.2.2 Rapidly Deployable Network
2.3 Hybrid Network
One of the major application areas of ad hoc wireless networks is in hybrid
wireless architectures such as multi-hop cellular networks and an integrated cellular
adhoc relay networks. The primary concept behind the cellular networks is geographical
channel reuse. Several techniques such as cell sectoring, cell resizing, and multi-tier cells
have been proposed to increase the capacity of cellular networks. This is the combination
of both infrastructure and rapidly deployable networks. Wireless internet is comes under
this category. Page 13
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
13
CHAPTER 3
ROUTING PROTOCOLS
3.1 Introduction
A routing protocol is a protocol that specifies how routers communicate with
each other to disseminate information that allows them to select routes between any two
nodes on a network. Typically, each router has a prior knowledge only of its immediate
neighbors. A routing protocol shares this information so that routers have knowledge of
the network topology at large. Three types of routing protocols have been identified.
They are
a) Proactive routing protocols
b) Reactive routing protocols
c) Hybrid routing protocols
3.2 Proactive routing protocols(Table Driven)
This type of protocols maintains fresh lists of destinations and their routes by
periodically distributing routing tables throughout the network. The main disadvantages
of such algorithms are -
1. Respective amount of data for maintenance.
2. Slow reaction on restructuring and failures.
Examples of proactive algorithms is DSDV etc,.
3.3 Reactive routing protocols(On demand protocols)
This type of protocols finds a route on demand by flooding the network with
Route Request packets. Source initiates the route discovery. Example for the same is
DSR(Dynamic Source routing) and MSR(Multipath Source Routing)
3.4 Hybrid routing protocols
This type of protocols combines the advantages of proactive and of reactive routing.
The routing is initially established with some proactively prospected routes and then
serves the demand from additionally activated nodes through reactive flooding. The
choice for one or the other method requires predetermination for typical cases. The main
disadvantages of such algorithms are - Page 14
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
14
1. Advantage depends on amount of nodes activated.
2. Reaction to traffic demand depends on gradient of traffic volume.
Example for this type of protocol is ZRP(Zone Routing Protocol)
CHAPTER 4
DYNAMIC SOURCE ROUTING
DSR uses source routing instead of hop-by-hop packet routing. Each data packet
carries the complete path from source to destination as a sequence of IP addresses. The
main benefit of source routing is that intermediate nodes need not keep route information
because the path is explicitly specified in the data packet. DSR is on-demand based; that
is, it does not require any kind of periodical message to be sent. The source routing
mechanism, coupled with the on-demand nature of this protocol, eliminates the need for
the periodic route advertisement and neighbor detection packets in other protocols.
CHAPTER 5
MSR (MULTIPLE SOURCE ROUTING)
5.1 Introduction
By using source routing, MSR can improve performance by giving applications
the freedom to use multiple paths within the same path service. However, maintaining
alternative paths requires more routing table space and computational overhead.
Fortunately, some DSRâ„¢s characteristics can suppress these disadvantages. First, Source
Routing is so flexible that messages can be forwarded on arbitrary paths, which makes it
very easy to dispatch messages to multiple paths without demanding path calculation in
the intermediate hops. Second, the on-demand nature of DSR reduces the routing storage
anti routing computation greatly.
The MSR protocol consists of two mechanisms: Route Discovery and Route
Maintenance.
5.2 Route Discovery
Route discovery is initiated by a source whenever a source has a data packet to
send but does not have any routing information to the destination. To establish a route,
the source floods the network with request messages carrying a unique request ID. When
a request message reaches the destination or a node that has route information to the
destination, the node sends a route reply message containing path information back to the
source. In order to reduce overhead generated during a route discovery phase, the route
cache maintained at each node records routes the node has learned and overheard over Page 15
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
15
that time frame. The following fig 5.1, 5.2, 5.3, 5.3, 5.4 and 5.5 depicts the same
mechanism.
Fig 5.1 Route discovery in MSR Page 16
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
16
Fig 5.2 Route Discovery in MSR(contd) Page 17
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
17
Fig 5.3 Route Discovery in MSR(contd) Page 18
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
18
Fig 5.4 Route Reply in MSR
Fig 5.5 Data delivery in MSR Page 19
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
19
5.3 Route Maintenance
Route Maintenance is the mechanism by which the sender S of a packet detects
network topology changes that render useless its route to the destination D (because two
nodes listed in the route have moved out of range of each other).
When Route Maintenance indicates a source route is broken, S is notified with a
ROUTE ERROR packet. The sender S can then attempt to use any other route to D
already in its cache or can invoke Route Discovery again to find a new route.
5.4 Path finding
MSR retains the route discovery mechanism of DSR whereby multiple paths can
be returned. Each route discovered is stored in the route cache with a unique route index.
So it is easy for us to pick multiple paths from the cache. In multipath routing, path
independence is an important property, because a more independent path set offers more
aggregate physical resources between a node pair (because when those resources are not
shared, the less likely the performance of one path affects the performances of other
paths). To achieve high path independence, the disjoint paths are preferred in MSR.
There is no looping problem in MSR, as the route information is contained inside the
packet itself; routing loops, either short- or long-lived, cannot be formed as they can be
immediately detected and eliminated.
5.5 Packet forwarding and load balancing
Since MSR uses source routing, intermediate nodes do nothing but forwarding the
packet as indicated by the route in its header, thus adding no more processing complexity
than that in DSR. All the work for path calculation is done in the source hosts. In MSR,
source nodes are responsible for load balancing. In our protocol, we implement a special
table containing multiple path information to the specific destination, as illustrated as
follows.
{struct mul-dest
int index ;
ID Dest;
float Delay;
float Weight;}
Dest is the destination of a route. Index is the current index of the route in DSRâ„¢s route
cache that has a destination to Dest. Delay is the current estimate of the round- trip time.
Weight is a per-destination based load distribution weight between all the routes that
have the same destination. Weight is in terms of the number of packets to be sent
consecutively on the same route every time. The choice of Weight is an interesting and
challenging task, and we make the following observation. Page 20
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
20
In this paper we address the multipath routing problem in the context of single
channel, for the disjoint path problem in multiple channel environment Within an ad hoc
network, which is always an autonomous system acting as a stub network, there is less
heterogeneity in some sense when compared to WAN and MAN. For instance, in WAN
or MAN the maximal bandwidths that every node can obtain vary little, so do the round-
trip delays. Therefore, we assume the bandwidth-delay product is a constant. Then the
available bandwidth is inversely proportional to the RTT. So the traffic can be distributed
among multiple paths proportional to the available bandwidth. The principle is inherently
simple but reasonable in ,wireless networks. In wireline networks, due to the very
different bandwidths, delay cannot be a definite indicator of the available bandwidth.
From our above observation, we propose to choose the weight Wij (i is the index
of the route toj) according to a heuristic
equation ( 1 ) :
where
is the maximum delay of all the routes to the same destination, dij is the
delay of route with index i, and U is a bound to insure that Wij should not to be too large.
R is a factor to control the switching frequency between routes. The larger the Râ„¢s value,
the less frequently the switching happens and the less processing overload of searching
and positioning an entry in the mul-dest table. When choosing R, the IFQ bufferâ„¢s size
should also be taken into considerations. we have done extensive experiments beyond the
R = 1 and we found R = 3 to be better in reducing the out-of-order deliveries in TCP. So
in our experiment, R is set to three for IFQ size of 50. When distributing the load, the
weighted-round-robin scheduling strategy is used.
To aid the load balancing and to decouple the interlayer dependence of delay
measurement, a network layer probing mechanism is employed. Probing is also an
enhancement to the DSR Route maintenance mechanism. Normally, in DSR, a link
breakage can be notified only when a Route Error message is returned. However, in
wireless mobile environment, it has a nontrivial chance that the Route Error message
cannot reach the original sender successfully. Although, as a last resort, a bit in the
packet header could be included to allow a host transmitting a packet to request an
explicit acknowledgement from the next hop receiver, probing one path constantly only
to test its validity is not (cost effective. Therefore, the function of probing in MSR is
two:fold: to get the path delay status and to test the validity of active paths. Page 21
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
21
5.6 Toward gratuitous mode
We should explain gratuitous packet here. In DSR, when a data packet is received
as the result of operating in promiscuous receive mode, the node checks if the Routing
Header packet contains its address in the unprocessed portion of the source route. If so,
the node knows that packet could bypass the unprocessed hops preceding it in the source
route. The node then sends what is called a gratuitous Route Reply message to the
packetâ„¢s source, giving it the shorter route without these hops.
Since in MSR, there are always routes that are not the shortest ones, The network
stack for a mobile node consists of a page link layer (LL), an ARP module connected to LL,
an interface priority queue (IFQ), a MAC layer (MAC), a networks interface (netiF), all
connected to the channel. The GRAT (GRATuitous) packets increase greatly, which take
too much IFQ and ARP buffer space. Thus, we turn off the gratuitous options in our
simulations.Page 22
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
22
CHAPTER 6
PERFORMANCE EVALUATION
6.1 Simulation environment
We use ns to conduct the simulation. CMU has extended ns with some wireless
supports, including new elements at the physical, link, and routing layers of the
simulation environment. Using these elements, it is possible to construct detailed and
accurate simulations of wireless subnets, LANs, or multi-hop ad hoc networks. For
scenario creation, two kinds of scenario files are used. The first is a movement pattern
file that describes the movement that all nodes should undergo during the simulation.
The second is a communication pattern file that describes the packet workload
that is offered to the network layer during the simulation. To get the performance of MSR
under different moving speeds environment, we use two simulation sets with speed 1 m/s
and 2Om/s respectively. Our simulations model a network of 50 mobile hosts placed
randomly within a 1500mx300m area, both with zero pause time. To evaluate the
performance of MSR, we experimented with different application traffic, including CBR
and FTP. CBR uses UDP as its transport protocol, and FTP uses TCP. The channel is
assumed error-free except for the presence of collision. For other simulation detail, please
refer [2]
6.2 Performance Metrics
In performance evaluation, we choose the following metrics:
¢ Queue size: The queue size of an IFQ object at each node;
¢ Packet delivery ratio: The ratio between the number of packets originated by the
application layer CBR sources and the number of packets received by the CBR
sink at the final destination;
¢ Data throughput: The total number of packets received during a measuring
interval divided by the measurement interval;
¢ End-to-end delay;
¢ Packet drop probability.
For TCP, another issue concerned is the out-of-order problem. To present the packet
dynamics clearly, the ack time-sequence plot is given.
6.3 Simulation Results
6.3.1 UDP traffic (max moving speed of 20 m/s)
We first look at CBR traffic implemented with UDP agents. A scenario with 20
CBR connections is adopted. Since UDP has no feedback control mechanism, all the
CBR traffic generated is constant no matter how the network runs. So it can act as a good
test bed for comparing routing protocols. We shall use it as a reference point. Fig. 1
shows that fewer CBR packets are dropped in MSR than that in DSR. Table I shows drop
summery in detail; the main reason of dropping is No Route and IFQ Full. Fig. 2 Page 23
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
23
provides the end-to-end packet delivery ratio of every connection, and the comparison
shows MSR is better than DSR. Page 24
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
24Page 25
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
25
From Fig. 3 we can see that MSR achieves higher throughput than DSR almost
on every connection, just as we expected. This can be attributed to the fact that the
multipath routing effectively utilizes currently unallocated network resources. Fig. 4
shows the end-to-end delay of every connection. Fig. 5 presents the average queue size
for all 50 hosts. From Fig. 5, we can see that, in MSR, the packets that should have been
queued in the IFQ have been redistributed to other nodes that have light load, through
which the traffic is balanced. Balancing the route load in MSR shortens the delay as the
chance of congestion is reduced.
Table 11 shows the routing overheads in DSR and MSR respectively. We can see the
routing messages in DSR are only little more than that of DSR. However, the packet
drops probability is lower than that of DSR. The main drop reason is still No Route and
IFQ Full. Page 26
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
26
6.3.2 TCP traffic (max- moving speed 20m/s)
For TCP traffic, we take a scenario with 30 FTP connections, with network rather
heavily loaded. Since TCP has an AIMD (Additive increase Multiplicative Decrease)
feedback control mechanism, the statistics at every node has less meaning than that of
UDP, we focus on the end-to-end packet dynamics instead. Figs. 6 and 7 show that the
multipath routing can also be used to reduce the end-to-end network latency and message
drop probability, or increase the likelihood of message delivery for TCP connections.
From Figs. 8 and 9, we can see there are not many out-of order deliveries in MSR.
On the contrary, the end-to-end throughput of TCP in MSR has increased a lot due to the
smooth increase of sequence number. Fig. 9 also implies that MSR recovers more quickly
than DSR does when the connection meets severe packets droppings (e.g. at time 90s). It
illustrates that cur load-balancing method achieves a good switching granularity.Page 27
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
27
CHAPTER 7
DISCUSSIONS
In our initial experiments, we found that the major statistics of Routing Packets of
MSR is comparable to that of DSR, except that the GRAT packets count in MSR is too
large compared to DSR. Thus we turn off the gratuitous options, and the results become
better. The simulation results show that the main reason for packet drops in DSR is No
Route and IFQ Full, while these two factors improve a lot in MSR.
Under max speed Id s , the throughput and end-to-end delay of MSR are also
better than those of DSR. There is no significant difference of packet drops between DSR
and MSR. Therefore, we can conclude that one of the mail gains we get from MSR is
attributed to less No Route drops. In other words, multipath routing compensates for
route failures efficiently in high-speed movement. It is consistent with the results in
Tables I and 11.
When evaluating a network routing protocol, control load should also be
considered. There is no more control load in MSR than that in DSR, except for probing
packets transmitted in networks. Since we use SRping (which is unicast), rather than
flooding, to test the validity of paths currently used, and the probing interval we choose is
very conservative, there is little overload added. Page 28
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
28
Fig 8. TCP segments time-sequence plot of a heavy connection
Node 49 to node 50 Page 29
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
29Page 30
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
30
CHAPTER 8
CONCLUSIONS
In this paper, a new multipath routing protocol in ad hoc networks, MSR is
presented. Our protocol is a direct descendant of DSR. By incorporating the multipath
mechanism into DSR and employing a probing based load-balancing mechanism, the
throughput, end-to-end delay, and drop probability have been improved significantly. The
drawback of MSR may be the processing overhead of originating the packets. Fortunately
the computer is becoming more powerful and cheaper. So it may not be the obstacle to
the deployment of MSR.. Page 31
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
31
APPENDIX
LIST OF FIGURES
Page No.
Fig 1.1 - Adhoc networks
8
Fig.2.1 Infrastructure network
11
Fig.2.2 Rapidly Deployable Network
12
Fig 5.1 Route discovery in MSR
15
Fig 5.2 Route Discovery in MSR(contd)
16
Fig 5.3 Route Discovery in MSR(contd)
17
Fig 5.4 Route Reply in MSR
18
Fig 5.5 Data delivery in MSR
18
Fig .1 CBR packets dropped at each node
23
Fig .2 Packet delivery ratio of every connection
24
Fig .3 End “ to-end throughput
24
Fig .4 End “ to “end delay
25
Fig .5 IFQ queue size at each node
25
Fig .6 End “to “ throughput of each connection
27
Fig .7 End “ to “ delay of each connection
28
Fig 8. TCP segments time-sequence plot of a heavy connection
28
Node 49 to node 50
Fig .9 Time sequence plot with sequence # mod 300
29 Page 32
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
32
LIST OF TABLES
Page no
Table I
23
Table II
26Page 33
Adaptive Routing in Adhoc Networks
Department of computer Science CUSAT
33
REFERENCES
1. Adaptive Multipath Source Routing in Ad Hoc Networks. Lei Wang, Yantai
Shu,Miao Dong, and. Lianfang Zhang. Department of Computer Science ...
ieeexplore.ieeeiel5/7452/20263/00937362.pdf?
2. Implementing multipath source routing in a wireless ad hoc network ...evaluation
of multipath source routing was conducted and. compared with dynamic source
routing ... (Multipath Source Routing) [7] is one such protocol our ...
ieeexplore.ieeeiel5/10170/32495/01517283.pdf?
3. Welcome to IEEE Xplore 2.0: Adaptive multipath source routing in ...Adaptive
multipath source routing in ad hoc networks Lei Wang Yantai Shu Miao Dong
Lianfang Zhang Yang, O.W.W. Dept. of Comput. Sci., Tianjin Univ.; ...
ieeexplore.ieeexpls/abs_all.jsp?
4. http://ietfproceedings/97dec/97dec-final-93.htm Adaptive Multipath
Source Routing in Ad Hoc Networks
5.
ieeexplore.ieeeiel5/8375/26364/01173115.pdf?arnumber=1173115
6. J. Broch, D. B. Johnson, and D. A. Maltz. The dynamic source routing protocol
for mobile ad hoc networks. http://ietf.org /internetdrafts/draft-ietf-
manet-dsr-03.txJtu, ne 1999.
7. J. Broch, D. A. Maltz, D. B. Johnson, Y-C. Hu, and J. Jetcheva. A performance
comparison of multi-hop wireless ad hoc network routing protocols. In ACM
MOBICOMâ„¢98, pp. 85-97, October 1998.
8. D. B. Johnson and D. A. Maltz, Dynamic Source Routing in AdHoc Wireless
Networks, In Mobile Computing, edited by Tomasz Imielinski and Hank Korth,
Chapter 5, Kluwer Academic Publishers, 1996,pp. 153-181.
9. MANET. http://ietfhtml.charters/manet-charter.html.
10. AdHoc wireless Networks Architectures and Protocols
By C. Siva Ram Murthy and B.S. Manoj
11. ns, http://mash.cs.berkeley.edu/ns.
12. L. Wang, L. F. Zhang, Y. T. Shu, M. Dong, and 0. W. W. Yang, Multipath
Source Routing in Wireless Ad Hoc Networks, in Proceedings of the IEEE
CCECE, pp. 479-483, Halifax, Nova Scotia, Canada, May 7-10.2000
