This page describes CAIDA's participation in the collaborative project Named Data Networking (NDN) supported by NSF grant CNS-1039646. This project is one of the four Future Internet Architecture Awards.
We found the hyperbolic coordinates of the nodes participating in the NDN testbed, simulated the greedy forwarding between these nodes, and measured the success ratio and stretch for the full graph and for the graphs obtained from it by all possible one-link removals that do not disconnect the full graph.
Our results showing greedy forwarding on the NDN testbed demonstrate the efficiency and robustness of such greedy forwarding in agreement with theoretical results of the paper, "Hyperbolic Geometry of Complex Networks", by D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguna.
NDN Project Overview
We are exploring a new Internet architecture called "Named Data Networking" (NDN). By naming data instead of locations, this architecture will transition the Internet from its focus today on "where" -- addresses and hosts -- to "what" -- the content that users and applications care about.
The NDN team consists of a diverse mix of over 20 researchers from 10 campuses bringing a wide spectrum of expertise to tackle the ambitious interdisciplinary reserarch agenda and test the emerging architecture against application needs. The researchers will investigate the core set of problems necessary to validate NDN as a future Internet architecture:
- scalability of routing on names
- fast forwarding based on variable-length hierarchical names (including per-packet state updates needed for multipath forwarding and caching)
- efficiency of signatures for finely-granular signing and verification
- usable trust models for data-centric security, network security and % defense, content protection and privacy
- fundamental communication theory for the new case of storage as an explicit part of the communication model.
This effort will provide a key missing link connecting several architectural components developed under NSF's FIND program and elsewhere, as well as identify new methods to resolve persistent problems in the current Internet architecture. Prototype implementations of both infrastructure and applications, will be released as open source software so that results may be broadly shared for research and education.
For more information please see http://www.named-data.net/.
CAIDA's role in the NDN
The NDN team members determined the following six key areas of research: Applications, Security, Routing and Forwarding, Evaluation and Measurement, Theory, and Software Coordination.
Co-PI Claffy is the leader of Evaluation and Measurement team.
To evaluate the NDN architecture, researchers will use quantitative and qualitative metrics that characterize its ability to support existing and new applications, as well as the performance, scalability, and robustness of NDN networks.
Evaluation methods will include measurements of NDN-connected testbeds, user surveys, simulations, and theoretical analysis to identify problems in the design and evaluate performance at different scales. The key metrics are:
|Architecture Component||Key Evaluation Metrics||Evaluation Method(s)|
|Routing and Data Delivery||FIB size, PIT size and lifetime, routing & Interest message overhead, successful path probability and length distribution, delay in finding data, optimal number and diversity of paths||testbed measurement, simulation, theoretical analysis|
|Hardware||FIB update delay, packet processing delay (including lookup delay)||testbed measurement|
|Caching||cache size, hit ratio as a function of content type||testbed measurement, simulation|
|Flow Control||interface throughput, link utilization||testbed measurement, simulation|
|Application support||ease of creating applications (e.g. closeness of mapping between application needs and network support), application-level data throughput||testbed measurement|
|Privacy||privacy preservation capability of TORNADO (NDN version of TOR)||testbed measurement|
|Data security||speed of generating and verifying signatures||testbed measurement|
|DDoS||percentage of requested data delivered to legitimate users||testbed measurement, simulation|
|Capacity and Traffic||total amount of information transported by the network in space and time (i.e. consumed entropy rate), traffic patterns compared with IP||testbed measurement, theoretical analysis|
For simulations, we will use the best available data on Internet structure, behavior, and usage patterns: traffic data from the DHS PREDICT project, AS-level topology derived from Route Views data, and annotated router-level topology data from CAIDA.
Co-PI Krioukov is a member of two teams, Theory and Routing/Forwarding.
The NDN architecture is sufficiently flexible to allow us to explore the most ambitious routing research idea to emerge from NSF's FIND program: greedy routing based on underlying metric spaces.
Assuming routers are assigned coordinates in a name-based metric space, they can compute the name-space distances between their directly connected neighbors and the destination name in the Interest packet. The key to the scalability of this approach is the hierarchical, or tree-like, name space structure. We have shown that even an approximately tree-like structure can be mapped to an underlying hyperbolic metric space which supports theoretically optimal routing performance characteristics when greedy routing is used.
The researchers will provide mathematical models of the name-space metric structure, develop methods to assign name-space addresses to routers, and design NDN routing algorithms using greedy routing and random walks. They will also investigate what combinations of the name-space structure and network topology ensure the high efficiency of these algorithms. Our first experiments conducted on the NDN testbed demonstrated the success and robustness of greedy forwarding when using the underlying hyperbolic metric space to calculate the distance between participating nodes.
Open research questions include:
- how routers can compute the name-space coordinates using only local information in their FIBs, and potentially the name-space coordinates of their neighbors?
- how routers can optimize their performance with probabilistic random walk algorithm?
- what are the specific properties that the structure of the name space and router topology must have to ensure efficiency?
- what mechanisms might induce these properties?