Diff for "DistanceVector"

Differences between revisions 6 and 12 (spanning 6 versions)

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)

Back to ComputerTerms

-  ⇤ ← Revision 6 as of 2003-09-25 17:43:10 → 
  Size: 1443
  Editor: yakko
  Comment:
+   ← Revision 12 as of 2003-09-25 17:46:15 → ⇥
  Size: 1441
  Editor: yakko
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 8:
-   B
  / \
A -- C
|\    \
| E    D
|     /
F----G
+  B
 / \
A - C
|\   \
| E   D
|    /
F---G
 Line 20:
-'''Initial''' distances stored at each node (global view)
   2 '''Initial''' routing table at node A.
-Line 23:
+Line 21:
-||Information Stored at Node A||||||||||||||Distance to reach Node||
||||A||B||C||D||E||F||G||
+. '''Initial''' distances stored at each node (global view)
   2. '''Initial''' routing table at node A.

||Information Stored ||||||||||||||Distance to reach Node||
||at Node A||A||B||C||D||E||F||G||
-Line 33:
+Line 34:
-||Destination||Cost||NextHop||
+||Destination||Cost||Next Hop||