Differences between revisions 1 and 14 (spanning 13 versions)
Revision 1 as of 2003-09-16 23:30:14
Size: 529
Editor: yakko
Comment:
Revision 14 as of 2003-09-25 17:49:21
Size: 1501
Editor: yakko
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
Back to ComputerTerms
Line 3: Line 5:
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. 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:
Line 5: Line 7:
. {{{
  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 ||||||||||||||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 ===
Line 11: Line 48:
Notes:
Line 15: Line 50:
   * 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

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

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

DistanceVector (last edited 2003-09-25 17:49:53 by yakko)