This post is a follow-up to our blog last week about a small Czech provider briefly causing global Internet mayhem via a single errant routing announcement. In this incident, SuproNet (AS 47868) announced its one prefix, 184.108.40.206/21, to its backup provider, Sloane Park Property Trust (AS 29113), with an extremely long AS path. We've gotten more feedback about this entry than any other in recent memory, so we thought we'd try to answer some of the questions that were posed both here and elsewhere, as well as provide some clarification about exactly what went on. The questions we try to address include:
How could anyone be this dumb?
I'll admit that this was my first thought. And since this incident interrupted my lunch, I was only too happy to join the mob. In hindsight, my reaction was due to the fact that my router experience is largely limited to Cisco gear and their router software, known as IOS. For example, suppose SuproNet was using a Cisco and wanted to prepend their ASN (47868) an additional four times to announcements to a particular provider. They could use something like the following, where the string of x's refers to the IP address of the provider's router. Notice that I had to explicitly list 47868 four times.
neighbor xx.xx.xx.xx route-map longerisbetter out route-map longerisbetter permit 10 set as-path prepend 47868 47868 47868 47868
The is a common way of prepending in Cisco IOS, so I naturally thought, who would be so dumb as to type (or cut-and-paste or whatever) their own ASN hundreds of times into a configuration for a router? Who? The only problem with this line of reasoning is that SuproNet wasn't using a Cisco. They were apparently using a router from MikroTik, a router vendor from Latvia, as first reported in this Czech blog. MikroTik obviously targets the Czech market since they have a local language web page and domain.
So how do you prepend on a MikroTik? According to their on-line manual, you set the following variable in an appropriate configuration mode.
bgp-prepend (integer: 0..16) - number which indicates how many times to prepend AS_NAME to AS_PATH
So if SuproNet was thinking "Cisco IOS", they might have typed "bgp-prepend 47868" to prepend 47868 once. However, this would be a mistake as this router is expecting a count, not an ASN. So at this point, it would be reasonable to expect the MikroTik to report something like "value out of range". Let's assume they didn't do any range checking on the input value and let's assume they devoted one byte (8 bits) to store this value. One byte can represent all integers from 0 to 255. So what happens when you try to stuff something larger, like 47868, into one byte? You get 47868 modulo 256 (i.e., the remainder after dividing of 47868 by 256), which equals 252. As Mikael Abrahamsson first noticed, this was the exact number of prepends of 47868 he was seeing. So I went back and looked at the copious number of announcements we saw of SuproNet's prefix and guess what? Every single one had 252 prepends of 47868, leading me to conclude that this was the exact number sent out by SuproNet. Originally I was thinking the number of prepends probably varied based how these long paths were being truncated and that it was this random truncation that was causing part of the problem.
And using this clue, Ivan Pepelnjak was able to spell out exactly what happened in his blog. As it turns out, the reason for all those routing resets and general instability was due to a previously unknown Cisco bug involving AS paths close to 255 in length. If you try to prepend to a long path that you receive and by doing so, create a path longer than 255, you are toast. So the maps we gave in our our last blog were more of an indication of Cisco market share (at least among prependers), rather than the propensity of outdated routers. Kudos to Ivan for figuring this out.
In summary, we have a situation where a single careless operator in the Czech Republic tickled one bug (i.e., lack of bounds checking in the MikroTik router) that in turn tickled another bug (i.e., a problem with long AS paths on a Cisco). And the result was global Internet instability due to prevalence of Cisco gear in the market. But in fairness to MikroTik we note that Mathias Sundman observes that bounds checking does now exist in version 3.20 of their router software.
Why did this cascade throughout the planet?
Short answer: There is a bug in Cisco IOS with regard to long AS paths and lots of folks use Cisco gear. Longer answer: Most ISPs apparently do not filter out announcements with long AS paths. As we noted in our previous blog on this topic, we are all fairly close to one another on the Internet and there is really no reason to be seeing excessively long AS paths. Such paths only indicate a problem or a clueless operator or both, and can be safely discarded. The fact that they were not dropped allowed them to tickle this bug on many Cisco boxes along the way.
Since we are all just a few AS hops away from each other, the problem only occurred because the paths originated from SuproNet were so close to 255. This allowed them to reach the core of the Internet and continue onto other edge networks before exceeding the 255 path length boundary. It was only when they did that all hell broke loose, far away from the original source of the problem. As Andree Toonk provides on this page, there are apparently others who have made the same mistake on MikroTik routers. AS 20912, Panservice of Italy, is doing it as of this writing, but 20912 modulo 256 is only 176 and these announcements are apparently not causing a problem.
Can you provide more details about the impact and its spread?
This was an easy one, as Renesys monitors every prefix (network) seen on the Internet and computes their stability over time. We also geo-locate them as accurately as possible. Thus we can see events like this propagate through the planet and Google Earth provides an excellent way of performing the visualization. We used it to show every newly unstable prefix in during the hour before and the hour of the incident. Here are a few composite images taken from Google Earth of a few regions and an indication of all the unstable prefixes seen during the 2 hour period. We start with the US where the impact was the greatest.
Next up is the heart of South America, where Cisco obviously needs to send some sales folks. (Before someone points out the population density of South America relative to the US, we noted in our last blog that South America was the least impacted continent on a percentage basis.)
Finally, we take a look at Europe, where all the trouble started.
How do we prevent this from happening again?
This one is really about assigning blame and there is plenty to go around. But before we get too caught up with that, keep in mind that this was really the perfect storm. As of today, Renesys has observed 31,188 unique non-private ASNs on the Internet over the last few weeks. If you compute modulo 256 of each of them, you get 731 with associated values ≥ 250 or 2.3% of the total. There is nothing special about 250. However, the likelihood of a problem decreases significantly as the values get lower, and 250 seems like a reasonable cutoff, given typical path lengths in the Internet. And there are still only 1,919 ASNs whose modulo 256 value is ≥ 240, or 6.2% of the total. Thus for this event to have occurred at all, besides the bugs in the router software of two vendors, only a few percent of the ASes on the Internet could have possibly initiated the meltdown, but only if they had a careless operator and an obscure Latvian router with outdated software. How likely was that?
As for the blame, network operators (SuproNet) should obviously read their router documentation and test any proposed changes in a lab environment to see if they get the results they expect. Router vendors should check bounds on input parameters (MikroTik) and on boundary conditions (Cisco). ISPs should filter out obvious useless garbage, like ridiculously long AS paths and unrouteable (private) IP addresses. They obviously don't, given the scope of the event. And who designed this BGP routing protocol anyway? What were they thinking?
Seriously, the reason for the success of the Internet is because it is not under the control of any one government or company. Because of this fact, it is both cheap and ubiquitous. But because there is no centralized control or authority, we are largely at the mercy of the weakest link. Sure there is plenty we can do to prevent things like this from happening again, but there will always be the next perfect storm. Who could have guessed something like this could have happened? You won't be able to guess the next one either. The happy ending to this story is that the community quickly rallied and worked together to both identify and mitigate the problem. No meetings were held, no bailouts were requested and not a single lawyer was needed to draft an agreement. The Internet was back to normal in short order.