Network discovery from passive measurements

ABSTRACT

Understanding the Internet's structure through empirical measurements is important in the development of new topology generators, new protocols, traffic engineering, and troubleshooting, among other things. While prior studies of Internet topology have been based on active (traceroute-like) measurements, passive measurements of packet traffic offer the possibility of a greatly expanded perspective of Internet structure with much lower impact and management overhead. In this paper we describe a methodology for inferring network structure from passive measurements of IP packet traffic. We describe algorithms that enable 1) traffic sources that share network paths to be clustered accurately without relying on IP address or autonomous system information, 2) topological structure to be inferred accurately with only a small number of active measurements, 3) missing information to be recovered, which is a serious challenge in the use of passive packet measurements. We demonstrate our techniques using a series of simulated topologies and empirical data sets. Our experiments show that the clusters established by our method closely correspond to sources that actually share paths. We also show the trade-offs between selectively applied active probes and the accuracy of the inferred topology between sources. Finally, we characterize the degree to which missing information can be recovered from passive measurements, which further enhances the accuracy of the inferred topologies.

REFERENCES

• 1: The Honeynet Project. http://www.honeynet.org/, 2008.
• 2: David Alderson , Lun Li , Walter Willinger , John C. Doyle, Understanding internet topology: principles, models, and validation, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1205-1218, December 2005 [doi>10.1109/TNET.2005.861250]
• 3: M. Bailey, E. Cooke, F. Jahanian, J. Nazario, and D. Watson. The Internet Motion Sensor: A Distributed Blackhole Monitoring System. In Proceedings of The Network and Distributed Security Symposium (NDSS '05), San Diego, CA, January 2005.
• 4: 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]
• 5: CAIDA. The Skitter Project. http://www.caida.org/tools/measurement/skitter/, 2007.
• 6: Mark Coates , Rui Castro , Robert Nowak , Manik Gadhiok , Ryan King , Yolanda Tsang, Maximum likelihood network topology identification from edge-based unicast measurements, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 7: Frank Dabek , Russ Cox , Frans Kaashoek , Robert Morris, Vivaldi: a decentralized network coordinate system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 8: Brian Eriksson , Paul Barford , Robert Nowak , Mark Crovella, Learning network structure from passive measurements, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298335]
• 9: Marina Fomenkov , Ken Keys , David Moore , K Claffy, Longitudinal study of Internet traffic in 1998-2003, Proceedings of the winter international synposium on Information and communication technologies, January 05-08, 2004, Cancun, Mexico
• 10: C. Fraleigh, S. Moon, B. Lyles, C. Cotton, M. Khan, D. Moll, R. Rockell, T. Seely, and C. Diot. Packet-Level Traffic Measurements from the Sprint IP Backbone. IEEE Network, 17(6), Nov.-Dec. 2003.
• 11: Paul Francis , Sugih Jamin , Cheng Jin , Yixin Jin , Danny Raz , Yuval Shavitt , Lixia Zhang, IDMaps: a global internet host distance estimation service, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.525-540, October 2001 [doi>10.1109/90.958323]
• 12: P. Francis, S. Jamin, V. Paxson, D. Bryniewicz, and Y. Jin. An Architecture for a Global Internet Host Distance Estimation Service. In Proceedings of IEEE INFOCOM '99, New York, NY, April 1999.
• 13: Z. Ghahramani and M. Jordan. Supervised Learning from Incomplete Data via the EM Approach. In Advances in Neural Information Processing, 1994.
• 14: Z. Ghahramani and M. I. Jordan. Supervised learning from incomplete data via the EM approach. Advances in Neural Information Processing Systems 6 (NIPS'94), 1994.
• 15: R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. In Proceedings of IEEE INFOCOM '00, Tel Aviv, Israel, March 2000.
• 16: Bamba Gueye , Artur Ziviani , Mark Crovella , Serge Fdida, Constraint-based geolocation of internet hosts, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028828]
• 17: Bamba Gueye , Artur Ziviani , Mark Crovella , Serge Fdida, Constraint-based geolocation of internet hosts, IEEE/ACM Transactions on Networking (TON), v.14 n.6, p.1219-1232, December 2006 [doi>10.1109/TNET.2006.886332]
• 18: Cheng Jin , Haining Wang , Kang G. Shin, Hop-count filtering: an effective defense against spoofed DDoS traffic, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948116]
• 19: Ethan Katz-Bassett , John P. John , Arvind Krishnamurthy , David Wetherall , Thomas Anderson , Yatin Chawathe, Towards IP geolocation using delay and topology measurements, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177090]
• 20: Balachander Krishnamurthy , Jia Wang, On network-aware clustering of Web clients, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.97-110, August 28-September 01, 2000, Stockholm, Sweden
• 21: B. Lyon. The opte project. http://opte.org, January 2008.
• 22: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 23: Mario A. T. Figueiredo , Anil K. Jain, Unsupervised Learning of Finite Mixture Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.3, p.381-396, March 2002 [doi>10.1109/34.990138]
• 24: Priya Mahadevan , Calvin Hubble , Dmitri Krioukov , Bradley Huffaker , Amin Vahdat, Orbis: rescaling degree correlations to generate annotated internet topologies, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 25: E. Ng and H. Zhang. Predicting Internet Network Distance with Coordinate-baseed Approaches. In Proceedings of IEEE INFOCOM '02, New York, NY, April 2002.
• 26: Packetdesign. Route Explorer. http://www.packetdesign.com/, 2008.
• 27: Ruoming Pang , Vinod Yegneswaran , Paul Barford , Vern Paxson , Larry Peterson, Characteristics of internet background radiation, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy [doi>10.1145/1028788.1028794]
• 28: Niels Provos, A virtual honeypot framework, Proceedings of the 13th conference on USENIX Security Symposium, p.1-1, August 09-13, 2004, San Diego, CA
• 29: Yuval Shavitt , Eran Shir, DIMES: let the internet measure itself, ACM SIGCOMM Computer Communication Review, v.35 n.5, October 2005 [doi>10.1145/1096536.1096546]
• 30: Yuval Shavitt , Tomer Tankel, Hyperbolic embedding of internet graph for distance estimation and overlay construction, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.25-36, February 2008 [doi>10.1109/TNET.2007.899021]
• 31: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 32: N. Spring, D. Wetherall, and T. Anderson. Reverse Engineering the Internet. In Proceedings of Hotnets-II, Cambridge, MA, November 2003.
• 33: Liying Tang , Mark Crovella, Virtual landmarks for the internet, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948223]
• 34: V. Yegneswaran, P. Barford, and D. Plonka. On the Design and Use of Internet Sinks for Network Abuse Monitoring. In Proceedings of Recent Advances on Intrusion Detection (RAID '04), Sophia, France, September 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

General Terms:
Algorithms, Measurement

Keywords:
embedding, imputation, inference, measurement, topology