Research Summaries

Back High-Frequency Active Internet Topology Mapping

Fiscal Year 2014
Division Graduate School of Operational & Information Sciences
Department Computer Science
Investigator(s) Beverly, Robert E.
Sponsor Department of Homeland Security (DHS)
Summary Inferring the logical and physical structure of large communication networks is an important component of infrastructure protection, offensive cybersecurity, and networking research. As such, topology mapping is an active research area with significant prior work. However, as applied to very large, complex, and dynamic networks such as the Internet, topology inference remains an unsolved problem.
Existing state-of-the-art production mapping systems must balance induced measurement load against model fidelity. Unfortunately, in practice, such balancing results in multiple days' worth of measurement to capture even an incomplete portion of the Internet topology. The accuracy of available maps from these and other systems is unknown, yet empirical evidence suggests that additional fine-grained probing exposes hidden links and temporal dynamics. Crucially, incorrect inferences over limited data can lead to false topological conclusions.
Recent techniques prevent incorrect inferences due to common load balancing, while continuing progress is being made in improving IP alias resolution for router-level topologies. These techniques are performed after obtaining an interface-level graph, and therefore require additional active probing. Thus, the number of active probes, and resulting load and time constraints, limits the ability to obtain useful maps of Internet-scale networks, especially in near real-time.
Our prior work examines longitudinal data from the Archipelago (Ark) and iPlane systems, as well as our own measurements, to understand how to maximize topological fidelity while being efficient. Our adaptive probing techniques leverage external knowledge (e.g. common subnetting structures) and information from prior probing to guide the selection of probed destinations and the assignment of destinations to vantage points - thereby shortening the time to obtain a complete topology, or permitting additional probing within a given time or load budget.
We propose to undertake the research and systems engineering to realize the benefits of our promising algorithms: integrating them into a cohesive whole and deploying on CAIDA's production Ark infrastructure. While we have shown their individual utility, we must refine each algorithm to work together as a system that accommodates the subtleties of their interactions when run on a highly dynamic, noisy, and complex Internet. The resulting system will provide high-frequency, high-fidelity active network topology mapping that detects and differentiates load balancing from true network changes, and enables better alias resolution. We expect to iteratively refine our algorithms as we gather and produce data, all of which we will release into public repositories.
Our close working relationship with CAIDA at UCSD, experience working with the Ark distributed measurement infrastructure, and record of producing publications and data from our research ensure the success of the proposed effort. PI Beverly will lead the project both in technical direction and management. In addition to dedicated research time, Dr. Beverly will manage several NPS students who will contribute to the project as part of their thesis obligation.
The proposed effort thus addresses the near real-time network mapping and alias resolution elements of ITA #7. Not only do we hope to perform the research and engineering to produce a high-frequency networking mapping system, our existing relationship with CAIDA provides a platform for rapid development, testing, and, ultimately, gathering new Internet topology results.
Publications Publications, theses (not shown) and data repositories will be added to the portal record when information is available in FAIRS and brought back to the portal
Data Publications, theses (not shown) and data repositories will be added to the portal record when information is available in FAIRS and brought back to the portal