Loop avoidance during network convergence in switched networks

• US 9,401,858 B2
• Filed: 06/30/2014
• Issued: 07/26/2016
• Est. Priority Date: 06/30/2014
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Francois, Pierre Jean Rene, Filsfils, Clarence, Previdi, Stefano B., Bryant, Stewart F., Shand, Ian Michael Charles
• Primary Examiner(s): Faroul, Farah
• Application Number:
  US14/319,353
• Publication Number:
  US 20150381406A1
• Time in Patent Office: 757 Days
• Field of Search: 370216-218
• US Class Current: 1/1
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

Various techniques can be used to avoid loops during network convergence after a topology change such as a failure. For example, a method can involve detecting a failure that disrupts an existing forwarding path between a node and a destination node; calculating at least one updated forwarding path from the node to the destination node; identifying a maximum time for at least a portion of the network to reach a post-convergence state with respect to the failure; until the maximum time has elapsed at the node, explicitly specifying at least a portion of the updated forwarding path in packet headers of any packets being sent from the node to the destination node; and after the maximum time has elapsed at the node, non-explicitly specifying the portion of the updated forwarding path in packet headers of any additional packets being sent from the node to the destination node.

Claims

1. A method comprising:

detecting a topology change within a network in which a segment routing (SR) protocol is implemented, wherein

the topology change disrupts an existing forwarding path between a first network node and a destination network node;

calculating new forwarding table information in response to the topology change, wherein

the new forwarding table information comprises forwarding table information for at least one updated forwarding path from the first network node to the destination network node, and

the new forwarding table information is generated according to the SR protocol;

identifying a maximum time for at least a portion of the network to reach a post-convergence state with respect to the topology change;

until the maximum time has elapsed at the first network node,

explicitly specifying at least a portion of the at least one updated forwarding path in a packet header of a packet, if the packet is being sent from the first network node to the destination network node; and

after the maximum time has elapsed at the first network node,

non-explicitly specifying the at least the portion of the at least one updated forwarding path in a packet header of an additional packet, if the additional packet is being sent from the first network node to the destination network node, wherein

the detecting, the calculating, the identifying, the explicitly specifying, and the non-explicitly specifying are performed by the first network node.

2. The method of claim 1, further comprising:

detecting the topology change at a second network node within the network, wherein

the first network node calculates the new forwarding information at a first time and performs the explicitly specifying the at least the portion of the at least one updated forwarding path from the first time until the first time plus the maximum time, and

the second network node calculates second new forwarding information at a second time; and

explicitly specifying at least a portion of a second updated forwarding path between the second network node and a second destination network node in a packet header of a packet sent from the second network node to the second destination network node from the second time until the second time plus the maximum time, wherein

the explicitly specifying the at least the portion of the second updated forwarding path is performed by the second network node.

3. The method of claim 1, further comprising:

detecting, after the topology change, that the first network node can communicate with a first set of network nodes without being affected by the topology change, and that a second set of network nodes can communicate with the destination network node without being affected by the topology change, but that the first set of network nodes is not included in the second set of network nodes; and

performing the explicitly specifying by generating a packet header that comprises;

a first sub-path identifier that identifies a path from the first network node to an edge of the first set of network nodes;

a second sub-path identifier that identifies at least a portion of a path from the edge of the first set of network nodes to an edge of the second set of network nodes; and

a third sub-path identifier that identifies a path from the edge of the second set of network nodes to the destination network node, wherein

the detecting and the performing are performed by the first network node.

4. The method of claim 3, wherein the non-explicitly specifying comprises:

generating a packet header that specifies fewer sub-path identifiers than the packet header generated during the explicitly specifying.

5. The method of claim 1, further comprising:

receiving a first packet, sent by the first network node, at a second network node, wherein

the first packet comprises

a first header explicitly specifying the at least the portion of the at least one updated forwarding path, and

the second network node receives the first packet before the second network node reaches a classic post-convergence state in response to the topology change.

6. The method of claim 1, further comprising:

receiving a first packet, sent by the first network node, at a second network node, wherein

the first packet comprises

a first header explicitly specifying the at least the portion of the at least one updated forwarding path, and

the second network node receives the first packet subsequent to the second network node reaching a classic post-convergence state in response to the topology change.

7. The method of claim 1, wherein the explicitly specifying comprises:

explicitly specifying a first N network nodes on the at least one updated forwarding path between the first network node and the destination network node.

8. A non-transitory computer-readable storage medium comprising program instructions executable by a first network node to:

detect a topology change within a network in which a segment routing (SR) protocol is implemented, wherein

the topology change disrupts an existing forwarding path between the first network node and a destination network node;

calculate new forwarding table information in response to the topology change, wherein

the new forwarding table information comprises forwarding table information for at least one updated forwarding path from the first network node to the destination network node, and

the new forwarding table information is generated according to the SR protocol;

identify a maximum time for at least a portion of the network to reach a post-convergence state with respect to the topology change;

until the maximum time has elapsed at the first network node,

explicitly specify at least a portion of the at least one updated forwarding path in a packet header of a packet, if the packet is being sent from the first network node to the destination network node; and

after the maximum time has elapsed at the first network node,

non-explicitly specify the at least the portion of the at least one updated forwarding path in a packet header of an additional packet, if the additional packet is being sent from the first network node to the destination network node.

9. The non-transitory computer-readable storage medium of claim 8, wherein the program instructions are further executable by the first network node to:

calculate the new forwarding information at a first time and execute the program instructions executable by the first network node to explicitly specify the at least the portion of the at least one updated forwarding path from the first time until the first time plus the maximum time, wherein

a second network node is configured to calculate second new forwarding information at a second time, and

the second network node is configured to explicitly specify at least a portion of a second updated forwarding path between the second network node and a second destination network node in a packet header of a packet sent from the second network node to the second destination network node from the second time until the second time plus the maximum time.

10. The non-transitory computer-readable storage medium of claim 8, wherein the program instructions are further executable by the first network node to:

detect, after the topology change, that the first network node can communicate with a first set of network nodes without being affected by the topology change, and that a second set of network nodes can communicate with the destination network node without being affected by the topology change, but that the first set of network nodes is not included in the second set of network nodes; and

execute the program instructions executable by the first network node to explicitly specify by virtue of comprising program instructions executable by the first network node to generate a packet header that comprises

a first sub-path identifier that identifies a path from the first network node to an edge of the first set of network nodes,

a second sub-path identifier that identifies at least a portion of a path from the edge of the first set of network nodes to an edge of the second set of network nodes, and

a third sub-path identifier that identifies a path from the edge of the second set of network nodes to the destination network node.

11. The non-transitory computer-readable storage medium of claim 10, wherein the program instructions executable by the first network node to non-explicitly specify comprise program instructions executable by the first network node to:

generate a packet header that specifies fewer sub-path identifiers than the packet header generated during the non-explicitly specifying.

12. The non-transitory computer-readable storage medium of claim 8, wherein the program instructions executable by the first network node to explicitly specify comprise program instructions executable by the first network node to:

explicitly specify a first N network nodes on the at least one updated forwarding path between the first network node and the destination network node.

13. The non-transitory computer-readable storage medium of claim 8, further comprising program instructions executable by a second network node to:

receive a first packet, sent by the first network node, at the second network node, wherein

the first packet comprises

a first header explicitly specifying the at least the portion of the at least one updated forwarding path.

14. A system comprising:

one or more processors; and

a memory storing program instructions executable by the one or more processors to

detect a topology change within a network in which a segment routing (SR) protocol is implemented, wherein

the topology change disrupts an existing forwarding path between a first network node and a destination network node,

calculate new forwarding table information in response to the topology change, wherein

the new forwarding table information comprises forwarding table information for at least one updated forwarding path from the first network node to the destination network node, and

the new forwarding table information is generated according to the SR protocol,

identify a maximum time for at least a portion of the network to reach a post-convergence state with respect to the topology change,

until the maximum time has elapsed at the first network node,

explicitly specify at least a portion of the at least one updated forwarding path in a packet header of a packet, if the packet is being sent from the first network node to the destination network node, and

after the maximum time has elapsed at the first network node,

non-explicitly specify the at least the portion of the at least one updated forwarding path in a packet header of an additional packet, if the additional packet is being sent from the first network node to the destination network node.

15. The system of claim 14, wherein the program instructions are further executable by the one or more processors to:

calculate the new forwarding information at a first time and execute the program instructions executable by the one or more processors to explicitly specify the at least the portion of the at least one updated forwarding path from the first time until the first time plus the maximum time, wherein

a second network node is configured to calculate second new forwarding information at a second time, and

the second network node is configured to explicitly specify at least a portion of a second updated forwarding path between the second network node and a second destination network node in a packet header of a packet sent from the second network node to the second destination network node from the second time until the second time plus the maximum time.

16. The system of claim 14, wherein the program instructions are further executable by the one or more processors to:

detect, after the topology change, that the first network node can communicate with a first set of network nodes without being affected by the topology change, and that a second set of network nodes can communicate with the destination network node without being affected by the topology change, but that the first set of network nodes is not included in the second set of network nodes; and

execute the program instructions executable by the one or more processors to explicitly specify by virtue of comprising program instructions executable by the one or more processors to generate a packet header that comprises

a first sub-path identifier that identifies a path from the first network node to an edge of the first set of network nodes,

a second sub-path identifier that identifies at least a portion of a path from the edge of the first set of network nodes to an edge of the second set of network nodes, and

a third sub-path identifier that identifies a path from the edge of the second set of network nodes to the destination network node.

17. The system of claim 16, wherein the program instructions executable by the one or more processors to non-explicitly specify comprise program instructions executable by the one or more processors to:

generate a packet header that specifies fewer sub-path identifiers than the packet header generated during the non-explicitly specifying.

18. The system of claim 14, wherein the program instructions executable by the one or more processors to explicitly specify comprise program instructions executable by the one or more processors to:

explicitly specify a first N network nodes on the at least one updated forwarding path between the first network node and the destination network node.

19. The system of claim 14, wherein additional program instructions are executable by the one or more processors of a second network node to:

receive a first packet, sent by the first network node, at the second network node, wherein

the first packet comprises

a first header explicitly specifying the at least the portion of the at least one updated forwarding path, and

the second network node receives the first packet before the second network node reaches a classic post-convergence state in response to the topology change.

20. The system of claim 14, wherein additional program instructions are executable by the one or more processors of a second network node to:

receive a first packet, sent by the first network node, at the second network node, wherein

the first packet comprises

a first header explicitly specifying the at least the portion of the at least one updated forwarding path, and

the second network node receives the first packet subsequent to the second network node reaching a classic post-convergence state in response to the topology change.