Project Links Logo Artwork
Graph Theory: Networking
Home > Graph Theory: Networking > The Internet > Distance-Vector Routing
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Distance-Vector Routing

Distance-vector routing makes this assumption:

Each router knows the identity of every other router in the network.

In an attempt to enforce this assumption, each router will maintain a distance vector, comprised of the list of tuples:

< destination, cost >

... for all nodes in the network. Here, cost is the current estimate of the shortest path from this router to the destination; the estimate is never smaller than the real cost of the path.

The distance-vector algorithm is a distributed implementation of the Bellman-Ford algorithm:

  1. Each router periodically sends a copy of its distance vector to its neighbors.
  2. When a router receives a distance vector from a neighbor, it determines whether its cost of reaching any destination would decrease if packets to that destination were to be sent through that neighbor.
  3. If so, that router updates its own distance vector.
 
 
go backgo forward
go backgo forward