Route Flap Damping and Adaptive Minimal Route Advertisement Interval in ns-2.34-BGP 2.0

Route Flap Damping and Policies

Route flap damping (RFD) is the occurrence where routers exchange repeated withdrawals and re-announcements of routes. RFD may cause instability of the Internet routing system. Several algorithms were proposed to address the issue of route flapping. However, because of aggressiveness of the RFD algorithms in suppressing routes, they are not widely used in the Internet. In this project, we address the issue of aggressiveness of the RFD algorithms by proposing to change value of the RFD parameter called maximum suppress value. RFD and BGP routing policies play a significant role in preserving the Internet routing stability and BGP convergence time. We also evaluate the impact of routing policies on BGP convergence time and the number of route flaps.

Flexible Load Dispersing Minimal Route Advertisement Interval (FLD-MRAI)

The Border Gateway Protocol (BGP) is an Inter-Autonomous System (AS) routing protocol currently used in the Internet. The Minimal Route Advertisement Interval (MRAI) plays a prominent role in convergence of the BGP. The previous studies have suggested using the adaptive MRAI and reusable timers to reduce the BGP convergence time. The adaptive MRAI timers perform well under the normal load of BGP update messages. However, a large number of BGP update messages may flood the Internet routers. In this thesis, we propose a new algorithm called MRAI with Flexible Load Dispersing (FLD-MRAI) that reduces the router's overhead by dispersing the load in case of a large number of BGP update messages. We examine the MRAI timers under both the normal and heavy loads of BGP update messages. The proposed algorithm is evaluated using the ns-BGP network simulator. Network topologies are derived from the BCNET BGP traffic and generated using various topology generators.

Adding Route Flap Damping and Routing Policies in ns-BGP 2.0

Download the file ns-2.34-bgp_2.0_rfd_rp.tar.gz (Details of ns-BGP 2.0 can be found here).

Unpack ns-bgp_2.0_rfd_rp.tar.gz in the "ns-2.34" directory:

> cd ~/ns-allinone-2.34/ns-2.34
> tar xvzf ns-bgp_2.0_rfd_rp.tar.gz

This will:

replace the "Makefile.in" file
replace some of the C++ files (global.h, routeinfo.h, routeinfo.cc, rtProtoBGP.h, rtProtoBGP.cc, mraitimer.h, and mraitimer.cc) under the "bgp" subdirectory
create some new C++ files (dampinfo.h, dampinfo.cc, vecroutes.h, vecroutes.cc, damp_reuse_timer.h, damp_reuse_timer.cc, processing_delay.h, processing_delay.cc, reusableMRAItimer.h, and reusableMRAItimer.cc) and policies folder under the "bgp" subdirectory
create a README file (Readme_rfd_mrai.txt) under the "bgp" subdirectory
replace a tcl file (ns-default.tcl) under the "tcl/lib" subdirectory
create some new tcl scripts for testing purposes (damping1.tcl and damping2.tcl) under the "tcl/bgp/test" subdirectory.

Note that the file "ns-2.34-bgp_2.0_rfd_rp.tar.gz" was created for ns-BGP 2.0. Make sure you have ns-2.34-BGP installed and ns-2.34-BGP-RFD added to ns-2.34-BGP before unpacking it.

Adding FLD-MRAI in ns-BGP 2.0

Download the file ns-2.34-bgp_2.0_fld_mrai.tar.gz (Details of ns-BGP 2.0 can be found here).

Unpack ns-bgp_2.0_fld_mrai.tar.gz in the "ns-2.34" directory:

> cd ~/ns-allinone-2.34/ns-2.34
> tar xvzf ns-bgp_2.0_fld_mrai.tar.gz

Recompiling ns-2

You need to recompile ns-2 before the changes take effect:

> cd ~/ns-allinone-2.34/ns-2.34
> ./configure
> ./make clean
> ./make

Configuring Route Flap Damping and Routing Policies in ns-BGP 2.0

There are two configuration commands you may use to enable the route flap damping feature for a particular BGP speaker:

1) $bgp_agent0 dampening 0 0 3000 750 900 1000 500 3600
2) $bgp_agent0 dampening

Option 1 will enable route flap damping for a particular BGP speaker using the following eight parameters:

first parameter indicates the damping algorithm used (only five values may be used here: 0, 1, 2, 3, 4 refer to original RFD, selective RFD, RFD+, modified RFD, and combined RFD, respectively)
second parameter indicates whether re-advertisement after withdrawal should be penalized (only two values may be used here: 0 implies that "re-advertisement after withdrawal is not penalized"; 1 implies that "re-advertisement after withdrawal is penalized")
third parameter is the suppress limit (3000 in the list of parameters)
fourth parameter is the reuse limit (750 in the list of parameters)
fifth parameter is the decay half life of penalty values (900 seconds in the list of parameters)
sixth parameter is the penalty for each route withdrawal (1000 in the list of parameters)
seventh parameter is the penalty for each route attribute change (500 in the list of parameters)
eighth parameter is the maximum suppress time (3600 seconds in the list of parameters)

Option 2 will enable route flap damping for a particular BGP speaker using the default values. The default values for the eight parameters are: 0, 0, 2000, 750, 900, 1000, 500, and 3600 (default Cisco settings). Therefore, the configuration command "$bpg_agent0 dampening" is equivalent to "$bgp_agent0 dampening 0 0 2000 750 900 1000 500 3600".

Please note that no error checking is performed on the values of these parameters. Changing these values to unrealistic values will most likely yield unexpected results. The default values may be found in the "ns-2.34/tcl/lib/ns-default.tcl" file.

Two additional commands are also included mainly for debugging purposes:

$bgp_agent0 show-all ;# display all feasible routes in Adj-RIB-In
$bgp_agent0 show-damping ;# display the related damping information

If you wish to enable route flap damping for all BGP speakers without configuring them individually in a tcl script, uncomment the relevant code in the rtProtoBGP constructor in the file "rtProtoBGP.cc" and modify the values of variables in the file "global.h" if necessary.

Configuring FLD- MRAI in ns-2.34-BGP 2.0

The modified DoP, computation of available CPU, duration of MRAI, and modified reusable timers are features of the FLD-MRAI algorithm that have been implemented in an existing BGP model (ns-BGP). These features are interconnected with each other. We may simply turn ON/OFF the FLD-MRAI algorithm switch in C++ rtprotoBGP class. If the FLD-MRAI algorithm switch in rtprotoBGP class is turned ON, then the modified reusable timers will be used and the modified DoP will be computed automatically. Furthermore, the cpu_timer feature should also be turned ON for calculating the available CPU. Other features such as global_MRAI and continuous_timer should be turned OFF. These variables are located at the beginning of the rtProtoBGP constructor function in the "rtProtoBGP.cc" file.

Publications and Presentations

R. Gill, R. Paul, and Lj. Trajkovic, "Effect of MRAI timers and routing policies on BGP convergence times," in Proc. 31st IEEE Int. Performance, Computing, and Communications Conference, Austin, TX, USA, Dec. 2012, pp. 314-323.

W. Shen and Lj. Trajkovic, "BGP route flap damping algorithms," Proc. SPECTS 2005, Philadelphia, PA, July 2005, pp. 488-495.
Reza Sahraei, Intergration of ns-BGP with ns-2.34 (ns-2.34-BGP) (online report), December 13, 2009.

Questions

Please email questions or bug reports related to route flap damping and policies in ns-2.34-BGP 2.0 to Ravinder Paul at rpa28 at sfu.ca.
Please email questions or bug reports related to FLD-MRAI in ns-2.34_BGP 2.0 to Rajvir Gill at rajvirg at sfu.ca.