System and method for efficient name-based content routing using link-state information in information-centric networks

• US 10,003,520 B2
• Filed: 12/22/2014
• Issued: 06/19/2018
• Est. Priority Date: 12/22/2014
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Garcia-Luna-Aceves, Jose J.
• Primary Examiner(s): Srivastava, Vivek
• Assistant Examiner(s): Raza, Muhammad
• Application Number:
  US14/579,925
• Publication Number:
  US 20160182353A1
• Time in Patent Office: 1,275 Days
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 45/38 Flow based routing

Abstract

One embodiment of the present invention provides a system for updating link-status information associated with a prefix in an information-centric network (ICN). During operation, a first node in the ICN receives a link-state advertisement (LSA) message from a neighbor node with the LSA message specifying a prefix and an anchor node advertising the specified prefix. The system determines, based on topology information stored on the first node, whether a shortest-path condition is met, and forwards the received LSA message to other neighbors of the first node in response to the shortest-path condition being met.

Claims

1. A computer-executable method for updating link-status information associated with a prefix in an information-centric network (ICN), the method comprising:

receiving, by a first node in the ICN, a link-state advertisement (LSA) message from a neighbor node, wherein the LSA message specifies a prefix and an anchor node advertising the specified prefix;

identifying one or more valid next-hop neighbors to the prefix;

determining whether each of the one or more valid next-hop neighbors is closer to the anchor node than the first node, by using a shortest-path first (SPF) algorithm to compute a distance between the anchor node and each of the one or more valid next-hop neighbors, to generate topology information;

determining, based on the topology information stored on the first node, whether a shortest-path condition is met, wherein determining whether the shortest-path condition is met includes computing, using the SPF algorithm, a shortest distance from the first node to the specified prefix;

in response to determining that a valid next-hop neighbor has a same distance to the anchor node as that of the first node, determining whether the valid next-hop neighbor has a smaller lexicographic value compared with that of the first node;

in response to the shortest-path condition being met, forwarding the received LSA message to other neighbors of the first node; and

in response to the shortest-path condition not being met, dropping the LSA message.

2. The method of claim 1, further comprising:

generating, by the first node, an LSA message reflecting a status change to a local prefix; and

forwarding the generated LSA message to neighbors of the first node.

3. The method of claim 1, wherein the topology information includes a routing table, the method further comprising:

updating, by the first node, the routing table based on the received LSA message.

4. The method of claim 1, wherein the LSA message further includes a sequence number created by the anchor node, and wherein the sequence number increments each time the anchor node updates the LSA message for the specified prefix.

5. The method of claim 4, further comprising:

determining whether the sequence number included in the LSA message is greater than a prior sequence number stored in the topology information.

6. The method of claim 5, further comprising:

in response to determining that the sequence number included in the LSA message is not greater than a prior sequence number stored in the topology information, dropping the LSA message.

7. The method of claim 1, wherein the LSA message further includes a remaining lifetime value, and the method further comprises:

determining whether the remaining lifetime value is greater than zero; and

in response to determining that the remaining lifetime value is not greater than zero, dropping the LSA message.

8. A non-transitory computer-readable storage medium storing instructions that when executed by a computing device cause the computing device to perform a method for updating link-status information associated with a prefix in an information-centric network (ICN), the method comprising:

receiving, by a first node in the ICN, a link-state advertisement (LSA) message from a neighbor node, wherein the LSA message specifies a prefix and an anchor node advertising the specified prefix;

identifying one or more valid next-hop neighbors to the prefix;

determining whether each of the one or more valid next-hop neighbors is closer to the anchor node than the first node, by using a shortest-path first (SPF) algorithm to compute a distance between the anchor node and each of the one or more valid next-hop neighbors, to generate topology information;

determining, based on the topology information stored on the first node, whether a shortest-path condition is met, wherein determining whether the shortest-path condition is met includes computing, using the SPF algorithm, a shortest distance from the first node to the specified prefix;

in response to determining that a valid next-hop neighbor has a same distance to the anchor node as that of the first node, determining whether the valid next-hop neighbor has a smaller lexicographic value compared with that of the first node;

in response to the shortest-path condition being met, forwarding the received LSA message to other neighbors of the first node; and

in response to the shortest-path condition not being met, dropping the LSA message.

9. The non-transitory computer-readable storage medium of claim 8, wherein the method further comprises:

generating, by the first node, an LSA message reflecting a status change to a local prefix; and

forwarding the generated LSA message to neighbors of the first node.

10. The non-transitory computer-readable storage medium of claim 8, wherein the topology information includes a routing table, and wherein the method further comprises updating, by the first node, the routing table based on the received LSA message.

11. The non-transitory computer-readable storage medium of claim 8, wherein the LSA message further includes a sequence number created by the anchor node, and wherein the sequence number increments each time the anchor node updates the LSA message for the specified prefix.

12. The non-transitory computer-readable storage medium of claim 11, wherein the method further comprises:

determining whether the sequence number included in the LSA message is greater than a prior sequence number stored in the topology information.

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

in response to determining that the sequence number included in the LSA message is not greater than a prior sequence number stored in the topology information, dropping the LSA message.

14. The non-transitory computer-readable storage medium of claim 8, wherein the LSA message further includes a remaining lifetime value, and the method further comprises:

determining whether the remaining lifetime value is greater than zero; and

in response to determining that the remaining lifetime value is not greater than zero, dropping the LSA message.

15. A computer system for updating link-status information associated with a prefix in an information-centric network (ICN), the system comprising:

a processor; and

a storage device coupled to the processor and storing instructions which when executed by the processor cause the processor to perform a method, the method comprising;

receiving, by a first node in the ICN, a link-state advertisement (LSA) message from a neighbor node, wherein the LSA message specifies a prefix and an anchor node advertising the specified prefix;

identifying one or more valid next-hop neighbors to the prefix;

determining whether each of the one or more valid next-hop neighbors is closer to the anchor node than the first node, by using a shortest-path first (SPF) algorithm to compute a distance between the anchor node and each of the one or more valid next-hop neighbors, to generate topology information;

determining, based on the topology information stored on the first node, whether a shortest-path condition is met, wherein determining whether the shortest-path condition is met includes computing, using the SPF algorithm, a shortest distance from the first node to the specified prefix;

in response to determining that a valid next-hop neighbor has a same distance to the anchor node as that of the first node, determining whether the valid next-hop neighbor has a smaller lexicographic value compared with that of the first node;

in response to the shortest-path condition being met, forwarding the received LSA message to other neighbors of the first node, and

in response to the shortest-path condition not being met, dropping the LSA message.

16. The system of claim 15, wherein the method further comprises:

generating, by the first node, an LSA message reflecting a status change to a local prefix; and

forwarding the generated LSA message to neighbors of the first node.

17. The system of claim 15, wherein the topology information includes a routing table, and wherein the method further comprises updating, by the first node, the routing table based on the received LSA message.

18. The system of claim 15, wherein the LSA message further includes a sequence number created by the anchor node, and wherein the sequence number increments each time the anchor node updates the LSA message for the specified prefix.

19. The system of claim 18, wherein the method further comprises:

determining whether the sequence number included in the LSA message is greater than a prior sequence number stored in the topology information.

20. The system of claim 19, wherein the method further comprises:

in response to determining that the sequence number included in the LSA message is not greater than a prior sequence number stored in the topology information, dropping the LSA message.