Internet Cartography

Metro Fiber Characterization

Optical fiber deployments in metropolitan areas are critical for information distribution to businesses and large segments of the population. In this paper, we describe a characterization study of metropolitan area fiber networks in the US. The goal of our work is to elucidate the key aspects of these infrastructures and to assess how they can be enhanced to support growth in cloud-mobile via expanded connectivity to data centers. We collect maps of 204 metro fiber networks and transcribe these into a geographic information system for analysis and visualization. We report on characteristics including raw miles, geography, proximity to users, correspondence to other infrastructure and PoP/data center proximity. These characteristics indicate highly diverse deployments in different metro areas and suggest different strategies for future deployments. Next, we conduct a resource allocation analysis to assess how fiber infrastructure can be deployed in metro areas to reduce the physical distance to data centers over a range of cost scenarios. Our results show that a small number of new connections to data centers can significantly reduce physical distances to users.

Publications

  • Characteristics of Metro Fiber Deployments in the US
    Sathiya Kumaran Mani, Matthew Nance Hall, Ramakrishnan Durairajan and Paul Barford
    In Proceedings of TMA’20, Berlin, Germany, June 2020. [Acceptance rate 33%]
    [PAPER]

Team

  • Matthew Nance-Hall (UO)
  • Prof. Ram Durairajan (UO)
  • Sathiya Kumaran Mani (UW-Madison)
  • Prof. Paul Barford (UW-Madison)

Funding

This work is supported by NSF CNS-1703592, DHS BAA 11-01, AFRL FA8750-12-2-0328, NSF CNS-1850297, UO faculty research award, and a Ripple fellowship. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of NSF, DHS, AFRL, UO, Ripple, or the U.S. Government.

IPv6 Alias Resolution

A new Alias Resolution Technique for both IPv4 and IPv6 Routers.

This study presents a new alias resolution technique/tool that exploits ICMP rate limiting and thus can be used on IPv6 routers.

Alias resolution techniques (e.g., Midar) associate, mostly through active measurement, a set of IP addresses as belonging to a com- mon router. These techniques rely on distinct router features that can serve as a signature. Their applicability is affected by router support of the features and the robustness of the signature. This study presents a new alias resolution tool called Limited Ltd. that exploits ICMP rate limiting, a feature that is increasingly supported by modern routers that has not previously been used for alias resolution. It sends ICMP probes toward target interfaces in order to trigger rate limiting, extracting features from the probe reply loss traces. It uses a machine learning classifier to designate pairs of interfaces as aliases. We describe the details of the algorithm used by Limited Ltd. and illustrate its feasibility and accuracy. Limited Ltd. not only is the first tool that can perform alias resolution on IPv6 routers that do not generate monotonically increasing fragmentation IDs (e.g., Juniper routers) but it also complements the state-of-the-art techniques for IPv4 alias resolution. All of our code and the collected dataset are publicly available.

Publications

  • Alias Resolution based on ICMP Rate Limiting
    Kevin Vermeulen, Burim Ljuma, Vamsi Krishna, Matthieu Gouel, Olivier Fourmaux, Timur Friedman and Reza Rejaie
    In Proceedings of PAM’20, Oregon, USA, March 2020.
    [PAPER]

Team

  • Kevin Vermeulen (Sorbonne Université)
  • Burim Ljuma (Sorbonne Université)
  • Vamsi Krishna(Sorbonne Université)
  • Matthieu Gouel(Sorbonne Université)
  • (Sorbonne Université)
  • Timur Friedman (Sorbonne Université)
  • Reza Rejaie (UO)

Mapping Internet Interconnections

Mapping Internet Interconnections to Colocation Facilities

This study presents a new method (mi2 ) for inferring and gelocating (i.e. mapping) public and private interconnections inside a given colocation facility.

Internet interconnections are the means by which networks exchange traffic between one another. These interconnections are typically established in facilities that have known geographic locations, and are owned and operated by so-called colocation and interconnection services providers (e.g., Equinix, CoreSite, and EdgeConneX). These previously under-studied colocation facilities and the critical role they play in solving the notoriously difficult problem of obtaining a comprehensive view of the structure and evolution of the interconnections in today’s Internet are the focus of this paper. We present mi2 , a new approach for mapping Internet interconnections inside a given colocation facility. We infer the existence of interconnections from localized traceroutes and use the Belief Propagation algorithm on a specially defined Markov Random Field graphical model to geolocate them to a target colocation facility. We evaluate mi2 by applying it initially to a small set of US-based colocation facilities. In the process, we compare our results against those obtained by two recently developed related techniques and discuss observed discrepancies that derive from how the different techniques determine the ownership of border routers. As part of our validation approach, we also identify drastic changes in today’s Internet interconnection ecosystem (e.g., new infrastructures in the form of “cloud exchanges” that offer new types of interconnections called “virtual private interconnections”), and discuss their wide-ranging implications for obtaining an accurate and comprehensive map of the Internet’s interconnection fabric.

Interconnects Graphic 2

Publications

  • On Mapping the Interconnections in Today’s Internet
    Reza Motamedi, Bahador Yeganeh, Balakrishnan Chandrasekaran, Reza Rejaie, Bruce M. Maggs, Walter Willinger
    In IEEE/ACM Transactions on Networking, Volume 27, Issue 5, October 2019.
    [PAPER]

Team

  • Reza Motamedi (UO)
  • Bahador Yeganeh (UO)
  • Balakrishnan Chandrasekaran (Duke)
  • Prof. Reza Rejaie (UO)
  • Bruce M. Maggs (Duke)
  • Dr. Walter Willinger(NIKSUN Inc.)

Funding

This material is based upon work supported by the National Science Foundation (NSF) Awards CNS-1320977, CNS- 1717187 and CNS-1719165 . Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF.

IPv6 Topology Discovery

Existing methods for active topology discovery within the IPv6 Internet largely mirror those of IPv4. In light of the large and sparsely populated address space, in conjunction with aggressive ICMPv6 rate limiting by routers, this work develops a different approach to Internet-wide IPv6 topology mapping. We adopt randomized probing techniques in order to distribute probing load, minimize the elects of rate limiting, and probe at higher rates. Second, we extensively analyze the efficiency and efficacy of various IPv6 hitlists and target generation methods when used for topology discovery, and synthesize new target lists based on our empirical results to provide both breadth (coverage across networks) and depth (to find potential subnetting). Employing our probing strategy, we discover more than 1.3M IPv6 router interface addresses from a single vantage point. Finally, we share our prober implementation, synthesized target lists, and discovered IPv6 topology results.

Publications

  • In the IP of the Beholder: Strategies for Active IPv6 Topology Discovery
    Robert Beverly, Ramakrishnan Durairajan, David Plonka and Justin P. Rohrer
    In Proceedings of ACM IMC’18, Boston, USA, November 2018.
    [PAPER] [arXiv]

Team

  • Prof. Rob Beverly (Naval Postgraduate School)
  • Prof. Ram Durairajan (UO)
  • Dr. Dave Plonka (Akamai)
  • Prof. Justin Rohrer (Naval Postgraduate School)

A Survey of Techniques for Internet Topology Discovery

This survey examines the main research studies on Internet topology discovery in the last 15-20 years and presents some of their main take-away lessons.

Capturing an accurate view of the Internet topology is of great interest to the networking research community as it has many uses ranging from the design and evaluation of new protocols and services to the vulnerability analysis of the network’s infrastructure. However, the scale of today’s Internet coupled with its distributed and heterogeneous nature makes it very challenging to acquire a complete and accurate snapshot of the topology.

The purpose of this survey is to examine the main research studies that have been conducted on topics related to Internet topology discovery in the last 15-20 years and present some of the main lessons learned from these past efforts. To this end, we classify these prior studies according to the “resolution” or “level” of the topology; that is, interface-level, router- level, PoP-level and AS-level. For each resolution, we describe the main techniques and tools used for data col- lection, identify their major limitations and issues, and dis- cuss the key implications that these limitations have on the quality of the collected data. In the process, we present the latest efforts in modeling the Internet’s topology at the different levels and report on the role that geographic characteristics play in this context. We present the lessons learned as a checklist that every researcher working on Internet topology discovery-related problems should consult to minimize the risk of repeating some of the same or similar mistakes that have been made in the past and as a result have hampered progress in this important area of Internet research.

Topology Discovery

Publications

  • A Survey of Techniques for Internet Topology Discovery
    Reza Motamedi, Reza Rejaie, Walter Willinger
    IEEE Communications Surveys and Tutorials, Volume 17, Number 2, pp. 1044 - 1065, 2nd quarter 2015
    [PAPER]

Team

  • Reza Motamedi (UO)
  • Prof. Reza Rejaie (UO)
  • Dr. Walter Willinger (NIKSUN Inc)

Geography of Eyeball ASes

This study presents a new approach to determine the geo- graphical footprint of individual Autonomous Systems that directly provide service to end-users, i.e.,eyeball ASes. The key idea is to leverage the geo-location of end-users asso- ciated with an eyeball AS to identify its geographical foot- print. We leverage the kernel density estimation method to estimate the density of users across individual eyeball ASes. This method enables us to cope with the potential error associated with the location of individual end-users while controlling the level of aggregation among data points to capture a geo-footprint at the desired resolution. We use the resulting geo-footprint of individual eyeball ASes to identify their likely Point-of-Presence (PoP) locations.

To demonstrate our proposed technique, we use the in- ferred geo-locations of 48 million users from three popular P2P applications and assess the geo- and PoP-level foot- prints of 1233 eyeball ASes. The validation of the identified PoP locations by our technique against online information and prior results by a commonly-used technique based on traceroute shows a very high accuracy. Leveraging the ac- quired PoP locations, we examine the implications of geo- footprint of eyeball ASes on their connectivity to the rest of the Internet. In particular, we present a case study that re- veals a much more complex picture of AS-level connectivity as compared to what the more traditional but geography-agnostic BGP- or traceroute-based approaches depict.

"Eyeball ASes"

Publications

Team

  • Amir H. Rasti
  • Nazanin Magharei
  • Prof. Reza Rejaie (UO)
  • Dr. Walter Willinger (NIKSUN Inc)