The Named Data Networking (NDN) project makes use of the CCN (ContentCentric Networking) architecture developed at the Palo Alto Research Center (PARC). The NDN project participants experiment, conduct research, and build applications that make use of the emerging CCNx Protocol.
We measured the performance metrics for the modified greedy forwarding algorithm in the NDN testbed. We report the results for the full graph of participating sites as well as for all the graphs obtained from the full graph by removing one link without disconnecting the full graph.
For more information about CAIDA's participation in the NDN project, see the CAIDA NDN Project page.
Modified Greedy Forwarding (MGF)
The paper [HGCN10] describes how the hyperbolic metric space underlying complex networks enables efficient greedy forwarding (GF) without any global knowledge of the network topology. Since each node in the network has its coordinates in this hidden metric space, a node can compute the distances between each of its neighbors in the network, and the destination whose coordinates are written in the information packet. GF then amounts to forwarding the information to the nodes neighbor closest to the destination in the hyperbolic space. In the experiments on the NDN testbed reported here we tested the modified greedy forwarding (MGF) algorithm that excludes the current node from any distance comparisons and finds the neighbor closest to the destination. The packet is dropped if this neighbor is the same as the packet's previously visited node.
To evaluate the MGF efficiency, we measured the following metrics:
 the success ratio which is the percentage of the successful paths that reach their destinations
 the average stretch of three types:
 Stretch 1  the standard hop stretch measured on the actual topology is the ratio between the hop lengths of greedy paths and the corresponding shortest paths in the graph. The shortest paths have stretch equal to 1.
 Stretch 2  measured in the underlying hyperbolic space, the ratio of the length of a successful greedy path to the actual hyperbolic distance between the source and the destination;
 Stretch 3  measured in the underlying hyperbolic space, the ratio of the length of the shortest path to the actual hyperbolic distance between the source and the destination;
The lower these two hyperbolic stretches, the closer the greedy and shortest paths stay to the hyperbolic geodesics, and the more congruent the network topology is with the underlying geometry. See [HGCN10] for details.
A Python script implementation of the MGF algorithm is made available.
Experiments
Following up on earlier 20112012 experiments, we present the data and code used in two experiments in 2013, below:
Reading the data
Each experiment has three files associated with it:
 nodes describes the nodes and their polar coordinates in the hyperbolic plane. The format is selfdocumenting.
 links lists each link as a pair of AS numbers.

paths
files contain the forwarding paths between all sourcedestination pairs.
Each line represents one path between a sourcedestination pair,
and has the format:
AS1AS2AS3 ... ASN1ASNoutcome
 AS1 is the source and ASN is the destination.
 AS2 ... ASN1 are other hops along the path.
 Outcome is either "s" for success, or "f" for failure. If outcome is "f", then ASN1 is the hop at which the forwarding algorithm gave up, meaning that ASN1 has seen the packet twice.
 Note: paths in which either the source or the destination are isolated nodes are not include in the results.
Computing AS hyperbolic coordinates
In order to obtain the hyperbolic coordinate for each AS in the NDN testbed, we embedded the AS topology of the Internet into its hyperbolic space, following the approach described in [NMRH13]. The AS topology is measured by CAIDA's Ark, see the description and full data (collected since 2007) at CAIDA's website. The data and code used in the experiments below are:
 AS topology: Data collected over one month, between August and September 2013.
 Embedding code: Exactly as used to embed the topology. The embedding algorithm is described in [NMRH13]. Here we used it with some recent optimizations, to be published elsewhere
 Hyperbolic coordinates: Obtained by running the code on the AS topology.
Experiment 1, December 2013
Experiment 1: Original NDN testbed topology
We set the hyperbolic coordinates of the NDN sites to the hyperbolic coordinates of their ASes in the embedding, and performed the greedy routing simulation on the current (Dec'13) NDN testbed topology. Note that UCLA and REMAP belong to the same AS.
Data files: nodesgraph  success ratio  avg stretch 1  avg stretch 2  avg stretch 3  paths 

full graph (links)  0.82  1.07 (max 1.50)  1.59 (max 4.04)  1.57 (max 3.29)  paths 
Experiment 2, December 2013
We modeled the network growth on the NDN testbed. We again assigned to the testbed gateways the hyperbolic coordinates of their ASes in the embedding, but then we constructed different testbed topologies in accordance with the network growth model in [PSGN12]. Specifically, to construct these topologies, we connected each node to its m=1,2,3 hyperbolically closest nodes. To stay consistent with this construction in the future, all future NDN sites should simply connect to the same number m of hyperbolically closest existing NDN sites. For each value of m, we measured the success ratio and the three stretches in the resulting networks, as well as in the networks obtained from those by all possible removals of one link and one node.
In summary, even m=2 is enough for 100% success ratio in the resulting topology and in topologies obtained from it by removal of a single link or node. However, we recommend to use m=3 in practice for better reliability. In that case, the asymptotic average degree in the network will be 6, similar to the average AS degree in the Internet. (The average AS degree in the AS topology that we embedded is 5.2)
Experiment 2: Growth with m=1
graph  success ratio  avg stretch 1  avg stretch 2  avg stretch 3  paths 

full graph  1  1  1.78  1.78  paths 
link removals  
453812145  0.47  1  1.49  1.49  paths 
1214514048  0.53  1  1.53  1.53  paths 
170612145  1  1  1.74  1.74  paths 
5212145  1  1  1.77  1.77  paths 
1954538  1  1  1.73  1.73  paths 
3637514048  1  1  1.69  1.69  paths 
258874538  1  1  1.79  1.79  paths 
1564538  1  1  1.79  1.79  paths 
3814048  1  1  1.78  1.78  paths 
node removals  
1706  1  1  1.74  1.74  paths 
156  1  1  1.79  1.79  paths 
12145  0.25  1  1.21  1.21  paths 
25887  1  1  1.79  1.79  paths 
38  1  1  1.78  1.78  paths 
52  1  1  1.77  1.77  paths 
4538  0.42  1  1.58  1.58  paths 
36375  1  1  1.69  1.69  paths 
14048  0.58  1  1.58  1.58  paths 
195  1  1  1.73  1.73  paths 
Experiment 2: Growth with m=2
graph  success ratio  avg stretch 1  avg stretch 2  avg stretch 3  paths 

full graph  1  1  1.35  1.36  paths 
link removals  
453812145  1  1.02  1.40  1.38  paths 
453814048  1  1  1.37  1.37  paths 
1214514048  1  1.02  1.42  1.38  paths 
1214552  1  1.02  1.47  1.45  paths 
1404836375  1  1.02  1.40  1.38  paths 
170612145  1  1.02  1.45  1.43  paths 
17064538  1  1  1.38  1.38  paths 
5214048  1  1  1.37  1.37  paths 
1954538  1  1.02  1.41  1.39  paths 
19512145  1  1  1.41  1.41  paths 
3637512145  1  1  1.42  1.42  paths 
258874538  1  1.02  1.40  1.38  paths 
2588712145  1  1  1.39  1.40  paths 
1564538  1  1.02  1.40  1.38  paths 
15612145  1  1  1.39  1.40  paths 
3814048  1  1.02  1.39  1.37  paths 
3812145  1  1  1.40  1.40  paths 
node removals  
1706  1  1  1.31  1.32  paths 
156  1  1  1.35  1.36  paths 
12145  1  1  1.63  1.63  paths 
25887  1  1  1.35  1.36  paths 
38  1  1  1.35  1.35  paths 
52  1  1  1.33  1.33  paths 
4538  1  1  1.40  1.41  paths 
36375  1  1  1.32  1.32  paths 
14048  1  1  1.37  1.37  paths 
195  1  1  1.33  1.33  paths 
Experiment 2: Growth with m=3
Data files: nodeslinksgraph  success ratio  avg stretch 1  avg stretch 2  avg stretch 3  paths 

full graph  1  1  1.25  1.25  paths 
link removals  
453812145  1  1.01  1.27  1.27  paths 
453814048  1  1  1.27  1.28  paths 
45381706  1  1  1.27  1.28  paths 
1214514048  1  1  1.27  1.28  paths 
1214552  1  1.03  1.32  1.28  paths 
1404836375  1  1.03  1.31  1.28  paths 
170612145  1  1.03  1.31  1.27  paths 
17064538  1  1  1.27  1.27  paths 
5214048  1  1  1.26  1.28  paths 
524538  1  1  1.26  1.27  paths 
1954538  1  1.03  1.31  1.29  paths 
19512145  1  1.01  1.26  1.27  paths 
19514048  1  1  1.26  1.27  paths 
3637512145  1  1  1.26  1.27  paths 
363754538  1  1  1.26  1.27  paths 
258874538  1  1.03  1.30  1.28  paths 
2588712145  1  1.01  1.26  1.27  paths 
2588714048  1  1  1.26  1.27  paths 
1564538  1  1.03  1.30  1.28  paths 
15612145  1  1.01  1.26  1.27  paths 
15614048  1  1  1.26  1.27  paths 
3814048  1  1.03  1.30  1.27  paths 
3812145  1  1  1.25  1.26  paths 
3836375  1  1  1.26  1.27  paths 
node removals  
1706  1  1  1.20  1.21  paths 
156  1  1  1.23  1.24  paths 
12145  1  1  1.31  1.31  paths 
25887  1  1  1.23  1.24  paths 
38  1  1  1.24  1.24  paths 
52  1  1  1.21  1.22  paths 
4538  1  1  1.31  1.32  paths 
36375  1  1  1.22  1.23  paths 
14048  1  1  1.31  1.32  paths 
195  1  1  1.21  1.22  paths 
References
 [HGCN10]  D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat, and M. Boguna;. Hyperbolic Geometry of Complex Networks, Physical Review E, v. 82, p. 036106, Oct 2010.
 [PSGN12]  F. Papadopoulos, M. Kitsak, M.A. Serrano, M. Boguna, and D. Krioukov. Popularity versus Similarity in Growing Networks, Nature, v. 489, p. 537, Oct 2012.
 [NMRH13]  F. Papadopoulos, C. Psomas, and D. Krioukov. Network Mapping by Replaying Hyperbolic Growth, IEEE/ACM Transactions on Networking, vol. 23, no. 1, pp. 198211, Feb 2015.