DISTANCE-BASED ROUTING IN AN INFORMATION-CENTRIC NETWORK

• US 20150163127A1
• Filed: 12/05/2013
• Published: 06/11/2015
• 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.
• Granted Patent: US 9,503,358 B2
• Time in Patent Office: Days
• 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:

identifying, by a computer node in an information-centric network (ICN), an identifier of a first anchor node associated with a name in an update message received from a neighbor node, wherein the first anchor node stores a content object identifiable based on the name, and wherein the name is independent of the first anchor node;

determining whether the name is validly reachable via a neighboring node based on a comparison between a lexicographic order of the identifier of the neighboring node and the identifier of the node;

responsive to determining that the name is validly reachable via the neighboring node;

adding the neighboring node to a valid list for the name;

determining, for the name, a next-hop neighbor list from the valid list;

computing new routing information for one or more neighboring nodes in the next-hop neighbor list; and

updating a routing table to include the new routing information for the one or more neighboring nodes for the name;

determining whether the first anchor node is a designated anchor node based on the new routing information in the updated routing table and a routing metric for the first anchor node.

2. The method of claim 1, wherein the routing metric for the first anchor node is equal to routing metric for a second anchor node of the name;

wherein determining whether the first anchor is a designated anchor node is further based on lexicographic order of the identifier of the first anchor node compared to an 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 neighbor node based on lexicographic order of the identifier of the neighbor node.

4. The method of claim 1, in response to determining that the first anchor node is not a designated anchor node, the method further comprises precluding the computer 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 the identifier of the first anchor node compared to an 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:

identifying an identifier of a first anchor node associated with a name in an update message received from a neighbor node, wherein the first anchor node stores a content object identifiable based on the name, and wherein the name is independent of the first anchor node;

determining whether the name is validly reachable via a neighboring node based on a comparison between a lexicographic order of the identifier of the neighboring node and the identifier of the node;

responsive to determining that the name is validly reachable via the neighboring node;

adding the neighboring node to a valid list for the name;

determining, for the name, a next-hop neighbor list from the valid list;

computing new routing information for one or more neighboring nodes in the next-hop neighbor list; and

updating a routing table to include the new routing information for the one or more neighboring nodes for the name;

determining whether the first anchor node is a designated anchor node based on the new routing information in the updated routing table and a routing metric for the first anchor node.

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

wherein determining whether the first anchor is a designated anchor node is further based on lexicographic order of the identifier of the first anchor node compared to an 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 neighbor node based on lexicographic order of the identifier of the neighbor node.

12. The non-transitory computer-readable storage medium of claim 9, in response to determining that the first anchor node is not a designated anchor node, the method further comprises precluding the computer 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 the identifier of the first anchor node compared to an 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 identify an identifier of a first anchor node associated with a name in an update message received from a neighbor node and retrievably stored in the memory, wherein the first anchor node stores a content object identifiable based on the name, and wherein the name is independent of the first anchor node; and

a forwarding mechanism configured to;

determine whether the name is validly reachable via a neighboring node based on a comparison between a lexicographic order of the identifier of the neighboring node and the identifier of the node;

responsive to determining that the name is validly reachable via the neighboring node;

adding the neighboring node to a valid list for the name;

determining, for the name, a next-hop neighbor list from the valid list;

computing new routing information for one or more neighboring nodes in the next-hop neighbor list; and

updating a routing table to include the new routing information for the one or more neighboring nodes for the name;

determine whether the first anchor node is a designated anchor node based on the new routing information in the updated routing table and a routing metric for the first anchor node.

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

wherein the forwarding mechanism is configured to determine whether the first anchor is a designated anchor node further based on lexicographic order of the identifier of the first anchor node compared to an 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 neighbor node based on lexicographic order of the identifier of the neighbor node.

20. The apparatus of claim 17, further comprising a notification mechanism configured to, in response to determining that the first anchor node is not a designated anchor node, 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 the identifier of the first anchor node compared to an 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.