Routing research at CAIDA pursues discovery of new paradigms for interdomain routing algorithms and protocols. We seek to collect and analyze the best available Internet topology and routing data to support Internet topology modeling and simulation.
Routing research is sponsored by NSF Grant 0964236 "NetSE: Discovering Hyperbolic Metric Spaces Hidden Beneath the Internet and Other Complex Networks".
- Ongoing Research
Network routing research and its theoretical results apply to many domains such as computer science, physics, mathematics, economics, social and political sciences. CAIDA's routing research currently focuses on applying key theoretical results in distributed computation theory to the development of protocols that will address issues of future Internet scalability.
We experimented with novel routing concepts using the NDN testbed developed as part of the Named Data Networking project. The results of this experiment with Greedy Forwarding on the NDN testbed are available.
Compact routing is the routing theory that studies the fundamental limits for routing efficiency, and tries to construct routing algorithms that meet those limits. Measures of routing efficiency include the routing table size, routing path stretch, and communication overhead, often estimated by the number of messages required for the algorithm to converge upon a network topology change. The global network topology knowledge is usually assumed, and all the efficiency parameters are estimated in the worst case, across all possible network topologies on which the routing algorithm correctly operates.
The most pessimistic fact from this theory is that there can exist no routing algorithm that would be able to converge with the number of control messages growing slower than linearly with the network size in the worst case. The most pessimistic finding in this paper is that the small-world topologies are this worst case. Almost all complex network topologies, including the Internet, are small-world: the average shortest path length in them grows (sub)logarithmically with the network size.
We have analyzed the rates of consumption of IPv4 addresses, predictions of upcoming IPv4 address space exhaustion dates, and the rates of IPv6 address adoption.
The research on IP resource consumption receives support from the American Registry for Internet Numbers (ARIN).
CAIDA is collaborating with the MIT ANA Spoofer project to assess macroscopic trends in IPv4 source address filtering, e.g., of private or bogon addresses, which should not be exiting appropriately configured networks.
Our data collection efforts support the scientific Internet research community in the process of validating their models, simulations, or theories. The following CAIDA datasets are available for researchers.
- AS Adjacencies
- AS Relationships
- AS Taxonomy
- Router Adjacencies
- Internet Topology Data Kit (ITDK)
- Raw Topology Traces
- AS Growth. An analysis of advertised Autonomous System (AS) growth trends in different regional registries.
- Overview of Greedy Routing on Hidden Metric Spaces (pdf)