Transcript Microsoft PowerPoint Presentation: 03_1_MobileComputing

Mobile and Wireless Computing
Lecture 3 : The Dynamic Source Routing Protocol

Lecture 3.1 : An Overview of the DSR Protocol.

Lecture 3.2 : Routing Details and Performance
of the DSR Protocol
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Dynamic Source Routing (DSR) Protocol

The DSR is a simple and efficient protocol for
routing in mobile, ad hoc and wireless networks.

DSR is suitable for routing in multi-hop networks.

A mobile, ad hoc network is completely selforganizing while using the DSR protocol. All
nodes cooperate to forward packets.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
The DSR Protocol (I)

Nodes in the network may move about, join or
leave.

All routing is automatically determined by the
protocol.

The number and sequence of intermediate hops
needed to reach any destination may change
dynamically. Hence the network topology may
be quite complex.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
The DSR Protocol (II)

DSR is an on-demand or reactive routing
protocol.

When a source node S wants to send a
message to a destination node D, the process
starts with a route discovery phase.

The message is sent once a route has been
discovered and S knows about the discovered
route.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
The DSR Protocol (III)

However, DSR extensively takes advantage of
existing knowledge of the network topology.

Each node gathers information about the
network topology by overhearing other nodes’
transmissions.

This is known as promiscuous mode of
operation and most wireless cards support this
(IEEE 802.11 standard).
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
The DSR Protocol (IV)

Each node maintains a route cache to
remember routes that it has learnt about.

One of the main advantages of DSR as opposed
to a table driven protocol like DSDV is that the
number of control messages is much smaller.

Hence DSR is more energy-efficient and does
not congest the network with too many control
messages.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
An Example when a Route is Discovered Completely
AB
A
B
A
A is
ABCD
C
ABC
trying to find a route to E
Each
E
D
intermediate node appends its ID at the end.
knows the reverse route and sends a route reply.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
E
Mobile and Wireless Computing
An Example when a Route is Discovered Partially
D
A
AB
B
A
A is
C
trying to find a route to E
C
already has a route to E in its route cache.
C
sends back the complete route to A.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
E
Mobile and Wireless Computing
Assumptions

All nodes wishing to communicate with other
nodes in the ad hoc network participate fully in
running the DSR protocol.

The diameter of the network is more than 1, but
usually a small number.

In other words, a message usually goes through
only a small number of hops.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Assumptions

The nodes may move at any time without notice
and may even move continuously.

However, we assume that the speed with which
the nodes move is moderate with respect to the
packet transmission latency or wireless
transmission range of the network.

If the nodes move extremely fast, the only
possible protocol is flooding.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Assumptions

Each node selects a single IP address by which
it is known in the network.

This is necessary for assigning a unique ID for
each node.

Each node may or may not work in the
promiscuous mode. However, most wireless
interface cards support this.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Overview and Important Properties

The DSR protocol has two important
mechanisms through which the protocol
operates.
–
Route Discovery : A node S wishing to send a packet
to node D obtains a route to D
–
Route Maintenance : When S is using a discovered
route to D, S may detect that the route is broken. In
such cases, S may use an alternate route to D (if it is
known), or start another route discovery phase to D.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Overview of the DSR Protocol



Route discovery and route maintenance operate
entirely on-demand.
There is no need to broadcast periodically to
update routing information in individual nodes.
DSDV requires such periodic broadcasts.
The number of overhead packets is much
smaller in DSR. The number of overhead
packets drop to zero when the nodes are static
and all routes have been discovered.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Overview of the DSR Protocol



When nodes are mobile and/or communication
pattern changes, the number of overhead
packets increase proportionately.
It is necessary to discover new routes in these
situations and hence the new route discovery
packets are the overhead packets.
Note that, a node may receive multiple routes to
a destination in response to a route discovery
request.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Overview of the DSR Protocol



A node may store multiple routes to a
destination in its route cache.
A node can react to changes in network topology
much more rapidly by taking advantage of
cached routes.
For example, if one route to a destination is
broken, the source node can choose another
route to the destination from its route cache.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
DSR Route Discovery

Consider the case when a source node S wants
to send a packet to a destination node D.

In a ‘good situation’, S already knows a route to
D from its route cache.

In this case, S will add the sequence of hops to
D in the header of the packet. Then S will send
the packet to the first node in this sequence.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
DSR Route Discovery

In the ‘bad case’ S will not find any route to D in
its route cache.

S will initiate the route discovery protocol. In this
case, we call S the initiator and D the target of
this protocol.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
DSR Route Discovery




Node S is trying to discover a route to node D.
S broadcasts a route request message to its
neighbours. This message is received by all
nodes within the transmission range of S.
Each route request message contains the
initiator and target of the route discovery.
Also, each route request is stamped with a
unique ID assigned by the initiator.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
An Example Route Discovery
D
A
AB
ABCD
B
A
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
C
ABC
E
Mobile and Wireless Computing
DSR Route Discovery

Every node that receives a route request
message, does one of the following :
–
–
A node like B first searches its route cache to see
whether it has a stored route to D. If it has such a
route, B sends that route to S.
If there is no such route in its route cache, B
broadcasts the route request message to its
neighbours. B attaches its own ID to the route request
message
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)