|
Size: 1443
Comment:
|
Size: 1447
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 20: | Line 20: |
| 1 '''Initial''' distances stored at each node (global view) 2 '''Initial''' routing table at node A. |
1. '''Initial''' distances stored at each node (global view) 2. '''Initial''' routing table at node A. |
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 |
|
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