Interior gateway protocol flood minimization

Patent metadata

Field	Value
Publication number	US-11991074-B2
Application number	US-202117543717-A
Country	US
Kind code	B2
Filing date	Dec 6, 2021
Priority date	Jan 12, 2018
Publication date	May 21, 2024
Grant date	May 21, 2024

Abstract

Disclosed is a mechanism for implementing link state flooding reduction (LSFR) in an Interior Gateway Protocol (IGP) network. The mechanism includes receiving data indicating connectivity of a plurality of nodes in the network. A flooding topology is built based on the connectivity. This includes selecting one of the nodes as a root node, and building a tree of links connecting the root node to the nodes in the network. The flooding topology is stored in a memory. The flooding topology may not be to the remaining nodes in the network. Link state messages may then be flooded over the flooding topology.

First claim

What is claimed is:

1. A method implemented by a first node in a network, the method comprising:
sending a first link state message to other nodes in the network, wherein the first link state message comprises a mode field and a flooding reduction flag, wherein the mode field is set to indicate centralized link state flooding reduction, wherein the flooding reduction flag is set to indicate the first node supports link state flooding reduction;
obtaining data indicating connectivity of a plurality of nodes in the network;
computing a flooding topology according to the data indicating connectivity of the plurality of nodes, wherein the first node is selected as a leader node;
distributing the flooding topology to one or more nodes to prompt the one or more nodes to flood link state messages on the flooding topology without transmitting such link state messages through network links that are excluded from the flooding topology.

2. The method of claim 1 , wherein the flooding topology is a subset of a physical network topology of the network.

3. The method of claim 1 , wherein the network comprises a leaf-spine network or a spine-leaf network.

4. The method of claim 1 , wherein the flooding topology comprises one or more flooding paths, wherein each path of the one or more flooding paths comprises node information of a flooding path.

5. The method of claim 1 , wherein the first node is selected as the leader node based on an identifier (ID) of the first node.

6. The method of claim 1 , wherein the first node is selected as the leader node in an Intermediate System to Intermediate System (IS-IS) area or an Open Shortest Path First (OSPF) area, wherein the leader node is used to compute the flooding topology for the IS-IS area or the OSPF area.

7. The method of claim 1 , wherein the flooding topology is computed according to one of a plurality of selectable algorithms.

8. The method of claim 7 , wherein the one of the plurality of selectable algorithms is identified by an algorithm field of a received message.

9. The method of claim 1 , further comprising:
receiving a request specifying a number of leaf links to add to the flooding topology; and
adding leaf links to the flooding topology that correspond to the number of leaf links.

10. The method of claim 1 , wherein links in the flooding topology are selected to contain a minimum number of links to connect the plurality of nodes in the network to the leader node.

11. The method of claim 1 , further comprising:
receiving a first link state message across a link that is excluded from the flooding topology; and
flooding the first link state message across links according to the flooding topology.

12. The method of claim 1 , further comprising:
receiving a second link state message indicating a second node in the network is down; and
flooding the second link state message to links that connect between the first node and neighbors of the second node.

13. The method of claim 1 , further comprising:
receiving a third link state message indicating a first link in the network is down; and
sending the third link state message to links that connect to neighbors which also connect nodes adjacent to a node attached to the first link.

14. The method of claim 1 , wherein the link state message is an OSPF Link State Advertisement (LSA), or a IS-IS Link State Protocol data unit (LSP).

15. A first node in a network, the first node comprising:
at least one processor; and
one or more memories coupled to the at least one processor and storing instructions for execution by the at least one processor that, when executed by the at least one processor cause the first node to:
sending a first link state message to other nodes in the network, wherein the first link state message comprises a mode field and a flooding reduction flag, wherein the mode field is set to indicate centralized link state flooding reduction, wherein the flooding reduction flag is set to indicate the first node supports link state flooding reduction;
obtain data indicating connectivity of a plurality of nodes in the network;
compute a flooding topology according to the data indicating connectivity of the plurality of nodes, wherein the first node is selected as a leader node;
distribute the flooding topology to one or more nodes to prompt the one or more nodes to flood link state messages on the flooding topology without transmitting such link state messages through network links that are excluded from the flooding topology.

16. The first node of claim 15 , wherein the flooding topology is a subset of a physical network topology of the network.

17. The first node of claim 15 , wherein the network comprises a leaf-spine network or a spine-leaf network.

18. The first node of claim 15 , wherein the flooding topology comprises one or more flooding paths, wherein each path of the one or more flooding paths comprises node information of a flooding path.

Assignees

• Huawei Tech Co Ltd

Inventors

• Chen Huaimo
• Cheng Dean

Classifications

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/488

  using root node determination · CPC title

• H04L45/03

  by updating link state protocols · CPC title

• H04L45/32 Primary

  Flooding (denial of service attacks H04L63/1458) · CPC title