Avoiding micro-loops in a ring topology of a network

Patent metadata

Field	Value
Publication number	US-9942057-B2
Application number	US-201514743715-A
Country	US
Kind code	B2
Filing date	Jun 18, 2015
Priority date	Oct 9, 2011
Publication date	Apr 10, 2018
Grant date	Apr 10, 2018

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.

First claim

What is claimed is:

1. A method, comprising:
performing operations in a network including bi-directional communicating packets according to a ring topology by a plurality of packet switching devices, with the plurality of packet switching devices including a particular packet switching device, a first neighbor packet switching device, and a non-neighbor packet switching device, with the particular packet switching device and the first neighbor packet switching device being neighbors in the ring topology via particular communications when active, and with said operations including:
generating, by the particular packet switching device, a particular packet including particular link state information identifying an unavailability of said particular communications; and
sending through the ring topology, by the particular packet switching device to the non-neighbor packet switching device the particular packet causing link state information advertising a high cost of said particular communication to initially propagate neighbor-by-neighbor through the ring topology not from the particular packet switching device but rather neighbor-by-neighbor through the ring topology from the non-neighbor packet switching device including away from the non-neighbor packet switching device towards the particular packet switching device;
wherein the particular packet switching device selectively sends said particular link state information identifying the unavailability of said particular communications to only a single packet switching device of the plurality of packet switching devices in the ring topology that is not a current neighbor of the particular packet switching device, with the single non-neighbor packet switching device being the non-neighbor packet switching device that 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 with forwarding information to send packets addressed to the first neighbor packet switching device through the particular packet switching device.

2. The method of claim 1 , wherein forwarding information in the non-neighbor packet switching device directs the non-neighbor packet switching device 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 said particular link state information of unavailability advertises said particular communications as being a very large cost.

5. 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.

6. The method of claim 1 , comprising: flooding, by the particular packet switching device link state information identifying an unavailability of particular communications to a neighbor packet switching device in the ring topology, after a predetermined time duration after said sending the particular packet to the non-neighbor packet switching device, with the predetermined time duration selected to allow for said particular link state information to said initially propagate neighbor-by-neighbor through the ring topology to the particular packet switching device.

7. The method of claim 1 , including flooding by the particular packet switching device link state information identifying an unavailability of particular communications to a neighbor packet switching device in the ring topology in response to the particular packet switching device receiving said particular link state information from a neighbor packet switching device in the ring topology that was said initially propagated neighbor-by-neighbor through the ring topology from the non-neighbor packet switching device.

8. 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.

9. 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 following the ring topology while not passing through said particular communications.

10. A particular packet switching device, comprising:
one or more processing elements;
memory;
a plurality of interfaces sending and receiving packets; and
one or more packet switching mechanisms packet switching packets among said interfaces;
wherein the particular packet switching device performs operations, with said operations including:
generating a particular packet including tunnel information, and with the particular packet including particular link state information identifying an unavailability of particular communications in a network of a plurality of packet switching devices communicating bi-directionally in and according to 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 not neighbors in the ring topology when said particular communications is unavailable; and
sending, via a tunnel not passing through said particular communications based on said tunnel information through the ring topology to a non-neighbor packet switching device in the ring topology when said particular communications is unavailable, the particular packet causing link state information advertising a high cost of said particular communication to initially propagate neighbor-by-neighbor through the ring topology not from the particular packet switching device but rather neighbor-by-neighbor through the ring topology away from the non-neighbor packet switching device including in neighbor-exchanged link state information away from the non-neighbor packet switching device towards the particular packet switching device in the direction that is not through said particular communications.

11. The particular packet switching device of claim 10 , wherein forwarding information in the non-neighbor packet switching device directs the non-neighbor packet switching device 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.

12. The particular packet switching device of claim 10 , 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 with forwarding information to send packets addressed to the first neighbor packet switching device through the particular packet switching device.

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

14. A method, comprising:
generating, by a particular packet switching device, a particular packet including tunnel information, and with the particula

Assignees

• Bryant Stewart Frederick
• Filsfils Clarence
• Shand Ian Michael Charles
• Cisco Tech Inc

Inventors

• Bryant Stewart Frederick
• Filsfils Clarence
• Shand Ian Michael Charles

Classifications

• H04L45/18

  Loop-free operations · CPC title

• H04L43/0811

  by checking connectivity · CPC title

• H04L12/437 Primary

  Ring fault isolation or reconfiguration {(for SDH/SONET ring networks H04J3/085)} · CPC title

• H04L45/28

  using route fault recovery · CPC title

• H04L12/427

  with decentralised control · CPC title