Capability aware routing

• US 10,171,263 B2
• Filed: 11/30/2017
• Issued: 01/01/2019
• Est. Priority Date: 01/27/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Lindem, III, Alfred C., Psenak, Peter, Wijnands, Ijsbrand
• Primary Examiner(s): Tran, Phuc H
• Application Number:
  US15/826,900
• Publication Number:
  US 20180159700A1
• Time in Patent Office: 397 Days
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/127 based on intermediate node capabilities

Abstract

Various systems and methods for bypassing one or more non-capable nodes. For example, one method involves a capable node determining that an adjacent node is non-capable, where capable nodes are configured to implement a data plane capability and non-capable nodes are not. The method then involves identifying a downstream node that is capable. The downstream node is on a shortest path. The method also involves generating information that identifies a tunnel to the downstream node.

Claims

1. A method comprising:

detecting a plurality of equal cost nodes, wherein

the plurality of equal cost nodes are equal cost with respect to a source node, and

the source node is capable by virtue of implementing a data plane capability;

determining whether one or more nodes of the plurality of equal cost nodes are capable, wherein

a capable node of the one or more nodes is capable by virtue of implementing the data plane capability, and

a non-capable node of the one or more nodes is non-capable by virtue of not implementing the data plane capability;

in response to at least one of the plurality of equal cost nodes being capable, selecting a capable node of the at least one of the plurality of equal cost nodes as a next-hop destination for network traffic; and

in response to none of the plurality of equal cost nodes being capable,

selecting a non-capable node of the plurality of equal cost nodes as the next-hop destination, and

implementing a network path from the source node to a capable downstream node, wherein

the capable downstream node is downstream of the non-capable node, and

the capable downstream node is capable by virtue of implementing the data plane capability.

2. The method of claim 1, wherein the implementing comprises:

performing a shortest path first calculation, wherein the shortest path first calculation facilitates identification of a shortest path.

3. The method of claim 2, wherein

each node between the source node and the capable downstream node on the shortest path is non-capable.

4. The method of claim 1, wherein

the network path is a tunnel, and

the tunnel traverses the non-capable node.

5. The method of claim 4, the implementing the network path comprises:

establishing the tunnel, wherein

the establishing comprises generating tunnel information, and

the tunnel begins at the source node and ends at the capable downstream node.

6. The method of claim 5, wherein the establishing comprises:

adding the non-capable node to a tunnel prototype as the next-hop destination for network traffic.

7. The method of claim 5, further comprising:

identifying the capable downstream node, wherein

the identifying is performed by the source node, and

the capable downstream node is on a shortest path from the source node to the capable downstream node.

8. The method of claim 7, further comprising:

detecting a configuration change, wherein

the configuration change comprises at least one of a topology change or a node configuration change; and

in response to the detecting the configuration change, updating a list of tunnels, wherein the list of tunnels comprises information identifying the tunnel.

9. The method of claim 8, wherein

the updating comprises

removing the information identifying a first tunnel from the list of tunnels, and the removing comprises

determining whether the information identifying the first tunnel indicates that the tunnel has exceeded an age threshold.

10. The method of claim 1, further comprising:

performing a next-hop calculation, wherein

the next-hop calculation is performed prior to the detecting, and

the detecting is based, at least in part, on a result of the next-hop calculation.

11. The method of claim 1, further comprising:

in response to the at least one of the plurality of equal cost nodes being capable,

updating a feature-specific routing information base, wherein

the feature-specific routing information base is stored by the source node.

12. The method of claim 11, further comprising:

updating a unicast routing information base, wherein

the unicast routing information base is stored by the source node.

13. The method of claim 1, wherein the determining comprises:

selecting a selected node of the plurality of equal cost nodes;

determining whether the selected node is capable or non-capable;

in response to the selected node being capable, updating a list of capable nodes; and

in response to the selected node being non-capable, updating a list of non-capable nodes.

14. A network device comprising:

one or more processors, wherein

the network device is a source node, and

the network device is configured to implement a data plane capability;

one or more network interfaces, coupled to the one or more processors and configured to be coupled to a network;

a computer-readable storage medium, coupled to the one or more processors; and

a plurality of instructions, encoded in the computer-readable storage medium and configured to cause the one or more processors to

detect a plurality of equal cost nodes, wherein

the plurality of equal cost nodes are equal cost with respect to the source node, and

the source node is capable by virtue of implement the data plane capability,

determine whether one or more nodes of the plurality of equal cost nodes are capable, wherein

a capable node of the one or more nodes is capable by virtue of being configured to implement the data plane capability, and

a non-capable node of the one or more nodes is non-capable by virtue of not being configured to implement the data plane capability,

in response to at least one of the plurality of equal cost nodes being capable, select a capable node of the at least one of the plurality of equal cost nodes as a next-hop destination for network traffic, and

in response to none of the plurality of equal cost nodes being capable,

select a non-capable node of the plurality of equal cost nodes as the next-hop destination, and

implement a network path from the source node to a capable downstream node, wherein

the capable downstream node is downstream of the non-capable node, and

the capable downstream node is capable by virtue of being configured to implement the data plane capability.

15. The network device of claim 14, wherein

the network path is a tunnel,

the tunnel traverses the non-capable node, and

the instructions configured to cause the one or more processors to implement the network path comprise instructions configured to cause the one or more processors to establish the tunnel, wherein

the instructions configured to cause the one or more processors to establish the tunnel comprise instructions configured to cause the one or more processors to generate tunnel information, and

the tunnel begins at the source node and ends at the capable downstream node.

16. The network device of claim 15, wherein the instructions are further configured to cause the one or more processors to:

identify the capable downstream node, wherein

the capable downstream node is on a shortest path from the source node to the capable downstream node.

17. The network device of claim 14, wherein the instructions are further configured to cause the one or more processors to:

perform a next-hop calculation, wherein

the next-hop calculation is performed prior to detection of the plurality of equal cost nodes, and

the detection of the plurality of equal cost nodes is based, at least in part, on a result of the next-hop calculation.

18. The network device of claim 14, wherein the instructions are further configured to cause the one or more processors to:

update a feature-specific routing information base, wherein

the source node further comprises a memory, and

the feature-specific routing information base is stored in the memory; and

update a unicast routing information base, wherein

the unicast routing information base is stored in the memory.

19. The network device of claim 14, wherein the instructions are further configured to cause the one or more processors to:

select a selected node of the plurality of equal cost nodes;

determine whether the selected node is capable or non-capable;

in response to the selected node being capable, update a list of capable nodes; and

in response to the selected node being non-capable, update a list of non-capable nodes.

20. A computer program product comprising:

a plurality of instructions, comprising

a first set of instructions, executable by a processor of a network device, configured to detect a plurality of equal cost nodes, wherein

the network device is a source node,

the plurality of equal cost nodes are equal cost with respect to the source node, and

the source node is capable by virtue of implement a data plane capability,

a second set of instructions, executable by the processor, configured to determine whether one or more nodes of the plurality of equal cost nodes are capable, wherein

a capable node of the one or more nodes is capable by virtue of being configured to implement the data plane capability, and

a non-capable node of the one or more nodes is non-capable by virtue of not being configured to implement the data plane capability,

a third set of instructions, executable by the processor, configured to in response to at least one of the plurality of equal cost nodes being capable, select a capable node of the at least one of the plurality of equal cost nodes as a next-hop destination for network traffic, and

a fourth set of instructions, executable by the processor, configured to in response to none of the plurality of equal cost nodes being capable,

select a non-capable node of the plurality of equal cost nodes as the next-hop destination, and

implement a network path from the source node to a capable downstream node, wherein

the capable downstream node is downstream of the non-capable node, and

the capable downstream node is capable by virtue of being configured to implement the data plane capability; and

a non-transitory computer-readable storage medium, wherein the instructions are encoded in the non-transitory computer-readable storage medium.