Bringing order to BGP: Decreasing time and message complexity
| Autor: | Jussi Kangasharju, Anat Bremler-Barr, Osnat Mokryn, Nir Chen, Yuval Shavitt |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Routing protocol
Computer Networks and Communications Computer science business.industry Distributed computing ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS IP forwarding 020206 networking & telecommunications 02 engineering and technology Network topology Border Gateway Protocol Convergence (routing) 0202 electrical engineering electronic engineering information engineering Default-free zone 020201 artificial intelligence & image processing The Internet Routing (electronic design automation) business Computer network |
| Zdroj: | PODC |
| ISSN: | 1389-1286 |
| DOI: | 10.1016/j.comnet.2009.04.001 |
| Popis: | The Border Gateway Protocol (BGP), the de facto routing protocol of the internet, generates excessive amount of traffic following changes in the underlying backbone. Previous papers [C. Labovitz, R. Wattenhofer, S. Venkatachary, A. Ahuja, The impact of internet policy and topology on delayed routing convergence, in: Proceedings of the INFOCOM, April 2001; C. Labovitz, A. Ahuja, A. Bose, F. Jahanianitz, Delayed internet routing convergence, in: Sigcomm, September 2000.] show that BGP suffers from high convergence delay and high message complexity after a fail down (detachment) of a network, due to path exploration caused by a limited version of the counting to infinity problem. Surprisingly, we show in this paper that BGP suffers from a high message complexity also after an up event (reattachment of a network). We analyze BGP dynamics data from raw update dumps and show that race conditions cause extensive path exploration that increases the amount of redundant updates. We show, based on these BGP dynamics, that up to 26% of the updates sent during up events are redundant. We also find that the effect of this phenomenon is bigger when the change occurs at the edge of the network. We suggest a minor modification to the waiting rule of BGP that pseudo orders the network and reduces the convergence latency of up events by half and the message complexity from O(DE )t oO(E), where D is the Diameter of the internet and E is the number of connections between ASes. Our simulation results suggest that our modification may improve the convergence messages and time during all events, with the most noted improvement of up to 36% in the number of messages and 81% in time to convergence during up events in Internet like topologies. We show that our results hold also for partial deployment of the modification in only some of the routers. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect