Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2009.04.001 Byline: Anat Bremler-Barr (a), Nir Chen (a), Jussi Kangasharju (b), Osnat Mokryn (c), Yuval Shavitt (d) Keywords: Routing protocols; BGP; Convergence; Path exploration Abstract: 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) to O(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. Author Affiliation: (a) School of Computer Science, The Interdisciplinary Center, Herzliya, Israel (b) University of Helsinki, Finland (c) School of Computer Science, Tel Aviv-Yaffo College, Israel (d) School of Electrical Engineering, Tel Aviv University, Israel Article History: Received 19 February 2008; Revised 26 December 2008; Accepted 7 April 2009 Article Note: (miscellaneous) Responsible Editor: T. Korkmaz

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.comnet.2005.11.010 Byline: Danny Dolev (a), Sugih Jamin (b), Osnat (Ossi) Mokryn (c), Yuval Shavitt (c) Keywords: Directed graph; AS relationships; Valley free routing Abstract: We investigate the resiliency of the Internet at the Autonomous System (AS) level to failures and attacks, under the real constraint of business agreements between the ASs. The agreements impose policies that govern routing in the AS level, and thus the resulting topology graph is directed, and thus the reachability between Ases is not transitive. We show, using partial views obtained from the Internet, that the Internet's resiliency to a deliberate attack is much smaller than previously found, and its reachability is also somewhat lower under random failures. We use different metrics to measure resiliency, and also investigate the effect of added backup connectivity on the resiliency. Author Affiliation: (a) School of Engineering and Computer Science, The Hebrew University, Jerusalem 91904, Israel (b) Department of EECS, University of Michigan, Michigan, United States (c) School of Electrical Engineering, Tel Aviv University, Ramat Aviv 69978, Israel Article History: Received 4 August 2004; Revised 26 June 2005; Accepted 7 November 2005 Article Note: (miscellaneous) Responsible Editor: J. Hou