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 distributes passes on its knowledge to all neighbors it receives frequent notifications of its neighbors knowledge.

(... to be continued)