URL: http://www.sds.lcs.mit.edu/papers/clustering-imw2002.html
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.3060 Entry Date: 2003-01-22 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. Datasets: Results: Presents a fully passive, BGP-based topology inference method. Prefixes are grouped based upon how frequently BGP updates for each pair of prefixes are observed within the same time window. A standard clustering algorithm is then applied to join these prefixes into successively larger groups. The authors claim that their temporal clustering produces higher-fidelity topologies than other passive, BGP-based approaches. An example of a drawback of other approaches is that many large ISPs announce a large number of prefixes under the same AS path. References: