This work is supported by Cisco URP grand and Trilogy project

The Add-Paths Analyser is a tool that evaluates the cost of enabling Add-Paths on the routers of an ISP. Based on a model of the network, it runs simulations to compare the behavior of the network using classical BGP versus the behavior of the same network using Add-Paths. Different Add-Paths selection modes can be explored and compared with each other.

Building a model of the network

The tool relies on the SimBGP simulator. A representation of a network in SimBGP needs the following configuration inputs :

• List of BGP routers
• IGP topology for hot-potato computation
• detailed iBGP organization
• List of eBGP sessions
• BGP routes: Ideally, the simulator should know all the paths received by all eBGP routers ("show ip bgp all" on each of them). A second, less recommended method is to provide only the paths known by some Route Reflectors, but this only gives a limited view of available paths. Furthermore, the path missed by this method are those subject to improved dissemination thanks to Add-Paths.

Defining a scenario

A deployment scenario consists in specifying which routers will run Add-Paths, and with which selection mode. For example, all routers can advertise two paths to each other when available. A second example scenario is to ask PE to advertise all their paths, while Route Reflectors advertise two paths.

The scenario may also specify the network event to evaluate. It can either evaluate the network state under normal operation, or the network behavior upon failure of some link.

Output of the tool

Once configured with the network model, the received eBGP routes and the Add-Paths scenario, the tool run a simulation and analysis the output of the simulator to compute a set of metrics :

• Number of messages exchanged (eBGP, iBGP, withdraws, updates) during an event
• Control plane convergence time (time between first and last BGP message) of an event
• Dataplane convergence time (time until all routers are able to forward traffic) of an event
• Number of paths in Adj-Rib-Ins
• Availability of path diversity (at least two different nexthops) for fast convergence
• Path optimality for Hot Potato Routing (IGP costs to the nexthops)

Case study : Abilene

To demonstrate the potentiality of the tool, we made an evaluation of the deployment of AddPaths on the Abilene network.

Modelisation of the network

Abilene provides information about its network on its website for the research community. Based on the map of the network, we were able to define the IGP topology model.

For the iBGP organization, instead of the original FullMesh, we used a modified topology with the routers from Chicago and NY acting as redundant Route Reflectors. Indeed, using Add-Paths is mostly relevant in network using Route Reflection.

Injecting routes into the model

We used the eBGP routes obtained from a collector in the Abilene Network. However, those routes are only the best routes of all routers. The routing state is thus incomplete, as eBGP-received, non-preferred routes were not advertised to the collector.

In order to reduce the simulation time, and as destination with only one path are not subject to improvement with Add-Paths, we filter the BGP routes to keep only those having at least two paths.

Results

Number of paths per prefix

This metric shows that on average, each router receives four paths per prefix when using Add-Paths instead of only two (one per route reflector) without. The exception is when Group Best mode is used, because only one path per advertising neighboring AS is propagated. This reveals that path diversity in Abilene comes mainly from dual-connected neighboring ASes.

Average total number of paths per router

Here, we measure the increase in terms of number of routes in the Adj-Rib-Ins. The number of routes is twice larger with Add-Paths than with normal BGP.

Lack of diversity

The metric measuring lack of diversity counts the number of routers that do not have two different nexthops for a prefix.

This figure shows that as soon as two paths are advertised by the routers thanks to Add-Paths, the number of prefixes lacking diversity because of Route Reflection or policies logically falls to zero. Fast-Convergence is thus ensured.

Here again, Group Best is not better than Normal BGP. It is thus not suited for Fast Convergence.

Nexthop optimality

This figure shows that in this particular network, using Add-Paths does not increase the optimality of Hot Potato routing.