Distance-based routing in an information-centric network

• US 9,503,358 B2
• Filed: 12/05/2013
• Issued: 11/22/2016
• Est. Priority Date: 12/05/2013
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Garcia-Luna-Aceves, Jose J.
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Barker, Todd L
• Application Number:
  US14/098,398
• Publication Number:
  US 20150163127A1
• Time in Patent Office: 1,083 Days
• Field of Search: 709/213, 709/217, 709/224, 709/238, 709/241, 709/242, 370/256, 370/390, 370/389, 370/392
• US Class Current: 1/1
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

One embodiment of the present invention provides a computing system. The computing system includes a processor and a computer-readable storage medium. The computer-readable storage medium stores instructions which when executed by the processor cause the processor to perform a method. The method comprises identifying an identifier of an anchor node associated with a name in an update message received from a neighbor node. The anchor node stores a content object identifiable based on the name independent of the anchor node. The method also comprises determining a valid next-hop neighbor in the ICN for the name based on a sequence number of the update message generated by the anchor node and lexicographic order of an identifier of the neighbor node; and determining whether the anchor node is a designated anchor node based on the validity of the next-hop neighbor and a routing metric for the anchor node.

Claims

1. A computer-executable method, comprising:

receiving, by a local computer node, an update message for a name prefix from a first neighboring node in an information-centric network (ICN), wherein the update message includes an updated sequence number for a first anchor node for the name prefix that stores a Content Object identifiable based on a name that includes the name prefix, and wherein the name prefix is location-independent;

identifying a first set of neighboring nodes, which are neighbors to the local computer node, via which the name prefix of the first anchor node is reachable;

determining, from the first set of neighboring nodes, a second set of neighboring nodes which are valid neighbors to the local computer node for the name prefix based on their sequence numbers being most recent sequence numbers matching the updated sequence number information from the update message;

computing new routing information for a plurality of neighbors from the second set of neighboring nodes for the name prefix;

updating, by the local computer node, a routing table with new routing information for the plurality of neighbors from the second set of neighboring nodes for the name prefix; and

responsive to receiving a request that includes a location-independent name comprising the name prefix, forwarding a request received over the ICN for a Content Object with the name prefix to a neighbor with smallest lexicographic ordering identifier in the ICN, based on the routing table with the new routing information.

2. The method of claim 1, wherein a routing metric for the first anchor node is equal to a routing metric for a second anchor node of the name and where the method further comprises:

determining whether the first anchor node is a designated anchor node based on lexicographic order of first identifier of the first anchor node compared to a second identifier of the second anchor node.

3. The method of claim 1, further comprising forwarding the update message from the first anchor node to a second neighbor node based on lexicographic order of a second identifier of the second neighbor node.

4. The method of claim 1, further comprising:

determining that the first anchor node is not a designated anchor node; and

precluding the local computer node from forwarding the update message from the first anchor node to a neighbor node.

5. The method of claim 1, in response to determining that the Content Object requires a multipoint communication, the method further comprises determining the first anchor node to be a root anchor node of the name based on lexicographic order of a first identifier of the first anchor node compared to a second identifier of a second anchor node of the name, wherein the second anchor node of the name is locally known.

6. The method of claim 5, further comprising forwarding an update message indicating the first anchor node as the root node to a neighbor node, wherein a suitable path to the second anchor node is via the neighbor node, and wherein the update message comprises route information toward the first anchor node.

7. The method of claim 5, further comprising:

maintaining an anchor-based tree (ABT) rooted at the first anchor node for the name; and

forwarding a request from the second anchor node for joining the ABT to the first anchor node.

8. The method of claim 7, further comprising broadcasting a request for the Content Object via the ABT.

9. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing distance-based routing in an information-centric network (ICN), the method comprising:

receiving, by a local computer node, an update message for a name prefix from a first neighboring node in an information-centric network (ICN), wherein the update message includes an updated sequence number information for a first anchor node for the name prefix that stores a Content Object identifiable based on a name that includes the name prefix, and wherein the name prefix is location-independent;

identifying a first set of neighboring nodes, which are neighbors to the local computer node, via which the name prefix of the first anchor node is reachable;

determining, from the first set of neighboring nodes, a second set of neighboring nodes which are valid neighbors to the local computer node for the name prefix based on their sequence numbers being most recent sequence numbers matching the updated sequence number information from the update message;

computing new routing information for a plurality of neighbors from the second set of neighboring nodes for the name prefix;

updating, by the local computer node, a routing table with new routing information for the plurality of neighbors from the second set of neighboring nodes for the name prefix; and

responsive to receiving a request that includes a location-independent name comprising the name prefix, forwarding a request received over the ICN for a Content Object with the name prefix to a neighbor with smallest lexicographic ordering identifier in the ICN, based on the routing table with the new routing information.

10. The non-transitory computer-readable storage medium of claim 9, wherein a routing metric for the first anchor node is equal to a routing metric for a second anchor node of the name, further comprising:

determining whether the first anchor node is a designated anchor node based on lexicographic order of a first identifier of the first anchor node compared to a second identifier of the second anchor node.

11. The non-transitory computer-readable storage medium of claim 9, wherein the method further comprises forwarding the update message from the first anchor node to a second neighbor node based on lexicographic order of a second identifier of the second neighbor node.

12. The non-transitory computer-readable storage medium of claim 9, further comprising determining that the first anchor node is not a designated anchor node;

and precluding the local computer node from forwarding the update message from the first anchor node to a neighbor node.

13. The non-transitory computer-readable storage medium of claim 9, in response to determining that the Content Object requires a multipoint communication, the method further comprises determining the first anchor node to be a root anchor node of the name based on lexicographic order of a first identifier of the first anchor node compared to a second identifier of a second anchor node of the name, wherein the second anchor node of the name is locally known.

14. The non-transitory computer-readable storage medium of claim 13, the method further comprises forwarding an update message indicating the first anchor node as the root node to a neighbor node, wherein a suitable path to the second anchor node is via the neighbor node, and wherein the update message comprises route information toward the first anchor node.

15. The non-transitory computer-readable storage medium of claim 13, the method further comprises:

maintaining an anchor-based tree (ABT) rooted at the first anchor node for the name; and

forwarding a request from the second anchor node for joining the ABT to the first anchor node.

16. The non-transitory computer-readable storage medium of claim 15, the method further comprises broadcasting a request for the Content Object via the ABT.

17. An apparatus for performing distance-based routing in an information-centric network (ICN) comprising:

one or more processor;

a memory;

a message processing mechanism configured to receive, at a local computer node, an update message for a name prefix from a first neighboring node in an information-centric network (ICN), wherein the update message includes updated sequence number information for a first anchor node for the name prefix that stores a Content Object identifiable based on a name that includes the name prefix, and wherein the name prefix is location-independent; and

a forwarding mechanism configured to;

identify a first set of neighboring nodes, which are neighbors to the local computer node, via which the name prefix of the first anchor node is reachable;

determine, from the first set of neighboring nodes, a second set of neighboring nodes which are valid neighbors to the local computer node for the name prefix based on their sequence numbers being most recent sequence numbers matching the updated sequence number information from the update message;

compute new routing information for a plurality of neighbors from the second set of neighboring nodes for the name prefix;

update, by the local computer node, a routing table with new routing information for the plurality of neighbors from the second set of neighboring nodes for the name prefix; and

responsive to receiving a request that includes a location-independent name comprising the name prefix, forward a request received over the ICN for a Content Object with the name prefix to a neighbor with smallest lexicographic ordering identifier in the ICN, based on the routing table with the new routing information.

18. The apparatus of claim 17, wherein a routing metric for the first anchor node is equal to a routing metric for a second anchor node of the name;

wherein the forwarding mechanism is configured to determine whether the first anchor node is a designated anchor node based on lexicographic order of a first identifier of the first anchor node compared to a second identifier of the second anchor node.

19. The apparatus of claim 17, further comprising a notification mechanism configured to forward the update message from the first anchor node to a second neighbor node based on lexicographic order of a second identifier of the second neighbor node.

20. The apparatus of claim 17, further comprising a notification mechanism configured to determine that the first anchor node is not a designated anchor node and preclude the apparatus from forwarding the update message from the first anchor node to a neighbor node.

21. The apparatus of claim 17, further comprising a multipoint communication mechanism configured to, in response to determining that the Content Object requires a multipoint communication, determine the first anchor node to be a root anchor node of the name based on lexicographic order of a first identifier of the first anchor node compared to a second identifier of a second anchor node of the name, wherein the second anchor node of the name is locally known.

22. The apparatus of claim 21, further comprising a notification mechanism configured to forward an update message indicating the first anchor node as the root node to a neighbor node, wherein a suitable path to the second anchor node is via the neighbor node, and wherein the update message comprises route information toward the first anchor node.

23. The apparatus of claim 21, wherein the multipoint communication mechanism is further configured to maintain an anchor-based tree (ABT) rooted at the first anchor node for the name;

and

wherein the apparatus further comprises a notification mechanism configured to forward a request from the second anchor node for joining the ABT to the first anchor node.

24. The apparatus of claim 23, wherein the notification mechanism is further configured to broadcast a request for the Content Object via the ABT.