Addressing Key Challenges in Mobile Ad-Hoc Networks
undefined
I
C
T
E
n
t
r
e
p
r
e
n
e
u
r
s
h
i
p
f
o
r
T
e
l
e
m
a
t
i
c
s
S
e
r
v
i
c
e
s
L
2
-
M
o
b
i
l
e
A
d
-
H
o
c
N
e
t
w
o
r
k
s
(
M
A
N
E
T
s
)
What Problems Do You See
As Important to Address and Why?
W
h
a
t
A
r
e
M
o
b
i
l
e
A
d
-
H
o
c
N
e
t
w
o
r
k
s
?
N
o
f
i
x
e
d
n
e
t
w
o
r
k
i
n
f
r
a
s
t
r
u
c
t
u
r
e
A
l
l
n
o
d
e
s
c
a
n
b
e
m
o
b
i
l
e
a
n
d
c
a
n
b
e
r
o
u
t
e
r
s
A
r
b
i
t
r
a
r
y
a
n
d
d
y
n
a
m
i
c
a
l
l
y
c
h
a
n
g
i
n
g
n
e
t
w
o
r
k
t
o
p
o
l
o
g
y
W
h
y
A
r
e
M
o
b
i
l
e
A
d
-
H
o
c
N
e
t
w
o
r
k
s
I
m
p
o
r
t
a
n
t
?
M
i
l
i
t
a
r
y
o
p
e
r
a
t
i
o
n
s
V
e
h
i
c
u
l
a
r
n
e
t
w
o
r
k
s
a
n
d
t
e
l
e
m
a
t
i
c
s
a
p
p
l
i
c
a
t
i
o
n
s
E
m
e
r
g
e
n
c
y
s
e
a
r
c
h
a
n
d
r
e
s
c
u
e
o
p
e
r
a
t
i
o
n
s
S
c
i
e
n
t
i
f
i
c
e
x
p
l
o
r
a
t
i
o
n
s
M
e
e
t
i
n
g
s
a
n
d
c
o
n
f
e
r
e
n
c
e
s
…
…
…
.
.
K
e
y
T
e
c
h
n
i
c
a
l
I
s
s
u
e
s
H
o
w
t
o
r
o
u
t
e
i
n
m
o
b
i
l
e
a
d
-
h
o
c
n
e
t
w
o
r
k
s
?
H
o
w
t
o
s
e
c
u
r
e
a
n
m
o
b
i
l
e
a
d
-
h
o
c
n
e
t
w
o
r
k
a
n
d
c
o
m
m
u
n
i
c
a
t
i
o
n
s
o
v
e
r
i
t
?
H
i
g
h
s
p
e
e
d
p
r
o
t
o
c
o
l
s
p
r
o
c
e
s
s
n
e
e
d
e
d
f
o
r
s
o
m
e
k
e
y
a
p
p
l
i
c
a
t
i
o
n
s
(
i
.
e
.
v
e
h
i
c
u
l
a
r
t
e
l
e
m
a
t
i
c
s
,
h
i
g
h
s
p
e
e
d
r
a
i
l
w
a
y
(
H
S
R
)
)
H
o
w
t
o
c
o
n
s
e
r
v
e
e
n
e
r
g
y
?
–
Nodes in mobile ad-hoc networks are likely to be energy-constrained
M
i
l
i
t
a
r
y
M
o
b
i
l
e
A
d
-
H
o
c
N
e
t
w
o
r
k
I
l
l
u
s
t
r
a
t
i
o
n
W
h
a
t
M
a
k
e
s
A
d
-
H
o
c
R
o
u
t
i
n
g
D
i
f
f
i
c
u
l
t
F
r
e
q
u
e
n
t
n
o
d
e
m
o
v
e
m
e
n
t
s
l
e
a
d
t
o
f
r
e
q
u
e
n
t
c
h
a
n
g
e
s
o
f
n
e
t
w
o
r
k
t
o
p
o
l
o
g
y
E
n
e
r
g
y
-
c
o
n
s
t
r
a
i
n
e
d
n
o
d
e
s
L
a
r
g
e
n
u
m
b
e
r
o
f
n
o
d
e
s
F
a
s
t
m
o
v
i
n
g
n
o
d
e
s
(
e
.
g
.
,
a
i
r
p
l
a
n
e
s
,
c
a
r
s
,
H
S
R
,
e
t
c
)
Routing protocols designed for the Internet
were designed for relatively stable networks
and cannot handle the dynamic changes in ad-hoc networks
D
e
s
i
r
a
b
l
e
C
h
a
r
a
c
t
e
r
i
s
t
i
c
s
o
f
A
d
-
H
o
c
R
o
u
t
i
n
g
D
i
s
t
r
i
b
u
t
e
d
o
p
e
r
a
t
i
o
n
s
L
o
o
p
f
r
e
e
S
c
a
l
a
b
l
e
E
n
e
r
g
y
c
o
n
s
e
r
v
a
t
i
v
e
R
a
p
i
d
c
o
n
v
e
r
g
e
n
c
e
S
e
c
u
r
i
t
y
a
n
d
p
r
i
v
a
c
y
p
r
e
s
e
r
v
i
n
g
H
o
w
i
s
R
o
u
t
i
n
g
D
o
n
e
i
n
I
P
N
e
t
w
o
r
k
s
?
K
e
y
m
e
t
h
o
d
s
–
Link state routing
OSPF – Open Shortest Path First
–
Distance vector routing
RIP – Routing Information Protocol
BGP – Border Gateway Protocol
H
o
w
t
o
s
c
a
l
e
t
o
l
a
r
g
e
n
e
t
w
o
r
k
s
?
–
Hierarchical Routing
Divide network into domains
Different protocols for intra-domain routing (OSPF, RIP) and inter-domain
routing (BGP)
–
Hierarchical IP addresses
–
Private addresses (NAT – Network Address Translation)
U
s
i
n
g
E
x
i
s
t
i
n
g
I
P
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
s
f
o
r
A
d
-
H
o
c
N
e
t
w
o
r
k
s
?
T
h
e
y
a
r
e
n
o
t
d
e
s
i
g
n
e
d
t
o
h
a
n
d
l
e
f
r
e
q
u
e
n
t
c
h
a
n
g
e
s
i
n
t
h
e
n
e
t
w
o
r
k
D
o
n
’
t
s
c
a
l
e
w
e
l
l
e
n
o
u
g
h
B
u
t
,
s
o
m
e
b
a
s
i
c
i
d
e
a
s
c
a
n
b
e
u
s
e
d
o
r
e
n
h
a
n
c
e
d
t
o
f
i
t
t
h
e
a
d
-
h
o
c
n
e
t
w
o
r
k
A
F
u
n
d
a
m
e
n
t
a
l
A
l
g
o
r
i
t
h
m
B
e
h
i
n
d
M
a
n
y
A
d
-
H
o
c
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
s
:
B
e
l
l
m
a
n
-
F
o
r
d
R
o
u
t
i
n
g
A
l
g
o
r
i
t
h
m
B
e
l
l
m
a
n
-
F
o
r
d
R
o
u
t
i
n
g
A
l
g
o
r
i
t
h
m
A
d
i
s
t
a
n
c
e
-
v
e
c
t
o
r
r
o
u
t
i
n
g
a
l
g
o
r
i
t
h
m
I
n
i
t
i
a
l
l
y
d
e
s
i
g
n
e
d
i
n
1
9
5
7
C
u
r
r
e
n
t
l
y
u
s
e
d
i
n
m
a
n
y
p
o
p
u
l
a
r
I
n
t
e
r
n
e
t
r
o
u
t
i
n
g
p
r
o
t
o
c
o
l
s
–
ARPANET (Advanced Research Projects Agency Network,
US DoD), the origin of the Internet
–
RIP (Routing Information Protocol)
–
BGP (Border Gateway Protocol)
–
NOVELL IPX
F
o
u
n
d
a
t
i
o
n
f
o
r
m
a
n
y
a
d
-
h
o
c
r
o
u
t
i
n
g
p
r
o
t
o
c
o
l
s
B
e
l
l
m
a
n
-
F
o
r
d
R
o
u
t
i
n
g
A
l
g
o
r
i
t
h
m
K
e
y
C
h
a
r
a
c
t
e
r
i
s
t
i
c
s
D
i
s
t
r
i
b
u
t
e
d
a
l
g
o
r
i
t
h
m
–
Each node exchanges routing information with its directly attached
neighbors and makes its own routing decisions
I
t
e
r
a
t
i
v
e
–
Routing information exchange continues until no new information is
exchanged between the neighborhood.
A
s
y
n
c
h
r
o
n
o
u
s
–
Do not require all nodes to operate in lock step with each other
B
e
l
l
m
a
n
-
F
o
r
d
R
o
u
t
i
n
g
A
l
g
o
r
i
t
h
m
H
o
w
I
t
W
o
r
k
s
E
a
c
h
r
o
u
t
e
r
m
a
i
n
t
a
i
n
s
a
d
i
s
t
a
n
c
e
t
a
b
l
e
,
w
h
i
c
h
i
s
a
o
n
e
-
d
i
m
e
n
s
i
o
n
a
l
a
r
r
a
y
,
h
e
n
c
e
t
h
e
t
e
r
m
“
d
i
s
t
a
n
c
e
v
e
c
t
o
r
“
D
i
s
t
a
n
c
e
t
a
b
l
e
m
a
i
n
t
a
i
n
s
t
h
e
“
d
i
s
t
a
n
c
e
”
a
n
d
t
h
e
s
h
o
r
t
e
s
t
p
a
t
h
t
o
e
a
c
h
n
o
d
e
i
n
t
h
e
n
e
t
w
o
r
k
.
“
D
i
s
t
a
n
c
e
”
c
a
n
b
e
h
o
p
-
c
o
u
n
t
d
i
s
t
a
n
c
e
o
r
t
i
m
e
i
t
t
a
k
e
s
t
o
t
r
a
n
s
m
i
t
a
p
a
c
k
e
t
t
o
t
h
e
d
e
s
t
i
n
a
t
i
o
n
–
Referred to generally as "
cost
“
A
s
s
u
m
p
t
i
o
n
:
E
a
c
h
n
o
d
e
k
n
o
w
s
t
h
e
c
o
s
t
o
f
t
h
e
l
i
n
k
t
o
e
a
c
h
o
f
i
t
s
d
i
r
e
c
t
l
y
c
o
n
n
e
c
t
e
d
n
e
i
g
h
b
o
r
s
.
Destination Node
Neighbor on shortest
path to Destination
Distance (Cost of Path)
to Destination
B
e
l
l
m
a
n
-
F
o
r
d
A
l
g
o
r
i
t
h
m
H
o
w
I
t
W
o
r
k
s
E
v
e
r
y
n
o
d
e
s
e
n
d
s
r
o
u
t
i
n
g
u
p
d
a
t
e
m
e
s
s
a
g
e
s
t
o
i
t
s
d
i
r
e
c
t
l
y
c
o
n
n
e
c
t
e
d
n
e
i
g
h
b
o
r
s
c
o
n
t
a
i
n
i
n
g
i
t
s
o
w
n
d
i
s
t
a
n
c
e
t
a
b
l
e
–
Upon first joining the network or change of the distance table
E
v
e
r
y
n
o
d
e
u
p
d
a
t
e
s
i
t
s
d
i
s
t
a
n
c
e
t
a
b
l
e
w
i
t
h
c
o
s
t
a
n
d
n
e
x
t
h
o
p
s
l
e
a
r
n
e
d
f
r
o
m
i
t
s
n
e
i
g
h
b
o
r
s
R
e
p
e
a
t
r
o
u
t
i
n
g
t
a
b
l
e
e
x
c
h
a
n
g
e
u
n
t
i
l
n
o
m
o
r
e
n
e
w
i
n
f
o
r
m
a
t
i
o
n
b
e
t
w
e
e
n
t
h
e
n
e
i
g
h
b
o
r
s
.
B
e
l
l
m
a
n
-
F
o
r
d
A
l
g
o
r
i
t
h
m
H
o
w
I
t
W
o
r
k
s
N
o
d
e
X
k
n
o
w
s
C
(
X
,
Z
j
)
f
o
r
e
v
e
r
y
n
e
i
g
h
b
o
r
Z
j
N
o
d
e
X
c
a
n
l
e
a
r
n
C
(
Z
j
,
Y
)
f
r
o
m
r
o
u
t
e
u
p
d
a
t
e
s
f
r
o
m
e
a
c
h
n
e
i
g
h
b
o
r
Z
j
.
N
o
d
e
X
c
a
n
c
o
m
p
u
t
e
D
(
X
,
Y
)
b
a
s
e
d
o
n
C
(
Z
j
,
Y
)
f
o
r
e
v
e
r
y
n
e
i
g
h
b
o
r
Z
j
,
a
n
d
C
(
X
,
Z
j
)
B
e
l
l
m
a
n
-
F
o
r
d
A
l
g
o
r
i
t
h
m
P
o
t
e
n
t
i
a
l
P
r
o
b
l
e
m
s
:
C
o
u
n
t
i
n
g
t
o
I
n
f
i
n
i
t
y
R
o
u
t
i
n
g
u
p
d
a
t
e
B
e
l
l
m
a
n
-
F
o
r
d
A
l
g
o
r
i
t
h
m
S
o
l
v
i
n
g
t
h
e
C
o
u
n
t
i
n
g
-
t
o
-
I
n
f
i
n
i
t
y
P
r
o
b
l
e
m
S
p
l
i
t
H
o
r
i
z
o
n
–
If you learn a route on an interface, do not send information about
that route back out that interface.
–
Split Horizon eliminates routing loops with only two nodes. It is not
effective in eliminating loops that involves more than two nodes
M
a
k
e
t
h
e
i
n
f
i
n
i
t
y
f
i
n
i
t
e
–
Specify a maximum distance vector metric as infinity
H
o
l
d
D
o
w
n
T
i
m
e
r
s
o
r
H
o
l
d
d
o
w
n
–
Hold downs are ways to try to eliminate larger routing loops.
–
When a node eliminates a node from its routing table, it initiates a
hold downs so no new entries can be accepted for that node for a
specific period of time. This helps to keep that node from being a
member of the loop.
E
x
i
s
t
i
n
g
A
d
-
H
o
c
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
s
P
r
e
-
C
o
m
p
u
t
e
d
(
T
a
b
l
e
-
D
r
i
v
e
n
)
R
o
u
t
i
n
g
–
Proactive routing
where every node maintains up-to-date and
consistent routes to every other node
O
n
-
D
e
m
a
n
d
R
o
u
t
i
n
g
–
Reactive routing
that discovers a route only when needed
P
r
o
b
a
b
i
l
i
s
t
i
c
/
O
p
p
o
r
t
u
n
i
s
t
i
c
R
o
u
t
i
n
g
–
Take advantage of the randomness
of the network to route packets
to further increase scalability
L
o
c
a
t
i
o
n
-
A
d
d
e
d
R
o
u
t
i
n
g
–
Use location of the destination to route the traffic
P
r
e
-
C
o
m
p
u
t
e
d
A
d
-
H
o
c
R
o
u
t
i
n
g
E
a
c
h
n
o
d
e
m
a
i
n
t
a
i
n
s
r
o
u
t
i
n
g
t
a
b
l
e
s
t
o
s
t
o
r
e
u
p
-
t
o
-
d
a
t
e
a
n
d
c
o
n
s
i
s
t
e
n
t
r
o
u
t
e
s
t
o
e
a
c
h
d
e
s
t
i
n
a
t
i
o
n
N
o
d
e
s
r
e
s
p
o
n
d
t
o
c
h
a
n
g
e
s
i
n
n
e
t
w
o
r
k
t
o
p
o
l
o
g
y
b
y
p
r
o
p
a
g
a
t
i
n
g
r
o
u
t
i
n
g
u
p
d
a
t
e
m
e
s
s
a
g
e
s
t
h
r
o
u
g
h
o
u
t
t
h
e
n
e
t
w
o
r
k
E
x
i
s
t
i
n
g
t
a
b
l
e
-
d
r
i
v
e
n
r
o
u
t
i
n
g
p
r
o
t
o
c
o
l
s
d
i
f
f
e
r
p
r
i
m
a
r
i
l
y
i
n
h
o
w
c
h
a
n
g
e
s
i
n
n
e
t
w
o
r
k
t
o
p
o
l
o
g
y
a
r
e
p
r
o
p
a
g
a
t
e
d
o
v
e
r
t
h
e
n
e
t
w
o
r
k
F
l
a
t
r
o
u
t
i
n
g
–
Requires each node to maintain a routing table containing all other
nodes in the network
H
i
e
r
a
r
c
h
i
c
a
l
r
o
u
t
i
n
g
–
Organizes nodes into a hierarchy of clusters
S
a
m
p
l
e
P
r
e
-
C
o
m
p
u
t
e
d
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
s
F
l
a
t
t
a
b
l
e
-
d
r
i
v
e
n
r
o
u
t
i
n
g
p
r
o
t
o
c
o
l
s
–
Dynamic
D
estination-
S
equenced
D
istance-
V
ector Routing Protocol
(DSDV)
–
Wireless Routing Protocol (WRP)
–
Global State Routing (GSR)
–
Fisheye State Routing (FSR)
–
………
H
i
e
r
a
r
c
h
i
c
a
l
t
a
b
l
e
-
d
r
i
v
e
n
r
o
u
t
i
n
g
–
Hierarchical State Routing (HSR)
–
Zone-based Hierarchical Link State Routing (ZLSR)
–
Dynamic Source Routing Protocol
–
………
D
y
n
a
m
i
c
D
e
s
t
i
n
a
t
i
o
n
-
S
e
q
u
e
n
c
e
d
D
i
s
t
a
n
c
e
-
V
e
c
t
o
r
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
D
S
D
V
)
B
a
s
e
d
o
n
B
e
l
l
m
a
n
-
F
o
r
d
D
i
s
t
a
n
c
e
-
V
e
c
t
o
r
R
o
u
t
i
n
g
A
l
g
o
r
i
t
h
m
E
a
c
h
n
o
d
e
m
a
i
n
t
a
i
n
s
a
R
o
u
t
i
n
g
T
a
b
l
e
,
w
h
i
c
h
c
o
n
t
a
i
n
s
–
All available destinations
–
Number of hops to reach the destination
–
Sequence number
assigned by the destination node
used to avoid
routing loops
D
e
s
t
i
n
a
t
i
o
n
1
H
o
p
c
o
u
n
t
s
t
o
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
1
D
e
s
t
i
n
a
t
i
o
n
2
H
o
p
c
o
u
n
t
s
t
o
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
2
K
e
y
d
i
f
f
e
r
e
n
c
e
f
r
o
m
c
l
a
s
s
i
c
a
l
B
e
l
l
m
a
n
-
F
o
r
d
p
r
o
t
o
c
o
l
D
y
n
a
m
i
c
D
e
s
t
i
n
a
t
i
o
n
-
S
e
q
u
e
n
c
e
d
D
i
s
t
a
n
c
e
-
V
e
c
t
o
r
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
D
S
D
V
)
E
a
c
h
n
o
d
e
s
e
n
d
s
r
o
u
t
e
u
p
d
a
t
e
p
a
c
k
e
t
s
t
o
i
t
s
n
e
i
g
h
b
o
r
s
p
e
r
i
o
d
i
c
a
l
l
y
a
n
d
a
l
s
o
w
h
e
n
t
h
e
i
r
r
o
u
t
i
n
g
t
a
b
l
e
s
c
h
a
n
g
e
s
i
g
n
i
f
i
c
a
n
t
l
y
–
Route update packet may carry the full routing table update or only an
incremental update
E
a
c
h
r
o
u
t
e
u
p
d
a
t
e
p
a
c
k
e
t
c
o
n
t
a
i
n
s
–
Address of known destinations
–
# of hops to each destination
–
A unique
sequence number
assigned by the originator for the route to the
destination.
R
o
u
t
e
w
i
t
h
t
h
e
h
i
g
h
e
s
t
(
i
.
e
.
m
o
s
t
r
e
c
e
n
t
)
s
e
q
u
e
n
c
e
n
u
m
b
e
r
i
s
u
s
e
d
.
I
f
t
w
o
r
o
u
t
e
s
h
a
v
e
a
n
i
d
e
n
t
i
c
a
l
s
e
q
u
e
n
c
e
n
u
m
b
e
r
,
t
h
e
r
o
u
t
e
w
i
t
h
t
h
e
b
e
s
t
m
e
t
r
i
c
(
i
.
e
.
s
h
o
r
t
e
s
t
r
o
u
t
e
)
i
s
u
s
e
d
D
y
n
a
m
i
c
D
e
s
t
i
n
a
t
i
o
n
-
S
e
q
u
e
n
c
e
d
D
i
s
t
a
n
c
e
-
V
e
c
t
o
r
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
D
S
D
V
)
X
Y
A
B
R
o
u
t
e
U
p
d
a
t
e
(
Y
,
H
o
p
c
o
u
n
t
t
o
d
i
s
t
a
n
c
e
=
2
,
S
e
q
.
#
=
1
)
R
o
u
t
e
u
s
e
d
b
y
X
f
o
r
d
e
s
t
i
n
a
t
i
o
n
Y
(
s
e
q
u
e
n
c
e
#
=
1
)
X
Y
A
R
o
u
t
e
U
p
d
a
t
e
(
Y
,
H
o
p
c
o
u
n
t
t
o
d
i
s
t
a
n
c
e
=
1
,
S
e
q
.
#
=
2
)
R
o
u
t
e
u
s
e
d
b
y
X
f
o
r
d
e
s
t
i
n
a
t
i
o
n
Y
(
s
e
q
u
e
n
c
e
#
=
2
)
W
i
r
e
l
e
s
s
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
W
R
P
)
(
1
/
7
)
A
n
o
t
h
e
r
d
i
s
t
a
n
c
e
-
v
e
c
t
o
r
r
o
u
t
i
n
g
p
r
o
t
o
c
o
l
E
a
c
h
n
o
d
e
m
a
i
n
t
a
i
n
4
t
a
b
l
e
s
–
Distance Table
–
Routing Table
–
Link-Cost Table
–
Message Retransmission List
W
i
r
e
l
e
s
s
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
W
A
P
)
(
2
/
7
)
D
i
s
t
a
n
c
e
T
a
b
l
e
D
i
s
t
a
n
c
e
t
o
e
a
c
h
d
e
s
t
i
n
a
t
i
o
n
v
i
a
e
a
c
h
n
e
i
g
h
b
o
r
T
h
e
d
o
w
n
s
t
r
e
a
m
n
e
i
g
h
b
o
r
o
f
e
a
c
h
n
e
i
g
h
b
o
r
t
h
r
o
u
g
h
w
h
i
c
h
a
p
a
t
h
i
s
r
e
a
l
i
z
e
d
X
Y
A
B
D
e
s
t
i
n
a
t
i
o
n
H
o
p
-
C
o
u
n
t
D
i
s
t
a
n
c
e
t
o
D
e
s
t
i
n
a
t
i
o
n
N
o
d
e
X
r
e
m
e
m
b
e
r
s
a
2
-
h
o
p
p
a
t
h
t
o
w
a
r
d
d
e
s
t
i
n
a
t
i
o
n
W
i
r
e
l
e
s
s
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
W
A
P
)
(
3
/
7
)
R
o
u
t
i
n
g
T
a
b
l
e
D
i
s
t
a
n
c
e
t
o
e
a
c
h
d
e
s
t
i
n
a
t
i
o
n
n
o
d
e
,
P
r
e
d
e
c
e
s
s
o
r
n
o
d
e
a
n
d
s
u
c
c
e
s
s
o
r
n
o
d
e
f
o
r
e
a
c
h
p
a
t
h
A
t
a
g
t
o
i
d
e
n
t
i
f
y
i
f
t
h
e
r
o
u
t
i
n
g
e
n
t
r
y
i
s
a
s
i
m
p
l
e
p
a
t
h
,
a
l
o
o
p
,
o
r
i
n
v
a
l
i
d
.
A
Y
X
B
D
e
s
t
i
n
a
t
i
o
n
Y
S
u
c
c
e
s
s
o
r
=
A
P
r
e
d
e
c
e
s
s
o
r
=
B
D
i
s
t
a
n
c
e
=
2
N
o
d
e
X
’
s
R
o
u
t
i
n
g
T
a
b
l
e
T
a
g
W
i
r
e
l
e
s
s
R
o
u
t
i
n
g
p
r
o
t
o
c
o
l
(
W
A
P
)
(
4
/
7
)
U
s
i
n
g
P
r
e
d
e
c
e
s
s
o
r
I
n
f
o
t
o
A
v
o
i
d
L
o
o
p
s
A
B
C
X
C
o
n
v
e
r
g
e
d
S
t
a
b
l
e
C
o
n
d
i
t
i
o
n
A
B
C
X
X
3
B
R
o
u
t
i
n
g
u
p
d
a
t
e
C
Destination
Distance
Next Hop
Predecessor
B
k
n
o
w
s
f
r
o
m
t
h
e
s
u
c
c
e
s
s
o
r
i
n
f
o
i
t
h
a
s
a
n
d
t
h
e
p
r
e
d
e
c
e
s
s
o
r
i
n
t
h
e
r
o
u
t
e
u
p
d
a
t
e
t
h
a
t
t
h
e
r
o
u
t
e
i
n
t
h
i
s
u
p
d
a
t
e
I
s
n
o
t
v
a
l
i
d
W
i
r
e
l
e
s
s
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
W
A
P
)
(
5
/
7
)
L
i
n
k
C
o
s
t
T
a
b
l
e
a
n
d
M
e
s
s
a
g
e
R
e
t
r
a
n
s
m
i
s
s
i
o
n
L
i
s
t
L
i
n
k
C
o
s
t
T
a
b
l
e
–
Cost of link to each neighboring node
–
The number of timeouts since an error-free message was received
from that neighbor
M
e
s
s
a
g
e
R
e
t
r
a
n
s
m
i
s
s
i
o
n
L
i
s
t
(
M
R
L
)
c
o
n
t
a
i
n
s
–
Information to let a node know which of its neighbor has not
acknowledged its update message and to retransmit update
message to that neighbor.
W
i
r
e
l
e
s
s
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
W
A
P
)
(
6
/
7
)
R
o
u
t
i
n
g
T
a
b
l
e
U
p
d
a
t
e
N
o
d
e
s
e
n
d
s
r
o
u
t
i
n
g
u
p
d
a
t
e
s
t
o
i
t
s
n
e
i
g
h
b
o
r
s
p
e
r
i
o
d
i
c
a
l
l
y
,
a
n
d
u
p
o
n
r
o
u
t
e
c
h
a
n
g
e
s
–
Route may change when a neighbor moves away or when the node receives
routing updates from its neighbors indicating new routes
–
If there is no change in routing table since last update, the node is required
to send an idle Hello message to ensure connectivity
–
Nodes learn the existence of neighbors from receipt of ACKs and other
messages
A
n
r
o
u
t
e
u
p
d
a
t
e
m
e
s
s
a
g
e
c
o
n
t
a
i
n
s
–
A list of updates: destination, distance to destination, predecessor node of
destination
–
A response list indicating which neighbors should acknowledge the update
U
p
o
n
r
e
c
e
i
v
i
n
g
a
n
r
o
u
t
e
u
p
d
a
t
e
m
e
s
s
a
g
e
,
a
n
o
d
e
m
o
d
i
f
i
e
s
i
t
s
t
a
b
l
e
s
a
n
d
l
o
o
k
s
f
o
r
b
e
t
t
e
r
p
a
t
h
s
u
s
i
n
g
n
e
w
i
n
f
o
r
m
a
t
i
o
n
.
W
i
r
e
l
e
s
s
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
W
A
P
)
(
7
/
7
)
R
o
u
t
i
n
g
T
a
b
l
e
U
p
d
a
t
e
A
n
y
n
e
w
p
a
t
h
i
s
r
e
l
a
y
e
d
b
a
c
k
t
o
t
h
e
o
r
i
g
i
n
a
l
n
o
d
e
s
s
o
t
h
a
t
t
h
e
y
c
a
n
u
p
d
a
t
e
t
h
e
i
r
t
a
b
l
e
s
.
T
h
e
n
o
d
e
u
p
d
a
t
e
s
i
t
s
r
o
u
t
i
n
g
t
a
b
l
e
i
f
t
h
e
n
e
w
p
a
t
h
i
s
b
e
t
t
e
r
t
h
a
n
t
h
e
e
x
i
s
t
i
n
g
p
a
t
h
.
U
p
o
n
r
e
c
e
i
v
i
n
g
a
n
A
C
K
,
t
h
e
n
o
d
e
u
p
d
a
t
e
s
i
t
s
M
e
s
s
a
g
e
R
e
t
r
a
n
s
m
i
s
s
i
o
n
L
i
s
t
.
N
o
d
e
c
h
e
c
k
s
t
h
e
c
o
n
s
i
s
t
e
n
c
y
o
f
t
h
e
i
n
f
o
r
m
a
t
i
o
n
r
e
p
o
r
t
e
d
o
n
t
h
e
p
r
e
d
e
c
e
s
s
o
r
s
b
y
a
l
l
i
t
s
n
e
i
g
h
b
o
r
s
e
v
e
r
y
t
i
m
e
i
t
d
e
t
e
c
t
s
a
c
h
a
n
g
e
i
n
l
i
n
k
o
f
a
n
y
o
f
i
t
s
n
e
i
g
h
b
o
r
s
.
T
h
i
s
h
e
l
p
s
e
l
i
m
i
n
a
t
e
l
o
o
p
s
a
n
d
e
n
a
b
l
e
f
a
s
t
c
o
n
v
e
r
g
e
n
c
e
.
G
l
o
b
a
l
S
t
a
t
e
R
o
u
t
i
n
g
(
G
S
R
)
A
l
i
n
k
-
s
t
a
t
e
r
o
u
t
i
n
g
p
r
o
t
o
c
o
l
E
a
c
h
n
o
d
e
m
a
i
n
t
a
i
n
s
4
t
a
b
l
e
s
–
Neighbor List
: Contains all neighbor nodes
–
Topology Table:
Contains the link state information as reported by
the destination and the timestamp of the information for each
destination
–
Next Hop Table:
Contains the next hop toward each destination
–
Distance Table
: Contains the shortest distance to each destination.
F
i
s
h
e
y
e
S
t
a
t
e
R
o
u
t
i
n
g
(
F
S
R
)
F
S
R
i
s
a
n
i
m
p
r
o
v
e
m
e
n
t
o
f
G
l
o
b
a
l
S
t
a
t
e
R
o
u
t
i
n
g
(
G
S
R
)
t
o
r
e
d
u
c
e
t
h
e
s
t
a
t
e
u
p
d
a
t
e
m
e
s
s
a
g
e
s
I
s
s
u
e
s
a
d
d
r
e
s
s
e
d
–
Update messages in GSR can be large and hence can waste a considerable
amount of network bandwidth.
S
o
l
u
t
i
o
n
i
n
F
S
R
–
Each update message does not contain information about all nodes. Instead,
it exchanges information about closer nodes more frequently than it does
about farther nodes thus reducing the update message size.
–
So each node gets accurate information about neighbors and the detail and
accuracy of information decreases as the distance from node increases.
–
Packets can be routed correctly because the route information becomes
more and more accurate as the packet moves closer to the destination.
H
i
e
r
a
r
c
h
i
c
a
l
S
t
a
t
e
R
o
u
t
i
n
g
(
H
S
R
)
N
e
t
w
o
r
k
i
s
d
i
v
i
d
e
d
i
n
t
o
c
l
u
s
t
e
r
s
o
f
n
o
d
e
s
E
a
c
h
e
l
e
c
t
s
a
c
l
u
s
t
e
r
h
e
a
d
a
s
i
n
a
c
l
u
s
t
e
r
-
b
a
s
e
d
r
o
u
t
i
n
g
a
l
g
o
r
i
t
h
m
C
l
u
s
t
e
r
h
e
a
d
s
o
r
g
a
n
i
z
e
t
h
e
m
s
e
l
v
e
s
i
n
t
o
c
l
u
s
t
e
r
s
a
n
d
s
o
o
n
.
N
o
d
e
s
i
n
a
c
l
u
s
t
e
r
b
r
o
a
d
c
a
s
t
t
h
e
i
r
l
i
n
k
i
n
f
o
r
m
a
t
i
o
n
t
o
e
a
c
h
o
t
h
e
r
E
a
c
h
c
l
u
s
t
e
r
h
e
a
d
s
u
m
m
a
r
i
z
e
s
i
t
s
c
l
u
s
t
e
r
'
s
i
n
f
o
r
m
a
t
i
o
n
a
n
d
s
e
n
d
s
i
t
t
o
n
e
i
g
h
b
o
r
i
n
g
c
l
u
s
t
e
r
h
e
a
d
s
v
i
a
g
a
t
e
w
a
y
s
A
n
o
d
e
a
t
e
a
c
h
l
e
v
e
l
f
l
o
o
d
s
t
o
i
t
s
l
o
w
e
r
l
e
v
e
l
t
h
e
i
n
f
o
r
m
a
t
i
o
n
t
h
a
t
i
t
o
b
t
a
i
n
s
s
o
t
h
e
l
o
w
e
r
l
e
v
e
l
h
a
s
a
h
i
e
r
a
r
c
h
i
c
a
l
t
o
p
o
l
o
g
y
i
n
f
o
r
m
a
t
i
o
n
.
E
a
c
h
n
o
d
e
h
a
s
a
h
i
e
r
a
r
c
h
i
c
a
l
a
d
d
r
e
s
s
R
o
u
t
i
n
g
H
i
e
r
a
r
c
h
y
i
n
H
S
R
V
i
r
t
u
a
l
N
o
d
e
s
G
a
t
e
w
a
y
s
C
l
u
s
t
e
r
P
h
y
s
i
c
a
l
N
o
d
e
s
C
l
u
s
t
e
r
H
e
a
d
C
l
u
s
t
e
r
H
e
a
d
C
l
u
s
t
e
r
H
e
a
d
C
l
u
s
t
e
r
H
e
a
d
C
l
u
s
t
e
r
H
e
a
d
V
i
r
t
u
a
l
L
i
n
k
P
h
y
s
i
c
a
l
L
i
n
k
X
X
.
1
X
.
2
X
.
2
.
1
X
.
2
.
2
X
.
2
.
3
Z
o
n
e
-
b
a
s
e
d
H
i
e
r
a
r
c
h
i
c
a
l
L
i
n
k
S
t
a
t
e
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
Z
H
L
S
)
(
1
/
2
)
T
h
e
n
e
t
w
o
r
k
i
s
d
i
v
i
d
e
d
i
n
t
o
n
o
n
-
o
v
e
r
l
a
p
p
i
n
g
z
o
n
e
s
N
o
z
o
n
e
h
e
a
d
i
s
n
e
e
d
e
d
b
e
t
t
e
r
s
c
a
l
a
b
i
l
i
t
y
U
s
e
s
2
l
e
v
e
l
s
o
f
t
o
p
o
l
o
g
i
e
s
:
n
o
d
e
l
e
v
e
l
a
n
d
z
o
n
e
l
e
v
e
l
U
s
e
2
t
y
p
e
s
o
f
L
i
n
k
S
t
a
t
e
P
a
c
k
e
t
s
(
L
S
P
)
–
Node LSP
contains information on a node’s physical neighbors and
is propagated within the zone
–
Zone LSP
contains the zone information and is propagated globally
so that each node has full node connectivity knowledge about the
nodes in its zone and only zone connectivity information about other
zones.
Z
o
n
e
-
b
a
s
e
d
H
i
e
r
a
r
c
h
i
c
a
l
L
i
n
k
S
t
a
t
e
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
Z
H
L
S
)
(
2
/
2
)
N
o
d
e
s
a
n
d
z
o
n
e
s
a
r
e
i
d
e
n
t
i
f
i
e
d
b
y
N
o
d
e
I
D
s
a
n
d
Z
o
n
e
I
D
s
P
a
c
k
e
t
r
o
u
t
i
n
g
–
A packet is routed first based on the Zone ID to the destination
zone.
–
The, within the destination zone, the packet is routed based on the
destination’s Node ID
O
n
-
D
e
m
a
n
d
A
d
-
H
o
c
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
s
D
i
s
c
o
v
e
r
s
a
r
o
u
t
e
o
n
l
y
w
h
e
n
n
e
e
d
e
d
,
b
y
f
l
o
o
d
i
n
g
a
q
u
e
r
y
t
o
a
l
l
n
o
d
e
s
E
a
c
h
q
u
e
r
y
p
a
c
k
e
t
r
e
m
e
m
b
e
r
s
t
h
e
i
n
t
e
r
m
e
d
i
a
t
e
n
o
d
e
s
i
t
t
r
a
v
e
r
s
e
s
D
e
s
t
i
n
a
t
i
o
n
,
o
r
n
o
d
e
s
t
h
a
t
k
n
o
w
h
o
w
t
o
r
e
a
c
h
t
h
e
d
e
s
t
i
n
a
t
i
o
n
,
s
e
n
d
s
t
h
e
r
o
u
t
e
i
n
f
o
r
m
a
t
i
o
n
a
c
c
u
m
u
l
a
t
e
d
i
n
t
h
e
q
u
e
r
y
p
a
c
k
e
t
b
a
c
k
t
o
t
h
e
s
o
u
r
c
e
R
o
u
t
e
s
a
r
e
k
e
p
t
f
o
r
a
f
i
n
i
t
e
l
i
f
e
t
i
m
e
S
a
m
p
l
e
O
n
-
D
e
m
a
n
d
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
s
D
y
n
a
m
i
c
S
o
u
r
c
e
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
D
S
R
P
)
A
d
h
o
c
O
n
-
D
e
m
a
n
d
D
i
s
t
a
n
c
e
V
e
c
t
o
r
(
A
O
D
V
)
R
o
u
t
i
n
g
–
IETF RFC 3561
C
l
u
s
t
e
r
-
b
a
s
e
d
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
T
e
m
p
o
r
a
r
i
l
y
O
r
d
e
r
e
d
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
D
y
n
a
m
i
c
S
o
u
r
c
e
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
O
n
-
d
e
m
a
n
d
s
o
u
r
c
e
r
o
u
t
i
n
g
p
r
o
t
o
c
o
l
.
S
o
u
r
c
e
r
o
u
t
e
:
A
p
a
c
k
e
t
c
a
r
r
i
e
s
i
n
i
t
s
h
e
a
d
e
r
t
h
e
e
n
t
i
r
e
r
o
u
t
e
f
r
o
m
s
o
u
r
c
e
t
o
d
e
s
t
i
n
a
t
i
o
n
A
n
o
d
e
c
a
c
h
e
s
s
o
u
r
c
e
r
o
u
t
e
s
t
h
a
t
i
t
k
n
o
w
s
a
n
d
u
p
d
a
t
e
s
t
h
e
m
w
h
e
n
n
e
e
d
e
d
–
A node can maintain multiple routes to the same destination
N
o
p
e
r
i
o
d
i
c
r
o
u
t
i
n
g
u
p
d
a
t
e
s
H
a
s
t
w
o
m
a
j
o
r
p
h
a
s
e
s
–
Route discovery and
–
Route maintenance.
D
y
n
a
m
i
c
S
o
u
r
c
e
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
R
o
u
t
e
D
i
s
c
o
v
e
r
y
P
h
a
s
e
W
h
e
n
a
s
o
u
r
c
e
n
o
d
e
w
a
n
t
s
t
o
s
e
n
d
a
p
a
c
k
e
t
t
o
a
d
e
s
t
i
n
a
t
i
o
n
,
i
t
–
Looks up its route cache to determine if it already knows a route to
the destination.
–
If it knows an unexpired route to the destination, it uses this route to
send the packet.
–
If is does not have an existing route, it initiates the route discovery
process by broadcasting a
route request packet
T
h
e
r
o
u
t
e
r
e
q
u
e
s
t
p
a
c
k
e
t
c
o
n
t
a
i
n
s
–
Addresses of the source and the destination, and
–
A unique ID.
D
y
n
a
m
i
c
S
o
u
r
c
e
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
R
o
u
t
e
D
i
s
c
o
v
e
r
y
P
h
a
s
e
E
a
c
h
i
n
t
e
r
m
e
d
i
a
t
e
n
o
d
e
c
h
e
c
k
s
w
h
e
t
h
e
r
i
t
k
n
o
w
s
a
r
o
u
t
e
t
o
t
h
e
d
e
s
t
i
n
a
t
i
o
n
.
–
If it does not, it appends its address to the route record of the packet
and forwards the packet to its neighbors
–
If it knows a route to the destination, it sends
a
route reply message
to the source along an unicast reverse path contained in the route
request message
T
o
l
i
m
i
t
t
h
e
n
u
m
b
e
r
o
f
r
o
u
t
e
r
e
q
u
e
s
t
s
p
r
o
p
a
g
a
t
e
d
,
a
n
o
d
e
p
r
o
c
e
s
s
e
s
t
h
e
r
o
u
t
e
r
e
q
u
e
s
t
p
a
c
k
e
t
o
n
l
y
i
f
i
t
h
a
s
n
o
t
a
l
r
e
a
d
y
s
e
e
n
t
h
e
p
a
c
k
e
t
a
n
d
i
t
s
o
w
n
a
d
d
r
e
s
s
i
s
n
o
t
p
r
e
s
e
n
t
i
n
t
h
e
r
o
u
t
e
r
e
c
o
r
d
o
f
t
h
e
p
a
c
k
e
t
D
y
n
a
m
i
c
S
o
u
r
c
e
R
o
u
t
i
n
g
I
l
l
u
s
t
r
a
t
i
o
n
S
o
u
r
c
e
S
o
u
r
c
e
D
e
s
t
i
n
a
t
i
o
n
D
e
s
t
i
n
a
t
i
o
n
R
o
u
t
e
D
i
s
c
o
v
e
r
y
R
o
u
t
e
R
e
p
l
y
(
1
)
(
1
)
(
1
)
(
1
,
2
)
(
1
,
3
)
(
1
,
2
,
5
)
(
1
,
2
,
5
)
(
1
,
4
)
(
1
,
3
,
6
)
(
1
,
3
,
6
,
7
)
(
1
,
3
,
6
,
7
)
(
1
,
3
,
6
,
7
)
I
n
t
e
r
m
e
d
i
a
t
e
n
o
d
e
c
a
c
h
e
s
s
o
u
r
c
e
r
o
u
t
e
i
n
t
h
e
p
a
c
k
e
t
D
y
n
a
m
i
c
S
o
u
r
c
e
R
o
u
t
i
n
g
R
o
u
t
e
M
a
i
n
t
e
n
a
n
c
e
E
a
c
h
n
o
d
e
a
l
o
n
g
a
r
o
u
t
e
i
s
r
e
s
p
o
n
s
i
b
l
e
f
o
r
d
e
t
e
c
t
i
n
g
f
a
i
l
u
r
e
o
f
t
h
e
p
a
r
t
o
f
t
h
e
r
o
u
t
e
t
h
a
t
g
o
e
s
t
h
r
o
u
g
h
i
t
U
p
o
n
d
e
t
e
c
t
i
n
g
a
b
r
o
k
e
n
l
i
n
k
,
i
t
i
n
f
o
r
m
s
t
h
e
s
o
u
r
c
e
S
o
u
r
c
e
d
e
l
e
t
e
s
a
n
y
r
o
u
t
e
i
n
i
t
s
c
a
c
h
e
t
h
a
t
u
s
e
s
t
h
e
b
r
o
k
e
n
l
i
n
k
S
o
u
r
c
e
m
a
y
r
e
-
i
n
i
t
i
a
t
e
t
h
e
r
o
u
t
e
d
i
s
c
o
v
e
r
y
p
r
o
c
e
d
u
r
e
t
o
f
i
n
d
a
n
e
w
r
o
u
t
e
A
d
-
H
o
c
O
n
-
D
e
m
a
n
d
D
i
s
t
a
n
c
e
V
e
c
t
o
r
R
o
u
t
i
n
g
(
A
O
D
V
)
D
i
s
t
a
n
c
e
-
v
e
c
t
o
r
r
o
u
t
i
n
g
u
s
e
d
o
n
a
n
o
n
-
d
e
m
a
n
d
f
a
s
h
i
o
n
N
o
d
e
s
e
a
r
c
h
f
o
r
a
r
o
u
t
e
t
o
a
d
e
s
t
i
n
a
t
i
o
n
o
n
l
y
w
h
e
n
i
t
n
e
e
d
s
t
o
s
e
n
d
p
a
c
k
e
t
s
t
o
t
h
e
d
e
s
t
i
n
a
t
i
o
n
a
n
d
d
o
e
s
n
o
t
a
l
r
e
a
d
y
h
a
v
e
a
r
o
u
t
e
t
o
t
h
e
d
e
s
t
i
n
a
t
i
o
n
N
o
d
e
k
e
e
p
s
a
c
t
i
v
e
r
o
u
t
e
s
i
n
t
h
e
s
a
m
e
m
a
n
n
e
r
a
s
i
n
t
r
a
d
i
t
i
o
n
a
l
r
o
u
t
i
n
g
t
a
b
l
e
s
:
<
d
e
s
t
i
n
a
t
i
o
n
,
n
e
x
t
h
o
p
>
–
An active route is one over which at least one packet has
been forwarded over the past active timeout period
T
w
o
m
a
i
n
o
p
e
r
a
t
i
o
n
s
–
Route discovery
–
Route maintenance
A
O
D
V
R
o
u
t
e
D
i
s
c
o
v
e
r
y
T
o
f
i
n
d
a
r
o
u
t
e
t
o
t
h
e
d
e
s
t
i
n
a
t
i
o
n
,
t
h
e
s
o
u
r
c
e
b
r
o
a
d
c
a
s
t
s
a
R
o
u
t
e
R
e
q
u
e
s
t
p
a
c
k
e
t
t
o
a
l
l
i
t
s
n
e
i
g
h
b
o
r
s
,
w
h
i
c
h
i
n
t
u
r
n
b
r
o
a
d
c
a
s
t
t
h
e
R
o
u
t
e
R
e
q
u
e
s
t
t
o
t
h
e
i
r
n
e
i
g
h
b
o
r
s
u
n
t
i
l
t
h
e
R
o
u
t
e
R
e
q
u
e
s
t
r
e
a
c
h
e
s
–
The destination, or
–
An intermediate node that has an up-to-date route to the destination
T
o
a
v
o
i
d
r
o
u
t
e
l
o
o
p
s
,
a
n
o
d
e
d
i
s
c
a
r
d
s
a
R
o
u
t
e
R
e
q
u
e
s
t
t
h
a
t
i
t
h
a
s
a
l
r
e
a
d
y
s
e
e
n
.
–
Route Request packets identified by sequence numbers
A
O
D
V
R
o
u
t
e
D
i
s
c
o
v
e
r
y
D
e
s
t
i
n
a
t
i
o
n
o
r
a
n
i
n
t
e
r
m
e
d
i
a
t
e
n
o
d
e
w
i
t
h
a
r
o
u
t
e
t
o
t
h
e
d
e
s
t
i
n
a
t
i
o
n
u
n
i
c
a
s
t
s
a
R
o
u
t
e
R
e
p
l
y
p
a
c
k
e
t
b
a
c
k
t
o
t
h
e
s
o
u
r
c
e
a
l
o
n
g
a
r
e
s
e
r
v
e
d
i
r
e
c
t
i
o
n
o
f
t
h
e
p
a
t
h
t
r
a
v
e
l
e
d
b
y
t
h
e
R
o
u
t
e
R
e
q
u
e
s
t
T
o
c
o
n
s
t
r
u
c
t
t
h
e
r
e
v
e
r
s
e
p
a
t
h
,
a
n
o
d
e
r
e
c
o
r
d
s
t
h
e
n
e
i
g
h
b
o
r
f
r
o
m
w
h
i
c
h
t
h
e
f
i
r
s
t
c
o
p
y
o
f
e
a
c
h
R
o
u
t
e
R
e
q
u
e
s
t
c
a
m
e
A
s
t
h
e
R
o
u
t
e
R
e
p
l
y
t
r
a
v
e
l
s
b
a
c
k
t
o
t
h
e
s
o
u
r
c
e
,
t
h
e
n
o
d
e
s
a
l
o
n
g
t
h
e
w
a
y
e
n
t
e
r
t
h
e
f
o
r
w
a
r
d
r
o
u
t
e
i
n
t
o
t
h
e
i
r
r
o
u
t
i
n
g
t
a
b
l
e
s
,
f
o
r
m
i
n
g
a
f
o
r
w
a
r
d
r
o
u
t
e
f
r
o
m
t
h
e
s
o
u
r
c
e
t
o
t
h
e
d
e
s
t
i
n
a
t
i
o
n
A
O
D
V
R
o
u
t
e
D
i
s
c
o
v
e
r
y
T
o
e
n
s
u
r
e
m
o
s
t
r
e
c
e
n
t
r
o
u
t
e
i
s
u
s
e
d
a
n
d
t
o
h
e
l
p
a
v
o
i
d
r
o
u
t
i
n
g
l
o
o
p
,
A
O
D
V
u
s
e
s
a
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
W
h
e
n
t
h
e
d
e
s
t
i
n
a
t
i
o
n
s
e
n
d
s
b
a
c
k
t
h
e
R
o
u
t
e
R
e
p
l
y
p
a
c
k
e
t
,
i
t
a
s
s
i
g
n
s
a
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
t
o
t
h
e
r
o
u
t
e
a
n
d
i
n
s
e
r
t
t
h
e
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
i
n
t
h
e
R
o
u
t
e
R
e
p
l
y
.
A
s
t
h
e
R
o
u
t
e
R
e
p
l
y
t
r
a
v
e
l
s
t
o
w
a
r
d
s
t
h
e
s
o
u
r
c
e
,
e
a
c
h
n
o
d
e
a
l
o
n
g
t
h
e
w
a
y
r
e
c
o
r
d
s
t
h
e
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
f
o
r
t
h
e
r
o
u
t
e
i
n
i
t
s
r
o
u
t
i
n
g
t
a
b
l
e
a
s
i
l
l
u
s
t
r
a
t
e
d
b
e
l
o
w
D
e
s
t
i
n
a
t
i
o
n
I
P
A
d
d
r
e
s
s
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
H
o
p
C
o
u
n
t
N
e
x
t
H
o
p
L
i
f
e
t
i
m
e
A
O
D
V
R
o
u
t
e
D
i
s
c
o
v
e
r
y
I
l
l
u
s
t
r
a
t
i
o
n
S
o
u
r
c
e
S
o
u
r
c
e
D
e
s
t
i
n
a
t
i
o
n
D
e
s
t
i
n
a
t
i
o
n
R
o
u
t
e
D
i
s
c
o
v
e
r
y
R
o
u
t
e
R
e
p
l
y
R
o
u
t
e
e
s
t
a
b
l
i
s
h
m
e
n
t
I
n
t
e
r
m
e
d
i
a
t
e
n
o
d
e
c
a
c
h
e
s
t
h
e
r
o
u
t
e
t
o
s
o
u
r
c
e
A
O
D
V
:
U
s
e
o
f
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
X
Y
A
D
e
s
t
i
n
a
t
i
o
n
S
o
u
r
c
e
1
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
=
1
F
o
r
r
o
u
t
e
t
o
Y
Q
Y
A
D
e
s
t
i
n
a
t
i
o
n
S
o
u
r
c
e
2
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
=
2
F
o
r
r
o
u
t
e
t
o
Y
B
X
Y
A
D
e
s
t
i
n
a
t
i
o
n
S
o
u
r
c
e
1
D
e
s
t
i
n
a
t
i
o
n
S
e
q
u
e
n
c
e
N
u
m
b
e
r
=
2
F
o
r
r
o
u
t
e
t
o
Y
R
o
u
t
e
R
e
q
u
e
s
t
(
D
e
s
t
.
S
e
q
.
#
=
1
)
N
o
d
e
A
w
i
l
l
u
s
e
n
e
w
r
o
u
t
e
t
o
Y
t
o
r
e
s
p
o
n
d
t
o
t
h
i
s
R
o
u
t
e
R
e
q
u
e
s
t
A
O
D
V
R
o
u
t
e
M
a
i
n
t
e
n
a
n
c
e
A
r
o
u
t
e
m
a
y
b
r
e
a
k
w
h
e
n
a
n
y
n
o
d
e
a
l
o
n
g
t
h
e
r
o
u
t
e
m
o
v
e
s
a
w
a
y
I
f
t
h
e
s
o
u
r
c
e
m
o
v
e
s
–
The source can reinitiate route discovery to find a new route to the
destination.
I
f
a
n
i
n
t
e
r
m
e
d
i
a
t
e
n
o
d
e
m
o
v
e
s
–
A neighbor of the moved node detects failure of link to the moved
node and sends a link failure notification to its upstream neighbors,
which in turn informs its upstream neighbors until the notification
reaches the source
–
The source can reinitiate route discovery to find a new route to the
destination
C
l
u
s
t
e
r
-
B
a
s
e
d
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
N
o
d
e
s
a
r
e
d
i
v
i
d
e
d
i
n
t
o
c
l
u
s
t
e
r
s
.
A
l
g
o
r
i
t
h
m
f
o
r
e
s
t
a
b
l
i
s
h
i
n
g
c
l
u
s
t
e
r
s
:
–
Upon powering up, node enters "
undecided
" state, starts a timer and
broadcasts a Hello message
–
Cluster head responds to the Hello message with its own Hello
message
–
Receipt of Hello from cluster head triggers the
undecided
node to
transition its state into "
member
".
–
If the undecided node times out, then it makes itself the cluster-head
if it has bi-directional link to some neighbor; otherwise it remains in
undecided state and repeats the procedure again.
–
Cluster heads are changed as
infrequently
as possible.
C
l
u
s
t
e
r
-
B
a
s
e
d
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
E
a
c
h
n
o
d
e
m
a
i
n
t
a
i
n
s
a
n
e
i
g
h
b
o
r
t
a
b
l
e
,
c
o
n
t
a
i
n
i
n
g
–
Status of the link to each neighbor and
–
State of the neighbor (cluster-head or member).
A
c
l
u
s
t
e
r
-
h
e
a
d
m
a
i
n
t
a
i
n
s
i
n
f
o
r
m
a
t
i
o
n
a
b
o
u
t
–
All members of its cluster and
–
A cluster
adjacency table
C
l
u
s
t
e
r
a
d
j
a
c
e
n
c
y
t
a
b
l
e
c
o
n
t
a
i
n
s
t
h
e
f
o
l
l
o
w
i
n
g
i
n
f
o
r
m
a
t
i
o
n
a
b
o
u
t
e
a
c
h
n
e
i
g
h
b
o
r
i
n
g
c
l
u
s
t
e
r
:
–
Gateway through which the cluster can be reached and
–
Cluster head of the cluster.
C
l
u
s
t
e
r
-
B
a
s
e
d
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
W
h
e
n
a
s
o
u
r
c
e
h
a
s
t
o
s
e
n
d
p
a
c
k
e
t
t
o
a
d
e
s
t
i
n
a
t
i
o
n
,
i
t
s
e
n
d
s
a
r
o
u
t
e
r
e
q
u
e
s
t
p
a
c
k
e
t
t
o
i
t
s
c
l
u
s
t
e
r
h
e
a
d
U
p
o
n
r
e
c
e
i
v
i
n
g
t
h
e
r
e
q
u
e
s
t
,
a
c
l
u
s
t
e
r
-
h
e
a
d
c
h
e
c
k
s
t
o
s
e
e
i
f
t
h
e
d
e
s
t
i
n
a
t
i
o
n
i
s
i
n
i
t
s
c
l
u
s
t
e
r
–
If yes, it sends the request directly to the destination
–
Else, it sends it to all its adjacent cluster-heads.
T
h
e
r
e
q
u
e
s
t
c
o
n
t
a
i
n
s
t
h
e
c
l
u
s
t
e
r
h
e
a
d
s
’
a
d
d
r
e
s
s
e
s
(
i
.
e
.
,
s
o
u
r
c
e
r
o
u
t
i
n
g
)
s
o
a
c
l
u
s
t
e
r
h
e
a
d
d
i
s
c
a
r
d
s
a
r
e
q
u
e
s
t
p
a
c
k
e
t
t
h
a
t
i
t
h
a
s
a
l
r
e
a
d
y
s
e
e
n
.
W
h
e
n
t
h
e
d
e
s
t
i
n
a
t
i
o
n
r
e
c
e
i
v
e
s
t
h
e
r
e
q
u
e
s
t
p
a
c
k
e
t
,
i
t
r
e
p
l
i
e
s
w
i
t
h
t
h
e
r
o
u
t
e
r
e
c
o
r
d
e
d
i
n
t
h
e
r
e
q
u
e
s
t
p
a
c
k
e
t
.
I
f
t
h
e
s
o
u
r
c
e
d
o
e
s
n
o
t
r
e
c
e
i
v
e
a
r
e
p
l
y
w
i
t
h
i
n
a
t
i
m
e
p
e
r
i
o
d
,
i
t
b
a
c
k
s
o
f
f
e
x
p
o
n
e
n
t
i
a
l
l
y
b
e
f
o
r
e
t
r
y
i
n
g
t
o
r
e
-
s
e
n
d
r
o
u
t
e
r
e
q
u
e
s
t
C
l
u
s
t
e
r
-
B
a
s
e
d
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
R
o
u
t
e
s
h
o
r
t
e
n
i
n
g
t
e
c
h
n
i
q
u
e
–
Upon receiving a source route packet, the node tries to find the
farthest node in the route that is its neighbor (this could have
happened due to a topology change) and sends the packet to that
node thus reducing the route
W
h
i
l
e
f
o
r
w
a
r
d
i
n
g
t
h
e
p
a
c
k
e
t
i
f
a
n
o
d
e
d
e
t
e
c
t
s
a
b
r
o
k
e
n
l
i
n
k
i
t
s
e
n
d
s
b
a
c
k
a
n
e
r
r
o
r
m
e
s
s
a
g
e
t
o
t
h
e
s
o
u
r
c
e
a
n
d
t
h
e
n
i
n
i
t
i
a
t
e
s
l
o
c
a
l
r
e
p
a
i
r
m
e
c
h
a
n
i
s
m
L
o
c
a
l
r
e
p
a
i
r
:
w
h
e
n
a
n
o
d
e
f
i
n
d
s
t
h
e
n
e
x
t
h
o
p
i
s
u
n
r
e
a
c
h
a
b
l
e
,
i
t
c
h
e
c
k
s
t
o
s
e
e
i
f
t
h
e
n
e
x
t
h
o
p
c
a
n
b
e
r
e
a
c
h
e
d
t
h
r
o
u
g
h
a
n
y
o
f
i
t
s
n
e
i
g
h
b
o
r
o
r
i
f
t
h
e
h
o
p
a
f
t
e
r
n
e
x
t
h
o
p
c
a
n
b
e
r
e
a
c
h
e
d
t
h
r
o
u
g
h
a
n
y
o
t
h
e
r
n
e
i
g
h
b
o
r
.
I
f
a
n
y
o
f
t
h
e
t
w
o
w
o
r
k
s
,
t
h
e
p
a
c
k
e
t
c
a
n
b
e
s
e
n
t
o
u
t
o
v
e
r
t
h
e
r
e
p
a
i
r
e
d
p
a
t
h
.
S
i
g
n
a
l
S
t
a
b
i
l
i
t
y
-
B
a
s
e
d
A
d
a
p
t
i
v
e
R
o
u
t
i
n
g
P
r
o
t
o
c
o
l
(
S
S
R
)
(
1
/
4
)
O
n
-
d
e
m
a
n
d
r
o
u
t
i
n
g
t
h
a
t
s
e
l
e
c
t
s
r
o
u
t
e
s
b
a
s
e
d
o
n
t
h
e
r
a
d
i
o
s
i
g
n
a
l
s
t
r
e
n
g
t
h
b
e
t
w
e
e
n
n
o
d
e
s
,
c
h
o
o
s
i
n
g
"
s
t
r
o
n
g
e
r
"
c
o
n
n
e
c
t
i
v
i
t
y
.
U
s
e
s
t
w
o
p
r
o
t
o
c
o
l
s
–
Dynamic Routing Protocol (DRP)
–
Static Routing Protocol (SRP).
E
a
c
h
n
o
d
e
m
a
i
n
t
a
i
n
s
–
Signal Stability Table (SST) and
–
Routing Table (RT).
S
S
R
(
2
/
4
)
S
i
g
n
a
l
S
t
a
b
i
l
i
t
y
T
a
b
l
e
(
S
S
T
)
s
t
o
r
e
s
t
h
e
s
i
g
n
a
l
s
t
r
e
n
g
t
h
o
f
n
e
i
g
h
b
o
r
i
n
g
n
o
d
e
s
o
b
t
a
i
n
e
d
b
y
p
e
r
i
o
d
i
c
b
e
a
c
o
n
s
f
r
o
m
t
h
e
l
i
n
k
l
a
y
e
r
o
f
e
a
c
h
n
e
i
g
h
b
o
r
i
n
g
n
o
d
e
.
–
Signal strength is either recorded as a
strong or weak
.
–
All transmissions are received by DRP and processed.
–
After updating the appropriate table entries, the DRP passes the
packet to the SRP.
S
S
R
(
3
/
4
)
S
R
P
p
a
s
s
e
s
t
h
e
p
a
c
k
e
t
u
p
t
h
e
p
r
o
t
o
c
o
l
s
t
a
c
k
i
f
t
h
e
n
o
d
e
i
s
t
h
e
d
e
s
t
i
n
a
t
i
o
n
.
O
t
h
e
r
w
i
s
e
,
i
t
l
o
o
k
s
u
p
t
h
e
d
e
s
t
i
n
a
t
i
o
n
i
n
t
h
e
R
T
a
n
d
f
o
r
w
a
r
d
s
t
h
e
p
a
c
k
e
t
.
–
If there is no entry for the destination in the RT, it initiates a route-
search process to find a route by sending a route-search packet to
neighbors from which it received strong signals
–
The destination chooses the first arriving route-search packet to
send back as it is highly likely that this packet arrived over the
shortest or least congested path.
–
The DRP reverses the selected route and sends a route-reply
message back to the initiator of route-request.
–
The DRP of the nodes along the path update their RTs accordingly.
S
S
R
(
4
/
4
)
R
o
u
t
e
-
s
e
a
r
c
h
p
a
c
k
e
t
s
a
r
r
i
v
i
n
g
a
t
t
h
e
d
e
s
t
i
n
a
t
i
o
n
h
a
v
e
n
e
c
e
s
s
a
r
i
l
y
a
r
r
i
v
e
d
o
n
t
h
e
p
a
t
h
o
f
s
t
r
o
n
g
e
s
t
s
i
g
n
a
l
s
t
a
b
i
l
i
t
y
b
e
c
a
u
s
e
t
h
e
p
a
c
k
e
t
s
a
r
r
i
v
i
n
g
o
v
e
r
a
w
e
a
k
c
h
a
n
n
e
l
a
r
e
d
r
o
p
p
e
d
a
t
i
n
t
e
r
m
e
d
i
a
t
e
n
o
d
e
s
.
I
f
t
h
e
s
o
u
r
c
e
t
i
m
e
s
o
u
t
b
e
f
o
r
e
r
e
c
e
i
v
i
n
g
a
r
e
p
l
y
,
i
t
c
a
n
r
e
-
t
r
a
n
s
m
i
t
t
h
e
p
a
c
k
e
t
a
n
d
s
e
t
s
t
h
e
P
R
E
F
f
i
e
l
d
i
n
t
h
e
p
a
c
k
e
t
h
e
a
d
e
r
t
o
i
n
d
i
c
a
t
e
t
h
a
t
w
e
a
k
c
h
a
n
n
e
l
s
c
a
n
a
l
s
o
b
e
u
s
e
d
W
h
e
n
a
n
i
n
t
e
r
m
e
d
i
a
t
e
n
o
d
e
d
e
t
e
c
t
s
a
l
i
n
k
f
a
i
l
u
r
e
,
i
t
s
e
n
d
s
a
n
e
r
r
o
r
m
e
s
s
a
g
e
t
o
t
h
e
s
o
u
r
c
e
i
n
d
i
c
a
t
i
n
g
w
h
i
c
h
c
h
a
n
n
e
l
h
a
s
f
a
i
l
e
d
.
T
h
e
s
o
u
r
c
e
t
h
e
n
s
e
n
d
s
a
n
e
r
a
s
e
m
e
s
s
a
g
e
t
o
n
o
t
i
f
y
a
l
l
n
o
d
e
s
o
f
t
h
e
b
r
o
k
e
n
l
i
n
k
a
n
d
i
n
i
t
i
a
t
e
s
a
n
e
w
r
o
u
t
e
-
s
e
a
r
c
h
p
r
o
c
e
s
s
t
o
f
i
n
d
a
n
e
w
p
a
t
h
t
o
t
h
e
d
e
s
t
i
n
a
t
i
o
n
.
What Problems Do You See
As Important to Address and Why?
Thanks !
Mobile Ad-Hoc Networks (MANETs) pose unique challenges such as dynamic topology changes, energy constraints, and security issues. This article delves into the important problems, significance, technical issues, and routing complexities associated with MANETs, offering insights into desirable routing characteristics.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ICT Entrepreneurship for Telematics Services L2- Mobile Ad-Hoc Networks (MANETs) February 6, 2013 T. Russell Hsing, FIEEE/FBCS(UK)/FSPIE Email: thsing@ieee.org
What Problems Do You See As Important to Address and Why?
What Are Mobile Ad-Hoc Networks? No fixed network infrastructure All nodes can be mobile and can be routers Arbitrary and dynamically changing network topology
Why Are Mobile Ad-Hoc Networks Important? Military operations Vehicular networks and telematics applications Emergency search and rescue operations Scientific explorations Meetings and conferences ..
Key Technical Issues How to route in mobile ad-hoc networks? How to secure an mobile ad-hoc network and communications over it? High speed protocols process needed for some key applications (i.e. vehicular telematics, high speed railway (HSR)) How to conserve energy? Nodes in mobile ad-hoc networks are likely to be energy-constrained
Military Mobile Ad-Hoc Network Illustration Tanks%25202 Tanks%25202 Tanks%25202 Tanks%25202 soldier-allied-gurkha-borneo Tanks%25202 Tanks%25202 soldier-allied-gurkha-borneo soldier-allied-gurkha-borneo soldier-allied-gurkha-borneo
What Makes Ad-Hoc Routing Difficult Frequent node movements lead to frequent changes of network topology Energy-constrained nodes Large number of nodes Fast moving nodes (e.g., airplanes, cars, HSR,etc) Routing protocols designed for the Internet were designed for relatively stable networks and cannot handle the dynamic changes in ad-hoc networks
Desirable Characteristics of Ad-Hoc Routing Distributed operations Loop free Scalable Energy conservative Rapid convergence Security and privacy preserving
How is Routing Done in IP Networks? Key methods Link state routing OSPF Open Shortest Path First Distance vector routing RIP Routing Information Protocol BGP Border Gateway Protocol How to scale to large networks? Hierarchical Routing Divide network into domains Different protocols for intra-domain routing (OSPF, RIP) and inter-domain routing (BGP) Hierarchical IP addresses Private addresses (NAT Network Address Translation)
Using Existing IP Routing Protocols for Ad- Hoc Networks? They are not designed to handle frequent changes in the network Don t scale well enough But, some basic ideas can be used or enhanced to fit the ad-hoc network
A Fundamental Algorithm Behind Many Ad-Hoc Routing Protocols: Bellman-Ford Routing Algorithm
Bellman-Ford Routing Algorithm A distance-vector routing algorithm Initially designed in 1957 Currently used in many popular Internet routing protocols ARPANET (Advanced Research Projects Agency Network, US DoD), the origin of the Internet RIP (Routing Information Protocol) BGP (Border Gateway Protocol) NOVELL IPX Foundation for many ad-hoc routing protocols
Bellman-Ford Routing Algorithm Key Characteristics Distributed algorithm Each node exchanges routing information with its directly attached neighbors and makes its own routing decisions Iterative Routing information exchange continues until no new information is exchanged between the neighborhood. Asynchronous Do not require all nodes to operate in lock step with each other
Bellman-Ford Routing Algorithm How It Works Each router maintains a distance table, which is a one- dimensional array, hence the term distance vector Distance table maintains the distance and the shortest path to each node in the network. Distance (Cost of Path) to Destination Neighbor on shortest path to Destination Destination Node Distance can be hop-count distance or time it takes to transmit a packet to the destination Referred to generally as "cost Assumption: Each node knows the cost of the link to each of its directly connected neighbors.
Bellman-Ford Algorithm How It Works Every node sends routing update messages to its directly connected neighbors containing its own distance table Upon first joining the network or change of the distance table Every node updates its distance table with cost and next hops learned from its neighbors Repeat routing table exchange until no more new information between the neighbors.
Bellman-Ford Algorithm How It Works Shortest distance from Z1 to Y: D(Z1,Y) Cost of direct link C(X,Z) Y X Z1 Shortest distance from X to Y via Z1 : D(X,Y) = C(X,Z) + minZ {D(Z,Y)} Y Z2 Node X knows C(X,Zj ) for every neighbor Zj Node X can learn C(Zj,Y) from route updates from each neighbor Zj. Node X can compute D(X,Y) based on C(Zj,Y) for every neighbor Zj, and C(X,Zj)
Bellman-Ford Algorithm Potential Problems: Counting to Infinity X A B C Converged Stable Condition X 3 B X 2 C X A B C Routing update X 3 B X 4 A X 5 B X 4 A X 5 B X 6 A
Bellman-Ford Algorithm Solving the Counting-to-Infinity Problem Split Horizon If you learn a route on an interface, do not send information about that route back out that interface. Split Horizon eliminates routing loops with only two nodes. It is not effective in eliminating loops that involves more than two nodes Make the infinity finite Specify a maximum distance vector metric as infinity Hold Down Timers or Hold down Hold downs are ways to try to eliminate larger routing loops. When a node eliminates a node from its routing table, it initiates a hold downs so no new entries can be accepted for that node for a specific period of time. This helps to keep that node from being a member of the loop.
Existing Ad-Hoc Routing Protocols Pre-Computed(Table-Driven) Routing Proactive routing where every node maintains up-to-date and consistent routes to every other node On-Demand Routing Reactive routing that discovers a route only when needed Probabilistic/Opportunistic Routing Take advantage of the randomness of the network to route packets to further increase scalability Location-Added Routing Use location of the destination to route the traffic
Pre-Computed Ad-Hoc Routing Each node maintains routing tables to store up-to-date and consistent routes to each destination Nodes respond to changes in network topology by propagating routing update messages throughout the network Existing table-driven routing protocols differ primarily in how changes in network topology are propagated over the network Flat routing Requires each node to maintain a routing table containing all other nodes in the network Hierarchical routing Organizes nodes into a hierarchy of clusters
Sample Pre-Computed Routing Protocols Flat table-driven routing protocols Dynamic Destination-Sequenced Distance-Vector Routing Protocol (DSDV) Wireless Routing Protocol (WRP) Global State Routing (GSR) Fisheye State Routing (FSR) Hierarchical table-driven routing Hierarchical State Routing (HSR) Zone-based Hierarchical Link State Routing (ZLSR) Dynamic Source Routing Protocol
Dynamic Destination-Sequenced Distance- Vector Routing Protocol (DSDV) Based on Bellman-Ford Distance-Vector Routing Algorithm Each node maintains a Routing Table, which contains All available destinations Number of hops to reach the destination Sequence number assigned by the destination node used to avoid routing loops Destination 1 Hop counts to Destination Sequence Number 1 Destination 2 Hop counts to Destination Sequence Number 2 Key difference from classical Bellman-Ford protocol
Dynamic Destination-Sequenced Distance- Vector Routing Protocol (DSDV) Each node sends route update packets to its neighbors periodically and also when their routing tables change significantly Route update packet may carry the full routing table update or only an incremental update Each route update packet contains Address of known destinations # of hops to each destination A unique sequence number assigned by the originator for the route to the destination. Route with the highest (i.e. most recent) sequence number is used. If two routes have an identical sequence number, the route with the best metric (i.e. shortest route) is used
Dynamic Destination-Sequenced Distance- Vector Routing Protocol (DSDV) Route used by X for destination Y (sequence #=1) X A B Y Route Update (Y, Hop count to distance = 2, Seq. #=1) Route used by X for destination Y (sequence #=2) X A Y Route Update (Y, Hop count to distance = 1, Seq. #=2)
Wireless Routing Protocol (WRP) (1 / 7) Another distance-vector routing protocol Each node maintain 4 tables Distance Table Routing Table Link-Cost Table Message Retransmission List
Wireless Routing Protocol (WAP) (2 / 7) Distance Table Distance to each destination via each neighbor The downstream neighbor of each neighbor through which a path is realized Node X remembers a 2-hop path toward destination Destination X A B Y Hop-Count Distance to Destination
Wireless Routing Protocol (WAP) (3 / 7) Routing Table Distance to each destination node, Predecessor node and successor node for each path A tag to identify if the routing entry is a simple path, a loop, or invalid. A X B Y Distance = 2 Successor =A Predecessor =B Destination Y Tag Node X s Routing Table
Wireless Routing protocol (WAP) (4 / 7) Using Predecessor Info to Avoid Loops X A B C Converged Stable Condition X 3 B X 2 C X A B C Routing update B knows from the successor info it has and the predecessor in the route update that the route in this update Is not valid X 3 B C Destination Next Hop Distance Predecessor
Wireless Routing Protocol (WAP) (5 / 7) Link Cost Table and Message Retransmission List Link Cost Table Cost of link to each neighboring node The number of timeouts since an error-free message was received from that neighbor Message Retransmission List (MRL) contains Information to let a node know which of its neighbor has not acknowledged its update message and to retransmit update message to that neighbor.
Wireless Routing Protocol (WAP) (6 / 7) Routing Table Update Node sends routing updates to its neighbors periodically, and upon route changes Route may change when a neighbor moves away or when the node receives routing updates from its neighbors indicating new routes If there is no change in routing table since last update, the node is required to send an idle Hello message to ensure connectivity Nodes learn the existence of neighbors from receipt of ACKs and other messages An route update message contains A list of updates: destination, distance to destination, predecessor node of destination A response list indicating which neighbors should acknowledge the update Upon receiving an route update message, a node modifies its tables and looks for better paths using new information.
Wireless Routing Protocol (WAP) (7 / 7) Routing Table Update Any new path is relayed back to the original nodes so that they can update their tables. The node updates its routing table if the new path is better than the existing path. Upon receiving an ACK, the node updates its Message Retransmission List. Node checks the consistency of the information reported on the predecessors by all its neighbors every time it detects a change in link of any of its neighbors. This helps eliminate loops and enable fast convergence.
Global State Routing (GSR) A link-state routing protocol Each node maintains 4 tables Neighbor List: Contains all neighbor nodes Topology Table: Contains the link state information as reported by the destination and the timestamp of the information for each destination Next Hop Table: Contains the next hop toward each destination Distance Table: Contains the shortest distance to each destination.
Fisheye State Routing (FSR) FSR is an improvement of Global State Routing (GSR) to reduce the state update messages Issues addressed Update messages in GSR can be large and hence can waste a considerable amount of network bandwidth. Solution in FSR Each update message does not contain information about all nodes. Instead, it exchanges information about closer nodes more frequently than it does about farther nodes thus reducing the update message size. So each node gets accurate information about neighbors and the detail and accuracy of information decreases as the distance from node increases. Packets can be routed correctly because the route information becomes more and more accurate as the packet moves closer to the destination.
Hierarchical State Routing (HSR) Network is divided into clusters of nodes Each elects a cluster head as in a cluster-based routing algorithm Cluster heads organize themselves into clusters and so on. Nodes in a cluster broadcast their link information to each other Each cluster head summarizes its cluster's information and sends it to neighboring cluster heads via gateways A node at each level floods to its lower level the information that it obtains so the lower level has a hierarchical topology information. Each node has a hierarchical address
Routing Hierarchy in HSR Cluster Head X X.1 X.2 Virtual Link Virtual Nodes Cluster Head Cluster Head Cluster Head X.2.2 Physical Nodes Physical Link X.2.3 X.2.1 Cluster Cluster Head Gateways
Zone-based Hierarchical Link State Routing Protocol (ZHLS) (1 / 2) The network is divided into non-overlapping zones No zone head is needed better scalability Uses 2 levels of topologies: node level and zone level Use 2 types of Link State Packets (LSP) Node LSP contains information on a node s physical neighbors and is propagated within the zone Zone LSP contains the zone information and is propagated globally so that each node has full node connectivity knowledge about the nodes in its zone and only zone connectivity information about other zones.
Zone-based Hierarchical Link State Routing Protocol (ZHLS) (2 / 2) Nodes and zones are identified by Node IDs and Zone IDs Packet routing A packet is routed first based on the Zone ID to the destination zone. The, within the destination zone, the packet is routed based on the destination s Node ID
On-Demand Ad-Hoc Routing Protocols Discovers a route only when needed, by flooding a query to all nodes Each query packet remembers the intermediate nodes it traverses Destination, or nodes that know how to reach the destination, sends the route information accumulated in the query packet back to the source Routes are kept for a finite lifetime
Sample On-Demand Routing Protocols Dynamic Source Routing Protocol (DSRP) Ad hoc On-Demand Distance Vector (AODV) Routing IETF RFC 3561 Cluster-based Routing Protocol Temporarily Ordered Routing Protocol
Dynamic Source Routing Protocol On-demand source routing protocol. Source route: A packet carries in its header the entire route from source to destination A node caches source routes that it knows and updates them when needed A node can maintain multiple routes to the same destination No periodic routing updates Has two major phases Route discovery and Route maintenance.
Dynamic Source Routing Protocol Route Discovery Phase When a source node wants to send a packet to a destination, it Looks up its route cache to determine if it already knows a route to the destination. If it knows an unexpired route to the destination, it uses this route to send the packet. If is does not have an existing route, it initiates the route discovery process by broadcasting a route request packet The route request packet contains Addresses of the source and the destination, and A unique ID.
Dynamic Source Routing Protocol Route Discovery Phase Each intermediate node checks whether it knows a route to the destination. If it does not, it appends its address to the route record of the packet and forwards the packet to its neighbors If it knows a route to the destination, it sends a route reply message to the source along an unicast reverse path contained in the route request message To limit the number of route requests propagated, a node processes the route request packet only if it has not already seen the packet and its own address is not present in the route record of the packet
Dynamic Source Routing Illustration (1, 2) 2 5 Route Discovery (1, 2, 5) (1, 2, 5) (1) (1) 1 4 7 Source Destination (1, 4) (1) (1, 3, 6) Intermediate node caches source route in the packet 3 6 (1, 3) 2 5 Route Reply 1 4 7 Source Destination (1, 3, 6, 7) (1, 3, 6, 7) 3 6 (1, 3, 6, 7)
Dynamic Source Routing Route Maintenance Each node along a route is responsible for detecting failure of the part of the route that goes through it Upon detecting a broken link, it informs the source Source deletes any route in its cache that uses the broken link Source may re-initiate the route discovery procedure to find a new route
Ad-Hoc On-Demand Distance Vector Routing (AODV) Distance-vector routing used on an on-demand fashion Node search for a route to a destination only when it needs to send packets to the destination and does not already have a route to the destination Node keeps active routes in the same manner as in traditional routing tables: <destination, next hop> An active route is one over which at least one packet has been forwarded over the past active timeout period Two main operations Route discovery Route maintenance
AODV Route Discovery To find a route to the destination, the source broadcasts a Route Request packet to all its neighbors, which in turn broadcast the Route Request to their neighbors until the Route Request reaches The destination, or An intermediate node that has an up-to-date route to the destination To avoid route loops, a node discards a Route Request that it has already seen. Route Request packets identified by sequence numbers
AODV Route Discovery Destination or an intermediate node with a route to the destination unicasts a Route Reply packet back to the source along a reserve direction of the path traveled by the Route Request To construct the reverse path, a node records the neighbor from which the first copy of each Route Request came As the Route Reply travels back to the source, the nodes along the way enter the forward route into their routing tables, forming a forward route from the source to the destination
AODV Route Discovery To ensure most recent route is used and to help avoid routing loop, AODV uses a Destination Sequence Number When the destination sends back the Route Reply packet, it assigns a Destination Sequence Number to the route and insert the Destination Sequence Number in the Route Reply. As the Route Reply travels towards the source, each node along the way records the Destination Sequence Number for the route in its routing table as illustrated below Destination IP Address Destination Sequence Number Hop Count Next Hop Lifetime
AODV Route Discovery Illustration 2 5 Route Discovery 1 4 7 Source Destination 3 6 Intermediate node caches the route to source 2 5 Route Reply 1 4 7 Source Destination Route establishment 3 6
AODV: Use of Destination Sequence Number Destination Sequence Number = 1 For route to Y Source 1 Destination X A B Y Source 2 Destination Sequence Number = 2 For route to Y Q Destination A Y Destination Sequence Number = 2 For route to Y Source 1 Destination Route Request (Dest. Seq. # =1) X A Y Node A will use new route to Y to respond to this Route Request
