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 to forward the message. 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 C. 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 before routing data. 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

Step One: Learning about Neighbors

The router which is trying to learn about it's neighbors sends out HELLO messages on each connected point-to-point line. The received replies then tell which router (node) is at the other end and what it's address is. LANs connected to a line may be treated as artificial node.

Step Two: Measuring Line Cost

Originally delay served as metric, so the time in between sending an ECHO packet and receiving the reply was measured and saved as cost for each line. In addition load effects may be incorporated into the roundtrip time, but including load might lead to oscillating routing tables.

Example:

  If two routers (A and B) are available to route to the same target, the 
  router with the least load (ie. A) will receive all the traffic to that
  target. That of course will turn around the situation, causing A to have 
  more load now and B -- at worst -- to be idle even.
  
  The LSR algorithm knows this and updates all routing tables to use B from
  now on causing the same effect the other way around. → situation keeps on
  going like that, causing routing tables to oszillate which leads to lots 
  of unnecessary routing traffic.

Step Three: Building Link State Packets

Each router builds a Link State Packet containing these values:

• identity of sender
• a 32 Bit sequence number
• age
• list of neighbors

Step Four: Distributing the Link State Packets

Flooding is used as distribution mechanism, but receiving routers have to take care not to adopt incoming changes instantly, because that might effect other routing packets that are still on their way, causing the flooding to fail. → routers have to wait a defined time.

The contained sequence number is used to identify duplicates and discard those.

Each link state packet starts with an initial value set in the age field, which is decremented every second (at least one second per hop) and old packets are finally discarded. This field (also known as time to live, TTL) is nowaday simple decremented by one per hop, since seconds are no longer adequate in today's high speed connections.

Step Five: Computing the New Routes

A router accumulates a full set of link state packets in order to construct the entire graph of the subnet. It then locally runs Dijkstra's algorithm to determine shortest paths to all the routers.

A problem to consider on huge subnets might result from broken routers which send out wrong information, leading to incorrect subgraphs. There are different proposals to solve this problem:
→ special solution (Pearlman)
→ special implementations (OSPF, IS-IS)

Literature

• Andrew S. Tanenbaum "Computer Networks" ISBN 0-13-066102-3
• Lecture Slides