Routing Algorithms

Link-State Protocols and Algorithms

The protocols that are link-state based are OSPF (Open Shortest Path Forwarding), IS-IS (Intermediate System - Intermediate System) and, very importantly, Shortest Path Bridging (SPB / 802.1aq). The basic concept of link-state routing is that every node constructs a map of the connectivity to the network, in the form of a graph, showing which nodes are connected to which other nodes. Each node then independently calculates the next best logical path from it to every possible destination in the network. Each collection of best paths will then form each node’s routing table. The Link-state algorithm of interest (Dijkstra’s) is covered in a separate section as part of the wider umbrella of Forward Search algorithms.

Distance-Vector Protocols and Algorithms

The protocols that are DV-based are RIP and BGP amongst others - BGP being one of the most important protocols in networking. A distance-vector routing protocol in data networks determines the best route for data packets based on distance. Distance-vector routing protocols measure the distance by the number of routers a packet has to pass, one router counts as one hop. Some distance-vector protocols also take into account network latency and other factors that influence traffic on a given route. To determine the best route across a network, routers, on which a distance-vector protocol is implemented, exchange information with one another, usually routing tables plus hop counts for destination networks and possibly other traffic information. Distance-vector routing protocols use the Bellman–Ford algorithm and Ford–Fulkerson algorithm to calculate the best route. The concept described here is of fundamental importance - it is also widely known as Dynamic Programming.

The DV based routing algorithm is best explained via an example extracted from here.

The shortest path in the routing tables below is highlighted in green, and a new shortest path is highlighted in lime. Grey columns indicate nodes that are not neighbors of the current node, and are therefore not considered as a valid direction in its table. Red indicates invalid entries in the table since they refer to distances from a node to itself, or via itself.

Example network

T=0 - all the routers (A,B,C,D) have new “shortest-paths” for their DV (the list of distances that are from them to another router via a neighbor). They each broadcast this new DV to all their neighbors: A to B and C, B to C and A, C to A, B, and D, and D to C. As each of these neighbors receives this information, they now recalculate the shortest path using it.

All the routers have gained in the last iteration (at T=1) new “shortest-paths”, so they all broadcast their DVs to their neighbors; This prompts each neighbor to re-calculate their shortest distances again. A receives a DV from C that tells A there is a path via C to D, with a distance (or cost) of 5. Since the current “shortest-path” to C is 23, then A knows it has a path to D that costs 23+5=28. As there are no other shorter paths that A knows about, it puts this as its current estimate for the shortest-path from itself (A) to D, via C.

This time, only routers A and D have new shortest-paths for their DVs. So they broadcast their new DVs to their neighbors: A broadcasts to B and C, and D broadcasts to C. This causes each of the neighbors receiving the new DVs to re-calculate their shortest paths. However, since the information from the DVs doesn’t yield any shorter paths than they already have in their routing tables, then there are no changes to the routing tables.

None of the routers have any new shortest-paths to broadcast. Therefore, none of the routers receive any new information that might change their routing tables. The algorithm comes to a stop.