DSDV Destination-Sequenced Distance-Vector Routing Protocol - PowerPoint PPT Presentation
DSDV Destination-Sequenced Distance-Vector Routing Protocol
Description:
DSDV Destination-Sequenced Distance-Vector Routing Protocol Outline Introduction Distance-Vector DSDV Protocol Summary Introduction The property of ad-hoc networks . – PowerPoint PPT presentation
Number of Views:149
Avg rating: 3.0/5.0
Slides: 32
Provided by: TobiasSc4
Category:
Tags: dsdv | destination | distance | even | numbers | protocol | routing | sequenced | vector
Transcript and Presenter's Notes
Title: DSDV Destination-Sequenced Distance-Vector Routing Protocol
- Introduction
- Distance-Vector
- DSDV Protocol
- Summary
- The property of ad-hoc networks
- Topology may be quite dynamic
- No administrative host
- Hosts with finite power
- The properties of the ad-hoc network routing
protocol
- Simple
- Less storage space
- Loop free
- Short control message (Low overhead)
- Less power consumption
- Multiple disjoint routes
- Fast rerouting mechanism
- Routing Protocol
- Table-driven (proactive)
- Source-initiated on-demand (reactive)
- Hybrid
- Routing Algorithm
- Link-State algorithm
- Each node maintains a view of the network
topology
- Distance-Vector algorithm
- Every node maintains the distance of each
destination
- Like the shortest-path computation method
- Each node maintains a view of the network
topology with a cost for each link
- Periodically broadcast link costs to its outgoing
links to all other nodes such as flooding
- known also as Distributed Bellman-Ford or RIP
(Routing Information Protocol)
- Every node maintains a routing table
- all available destinations
- the next node to reach to destination
- the number of hops to reach the destination
- Periodically send table to all neighbors to
maintain topology
D C 2
Dest. Next Metric
D B 3
Dest. Next Metric
D B 1
Dest. Next Metric
D D ?
13
Distance Vector (Loops)
(D, 2)
(D, 2)
1
1
1
D
C
B
A
Dest. Next Metric
D B 3
Dest. Next Metric
D C 2
Dest. Next Metric
D B 3, 5,
Dest. Next Metric
D B 3, 5,
Dest.c Next Metric
- DV not suited for ad-hoc networks!
- Loops
- Count to Infinity
- New Solution -gt DSDV Protocol
- DSDV is Destination Based
- No global view of topology
- DSDV is Proactive (Table Driven)
- Each node maintains routing information for all
known destinations
- Routing information must be updated periodically
- Traffic overhead even if there is no change in
network topology
- Maintains routes which are never used
- Keep the simplicity of Distance Vector
- Guarantee Loop Freeness
- New Table Entry for Destination Sequence Number
- Allow fast reaction to topology changes
- Make immediate route advertisement on significant
changes in routing table
- but wait with advertising of unstable
routes(damping fluctuations)
- Sequence number originated from destination.
Ensuresloop freeness.
- Install Time when entry was made (used to delete
stale entries from table)
- Stable Data Pointer to a table holding
information on how stable a route is. Used to
damp fluctuations in network.
- Advertise to each neighbor own routing
information
- Destination Address
- Metric Number of Hops to Destination
- Destination Sequence Number
- Rules to set sequence number information
- On each advertisement increase own destination
sequence number (use only even numbers)
- If a node is no more reachable (timeout) increase
sequence number of this node by 1 (odd sequence
number) and set metric ?
- Update information is compared to own routing
table
- 1. Select route with higher destination sequence
number (This ensure to use always newest
information from destination)
- 2. Select the route with better metric when
sequence numbers are equal.
- Immediate advertisements
- Information on new Routes, broken Links, metric
change is immediately propagated to neighbors.
- Full/Incremental Update
- Full Update Send all routing information from
own table.
- Incremental Update Send only entries that has
changed. (Make it fit into one single packet)
Dest. Next Metric Seq.
A A 1 A-550
B B 0 B-104
C C 1 C-590
Dest. Next Metric Seq.
A B 2 A-550
B B 1 B-104
C C 0 C-590
D D 1 D-000
26
DSDV (New Node cont.)
3. C increases its sequence number to C-592 then
broadcasts its new table.
4. B gets this new information and updates its
table.
(A, 2, A-550) (B, 1, B-102) (C, 0, C-592) (D, 1,
D-000)
(A, 2, A-550) (B, 1, B-102) (C, 0, C-592) (D, 1,
D-000)
C
B
A
D
Dest. Next Metric Seq.
A A 1 A-550
B B 0 B-102
C C 1 C-592
D C 2 D-000
Dest. Next Metric Seq.
A A 0 A-550
B B 1 B-104
C B 2 C-590
Dest. Next Metric Seq.
A B 2 A-550
B B 1 B-102
C C 0 C-592
D D 1 D-000
27
DSDV (no loops, no count to infinity)
2. B does its broadcast-gt no affect on C (C
knows that B has stale information because C has
higher seq. number for destination D) -gt no loop
-gt no count to infinity
1. Node C detects broken Link-gt Increase Seq.
Nr. by 1(only case where not the destination
sets the sequence number -gt odd number)
(D, 2, D-100)
(D, 2, D-100)
D
C
B
A
Dest.c Next Metric Seq.
D C 2 D-100
Dest. Next Metric Seq.
D B 3 D-100
Dest. Next Metric Seq.
D D ? D-101
28
DSDV (Immediate Advertisement)
3. Immediate propagation B to A(update
information has higher Seq. Nr. -gt replace table
entry)
2. Immediate propagationC to B(update
information has higher Seq. Nr. -gt replace table
entry)
1. Node C detects broken Link-gt Increase Seq.
Nr. by 1(only case where not the destination
sets the sequence number -gt odd number)
(D, ?, D-101)
(D, ?, D-101)
D
C
B
A
Dest.c Next Metric Seq.
D C 3 D-100
Dest. Next Metric Seq.
D B 4 D-100
Dest. Next Metric Seq.
D B 1 D-100
Dest. Next Metric Seq.
- What are Fluctuations
- Entry for D in A D, Q, 14, D-100
- D makes Broadcast with Seq. Nr. D-102
- A receives from P Update (D, 15, D-102)-gt Entry
for D in A D, P, 15, D-102 A must propagate
this route immediately.
- A receives from Q Update (D, 14, D-102)-gt Entry
for D in A D, Q, 14, D-102A must propagate
this route immediately.
- This can happen every time D or any other node
does its broadcast and lead to unnecessary route
advertisements in the network, so called
fluctuations.
- How to damp fluctuations
- Record last and avg. Settling Time of every Route
in a separate table. (Stable Data)Settling Time
Time between arrival of first route and the
best route with a given seq. nr.
- A still must update his routing table on the
first arrival of a route with a newer seq. nr.,
but he can wait to advertising it. Time to wait
is proposed to be 2(avg. Settling Time).
- Like this fluctuations in larger networks can be
damped to avoid unececarry adverdisment, thus
saving bandwith.
- Advantages
- Simple (almost like Distance Vector)
- Loop free through destination seq. numbers
- No latency caused by route discovery
- Disadvantages
- No sleeping nodes
- Overhead most routing information never used
