Community-Triggered BGP Updates

Welcome

This website provides access to our current research on BGP communities. 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:

Keep your Communities Clean: Exploring the Routing Message Impact of BGP Communities
Thomas Krenc, Robert Beverly and Georgios Smaragdakis, In ACM CoNEXT'20

For questions and feedback, please contact us:

communityexploration AT cmand DOT org

Summary

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.

Updates

November 21 2020: FRRouting patch developed and tested.
November 9 2020: added guide to identify unnecessary announcements
November 4 2020: added router configurations
November 2 2020: paper updated.
October 27 2020: added Nokia SR OS to lab experiments.
October 26 2020: added summary of lab experiments and results.
October 24 2020: added Quagga to lab experiments.
October 17 2020: added FRRouting and OpenBGPD to lab experiments.

Last modified: February 11 2022 18:38 (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
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
1584237687	[withdrawal]
06:00
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
1584252076	[withdrawal]
10:00
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
1584266505	[withdrawal]
14:00
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
1584280880	[withdrawal]
18:00
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
1584295273	[withdrawal]
22:00
1584309659	3356:3 3356:86 3356:575 3356:666 3356:2057
1584309664	3356: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)T	true	false	true	true
XR 6.0.1	true	false	true	true
Juniper Junos
Olive 12.1R1.9	false	true	false	true
Nokia SR OS
20.7.R2	false	true	false	true
BIRD
v1.6.6	true	true	true	true
v2.0.7*	true	true	true	true
*duplicate suppression can be enabled by setting 'export table on;', see router configurations.
FRRouting
v6.0.2	true	true	true	true
v7.6-dev**	false	true	false	true
**patch fixes the sending of duplicates in Exp1 and Exp3 and will be available in next release 7.6. backports possible.
OpenBGPD
v5.2	true	true	true	true
v6.6	true	true	false	true
Quagga
v1.2.4	true	true	true	true

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]
community	meaning

3356:2	Europe
3356:3	North America

3356:22	[unknown]
3356:86	[unknown]
3356:666	Peer route
3356:901	[unknown]

3356:575	USA
3356:511	Austria

3356:2008	Dallas
3356:2010	New York City
3356:2011	San Jose
3356:2013	Atlanta
3356:2022	Miami
3356:2052	Toronto
3356:2057	Washington DC
3356:2059	[unknown]
3356:2082	Vienna

References

[1] https://onestep.net/communities/as3356/

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