Automatically detecting potential microloop conditions associated with network convergence

Patent metadata

Field	Value
Publication number	US-2018212860-A1
Application number	US-201715411451-A
Country	US
Kind code	A1
Filing date	Jan 20, 2017
Priority date	Jan 20, 2017
Publication date	Jul 26, 2018
Grant date	—

Abstract

The disclosed embodiments provide a system that automatically detects a potential microloop condition associated with network convergence. During operation, the system obtains a topology for a network containing a set of nodes connected by a set of links. Next, the system uses the topology to detect a ring containing at least four hops in the network. The system then outputs an indication of a potential microloop condition associated with one or more nodes on the ring to improve improve routing of network traffic by the one or more nodes.

First claim

What is claimed is:

1 . A method, comprising:
obtaining a topology for a network comprising a set of nodes connected by a set of links; using the topology to detect, by a node in the set of nodes, a ring comprising at least four hops in the network; and outputting an indication of a potential microloop condition associated with one or more nodes on the ring to improve routing of network traffic by the one or more nodes.

2 . The method of claim 1 , wherein using the topology to detect the ring comprises:
removing a link between the node and another node in the topology; calculating, based on the removed link, an alternative path between the node and the other node; and detecting the ring when the alternative path comprises more than two hops.

3 . The method of claim 2 , wherein the alternative path comprises a loop-free alternate (LFA) path between the node and the other node.

4 . The method of claim 1 , further comprising:
obtaining, based on the potential microloop condition, one or more loop-free alternate (LFA) paths from the node to another node on the ring; and storing the one or more LFA paths as backup paths between the node and the other node.

5 . The method of claim 4 , further comprising:
when a failure in a link between the node and the other node is detected, using the one or more LFA paths to route network traffic between the node and the other node.

6 . The method of claim 5 , wherein the one or more LFA paths comprise at least one of:
a local LFA; and a remote LFA.

7 . The method of claim 1 , wherein outputting the indication of the potential microloop condition comprises:
assigning the potential microloop condition to all nodes on the ring.

8 . The method of claim 1 , wherein outputting the indication of the potential microloop condition comprises:
transmitting the indication from the node to other nodes on the ring.

9 . The method of claim 1 , wherein convergence of the network is performed using a link state protocol.

10 . An apparatus, comprising:
one or more processors; and memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
obtain a topology for a network comprising a set of nodes connected by a set of links;
use the topology to detect a ring comprising at least four hops in the network; and
output an indication of a potential microloop condition associated with one or more nodes on the ring to improve routing of network traffic by the one or more nodes.

11 . The apparatus of claim 10 , wherein using the topology to detect the ring comprises:
removing a link between the node and another node in the topology; calculating, based on the removed link, an alternative path between the node and the other node; and detecting the ring when the alternative path comprises more than two hops.

12 . The apparatus of claim 10 , wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
obtain, based on the potential microloop condition, one or more loop-free alternate (LFA) paths for the node to another node on the ring; and store the one or more LFA paths as backup paths between the node and the other node.

13 . The apparatus of claim 12 , wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
use the one or more LFA paths to route network traffic between the node and the other node when a failure in a link between the node and the other node is detected.

14 . The apparatus of claim 13 , wherein the one or more LFA paths comprise at least one of:
a local LFA; and a remote LFA.

15 . The apparatus of claim 10 , wherein outputting the indication of the potential microloop condition comprises:
assigning the potential microloop condition to all nodes on the ring.

16 . The apparatus of claim 10 , wherein outputting the indication of the potential microloop condition comprises:
transmitting the indication from the node to other nodes on the ring.

17 . A system, comprising:
a network comprising a set of nodes connected by a set of links; and a node in the set of nodes, wherein the node comprises a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to:
obtain a topology for the network;
use the topology to detect a ring comprising at least four hops in the network; and
output an indication of a potential microloop condition associated with one or more nodes on the ring to improve routing of network traffic by the one or more nodes.

18 . The system of claim 17 , wherein using the topology to detect the ring comprises:
removing a link between the node and another node in the topology; calculating, based on the removed link, an alternative path between the node and the other node; and detecting the ring when the alternative path comprises more than two hops.

19 . The system of claim 17 , wherein outputting the indication of the potential microloop condition comprises:
assigning the potential microloop condition to all nodes on the ring.

20 . The system of claim 17 , wherein outputting the indication of the potential microloop condition comprises:
transmitting the indication from the node to other nodes on the ring.

Assignees

• Linkedin Corp

Inventors

• White Russell I
• Zandi Shafagh
• Kahn Zaid A

Classifications

• H04L49/102

  using shared medium, e.g. bus or ring · CPC title

• H04L45/18

  Loop-free operations · CPC title

• H04L45/20

  Hop count for routing purposes, e.g. TTL · CPC title

• H04L45/02 Primary

  Topology update or discovery · CPC title