RoutingPrinciples

Routing is the process of determining a message path from source to target (which are not directly connected) using multiple other hosts in the middle. Low level network communication is usually point to point and does know routing. Therefor higher level protocols need to be established -- routing protocols.

Many objectives lead to different routing mechanisms serving different ranges of application. This article will discuss the routing principles, the basic protocols, which are basis for many other optimized and specific protocols.

While Distance Vector and Link State Routing serve to show these principles, you will find more detail on special Ad-Hoc Network oriented routing protocols in the Routing Protocols article.

Distance Vector Routing (DV)

History

Distance Vector -- also known as Bellman-Ford or Ford-Fulkerson -- is a dynamic routing algorithm, meaning it dynamically determins the route for each packet independently. DV is the original ARPANET routing algorithm, was replaced by Link State Routing in 1979, though.

Routing Table

In DV each router maintains a routing table containing one entry for each router in the subnet. A router usually has many outgoing lines or connections (e.g. wireless) from which more than one may lead to the same target, but with different quality, speed, or whatever metric is used to distinguish the best connection. The routing table keeps an entry for each router in the subnet, telling what line to choose when addressing that router including an estimate of time or distance to that destination (metric).

Distributing Routing Knowledge

For each router to know the best path to all others, routing knowledge has to be distributed among the routers. To make things easy, let delay be the used metric from now on, you may replace it with whatever you think to be applicable, though.

First of all lets state, that every router knows the delay to all of its neighbors. As a router passes on its knowledge to all neighbors, it also receives frequent notifications of its neighbors knowledge. When a router processes an incoming routing table (from a neighbor), it automatically adds the distance (delay) to that neighbor to the table's entries and compares it to the values of the other neighbors' incoming knowledge . If the local table's value is greater than the received value + distance, the new value is written to the local routing table, replacing the old value.

Step by step new knowledge is passed from router to router and trickles through the subnet.

Count-to-Infinity Problem

As routers usually only add better routes to their routing tables, a problem raises, which actually is DV's greatest disadvantage. While reports about short delays are adopted quickly, bad news only spread in slow increments.

Example: Router B looses link to A (and sets the local routing table entry for A to infinity), but C still thinks it has a route to A over B. C propagates this to B and B believes it can reach A over B. B now adds its delay to C to the received value and saves the new (believed) connection to its routing table (because it is smaller than infinity), creating a loop between B and C for all messages sent to A. Step by step B and C now update eachothers routing tables, increasing the entry for A each time until it reaches the value defined as infinity, causing the link to be recognized as broken.

This process of counting to infinity is very slow compared to other route updates, causing the whole network not noticing a routers down state for quite a while, and was therefor named count-to-infinity problem

Link State Routing (LSR)

(... to be edited ...)