Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

An Analysis of Convergence Properties of the Border Gateway Protocol Using Discrete Event Simulation
Brian J. Premore
Dartmouth TR2003-452

Abstract: The Internet is an enormous internetwork formed by connecting tens of thousands of independently managed computer networks. Though the Internet has no central authority and is highly heterogeneous, a universally adopted addressing scheme---defined by the Internet Protocol (IP)---makes interaction between the individual networks possible. Complementing IP is the Border Gateway Protocol (BGP), which facilitates communication between parts of the internetwork 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 network-to-network routing.

Because BGP is universal, its well-being is the concern of everyone. In other words, when BGP suffers, everyone suffers. Even when just one instance of BGP on one router is ill-behaved, it can have global effects. Unfortunately, as the Internet has grown, the amount of stress put on BGP has increased. For a long time, the behavior of inter-domain routing was studied minimally and was assumed to be working just fine. Research eventually showed, however, that routing was not actually functioning so smoothly, and the highly dynamic nature of the Internet was taking its toll on the routing infrastructure. This discovery prompted a closer look at the behavior of BGP.

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 an address in the network. 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.

Note: This is a Ph.D. thesis. It differs from the version of the thesis which appears in the Dartmouth College library in a couple of significant ways. First, it is single-spaced. Figures have moved around in order to accommodate this change. Second, it includes some corrections. The primary correction is that some bibliography entries were reordered in order to properly alphabetize them. This has the side effect that the numbered citations throughout the document are different in this version than in the original version.

PS.Z compressed postscript .ps.Z (844KB) , PDF PDF (2388KB) (derived from the ps.Z)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Brian J. Premore, "An Analysis of Convergence Properties of the Border Gateway Protocol Using Discrete Event Simulation." Dartmouth Computer Science Technical Report TR2003-452, May 2003.

Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.