Avoiding Micro-loops in a Ring Topology of a Network

• US 20150288536A1
• Filed: 06/18/2015
• Published: 10/08/2015
• 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,942,057 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method, comprising:

generating, by a particular packet switching device, a particular packet including particular link state information identifying an unavailability of particular communications in a network of a plurality of packet switching devices configured to communicate bi-directionally in a ring topology, with the particular packet switching device and a first neighbor packet switching device being neighbors in the ring topology via said particular communications when active; and

sending, by the particular packet switching device to a non-neighbor packet switching device in the ring topology, the particular packet so that link state information advertising the high cost of said particular communication initially propagates neighbor-by-neighbor in the ring topology away from the non-neighbor packet switching device.

2. The method of claim 1, wherein the non-neighbor packet switching device is currently configured to send packets addressed to the first neighbor packet switching device in the direction not through the particular packet switching device in the ring topology.

3. The method of claim 2, wherein the non-neighbor packet switching device is a closest packet switching device to the particular packet switching device in the ring topology in the direction not through said particular communications.

4. The method of claim 1, wherein the non-neighbor packet switching device is a packet switching device furthest away from the particular packet switching device in the ring topology in the direction not through said particular communications that is currently configured to send packets to the first neighbor packet switching device through the particular packet switching device.

5. The method of claim 1, wherein said particular link state information of unavailability advertises said particular communications as being a very large cost.

6. The method of claim 1, comprising:

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

flooding, by the non-neighbor packet switching device, said particular link state information to each of its neighbor packet switching devices in the ring topology.

7. The method of claim 1, comprising:

flooding, by the particular packet switching device subsequent to delaying after said sending the particular packet, of link state information identifying an unavailability of particular communications to a neighbor packet switching device in the ring topology, with said delaying providing time for said particular link state information to said propagate neighbor-by-neighbor around the ring topology.

8. The method of claim 7, wherein said flooding is performed in response to the particular packet switching device receiving said particular link state information from a neighbor packet switching device in the ring topology.

9. The method of claim 7, wherein said flooding is performed in response to an expiration of a time period after said sending the particular packet.

10. The method of claim 1, wherein said generating and sending operations are performed in response to said particular communications being no longer available between the particular packet switching device and the first neighbor packet switching device.

11. The method of claim 1, wherein said sending the particular packet is performed using a tunnel from the particular packet switching device to the non-neighbor packet switching device, with the tunnel not passing not through said particular communications.

12. The method of claim 1, wherein each of packet switching devices in the ring topology is configured to exchange link state information with its current one or more neighbors in the ring topology and to update its respective local forwarding information accordingly.

13. A particular packet switching device, comprising:

one or more processing elements;

memory;

a plurality of interfaces configured to send and receive packets; and

one or more packet switching mechanisms configured to packet switch packets among said interfaces;

wherein the particular packet switching device is configured to perform operations, with said operations including;

generating a particular packet including particular link state information identifying an unavailability of particular communications in a network of a plurality of packet switching devices configured to communicate bi-directionally in a ring topology, with the particular packet switching device and a first neighbor packet switching device being neighbors in the ring topology via said particular communications when active; and

sending, to a non-neighbor packet switching device in the ring topology, the particular packet so that link state information advertising the high cost of said particular communication initially propagates neighbor-by-neighbor in the ring topology away from the non-neighbor packet switching device.

14. The particular packet switching device of claim 13, wherein the non-neighbor packet switching device is currently configured to send packets addressed to the first neighbor packet switching device in the direction not through the particular packet switching device in the ring topology.

15. The particular packet switching device of claim 13 wherein the non-neighbor packet switching device is a packet switching device furthest away from the particular packet switching device in the ring topology in the direction not through said particular communications that is currently configured to send packets to the first neighbor packet switching device through the particular packet switching device.

16. The particular packet switching device of claim 13, wherein said particular link state information of unavailability advertises said particular communications as being a very large cost.

17. The particular packet switching device of claim 13, wherein said sending the particular packet is performed using a tunnel from the particular packet switching device to the non-neighbor packet switching device, with the tunnel not passing not through said particular communications.

18. A method, comprising:

generating, by a particular packet switching device, a particular packet including particular link state information identifying a high cost of particular communications for reaching a first neighbor packet switching device from the particular packet switching device, wherein the particular packet switching device and the first neighbor packet switching device are two of a plurality of packet switching devices in a network configured to communicate bi-directionally in a ring topology, with the particular packet switching device and the first neighbor packet switching device being neighbors in the ring topology via said particular communications when active; and

wherein each of the plurality of packet switching devices is configured to exchange link state information with their current neighbors in the ring topology and to update their respective local forwarding information accordingly; and

sending, by the particular packet switching device to an intermediate packet switching device of the plurality of packet switching devices which is not a neighbor of the particular packet switching device in the ring topology, the particular packet so that link state information advertising the high cost of said particular communication initially propagates in the ring topology away from the intermediate packet switching device which includes initially propagating in neighbor-exchanged link state information towards the particular packet switching device in the direction that is not through said particular communications.

19. The method of claim 18, wherein the intermediate packet switching device is currently configured to send packets addressed to the first neighbor packet switching device in the direction not through the particular packet switching device in the ring topology.

20. The method of claim 18, wherein the intermediate packet switching device is a packet switching device furthest away from the particular packet switching device in the ring topology in the direction not through said particular communications that is currently configured to send packets addressed to the first neighbor packet switching device through the particular packet switching device.