Border Gateway Protocol (BGP) communities are increasingly used by Autonomous Systems (ASes) to tag routes or to facilitate more complex routing policies for customers.
Knowing which AS adds or deletes BGP communities is crucial for researchers and operators measuring the Internet and uncovering important properties of operational networks in the wild.
Previous research has used BGP communities to detect outages as well as black-holing events, and measured the implications of propagating communities on security and the update behaviour of routers.
This post highlights the challenges, methods, and results of our BGP community usage work at the Naval Postgraduate School and TU Delft during which we positively identified the community tagging behaviour of more than one in six ASes.
Sourcing wild communities
The key challenge in identifying community usage in the wild is the small number of available route collectors providing BGP data.
Communities that are stored inside the ‘Communities attribute’ are simple integers, usually represented in the form α:β (RFC 1997) and α:β:γ (RFC 8092), respectively. By convention, α represents the AS number (ASN) of the defining AS, such that every public AS can define communities without overlap.
In our research, we considered the α-value of a community as the ASN of the originating AS — only if α corresponds to a public ASN in the AS-PATH. Yet, any AS along the path can modify the attribute and its communities.
Also, some provider-defined communities are meant to be set only by their customers — action communities — to influence the default route distribution at the provider (RFC 8195). Therefore, our study focused on communities that are defined and set by provider ASes — informational communities — to inform neighbors about the origin or the ingress location of a route. We argued that while action communities are more temporarily in usage, informational communities are used to tag all incoming routes in a consistent fashion.
Another challenge is that some ASes strip communities from incoming routes or before advertising them, potentially hiding informational communities. We do not make an inference when the behaviour of an AS is completely hidden. Consequently, in addition to determining the tagging behaviour, we also determine the forwarding behaviour of an AS.
Tagging and forwarding
To infer community usage, we used the AS-PATH and the transitive community attribute in millions of BGP update messages and developed an algorithm that identifies the behaviour for each AS. The algorithm traverses all paths simultaneously from the collector peers (ASes that peer with collectors) to the origin ASes. This approach enabled us to implement the following constraints while counting and therefore reduce wrong inferences.
- It is safe to determine the tagging behaviour of collector peers: If we always observe a corresponding community, we consider it a tagging AS. If we never observe such a community, we consider it a silent AS.
- Further, to test the forwarding behaviour of a collector peer, it must be preceded by a tagging AS: If we always observe communities from the tagging AS, the collector peer is a forwarding AS. If we never see those communities, it is a cleaning AS.
- Finally, to test the behaviours of non-collector peers, in addition, all succeeding ASes in the AS-PATH must be forwarding ASes.
Tagging behaviour is prevalent among large networks
Using the extracted AS-PATH and community attributes from publicly available BGP routing information (RIPE RIS, RouteViews and Isolario), we considered around 73,000 public ASes for inference (Figure 1).
We attributed consistent tagging behaviour to around 13,000 ASes, divided into 860 tagging ASes and around 12,300 silent ASes.
Around 1,000 ASes exhibited inconsistent behaviour. For around 59,000 ASes, our conservative algorithm did not yield any inference (None).
Further, we found 271 forwarding ASes, 417 cleaning ASes, and 308 ASes that show inconsistent forwarding behaviour.
The majority of 72,000 ASes evaded our inference method. Note that more than 60,000 ASes are at the edge of the AS-level graph and thus have no forwarding behaviour to be inferred.
Finally, we obtained 523 ASes where both tagging and forwarding behaviour is inferred (full classification).
With silent-cleaner being the largest group of 251 ASes, the other groups show comparable numbers ranging between 81 and 107 ASes. Figure 2 shows the longitudinal evolution of ASes with full classification.
Over the past four years, the total numbers have increased by 30 to 90%, while their proportions have not changed. The number of ASes in each group is growing slowly, but steadily.
Consistent tagging and forwarding behaviour is common
Our findings indicate that consistent tagging and forwarding behaviour is and has been common.
While 860 tagging ASes does not sound like a lot, we found that most of those ASes are large ISPs (with a large customer cone), while the majority of silent ASes are ASes at the edge.
The slow but steady increase of fully classified ASes over time hints at the need for community-based tools in an increasingly complex routing system.
See our project website for more information, inference results and tools for reproduction. We have performed real-world experiments using the PEERING test bed as well as extensive simulations to verify the correct functioning of the algorithm and validate the inference results.
Thomas Krenc is a postdoctoral researcher at CAIDA / UC San Diego. At the time this paper was published, he was a postdoctoral research associate at the NPS.
The views expressed by the authors of this blog are their own and do not necessarily reflect the views of APNIC. Please note a Code of Conduct applies to this blog.