Greedy Forwarding on the NDN Testbed

The Named Data Networking (NDN) project makes use of the CCN (Content-Centric 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:
1. 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.
2. 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;
3. 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 2011-2012 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 self-documenting.
links lists each link as a pair of AS numbers.
paths files contain the forwarding paths between all source-destination pairs. Each line represents one path between a source-destination pair, and has the format:
```
AS1AS2AS3 ... ASN-1ASNoutcome
```
- AS1 is the source and ASN is the destination.
- AS2 ... ASN-1 are other hops along the path.
- Outcome is either "s" for success, or "f" for failure. If outcome is "f", then ASN-1 is the hop at which the forwarding algorithm gave up, meaning that ASN-1 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.

Note: In order to reduce the computational complexity of the algorithm, only nodes of degree two or higher were embedded. Degree-1 nodes receive their corresponding radial coordinates but take the angular coordinates of their neighbors

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: nodes

graph	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

Representation of the NDN testbed in the hyperbolic plane using polar coordinates. Each node is connected to its hyperbolically closest node. All visualization details are as in Fig. 5 of [HGCN10].

Data files: nodes links

graph	success ratio	avg stretch 1	avg stretch 2	avg stretch 3	paths
full graph	1	1	1.78	1.78	paths
link removals
4538-12145	0.47	1	1.49	1.49	paths
12145-14048	0.53	1	1.53	1.53	paths
1706-12145	1	1	1.74	1.74	paths
52-12145	1	1	1.77	1.77	paths
195-4538	1	1	1.73	1.73	paths
36375-14048	1	1	1.69	1.69	paths
25887-4538	1	1	1.79	1.79	paths
156-4538	1	1	1.79	1.79	paths
38-14048	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

As in the previous figure, red links connect each node to its hyperbolically closest neighbor. Connections to their second closest nodes are blue.

Data files: nodes links

graph	success ratio	avg stretch 1	avg stretch 2	avg stretch 3	paths
full graph	1	1	1.35	1.36	paths
link removals
4538-12145	1	1.02	1.40	1.38	paths
4538-14048	1	1	1.37	1.37	paths
12145-14048	1	1.02	1.42	1.38	paths
12145-52	1	1.02	1.47	1.45	paths
14048-36375	1	1.02	1.40	1.38	paths
1706-12145	1	1.02	1.45	1.43	paths
1706-4538	1	1	1.38	1.38	paths
52-14048	1	1	1.37	1.37	paths
195-4538	1	1.02	1.41	1.39	paths
195-12145	1	1	1.41	1.41	paths
36375-12145	1	1	1.42	1.42	paths
25887-4538	1	1.02	1.40	1.38	paths
25887-12145	1	1	1.39	1.40	paths
156-4538	1	1.02	1.40	1.38	paths
156-12145	1	1	1.39	1.40	paths
38-14048	1	1.02	1.39	1.37	paths
38-12145	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: nodes links

graph	success ratio	avg stretch 1	avg stretch 2	avg stretch 3	paths
full graph	1	1	1.25	1.25	paths
link removals
4538-12145	1	1.01	1.27	1.27	paths
4538-14048	1	1	1.27	1.28	paths
4538-1706	1	1	1.27	1.28	paths
12145-14048	1	1	1.27	1.28	paths
12145-52	1	1.03	1.32	1.28	paths
14048-36375	1	1.03	1.31	1.28	paths
1706-12145	1	1.03	1.31	1.27	paths
1706-4538	1	1	1.27	1.27	paths
52-14048	1	1	1.26	1.28	paths
52-4538	1	1	1.26	1.27	paths
195-4538	1	1.03	1.31	1.29	paths
195-12145	1	1.01	1.26	1.27	paths
195-14048	1	1	1.26	1.27	paths
36375-12145	1	1	1.26	1.27	paths
36375-4538	1	1	1.26	1.27	paths
25887-4538	1	1.03	1.30	1.28	paths
25887-12145	1	1.01	1.26	1.27	paths
25887-14048	1	1	1.26	1.27	paths
156-4538	1	1.03	1.30	1.28	paths
156-12145	1	1.01	1.26	1.27	paths
156-14048	1	1	1.26	1.27	paths
38-14048	1	1.03	1.30	1.27	paths
38-12145	1	1	1.25	1.26	paths
38-36375	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. 198--211, Feb 2015.