Finding a Dense-Core in Jellyfish Graphs
The connectivity of the Internet crucially depends on the relationships between thousands of Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). These relationships can be modeled as a graph, called the AS-
- PDF / 471,185 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 97 Downloads / 210 Views
Abstract. The connectivity of the Internet crucially depends on the relationships between thousands of Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). These relationships can be modeled as a graph, called the AS-graph, in which the vertices model the ASes, and the edges model the peering arrangements between the ASes. Based on topological studies, it is widely believed that the Internet graph contains a central dense-core: Informally, this is a small set of high-degree, tightly interconnected ASes that participate in a large fraction of end-to-end routes. Finding this densecore is a very important practical task when analyzing the Internet’s topology. In this work we introduce a randomized sublinear algorithm that finds a densecore of the AS-graph. We mathematically prove the correctness of our algorithm, bound the density of the core it returns, and analyze its running time. We also implemented our algorithm and tested it on real AS-graph data. Our results show that the core discovered by our algorithm is nearly identical to the cores found by existing algorithms - at a fraction of the running time.
1 Introduction 1.1 Background and Motivation The connectivity of the Internet crucially depends on the relationships between thousands of Autonomous Systems (ASes) that exchange routing information using the Border Gateway Protocol (BGP). These relationships can be modeled as a graph, called the AS-graph, in which the vertices model the ASes, and the edges model the peering arrangements between the ASes. Significant progress has been made in the study of the AS-graph’s topology over the last few years. A great deal of effort has been spent measuring topological features of the Internet. Numerous research projects [14, 1, 13, 25, 35, 36, 9, 5, 4, 24, 30, 26, 7, 6, 28, 34, 32, 33, 21, 8, 29, 31] have ventured to capture the Internet’s topology. Based on these and other topological studies, it is widely believed that the Internet graph contains a central dense-core: Informally, this is a small set of high-degree, tightly interconnected ASes that participate in a large fraction of end-to-end routes. Finding this dense-core is a very important practical task when analyzing the Internet’s topology. There are several ways to define a dense-core precisely, and various corresponding algorithms and heuristics. In the next subsection we briefly survey known definitions
This work was supported by the Israel Science Foundation (grant number 89/05).
A. Bonato and F.R.K. Chung (Eds.): WAW 2007, LNCS 4863, pp. 29–40, 2007. c Springer-Verlag Berlin Heidelberg 2007
30
M. Gonen et al.
and algorithms, and shortly discuss their pros and cons. The goal of our work is to describe an algorithm that finds the dense-core (using a reasonable definition of a dense core), is amenable to rigorous mathematical analysis, and is efficient, both asymptotically and when implemented and tested on real AS data. 1.2 Defining a Dense-Core An early conceptual model for the Internet topology was
Data Loading...
