Transcript Microsoft PowerPoint Presentation: 09_2_MobileComputing

Mobile and Wireless Computing
The Possibility of Permanent Routing Loops




There are two cases when a router determines
that a recent update may cause a permanent
routing loop in its source tree.
Case 1 : Suppose router i has a path to a
destination dest in its source tree such that the
successor of i (i.e., next hop) is a node j with i<j.
In this case, i sends an LSU message to its
neighbours.
We are assuming that the addresses of the
routers are unique integers.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Possibility of Routing Loops (Case 1)


The loop-prevention mechanism is implemented
through the following local route selection
algorithm :
Router i cannot add a link (u,v) to its new source
tree choosing k on the path to (u,v) if (u,v) is not
in the source tree reported by k.
v
i
k
u
(u,v) must be in the source
tree reported by k (in the
same order) if i wants to
include the link (u,v) in its
source tree.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Possibility of Routing Loops (Case 1)
v
i
k
u
(u,v) must be in the source
tree reported by k (in the
same order) if i wants to
include the link (u,v) in its
source tree.
Each
link in the topology graph can be labelled with the
neighbours that have reported the link.
A link
(u,v) is added in the source tree of i only if the
neighbour k along the path from i to u has reported the
link (u,v) in its source tree.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
The Use of Case 1
V
U
J
K
(Minimum node)
K<L
I
L
Since K is forced to choose L (K<L) as its successor in its
source tree, K is forced to send an LSU and other nodes
will update their source trees.
Nodes
like I and J will be forced to recompute their source
trees and will include either (U,V) or (V,U) in their source
trees.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Possibility of Permanent Routing Loops (Case 2)


The rule in Case 1 may not be sufficient to break
all loops and hence we need the rule in Case 2.
Case 2: Router i sends a source-tree update
after processing an input event if :
–
The distance from the new successor n to a
destination j is longer than the distance from the
previous successor m to the same destination j.
m
i
n
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
j
Mobile and Wireless Computing
Possibility of Routing Loops (Case 2)
b
b
e
a
f
e
a
f
c
d
c
d
b
e
b
e
a
f
c
d
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
a
f
c
d
Mobile and Wireless Computing
Possibility of Routing Loops (Case 2)
b
e
a
f
c
b
d
e
a
b
f
c
c>b d
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
e
a
f
c
b>a d
Mobile and Wireless Computing
Possibility of Routing Loops (Case 2)
b
e
a
b
e
f
a
c
d
b
c
d
(b,e,1) (e,d,1) (e,f,1)
e
b
e
a
f
c
d
(b,e,1) (e,d,1) (e,f,1)
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
f
a
c
(b,e,infinity)
Mobile and Wireless Computing
Possibility of Routing Loops (Case 2)
b
e
b
a
a
c
(b,e,infinity)
c
(b,e,infinity)
b
Nodes
a,b and c realize that
there is no path to nodes d,e
and f
a
c
(b,e,infinity)
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Implementation of Cases 1 and 2



A router must remember a copy of its source
tree that it last notified to its neighbours.
If the new source tree includes new neighbours,
then the router must send its entire source tree
as an update.
If the new source tree includes the same set of
neighbours as the previous source tree, the
router sends only the updates necessary to get
the new source tree from the previous one.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
STAR Protocol Ensures Loop-free Paths

Since the network is a finite graph, any
propagation of an LSU message reaches every
node within a finite time.

We will assume that changes in network
topology is not so fast that flooding is the only
alternative.
Under these assumptions, it is easy to show that
STAR ensures loop-free paths when each LSU
message is processed in the order they are
received.

Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
STAR Protocol Ensures Loop-free Paths

There are three cases when a loop may form :
–
–
–
When a new node has joined an existing source tree
When a router is forced to choose a new successor
due to the higher cost of an existing path.
When there is a link failure and a router is forced to
choose a new successor to maintain the connectivity
of its source tree.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
When a New Node Joins an Existing Source Tree




Suppose a loop forms due to a new node n.
However, a router sends an LSU message
whenever it has a new neighbour.
At least one of n´s neighbours will generate an
LSU message which will propagate through the
network and other nodes will update their source
trees.
Hence, each node will have a loop-free source
tree within a finite time.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
When a Router is Forced to Choose a New Successor

Suppose a router i chooses a new successor
and a loop forms due to this.

There must be at least one node in this loop that
has a successor with a higher address.

We have seen in Case 1 that this smallest node
will generate an LSU message and the other
nodes will update their source trees.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Link Failure (when Case 2 Occurs)



Each router computes its source tree by running
Dijkstra´s shortest path algorithm on its partial
topology graph.
Assume that the previous source tree is ST(1)
and the new source tree after the link failure is
ST(2) for a router i.
Since the link failure is the only event in between
the computations of ST(1) and ST(2), there must
be at least one node d whose distance is higher
in ST(2) from i compared to ST(1).
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Link Failure (when Case 2 Occurs)



This is due to the fact that Dijkstra´s shortest
path algorithm ensures shortest paths to each
destination.
Since there is at least one destination with a
higher distance, i will generate an LSU message
(as we have seen in Case 2).
Other nodes will recompute their source trees
due to this LSU message and they can
recompute their loop-free source trees.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)
Mobile and Wireless Computing
Performance of STAR

STAR outperforms both proactive protocols like
DSDV and on-demand protocols like DSR in
terms of lower number of overhead packets and
higher percentage of packets delivered.

This is due to the fact that STAR has lower
latency in finding routes compared to ondemand protcols and STAR need not send
periodic update messages like proactive
protocols.
Institute for Computer Science, University of Freiburg
Western Australian Interactive Virtual Environments Centre (IVEC)