Avoiding Micro-loops in a Ring Topology of a Network

• US 20130088974A1
• Filed: 10/09/2011
• Published: 04/11/2013
• Est. Priority Date: 10/09/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Bryant, Stewart Frederick, Filsfils, Clarence, Shand, Ian Michael Charles
• Granted Patent: US 9,094,329 B2
• Time in Patent Office: Days
• US Class Current: 370/242
• CPC Class Codes: H04L 12/427 with decentralised control
• CPC Class Codes: H04L 12/437 Ring fault isolation or reconfiguration for SDH/SONET ring networks H04J3/085
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/28 using route fault recovery

Abstract

In one embodiment, micro-loops are avoided in ring topologies of packet switching devices by changing the order of propagation of link state information concerning failed communications between a particular packet switching device and a neighbor packet switching device. In one embodiment, the particular packet switching device communicates link state information of a high cost of the particular communications (e.g., in the direction from particular to neighbor packet switching devices) such that this link state information will propagate towards the particular packet switching device from at least from the furthest packet switching device in the ring topology that is currently configured to forward packets having a destination address of the neighbor packet switching device through the particular packet switching device.

Claims

1. A network, comprising:

a plurality of packet switching devices communicatively coupled in a ring topology, with the plurality of packet switching devices including;

a particular packet switching device, a neighbor packet switching device, a second neighbor packet switching device, and an intermediate packet switching device;

wherein the particular packet switching device and the neighbor packet switching device are neighbors in the ring topology when particular communications is established between the particular packet switching device and the neighbor packet switching device;

wherein the particular packet switching device and the second neighbor packet switching device are neighbors in the ring topology;

wherein each of the plurality of packet switching devices are configured to exchange link state information and to update their respective local forwarding information accordingly; and

wherein the particular packet switching device is configured to cause a particular link state packet, including particular link state information identifying a very high cost of the particular communications for reaching the neighbor packet switching device from the particular packet switching device, to be communicated to the neighbor packet switching device such that said particular link state information is processed by the neighbor packet switching device before any other packet switching device in the plurality of packet switching devices; and

wherein the particular packet switching device is configured not to flood said particular link state information to the second neighbor packet switching device.

2. The network of claim 1,wherein said configuration of the particular switching device includes said causing of the particular link state packet to be communicated to the neighbor packet switching device in response to the particular communications being no longer available between the particular packet switching device and the neighbor packet switching device.

3. The network of claim 1, wherein the intermediate packet switching device is configured to forward packets addressed to the neighbor packet switching device to another packet switching device of the plurality of packet switching devices towards the neighboring node and away from the particular packet switching device in the ring topology;

wherein the packet switching device is configured to communicate with the intermediate packet switching device via a tunnel through one or more packet switching devices of the plurality of packet switching devices; and

wherein said causing of the particular link state packet to be communicated to the neighbor packet switching device includes sending a tunnel packet, including a packet addressed to the neighbor packet switching device and including the particular link state packet, over the tunnel.

4. The network of claim 1, wherein the particular packet switching device is configured to flood to the second neighbor packet switching device, subsequent to said causing of the particular link state packet to be communicated to the neighbor packet switching device, link state information identifying the unavailability of the particular communications.

5. The network of claim 4, wherein said flooding of said link state information identifying the unavailability of the particular communications is configured to be performed in response to the particular packet switching device receiving the particular link state information from the second neighbor packet switching device.

6. The network of claim 4, wherein said flooding of said link state information identifying the unavailability of the particular communications is configured to be performed in response to an expiration of a time period after said causing of the particular link state packet to be communicated to the neighbor packet switching device.

7. The network of claim 1, wherein each packet switching device, different than the particular packet switching device, of the plurality of packet switching devices is configured to flood said particular link state information only after updating its local forwarding information.

8. A network, comprising:

a plurality of packet switching devices communicatively coupled in a ring topology, with the plurality of packet switching devices including;

a particular packet switching device, a neighbor packet switching device, a second neighbor packet switching device, and an intermediate packet switching device;

wherein the particular packet switching device and the neighbor packet switching device are neighbors in the ring topology when particular communications is established between the particular packet switching device and the neighbor packet switching device;

wherein the particular packet switching device and the second neighbor packet switching device are neighbors in the ring topology;

wherein each of the plurality of packet switching devices are configured to exchange link state information and to update their respective local forwarding information accordingly;

wherein the intermediate packet switching device is configured to forward packets addressed to the neighbor packet switching device to another packet switching device of the plurality of packet switching devices towards the neighboring node and away from the particular packet switching device in the ring topology, or is the furthest packet switching device from the particular packet switching device in the ring topology that is configured to forward packets addressed to the neighbor packet switching device through the particular packet switching device; and

wherein the particular packet switching device is configured to encapsulate a particular link state packet, including particular link state information identifying a very high cost of the particular communications for reaching the neighbor packet switching device from the particular packet switching device, and to send said encapsulated particular link state packet to the intermediate packet switching device in response to the particular communications being no longer available between the particular packet switching device and the neighbor packet switching device; and

wherein the particular packet switching device is configured not to flood said particular link state information to the second neighbor packet switching device.

9. The network of claim 8, wherein the intermediate packet switching device is configured to process said particular link state information, and to flood said particular link state information to a next packet switching device of the plurality of packet switching devices towards the particular packet switching device.

10. The network of claim 9, wherein the intermediate packet switching device is configured to flood said particular link state information to a next packet switching device of the plurality of packet switching devices towards the neighbor packet switching device.

11. The network of claim 8, wherein said encapsulated particular link state packet is communicated over a tunnel between the particular packet switching device and the intermediate packet switching device.

12. The network of claim 8, wherein the particular packet switching device is configured to flood to the second neighbor packet switching device, subsequent to said sending said encapsulated particular link state packet to the intermediate packet switching device, link state information identifying the unavailability of the particular communications.

13. The network of claim 12, wherein said flooding of said link state information identifying the unavailability of the particular communications is configured to be performed in response to the particular packet switching device receiving the particular link state information from the second neighbor packet switching device.

14. The network of claim 12, wherein said flooding of said link state information identifying the unavailability of the particular communications is configured to be performed in response to an expiration of a time period after said sending said encapsulated particular link state packet to the intermediate packet switching device.

15. A method, comprising:

performing operations by a particular packet switching device in a network;

wherein the network includes a plurality of packet switching devices communicatively coupled in a ring topology, with the plurality of packet switching devices including;

the particular packet switching device, a neighbor packet switching device, a second neighbor packet switching device, and an intermediate packet switching device;

wherein the particular packet switching device and the neighbor packet switching device are neighbors in the ring topology when particular communications is established between the particular packet switching device and the neighbor packet switching device;

wherein the particular packet switching device and the second neighbor packet switching device are neighbors in the ring topology;

wherein each of the plurality of packet switching devices are configured to exchange link state information and to update their respective local forwarding information accordingly; and

wherein said operations include;

generating a particular link state packet, including particular link state information identifying a very high cost of the particular communications for reaching the neighbor packet switching device from the particular packet switching device; and

communicating the particular link state packet to the neighbor packet switching device such that said particular link state information is processed by the neighbor packet switching device before any other packet switching device in the plurality of packet switching devices, but not flooding said particular link state information to the second neighbor packet switching device.

16. The method of claim 15, wherein said operation of generating the particular link state packet is performed in response to the particular communications being no longer available between the particular packet switching device and the neighbor packet switching device.

17. The method of claim 16, wherein said operations include flooding to the second neighbor packet switching device, subsequent to said causing of the particular link state packet to be communicated to the neighbor packet switching device, link state information identifying the unavailability of the particular communications.

18. The method of claim 15, wherein the intermediate packet switching device is configured to forward packets addressed to the neighbor packet switching device to another packet switching device of the plurality of packet switching devices towards the neighboring node and away from the particular packet switching device in the ring topology;

and

wherein said operation of communicating the particular link state packet to the neighbor packet switching device includes sending a tunnel packet, including a packet addressed to the neighbor packet switching device and including the particular link state packet, over a tunnel through one or more packet switching devices of the plurality of packet switching devices to the intermediate packet switching device.

19. A method, comprising:

performing operations by a particular packet switching device in a network;

wherein the network includes a plurality of packet switching devices communicatively coupled in a ring topology, with the plurality of packet switching devices including;

the particular packet switching device, a neighbor packet switching device, a second neighbor packet switching device, and an intermediate packet switching device;

wherein the particular packet switching device and the neighbor packet switching device are neighbors in the ring topology when particular communications is established between the particular packet switching device and the neighbor packet switching device;

wherein the particular packet switching device and the second neighbor packet switching device are neighbors in the ring topology;

wherein each of the plurality of packet switching devices are configured to exchange link state information and to update their respective local forwarding information accordingly; and

wherein said operations include;

encapsulating a particular link state packet, including particular link state information identifying a very high cost of the particular communications for reaching the neighbor packet switching device from the particular packet switching device; and

sending said encapsulated particular link state packet to the intermediate packet switching device in response to the particular communications being no longer available between the particular packet switching device and the neighbor packet switching device;

not flooding said particular link state information to the second neighbor packet switching device.

20. The method of claim 19, comprising:

processing, by the intermediate packet switching device, said particular link state information to update forwarding information of the intermediate packet switching device; and

flooding said particular link state information to a next packet switching device of the plurality of packet switching devices towards the particular packet switching device, and to a next packet switching device of the plurality of packet switching devices towards the neighbor packet switching device.

21. The method of claim 20, wherein the intermediate packet switching device is configured to forward packets addressed to the neighbor packet switching device to another packet switching device of the plurality of packet switching devices towards the neighboring node and away from the particular packet switching device in the ring topology, or is the furthest packet switching device from the particular packet switching device in the ring topology that is configured to forward packets addressed to the neighbor packet switching device through the particular packet switching device.

22. The method of claim 21, wherein said operations include flooding to the second neighbor packet switching device, subsequent to said causing of the particular link state packet to be communicated to the neighbor packet switching device, link state information identifying the unavailability of the particular communications.