Tag: Internet topology

Categories
Papers Publications

New conference paper “Towards Geolocation of Millions of IP Addresses” at IMC 2012

The paper “Towards Geolocation of Millions of IP Addresses” was accepted by IMC 2012 in Boston, MA (available at http://www.isi.edu/~johnh/PAPERS/Hu12a.html).

From the abstract:

Previous measurement-based IP geolocation algorithms have focused on accuracy, studying a few targets with increasingly sophisticated algorithms taking measurements from tens of vantage points (VPs). In this paper, we study how to scale up existing measurement-based geolocation algorithms like Shortest Ping and CBG to cover the whole Internet. We show that with many vantage points, VP proximity to the target is the most important factor affecting accuracy. This observation suggests our new algorithm that selects the best few VPs for each target from many candidates. This approach addresses the main bottleneck to geolocation scalability: minimizing traffic into each target (and also out of each VP) while maintaining accuracy. Using this approach we have currently geolocated about 35% of the allocated, unicast, IPv4 address-space (about 85% of the addresses in the Internet that can be directly geolocated). We visualize our geolocation results on a web-based address-space browser.

Citation: Zi Hu and John Heidemann and Yuri Pradkin. Towards Geolocation of Millions of IP Addresses. In Proceedings of the ACM Internet Measurement Conference, p. to appear. Boston, MA, USA, ACM. 2012. <http://www.isi.edu/~johnh/PAPERS/Hu12a.html>

 

Categories
Publications Technical Report

New Tech Report “Towards Geolocation of Millions of IP Addresses”

We just published a new technical report “Towards Geolocation of Millions of IP Addresses”, available at ftp://ftp.isi.edu/isi-pubs/tr-680.pdf.

From the abstract:

Previous measurement-based IP geolocation algorithms have focused on accuracy, studying a few targets with increasingly sophisticated algorithms taking measurements from tens of vantage points (VPs). In this paper, we study how to scale up existing measurement-based geolocation algorithms like Shortest Ping and CBG to cover the whole Internet. We show that with many vantage points, VP proximity to the target is the most important factor affecting accuracy. This observation suggests our new algorithm that selects the best few VPs for each target from many candidates. This approach addresses the main bottleneck to geolocation scalability: minimizing traffic into each target (and also out of each VP) while maintaining accuracy. Using this approach we have currently geolocated about 24% of the allocated, unicast, IPv4 address-space (about 55% of the addresses in the Internet that can be directly geolocated).

Categories
Publications Technical Report

New Tech Report “An Organization-Level View of the Internet and its Implications (extended)”

We just published a new technical report “An Organization-Level View of the Internet and its Implications (extended)”, available at ftp://ftp.isi.edu/isi-pubs/tr-679.pdf.
From the abstract:

We present a new clustering approach for mapping ASes to organizations, to develop an organization-level view of the Internet’s AS ecosystem. We demonstrate that the choice of clustering method and use of a new (though unconventional) data source in the form of company subsidiary information contained in the U.S. SEC~Form 10-K filings are both essential to get accurate results. Evaluating our mapping and validating it against carefully chosen datasets shows few (less than 10%) false negatives for 90% of organizations and few false positives for 60% of our organizations. We apply our map to show the importance of an organization-level view of the Internet by contrasting it with the commonly-used view that considers only an organization’s “main” AS. We find that this main-AS view sometimes severely underrepresents the influence of an organization in terms of announced addresses, geographic footprint, and peerings at Internet eXchange Points (IXPs). For example, for 20% of our organizations, the main-AS view detects only 10-60% of the cities covered by the corresponding organization-level view.

Categories
Publications Technical Report

New Tech Report “Detecting Internet Outages with Precise Active Probing (extended)”

We just published a new technical report “Detecting Internet Outages with Precise Active Probing (extended)”, available at ftp://ftp.isi.edu/isi-pubs/tr-678b.pdf. This is an update of ISI-TR-678.

From the abstract:

Parts of the Internet are down every day, from the intentionalshutdown of the Egyptian Internet in Jan. 2011 and natural disasterssuch as the Mar. 2011 Japanese earthquake, to the thousands of smalloutages caused by localized accidents, and human error, maintenance,or choices.  Understanding these events requires efficient andaccurate detection methods, motivating our new system to detectnetwork outages by active probing.  We show that a single computer cantrack outages across the entire analyzable IPv4 Internet, probing asample of 20 addresses in all 2.5M responsive /24 address blocks.  Weshow that our approach is significantly more accurate than the bestcurrent methods, with 31% fewer false conclusions, while providing 14%greater coverage and requiring about the same probing traffic.  Wedevelop new algorithms to identify outages and cluster them to events,providing the first visualization of outages.  We carefully validateour approach, showing consistent results over two years and from threedifferent sites.  Using public BGP archives and news sources weconfirm 83% of large events.  For a random sample of 50 observedevents, we find 38% in partial control-plane information, reaffirmingprior work that small outages are often not caused by BGP.  Throughcontrolled emulation we show that our approach detects 100% offull-block outages that last at least twice our probing interval.Finally, we report on Internet stability as a whole, and the size andduration of typical outages, using core-to-edge observations with muchlarger coverage than prior mesh-based studies.  We find that about0.3% of the Internet is likely to be unreachable at any time,suggesting the Internet provides only 2.5 “nines” of availability.

Categories
Publications Technical Report

New tech report “Detecting Internet Outages with Active Probing”

We just published a new technical report “Detecting Internet Outages with Active Probing”, available at ftp://ftp.isi.edu/isi-pubs/tr-672.pdf.

From the abstract:

With businesses, governments, and individuals increasingly
dependent on the Internet, understanding its reliability is more
important than ever. Network outages vary in scope and
cause, from the intentional shutdown of the Egyptian Inter-
net in February 2011, to outages caused by the effects of
March 2011 earthquakes on undersea cables entering Japan,
to the thousands of small, daily outages caused by localized
accidents or human error. In this paper we present a new
method to detect network outages by probing entire blocks.
Using 24 datasets, each a 2-week study of 22,000 /24 address
blocks randomly sampled from the Internet, we develop new
algorithms to identify and visualize outages and to cluster
those outages into network-level events. We validate our ap-
proach by comparing our data-plane results against control-
plane observations from BGP routing and news reports, ex-
amining both major and randomly selected events. We con-
firm our results are stable from two different locations and
over more than one and half years of observations. We show
that our approach of probing all addresses in a /24 block is
significantly more accurate than prior approaches that use a
single representative for all routed blocks, cutting the num-
ber of mistake outage observations from 44% to under 1%.
We use our approach to study several large outages such as
those mentioned above. We also develop a general estimate
for how much of the Internet is regularly down, finding about
0.3% of the Internet is likely to be unreachable at any time.
By providing a baseline estimate of Internet outages, our
work lays the groundwork to evaluate ISP reliability.

Citation: Lin Quan and John Heidemann. Detecting Internet Outages with Active Probing. Technical Report N. ISI-TR-672. USC/Information Sciences Institute, May 2011. http://ftp://ftp.isi.edu/isi-pubs/tr-672.pdf

Categories
Presentations

New Video About Address Utilization and Allocations on Map Browser

The ANT project released a video describing Internet address allocation and how we study address utilization with IPv4 censuses. Aniruddh Rao prepared this video, working with John Heidemann and Xue Cai.

a scene from the ANT video describing address allocation and census taking

We have also updated our web-based IPv4 address browser to provide information about to what organizations each address block is allocated. The map now visualizes the whois allocation data; we thank the five regional internet registries for sharing this data with us and authorizing this visualization.

organizations in our Internet map

Finally, our web-based IPv4 address browser now has better time travel, with nearly 30 different census from Dec. 2005 to Nov. 2010, and we continue to update the map regularly.

Data collection for this work is through the LANDER project, and the map browser improvements are due to AMITE, both supported by DHS. Video preparation was supported by these projects and NSF through the MADCAT project.

Categories
Papers Publications

new conference paper “Towards an AS-to-Organization Map” to appear at IMC

The paper “Towards an AS-to-Organization Map” was accepted by IMC’10 in Melbourne, Australia (available at http://www.isi.edu/~johnh/PAPERS/Cai10c.html).

From the abstract:

An understanding of Internet topology is central to answer various questions ranging from network resilience to peer selection or data center location. While much of prior work has examined AS-level connectivity, meaningful and relevant results from such an abstract view of Internet topology have been limited. For one, semantically, AS relationships capture business relationships and not physical connectivity. Additionally, many organizations often use multiple ASes, either to implement different routing policies, or as legacies from mergers and acquisitions. In this paper, we move beyond the traditional AS graph view of the Internet to define the problem of AS-to-organization mapping. We describe our initial steps at automating the capture of the rich semantics inherent in the AS-level ecosystem where routing and connectivity intersect with organizations. We discuss preliminary methods that identify multi-AS organizations from WHOIS data and illustrate the challenges posed by the quality of the available data and the complexity of real-world organizational relationships.

Citation: Xue Cai, John Heidemann, Balachander Krishnamurthy, and Walter Willinger. Towards an AS-to-Organization Map. In Proceedings of the ACM Internet Measurement Conference, p. to appear. Melbourne, Australia, ACM. November, 2010.