Skip to Content
[CAIDA - Center for Applied Internet Data Analysis logo]
Center for Applied Internet Data Analysis
www.caida.org > funding : nets-congestion
Mapping Interconnection in the Internet: Colocation, Connectivity and Congestion
Sponsored by:
National Science Foundation (NSF)
In collaboration with David Clark (MIT/CSAIL), we will characterize the changing nature of the Internet's topology and traffic dynamics, and describe the implications of these changes for network science, architecture, operations, and public policy.

Funding source: NSF CNS-1414177. Period of performance: October 1, 2014 - September 30, 2017.

|   Project Summary    Proposal   |

Project Summary

As the global Internet expands to satisfy the demands and expectations of an ever-increasing fraction of the world's population, profound changes are occurring in its interconnection structure, traffic dynamics, and the economic and political power of different players in the ecosystem. These changes not only impact network engineering and operations, but also present broader challenges for technology investment, future network design, public policy, and scientific study of the Internet itself. And yet, from both scientific and policy perspectives, the evolving ecosystem is largely uncharted territory.

We will focus our attention on two related transformations of the ecosystem: the emergence of Internet exchanges (IXes) as anchor points in the mesh of interconnection, and the growing role of content providers and Content Delivery Networks (CDNs) as major sources of traffic flowing into the Internet. By some accounts over half the traffic volume in North America now comes from just two content distributors (Youtube and Netflix). This shift constitutes the rise of a new kind of hierarchy in the ecosystem, bringing fundamentally new constraints on existing players who need to manage traffic on their networks to minimize congestion. Evidence of trouble has increased dramatically in the last five years, resulting in tussles among commercial players as well as between the private sector and regulatory bodies, at the expense of users suffering degraded quality of experience.

The proposed research is structured as two foundational tasks and a set of research questions that build on those tasks. First, we will construct a new type of semantically rich Internet map, which will elucidate the role of IXes in facilitating robust and geographically diverse but complex interdomain connectivity. This map will guide our second task: a measurement study of traffic congestion dynamics induced by evolving peering and traffic management practices of CDNs and ISPs. We will use our own measurement infrastructure as well as measurements from four industry collaborators: Akamai, Netflix, Google, and Comcast. Finally, we will use the results of these two tasks to investigate questions related to infrastructure resiliency, scientific modeling, network economics, and public policy.


Project Timeline

Task 1: Create an IX-aware map of the Internet (October 1, 2014 - September 30, 2016). Lead: CAIDA

DescriptionProjected DateAssigned toStatus
Task 1.1: Incorporating IX connectivity into an AS-level Internet map
1.1.1automate our technique extracting multilateral peering (MLP) links from public route servers at IXPsMay 2015CAIDAdone
1.1.2build a colocation database using available data sources (PeeringDB, Euro-IX, Packet Clearing House, published IX member lists and peering matrices)Sep 2015CAIDAdone
1.1.3use colocation database to identify private peering pointsSep 2015CAIDA/MITdone
1.1.4conduct targeted traceroute probing from multiple vantage points: ArkYear 1CAIDAdone
1.1.5conduct targeted traceroute probing from multiple vantage points: Akamai - MIT - targeted traceroute - CoNEXTYear 1MITdone
1.1.6conduct targeted traceroute probing from multiple vantage points: traceroute.orgYear 1CAIDAin progress
1.1.7conduct targeted traceroute probing from multiple vantage points: RIPE AtlasYear 2CAIDA
1.1.8explore techniques to identify IXes not explicitly seen in the path or documented in public databases and peering at themYear 2CAIDA
Task 1.2: Enrich AS map annotations
1.2.1incorporate additional inputs into machine learning classifier of AS graph node typesYear 1CAIDAdone
1.2.2improve node classification by using a much larger training data set of ground-truth AS classifications available from PeeringDBYear 1CAIDAdone
1.2.3improve link classification by analyzing geographic trends in observed BGP announcements to infer regional business AS relationshipsYear 1CAIDAdone
1.2.4improve link classification using insights into region-specific peering behavior extracted from our MLP inferencesDec 2016CAIDAin progress
Task 1.3: Validate the IX-aware map
1.3.1publish a list of looking glasses hosted at/nearby IXPs and automate querying them to validate the accuracy of our MLP inferences over timeApr 2016CAIDAdone
1.3.2integrate IX-awareness into AS-Rank and collect feedback from network operatorsSep 2015CAIDAdone
1.3.3test our classifications of region-specific relationships using the BGP community values with region-specific annotationsYear 1CAIDAdone
1.3.4assign a confidence level to each link observed in traceroute dataYear 2CAIDA
1.3.5cross-validate inferences from BGP tables, MLP inferences, targeted traceroutes, and published peering matricesYear 2CAIDA
1.3.6explore new validation methods combining information from multiple sources to obtain hints about the likely existence of peering linksYear 2CAIDA

Task 2: Inferring congestion at interconnection points (October 1, 2014 - September 30, 2016). Lead: MIT

DescriptionProjected DateAssigned toStatus
Task 2.1: Conduct delay-based measurements of congestion
2.1.1collect and analyze time-series of delay measurementsongoingCAIDAdone
2.1.2study diurnal RTT variations along the paths in questionongoingCAIDA/MITongoing
2.1.3identify and analyze manifestations of interesting eventsongoingCAIDAongoing
2.1.4provide backend for measurementsMay 2015MITdone
Task 2.2: Conduct throughput-based measurements of congestion
2.2.1confirm experimentally that a rate-limited TCP download probe (RLTP) can detect congestion from a single test measuring each direction separatelyJul 2016MITin progress
2.2.2using M-Lab and Ark as both clients and servers, conduct rate-limited downloads attempting to cross known interconnection pointsAug 2016MIT
2.2.3determine the most likely location of congestion by analyzing collected traceroutes and congestion signal with a binary tomography algorithmSep 2016MIT
2.2.4collaborate with Google researchers to integrate the results into their open source Model-Based Internet Performance Metrics (MBM) toolYear 2MIT
Task 2.3: Conduct passive traffic-based measurements of congestion
2.3.1analyze CDN per-download data (transfer rate, time of selected file downloads, anonymized source/destination addresses) for evidence of congestion Year 2MIT
2.3.2map discovered congestion onto interconnection paths using binary tomographyYear 2CAIDA
2.3.3compare passive download performance with congestion signal from delay-based measurementsYear 2MIT
2.3.4after determining paths between the CDN server and the ISP of the client by active probing, infer the presence of congestion based on data provided by CDNYear 2MIT
Task 2.4: Validation and automation of congestion-related inferences
2.4.1automate detection and analysis of congestion in raw data ongoingCAIDA/MITdone
2.4.2validate congestion inferences using ground truth data provided by collaborating ISPs ongoing CAIDA/MIT
2.4.3cross-validate the three methods (2.1, 2.2, and 2.3) of discovering congestion ongoing CAIDA/MIT
2.4.4automate finding routers along the path of interest and selecting ping targetsYear 1CAIDA/MITin progress
2.4.5validate congestion inferences using external tools (testing link capacities and identifying bottlenecks) and data sets (TCP tests from M-Lab) Year 2CAIDA
2.4.6explore approaches (using reverse traceroutes, Akamai traceroute data) to detect and resolve asymmetric routes to localize congestion Year 2CAIDA

Task 3: Exploring implications for network resiliency, policy, and science (April 1, 2016 - September 30, 2017). Lead: joint CAIDA and MIT

DescriptionProjected DateAssigned toStatus
Task 3.1: Investigate how IXes influence Internet resiliency
3.1.1assess the importance of certain ASes and AS-links in maintaining global or local reachabilityYear 2CAIDA
3.1.2consider whether networks tend to connect at multiple IXes in a city/region (for redundancy) or in different regions (for geo-diversity)Year 2 and 3CAIDA
3.1.3characterize the degree to which the loss of a major IX might potentially isolate or impair regions of the InternetYear 2 and 3CAIDA
Task 3.2: Study consequences of regional differences in peering behavior
3.2.1compare topological structure of different countries/regionsYear 2CAIDA
3.2.2analyze the extent to which some countries/regions/organizations are essential hubs connecting to the global InternetYear 2CAIDA
3.2.3identify ASes or IXes exercising regional control of Internet infrastructure ("choke points")Year 2CAIDA
3.2.4reveal routing inefficiencies due to peering issues or unavailability of IXes for local interconnectionYear 3CAIDA
Task 3.3: Inform growing policy concerns such as network transparency, investment incentives, and market power
3.3.1publish data on the degree and character of the connections between an ISP and the rest of the Internet, including persistent under-provisioning of interconnection links and compare practices across regions;Year 2 and 3 CAIDA/MIT
3.3.2define requirements for data disclosures by ISPs under various scenariosSep 2016MIT
3.3.3derive quantitative metrics of market power from our measurements and examine correlations between these new and conventional metrics and the prevalence of observed congestion on the interconnection links Year 2 and 3MIT
3.3.4extend our past modeling work on fair and stable peering settlements to model performance degradations due to congested interconnectionsYear 3CAIDA
Task 3.4: Refine modeling assumptions about Internet topology and routing
3.4.1produce an AS graph that is an order of magnitude larger than the previous graphs and is both a multi-graph and a hypergraphYear 3CAIDA
3.4.2revise the definition and significance of commonly used topological characteristics (degree distribution, clustering, assortativity, etc.)Year 3CAIDA
3.4.3quantify the prevalence of complex region-specific AS-relationships in the real worldYear 3CAIDA
3.4.4quantify the extent of violations to the assumed "valley free, prefer-customer, prefer-peer" routing policy, and the ASes most likely to produce such violationsYear 3CAIDA
3.4.5develop more realistic and empirically grounded models for AS business relationships and interdomain routing policiesYear 3CAIDA
3.4.6distill relevant statistical properties from the IX-aware map: colocation and peering behavior of different AS types, distributions of the number of physical locations at which two ASes connect, the scope and nature of region-specific business relationships, etc.Year 3CAIDA
3.4.7construct more realistic scalable synthetic maps for modeling and simulationYear 3CAIDA
Task 3.5: Study trends over time in interconnection and performance
3.5.1develop, maintain, and archive classic data sets to preserve Internet historyYear 3CAIDA
3.5.2track longitudinal trends in the practices and effects of interconnectionYear 3CAIDA
3.5.3capture dynamics and evolution of the interaction between CDNs and IXesYear 3CAIDA

  Last Modified: Thu Jun-30-2016 15:12:41 PDT
  Page URL: http://www.caida.org/funding/nets-congestion/index.xml