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

A DV based routing algorithm that solves the count-to-infinity problem is Destination Sequenced Distance Vector.

Link State Routing (LSR)

History

The Link State Routing Algorithm replaced Distance Vector (DV) in the late 70's of the 20th century because the latter hat several problems:

• the original DV used queue length as metric (to distinguish good from bad links). That worked well as long everyone had about the same line speed (56kbps used to be fast). With higher bandwidths coming up, queues were either empty or full (congestion) → not functioning as metric anymore.
• the Count-to-Infinity Problem

These and maybe other reasons caused Link State Routing to become the new dynamic routing algorithm of the ARPANET in 1979.

Overview

Link State Routing is not like DV based on local knowledge, but on measuring and distributing the complete topology first. The Dijkstra shortest path algorithm finally helps to determine the best routes through the subnet. And this is how it's done:

1. discover neighbors/learn network addresses
2. measure delay/cost to each neighbor
3. construct packet to distribute knowledge
4. send packet to all other routers
5. compute shortest path to every router