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, Destination-Sequenced Distance-Vector Routing is an example for a more specific, Ad-Hoc Network oriented implementation.

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 local routing table. 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.

(... to be continued)