Rapid flood processing

• US 9,906,441 B2
• Filed: 01/16/2015
• Issued: 02/27/2018
• Est. Priority Date: 01/17/2014
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Lu, Lu, Wang, Wei
• Primary Examiner(s): Kassim, Khaled
• Application Number:
  US15/112,014
• Publication Number:
  US 20160337233A1
• Time in Patent Office: 1,138 Days
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/66 Layer 2 routing, e.g. in Ethernet based MAN's

Abstract

When a device is a primary backbone device, the device adds a backbone device on each branch of a STP tree calculated by the device to a selected group, wherein a distance between the device and the added backbone device is kN hops, where k is an integer and N is a predefined natural number, 3≦N≦6, k=1, 2, . . . . The device enables a rapid flood function, and notifies backbone devices in the selected group of the enabling of the rapid flood function.

Claims

1. A rapid flood processing method, applied to a Shortest Path Bridging MAC (SPBM) network and comprising:

when a device is a primary backbone device, adding a backbone device on each branch of a Spanning Tree Protocol (STP) tree calculated by the device to a selected group, a distance between the device and the added backbone device being kN hops, and N being a predefined natural number and k being an integer, where 3≦

N≦

6, k=1, 2, . . . ; and

enabling a rapid flood function of the device, and notifying backbone devices in the selected group of the enabling of the rapid flood function.

2. The method of claim 1, wherein adding the backbone device on each branch of the STP tree calculated by the device to the selected group, comprises:

determining forwarding paths from the device to other backbone devices in the SPBM network according to the STP tree;

arranging the forwarding paths according to an ascending order of the number of hops of the forwarding paths;

removing a forwarding path from the arranged forwarding paths, wherein the number of hops of the removed forwarding path is smaller than N; and

adding the backbone device on each remaining forwarding path to the selected group, wherein the distance between the device and the added backbone device on each of the remaining forwarding paths is kN hops.

3. The method of claim 2, wherein adding the backbone device on each branch of the STP tree calculated by the device to the selected group, further comprises:

when the number M of hops from a specific backbone device to the last backbone device on each of the remaining forwarding paths meets a condition, adding the last backbone device to the selected group, wherein the specific backbone device is a backbone device on the forwarding path that is closest to the last backbone device and has been added to the selected group, and the condition is N/2<

M<

N.

4. The method of claim 1, further comprising:

determining according to configuration information whether the device is the primary backbone device; and

clearing the selected group after learning change of network topology, adding a backbone device on each branch of a new STP tree calculated by the device to a new selected group, wherein a distance between the device and the added backbone device is kN hops;

notifying backbone devices in the new selected group of the enabling of the rapid flood function, and notifying backbone devices in the previous selected group but not in the new selected group of the disabling of the rapid flood function.

5. The method of claim 4, wherein notifying the backbone devices in the new selected group of the enabling of the rapid flood function, and notifying the backbone devices in the previous selected group but not in the new selected group of the disabling of the rapid flood function comprises:

sending to all other backbone devices in the SPBM network a first notification message containing IDs of the backbone devices in the new selected group, wherein the first notification message indicates each of other backbone devices receiving the first notification message in the SPBM network to determine whether the first notification message contains an ID of the backbone device;

when determining that the first notification message does not contain the ID of the backbone device and the backbone device has enabled the rapid flood function, disabling the rapid flood function of the backbone device;

when determining that first notification message contains the ID of the backbone device and the backbone device has not enabled the rapid flood function, enabling the rapid flood function of the backbone.

6. A rapid flood processing apparatus, applied to a Shortest Path Bridging MAC (SPBM) network, the apparatus comprising a processor for executing instructions stored in a non-transitory computer readable storage medium, the instructions comprise:

selected group determining instructions, to add a backbone device on each branch of a Spanning Tree Protocol (STP) tree calculated by a device to a selected group when the device is a primary backbone device, a distance between the device and the added backbone device being kN hops, k being an integer and N being a predefined natural number, where 3≦

N≦

6, k=1,2, . . . ;

enabling instructions, to enable the rapid flood function of the device; and

notifying instructions, to notify backbone devices in the selected group of the enabling of the rapid flood function.

7. The apparatus of claim 6, wherein the selected group determining instructions comprise:

forwarding path determining sub-instructions, to determine forwarding paths from the device to other backbone devices in the SPBM network according to the STP tree;

arranging sub-instructions, to arrange the forwarding paths according to an ascending order of the number of hops of the forwarding paths;

removing sub-instructions, to delete a forwarding path from the arranged forwarding paths wherein the number of hops of the removed forwarding path is smaller than N; and

adding sub-instructions, to add the backbone device on each remaining forwarding paths to the selected group, wherein the distance between the device and the added backbone device on each of the remaining forwarding paths is kN hops.

8. The apparatus of claim 7, wherein the adding sub-instructions are further to, when the number M of hops from a specific backbone device to the last backbone device on each of the remaining forwarding paths meets a condition, add the last backbone device to the selected group, wherein the specific backbone device is a backbone device on the forwarding path that is closest to the last backbone device and has been added to the selected group, and the condition is N/2<

M<

N.

9. The apparatus of claim 6, further comprising:

role determining instructions, to determine through a configuration whether the device is the primary backbone device, wherein the configuration comprises determining according to configuration information whether the device is the primary backbone device;

the selected group determining instructions are to clear the selected group when learning change of network topology, add a backbone device on each branch of a new STP tree calculated by the device to a new selected group, wherein the distance between the device and the added backbone device is kN hops, and the change of the network topology does not include that the rapid flood function of the primary backbone device is disabled manually and the primary backbone device is abnormal; and

the notifying instructions are to notify backbone devices in the new selected group of the enabling of the rapid flood function, and notifying a backbone device in the previous selected group but not in the new selected group of the disabling of the rapid flood function.

10. The apparatus of claim 6, further comprising:

role determining instructions, to determine through an automatic vote method whether the device is the primary backbone device, wherein the automatic vote method comprises determining whether an ID of the device meets a predefined rule;

when determining that the ID of the backbone device meets the predefined rule, determine that the device is the primary backbone device;

when determining that the ID of the backbone device does not meet the predefined rule, determine that the device is not the primary backbone device;

the predefined rule comprises that the ID of the device is the largest or smallest ID among IDs of all backbone devices in the SPBM network;

when learning change of network topology and it is because a new backbone device is added to the SPBM network that the network topology changes, determine over again whether the ID of the device meets the predefined rule, wherein the change of the network topology does not comprise changes that the rapid flood function of the primary backbone device is disabled manually and the primary backbone device is abnormal;

the selected group determining instructions are to clear the selected group when the role determining instructions determine over again that the ID of the device meets the predefined rule, and add a backbone device on each branch of a new STP tree calculated by the device to a new selected group, wherein the distance between the device and the added backbone device is kN hops; and

the notifying instructions are to notify backbone devices in the new selected group of the enabling of the rapid flood function, and notify a backbone device in the previous selected group but not in the new selected group of the disabling of the rapid flood function.

11. The apparatus of claim 9, wherein the notifying instructions are to send a first notification message to all other backbone devices in the SPBM network, wherein the first notification message comprises IDs of backbone devices in the new selected group and indicates each of other backbone devices receiving the first notification message in the SPBM network to determine whether the first notification message contains the ID of the backbone device;

when determining that the first notification message does not contain the ID of the backbone device and the backbone device has enabled the rapid flood function, the backbone device receiving the first notification message disables the rapid flood function;

when determining that the first notification message contains the ID of the backbone device and the backbone device has not enabled the rapid flood function, the backbone device receiving the first notification message enables the rapid flood function.

12. The apparatus of claim 10, wherein the notifying instructions are to send a first notification message to all other backbone devices in the SPBM network, wherein the first notification message comprises IDs of backbone devices in the new selected group and indicates each of other backbone devices receiving the first notification message in the SPBM network to determine whether the first notification message contains the ID of the backbone device;

when determining that the first notification message does not contain the ID of the backbone device and the backbone device has enabled the rapid flood function, the backbone device receiving the first notification message disables the rapid flood function;

when determining that the first notification message contains the ID of the backbone device and the backbone device has not enabled the rapid flood function, the backbone device receiving the first notification message enables the rapid flood function.

13. The apparatus of claim 10, wherein the role determining instructions are to switch the device to a non-primary backbone device when determining over again that the ID of the device does not meet the predefined rule;

and

the notifying instructions are to send a second notification message to all other backbone devices in the SPBM network when the role determining instructions determine over again that the ID of the device does not meet the predefined rule, wherein the second notification message indicates each of other backbone devices in the SPBM network to reselect a new primary backbone device through the automatic vote method.

14. The apparatus of claim 10, wherein the notifying instructions are to send a second notification message to all other backbone devices in the SPBM network when the rapid flood function of the device is disabled manually, wherein the second notification message indicates each of other backbone devices in the SPBM network to reselect a new primary backbone device through the automatic vote method.

15. The apparatus of claim 10, further comprising determining instructions and processing instructions, wherein

when the device is not the primary backbone device and after the network topology changes and a new STP tree is calculated, the determining instructions are to determine whether LSP information corresponding to the primary backbone device in a local Link State Data Base (LSDB) is updated within a period of time X*T;

and

the processing instructions are to determine that the primary backbone device is abnormal when the determining instructions determine that the LSP information corresponding to the primary backbone device in the local LSDB is not updated within a period of time X*T, and reselect a new primary backbone device through the automatic vote method, X is a predefined natural number larger than 1, and T is an aging period of LSP information.