Link-State vs Distance Vector: Routing Showdown

In the modern networking world routing protocols fall into two distinct camps, Link-state and Distance Vector. Being a network consultant I often have customers asking me which routing protocol is better so I figure I would create a post comparing the different routing protocols.

What makes a routing protocol Link-state vs Distance Vector? The simplest way to answer this is to ask does the router need to learn about all routes and routers on the network to find the best path, or does it only need to know about directly connected routers and learn the best paths between its neighbors? If the answer is the router needs to learn about all paths then that protocol is Link-State, if it only needs to learn paths between different neighbors then the protocol is Distance Vector.

So, now that we know the difference, which one is better? As with everything in life, that question is just not that simple. There are Pros and Cons to each, so let’s break them down. I’ve put together a few categories to test both link-state and distance vector to see which one shines. The categories are:

  • Router Utilization
  • Network Convergence
  • Best Path Accuracy

Router Utilization

Router Utilization is really all about the hardware. Some routing protocols are light weight, while others can be taxing on CPU and memory utilization, requiring beefier hardware. In this section we are going to talk about router utilization from a high level, we won’t go deep into each routing protocol.

While some routing protocols are more efficient than others and we could go into a longwinded discussion of each, overall Link-State routing protocols require more resources than Distance Vector. The reason for this is simply in a Link-State routing protcol, such as OSPF, every router needs to know the state of each link and node in the network. The link-state database has to be the same on every router and can get quite large in complex environments. Link-state routing algorithms require the full picture to accurately choose the best path through the network.

On the other side Distance Vector routing protools only need to know the state of its neighbors and the metrics for each path to a particular subnet. Each routers database is slightly different as the number of paths to and metrics for a subnet change. This means smaller tables and less memory utilization.

With modern SD-WAN solutions many of the routers are now “dumb devices” with the decision making happening at a centralized controller with those final routing tables being passed down to the routers. This solution is Link-State like however with all of the processing and database creation happening on a single or a few nodes, it is the most effient use of router utilization.

Network Convergence

Identifying how quickly network convergence happens really comes down to the design of the network. Your network design plays a big role in choosing which type of routing protocol you choose. For the purposes of this blog post we are going to describe two network design types; Hub and Spoke, or Full Mesh.

Hub and Spoke designs, as well as any variant of a hybrid Hub and Spoke design, by definition have fewer connections between routers. With the exception of the hub routers, the routers will only have one or two connections. Distance Vector routing protocols work well in a hub and spoke design because each spoke router only has to calculate metrics for routes coming from the hubs. This reduces the amount of calculations the protocol has to preform reducing convergence time. In a Distance Vector routing protocol the hub routers are the work horses as they will have the most amount of connections, and therefore require beefed up hardware.

I should note that the diameter of the network, or the number of hops between the core and edge of the network, plays a much larger role in how quickly a Distance Vector protocol will converge. The smaller the diameter the faster the convergence.

Full Mesh designs by definition have a greater number of connections than nodes so a Link-State routing protocol would work well in this design. In all honesty because in a Full Mesh design each node is neighbors with every other node a Distance Vector routing protocol would act like a Link-State protocol so we might as well take advantage of the benefits of a Link-State protocol.

In most of the SD-WAN solutions I’ve seen use a Full Mesh design. Not surprising we tend to also see some form of Link-State protocol used in routing.

Best Path Accuracy

The whole point of using a dynamic routing protocol is to choose the best path through the network. How a routing protocol chooses that best path tends to be the bread and butter that defines each protocol. Because the point of this post is to stay high level I won’t be going into details about each routing protocol’s best path selection, instead I will talk about what each of the routing camps have in common.

In the Link-State camp, these protocols need to know the metrics for each link in the path. This means that each router has a very clear picture of the costs associated with each link and because of this can calculate the best path accurately. Additionally, alternate paths can be calculated using the same methods as choosing the best path, reducing the complexity of that protocol.

Over in the Distance Vector camp, these protocols only calculate the metrics of the directly connected links. The neighbor has to provide a metric to the router that represents the calculated route to the end network for them, from there the router adds its local metic to the reported metic. What this means is that every router trusts the neighbor calculated the routes correctly, meaning inaccuracies can escalate in a Distance Vector routing protocol. Additionally more complex loop prevention methods have to be in play to calculate alternate paths, increasing the complexity of the routing protocol.

Overall your WAN design will drive your selection of a routing protocol. Many of the modern WAN topologies are designed with either Link-State or Distance Vector protocol in mind. Ultimately the design guides for your chosen WAN design may guide you towards a particular protocol.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s