Back to ComputerTerms
Routing Algorithm
The Distance Vector algorithm is one in which global information is given to local nodes - that is neighboring nodes. Below is a table of how a node interacts with it's peers, but first an example:
B / \ A -- C |\ \ | E D | / F----G Figure 1
We build two tables
1 Initial distances stored at each node (global view) 2 Initial routing table at node A.
Information Stored at Node A |
Distance to reach Node |
||||||
A |
B |
C |
D |
E |
F |
G |
|
A |
0 |
1 |
1 |
inf |
1 |
1 |
inf |
B |
1 |
0 |
1 |
inf |
inf |
inf |
inf |
C |
1 |
1 |
0 |
1 |
inf |
inf |
inf |
D |
inf |
inf |
1 |
0 |
inf |
inf |
1 |
E |
1 |
inf |
inf |
inf |
0 |
inf |
inf |
F |
1 |
inf |
inf |
inf |
inf |
0 |
1 |
G |
inf |
inf |
inf |
1 |
inf |
1 |
0 |
Destination |
Cost |
|
B |
1 |
B |
C |
1 |
C |
D |
inf |
- |
E |
1 |
E |
F |
1 |
F |
G |
inf |
- |
Notes
Who: |
Broadcasts information to it's neighbors |
What: |
(Destination, Cost) tuples |
When: |
Periodically and when triggered by a change. Information is deleted after a time out. |
- Converges when the topology is static
- Suseptible to routing loops - race to infinity problem.
Routing loops between neighbors can be fixed with either SplitHorizon or SplitHorizon with poison reverse.
Example: InteriorGatewayRoutingProtocol (IGRP)
Back to ComputerTerms