We have identified unwanted behavior in the routing eco system caused by BGP communities,
in particular, during path exploration events:
Around 60% of communities become visible as a result of prefix withdrawals at the origin.
We are able to reconstruct that behavior in controlled laboratory experiments where we test Cisco, Juniper and Nokia routers,
as well as the routing daemons BIRD, FRRouting, Quagga, and OpenBGPD.
It is well-known that intra-AS changes can lead to updates with no AS path change and even full duplicates.
In observation A and observation B,
we highlight the impact of BGP communities.
While our observations base on router messages provided by RIPE and RouteViews, as well as on laboratory experiments,
the root causes for observation B specifically, are hard to determine.
We show, that BGP communities alone, when filtered at egress, can be responsible for this behavior, as demonstrated in Experiment 3.
In the laboratory experiments we find that
Junos, SR OS, and OpenBGPD (v6.6) detect duplicate routes (probably in Adj-RIB-Out) and suppress them, while
IOS, BIRD, FRRouting (v6.0.2), Quagga, and OpenBGPD (v5.2) generate duplicates.
It is well known that BGP, as a distance vector protocol, suffers from path exploration:
For every withdrawn route (or AS path), the next best, supposedly valid route is selected and announced, until there are no more candidates left in the router's RIB.
We hypothesize that the same route can be announced multiple times during path exploration,
if it is associated with multiple, unique community sets.
This effect becomes particularly pronounced with routes that are tagged with different inbound locations,
e.g., at large ASes.
We provide an example in observation A.
Moreover, we observe a similar update behavior where BGP communities are completely absent,
as can be seen in observation B.
We speculate that, analogously to observation A, the router enters the path exploration phase,
however, before the alternative paths are announced the community attribute is emptied at egress.
Thus, ASes can generate multiple identical announcement with empty community attributes.
Since in both observations the destination prefix is not reachable anyways,
we conclude that BGP communities unnecessarily increase the message overhead during path exploration.
Moreover, it discloses potentially sensitive information that would not have become visible otherwise, e.g., the number and locations of peerings.
Next, we look at a real example:
Table 1 shows announcements and withdrawals over the day of March 15, 2020,
for the beacon prefix 18.104.22.168/24 via AS path (20205 3356 174 12654),
at a single BGP session (22.214.171.124 at rrc00).
We note that all the announcements occured during the six fixed withdrawal phases of that beacon prefix.
Thus, the AS path (20205 3356 174 12654) becomes active only for around a minute during path exploration.
By manually checking the meaning of the community values, we find almost all of them to encode geographical information, see Table 4.
Note that AS20205 re-announces routes that were tagged by AS3356.
We conclude that due to the existence of multiple, distinct community sets for the same route,
the number of announcements during path exploration is increased.
|Table 1: Community changes for path (20205 3356 174 12654)|
|time (UTC)||community sets|
|1584237652||3356:3 3356:22 3356:86 3356:575 3356:666 3356:2059|
|1584237659||3356:3 3356:86 3356:575 3356:666 3356:2008|
|1584237660||3356:3 3356:22 3356:86 3356:575 3356:666 3356:2011|
|1584252030||3356:3 3356:86 3356:575 3356:666 3356:2008|
|1584252031||3356:3 3356:22 3356:86 3356:575 3356:666 3356:2052|
|1584252066||3356:3 3356:86 3356:575 3356:666 3356:2010|
|1584252074||3356:3 3356:86 3356:575 3356:666 3356:2013|
|1584266437||3356:3 3356:22 3356:86 3356:575 3356:666 3356:2052|
|1584266442||3356:3 3356:86 3356:575 3356:666 3356:2057|
|1584266451||3356:2 3356:22 3356:86 3356:511 3356:666 3356:2082|
|1584280839||3356:3 3356:86 3356:575 3356:666 3356:2008|
|1584280844||3356:3 3356:86 3356:575 3356:666 3356:2057|
|1584280877||3356:3 3356:86 3356:575 3356:666 3356:901 3356:2022|
|1584295230||3356:3 3356:86 3356:575 3356:666 3356:2008|
|1584295230||3356:3 3356:22 3356:86 3356:575 3356:666 3356:2052|
|1584295255||3356:3 3356:86 3356:575 3356:666 3356:2057|
|1584295266||3356:3 3356:86 3356:575 3356:666 3356:2010|
|1584309659||3356:3 3356:86 3356:575 3356:666 3356:2057|
|1584309664||3356:3 3356:86 3356:575 3356:666 3356:2013|
Looking into the wild, Table 2 shows announcements and withdrawals for the same day (March 15, 2020)
and the same beacon prefix 126.96.36.199/24,
as in observation A.
However, we look at a slightly different AS path: (20811 3356 174 12654) via BGP session (188.8.131.52 / rrc10).
Note that except for the left-most AS, the AS path is the same as in observation A.
Again, all the announcements occur only during the six fixed withdrawal phases of that beacon prefix, i.e., a short time period during path exploration.
We confirm that attributes other than the community attribute also show no changes at the collector.
Due to the lack of ground truth information, we can only speculate as for the root cause leading to these duplicate announcements.
We believe that the series of announcements can indeed be triggered by multiple communities associated with a single route (as in observation A).
While we do not exclude the possibility for other reasons, like internal changes, misconfiguration or rate limiting,
here are some arguments to consider:
We know that AS3356 tags routes based on the ingress location.
However, at the same time we observe routes coming from AS20811 with an empty community attribute in >99% of the cases.
It is therefore conceivable that AS20811 removes communities prior to re-announcing routes learned from AS3356.
Moreover, the temoporal pattern is indicative of a repeating and limited event, like that of a beacon withdrawal.
We argue that the particularity of our observations correlate with those in observation A and, more importantly, can be observed at many ASes.
Finally, we are able to recreate this behavior in controlled laboratory experiments using Cisco routers, BIRD, FRRouting (v6.0.2), Quagga and OpenBGPD (v5.2).
We perform a series of controlled experiments
in a setup as depicted in Figure 3.
For each run of the experiments, we configure all routers to use
Cisco IOS (12.4(20)T and XR 6.0.1),
Juniper Junos (Olive 12.1R1.9 April, 2012),
Nokia SR OS (20.7.R2), as well as the routing daemons
BIRD (v1.6.6 and v2.0.7), FRRouting (v6.0.2), Quagga (v.1.2.4), and OpenBGPD (v5.2 and v6.6),
each with default settings.
|Figure 3: Lab Experiment|
Assume a converged network.
In order to induce updates for prefix p, we disable the link between Y1 and Y2, and wait for arriving updates at collector C1.
Below and in Table 3 we provide a (very brief) summary of our experiments and the results.
Note that most routers behave in the same way in all experiments, i.e., they forward communities by default and generate duplicates.
We observe some exceptions related to the generation of duplicates due to changes in the next-hop (Junos and SR OS) and cleaning communities at egress (Junos, SR OS and OpenBGPD v6.6),
as well as the default forwarding of communities (IOS).
We show in these experiments that the use of BGP communities can trigger unnecessary updates if not filtered properly, i.e., at ingress (Exp4).
- Experiment 1: To evaluate the default behavior, no communities are configured. Y1 generates duplicates (all except Junos and SR OS) due to next-hop change, X1 ignores duplicates. No updates observed at C1.
- Experiment 2: Incoming routes are tagged at ingress (by Y2 and Y3) and forwarded by X1 (all except IOS forward communities by default). Update with new community observed at C1.
- Experiemnt 3: X1 filters communities at egress. Update without community observed (duplicates) at C1; no duplicates observed with Junos, SR OS and OpenBGPD (v6.6).
- Experiemnt 4: X1 filters communities at ingress. No updates observed at C1 with all router implementations.
|Table 3: Overview of experiments and results.|
||Exp1: Y1 sends dups (next-hop change)
||Exp2: X1 forwards communities sent by Y1
||Exp3: X1 filters at egress, sends dups
||Exp4: X1 filters at ingress, no dups generated
|Nokia SR OS|
|*duplicate suppression can be enabled by setting 'export table on;', see router configurations.|
|**patch fixes the sending of duplicates in Exp1 and Exp3 and will be available in next release 7.6. backports possible.|
If you are interested in more details, we kindly refer you to the paper.
BGP community is a transitive attribute used to tag prefix aggregates and is propagated in BGP updates. The community attribute can include multiple communities.
While communities are 32-bit integers, they are typically represented in the form x:y, where x is the ASN that adds this community, and y is the community value itself.
We differentiate between two broad types: (a) action community, instructing a receiving router to perform a specific action associated with the community value, e.g. blackholing, and (b) informational community, informing other ASes about certain characteristics of a route, e.g., the location at which it has been learned.
Path Exploration describes the behavior of a BGP router announcing alternative routes (or paths)
towards a prefix that has been withdrawn globally, but not yet by all local neighbors.
This is an inherent problem to distance vector protocols, such as BGP.
A BGP router can store multiple routes (via different AS paths) to the same destination prefix in the RIB.
When the origin AS withdraws a prefix, all possible paths are invalidated as the withdrawal messages propagate through the AS graph. With every withdrawn route, the router selects and announces a new best path based on the remaining routes in the RIB. When there is no more route abailable, a withdrawal message is sent.
Beacon Prefixes are announced and withdrawn at specific periodic intervals.
This can help network operators and researchers investigate
the behavior of the routing system as well as anomalies.
RIPE operates such routing beacons with an update pattern of a single announcement every 4 hours,
starting at 00:00 UTC, and a single withdrawal every 4 hours, starting at 02:00 UTC .