An analysis of convergence properties of the Border Gateway Protocol using discrete event simulation.

The Border Gateway Protocol (BGP) facilitates communication between parts of the Internet by determining paths by which data can get from one network to any other. Just as IP is used ubiquitously as an addressing scheme, BGP is used ubiquitously for the purpose of inter-network routing. As the Internet has grown, the amount of stress put on BGP has increased. For a long time, the behavior of Internet routing was studied minimally and was assumed to be working smoothly. Research eventually showed, however, that this was not the case, and that the highly dynamic nature of the Internet was taking its toll on the routing infrastructure. Though its underlying premise is a simple distributed shortest-path algorithm, the dynamic nature of the Internet, combined with some additional constraints in the protocol, has made analytical approaches to studying the protocol infeasible. Measurement-based approaches have been taken, but they are difficult to implement and have minimal leeway for allowing exploration of the protocol's behavior under different conditions. For these reasons we have taken the approach of simulation in order to begin to understand some of the complex ways in which BGP behaves. Simulation allows one to explore the protocol more fully, testing it under various conditions and modifying the protocol itself to explore the consequences of its fundamental design. We have studied BGP behavior with respect to several parameters, some external (network characteristics) and some internal (protocol characteristics). We show that there is room for improvement in the protocol, in particular with respect to convergence following changes in availability of network destinations. The rate-limiting mechanism of the protocol is a particular parameter of concern. Although it was previously thought to help improve convergence, we found that in some cases it can have drastic degrading effects. As a result of our work, we suggest ways in which BGP could be modified in practice to reduce the instability of the protocol.