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
Initial distances stored at each node (global view)
Initial routing table at node A.
Information Stored |
Distance to reach Node |
||||||
at Node A |
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 |
Next Hop |
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) RoutingInformationProtocol (RIP) as in Rest In Peace.
Back to ComputerTerms