ROUTE CALCULATION METHOD AND MASTER NODE DEVICE IN VIRTUAL NETWORK ELEMENT

• US 20130286893A1
• Filed: 06/28/2013
• Published: 10/31/2013
• Est. Priority Date: 05/25/2011
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: LI, Yuhua, ZHU, Mingming
• Granted Patent: US 9,077,608 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

The present invention provides a route calculation method and a master node device in a virtual network element. The method includes: receiving and storing, by the master node, topology information; performing, according to a topology type of the VNE, topology verification for all topology information locally stored on the master node; and calculating, after the topology verification is passed, internal paths in the VNE and weights of the internal paths, generating and storing an internal routing entry, and sending the internal routing entry to nodes except the master node in the VNE. Therefore, in various topology structures, such as a dual-homing tree, a ring, and a half ring, calculation of the internal routes in the VNE and load balancing within the VNE can be implemented.

Claims

1. A route calculation method in a virtual network element, comprising:

receiving and storing, by a master node in the virtual network element, first topology information reported by nodes except the master node in the virtual network element;

performing, by the master node, according to a topology type of the virtual network element, topology verification for all topology information locally stored on the master node, wherein the locally stored topology information comprises second topology information about the master node and the first topology information;

calculating, by the master node, internal paths in the virtual network element and weights of the internal paths according to the topology type and the locally stored topology information after the topology verification is passed; and

generating and storing, by the master node, an internal routing entry according to the internal paths and the weights of the internal paths and sending the internal routing entry to the nodes except the master node in the virtual network element.

2. The method according to claim 1, before the receiving and storing, by the master node in the virtual network element, the first topology information reported by nodes except the master node in the virtual network element, further comprising:

sending, by the master node, topology collection request messages of the virtual network element in broadcast mode, wherein the topology collection request messages carry information about the master node and an identity, a name, and the topology type of the virtual network element, wherein

the receiving and storing, by the master node in the virtual network element, the first topology information reported by nodes except the master node in the virtual network element comprises;

receiving, by the master node, topology collection response messages sent by the nodes except the master node in the virtual network element, wherein the topology collection response messages carry the first topology information and the topology collection response messages are sent to the master node by the nodes except the master node in the virtual network element after the nodes receive the topology collection request messages and determine that the virtual network element corresponding to the virtual network element identity is a home virtual network element of the nodes; and

storing, by the master node, the first topology information and adding all nodes in the virtual network element to virtual network element cluster management.

3. The method according to claim 1, further comprising one of the following:

after the topology verification is passed, if a new node is added to the virtual network element, receiving and storing, by the master node, third topology information reported by the new node in the virtual network element and performing, according to the topology type, the topology verification again for all the topology information locally stored on the master node;

receiving and storing, by the master node, fourth topology information sent by a node connected to the new node in the virtual network element and performing, according to the topology type, the topology verification again for all the topology information locally stored on the master node, wherein the fourth topology information sent by the node connected to the new node in the virtual network element is sent to the master node by the node connected to the new node after the node receives a topology packet sent by the master node and determines that the fourth topology information of itself is different from fifth topology information carried in the topology packet;

receiving and storing, by the master node, the third topology information reported by the new node after the new node receives the topology packet sent by the master node and performing, according to the topology type, the topology verification again for all the topology information locally stored on the master node.

4. The method according to claim 1, further comprising:

after the topology verification is passed, if a node is removed from the virtual network element, receiving and storing, by the master node, changed topology information reported by a node directly connected to the removed node in the virtual network element and performing, according to the topology type, the topology verification again for all the topology information locally stored on the master node,

wherein the changed topology information is actively reported to the master node by the node directly connected to the removed node, or the changed topology information is sent to the master node by the node directly connected to the removed node after the node receives a topology packet sent by the master node and determines that the changed topology information about itself is different from topology information carried in the topology packet.

5. The method according to claim 1, further comprising:

after the topology verification is passed, when an internal link of the virtual network element is faulty, receiving and storing, by the master node, first changed topology information that is reported through a standby path by a first node on the faulty link and second changed topology information that is reported by a second node connected to the first node on the faulty link and performing, according to the topology type, the topology verification for all the topology information locally stored on the master node.

6. The method according to claims 1, wherein topology information comprises an identifier of a node in the virtual network element, basic information about a device where the node resides, first information about external interfaces, and second information about internal interfaces.

7. The method according to claim 6, wherein the performing, by the master node, according to the topology type of the virtual network element, the topology verification for all the topology information locally stored on the master node comprises:

when the topology type is a dual-homing tree topology, judging, by the master node, whether verification criteria of the dual-homing tree topology are met according to all the topology information locally stored on the master node, wherein;

the passing of the topology verification comprises;

the verification criteria of the dual-homing tree topology are met; and

the verification criteria of the dual-homing tree topology comprises;

each node within the virtual network element has at least two available internal interfaces;

the master node is directly connected to a standby master node through the internal interfaces and the internal interfaces and links between the master node and the standby master node are normal;

each slave node in the virtual network element only has two internal interfaces for connecting to the master node and the standby master node; and

a quantity of slave nodes that have reported topology information of the slave nodes in the virtual network element is the same as a quantity of slave nodes planned in advance.

8. The method according to claim 6, wherein the performing, by the master node, according to a topology type of the virtual network element, the topology verification for all the topology information locally stored on the master node comprises:

when the topology type is a ring topology, judging, by the master node, whether verification criteria of the ring topology are met according to all the topology information locally stored on the master node, wherein;

the passing of the topology verification comprises;

verification criteria of the ring topology are met; and

the verification criteria of the ring topology comprises;

each node in the virtual network element has two normal internal interfaces;

the master node is directly connected to a standby master node through the internal interfaces;

nodes in the virtual network element are mutually connected and one internal interface of the master node is reachable from another internal interface of the master node through any node except the master node in the virtual network element; and

sequences of nodes that two ring paths starting from two internal interfaces of the master node pass through are opposite.

9. The method according to claim 6, wherein the performing, by the master node, according to the topology type of the virtual network element, the topology verification for all the topology information locally stored on the master node comprises:

when the topology type is a half ring topology, judging, by the master node, whether verification criteria of the half ring topology are met according to all the topology information locally stored on the master node, wherein;

the passing of the topology verification comprises;

the verification criteria of the half ring topology are met; and

the verification criteria of the half ring topology comprises;

each node except the master node and a standby master node in the virtual network element has at least two normal internal interfaces;

both the master node and the standby master node have at least one internal interface and no internal link that directly connects the master node and the standby master node exists;

the nodes except the master node and the standby master node in the virtual network element are mutually connected and a normal internal interface of the standby master node is reachable from an internal interface of the master node through the nodes except the master node and the standby master node in the virtual network element; and

a half ring path starting from the internal interface of the master node passes through any node except the master node in the virtual network element and a last node of the half ring path is the standby master node.

10. The method according to claim 6, wherein the calculating, by the master node, the internal paths in the virtual network element and the weights of the internal paths according to the topology type and the locally stored topology information comprises:

when the topology type is a dual-homing tree topology, calculating, by the master node, two paths between every two slave nodes in the virtual network element and calculating, for each slave node in the virtual network element, paths from the slave node to the master node and from the slave node to a standby master node; and

determining, by the master node, that in the two paths, a weight of a path that passes through the master node is the sum of a weight of a path between a first slave node and the master node and a weight of a path between the master node and a second slave node;

determining that in the two paths, a weight of a path that passes through the standby master node is the sum of a weight of a path between the first slave node and the standby master node and a weight of a path between the standby master node and the second slave node; and

determining that in the two paths, the path with a lower weight is a primary path and the path with a higher weight is a secondary path, wherein;

the weight of the path between the master node and the first slave node or the weight of the path between the master node and the second slave node is preset, or is assigned by the master node according to a quantity of first slave nodes or second slave nodes; and

the weight of the path between the standby master node and the first slave node or the weight of the path between the standby master node and the second slave node is preset, or is assigned by the master node according to the quantity of the first slave nodes or the second slave nodes.

11. The method according to claim 10, further comprising:

when weights of the two paths are the same, comparing, by the master node, the weight of the path between the first slave node and the master node with the weight of the path between the first slave node and the standby master node;

when the weight of the path between the first slave node and the master node is lower, determining, by the master node, that the path that passes through the master node is the primary path and the path that passes through the standby master node is the secondary path; and

when the weight of the path between the first slave node and the standby master node is lower, determining, by the master node, that the path that passes through the standby master node is the primary path and the path that passes through the master node is the secondary path.

12. The method according to claim 6, wherein the calculating, by the master node, internal paths in the virtual network element and weights of the internal paths according to the topology type and the locally stored topology information comprises:

when the topology type is a ring topology, calculating, by the master node, for each node in the virtual network element, two paths from the node to any other node except the node in the virtual network element; and

one of the group consisting of (a) and (b);

(a) determining, by the master node, that in the two paths, a path that passes through less nodes is a primary path and a path that passes through more nodes is a secondary path and assigning a lower weight to the primary path and a higher weight to the secondary path; and

,

(b) determining, by the master node, that weights of the two paths are the sum of weights preset for paths between two adjoining nodes on the two paths and determining that the path with a lower weight is the primary path and the path with the higher weight is the secondary path; and

the generating and storing, by the master node, an internal routing entry according to the internal paths and the weights of the internal paths comprises;

generating and storing, by the master node, the internal routing entry according to the primary path, the weight of the primary path, the secondary path, and the weight of the secondary path.

13. The method according to claim 6, wherein the calculating, by the master node, the internal paths in the virtual network element and the weights of the internal paths according to the topology type and the topology information comprises:

when the topology type is a half ring topology, calculating, by the master node, for each slave node in the virtual network element, paths from the slave node to the master node and from the slave node to a standby master node;

one of the group consisting of (a) and (b);

(a) comparing, by the master node, a quantity of nodes through which the path from the slave node to the master node passes with a quantity of nodes through which the path from the slave node to the standby master node passes, and setting a higher weight for the path that passes through more nodes and a lower weight for the path that passes through less nodes; and

,

(b) determining, by the master node, that a weight of the path from the slave node to the master node is the sum of weights preset for paths between two adjoining nodes on the path from the slave node to the master node and determining that a weight of the path from the slave node to the standby master node is the sum of weights preset for paths between two adjoining nodes on the path from the slave node to the standby master node; and

determining, by the master node, that the path with the lower weight is a primary path and the path with the higher weight is a secondary path; and

the generating and storing, by the master node, the internal routing entry according to the internal paths and the weights of the internal paths comprises;

generating and storing, by the master node, the internal routing entry according to the primary path, the weight of the primary path, the secondary path, and the weight of the secondary path.

14. A master node device in a virtual network element, comprising:

a receiving module, configured to receive first topology information reported by node devices except the master node device in the virtual network element;

a storing module, configured to store the first topology information received by the receiving module;

a verification module, configured to perform, according to a topology type of the virtual network element, topology verification for all topology information stored by the storing module, wherein all the topology information stored by the storing module comprises second topology information about the master node device and the first topology information received by the receiving module;

a calculating module, configured to calculate internal paths in the virtual network element and weights of the internal paths according to the topology type and the topology information stored by the storing module after the topology verification is passed;

a generating module, configured to generate and store an internal routing entry according to the internal paths and the weights of the internal paths that are calculated by the calculating module; and

a sending module, configured to send the internal routing entry generated by the generating module to the node devices except the master node device in the virtual network element.

15. The device according to claim 14, wherein:

the sending module is further configured to send topology collection request messages of the virtual network element in broadcast mode, wherein the topology collection request messages carry information about the master node device and an identity, a name, and the topology type of the virtual network element;

the receiving module is specifically configured to receive topology collection response messages sent by the node devices except the master node device in the virtual network element, wherein the topology collection response messages carry the first topology information and the topology collection response messages are sent to the master node device by the node devices except the master node device in the virtual network element after the node devices receive the topology collection request messages and determine that the virtual network element corresponding to the virtual network element identity is a home virtual network element of the node devices; and

the storing module is specifically configured to store the first topology information and add all node devices in the virtual network element to virtual network element cluster management.

16. The device according to claim 14, wherein the calculating module comprises:

a first calculating sub-module, configured to;

when the topology type is a dual-homing tree topology, calculate two paths between every two slave node devices in the virtual network element and calculate, for each slave node device in the virtual network element, paths from the slave node device to the master node device and from the slave node device to a standby master node device; and

a first determining sub-module, configured to determine that in the two paths, a weight of a path that passes through the master node device is the sum of a weight of a path between a first slave node device and the master node device and a weight of a path between the master node device and a second slave node device;

determine that in the two paths, a weight of a path that passes through the standby master node device is the sum of a weight of a path between the first slave node device and the standby master node device and a weight of a path between the standby master node device and the second slave node device; and

determine that in the two paths, the path with a lower weight is a primary path and the path with a higher weight is a secondary path, wherein;

the weight of the path between the master node device and the first slave node device or the second slave node device is preset, or is assigned by the master node device according to a number of the first slave node device or the second slave node device; and

the weight of the path between the standby master node device and the first slave node device or the second slave node device is preset, or is assigned by the master node device according to the number of the first slave node device or the second slave node device.

17. The device according to claim 16, wherein:

the first determining sub-module is further configured to;

when weights of the two paths are the same, compare a weight of the path between the first slave node device and the master node device with a weight of the path between the first slave node device and the standby master node device;

when the weight of the path between the first slave node device and the master node device is lower, determine that the path that passes through the master node device is the primary path and the path that passes through the standby master node device is the secondary path; and

when the weight of the path between the first slave node device and the standby master node device is lower, determine that the path that passes through the standby master node device is the primary path and the path that passes through the master node device is the secondary path.

18. The device according to claim 14, wherein the calculating module comprises:

a second calculating sub-module, configured to;

when the topology type is a ring topology, calculate for each node device in the virtual network element, two paths from the node device to any other node device except the node device in the virtual network element; and

a second determining sub-module, configured to determine that in the two paths, a path that passes through less node devices is a primary path and a path that passes through more node devices is a secondary path and assign a lower weight to the primary path and a higher weight to the secondary path;

or, determine that weights of the two paths are the sum of weights preset for paths between two adjoining node devices on the two paths, and determine that the path with a lower weight is the primary path and the path with a higher weight is the secondary path; and

the generating module is specifically configured to generate the internal routing entry according to the primary path, the weight of the primary path, the secondary path, and the weight of the secondary path.

19. The device according to claim 14, wherein the calculating module comprises:

a third calculating sub-module, configured to;

when the topology type is a half ring topology, calculate for each slave node device in the virtual network element, paths from the slave node device to the master node device and from the slave node device to a standby master node device; and

a third determining sub-module, configured to compare the number of node devices through which the path from the slave node device to the master node device passes with the number of node devices through which the path from the slave node device to the standby master node device passes, and set a higher weight for the path that passes through more node devices and a lower weight for the path that passes through less node devices;

or, a third determining sub-module, configured to determine that a weight of the path from the slave node device to the master node device is the sum of weights preset for paths between two adjoining node devices on the path from the slave node device to the master node device and determine that a weight of the path from the slave node device to the standby master node device is the sum of weights preset for paths between two adjoining node devices on the path from the slave node device to the standby master node device, wherein;

the third determining sub-module is further configured to determine that the path with a lower weight is a primary path and the path with a higher weight is a secondary path; and

the generating module is specifically configured to generate the internal routing entry according to the primary path, the weight of the primary path, the secondary path, and the weight of the secondary path.