Unnecessary Updates?
Welcome
The goal of this website is to provide the knowledgeable audience access to our current research. If you are new to this website, we recommend to have a quick look at the introduction. If you are interested in the full technical details, please don't hesitate to read our paper.
In short: We have identified unwanted behavior in the routing eco system that has to do with the propagation of BGP communities, in particular, during path exploration events. We are able to reconstruct that behavior in controlled laboratory experiments using Cisco, Juniper and Nokia routers, as well as the routing daemons BIRD, FRRouting, Quagga, and OpenBGPD.
However, certain aspects regarding our findings remain unclear for which we hope to get some feedback and possibly even insights. And this is where we need your help:

  1. While it is well-known that intra-AS changes can lead to updates with no AS path change and even full duplicates, in our work we highlight the impact of BGP communities at a large scale. Are you, as the networking community, aware of this large-scale behavior, as shown in observation A and observation B?
  2. 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. Can you confirm our observation in your own network(s) / your data?
  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. Is latter behavior intentional, per default?
We would like to thank everybody for your interest. For any questions and feedback, please don't hesitate to contact us:

communityexploration AT cmand DOT org

Updates

Last modified: December 03 2020 19:20 (UTC)

Introduction
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.

Observation A
In the following, we present an example of consecutive announcements with changing community attributes for a fixed route / path. Figure 1 below illustrates our observation. The colors indicate different routes and the shapes different communities. The middle AS (X) re-announces multiple tagged, blue routes.
Figure 1: No filtering.
Next, we look at a real example: Table 1 shows announcements and withdrawals over the day of March 15, 2020, for the beacon prefix 84.205.64.0/24 via AS path (20205 3356 174 12654), at a single BGP session (64.246.96.5 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
02:00
15842376523356:3 3356:22 3356:86 3356:575 3356:666 3356:2059
15842376593356:3 3356:86 3356:575 3356:666 3356:2008
15842376603356:3 3356:22 3356:86 3356:575 3356:666 3356:2011
1584237687[withdrawal]
06:00
15842520303356:3 3356:86 3356:575 3356:666 3356:2008
15842520313356:3 3356:22 3356:86 3356:575 3356:666 3356:2052
15842520663356:3 3356:86 3356:575 3356:666 3356:2010
15842520743356:3 3356:86 3356:575 3356:666 3356:2013
1584252076[withdrawal]
10:00
15842664373356:3 3356:22 3356:86 3356:575 3356:666 3356:2052
15842664423356:3 3356:86 3356:575 3356:666 3356:2057
15842664513356:2 3356:22 3356:86 3356:511 3356:666 3356:2082
1584266505[withdrawal]
14:00
15842808393356:3 3356:86 3356:575 3356:666 3356:2008
15842808443356:3 3356:86 3356:575 3356:666 3356:2057
15842808773356:3 3356:86 3356:575 3356:666 3356:901 3356:2022
1584280880[withdrawal]
18:00
15842952303356:3 3356:86 3356:575 3356:666 3356:2008
15842952303356:3 3356:22 3356:86 3356:575 3356:666 3356:2052
15842952553356:3 3356:86 3356:575 3356:666 3356:2057
15842952663356:3 3356:86 3356:575 3356:666 3356:2010
1584295273[withdrawal]
22:00
15843096593356:3 3356:86 3356:575 3356:666 3356:2057
15843096643356:3 3356:86 3356:575 3356:666 3356:2013
1584309665[withdrawal]
In order to obtain the above data for the 02:00 (UTC) withdrawal phase:
wget http://data.ris.ripe.net/rrc00/2020.03/updates.20200315.0200.gz;
zcat updates.20200315.0200.gz | bgpdump -m - | grep "84.205.64.0/24|20205 3356 174 12654|";

Observation B
In this example, we look at a path that exhibits consecutive announcements, however, with an always empty community attribute. Figure 2 below illustrates our observation. The colors indicate different routes and the shapes different communities. The middle AS (X) filters communities prior to re-announcing routes, e.g., at egress, which leads to duplicate blue routes.
Figure 2: Filtering at egress.
Looking into the wild, Table 2 shows announcements and withdrawals for the same day (March 15, 2020) and the same beacon prefix 84.205.64.0/24, as in observation A. However, we look at a slightly different AS path: (20811 3356 174 12654) via BGP session (217.29.66.88 / 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).


Table 2: No communities for path (20811 3356 174 12654)
time (UTC)community sets
02:00
1584237627[empty]
1584237628[empty]
1584237640[empty]
1584237647[empty]
1584237647[empty]
1584237659[empty]
1584237661[empty]
1584237688[empty]
1584237688[withdrawal]
06:00
1584252030[empty]
1584252042[empty]
1584252074[empty]
1584252077[empty]
1584252747[withdrawal]
10:00
1584266412[empty]
1584266412[empty]
1584266441[empty]
1584266444[empty]
1584266506[withdrawal]
14:00
1584280833[empty]
1584280846[empty]
1584280872[empty]
1584280877[empty]
1584280886[withdrawal]
18:00
1584295229[empty]
1584295231[empty]
1584295239[empty]
1584295239[empty]
1584295266[empty]
1584295273[empty]
1584295274[withdrawal]
22:00
1584309633[empty]
1584309633[empty]
1584309634[empty]
1584309660[empty]
1584309664[empty]
1584309691[withdrawal]
In order to obtain the above data for the 02:00 (UTC) withdrawal phase:
wget http://data.ris.ripe.net/rrc10/2020.03/updates.20200315.0200.gz;
zcat updates.20200315.0200.gz | bgpdump -m - | grep "84.205.64.0/24|20811 3356 174 12654|";


Laboratory Experiments
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.
  • 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.
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).
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
Cisco IOS
12.4(20)Ttruefalsetruetrue
XR 6.0.1truefalsetruetrue
Juniper Junos
Olive 12.1R1.9falsetruefalsetrue
Nokia SR OS
20.7.R2falsetruefalsetrue
BIRD
v1.6.6truetruetruetrue
v2.0.7*truetruetruetrue
*duplicate suppression can be enabled by setting 'export table on;', see router configurations.
FRRouting
v6.0.2truetruetruetrue
v7.6-dev**falsetruefalsetrue
**patch fixes the sending of duplicates in Exp1 and Exp3 and will be available in next release 7.6. backports possible.
OpenBGPD
v5.2truetruetruetrue
v6.6truetruefalsetrue
Quagga
v1.2.4truetruetruetrue
If you are interested in more details, we kindly refer you to the paper.


Router Configurations
In the following, we provide configurations for router X1 in Experiment 3, where we test the generation of duplicates when communities are filtered at egress.

Routers: C1 - X1 - (Y1, Y2, Y3) - Z1
ASes: 65001 - 65002 - 65003 - 65004

AS 65002 imports routes from 65003 and exports to 65001. 65002 is configured to filter all communities upon exporting routes. The configuration of the other routers are trivial.
Juniper routing-options { autonomous-system 65002; } protocols { bgp { group external-peers { type external; neighbor 10.12.0.1 { export strip; peer-as 65001; } neighbor 10.23.0.2 { peer-as 65003; } } } } policy-options { policy-statement strip { term stripper { then { community delete wild; } } } community wild members *:*; }
Cisco IOS XR community-set all *:* end-set route-policy nofilter pass end-policy route-policy egressfilter delete community in all pass end-policy router bgp 65002 bgp router-id 10.12.0.2 address-family ipv4 unicast neighbor 10.12.0.1 remote-as 65001 address-family ipv4 unicast send-community-ebgp route-policy egressfilter out neighbor 10.23.0.2 remote-as 65003 address-family ipv4 unicast
FRRouting router bgp 65002 neighbor 10.12.0.1 remote-as 65001 neighbor 10.23.0.2 remote-as 65003 address-family ipv4 neighbor 10.12.0.1 route-map EXPORT out neighbor 10.23.0.2 route-map IMPORT in exit-address-family access-list all permit any route-map IMPORT permit 1 match ip address all !!cleaning at ingress ! set community none route-map EXPORT permit 1 match ip address all !!cleaning at egress set community none
Quagga router bgp 65002 neighbor 10.12.0.1 remote-as 65001 neighbor 10.23.0.2 remote-as 65003 address-family ipv4 neighbor 10.12.0.1 route-map EXPORT out neighbor 10.23.0.2 route-map IMPORT in exit-address-family access-list all permit any route-map IMPORT permit 1 match ip address all !!cleaning at ingress ! set community none route-map EXPORT permit 1 match ip address all !!cleaning at egress set community none
Nokia SR OS (Classic CLI) policy-options begin community "delete" members ".*:.*" exit policy-statement "clean_egress" entry 1 from protocol bgp exit action accept community remove "delete" exit exit exit commit exit bgp group "external" family ipv4 export "clean_egress" neighbor 10.12.0.1 peer-as 65001 exit neighbor 10.23.0.2 peer-as 65003 exit exit no shutdown exit
Cisco IOS router bgp 65002 neighbor 10.12.0.1 remote-as 65001 neighbor 10.12.0.1 send-community neighbor 10.12.0.1 route-map CLEAN out neighbor 10.23.0.2 remote-as 65003 route-map CLEAN permit 10 set community none
BIRD filter clean_egress { bgp_community.delete([(65003,*)]); accept; } protocol bgp peering_c1 { local 10.12.0.2 as 65002; neighbor 10.12.0.1 as 65001; # uncomment for bird2 # ipv4 { import all; export filter clean_egress; # }; } protocol bgp peering_y1 { local 10.23.0.1 as 65002; neighbor 10.23.0.2 as 65003; # uncomment for bird2 # ipv4 { # bird2, keep rib-out state # export table on; import all; export all; # }; }
OpenBGPD AS 65002 nexthop qualify via default neighbor 10.12.0.1 { remote-as 65001 ## uncomment for openbgpd 5.2 # announce all } neighbor 10.23.0.2 { remote-as 65003 } ## uncomment for openbgpd 6.6 allow from any allow to any # filter on egress match to 10.12.0.1 set { community delete *:* } # filter on ingress #match from 10.23.0.2 set { community delete *:* }


How to find unnecessary announcements?
In the following we show how to classify announcements based on changes in the AS path and community attribute. All you need is one or more MRT update files, e.g., from RIPE or RouteViews, the bgpdump tool and a little bit of perl code.
The following commands download and process an update file. # download a MRT update file; here from RIPE collector rrc00: wget http://data.ris.ripe.net/rrc00/2020.03/updates.20200315.0200.gz; # pipe MRT update file to # bgpdump (-m "one-line per entry with unix timestamps") and then to the # classification script announcementTypes.sh: zcat updates.20200315.0200.gz | bgpdump - -m | ./announcementTypes.sh | less

The script announcementTypes.sh contains Perl code that annotates the bgpdump output with one of the following announcement types:

pn - path change (p) and no community change (n)
pc - path change (p) and community change (c)
nn - no path change (n) and no community change (n)
nc - no path change (n) and community change (c)

or init if it is the initial announcement.

The output format is as followed:

Peer ASN|Peer IP|Prefix|timestamp|A/W|AS Path|Community set|type

Note: To keep this guide simple, here we omit xn and xc, two announcement types which capture the inflation or deflation of AS paths. Also, the simple code does not sanitize or preprocess the data in any way. Artifacts like unallocated ASNs or prefixes need to be handled separately. Please refer to the paper where we detail our data processing steps and methodology.

announcementTypes.sh #!/bin/bash perl -lane ' BEGIN{$peer="";$aw="";$asp="";$com="";} # expected input fields: # 0 BGP Protocol # 1 timestamp # 2 A/W (announcement/withdrawal) # 3 Peer IP # 4 Peer ASN # 5 Prefix # 6 AS Path # 7 Origin Protocol # 8 Next Hop # 9 LocalPref # 10 MED # 11 Community set # 12 Atomic Aggregator # 13 Aggregator # output fields # 0 Peer ASN # 1 Peer IP # 2 Prefix # 3 timestamp # 4 A/W # 5 AS Path # 6 Community set # 7 Type (pn, pc, nn, nc or "init") my @x = split /\|/; # consider announcements and withdrawals only if( $x[2] != "A" && $x[2] != "W" ) { next; } # group announcement by Peer AS, Peer IP and Prefix my $key = $x[4]."|".$x[3]."|".$x[5]; my @data = ($x[1],$x[2],$x[6],$x[11]); push( @{ $y{$key} }, \@data ); END { foreach $k (keys %y) { foreach $v ( @{$y{$k}} ) { if( $k ne $peer || @$v[1] ne $aw ){ print "$k|@$v[0]|@$v[1]|@$v[2]|@$v[3]|init"; $peer=$k; $aw=@$v[1]; $asp=@$v[2]; $com=@$v[3]; } else { # determine AS path and community attribute change if( $asp ne @$v[2] ) { $type="p"; } else { $type="n"; } if( $com ne @$v[3] ) { $type.="c"; } else { $type.="n"; } print "$k|@$v[0]|@$v[1]|@$v[2]|@$v[3]|".$type; $asp=@$v[2]; $com=@$v[3]; } } } } '


Background
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 [2].


Appendix

Table 4: Community dictionary [1]
communitymeaning
3356:2Europe
3356:3North America
3356:22[unknown]
3356:86[unknown]
3356:666Peer route
3356:901[unknown]
3356:575USA
3356:511Austria
3356:2008Dallas
3356:2010New York City
3356:2011San Jose
3356:2013Atlanta
3356:2022Miami
3356:2052Toronto
3356:2057Washington DC
3356:2059[unknown]
3356:2082Vienna


References
[1] https://onestep.net/communities/as3356/
[2] https://www.ripe.net/analyse/internet-measurements/routing-information-service-ris/current-ris-routing-beacons