Differences between revisions 2 and 16 (spanning 14 versions)
Revision 2 as of 2003-09-16 23:31:19
Size: 579
Editor: yakko
Comment:
Revision 16 as of 2003-09-25 17:49:53
Size: 1506
Editor: yakko
Comment:
Deletions are marked like this. Additions are marked like this.
Line 5: 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:

{{{
  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||
Line 8: Line 35:

||Destination||Cost||Next Hop||
||B||1||B||
||C||1||C||
||D||inf||-||
||E||1||E||
||F||1||F||
||G||inf||-||

=== Notes ===
Line 13: Line 50:
Notes:
Line 17: Line 52:
   * 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

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)