Method and apparatus for deploying a minimal-cost CCN topology

• US 9,537,719 B2
• Filed: 06/19/2014
• Issued: 01/03/2017
• Est. Priority Date: 06/19/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Mahadevan, Priya, Quereilhac, Alina
• Primary Examiner(s): Elpenord, Candal
• Application Number:
  US14/309,686
• Publication Number:
  US 20150372873A1
• Time in Patent Office: 929 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/126 minimising geographical or physical path length
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them

Abstract

A CCN-deployment system can design and deploy a content centric network (CCN) topology, either across a collection of CCN nodes or across an existing computer network. During operation, the system analyzes a computer network of N network nodes to determine a physical network topology. The system also determines a number, k, of network nodes of the physical network on which to overlay a content centric network (CCN). The system then determines an average degree of connectivity, and a degree-of-connectivity distribution, that achieves an optimal performance metric for the CCN overlay network. The system generates a network topology of k network nodes that satisfies the average degree of connectivity, and that satisfies the degree-of-connectivity distribution. The system can deploy the content centric network topology across k nodes of the underlying physical network.

Claims

1. A computer-implemented method, comprising:

determining, by a computing device, a number k, of network nodes for a content centric networking (CCN) network;

determining an average node degree as twice a number of edges divided by a number of nodes, a degree-of-connectivity distribution, and a joint degree or higher-order distribution, that achieves an optimal performance metric for the CCN network to transmit a CCN Interest, wherein the joint degree distribution indicates an occurrence for a respective pair of node degrees, and wherein the higher-order distribution indicates a probability distribution of loops with at least three nodes;

generating a network topology of k network nodes that satisfies the average node degree, and satisfies the degree-of-connectivity distribution and joint degree or higher-order distribution;

mapping the k nodes of the generated network topology to nodes of a physical computer network; and

transmitting the CCN Interest via the physical computer network according to the mapped network topology.

2. The method of claim 1, wherein mapping the k nodes of the generated network topology to nodes of the physical computer network involves selecting the k network nodes of the physical computer network on which to overlay the CCN network, such that the selected nodes satisfy the generated network topology for the CCN network;

and

wherein the method further comprises deploying the CCN network across the k nodes selected from the physical computer network.

3. The method of claim 1, wherein the performance metrics include at least one of:

CCN Interest overhead;

a number or percentage of CCN Interest retransmissions; and

an Interest-to-Content-Object round-trip delay.

4. The method of claim 1, wherein determining the average node degree involves:

iterating over one or more average node degrees, to generate a network topology of k network nodes for each average node degree;

computing a performance metric for each network topology; and

selecting an average node degree with a highest performance metric.

5. The method of claim 1, wherein determining the degree-of-connectivity distribution involves determining an optimal distribution based on one or more of:

a power-law distribution; and

a Gaussian distribution.

6. The method of claim 1, wherein determining the degree-of-connectivity distribution involves:

iterating over one or more distribution functions, to generate a network topology of k network nodes that satisfies the average node degree based on a corresponding distribution function;

computing a performance metric for each network topology; and

selecting a degree-of-connectivity distribution with a highest performance metric.

7. The method of claim 6, wherein determining the degree-of-connectivity distribution further involves:

iterating over one or more parameters for the distribution function, to generate a network topology of the k network nodes that satisfies the average node degree based on each distribution function;

computing a performance metric for each network topology; and

selecting network parameters with a highest performance metric.

8. The method of claim 1, wherein the joint degree or higher-order distribution includes a degree-distribution matrix.

9. The method of claim 8, wherein determining the degree-of-connectivity distribution involves:

generating the degree-distribution matrix to indicate the occurrence value for each pair of node degrees, wherein the degree-distribution matrix is multi-dimensional, and achieves an optimal performance metric for a network topology of the k network nodes that satisfies the average node degree.

10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method:

determining a number k, of network nodes for a content centric networking (CCN) network;

determining an average node degree as twice a number of edges divided by a number of nodes, a degree-of-connectivity distribution, and a joint degree or higher-order distribution, that achieves an optimal performance metric for the CCN network to transmit a CCN Interest, wherein the joint degree distribution indicates an occurrence for a respective pair of node degrees, and wherein the higher-order distribution indicates a probability distribution of loops with at least three nodes;

generating a network topology of k network nodes that satisfies the average node degree, and satisfies the degree-of-connectivity distribution and joint degree or higher-order distribution;

mapping the k nodes of the generated network topology to nodes of a physical computer network; and

transmitting the CCN Interest via the physical computer network according to the mapped network topology.

11. The non-transitory computer-readable storage medium of claim 10, wherein mapping the k nodes of the generated network topology to nodes of the physical computer network involves selecting the k network nodes of the physical computer network on which to overlay the CCN network, such that the selected nodes satisfy the generated network topology for the CCN network;

and

wherein the method further comprises deploying the CCN network across the k nodes selected from the physical computer network.

12. The non-transitory computer-readable storage medium of claim 10, wherein determining the average node degree involves:

iterating over one or more average node degrees, to generate a network topology of k network nodes for each average node degree;

computing a performance metric for each network topology; and

selecting an average node degree with a highest performance metric.

13. The non-transitory computer-readable storage medium claim 10, wherein determining the degree-of-connectivity distribution involves determining an optimal distribution based on one or more of:

a power-law distribution; and

a Gaussian distribution.

14. The non-transitory computer-readable storage medium of claim 10, wherein determining the degree-of-connectivity distribution involves:

iterating over one or more distribution functions, to generate a network topology of k network nodes that satisfies the average node degree based on a corresponding distribution function;

computing a performance metric for each network topology; and

selecting a degree-of-connectivity distribution with a highest performance metric.

15. The non-transitory computer-readable storage medium of claim 14, wherein determining the degree-of-connectivity distribution further involves:

iterating over one or more parameters for the distribution function, to generate a network topology of the k network nodes that satisfies the average node degree based on each distribution function;

computing a performance metric for each network topology; and

selecting network parameters with a highest performance metric.

16. The non-transitory computer-readable storage medium of claim 10, wherein the joint degree or higher-order distribution includes a degree-distribution matrix.

17. The non-transitory computer-readable storage medium of claim 16, wherein determining the degree-of-connectivity distribution involves:

generating the degree-distribution matrix to indicate the occurrence value for each pair of node degrees, wherein the degree-distribution matrix is multi-dimensional, and achieves an optimal performance metric for a network topology of the k network nodes that satisfies the average node degree.

18. An apparatus, comprising:

a processor; and

storage medium storing instructions that when executed by the processor cause the apparatus to perform a method, the method comprising;

determining a number k, of network nodes for a content centric networking (CCN) network;

determining an average node degree as twice a number of edges divided by a number of nodes, a degree-of-connectivity distribution, and a joint degree or higher-order distribution, that achieves an optimal performance metric for the CCN network to transmit a CCN Interest, wherein the joint degree distribution indicates an occurrence for a respective pair of node degrees, and wherein the higher-order distribution indicates a probability distribution of loops with at least three nodes;

generating a network topology of k network nodes that satisfies the average node degree, and satisfies the degree-of-connectivity distribution and joint degree or higher-order distribution;

mapping the k nodes of the generated network topology to nodes of a physical computer network; and

transmitting the CCN Interest via the physical computer network according to the mapped network topology.

19. The apparatus of claim 18, wherein mapping the k nodes of the generated network topology to nodes of the physical computer network involves selecting k network nodes of the physical computer network on which to overlay the CCN network, such that the selected nodes satisfy the generated network topology for the CCN network;

and

wherein the method further comprises deploying the CCN network across the k nodes selected from the physical computer network.

20. The apparatus of claim 18, wherein determining the average node degree involves:

iterating over one or more average node degrees, to generate a network topology of k network nodes for each average node degree;

computing a performance metric for each network topology; and

selecting an average node degree with a highest performance metric.

21. The apparatus of claim 18, wherein determining the degree-of-connectivity distribution involves:

iterating over one or more distribution functions, to generate a network topology of k network nodes that satisfies the average node degree based on a corresponding distribution function;

computing a performance metric for each network topology; and

selecting a degree-of-connectivity distribution with a highest performance metric.

22. The apparatus of claim 21, wherein determining the degree-of-connectivity distribution further involves:

iterating over one or more parameters for the distribution function, to generate a network topology of the k network nodes that satisfies the average node degree based on each distribution function;

computing a performance metric for each network topology; and

selecting network parameters with a highest performance metric.

23. The apparatus of claim 18, wherein the joint degree or higher-order distribution includes a degree-distribution matrix.

24. The apparatus of claim 23, wherein determining the degree-of-connectivity distribution involves:

generating the optimal degree-distribution matrix to indicate the occurrence value for each pair of node degrees, wherein the degree-distribution matrix is multi-dimensional, and achieves an optimal performance metric for a network topology of the k network nodes that satisfies the average node degree.