Learning network structure from passive measurements

ABSTRACT

The ability to discover network organization, whether in the form of explicit topology reconstruction or as embeddings that approximate topological distance, is a valuable tool. To date, network discovery has been based on active measurements. However, it is feasible to envision passive discovery of network topology and distance, simply by monitoring packet traffic. Unfortunately, the lack of explicit control over the choices of which endpoints are measured means that passive network discovery must deal with the problem of missing information. We consider one such example, namely reconstructing embeddings and some network structure information from unwanted network traffic captured at a set of honeypots. We develop a number of algorithms for reconstruction of missing measurements. Our algorithms use insights derived from the known topology of the Internet as well as local imputation techniques from approximation theory. We characterize the degree to which missing information can be reconstructed and show that a limited but useful amount of reconstruction is possible, allowing the recovery of network embeddings and some topological relationships from passively collected data.

REFERENCES

• 1: 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]
• 2: 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.
• 3: 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]
• 4: CAIDA. The Skitter Project. http://www.caida.org/tools/measurement/skitter/,2007.
• 5: 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
• 6: Benoit Donnet , Philippe Raoult , Timur Friedman , Mark Crovella, Efficient algorithms for large-scale topology discovery, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 7: 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]
• 8: 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.
• 9: R. Govindan and H. Tangmunarunkit. Heuristics for Internet Map Discovery. In Proceedings of IEEE INFOCOM '00, Tel Aviv, Israel, March 2000.
• 10: 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]
• 11: C. Jin, H. Wang, and K. Shin. Hop-Count Filtering: An Effective Defense Against Spoofed Traffic. In Proceedings of IEEE INFOCOM '03, San Francisco, CA, April 2003.
• 12: 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]
• 13: J. Ledlie, P. Gardner, and M. Seltzer. Network Coordinates in the Wild. In Proceedings of USSENIX Network Systems Design and Implementation (NSDI'07), San Jose, CA, April 2007.
• 14: E. Ng and H. Zhang. Predicting Internet Network Distance with Coordinate-based Approaches. In Proceedings of IEEE INFOCOM '02, New York, NY, April 2002.
• 15: 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]
• 16: 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
• 17: Y. Shavitt and T. Tankel. Hyperbolic Embedding of Internet Graphs for Distance Estimation and Overlay Construction. IEEE/ACM Transactions on Networking, To Appear.
• 18: 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
• 19: 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]
• 20: 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.
• 21: H. Zheng, E. Lua, M. Pias, and T. Griffin. Internet Routing Policies and Round Trip Times. In Proceedings of The Passive and Active Measurement Workshop, Boston, MA, April 2005.

INDEX TERMS

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

General Terms:
Measurement

Keywords:
embedding, imputation, inference, measurement, topology