Multi-publisher routing protocol for named data networks

• US 9,363,179 B2
• Filed: 03/26/2014
• Issued: 06/07/2016
• Est. Priority Date: 03/26/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Mosko, Marc E., Garcia-Luna-Aceves, Jose J.
• Primary Examiner(s): WON, MICHAEL YOUNG
• Application Number:
  US14/226,559
• Publication Number:
  US 20150281071A1
• Time in Patent Office: 804 Days
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering

Abstract

A multi-publisher routing system facilitates forwarding an Interest to multiple publishers associated with a namespace. During operation, network devices across a computer network can perform distance-vector routing with one or more network neighbors to determine a network topology. Also, one or more network devices may receive a namespace-join message from one or more publishers that are to provide content objects for the namespace. These network devices that receive the namespace-join message can construct an acyclic graph that includes one or more publishers for the namespace, and includes one or more forwarder nodes that form network paths between the one or more publishers. Then, when a network node in the acyclic graph receives an Interest message that specifies a name prefix associated with the namespace, this network node can forward the Interest message along the acyclic graph to one or more publishers associated with the namespace.

Claims

1. A computer-implemented method, comprising:

performing, by a network node, distance-vector routing with one or more network neighbors to determine a network topology for a computer network;

receiving a namespace-join message that specifies a publisher in the computer network that is to provide content objects for the namespace;

constructing an acyclic graph that includes one or more publishers for the namespace, and includes one or more forwarder nodes that form network paths between the one or more publishers;

receiving, from a first neighbor in the acyclic graph, a first core advertisement for a first publisher in the acyclic graph that is to function as a core for the namespace;

receiving, from a second neighbor in the acyclic graph, a second core advertisement for a second publisher in the acyclic graph that is to function as a core for the namespace;

comparing information on the first and second core network nodes to elect a core for the namespace;

responsive to electing the first network node as the core for the namespace, forwarding the first core advertisement to the second neighbor and the elected core, and storing the core election in association with the namespace, wherein the core election specifies a namespace, and specifies a publisher in the acyclic graph that is to function as a core network node for the namespace; and

responsive to receiving an Interest message that specifies a name prefix associated with the namespace, forwarding the Interest message along the acyclic graph to one or more publishers associated with the namespace.

2. The method of claim 1, wherein constructing the acyclic graph involves:

forwarding the namespace-join message toward the elected core to activate the network paths in the acyclic graph that include the forwarder nodes between the publisher and the elected core.

3. The method of claim 1, wherein receiving the core election involves receiving an election of one or more publishers in the acyclic graph that are each to function as a core network node for the namespace.

4. The method of claim 1, further comprising:

responsive to receiving the core election from a first network neighbor in the acyclic graph, forwarding the core election to at least a second neighbor in the acyclic graph.

5. The method of claim 1, wherein the acyclic graph includes a directed acyclic graph (DAG) topology.

6. The method of claim 1, wherein performing distance-vector routing involves:

receiving network-neighborhood information from the one or more network neighbors;

updating a local network-neighborhood information to include the network-neighborhood information from the one or more network neighbors;

sending the local network-neighborhood information to the one or more network neighbors;

determining a set of network nodes in the network topology;

determining an interface and a distance to a respective network node in the network topology, wherein the distance indicates a cost to reach the respective network node; and

storing the direction and distance to the respective network node.

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

performing distance-vector routing with one or more network neighbors to determine a network topology for a computer network;

receiving a namespace-join message that specifies a publisher in the computer network that is to provide content objects for the namespace;

constructing an acyclic graph that includes one or more publishers for the namespace, and includes one or more forwarder nodes that form network paths between the one or more publishers;

receiving, from a first neighbor in the acyclic graph, a first core advertisement for a first publisher in the acyclic graph that is to function as a core for the namespace;

receiving, from a second neighbor in the acyclic graph, a second core advertisement for a second publisher in the acyclic graph that is to function as a core for the namespace;

comparing information on the first and second core network nodes to elect a core for the namespace;

responsive to electing the first network node as the core for the namespace, forwarding the first core advertisement to the second neighbor and the elected core, and storing the core election in association with the namespace, wherein the core election specifies a namespace, and specifies a publisher in the acyclic graph that is to function as a core network node for the namespace; and

responsive to receiving an Interest message that specifies a name prefix associated with the namespace, forwarding the Interest message along the acyclic graph to one or more publishers associated with the namespace.

8. The storage medium of claim 7, wherein constructing the acyclic graph involves:

forwarding the namespace-join message toward the elected core to activate the network paths in the acyclic graph that include the forwarder nodes between the publisher and the elected core.

9. The storage medium of claim 7, wherein receiving the core election involves receiving an election of one or more publishers in the acyclic graph that are each to function as a core network node for the namespace.

10. The storage medium of claim 7, further comprising:

responsive to receiving the core election from a first network neighbor in the acyclic graph, forwarding the core election to at least a second neighbor in the acyclic graph.

11. The storage medium of claim 7, wherein the acyclic graph includes a directed acyclic graph (DAG) topology.

12. The storage medium of claim 7, wherein performing distance-vector routing involves:

receiving network-neighborhood information from the one or more network neighbors;

updating a local network-neighborhood information to include the network-neighborhood information from the one or more network neighbors;

sending the local network-neighborhood information to the one or more network neighbors;

determining a set of network nodes in the network topology;

determining an interface and a distance to a respective network node in the network topology, wherein the distance indicates a cost to reach the respective network node; and

storing the direction and distance to the respective network node.

13. An apparatus, comprising:

a routing module to perform distance-vector routing with one or more network neighbors to determine a network topology for a computer network;

a communication module to receive a namespace-join message that specifies a publisher in the computer network that is to provide content objects for the namespace; and

a graph-constructing module to constructing an acyclic graph that includes one or more publishers for the namespace, and includes one or more forwarder nodes that form network paths between the one or more publishers;

wherein the communication module is further configured to;

receive, from a first neighbor in the acyclic graph, a first core advertisement for a first publisher in the acyclic graph that is to function as a core for the namespace; and

receive, from a second neighbor in the acyclic graph, a second core advertisement for a second publisher in the acyclic graph that is to function as a core for the namespace; and

wherein the apparatus further comprises;

a core-electing module to;

compare information on the first and second core network nodes to elect a core for the namespace; and

responsive to electing the first network node as the core for the namespace, forward the first core advertisement to the second neighbor and the elected core, and store the core election in association with the namespace, wherein the core election specifies a namespace, and specifies a publisher in the acyclic graph that is to function as a core network node for the namespace; and

an Interest-processing module to;

process an Interest message received by the communication module, wherein the an Interest message specifies a name prefix associated with the namespace; and

forward the Interest message along the acyclic graph to one or more publishers associated with the namespace.

14. The apparatus of claim 13, wherein while constructing the acyclic graph, the graph-constructing module is further configured to forward the namespace-join message toward the elected core to activate the network paths in the acyclic graph that include the forwarder nodes between the publisher and the elected core.

15. The apparatus of claim 13, wherein while receiving the core election, the communication module is further configured to receive an election of one or more publishers in the acyclic graph that are each to function as a core network node for the namespace.

16. The apparatus of claim 13, wherein the communication module is further configured to forward the core election to at least a second neighbor in the acyclic graph, in response to receiving the core election from a first network neighbor in the acyclic graph.

17. The apparatus of claim 13, wherein the acyclic graph includes a directed acyclic graph (DAG) topology.

18. The apparatus of claim 13, wherein while performing distance-vector routing, the routing module is further configured to:

receive network-neighborhood information from the one or more network neighbors;

update a local network-neighborhood information to include the network-neighborhood information from the one or more network neighbors;

send the local network-neighborhood information to the one or more network neighbors;

determine a set of network nodes in the network topology;

determine an interface and a distance to a respective network node in the network topology, wherein the distance indicates a cost to reach the respective network node; and

store the direction and distance to the respective network node.