Routing Principles

Networking Basics

Routing can be compared with the kind of routing we would do when we try to travel to another city by car. We need to figure out which way to take, we need to get a new route when something on our normal route is blocked, etc.

In computer networks routing is needed in lots of different situation. For example in a circuit switched network (like the phone network) a connection needs to be established at the beginning and it remains static till the end of the conversation. In a packed switched network (like the internet), each packet (chunk of information) gets routed seperately, so the decision which way to take needs to be performed way more often. This decision happens on special hardware, so called routers.

The routers build a topology map of the network where each router represents a node. Nodes in the network can be added or removed, therefore the routing needs to adjust dynamically to changes of the network topology. Routing algorithms calculate the ways we can take through a network on demand and save or update them to routing tables.

Common routing protocols are based on two algorithms:

• Global information, where all routers know the whole topology of the network and calculate the routing tables with a link state algorithm.

• Decentralized information, where the routers only know their directly connected neighbors and calculate their routing tables with a distance vector algorithm.

Link State Routing

Link state routing was invented by John McQuillan in 1978 and used in the early days of the ARPANET. Known protocols that implement link stare algorithms are OSPF or ISIS.

Every link between two nodes has costs, these can be configured as any metric at choice (eg. delay). Link state algorithms are based on global information, that means that every node knows all the other nodes (the whole network topology) and the link costs to them. Using Dijkstra's algorithm it then computes the least cost paths to all nodes other and store that information in the routing table.

To build the whole topology map each node first checks the links to its directly connected neighbors. Then it sends a so called link state advertisements through the network with all the information about its neighbors. From all the received advertisements each node can now compute the topology.

Dijkstra's Algorithm

To calculate the routing table from the computed topology map, link state protocols perform Dijkstra's shortest path first algorithm. In small graphs the shortest path (the one with the least costs) is easy to see, like in the graph below, but in more complex networks an algorithm is needed to compute it.

      3
   A-----B
   |     |
 2 |     | 4
   |     |
   C-----D
      1

Obviously the shortest path from A to D in this graph would be via C. Following the algorithm we would compute that as follows:

For node A:

• for all nodes, if node adjacent to A set known costs, else set infinity

 N'  D(B)  D(C)  D(D)
 ------------------------------
 A   3     2     infinity

• take the next node (which is not in N') and has the minimum costs (in our example C)
• check all neighbors of this node, update costs if they are less via C (or replace infinity)

 N'  D(B)  D(C)  D(D)
 ------------------------------
 A   3     2     infinity
 AC  3     -     3

• loop last 2 steps until all nodes in N'

Now we can compute the routing table (or next hop table) for node A:

 Destination  Next-Hop
 ------------------------------
 B           B
 C           C
 D           C

OSPF

OSPR (Open Shortest Path First) is an interior gateway protocol which uses the link state algorithm to compute the routing table. It is one example for an implementation of the link state algorithm. It doesn't send all link state advertisements over and over again, but sends out incremental updates after a link state change.

It checks the link state by sending Hello packets periodically. If one neighbor doesn't respond the network gets flooded with an update (to a multicast address). The updates must be acknowledged by the recipients to ensure identical maps at each node.