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:

1. Adjacencies
2. Policy restrictions
3. Metrics
4. Reachability
5. 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 shortest path first / Dijkstra algorithm on each router to calculate paths through the network.

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

Securing BGP: we can do it!

▼ In this month's edition of The ISP Column Why is Securing BGP just so Damn Hard? Geoff Huston asks himself exactly this question. He lists ten reasons. I don't agree with most of them: this is a solvable problem.

I think Geoff's main point is that BGP allows for arbitrary policies, which may lead to conflicting policies in different ASes and non-deterministic results.

And then, should we come up with new security mechanisms, it's hard to get them deployed because the business case for security (or business continuity in general, see IPv6) is hard: you need to spend money to keep what you already have.

So basically, BGP gives operators too much rope so they may end up hanging themselves. Interestingly, BGP's predecessor EGP was made to explicitly support the then (early 1980s) existing topology of the internet/ARPANET: a central backbone that all networks connect to in some way. In the early 1990s, the US government wanted to get out of the business of running the internet backbone, and BGP, which was created around that time, no longer makes any assumptions about the structure of the network.

This allows for conflicting policies, such as A trying to reach C through B, while B is trying to reach C through A. Obviously A and B can't both get what they want at the same time here.

Another ten years later, the work by Lixin Gao and Jennifer Rexford showed that if all networks apply a set of simple BGP policies that encode four different types of (business) relationships between networks, then BGP will reach a stable state. Hence their aptly titled paper Stable internet routing without global coordination.

Finally, in recent years we've realized that many unintended internet routing disruptions (route leaks) are caused by networks failing to properly translate their business relationships into BGP policies. See RFC 7908 types 1 - 4.

If we were to create BGP from scratch today, it would make sense to have baked-in policies for the four possible relationships between networks rather than expect every network operator to reinvent the wheel. The protocol can then check whether both sides of a BGP session agree on the type of relationship and alert the operators if that's not the case rather than let bad things happen. This would take care of most accidental route leaks.

However, that's not the BGP we have today. So what we need to do instead is detect those route leaks and filter out the affected routing information, see my blog post on fixing route leaks for an idea on how to extend RPKI to do this. With such an extension in place, RPKI can fix all six types of route leaks mentioned in RFC 7908.

That leaves the intentional BGP hijacks, that manipulate the BGP AS path to avoid the RPKI checks. BGPsec can fix this, but unfortunately that protocol is very heavy weight and it doesn't provide many benefits in partial deployment, so it's hard to see how the whole internet is going to adopt BGPsec.

But as more networks apply stringent (extended RPKI-based?) checks, there will be fewer and fewer places where rogue networks will be able to inject false AS paths and get away with it. Contiguous parts of the internet that perform these checks will thus be protected. That last part is crucial, because "boil the ocean" type solutions, which require the entire internet to adopt the solution before we gain any benefits, are a non-starter.

However, there is one last thing we should look at: rogue networks connecting to other networks using another network's AS number. That's a hefty investment in time and money for an attacker to be able to inject false information into BGP, but with other avenues closed this could start happening.

In conclusion: after more than two decades of experience and research, we understand BGP much better and we have a good idea of what needs to be improved. RPKI is a relatively successful example of a BGP security mechanism, while BGPsec is an example of something that's on the one hand too ambitious and on the other hand doesn't fix any immediate problems (i.e., route leaks). So I think we're in a good position to improve BGP security significantly over the next few years.

Permalink - posted 2019-09-20