On the impact of route monitor selection

ABSTRACT

Several route monitoring systems have been set up to help understand the Internet routing system. They operate by gathering real-time BGP updates from different networks. Many studies have relied on such data sources by assuming reasonably good coverage and thus representative visibility into the Internet routing system. However, different deployment strategies of route monitors directly impact the accuracy and generality of conclusions.

Our work is the first to critically examine the visibility constraints imposed by the deployment of route monitors on various applications. We study the difference due to diverse deployment schemes on three important classes of applications: (1) discovery of relatively stable Internet properties such as the AS topology and prefix to origin AS mappings, (2) discovery of dynamic routing behavior such as IP prefix hijack attacks and routing instability, and (3) inference of important network properties such as AS relationships and AS-level paths. We study several simple schemes of route monitor selection and provide insights on improving monitor placement.

REFERENCES

• 1: "University of Oregon Route Views Archive Project." www.routeviews.org.
• 2: "Ripe NCC." http://www.ripe.net/ripencc/pub-services/np/ris/.
• 3: Y. He, G. Siganos, M. Faloutsos, and S. V. Krishnamurthy, "A systematic framework for unearthing the missing links: Measurements and Impact," in Proc. of NSDI, 2007.
• 4: Xenofontas Dimitropoulos , George Riley, Modeling Autonomous-System Relationships, Proceedings of the 20th Workshop on Principles of Advanced and Distributed Simulation, p.143-149, May 24-26, 2006 [doi>10.1109/PADS.2006.26]
• 5: Xenofontas Dimitropoulos , Dmitri Krioukov , Marina Fomenkov , Bradley Huffaker , Young Hyun , kc claffy , George Riley, AS relationships: inference and validation, ACM SIGCOMM Computer Communication Review, v.37 n.1, January 2007 [doi>10.1145/1198255.1198259]
• 6: G. Battista, M. Patrignani, and M. Pizzonia, "Computing the Types of the Relationships Between Autonomous Systems," in Proc. IEEE INFOCOM, March 2003.
• 7: L. Subramanian, S. Agarwal, J. Rexford, and R. H. Katz, "Characterizing the Internet hierarchy from multiple vantagepoints," in Proc. IEEE INFOCOM, 2002.
• 8: L. Gao, "On Inferring Autonomous System Relationships in the Internet," in Proc. IEEE Global Internet Symposium, 2000.
• 9: Z. Morley Mao , Lili Qiu , Jia Wang , Yin Zhang, On AS-level path inference, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 10: Wolfgang Mühlbauer , Anja Feldmann , Olaf Maennel , Matthew Roughan , Steve Uhlig, Building an AS-topology model that captures route diversity, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 11: Anja Feldmann , Olaf Maennel , Z. Morley Mao , Arthur Berger , Bruce Maggs, Locating internet routing instabilities, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 12: Xin Hu , Z. Morley Mao, Accurate Real-time Identification of IP Prefix Hijacking, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.3-17, May 20-23, 2007 [doi>10.1109/SP.2007.7]
• 13: Mohit Lad , Dan Massey , Dan Pei , Yiguo Wu , Beichuan Zhang , Lixia Zhang, PHAS: a prefix hijack alert system, Proceedings of the 15th conference on USENIX Security Symposium, p.11-11, July 31-August 04, 2006, Vancouver, B.C., Canada
• 14: Mohit Lad , Ricardo Oliveira , Beichuan Zhang , Lixia Zhang, Understanding Resiliency of Internet Topology against Prefix Hijack Attacks, Proceedings of the 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, p.368-377, June 25-28, 2007 [doi>10.1109/DSN.2007.95]
• 15: Josh Karlin , Stephanie Forrest , Jennifer Rexford, Pretty Good BGP: Improving BGP by Cautiously Adopting Routes, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.290-299, November 12-15, 2006 [doi>10.1109/ICNP.2006.320179]
• 16: Yoichi Shinoda , Ko Ikai , Motomu Itoh, Vulnerabilities of passive internet threat monitors, Proceedings of the 14th conference on USENIX Security Symposium, p.14-14, July 31-August 05, 2005, Baltimore, MD
• 17: Paul Barford , Azer Bestavros , John Byers , Mark Crovella, On the marginal utility of network topology measurements, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505204]
• 18: D. Raz and R. Cohen, "The internet dark matter: on the missing links in the as connectivity map," in Proc. IEEE INFOCOM, 2006.
• 19: Beichuan Zhang , Raymond Liu , Daniel Massey , Lixia Zhang, Collecting the internet AS-level topology, ACM SIGCOMM Computer Communication Review, v.35 n.1, January 2005 [doi>10.1145/1052812.1052825]
• 20: R. Oliveira, M. Lad, B. Zhjang, D. Pei, D. Massey, and L. Zhang, "Placing BGP Monitors in the Internet." Technical Report, UCLA CS Department, TR 060017, May 2006.
• 21: Hyunseok Chang , Ramesh Govindan , Sugih Jamin , Scott J. Shenker , Walter Willinger, Towards capturing representative AS-level Internet topologies, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.6, p.737-755, 22 April 2004 [doi>10.1016/j.comnet.2003.03.001]
• 22: Beichuan Zhang , Raymond Liu , Daniel Massey , Lixia Zhang, Collecting the internet AS-level topology, ACM SIGCOMM Computer Communication Review, v.35 n.1, January 2005 [doi>10.1145/1052812.1052825]
• 23: Wolfgang Mühlbauer , Anja Feldmann , Olaf Maennel , Matthew Roughan , Steve Uhlig, Building an AS-topology model that captures route diversity, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Experimentation, Measurement

Keywords:
bgp, internet measurement