The Control Plane: Static & Dynamic Routing

Modeling the Network as a Graph

A network can be modeled as a directed weighted graph. Each router is a node, and the links between routers are the edges in the graph. A positive weight is associated with each directed edge. Routers use the shortest path to reach each destination. In practice, different types of weights can be associated with each directed edge:

• Unit weight. If all links have a unit weight, shortest path routing prefers the paths with the least number of intermediate routers.
• Weight proportional to the propagation delay. If all link weights are configured this way, shortest path routing algorithms will prefer the paths with the smallest propagation delay.
• Weight proportional to the available bandwidth. $weight = \frac{C}{bandwidth}$ where $C$ is a constant larger than the highest link bandwidth in the network. If all link weights are configured this way, shortest path routing algorithms will prefer paths with higher bandwidth.

Usually, the same weight is assigned to the two edges that correspond to a physical link (i.e. $R1→R2$ and $R2→R1$). However, it’s not necessary and some asymmetric links may have different bandwidths upstream and downstream.

Static Routing

Manually computed routes are manually added to the routing table. This is useful if there are a few outgoing links from your network. It gets difficult when you have rich connectivity (in terms of the number of links to other networks). It also does not automatically adapt to changes – addition or removal of links or routers.

Disadvantages of Static Routing

1. The main drawback of static routing is that it doesn’t adapt to the evolution of the network and hence doesn’t scale well. When a new route or link is added, all routing tables must be recomputed.
2. Furthermore, when a link or router fails, the routing tables must be updated as well.

Dynamic Routing Algorithms

Unlike static routing algorithms, dynamic ones adapt routing tables with changes in the network. There are two main classes of dynamic routing algorithms: distance vector and link-state routing algorithms.

Distance Vector Routing

Distance vector is a simple distributed routing protocol. Distance vector routing allows routers to discover the destinations reachable inside the network as well as the shortest path to reach each of these destinations. The shortest path is computed based on the cost that is associated with each link.

Link-State Routing

Another way to create a routing table with the most efficient path between two routers or ‘nodes’ is by using link-state routing.

Link-state routing works in two phases: reliable flooding and route calculation.

Routers running distance vector algorithms share summarized reachability information with their neighbors. Every router running link-state algorithms, on the other hand, builds a complete picture of the whole network (which is phase I) before computing the shortest path to all destinations.

Then, based on this learned topology, each router is able to compute its routing table by using the shortest path computation such as Dijkstra’s Algorithm. This is phase II.

Here’s a little roadmap of routing algorithm types.

Note: Central Route Calculation It’s possible that in a network all the routes are computed centrally using a specific routing algorithm, and then downloaded to all the routers in the network. This approach can be used in relatively small networks but has scalability problems. This is usually achieved via architectures based on constructs such as Path Computation Element (PCE).

On the other hand, routing tables can be computed in a distributed manner, whereby routers share reachability information with their neighbors. Then all routers independently run a routing algorithm to compute their local routing table. This is what we’re mainly focusing on in this course.

Quick Quiz!