Advertising Multiple Paths in BGP (BGP-Addpath)

The BGP advertisement of a prefix with new attributes replaces the previous announcement of that prefix. This behavior is known as an Implicit Withdraw, which effectively prevents the advertisement of multiple paths for the same prefix. The RFC7911 discusses a BGP extension that allows the advertisement of multiple paths (ADD-PATH) for the same prefix (NLRI). This extension helps reduce route oscillations (RFC3345) and achieve faster re-convergence, as an alternative path is immediately available when a primary path fails.  

BGP peers indicate their support for the ADD-PATH capability by exchanging BGP OPEN messages with a capability set to: Support for additional path (code 69) for each Address Family Identifier (AFI) and Subsequent Address Family Identifier (SAFI). Based on the value set in a Send/Receive field, BGP sender informs a peer that it is either capable to receive multiple paths from its peer, send multiple paths to the peer or both. For instance, the BGP speaker 10.10.1.1 can both receive and advertise multiple paths (type 3) (Picture1). Value 1 in the Send/Receive field means that BGP sender is only able to install multiple paths received from its peers but it does not advertise multiple paths to its peers. Value 2 means that the sender is able to send multiple paths to the peer but installs only the best path.

Picture 1: BGP OPEN Message with Support for Additional Paths

According to RFC7911, in order for a BGP speaker to advertise multiple paths for the same prefix, a new identifier (termed “Path Identifier” hereafter) needs to be introduced. A  particular path (defined by path attributes) for an address prefix is identified by a combination of the address prefix and the Path Identifier. Therefore, the NLRI encoding inside the BGP UPDATE message (RFC4271) must be extended with the Path Identifier field. Picture 2 depicts the BGP UPDATE message with extended NLRI. The NLRI prefix 172.16.0.0/24 is identified by Path Identifier 3.

Picture 2: BGP UPDATE Message with Extended NLRI Encoding

RFC 7911 specifies that the Path Identifiers are locally assigned by the BGP speakers. They are generated automatically, with no configuration involved. However, the Path Identifier must be assigned in such a way that a BGP speaker is able to use the Prefix and Path Identifier to uniquely identify a path advertised to a neighbor. For instance, if the normal BGP IPv4 route is identified by the prefix 172.16.0.0/24, the combination of the prefix and Path ID – 172.16.0.0/24 PathId 1, 172.16.0.0/24 PathId 2, and 172.16.0.0/24 PathId 3 means that there are three different paths to reach prefix 172.16.0.0/24 (Picture 3). The BGP speaker 10.10.1.1 (XR-1) can reach prefix 172.16.0.0/24 via three unique next-hops 1.1.1.1, 1.1.1.2 and 1.1.1.3 (Picture 4).

Picture 3: BGP UPDATE Message with three NLRIs 172.16.0.0/24 and their Corresponding Path IDs

In order to illustrate the ADD-PATH capability concept, we are going to build a simple network topology (Picture 4). The objective of this topology is for XR-2 to receive multiple copies of the route 172.16.0.0/24 with redundant next hops to provide faster re-convergence in case of a failure. All network devices are Cisco routers running IOS XR (except the L2 switch on the left) in AS 64100. Routers XR-3, XR-4 and XR-5 are configured to announce the 172.16.0.0/24 network to XR-1 via iBGP. These routers are not configured to send ADD-PATH capability (support for additional paths) thus the capability is missing in OPEN messages sent to XR-1.

Picture 4: Network Topology

Router XR-1 is configured with the route-policy (RPL) backup2. It enables XR-1 to advertise all available paths (via next-hops 1.1.1.1, 1.1.1.2 and 1.1.1.3) towards the XR-2. However, XR-1 only installs the route 172.16.0.0/24 via 1.1.1.1.1 into its Routing Information Base (RIB) (Picture 5) due to the omitted keyword install in the RPL backup2. Therefore, no additional paths are installed except for the best path.

XR-1 Configuration

route-policy PASS 
 pass 
end-policy 

route-policy backup2 
 set path-selection all advertise 
end-policy 

router ospf 1 
area 0 
 interface Loopback0 
 interface GigabitEthernet0/0/0/0 
 interface GigabitEthernet0/0/0/1 
 interface GigabitEthernet0/0/0/2 
 interface GigabitEthernet0/0/0/3 

router bgp 64100 
address-family ipv4 unicast 
 additional-paths receive 
 additional-paths send 
 additional-paths selection route-policy backup2 
 redistribute connected 

neighbor 1.1.1.1 
 remote-as 64100 
 update-source Loopback0 
 address-family ipv4 unicast 
  route-policy PASS in 
  route-reflector-client 
  route-policy PASS out 

neighbor 1.1.1.2 
 remote-as 64100 
 update-source Loopback0 
 address-family ipv4 unicast 
  route-policy PASS in 
  route-reflector-client 
  route-policy PASS out 

neighbor 1.1.1.3 
 remote-as 64100 
 update-source Loopback0 
 address-family ipv4 unicast 
  route-policy PASS in 
  route-reflector-client 
  route-policy PASS out 

neighbor 10.10.1.2 
 remote-as 64100 
 update-source Loopback0 
 address-family ipv4 unicast 
  route-policy PASS in 
  route-reflector-client 
  route-policy PASS out

Picture 5: Routing Table (BGP routes only) and BGP Table of XR-1

Note: If we want XR-1 to advertise only the best path (via 1.1.1.1) and the second best path (via 1.1.1.2) towards to XR-2 and let it also install the second best path into its RIB, RPL backup2 should be changed for XR-1:

route-policy backup2 
 set path-selection backup 1 install advertise

The RIB of XR-1 after the applied change of RPL backup2 is depicted in Picture 6.

Picture 6: Routing Table of XR-1 (BGP routes only) after Installation of Second Best Path

Now, we will explain the configuration of XR-2. The router is configured with the RPL backup2 which enables XR-2 to install the best and the second best path into its RIB (Picture 7). However, this policy allows XR-2 to advertise the best route 172.16.0.0/24 via 1.1.1.1 only, as the advertisement of additional paths is not configured (the keyword advertise is missing).

Router XR-2 Configuration

route-policy PASS 
 pass 
end-policy 

route-policy backup2 
 set path-selection backup 1 install 
end-policy 

router ospf 1 
area 0 
 interface Loopback0 
 interface GigabitEthernet0/0/0/0 

router bgp 64100 
address-family ipv4 unicast 
 additional-paths receive 
 additional-paths send 
 additional-paths selection route-policy backup2 
 redistribute connected 

neighbor 10.10.1.1 
 remote-as 64100 
 update-source Loopback0 
 address-family ipv4 unicast 
  route-policy PASS in 
  route-policy PASS out

Picture 7: Routing Table of XR-2 (BGP routes only)

The BGP table of XR-2 for the prefix 172.16.0.0/24 is depicted in Picture 8. The table contains all three paths to the prefix 172.16.0.0/24 as XR-1 is configured with the RPL that ensures advertisement of all available paths (set path-selection all advertise). However, the RIB of XR-2 contains only two routes (via next-hops 1.1.1.1 and 1.1.1.2) (Picture 7). It is because the XR IOS only allows the best and the second best path advertisement for a prefix.

Picture 8: BGP Table of XR-2

Picture 9 depicts three redundant paths for 172.16.0.0/24. Path 1 with the originator 1.1.1.1 is marked as the best path. Path 2 with the originator 1.1.1.2 is marked as the backup path.

Picture 9: BGP Table of XR-2 for Prefix 172.16.0.0/24

Conclusion:

With the use of Add-paths, the convergence time can be considerably reduced, as there is an alternate or a backup path available prior to the failure of the best path. It is important to mention, however, that the BGP additional path feature increases memory utilization since the additional backup paths increase the BGP table size. Memory can be also depleted by a DoS attack, announcing multipath for the large prefixes.