Learning network structure from passive measurements
Authors:
Open Access
- 24 October 2007
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 209-214
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.Keywords
This publication has 17 references indexed in Scilit:
- Towards IP geolocation using delay and topology measurements2006
- Internet Routing Policies and Round-Trip-TimesLecture Notes in Computer Science, 2005
- Constraint-based geolocation of internet hosts2004
- Characteristics of internet background radiation2004
- Vivaldi2004
- On the Design and Use of Internet Sinks for Network Abuse MonitoringLecture Notes in Computer Science, 2004
- Hop-count filtering2003
- Measuring ISP topologies with rocketfuel2002
- IDMaps: a global Internet host distance estimation serviceIEEE/ACM Transactions on Networking, 2001
- On the marginal utility of network topology measurements2001