Europe runs out of IPv4 addresses even further, what now?

▼ Less than three months ago I wrote about how the uptake of the remaining IPv4 addresses at RIPE was accelerating, with the RIPE NCC likely to run out of the addresses set aside in the "last /8" before the end of the year. And so they did, two days ago. So as of this week, it's no longer possible to request address space in the RIPE service region (Europe, former Soviet Union, Middle East) and get them within a somewhat predictable period.

In September, a million IPv4 addresses were given out every six weeks, and that rate seems to have continued. That's about a thousand /22s (blocks of 1024 IPv4 addresses), where each LIR ("RIPE member") can only get one of those. Thus, most of these blocks must have gone to new LIRs, at a rate of nearly a thousand every 30 business days, so the RIPE NCC must have been processing a new LIR, or at least a /22, every 15 minutes or so!

So what if you're in the RIPE region and you need IPv4 addresses in order to talk to the part of the internet that hasn't adopted IPv6 yet?

The RIPE NCC is not completely out of the game, so one option is to go on the waiting list.

LIRs "that have never received an IPv4 allocation from the RIPE NCC can make a request via the waiting list". So: sign up to be an LIR, put in a request, and wait for address space to become available. At that point you'll get a /24. Note that the NCC does in fact get back IPv4 address space at some rate, and there's currently nearly half a million addresses (about 2000 /24s) in quarantine, which lasts for six months if I'm informed correctly. So presumably, on average 75 /24s should become available every week over the next six months.

So it seems the game where a single organization would just sign up multiple RIPE memberships to qualify for a small block of IPv4 space multiple times can continue. However, you'll only get a quarter of the address space and there will be an unpredictable delay. So I'm thinking that the people who wanted to play that game were trying to take advantage of the /22-per-LIR policy and we're going to see less of this.

ARIN (North America) didn't have a final /8 policy, and has had a waiting list in operation for some years now. Currently, there are 160 requests on the list, and the next in line has been waiting for about six months.

The alternative is to buy IPv4 addresses on the open market. The going rate seems to be around $20 per address right now.

All of this puts a lot of pressure on IPv4 addresses for those organizations that weren't around when it was easy to get IPv4. So those organizations need to deploy address sharing techniques such as "carrier grade NAT" (CGN/CGNAT), "large scale NAT" (LSN) or stateful NAT64.

But what about IPv6? IPv6 addresses are for all intents and purposes free. However, you can't use IPv6 to communicate with a system that only has IPv4. But it makes sense to do as much as possible over IPv6 and only use translators to share IPv4 addresses when necessary. This limits the amount of address space required as well as the equipment that has to do all the NATing.

Permalink - posted 2019-11-27

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

Be gone, AS_SETs!

▼ As I was writing my RPKI path validation draft last week, I considered the issue of filtering BGP AS paths with AS_SETs in them.

For those of you who haven't read the BGP specification recently, the idea is that if a BGP router takes a bunch of prefixes and aggregates these into a single prefix, it then adds the AS numbers in the AS paths of the original prefixes to the AS path of the new prefix in the form of an AS_SET. The AS_SET has all the AS numbers in it so loops can be detected, but for the purposes of comparing the AS path length, the AS_SET counts as a single AS hop, regardless of the number of ASes in the AS_SET. (Or the router can leave out one or more ASes and then set the ATOMIC_AGGREGATE attribute instead.)

I think aggregation was added to BGP-4 as a way to start shrinking the BGP table while BGP-3 was still in use. BGP-4 added Classless Inter-Domain Routing (CIDR), allowing it to advertise (for instance) 16 class C networks to be advertised as a /20 prefix.

However, aggregation is the easy part, you also need to get rid of those original unaggregated prefixes (the 16 class C /24s in the above example). As these may also be advertised over other paths, that's very difficult. As such, there's really not much point to this type of aggregation, and thus, no point to using AS_SETs. In fact, I didn't even mention them in my book.

Turns out that I'm not the only one who feels AS_SETs are unnecessary: there's an RFC saying the exact same thing: RFC 6472.

Of course this being the internet, the fact that AS_SETs are of no use doesn't mean people don't use them. This is what I got from RouteViews just now:

>route-views>sh ip bgp | incl {
 *   5.28.128.0/20    203.181.248.168    0 7660 2516 3356 1299 12849 {12849} i
 *   5.28.144.0/22    203.181.248.168    0 7660 2516 3356 1299 12849 {12849} i
 *   5.39.176.0/21    203.181.248.168    0 7660 2516 3356 8530 {198753} i
...

There's currently 377 out of 803582 prefixes with AS_SETs in them in the global IPv4 routing table (0.046%), and 31 of 73138 in the IPv6 BGP table (0.042%).

Note that you can filter on an AS in an AS_SET with a Cisco BGP AS path regular expression like _8111_. The _ also matches the { and } that surround an AS_SET as well as the commas separating AS numbers in an AS_SET. However, if you filter a customer's AS path like this, as I always recommend:

^(65537_)+$

it won't work, as there is nothing to match the { in this regular expression. Which is fine, there's really no good reason to use AS_SETs.

Permalink - posted 2019-06-24

Path validation with RPKI draft

▼ Last week, I suggested it's time fix those BGP route leaks. I live by the words everybody complains about the weather, but nobody does anything about it, so as such I wrote an Internet-Draft with the protocol changes necessary:

draft-van-beijnum-sidrops-pathrpki-00

I think we can stop these route leaks with a relatively modest change to RPKI: by combining the ASes the origin trusts and the ASes the operator of an RPKI relying party server trusts, we have a list of all the ASes that may legitimately appear in the AS path as seen from this particular vantage point.

I believe deployment will be relatively easy, as it works for the two ASes at both ends even if ASes in the middle don't participate.

There is path filter example code in the appendix to show that this part is easy. 😀

You can see that filter code in action here:

http://bgpexpert.com/pathrpki/

I'm looking forward to hearing feedback. I've started discussions on the RIPE routing-wg mailinglist and the IETF sidrops working group mailinglist. Also feel free to mail me directly or talk to me on Twitter.

Permalink - posted 2019-06-20