Switch has routing table, which is consulted to determine which output line to send the packet out.

Methods for determining routes in network fall into several categories. Consider the advantages and disadvantages of each:

1. centralized. A distinguished node has global knowledge of network and runs algorithm to determine shortest path, then distributes routing information to other nodes.
2. distributed. Each node dynamically builds its routing table using local information, usually obtained from backward learning, plus information it receives from its neighbors (and possibly from other nodes as well).
3. isolated. Each node determines routing tables using only local information obtained from backward learning. An extreme form of the distributed method.

Essence:

• routers exchange routing information with neighbors.
• Information packet from each neighbor is called "vector"
• Vector contains "best known distance" to each destination from that neighbor.
• "Neighbor" means directly connected.
• router uses info from neighbors to update its routing table

Router receiving this vector:

• destination
• estimated shortest distance (normally hop count)
• next hop on shortest path

Upon receipt of vector, router processes each destination included in vector:

1. add "distance to neighbor" to "best known distance" (from vector)
2. compare sum to routing table "estimated shortest distance" to that destination
3. if less, store new sum and neighbor into routing table entry
4. if more, but "next hop" is vector’s router, update "estimated shortest distance"

In practice, it was found that "good news traveled faster than bad" Network was quicker to record reduced distances than increased ones. Traffic would quickly flow to routers along the new path.

Essense is that each router:

• knows its neighbors
• knows "distance" to each neighbor. (#hops, bandwidth, congestion, etc.)
• broadcasts "distance to neighbor" to all other routers in the internet.
• uses received broadcasts to run Shortest Path algorithm locally

Dijkstra shortest path algorithm:

PreDefinitions:

1. designate source node
2. put all other nodes into set S
3. array D[v] is weight from source to node v if known (else infinite)
4. routing table R, where R[v] is next hop router for destination v.

Algorithm:

while S is not empty,

1. chose node u from S s.t. D[u] is minimum
2. remove u from S
3. for each neighbor v (of u) which is still in S

• weight from source to v is calculated
• if it is less then D[v], update distance
• make it the new D[v]
• set next-hop in routing table R[v] to R[u] (e.g. same next-hop if dest is u or v)

Dijkstra's algorithm is attractive in that "weight" is defined to be whatever the network designers want: distance, bandwidth, delay,utilization, number of switches (each hop has weight of one), etc.

 Note of Historical Interest

Last reviewed: 10 April 2000