Routing theory: are link state and distance vector the only games in town?
▼ During his talk about 30 years of BGP, Geoff Huston said something along the lines of "someone should come up with another type of routing protocol besides distance vector and link state". That is of course too delicious a challenge to ignore.
But what would such new routing protocol type look like? It seems really strange that there would be exactly two ways to accomplish this task, and yet, as far as I know, nobody has ever proposed something truly different. And I can't think of anything. My conclusion: distance vector and link state routing protocols, with RIP and OSPF, respectively, as the archetypical examples, are not two completely separate ways to do routing, but rather, variations of basically the same thing.
This is the information that can be relevant for routing decisions that needs to distributed to all routers:
- Adjacencies
- Policy restrictions
- Metrics
- Reachability
- Unreachability
Link state protocol OSPF doesn't do policies, and it floods updates that convey reachability between two routers (and thus implied adjacency) along with a metric. When the reachability is lost, this information is also flooded. That means that the path the OSPF updates follow can be different from the path towards a destination.
Distance vector protocol RIP doesn't deal with the reachability between pairs of routers, but rather, the reachability towards a destination. So there is no adjacency information, nor any policy information. Rather, if there is policy, it's implemented through a filter that removes reachability information. There's also no explicit unreachability information. Unlike with OSPF, updates aren't flooded throughout the network, but propagated over the links between routers.
Because a link state protocol knows all the adjacencies and reachability of the whole network, it needs to run an algorithm like the
A distance vector protocol uses the distributed Bellman-Ford algorithm that propagates only the local notion of the best available path to the next router, so each router only has to choose between paths advertised by its neighbors.
Now let's look at BGP. BGP is definitely in the distance vector camp, but it does add a path for easy loop detection and an explicit unreachability update (withdrawal). Policy in BGP is traditionally applied locally, by simply hiding reachability and thus adjacency information from downstream neighbors.
However, a mechanism such as RPKI can be viewed as a policy distribution system. Here, the policy information isn't distributed by flooding or passing it downstream. Rather, the information is distributed out-of-band from a (more or less) central place. The internet routing registries can be viewed as central sources of adjacency information.
So we have five types of information to distribute, and three ways to distribute it (flooding, downstream, out-of-band) as well as simply not distributing and thus not using that information at all. So that's 5 x 4 = 20 possible way to accomplish routing.
Of course many of these combinations make very little sense. However, there are certainly places where we could change an existing protocol slightly and maybe gain some benefits. For instance, what if we add the idea of flooding unreachability updates to BGP? Currently, if a BGP router loses its BGP session to a neighbor, it executes the Bellman-Ford algorithm by selecting a new path. Of course if the old and the new path have the same now unreachable adjacency in common, that's not very helpful—an update replacing or withdrawing the new path will be on its way shortly. So why not add "X has lost reachability to Y" to an update, so the next router knows to look for a new path that doesn't include the X - Y adjacency?
But I don't think that we'll be able to carve out a workable new type of routing protocol from these 20 options. So link state and distance vector it is.
Permalink - posted 2019-10-15
