Named Data Networking (NDN)

This page describes CAIDA's participation in the collaborative project Named Data Networking (NDN) supported by NSF grant CNS-1039646 (Period of performance: September 1, 2010 - August 31, 2014). 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 Testbed Results

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 ComponentKey Evaluation MetricsEvaluation 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?

Funding support

National Science Foundation (NSF)

Support for the Named Data Networking project is provided by the National Science Foundation (NSF) grant CNS-1039646 Named Data Networking First Phase. 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.


Additional Content

Named Data Networking(NDN): Evaluation

Eight external experts joined the October 2012 PI meeting in DC, observing that the conversation about evaluating architectures would benefit from more time, structure, and diversity of interests represented. This page summarizes proposed suggestions related to evaluation.

Hyperbolic CCN Forwarding

Below we show the performance metrics for the modified greedy forwarding (MGF) algorithm in the CCN testbed. The results are reported for the full CCN graph, and also for all the graphs obtained from the full graph by removing one link without disconnecting the full graph.

Hyperbolic routing in minimally-linked NDN testbed

Each graph is generated using the NDN testbed nodes, with the hyperbolic coordinates of the involved ASs given in Supplementary Information of this paper. Each node is linked to the m nodes closest to it according to their hyperbolic coordinates.

Published
Last Modified