David G. Andersen
Nick Feamster
ABSTRACT
This paper describes a method of inferring logical relationships between network prefixes within an Autonomous System (AS) using only passive monitoring of BGP messages. By clustering these prefixes based upon similarities between their update times, we create a hierarchy linking the prefixes within the larger AS. We can frequently identify groups of prefixes routed to the same ISP Point of Presence (POP), despite the lack of identifying information in the BGP messages. Similarly, we observe disparate prefixes under common organizational control, or with long shared network paths. In addition to discovering interesting network characteristics, our passive method facilitates topology discovery by potentially reducing the number of active probes required in traditional traceroute-based Internet mapping mechanisms.
- "Skitter;" http://www.caida.org/tools/measurement/skitter/, 2002.Google Scholar
- Ramesh Govindan and Hongsuda Tangmunarunkit, "Heuristics for internet map discovery," in IEEE INFOCOM 2000. IEEE, Mar. 2000, pp. 1371--1380.Google Scholar
- Balachander Krishnamurthy and Jia Wang, "On network-aware clustering of Web clients," in Proc. ACM SIGCOMM, 2000. Google ScholarDigital Library
- Neil Spring, Ratul Mahajan, and David Wetherall, "Measuring ISP topologies with Rocketfuel," in Proc. ACM SIGCOMM, Aug. 2002. Google ScholarDigital Library
- Tian Bu, Lixin Gao, and Don Towsley, "On routing table growth," (Submitted for review) http://www.net.cs.umass.edu/~tbu/, 2002. Google ScholarDigital Library
- Jure Zupan, Clustering of Large Data Sets, John Wiley and Sons, Ltd., 1982.Google Scholar
- "Gnu Zebra," http://www.zebra.org/.Google Scholar
- Ratul Mahajan, David Wetherall, and Tom Anderson, "Understanding BGP misconfiguration," in Proc. ACM SIGCOMM, Aug. 2002, (to appear) http://www.cs.washington.edu/homes/ratul/bgp/bgp-misconfigs.ps. Google ScholarDigital Library
- Bela Bollobas, Random Graphs, Academic Press, London, UK, 1985.Google Scholar
- Venkata N. Padmanabhan and Lakshminarayanan Subramanian, "An investigation of geographic mapping techniques for internet hosts," in Proc. ACM SIGCOMM, 2001. Google ScholarDigital Library
- Bill Cheswick, Hal Burch, and Steve Branigan, "Mapping and visualizing the Internet," in Proc. USENIX Technical Conference, 2000. Google ScholarDigital Library
- Paul Barford, Azer Bestavros, John Byers, and Mark Crovella, "On the marginal utility of network topology measurements," in Proc. ACM SIGCOMM lnternet Measurement Workshop, Nov. 2001. Google ScholarDigital Library
- Hyunseok Chang, Sugih Jamin, and Walter Willinger, "'Inferring AS-level Internet topology from router-level path traces', in Proc. of SPIE ITCom, Aug. 2001, pp. 1, 9--24.Google Scholar
- University of Oregon, "RouteViews' http://www.routeviews.org/.Google Scholar
- Balachander Krishnamurthy and Jia Wang, "Topology modeling via cluster graphs," in Proc. ACM SIGCOMM lnternet Measurement Workshop, Nov. 2001. Google ScholarDigital Library
Index Terms
- Topology inference from BGP routing dynamics
Recommendations
ETMP-BGP: Effective tunnel-based multi-path BGP routing using software-defined networking
2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC)Border Gateway Protocol (BGP) has been the de facto inter-domain routing protocol since it was introduced. Its destination-based routing nature, which is not able to choose a specific end-to-end AS-level route, might overload some popular peering (or ...
Dynamics of hot-potato routing in IP networks
Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Dynamics of hot-potato routing in IP networks
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systemsDespite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Comments