CN106302158B - Method and device for selecting transmission path in network topology - Google Patents

Abstract

A method and device for selecting a transmission path in a network topology provided by an embodiment of the present invention can automatically filter out a transmission path from the source node to the sink node that does not pass through a specific node, which helps to improve the efficiency of path selection . In this method, the control device obtains the information of the first ring according to the first network topology, the information of the first layer and the source node of the path. The control device obtains the information of the second ring according to the first network topology, the sink node, and the information of the first layer. The control device obtains a preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring, and the preferred path is the slave that satisfies the routing condition. The path from the source node to the sink node.

Description

Method and device for selecting transmission path in network topology

technical field

The invention relates to the field of communication technology, in particular to a method and device for selecting a transmission path in a network topology.

Background technique

When an operator opens a new service or optimizes an already opened service, it needs to select a transmission path from the source node to the sink node in the network topology, and use the selected transmission path to transmit the service. At present, a Path Compute Element (PCE) is mainly used to select an end-to-end transmission path from a network topology.

When using PCE to select a transmission path of a network topology, the topology structure of the network topology is input into the PCE, the topology structure includes the connection relationship between all nodes of the network topology, and the PCE output a transmission path from the source node to the sink node according to the preselected source node and sink node.

The PCE is used to calculate the transmission path from the source node to the sink node, and the PCE selects the transmission path with the shortest delay or the shortest path according to the connection relationship between each node in the network topology. If it is necessary to select a transmission path from the source node to the sink node that does not pass through a specific node, and any one of the multiple transmission paths is the transmission path from the source node to the sink node, it is necessary to manually analyze the multiple transmission paths obtained by PCE calculation. The path is screened to obtain a transmission path from the source node to the sink node that does not pass through a specific node.

Contents of the invention

The embodiment of the present invention is to provide a method and device for selecting a transmission path in a network topology, which can automatically filter out a transmission path from the source node to the sink node that does not pass through a specific node, which helps to improve the efficiency of path selection .

For this reason, the technical scheme that the present invention solves technical problem is:

In the first aspect, a method for selecting a transmission path in a network topology is provided, including:

The control device obtains the information of the first ring according to the first network topology, the information of the first level, and the source node of the path, where the first network topology includes the source node, the sink node of the path, and the first level Included nodes and connection relationships between adjacent nodes, the first level is the highest level in the first network topology, and the information of the first level includes connection relationships between nodes included in the first level , the information of the first ring includes the layer to which the first ring belongs and the nodes included in the first ring, and the first ring includes the source node in the layer to which the first ring belongs and includes The ring with the least number of nodes;

The control device obtains the information of the second ring according to the first network topology, the sink node, and the information of the first layer, and the information of the second ring includes the layer to which the second ring belongs and the nodes included in the second ring, where the second ring is a ring that includes the sink node and includes the least number of nodes in the hierarchy to which the second ring belongs;

The control device obtains a preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring, and the preferred path is the slave that satisfies the routing condition. The path from the source node to the sink node, the path selection condition is: do not pass through the nodes included in the third ring and/or the nodes included in the fourth ring, the third ring includes the nodes that belong to the first ring rings of the same level and/or a level lower than the level to which the first ring belongs, and the fourth ring includes rings of the same level as the second ring and/or a level lower than the second ring The ring of the hierarchy it belongs to.

In a first possible implementation manner of the first aspect, the obtaining, by the control device, the information of the first ring according to the first network topology, the information of the first layer, and the source node of the path includes:

The control device obtains a first node according to the first network topology and the information of the first level, the first node is a node with child nodes in the first level, and the child nodes of the first node The node is the source node, a node directly connected to the source node, or a node indirectly connected to the source node;

The control device obtains information of a fifth ring according to the first network topology and the first node, and the fifth ring includes the first node in the second level and includes a smaller number of nodes than the first A set of rings with preset values, the information of the fifth ring includes the second level and the nodes included in the fifth ring, and the level of the second level is lower than the level of the first level;

The control device judges whether the information of the fifth ring includes the source node;

If the information of the fifth ring includes the source node, the control device obtains the information of the sixth ring from the information of the fifth ring, and uses the information of the sixth ring as the information of the first ring , the sixth ring is a ring that includes the source node and includes the least number of nodes in the fifth ring.

In combination with the first possible implementation manner of the first aspect above, a second possible implementation manner of the first aspect is also provided, wherein the control device, according to the first network topology, the first-level information, and the source node of the path, Access to information on the first ring also includes:

If the information of the fifth ring does not include the source node, the control device obtains a second node according to the first network topology and the information of the fifth ring, and the second node is the first node. A node having a child node in the second level, where the child node of the second node is the source node, a node directly connected to the source node, or a node indirectly connected to the source node;

The control device obtains the information of the first ring according to the first network topology and the second node, the layer to which the first ring belongs is a third layer, and the level of the third layer is lower than the Describe the level of the second level.

In combination with the above first aspect, the first possible implementation manner of the first aspect, or the second possible implementation manner of the first aspect, a third possible implementation manner of the first aspect is also provided, the control device according to The information about the first network topology, the sink node, and the first layer, and obtaining the information about the second ring include:

The control device obtains a third node according to the first network topology and information of the first level, the third node is a node with child nodes in the first level, and the child nodes of the third node The node is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node;

The control device obtains information of a seventh ring according to the first network topology and the third node, and the seventh ring includes the third node in the second level and includes a smaller number of nodes than the second A set of rings with preset values, the information of the seventh ring includes the second level and the nodes included in the seventh ring, and the level of the second level is lower than the level of the first level;

The control device judges whether the information of the seventh ring includes the sink node;

If the information of the third ring includes the sink node, the control device obtains the information of the eighth ring from the information of the seventh ring, and uses the information of the eighth ring as the information of the second ring , the eighth ring is the ring that includes the source node and includes the least number of nodes in the seventh ring.

In combination with the third possible implementation manner of the first aspect above, a fourth possible implementation manner of the first aspect is also provided, where the control device, according to the first network topology, the sink node, and the first Hierarchical information, the second ring information also includes:

If the information of the seventh ring does not include the source node, the control device obtains a fourth node according to the first network topology and the information of the seventh ring, and the fourth node is the first A node with child nodes in the second level, where the child node of the fourth node is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node;

The control device obtains the information of the second ring according to the first network topology and the fourth node, the layer to which the second ring belongs is a third layer, and the level of the third layer is lower than the Describe the level of the second level.

In combination with the above first aspect, the first possible implementation of the first aspect, the second possible implementation of the first aspect, the third possible implementation of the first aspect or the fourth possible implementation of the first aspect, A fifth possible implementation manner of the first aspect is also provided, the control device obtains the preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring include:

The control device obtains a second network topology based on the routing condition and the first network topology, and the second network topology is to filter out rings that do not meet the routing condition based on the first network topology. and/or the network topology obtained after links that do not meet the routing conditions;

The control device obtains the first subnet topology, the second subnet topology, and the second subnet topology according to the second network topology, the first layer information, the first ring information, and the second ring information. Three subnet topology, the first subnet topology includes only nodes included in the first level, the second subnet topology includes nodes included in the first ring, and the third subnet topology includes the the nodes included in the second ring;

The control device obtains a first path according to information about the second subnet topology and the first ring, and the first path is from the source node to the first ring in the second subnet topology. the subnet topology includes a path of a fifth node connecting one or more nodes in the second subnet topology;

The control device obtains a second path according to the information of the third subnet topology and the second ring, and the second path is from the sink node to the first link in the third subnet topology. a path of a sixth node included in the subnet topology, the sixth node connecting one or more nodes in the third subnet topology;

The control device obtains a third path according to the first subnet topology, the fifth node, and the sixth node, and the third path is the fifth node in the first subnet topology a path to the sixth node;

The control device obtains the preferred route according to the first route, the second route and the third route, and the preferred route is the first route, the second route and the third route The path obtained after path splicing.

In combination with the above first aspect, the first possible implementation of the first aspect, the second possible implementation of the first aspect, the third possible implementation of the first aspect or the fourth possible implementation of the first aspect, A sixth possible implementation manner of the first aspect is also provided, wherein the control device obtains a preferred path according to routing conditions, the first network topology, information about the first ring, and information about the second ring include:

The control device obtains a third network topology based on the routing condition and the first network topology, and the third network topology is to filter out rings that do not meet the routing condition based on the first network topology. and/or the network topology obtained after links that do not meet the routing conditions;

The control device obtains a fourth subnetwork topology according to the third network topology, the information of the first layer, the information of the first ring, and the information of the second ring, and the fourth subnetwork topology including nodes included in the first ring and nodes included in the second ring;

The control device obtains a preferred path according to the fourth sub-network topology, the information of the first layer, the information of the first ring, and the information of the second ring, where the fourth sub-network topology includes the The nodes included in the first ring include the nodes included in the second ring, and the preferred path is a path from the source node to the sink node.

In combination with the above first aspect, the first possible implementation of the first aspect, the second possible implementation of the first aspect, the third possible implementation of the first aspect or the fourth possible implementation of the first aspect, A seventh possible implementation manner of the first aspect is also provided, the route selection condition further includes that the number of horizontal links contained in the preferred path is less than a third preset value, and the control device according to the route selection condition, the The first network topology, the information of the first ring and the information of the second ring, obtaining the preferred path includes:

The control device obtains a fourth network topology according to the routing condition and the first network topology, and the fourth network topology is obtained after identifying one or more horizontal links on the basis of the first network topology network topology;

The control device obtains the fifth subnet topology, the sixth subnet topology, and the sixth subnet topology according to the fourth network topology, the information of the first layer, the information of the first ring, and the information of the second ring. Seven subnet topology, the fifth subnet topology only includes nodes included in the first level, the sixth subnet topology includes nodes included in the first ring, and the seventh subnet topology includes the the nodes included in the second ring;

The control device obtains a fourth path according to the information of the sixth subnet topology and the first ring, and the fourth path is from the source node to the fourth path in the sixth subnet topology. the subnet topology includes a path of a seventh node connecting one or more nodes in the fifth subnet topology;

The control device obtains a fifth path according to the information of the seventh subnet topology and the second ring, and the fifth path is from the destination node to the fourth ring in the seventh subnet topology. The subnetwork topology includes the eighth node path, the eighth node connects one or more nodes in the sixth subnetwork topology, the fifth path and the number of horizontal links contained in the fourth path less than the third preset value;

The control device obtains a sixth path according to the fifth subnet topology, the seventh node, and the eighth node, and the sixth path is the seventh node in the fifth subnet topology a path to the eighth node;

The control device obtains the preferred route according to the fourth route, the fifth route and the sixth route, and the preferred route is the fourth route, the fifth route and the sixth route The path obtained after path splicing.

In a second aspect, a device for selecting a transmission path in a network topology is provided, including:

The first ring information obtaining unit is configured to obtain the information of the first ring according to the first network topology, the information of the first level and the source node of the path, and the first network topology includes the source node and the sink of the path Nodes, nodes included in the first level, and connection relationships between adjacent nodes, the first level is the highest level in the first network topology, and the information of the first level includes the first level The connection relationship between the included nodes, the information of the first ring includes the layer to which the first ring belongs and the nodes included in the first ring, and the first ring is in the layer to which the first ring belongs a ring including the source node and including the least number of nodes;

The second ring information obtaining unit is configured to obtain information of a second ring according to the first network topology, the sink node, and the information of the first layer, and the information of the second ring includes the second ring The level to which it belongs and the nodes included in the second ring, where the second ring is a ring that includes the sink node and includes the least number of nodes in the level to which the second ring belongs;

a path obtaining unit, configured to obtain a preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring, and the preferred path is a route that satisfies the routing condition For the path from the source node to the sink node, the route selection condition is: not passing through the nodes included in the third ring and/or the nodes included in the fourth ring, the third ring includes the nodes included in the first ring rings belonging to the same level and/or lower than the level of the first ring, and the fourth ring includes rings of the same level as the second ring and/or lower than the first ring The ring of the hierarchy to which the second ring belongs.

In a first possible implementation manner of the second aspect, the first ring information acquiring unit is specifically configured to:

According to the information of the first network topology and the first level, a first node is obtained, the first node is a node with child nodes in the first level, and the child nodes of the first node are the a source node, a node directly connected to said source node, or a node indirectly connected to said source node;

Obtain information about a fifth ring according to the first network topology and the first node, the fifth ring includes the first node in the second level and the number of nodes included is less than a first preset value a set of rings, the information of the fifth ring includes the second level and the nodes included in the fifth ring, and the level of the second level is lower than that of the first level;

judging whether the information of the fifth ring includes the source node;

If the information of the fifth ring includes the source node, obtain the information of the sixth ring from the information of the fifth ring, use the information of the sixth ring as the information of the first ring, and the information of the sixth ring The sixth ring is the ring that includes the source node and includes the least number of nodes in the fifth ring.

In combination with the first possible implementation of the second aspect above, a second possible implementation of the second aspect is also provided, and the first ring information acquisition unit is further specifically configured to:

If the information of the fifth ring does not include the source node, according to the first network topology and the information of the fifth ring, obtain a second node, and the second node is a child node in the second layer A node of a node, the child node of the second node is the source node, a node directly connected to the source node, or a node indirectly connected to the source node;

According to the first network topology and the second node, obtain the information of the first ring, the level to which the first ring belongs is a third level, and the level of the third level is lower than the second level level.

In combination with the second aspect above, the first possible implementation of the second aspect or the second possible implementation of the second aspect, a third possible implementation of the second aspect is also provided, the second ring information acquisition unit Specifically for:

According to the information of the first network topology and the first level, a third node is obtained, the third node is a node with child nodes in the first level, and the child nodes of the third node are the a sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node;

Obtain information about a seventh ring according to the first network topology and the third node, the seventh ring includes the third node in the second level and the number of nodes included is less than a second preset value a set of rings, the information of the seventh ring includes the second level and the nodes included in the seventh ring, and the level of the second level is lower than the level of the first level;

judging whether the information of the seventh ring includes the sink node;

If the information of the third ring includes the sink node, obtain the information of the eighth ring from the information of the seventh ring, use the information of the eighth ring as the information of the second ring, and the information of the second ring The eighth ring is the ring that includes the source node and includes the least number of nodes in the seventh ring.

In combination with the above-mentioned third possible implementation of the second aspect, a fourth possible implementation of the second aspect is also provided, and the second ring information acquisition unit is further specifically configured to:

If the information of the seventh ring does not include the source node, according to the first network topology and the information of the seventh ring, a fourth node is obtained, and the fourth node is a child node in the second layer A node of a node, where the child node of the fourth node is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node;

According to the first network topology and the fourth node, obtain the information of the second ring, the level to which the second ring belongs is a third level, and the level of the third level is lower than the second level level.

In combination with the second aspect above, the first possible implementation of the second aspect, the second possible implementation of the second aspect, the third possible implementation of the second aspect or the fourth possible implementation of the second aspect, A fifth possible implementation manner of the second aspect is also provided, and the path obtaining unit is specifically used for:

According to the routing conditions and the first network topology, a second network topology is obtained, and the second network topology is to filter out rings that do not meet the routing conditions and/or rings that do not meet the routing conditions based on the first network topology. The network topology obtained after the link meeting the routing condition;

Obtain a first subnet topology, a second subnet topology, and a third subnet topology according to the second network topology, the information of the first layer, the information of the first ring, and the information of the second ring , the first subnet topology includes only nodes included in the first level, the second subnet topology includes nodes included in the first ring, and the third subnet topology includes nodes included in the second ring the node;

Obtaining a first path according to the information about the second subnet topology and the first ring, where the first path is from the source node in the second subnet topology to the first subnet topology includes a path of a fifth node, the fifth node connecting one or more nodes in the second subnet topology;

Obtaining a second path according to information about the third subnet topology and the second ring, where the second path is from the destination node in the third subnet topology to the first subnet topology includes The path of the sixth node of the sixth node, the sixth node is connected to one or more nodes in the third subnet topology;

According to the first subnet topology, the fifth node, and the sixth node, a third path is obtained, and the third path is from the fifth node to the sixth node in the first subnet topology. A six-node path;

Obtain the preferred route according to the first route, the second route and the third route, where the preferred route is obtained by splicing the first route, the second route and the third route path of.

In combination with the second aspect above, the first possible implementation of the second aspect, the second possible implementation of the second aspect, the third possible implementation of the second aspect or the fourth possible implementation of the second aspect, A sixth possible implementation manner of the second aspect is also provided, and the path obtaining unit is specifically configured to:

According to the routing conditions and the first network topology, a third network topology is obtained, and the third network topology is to filter out rings that do not meet the routing conditions and/or rings that do not meet the routing conditions based on the first network topology. The network topology obtained after the link meeting the routing condition;

According to the third network topology, the information of the first layer, the information of the first ring, and the information of the second ring, obtain a fourth subnetwork topology, where the fourth subnetwork topology includes the first the nodes included in the first ring and the nodes included in the second ring;

A preferred path is obtained according to the fourth sub-network topology, the information of the first level, the information of the first ring, and the information of the second ring, the fourth sub-network topology includes the first ring including and nodes included in the second ring, and the preferred path is a path from the source node to the sink node.

In combination with the second aspect above, the first possible implementation of the second aspect, the second possible implementation of the second aspect, the third possible implementation of the second aspect or the fourth possible implementation of the second aspect, A sixth possible implementation manner of the second aspect is also provided, the route selection condition further includes that the number of horizontal links included in the preferred route is less than a third preset value, and the route obtaining unit is specifically configured to:

Obtaining a fourth network topology according to the routing condition and the first network topology, where the fourth network topology is a network topology obtained after identifying one or more horizontal links on the basis of the first network topology;

Obtain a fifth subnet topology, a sixth subnet topology, and a seventh subnet topology according to the fourth network topology, the information of the first layer, the information of the first ring, and the information of the second ring , the fifth subnet topology includes only nodes included in the first level, the sixth subnet topology includes nodes included in the first ring, and the seventh subnet topology includes nodes included in the second ring the node;

Obtaining a fourth path according to the information about the sixth subnet topology and the first ring, where the fourth path is from the source node in the sixth subnet topology to the fourth subnet topology includes A path of a seventh node of the fifth subnetwork topology, the seventh node connecting one or more nodes in the fifth subnet topology;

Obtaining a fifth path according to the seventh subnet topology and the information of the second ring, where the fifth path is from the sink node to the fourth subnet topology in the seventh subnet topology includes The path of the eighth node, the eighth node is connected to one or more nodes in the sixth subnetwork topology, the number of horizontal links contained in the fifth path and the fourth path is smaller than that of the first Three preset values;

According to the fifth subnet topology, the seventh node, and the eighth node, a sixth path is obtained, and the sixth path is from the seventh node to the fifth subnet topology in the fifth subnet topology. eight-node path;

Obtain the optimal path according to the fourth path, the fifth path, and the sixth path, where the optimal path is obtained by splicing the fourth path, the fifth path, and the sixth path path of.

In the method and device for selecting a transmission path in a network topology provided by an embodiment of the present invention, a control device obtains information of a first ring according to a first network topology, information of a first layer, and a source node of a path. The control device obtains the information of the second ring according to the first network topology, the sink node, and the information of the first layer. The control device obtains a preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring, and the preferred path is the slave that satisfies the routing condition. The path from the source node to the sink node. The control device uses the route selection condition to select a preferred path from the source node to the sink node, and the preferred route may not pass through a specific node, which helps to improve the efficiency of route selection.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only These are some embodiments of the present invention. Those skilled in the art can also obtain other drawings based on these drawings without creative work.

FIG. 1 is a flowchart of a method for selecting a transmission path in a network topology provided by an embodiment of the present invention;

FIG. 2 is a schematic diagram of the source node and the parent node of the sink node being different nodes in the first level according to an embodiment of the present invention;

FIG. 3 is a schematic diagram of a parent node of the source node and the sink node being the same node in the first level provided by an embodiment of the present invention;

FIG. 4 is a schematic diagram of a network topology structure provided by an embodiment of the present invention;

5 is a schematic structural diagram of a first network topology in which the parent nodes of the source node and the sink node are different nodes in the first layer according to an embodiment of the present invention;

FIG. 6 is a schematic diagram of a second network topology structure obtained by removing rings at levels lower than the first ring and the second ring provided by an embodiment of the present invention;

FIG. 7 is a schematic diagram of a second network topology obtained by removing rings at the same level as the first ring and the second ring provided by an embodiment of the present invention;

FIG. 8 is a schematic diagram of a second network topology structure obtained by removing rings with levels lower than and equal to the first ring and the second ring provided by an embodiment of the present invention;

FIG. 9 is a schematic diagram of the second network topology divided into three sub-network topologies according to an embodiment of the present invention;

FIG. 10 is a schematic diagram of a preferred path in the first network topology shown in FIG. 5 provided by an embodiment of the present invention;

FIG. 11 is a schematic diagram of a first network topology in which the parent nodes of the source node and the sink node are the same node in the first level provided by an embodiment of the present invention;

FIG. 12 is a schematic diagram of a preferred path in the first network topology shown in FIG. 11 provided by an embodiment of the present invention;

FIG. 13 is a schematic diagram of a horizontal link provided by an embodiment of the present invention;

FIG. 14 is a schematic structural diagram of a device for selecting a transmission path in a network topology provided by an embodiment of the present invention;

FIG. 15 is a schematic structural diagram of a path acquisition unit provided by an embodiment of the present invention;

FIG. 16 is a schematic structural diagram of an apparatus for selecting a transmission path in a network topology according to an embodiment of the present invention.

Detailed ways

Embodiments of the present invention provide a method and device for selecting a transmission path in a network topology. In order to make the purpose, technical solutions, and advantages of the embodiments of the present invention clearer, the following will implement the present invention in conjunction with the accompanying drawings in the embodiments of the present invention. The technical solution in the example is clearly described.

According to the nodes included in the network topology and the connection relationship between adjacent nodes, the transmission path from the source node to the sink node selected in a network topology may have reverse and/or detour. If the parent node of the source node and the parent node of the sink node belong to the highest level in the network topology, the retrograde existence of the transmission path means that the transmission path passes through a level lower than the level to which the source node belongs or through a ring lower than the level to which the sink node belongs. The transmission path including the retrograde path will occupy the transmission bandwidth of the low-level service data and affect the transmission rate of the low-level service data. The detour of the transmission path means that the transmission path passes through at least two rings on the level to which the source node belongs or passes through at least two rings on the level to which the sink node belongs. At least two rings on the level to which the source node belongs include a first ring, and the first ring is a ring that includes the source node and includes the least number of nodes in the level to which the first ring belongs. At least two rings on the level to which the sink node belongs include a second ring, and the second ring is a ring that includes the sink node and includes the least number of nodes in the level to which the second ring belongs. The transmission path including the detour path will occupy the transmission bandwidth of service data on the same layer and affect the transmission rate of other service data on the same layer. The routing conditions provided by the embodiments of the present invention require that the transmission path does not have a reverse path and/or a detour path.

An embodiment of the present invention provides a method for selecting a transmission path in a network topology. The method includes: the control device obtains information about the first ring according to the first network topology, information at the first level, and the source node of the path. The first network topology includes the source node, the sink node of the path, the nodes included in the first level, and the connection relationship between adjacent nodes, and the first level is the highest level in the first network topology. level, the information of the first level includes the connection relationship between the nodes included in the first level, the information of the first ring includes the level to which the first ring belongs and the nodes included in the first ring, the The first ring is a ring that includes the source node and includes the least number of nodes in the hierarchy to which the first ring belongs; the control device according to the first network topology, the sink node, and the first ring Hierarchy information, obtain the information of the second ring, the information of the second ring includes the level to which the second ring belongs and the nodes included in the second ring, the second ring is the The ring that includes the sink node and includes the least number of nodes in the hierarchical level; the control device obtains the A preferred path, where the preferred path is a path from the source node to the sink node that satisfies the routing condition, and the routing condition is: no nodes included in the third ring and/or nodes included in the fourth ring nodes, the third ring includes rings at the same level as the first ring and/or rings at a lower level than the first ring, and the fourth ring includes rings at the same level as the second ring rings belonging to the same level and/or rings whose level is lower than the level to which the second ring belongs.

FIG. 1 is a flowchart of a method for selecting a transmission path in a network topology provided by an embodiment of the present invention. The method provided by the embodiment of the present invention will be described in detail below with reference to FIG. 1 .

101: The control device obtains the information of the first ring according to the first network topology, the first-level information, and the source node of the path, where the first network topology includes the source node, the sink node of the path, and the second The nodes included in one level and the connection relationship between adjacent nodes, the first level is the highest level in the first network topology, the information of the first level includes the connection between the nodes included in the first level connection relationship, the information of the first ring includes the layer to which the first ring belongs and the nodes included in the first ring, and the first ring includes the source node in the layer to which the first ring belongs and contains the least number of nodes.

For example, the first network topology includes multiple nodes and connection relationships between adjacent nodes, and the multiple nodes include the source node, the sink node, and nodes included in the first level. The connection relationship between nodes included in the first level includes the connection relationship between two adjacent nodes included in the first level. The connection relationship between the adjacent nodes may be represented by an identifier of a link (link) and identifiers of nodes at both ends of the link.

For example, the parent node of the source node is a node of the first level, and the parent node of the sink node is a node of the first level. The parent node of the source node may be the same as the parent node of the sink node, or may be different from the parent node of the sink node. In the first network topology as shown in Figure 2, the parent nodes of the source node and the sink node are different nodes in the first level, and the parent node of the source node is a node of the first level M, the parent node of the sink node is the node N of the first level. In the first network topology shown in FIG. 3 , the parent nodes of the source node and the sink node are the same nodes in the first level, and the parent nodes of the source node and the sink node are both the Node N of the first level. The parent node of the source node mentioned in the embodiment of the present invention may be a node directly connected to the source node and located at the upper level of the level to which the source node belongs, and the parent node of the source node is also It may be a node indirectly connected to the source node and located above the level to which the source node belongs, as shown in FIG. 2 and FIG. 3 . The parent node of the sink node mentioned in the embodiment of the present invention may be a node directly connected to the sink node and located at a level above the level to which the sink node belongs, and the parent node of the sink node is also It may be a node indirectly connected to the sink node and located above the level to which the sink node belongs, as shown in FIG. 2 and FIG. 3 .

For example, the obtaining the information of the first ring by the control device according to the first network topology, the information of the first level and the source node of the path includes: the control device according to the first network topology and the information of the first level Information to obtain a first node, the first node is a node with child nodes in the first level, and the child nodes of the first node are the source node, a node directly connected to the source node, or an indirect connection A node of the source node; the control device obtains information of a fifth ring according to the first network topology and the first node, where the fifth ring includes the first node in the second level and A set of rings whose number of nodes is less than a first preset value, the information of the fifth ring includes the nodes included in the second level and the fifth ring, and the level of the second level is lower than that of the fifth ring One-level level; the control device judges whether the information of the fifth ring includes the source node; if the information of the fifth ring includes the source node, obtain the sixth ring information, the sixth ring is the ring that includes the source node and includes the least number of nodes in the fifth ring, then the control device uses the information of the sixth ring as the first ring Information.

In the network topology shown in Figure 4, a ring containing node A1 can pass through node A1, node B1, node B3, node B4, node B5 and node B2 in turn, in other words, a ring containing node A1 includes node A1 Node B1, Node B3, Node B4, Node B5 and Node B2. A ring including node B4 may be a ring including node A1, and a ring including node B4 may also be a ring passing through node B4, node C1, node C2, node C3, node C4 and node B5 in sequence, in other words, A ring including node B4 may also be a ring including node B4, node C1, node C2, node C3, node C4 and node B5.

In the network topology shown in Figure 4, node C2 is the source node, and the level to which node A1, node A2, and node A3 belong is the first level. Nodes in a hierarchy. According to the network topology shown in FIG. 4 , the control device finds out that the node A1 , the node A2 and the node A3 are nodes with child nodes in the first layer. According to the network topology shown in FIG. 4 , the control device finds out that the child node B1 of node A1 is a node indirectly connected to the source node (node C2 ), then the control device takes node A1 as the first node. If the node B9 is the source node, the control device will use the node A2 or the node A3 as the first node. The child node B8 of the node A2 is a node directly connected to the source node (node B9). If node B1 is the source node, the child node of node A1 is the source node (node B1), and the control device selects node A1 as the first node. .

For example, the control device finds, according to the connection relationship between adjacent nodes in the first network topology, a set of rings that include the first node and whose number of nodes is less than a first preset value. The first preset value can be specifically set according to actual needs, and generally, the first preset threshold value does not exceed 11. In the network topology shown in FIG. 4 , if the first node is node A1, the fifth ring found by the control device includes ring Bh1 and ring Bh2. Either of the ring Bh1 and the ring Bh2 includes the node A1 and the number of nodes included is less than a first preset value. Ring Bh1 includes node A1, node B1, node B3, node B4, node B5 and node B2. Ring Bh2 includes node A1, node B1, node B6, node B7, node B3, node B4, node B5 and node B2. Here, it is described as an example that the control device finds two rings that include the first node and the number of nodes included is less than a first preset value. The control device may also find more than two rings including the first node and the number of nodes included is less than a first preset value, which will not be repeated here.

As shown in the network topology of FIG. 4 , if the source node is node B1, both ring Bh1 and ring Bh2 include the first node and the source node. The number of nodes included in the ring Bh1 is smaller than the number of nodes included in the ring Bh2, that is, the ring Bh1 is the ring with the smallest number of nodes included in the fifth ring. The control device obtains the information of the ring Bh1 from the information of the fifth ring, and the information of the ring Bh1 is the information of the sixth ring, that is, the information of the ring Bh1 is the information of the first ring.

Optionally, the obtaining the information of the first ring by the control device according to the first network topology, the information of the first level, and the source node of the path further includes: if the information of the fifth ring does not include the source node, then The control device obtains a second node according to the information of the first network topology and the fifth ring, the second node is a node with child nodes in the second level, and the child nodes of the second node The node is the source node, a node directly connected to the source node, or a node indirectly connected to the source node; the control device obtains the information of the first ring according to the first network topology and the second node Information, the level to which the first ring belongs is the third level, and the level of the third level is lower than the level of the second level.

As shown in the network topology of FIG. 4 , if the source node is node C2, neither ring Bh1 nor ring Bh2 includes the source node, that is, the information of the fifth ring does not include the source node. The control device takes the level where the ring Bh1 and the ring Bh2 are located as the second level, that is, the second level includes the ring Bh1 and the ring Bh2. The control device obtains node B4 and node B10 having child nodes in the second layer according to the connection relationship between adjacent nodes in the first network topology and the information of the fifth ring. Node B4 is a node indirectly connected to node C2, and the control device uses node B4 as the second node. Node B10 is not directly connected to node C2 or indirectly connected to node C2, so node B10 is not the second node.

As shown in the network topology in FIG. 4 , the control device obtains a ring Ch1 and a ring Ch2 according to the connection relationship between adjacent nodes in the first network topology. Both the ring Ch1 and the ring Ch2 include the node B4 as the second node and the node C2 as the source node. Ring Ch1 contains node B4, node C1, node C2, node C3 and node C4. Ring Ch2 includes node B4, node C1, node C10, node C11, node C2, node C3 and node C4. The number of nodes included in the ring Ch1 is smaller than the number of nodes included in the ring Ch2. The control device uses the ring Ch1 as the first ring, and uses the information of the ring Ch1 as the information of the first ring. The level to which the ring Ch1 and the ring Ch2 belong is the third level, that is, the third level includes the ring Ch1 and the ring Ch2.

In this embodiment of the present invention, the first ring is a ring in the second level that includes the source node and includes the smallest number of nodes, or the first ring is a ring in the third level that includes the source node and includes the smallest number of nodes. The first ring may also be a ring that includes source nodes and includes the smallest number of nodes in a layer lower than the third layer, and the implementation manner for the control device to obtain the information of the first ring is similar to the above description , which will not be repeated here.

102: The control device obtains information about a second ring according to information about the first network topology, the destination node, and the first layer, where the information about the second ring includes the layer to which the second ring belongs and the nodes included in the second ring, where the second ring is a ring that includes the sink node and includes the least number of nodes in the hierarchy to which the second ring belongs.

For example, the obtaining, by the control device, the information of the second ring according to the information of the first network topology, the sink node, and the first layer includes: the control device according to the first network topology and the information of the The information of the first level is obtained by obtaining a third node, the third node is a node with a child node in the first level, and the child node of the third node is the sink node directly connected to the sink node node or a node indirectly connected to the sink node; the control device obtains the information of the seventh ring according to the first network topology and the third node, and the seventh ring includes the A set of rings with a third node and the number of nodes included is less than a second preset value, the information of the seventh ring includes the nodes included in the second level and the seventh ring, and the level of the second level is low at the level of the first layer; the control device judges whether the information of the seventh ring includes the sink node; if the information of the third ring includes the sink node, from the information of the seventh ring The information of the eighth ring is obtained in the eighth ring, the eighth ring is the ring that includes the source node and includes the least number of nodes in the seventh ring, then the control device uses the information of the eighth ring as Information about the second ring.

For example, the first node and the third node may be the same, and the first node and the third node may also be different. If the parent node of the source node and the parent node of the sink node are the same node at the first level, then the first node and the third node are the same. If the parent node of the source node and the parent node of the sink node are different nodes of the first level, the first node and the third node are different.

In the network topology shown in FIG. 4 , if the sink node is node C8, the control device finds out node A1 included in the first level, and both node A2 and node A3 have child nodes. The control device finds that the child node B8 of the node A2 is indirectly connected to the sink node C8, and the control device also finds that the child node B10 of the node A3 is indirectly connected to the sink node C8. The control device uses node A2 or node A3 as the third node.

In the network topology shown in FIG. 4 , if the control device uses node A2 as the third node, the control device finds a ring Bh3 and a ring Bh4 . Both ring Bh3 and ring Bh4 include the third node (node A2), and the number of nodes included is less than the first preset value. Ring Bh3 includes node A2, node B8, node B9, node B10, node B11, node B12 and node A3. Ring Bh4 includes node A2, node B8, node B9, node B10, node B11, node 13, node 14, node B12 and node A3. Both the loop Bh3 and the loop Bh4 belong to the seventh loop. Here, an example is described where the control device finds two rings including the third node and the number of nodes included is smaller than a first preset value. The control device may also find more than two rings including the third node and the number of nodes included is less than a first preset value, which will not be repeated here.

In the network topology shown in FIG. 4 , if node B9 is the sink node, both ring Bh3 and ring Bh4 include the third node and the sink node. The ring Bh3 is the ring including the least number of nodes, and the control device obtains the information of the ring Bh3 from the information of the seventh ring, and uses the information of the ring Bh3 as the information of the eighth ring. In other words, the control device uses the information of the ring Bh3 as the information of the second ring. The level where ring Bh3 and ring Bh4 are located is the second level, that is, the second level includes ring Bh3 and ring Bh4.

Optionally, the controlling device obtaining the information of the second ring according to the information of the first network topology, the sink node, and the first layer further includes: if the information of the seventh ring does not include the source node, the control device obtains a fourth node according to the information of the first network topology and the seventh ring, the fourth node is a node with child nodes in the second level, and the fourth node The child node of the four nodes is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node; the control device obtains the For the information of the second ring, the level to which the second ring belongs is the third level, and the level of the third level is lower than the level of the second level.

In the network topology shown in FIG. 4, if node C8 is the sink node, neither ring Bh3 nor ring Bh4 includes the sink node (node C8), that is, the information of the seventh ring does not include the sink node. The control device acquires that the node B10 in the second level has child nodes according to the connection relationship between adjacent nodes in the first network topology and the information of the seventh ring. The node B10 is a node indirectly connected to the sink node, and the control device uses the node B10 as the fourth node.

In the network topology shown in FIG. 4 , the control device finds ring Ch3 and ring Ch4 according to the connection relationship between adjacent nodes in the first network topology. Both ring Ch3 and ring Ch4 include the fourth node (node B10) and the sink node (node C8). Ring Ch3 contains node B10, node C5, node C6, node C7, node C8 and node C9. Ring Ch4 contains node B10, node C5, node C6, node C7, node C8, node C12, node 13 and node C9. The number of nodes included in ring Ch3 is smaller than the number of nodes included in ring Ch4. The control device uses the ring Ch3 as the second ring, and uses the information of the ring Ch3 as the information of the second ring.

In this embodiment of the present invention, the second ring is a ring in the second level that includes the sink node and includes the smallest number of nodes, or the second ring is a ring in the third level that includes the sink node and includes the smallest number of nodes. The second ring may also be a ring that contains the sink node and includes the smallest number of nodes in a layer lower than the third layer, and the implementation of obtaining the information of the second ring is similar to the method described above , which will not be repeated here.

103: The control device obtains a preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring, and the preferred path is a route that satisfies the routing condition. For the path from the source node to the sink node, the route selection condition is: not passing through the nodes included in the third ring and/or the nodes included in the fourth ring, the third ring includes the nodes included in the first ring rings belonging to the same level and/or lower than the level of the first ring, and the fourth ring includes rings of the same level as the second ring and/or lower than the first ring The ring of the hierarchy to which the second ring belongs.

For example, if the parent node of the source node and the parent node of the sink node belong to the first level, and the parent node of the source node is different from the parent node of the sink node, the routing condition is Not passing through the nodes included in the third ring and the nodes included in the fourth ring, the third ring includes a ring at the same level as the first ring and/or a ring at a level lower than the level to which the first ring belongs , the fourth ring includes a ring at the same level as the second ring and/or a ring at a lower level than the second ring. If the parent node of the source node and the parent node of the sink node belong to the first level, and the parent node of the source node and the parent node of the sink node are the same, the routing condition is Nodes included in the third ring or nodes not included in the fourth ring.

For example, if the parent node of the source node is different from the parent node of the sink node, the control device will The information about the ring, obtaining the preferred path includes: the control device obtains a second network topology according to the routing condition and the first network topology, and the second network topology is filtered out on the basis of the first network topology The network topology obtained after the rings that do not meet the routing conditions and/or the links that do not meet the routing conditions; the control device according to the second network topology, the information of the first layer, the The information of the first ring and the information of the second ring obtain the first subnet topology, the second subnet topology and the third subnet topology, and the first subnet topology only includes nodes included in the first level , the second subnet topology includes nodes included in the first ring, and the third subnet topology includes nodes included in the second ring; the control device according to the second subnet topology and the Information about the first ring to obtain a first path, where the first path is a path from the source node in the second subnet topology to a fifth node included in the first subnet topology, and the fifth The nodes are connected to one or more nodes in the second subnet topology; the control device obtains a second path according to the information of the third subnet topology and the second ring, and the second path is the A path from the sink node in the third subnet topology to a sixth node included in the first subnet topology, where the sixth node is connected to one or more nodes in the third subnet topology; The control device obtains a third path according to the first subnet topology, the fifth node, and the sixth node, and the third path is reached by the fifth node in the first subnet topology the path of the sixth node; the control device obtains the preferred path according to the first path, the second path, and the third path, and the preferred path is the first path, the A path obtained by splicing the second path and the third path.

For example, in Fig. 5 to Fig. 12, the first level includes node 1, node 2, node 3, node 4, node 5, node 6, node 7 and node 8. 6-1 indicates that the parent node is the first level 6, and belongs to the node of the second level; 6-2 indicates that the parent node is the node 6 of the first level, and belongs to the node of the third level; 6-3 indicates that the parent node is the node of the first level 6, and belongs to the fourth level of nodes. 6-4 indicates that the parent node is the node 6 of the first level and belongs to the node of the fifth level. 3-1 indicates that the parent node is node 3 of the first level and belongs to the node of the second level; 3-2 indicates that the parent node is node 3 of the first level and belongs to the node of the third level; 3- 3 indicates that the parent node is node 3 of the first level and belongs to the node of the fourth level; 3-4 indicates that the parent node is node 6 of the first level and belongs to the node of the fifth level. Wherein, the second level is lower than the first level, the third level is lower than the second level, the fourth level is lower than the third level, and the fifth level is lower than the fourth level.

The control device filters out the rings lower than the level to which the first ring belongs and the rings lower than the level to which the second ring belongs included in the first network topology shown in FIG. 5 , to obtain the The second network topology. The control device filters rings at the same level as the first ring and rings at the same level as the second ring in the first network topology shown in FIG. 5 to obtain the first ring shown in FIG. 7 . Two network topology. The control device shown in FIG. 5 associates rings at the same level as the first ring, rings at a level lower than the level to which the first ring belongs, and rings at the same level as the second ring in the first network topology shown in FIG. Rings with the same level and rings with a level lower than the level to which the second ring belongs are filtered out to obtain the second network topology shown in FIG. 8 . The network topologies shown in FIG. 6 , FIG. 7 and FIG. 8 are three specific forms of the second network topology shown.

For example, the control device may divide the second network topology shown in FIG. 8 into three sub-network topologies, as shown in FIG. 9 , based on the second network topology shown in FIG. 8 . The first sub-network topology is shown as the Z2 area in FIG. 9 , and the first sub-network topology only includes nodes included in the first layer. The second sub-network topology is shown as the Z1 area in FIG. 9 , and the second sub-network topology includes the nodes included in the first ring, that is, the second sub-network topology includes the source node. The third sub-network topology is shown in the Z3 area in FIG. 9 , and the second sub-network topology includes nodes included in the second ring, that is, the second sub-network topology includes the sink node.

For example, the control device obtains a path from the source node to a fifth node included in the first sub-network topology as the first path according to the information of the Z1 area and the first ring. The first ring is the ring that includes the source node and includes the least number of nodes, and the first ring is shown as a ring H1 circled by a dotted line in the area Z1 in FIG. 9 . The first node is a node with a child node in the first level, and the child node of the first node is the source node, a node directly connected to the source node, or a node indirectly linked to the source node, As shown in FIG. 9 , the first node is a node 6 indirectly connected to the source node in the first level. The fifth node is a node connected to one or more nodes in the second subnetwork topology in the first subnetwork topology. As shown in FIG. 9, the fifth node is a node in the first subnetwork topology A node 6 linking multiple nodes in the second sub-network. Wherein, the fifth node may be the same as the first node, or may be different from the first node. As shown in FIG. 9 , the first path is the path from the source node to node 6 shown in FIG. 9 . The first path is the path shown by the solid line from the source node to the node 6 in the first level in FIG. 10 .

The control device obtains, as a second path, a path from the sink node to a sixth node included in the first subnetwork topology according to the third subnetwork topology and information about the second ring. The second ring is the ring that contains the sink node and contains the least number of nodes, and the second ring is shown as the ring H2 circled by the dotted circle in the Z3 area in FIG. 9 . The third node is a node with a child node in the first level, and the child node of the third node is the sink node, a node directly connected to the source node, or a node indirectly connected to the source node, As shown in FIG. 9 , the third node is a node 3 indirectly connected to the sink node in the first level. The sixth node is a node connected to one or more nodes in the second subnetwork topology in the first subnetwork topology. As shown in FIG. 9, the sixth node is a node in the first subnetwork topology A node 3 linking multiple nodes in the second subnetwork. Wherein, the sixth node may be the same as the third node, or may be different from the third node. As shown in FIG. 9 , the first path is a path from the sink node to node 3 shown in FIG. 9 . The second path is the path shown by the solid line from the sink node to node 3 in the first level in FIG. 10 .

The control device obtains a path from the fifth node to the sixth node as a third path according to the first subnet topology, the fifth node, and the sixth node. As shown in FIG. 9 , the third path is the path from node 6 to node 3 shown in FIG. 9 . The third path is the path shown by the solid line from node 6 in the first level to node 3 in the first level in FIG. 10 .

The control device obtains the preferred path of the first network topology after concatenating the first path, the second path, and the third path. The preferred path is shown in FIG. 10 .

For example, if the parent node of the source node is the same as the parent node of the sink node and is the same node at the first level, the control device, according to the routing condition, the first network topology, the The information of the first ring and the information of the second ring, obtaining the preferred path includes: the control device obtains a third network topology according to the routing condition and the first network topology, and the third network topology is a network topology obtained after filtering rings that do not meet the routing conditions and/or links that do not meet the routing conditions on the basis of the first network topology; the control device according to the third network topology , the information of the first level, the information of the first ring and the information of the second ring to obtain a fourth subnetwork topology, the fourth subnetwork topology includes the nodes included in the first ring and the The nodes included in the second ring; the control device obtains a preferred path according to the fourth subnetwork topology, the information of the first layer, the information of the first ring, and the information of the second ring, the The fourth subnetwork topology includes nodes included in the first ring and nodes included in the second ring, and the preferred path is a path from the source node to the sink node.

The first network topology is shown in Figure 11, and the control device filters out rings that do not meet the routing conditions and/or rings that do not meet the routing conditions based on the first network topology shown in Figure 11 After the links, the third network topology is obtained. The third network topology is obtained by filtering out rings at the same level as the first ring and/or rings at a level lower than the level to which the first ring belongs from the first network topology shown in FIG. 11 Network topology. Since the source node indirectly connected to the node belonging to the first level is the same as the parent node of the sink node, the source node and the sink node belong to the same sub-network topology, such as the fourth sub-network topology shown in FIG. 12 .

The control device selects a path from the source node to the sink node from the fourth sub-network topology shown in FIG. 12 as the preferred transmission path.

Optionally, the route selection condition further includes: the number of horizontal links included in the preferred path is less than a third preset value, and the control device according to the route selection condition, the first network topology, the first The information about the ring and the information about the second ring, and obtaining the preferred path includes: the control device obtaining a fourth network topology according to the routing condition and the first network topology, and the fourth network topology is the A network topology obtained after one or more horizontal links are identified on the basis of a network topology; the control device according to the fourth network topology, the information of the first layer, the information of the first ring, and the According to the information of the second ring, the fifth subnet topology, the sixth subnet topology and the seventh subnet topology are obtained, the fifth subnet topology only includes the nodes included in the first level, and the sixth subnet The topology includes nodes included in the first ring, and the seventh subnet topology includes nodes included in the second ring; the control device obtains, according to information about the sixth subnet topology and the first ring, a fourth path, the fourth path is a path from the source node in the sixth subnet topology to the seventh node included in the fourth subnet topology, and the seventh node is connected to the fifth subnet topology One or more nodes in the topology of the network; the control device obtains a fifth path according to the information of the seventh subnet topology and the second ring, and the fifth path is in the seventh subnet topology A path from the sink node to an eighth node included in the fourth subnet topology, where the eighth node is connected to one or more nodes in the sixth subnet topology, the fifth path and the The number of horizontal links included in the fourth path is less than the third preset value; the control device obtains a sixth path according to the fifth subnet topology, the seventh node, and the eighth node, and the The sixth path is the path from the seventh node to the eighth node in the fifth subnet topology; the control device according to the fourth path, the fifth path and the sixth path , to obtain the preferred path, where the preferred path is a path obtained by concatenating the fourth path, the fifth path, and the sixth path.

The horizontal link in the embodiment of the present invention is a link between two nodes belonging to different rings in the first network topology. As shown in Figure 13, in the ring composed of W1, W2, W3, W4 and W5, node W1 and node W5 respectively belong to two different rings, then the link between W1 and W5 is a horizontal link. Node W2 and node W3 respectively belong to two different rings, and the link between W2 and W3 is another horizontal link. After identifying the horizontal link, the control device may identify the horizontal link in the first network topology to obtain a fourth network topology. The fourth network topology is the first network topology with lateral links identified. The control device obtains the fifth subnet topology, the sixth subnet topology and the seventh subnet topology, similar to the above-mentioned obtaining the first subnet topology, the second subnet topology and the third subnet topology, refer to the above description, here No longer.

There are many paths from the source node to the fourth subnetwork topology including the seventh node, and the paths whose number of horizontal links exceeds the third preset value are removed from the multiple paths. There are many paths from the sink node to the fourth subnetwork topology including the eighth node, and the paths whose number of horizontal links exceeds the third preset value are removed from the multiple paths. If the third preset value is set to 1, the number of horizontal links in the selected transmission path cannot exceed one, and the control device selects the first horizontal link whose number of horizontal links does not exceed one. four paths and the fifth path. Wherein, the seventh node may be the same as or different from the first node, and the eighth node may be the same as or different from the third node.

In the method provided in the embodiment of the present invention, the control device obtains a preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring, and the preferred path is A path from the source node to the sink node that satisfies the routing condition. Use the routing condition to select the preferred path from the source node to the sink node, the preferred path does not pass through any ring that meets the hierarchy contained in the routing condition, and the selected preferred path can avoid practical applications. The rings on the passed levels make the optimal path of the output meet the requirements of practical applications.

FIG. 14 is a schematic structural diagram of an apparatus for selecting a transmission path in a network topology according to an embodiment of the present invention. The apparatus for selecting a transmission path in a network topology provided in an embodiment of the present invention may execute the method provided in an embodiment of the present invention. The apparatus for selecting a transmission path in a network topology provided in an embodiment of the present invention may be the control device in the foregoing embodiments. The device for selecting a transmission path in a network topology provided by an embodiment of the present invention includes: a first ring information acquisition unit 1401 , a second ring information acquisition unit 1402 , and a path acquisition unit 1403 .

The first ring information obtaining unit 1401 is configured to obtain the information of the first ring according to the first network topology, the information of the first level and the source node of the path, the first network topology includes the source node, the path The sink node, the nodes included in the first level, and the connection relationship between adjacent nodes, the first level is the highest level in the first network topology, and the information of the first level includes the first level A connection relationship between nodes included in a level, the information of the first ring includes the level to which the first ring belongs and the nodes included in the first ring, the first ring is the A ring that includes the source node and includes the least number of nodes in the hierarchy.

For example, the first ring information obtaining unit 1401 is specifically configured to: obtain a first node according to the first network topology and the information of the first layer, and the first node is a A node of a child node, the child node of the first node is the source node, a node directly connected to the source node or a node indirectly connected to the source node; according to the first network topology and the first node , to obtain the information of the fifth ring, the fifth ring is a set of rings including the first node in the second level and the number of nodes included is less than the first preset value, the information of the fifth ring includes the The nodes included in the second level and the fifth ring, the level of the second level is lower than the level of the first level; judging whether the information of the fifth ring includes the source node; if the second level The information of the fifth ring includes the source node, the information of the sixth ring is obtained from the information of the fifth ring, and the information of the sixth ring is used as the information of the first ring, and the sixth ring is the The fifth ring includes the source node and includes the least number of nodes.

Optionally, the first ring information obtaining unit 1401 is further specifically configured to: if the information of the fifth ring does not include the source node, according to the first network topology and the information of the fifth ring, obtain The second node, the second node is a node with a child node in the second level, and the child node of the second node is the source node, a node directly connected to the source node or indirectly connected to the source A node of a node; according to the first network topology and the second node, obtain the information of the first ring, the level to which the first ring belongs is a third level, and the level of the third level is lower than the level of the Describe the level of the second level.

The second ring information obtaining unit 1402 is configured to obtain second ring information according to the first network topology, the sink node, and the first layer information, and the second ring information includes the first The level to which the second ring belongs and the nodes included in the second ring, where the second ring is a ring that includes the sink node and includes the least number of nodes in the level to which the second ring belongs.

For example, the second ring information obtaining unit 1402 is specifically configured to: obtain a third node according to the first network topology and the information of the first layer, and the third node is a A node of a child node, the child node of the third node is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node; according to the first network topology and the third node , obtaining the information of the seventh ring, the seventh ring is a set of rings including the third node in the second level and the number of nodes included is less than a second preset value, the information of the seventh ring includes the The nodes included in the second level and the seventh ring, the level of the second level is lower than the level of the first level; judging whether the information of the seventh ring includes the sink node; if the second level The information of the third ring includes the sink node, the information of the eighth ring is obtained from the information of the seventh ring, and the information of the eighth ring is used as the information of the second ring, and the eighth ring is the information of the eighth ring. The seventh ring includes the source node and is the ring that includes the least number of nodes.

Optionally, the second ring information obtaining unit 1402 is further specifically configured to: if the information of the seventh ring does not include the source node, according to the first network topology and the information of the seventh ring, obtain A fourth node, where the fourth node is a node with a child node in the second level, and the child node of the fourth node is the sink node, a node directly connected to the sink node, or indirectly connected to the sink node A node of a node; according to the first network topology and the fourth node, obtain the information of the second ring, the level to which the second ring belongs is a third level, and the level of the third level is lower than the level of the Describe the level of the second level.

The path acquisition unit 1403 is configured to obtain an optimal path according to the path selection condition, the first network topology, the information of the first ring, and the information of the second ring, and the optimal path satisfies the path selection Conditional path from the source node to the sink node, the routing condition is: not passing through the nodes included in the third ring and/or the nodes included in the fourth ring, the third ring includes the same A ring belongs to a ring at the same level and/or a ring at a level lower than the first ring, and the fourth ring includes a ring at the same level as the second ring and/or at a level lower than the ring at which the first ring belongs. The ring of the hierarchy to which the second ring belongs.

For example, the path obtaining unit 1403 is specifically configured to: obtain a second network topology according to the path selection condition and the first network topology, and the second network topology is to filter out A network topology obtained after a ring and/or a link that does not meet the routing condition; according to the second network topology, the information of the first layer, and the information of the first ring information and the information of the second ring to obtain the first subnet topology, the second subnet topology and the third subnet topology, the first subnet topology only includes nodes included in the first level, and the second The second subnet topology includes nodes included in the first ring, and the third subnet topology includes nodes included in the second ring; according to information about the second subnet topology and the first ring, obtain the second A path, the first path is a path from the source node in the second subnet topology to a fifth node included in the first subnet topology, and the fifth node is connected to the second subnet One or more nodes in the topology; according to the information of the third subnet topology and the second ring, obtain a second path, the second path is the sink node in the third subnet topology A path to a sixth node included in the first subnet topology, the sixth node connecting to one or more nodes in the third subnet topology; according to the first subnet topology, the fifth The node and the sixth node obtain a third path, and the third path is a path from the fifth node to the sixth node in the first subnet topology; according to the first path, the The second path and the third path are used to obtain the optimal path, and the optimal path is a path obtained by splicing the first path, the second path, and the third path.

It should be noted here that, according to the second network topology, the information of the first layer, the information of the first ring and the information of the second ring, the first subnet topology and the second subnet topology and the third subnet topology are processed by the policy engine subunit in the path obtaining unit 1403, and the first path is obtained according to the information of the second subnet topology and the first ring, and according to the third Subnet topology and the information of the second ring to obtain the second path, according to the first path, the second path and the third path, the path calculator in the path obtaining unit 1403 A path computing subunit (Path Compute Element, PCE) performs processing. As shown in FIG. 15 , the path acquisition unit 1403 includes a policy engine subunit 1501 and a PCE subunit 1502 .

When the first network topology is a large network topology such as a software-defined packet transport network (SDN-Packet TransportNetwork, SPTN) provincial network topology, since the nodes included in the network topology can reach the order of 100,000, PCE cannot calculate such a huge The transmission path from the source node to the sink node in the first network topology. The policy engine subunit 1501 in the path acquisition unit 1403 first removes the rings that do not meet the routing conditions in the first network topology, and then removes the rings that do not meet the routing conditions from the first network topology. Divide into three subnetwork topologies: a first subnetwork topology, a second subnetwork topology and a third subnetwork topology are obtained. Then, the PCE subunit 1502 obtains the first path according to the information of the second subnet topology and the first ring, and obtains the second path according to the information of the third subnet topology and the second ring , according to the first path, the second path and the third path. The policy engine subunit 1501 then combines the first path, the second path and the third path to output a transmission path from the source node to the sink node. In this way, the traditional PCE subunit can be used to calculate the transmission path from the source node to the sink node in the first network topology.

For example, the path obtaining unit 1403 is specifically configured to: obtain a third network topology according to the path selection condition and the first network topology, and the third network topology is filtered out based on the first network topology A network topology obtained after a ring and/or a link that does not meet the routing condition; according to the third network topology, the information of the first layer, and the information of the first ring information and the information of the second ring to obtain a fourth subnetwork topology, the fourth subnetwork topology includes the nodes included in the first ring and the nodes included in the second ring; according to the fourth subnetwork Topology, the information of the first level, the information of the first ring and the information of the second ring obtain a preferred path, and the fourth sub-network topology includes the nodes included in the first ring and includes the nodes included in the second ring The nodes included in the second ring, the preferred path is a path from the source node to the sink node.

Optionally, the route selection condition further includes that the number of horizontal links contained in the preferred path is less than a third preset value, and the route acquisition unit 1403 is further specifically configured to: according to the route selection condition and the first A network topology, obtaining a fourth network topology, the fourth network topology is a network topology obtained after one or more horizontal links are identified on the basis of the first network topology; according to the fourth network topology, the The information of the first level, the information of the first ring and the information of the second ring obtain the fifth subnet topology, the sixth subnet topology and the seventh subnet topology, and the fifth subnet topology only includes The nodes included in the first level, the sixth subnet topology includes nodes included in the first ring, and the seventh subnet topology includes nodes included in the second ring; according to the sixth subnet information about the topology and the first ring, and obtain a fourth path, where the fourth path is a path from the source node to the seventh node included in the fourth subnet topology in the sixth subnet topology, The seventh node is connected to one or more nodes in the fifth subnet topology; according to the information of the seventh subnet topology and the second ring, a fifth path is obtained, and the fifth path is the In the seventh subnet topology, the path from the sink node to the eighth node included in the fourth subnet topology, where the eighth node is connected to one or more nodes in the sixth subnet topology, the The number of horizontal links contained in the fifth path and the fourth path is less than the third preset value; according to the fifth subnet topology, the seventh node, and the eighth node, the sixth a path, the sixth path is a path from the seventh node to the eighth node in the fifth subnet topology; according to the fourth path, the fifth path, and the sixth path, The preferred path is obtained, where the preferred path is a path obtained by splicing the fourth path, the fifth path, and the sixth path.

FIG. 16 is a schematic structural diagram of an apparatus for selecting a transmission path in a network topology according to an embodiment of the present invention. The apparatus for selecting a transmission path in a network topology provided in an embodiment of the present invention may execute the method provided in an embodiment of the present invention. The apparatus for selecting a transmission path in a network topology provided in an embodiment of the present invention may be the control device in the foregoing embodiments. The device shown in FIG. 16 and the device shown in FIG. 14 may be the same device. Figure 16 shows the content of the device for selecting a transmission path in the network topology from a physical point of view, and Figure 14 shows the content of the device for selecting a transmission path in the network topology from a logical point of view.

The device for selecting a transmission path in a network topology provided in an embodiment of the present invention includes: a memory 1601 , a processor 1602 , a communication interface 1603 and a communication bus 1604 . The processor 1602 , the memory 1601 and the communication interface 1603 communicate through the communication bus 1604 . The memory 1601 is used to store program codes.

The processor 1602 is configured to execute the following content after reading the program code stored in the memory 1601:

According to the first network topology, the information of the first level and the source node of the path, the information of the first ring is obtained, and the first network topology includes the source node, the sink node of the path, and the path included in the first level. The connection relationship between nodes and adjacent nodes, the first level is the highest level in the first network topology, and the information of the first level includes the connection relationship between nodes included in the first level, so The information of the first ring includes the layer to which the first ring belongs and the nodes included in the first ring, and the first ring is a node that includes the source node and includes nodes in the layer to which the first ring belongs the least number of rings;

Obtain information about a second ring according to the first network topology, the sink node, and the information about the first layer, where the information about the second ring includes the layer to which the second ring belongs and the second ring Included nodes, the second ring is a ring that includes the sink node and includes the least number of nodes in the hierarchy to which the second ring belongs;

According to the routing conditions, the first network topology, the information of the first ring, and the information of the second ring, an optimal path is obtained, and the optimal path is a route from the source node that satisfies the routing conditions For the path of the sink node, the path selection condition is: no nodes included in the third ring and/or nodes included in the fourth ring, the third ring includes the same level as the first ring and/or a ring whose level is lower than the level to which the first ring belongs, the fourth ring includes the same ring as the level to which the second ring belongs and/or a ring whose level is lower than the level to which the second ring belongs ring.

For example, the processor 1602 specifically performs the following operations:

According to the information of the first network topology and the first level, a first node is obtained, the first node is a node with child nodes in the first level, and the child nodes of the first node are the a source node, a node directly connected to said source node, or a node indirectly connected to said source node;

Obtain information about a fifth ring according to the first network topology and the first node, the fifth ring includes the first node in the second level and the number of nodes included is less than a first preset value a set of rings, the information of the fifth ring includes the second level and the nodes included in the fifth ring, and the level of the second level is lower than that of the first level;

judging whether the information of the fifth ring includes the source node;

If the information of the fifth ring includes the source node, obtain the information of the sixth ring from the information of the fifth ring, use the information of the sixth ring as the information of the first ring, and the information of the sixth ring The sixth ring is the ring that includes the source node and includes the least number of nodes in the fifth ring.

Optionally, the processor 1602 further performs the following operation: if the information of the fifth ring does not include the source node, obtain a second node according to the first network topology and the information of the fifth ring, The second node is a node having a child node in the second level, and the child node of the second node is the source node, a node directly connected to the source node, or a node indirectly connected to the source node; According to the first network topology and the second node, obtain the information of the first ring, the level to which the first ring belongs is a third level, and the level of the third level is lower than the second level level.

For example, the processor 1602 specifically performs the following operations:

According to the information of the first network topology and the first level, a third node is obtained, the third node is a node with child nodes in the first level, and the child nodes of the third node are the a sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node;

Obtain information about a seventh ring according to the first network topology and the third node, the seventh ring includes the third node in the second level and the number of nodes included is less than a second preset value a set of rings, the information of the seventh ring includes the second level and the nodes included in the seventh ring, and the level of the second level is lower than the level of the first level;

judging whether the information of the seventh ring includes the sink node;

If the information of the third ring includes the sink node, obtain the information of the eighth ring from the information of the seventh ring, use the information of the eighth ring as the information of the second ring, and the information of the second ring The eighth ring is the ring that includes the source node and includes the least number of nodes in the seventh ring.

Optionally, the processor 1602 further performs the following operation: if the information of the seventh ring does not include the source node, obtain a fourth node according to the first network topology and the information of the seventh ring, The fourth node is a node with a child node in the second level, and the child node of the fourth node is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node; According to the first network topology and the fourth node, obtain the information of the second ring, the level to which the second ring belongs is a third level, and the level of the third level is lower than the second level level.

For example, the processor 1602 specifically performs the following operations:

According to the routing conditions and the first network topology, a second network topology is obtained, and the second network topology is to filter out rings that do not meet the routing conditions and/or rings that do not meet the routing conditions based on the first network topology. The network topology obtained after the link meeting the routing condition;

Obtain a first subnet topology, a second subnet topology, and a third subnet topology according to the second network topology, the information of the first layer, the information of the first ring, and the information of the second ring , the first subnet topology includes only nodes included in the first level, the second subnet topology includes nodes included in the first ring, and the third subnet topology includes nodes included in the second ring the node;

Obtaining a first path according to the information about the second subnet topology and the first ring, where the first path is from the source node in the second subnet topology to the first subnet topology includes a path of a fifth node, the fifth node connecting one or more nodes in the second subnet topology;

Obtaining a second path according to information about the third subnet topology and the second ring, where the second path is from the destination node in the third subnet topology to the first subnet topology includes The path of the sixth node of the sixth node, the sixth node is connected to one or more nodes in the third subnet topology;

According to the first subnet topology, the fifth node, and the sixth node, a third path is obtained, and the third path is from the fifth node to the sixth node in the first subnet topology. A six-node path;

Obtain the preferred route according to the first route, the second route and the third route, where the preferred route is obtained by splicing the first route, the second route and the third route path of.

For example, the processor 1602 specifically performs the following operations:

According to the routing conditions and the first network topology, a third network topology is obtained, and the third network topology is to filter out rings that do not meet the routing conditions and/or rings that do not meet the routing conditions based on the first network topology. The network topology obtained after the link meeting the routing condition;

According to the third network topology, the information of the first layer, the information of the first ring, and the information of the second ring, obtain a fourth subnetwork topology, where the fourth subnetwork topology includes the first the nodes included in the first ring and the nodes included in the second ring;

A preferred path is obtained according to the fourth sub-network topology, the information of the first level, the information of the first ring, and the information of the second ring, the fourth sub-network topology includes the first ring including and nodes included in the second ring, and the preferred path is a path from the source node to the sink node.

For example, the route selection condition is that the number of horizontal links contained in the preferred route is less than a third preset value, and the processor 1602 specifically performs the following operations:

Obtaining a fourth network topology according to the routing condition and the first network topology, where the fourth network topology is a network topology obtained after identifying one or more horizontal links on the basis of the first network topology;

Obtain a fifth subnet topology, a sixth subnet topology, and a seventh subnet topology according to the fourth network topology, the information of the first layer, the information of the first ring, and the information of the second ring , the fifth subnet topology includes only nodes included in the first level, the sixth subnet topology includes nodes included in the first ring, and the seventh subnet topology includes nodes included in the second ring the node;

Obtaining a fourth path according to the information about the sixth subnet topology and the first ring, where the fourth path is from the source node in the sixth subnet topology to the fourth subnet topology includes A path of a seventh node of the fifth subnetwork topology, the seventh node connecting one or more nodes in the fifth subnet topology;

Obtaining a fifth path according to the seventh subnet topology and the information of the second ring, where the fifth path is from the sink node to the fourth subnet topology in the seventh subnet topology includes The path of the eighth node, the eighth node is connected to one or more nodes in the sixth subnetwork topology, the number of horizontal links contained in the fifth path and the fourth path is smaller than that of the first Three preset values;

The control device obtains a sixth path according to the fifth subnet topology, the seventh node, and the eighth node, and the sixth path is the seventh node in the fifth subnet topology a path to the eighth node;

The control device obtains the preferred route according to the fourth route, the fifth route and the sixth route, and the preferred route is the fourth route, the fifth route and the sixth route The path obtained after path splicing.

The aforementioned processor may be a microprocessor or the processor may be any conventional processor. The steps of the methods disclosed in the embodiments of the present invention may be directly implemented by a hardware processor, or implemented by a combination of hardware and software modules in the processor. When implemented in software, codes for realizing the functions described above can be stored in a computer-readable medium. Computer-readable media includes computer storage media. A storage media may be any available media that can be accessed by a computer. Take this as an example but not limited to: the computer readable medium can be random access memory (full name in English is random access memory, English abbreviation is RAM), read-only memory (full name in English is read-only memory, English abbreviation is ROM), Electrically Erasable Programmable Read-Only Memory (English full name is electrically erasableprogrammable read-only memory, English abbreviation is EEPROM), read-only CD (English full name is compactdisc read-only memory, English abbreviation is CD-ROM) or other optical disc storage, Disk storage medium or other magnetic storage device, or any other medium that can be used to carry or store program code in the form of instructions or data structures and can be accessed by a computer. The computer-readable medium may be a compact disc (compact disc in English, abbreviated as CD in English), laser disc, digital video disc (digital video disc in English, abbreviated as DVD in English), floppy disk or Blu-ray disc.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, and are not intended to limit them; although the present invention and the beneficial effects brought by the present invention have been described in detail with reference to the foregoing embodiments, those skilled in the art Those of ordinary skill in the art should understand that: they can still modify the technical solutions described in the foregoing embodiments, or perform equivalent replacements for some of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the present invention Scope of Claims.

Claims (16)

1. A method for selecting a transmission path in a network topology, characterized in that the method comprises: The control device obtains the information of the first ring according to the first network topology, the information of the first level, and the source node of the path, where the first network topology includes the source node, the sink node of the path, and the first level Included nodes and connection relationships between adjacent nodes, the first level is the highest level in the first network topology, and the information of the first level includes connection relationships between nodes included in the first level , the information of the first ring includes the layer to which the first ring belongs and the nodes included in the first ring, and the first ring includes the source node in the layer to which the first ring belongs and includes The ring with the least number of nodes; The control device obtains the information of the second ring according to the first network topology, the sink node, and the information of the first layer, and the information of the second ring includes the layer to which the second ring belongs and the nodes included in the second ring, where the second ring is a ring that includes the sink node and includes the least number of nodes in the hierarchy to which the second ring belongs; The control device obtains a preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring, and the preferred path is the slave that satisfies the routing condition. The path from the source node to the sink node, the path selection condition is: do not pass through the nodes included in the third ring and/or the nodes included in the fourth ring, the third ring includes the nodes that belong to the first ring rings of the same level and/or a level lower than the level to which the first ring belongs, and the fourth ring includes rings of the same level as the second ring and/or a level lower than the second ring The ring of the hierarchy it belongs to. 2. The method according to claim 1, wherein the control device obtains the information of the first ring according to the first network topology, the information of the first level and the source node of the path, comprising: The control device obtains a first node according to the first network topology and the information of the first level, the first node is a node with child nodes in the first level, and the child nodes of the first node The node is the source node, a node directly connected to the source node, or a node indirectly connected to the source node; The control device obtains information of a fifth ring according to the first network topology and the first node, and the fifth ring includes the first node in the second level and includes a smaller number of nodes than the first A set of rings with preset values, the information of the fifth ring includes the second level and the nodes included in the fifth ring, and the level of the second level is lower than the level of the first level; The control device judges whether the information of the fifth ring includes the source node; If the information of the fifth ring includes the source node, the control device obtains the information of the sixth ring from the information of the fifth ring, and uses the information of the sixth ring as the information of the first ring , the sixth ring is a ring that includes the source node and includes the least number of nodes in the fifth ring. 3. The method according to claim 2, wherein the control device obtaining the information of the first ring according to the first network topology, the information of the first level and the source node of the path further comprises: If the information of the fifth ring does not include the source node, the control device obtains a second node according to the first network topology and the information of the fifth ring, and the second node is the first node. A node having a child node in the second level, where the child node of the second node is the source node, a node directly connected to the source node, or a node indirectly connected to the source node; The control device obtains the information of the first ring according to the first network topology and the second node, the layer to which the first ring belongs is a third layer, and the level of the third layer is lower than the Describe the level of the second level. 4. The method according to any one of claims 1 to 3, wherein the control device obtains the information of the second ring according to the first network topology, the sink node, and the information of the first layer Information includes: The control device obtains a third node according to the first network topology and information of the first level, the third node is a node with child nodes in the first level, and the child nodes of the third node The node is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node; The control device obtains information of a seventh ring according to the first network topology and the third node, and the seventh ring includes the third node in the second level and includes a smaller number of nodes than the second A set of rings with preset values, the information of the seventh ring includes the second level and the nodes included in the seventh ring, and the level of the second level is lower than the level of the first level; The control device judges whether the information of the seventh ring includes the sink node; If the information of the third ring includes the sink node, the control device obtains the information of the eighth ring from the information of the seventh ring, and uses the information of the eighth ring as the information of the second ring , the eighth ring is the ring that includes the sink node and includes the least number of nodes in the seventh ring. 5. The method according to claim 4, wherein the control device obtaining the information of the second ring according to the first network topology, the sink node, and the information of the first layer further comprises: If the information of the seventh ring does not include the sink node, the control device obtains a fourth node according to the first network topology and the information of the seventh ring, and the fourth node is the first A node with child nodes in the second level, where the child node of the fourth node is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node; The control device obtains the information of the second ring according to the first network topology and the fourth node, the layer to which the second ring belongs is a third layer, and the level of the third layer is lower than the Describe the level of the second level. 6. The method according to claim 1, 2, 3 or 5, characterized in that, the control device according to the route selection condition, the first network topology, the information of the first ring and the information of the second ring information, the preferred path to obtain includes: The control device obtains a second network topology based on the routing condition and the first network topology, and the second network topology is to filter out rings that do not meet the routing condition based on the first network topology. and/or the network topology obtained after links that do not meet the routing conditions; The control device obtains the first subnet topology, the second subnet topology, and the second subnet topology according to the second network topology, the first layer information, the first ring information, and the second ring information. Three subnet topology, the first subnet topology includes only nodes included in the first level, the second subnet topology includes nodes included in the first ring, and the third subnet topology includes the the nodes included in the second ring; The control device obtains a first path according to information about the second subnet topology and the first ring, and the first path is from the source node to the first ring in the second subnet topology. the subnet topology includes a path of a fifth node connecting one or more nodes in the second subnet topology; The control device obtains a second path according to the information of the third subnet topology and the second ring, and the second path is from the sink node to the first link in the third subnet topology. a path of a sixth node included in the subnet topology, the sixth node connecting one or more nodes in the third subnet topology; The control device obtains a third path according to the first subnet topology, the fifth node, and the sixth node, and the third path is the fifth node in the first subnet topology a path to the sixth node; The control device obtains the preferred route according to the first route, the second route and the third route, and the preferred route is the first route, the second route and the third route The path obtained after path splicing. 7. The method according to claim 1, 2, 3 or 5, wherein the control device according to the routing condition, the first network topology, the information of the first ring and the information of the second ring information, the preferred path to obtain includes: The control device obtains a third network topology based on the routing condition and the first network topology, and the third network topology is to filter out rings that do not meet the routing condition based on the first network topology. and/or the network topology obtained after links that do not meet the routing conditions; The control device obtains a fourth subnetwork topology according to the third network topology, the information of the first layer, the information of the first ring, and the information of the second ring, and the fourth subnetwork topology including nodes included in the first ring and nodes included in the second ring; The control device obtains an optimal path according to the fourth subnetwork topology, the information of the first layer, the information of the first ring, and the information of the second ring, and the optimal path is the source node reaching The path of the sink node. 8. The method according to claim 1, 2, 3 or 5, wherein the route selection condition further comprises that the number of transverse links included in the preferred route is less than a third preset value, and the control device According to the routing condition, the first network topology, the information of the first ring and the information of the second ring, obtaining the optimal path includes: The control device obtains a fourth network topology according to the routing condition and the first network topology, and the fourth network topology is obtained after identifying one or more horizontal links on the basis of the first network topology network topology; The control device obtains the fifth subnet topology, the sixth subnet topology, and the sixth subnet topology according to the fourth network topology, the information of the first layer, the information of the first ring, and the information of the second ring. Seven subnet topology, the fifth subnet topology only includes nodes included in the first level, the sixth subnet topology includes nodes included in the first ring, and the seventh subnet topology includes the the nodes included in the second ring; The control device obtains a fourth path according to the information of the sixth subnet topology and the first ring, and the fourth path is from the source node to the fifth ring in the sixth subnet topology. the subnet topology includes a path of a seventh node connecting one or more nodes in the sixth subnet topology; The control device obtains a fifth path according to the information of the seventh subnet topology and the second ring, and the fifth path is from the destination node to the fifth path in the seventh subnet topology. The path of the eighth node included in the subnetwork topology, the eighth node connecting one or more nodes in the seventh subnetwork topology, the number of horizontal links contained in the fifth path and the fourth path less than the third preset value; The control device obtains a sixth path according to the fifth subnet topology, the seventh node, and the eighth node, and the sixth path is the seventh node in the fifth subnet topology a path to the eighth node; The control device obtains the preferred route according to the fourth route, the fifth route and the sixth route, and the preferred route is the fourth route, the fifth route and the sixth route The path obtained after path splicing. 9. A device for selecting a transmission path in a network topology, characterized in that the device comprises: The first ring information obtaining unit is configured to obtain the information of the first ring according to the first network topology, the information of the first level and the source node of the path, and the first network topology includes the source node and the sink of the path Nodes, nodes included in the first level, and connection relationships between adjacent nodes, the first level is the highest level in the first network topology, and the information of the first level includes the first level The connection relationship between the included nodes, the information of the first ring includes the layer to which the first ring belongs and the nodes included in the first ring, and the first ring is in the layer to which the first ring belongs a ring including the source node and including the least number of nodes; The second ring information obtaining unit is configured to obtain information of a second ring according to the first network topology, the sink node, and the information of the first layer, and the information of the second ring includes the second ring The level to which it belongs and the nodes included in the second ring, where the second ring is a ring that includes the sink node and includes the least number of nodes in the level to which the second ring belongs; a path obtaining unit, configured to obtain a preferred path according to the routing condition, the first network topology, the information of the first ring, and the information of the second ring, and the preferred path is a route that satisfies the routing condition For the path from the source node to the sink node, the route selection condition is: not passing through the nodes included in the third ring and/or the nodes included in the fourth ring, the third ring includes the nodes included in the first ring rings belonging to the same level and/or lower than the level of the first ring, and the fourth ring includes rings of the same level as the second ring and/or lower than the first ring The ring of the hierarchy to which the second ring belongs. 10. The device according to claim 9, wherein the first ring information acquisition unit is specifically configured to: According to the information of the first network topology and the first level, a first node is obtained, the first node is a node with child nodes in the first level, and the child nodes of the first node are the a source node, a node directly connected to said source node, or a node indirectly connected to said source node; Obtain information about a fifth ring according to the first network topology and the first node, the fifth ring includes the first node in the second level and the number of nodes included is less than a first preset value a set of rings, the information of the fifth ring includes the second level and the nodes included in the fifth ring, and the level of the second level is lower than that of the first level; judging whether the information of the fifth ring includes the source node; If the information of the fifth ring includes the source node, obtain the information of the sixth ring from the information of the fifth ring, use the information of the sixth ring as the information of the first ring, and the information of the sixth ring The sixth ring is the ring that includes the source node and includes the least number of nodes in the fifth ring. 11. The device according to claim 10, wherein the first ring information acquisition unit is further specifically configured to: If the information of the fifth ring does not include the source node, according to the first network topology and the information of the fifth ring, obtain a second node, and the second node is a child node in the second layer A node of a node, the child node of the second node is the source node, a node directly connected to the source node, or a node indirectly connected to the source node; According to the first network topology and the second node, obtain the information of the first ring, the level to which the first ring belongs is a third level, and the level of the third level is lower than the second level level. 12. The device according to any one of claims 9 to 11, wherein the second ring information acquisition unit is specifically used for: According to the information of the first network topology and the first level, a third node is obtained, the third node is a node with child nodes in the first level, and the child nodes of the third node are the a sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node; Obtain information about a seventh ring according to the first network topology and the third node, the seventh ring includes the third node in the second level and the number of nodes included is less than a second preset value a set of rings, the information of the seventh ring includes the second level and the nodes included in the seventh ring, and the level of the second level is lower than the level of the first level; judging whether the information of the seventh ring includes the sink node; If the information of the third ring includes the sink node, obtain the information of the eighth ring from the information of the seventh ring, use the information of the eighth ring as the information of the second ring, and the information of the second ring The eighth ring is the ring that includes the sink node and includes the least number of nodes in the seventh ring. 13. The device according to claim 12, wherein the second ring information acquisition unit is further specifically configured to: If the information of the seventh ring does not include the sink node, according to the first network topology and the information of the seventh ring, a fourth node is obtained, and the fourth node is a sub-node in the second layer A node of a node, where the child node of the fourth node is the sink node, a node directly connected to the sink node, or a node indirectly connected to the sink node; According to the first network topology and the fourth node, obtain the information of the second ring, the level to which the second ring belongs is a third level, and the level of the third level is lower than the second level level. 14. The device according to claim 9, 10, 11 or 13, wherein the path obtaining unit is specifically used for: According to the routing conditions and the first network topology, a second network topology is obtained, and the second network topology is to filter out rings that do not meet the routing conditions and/or rings that do not meet the routing conditions based on the first network topology. The network topology obtained after the links meeting the routing conditions; Obtain a first subnet topology, a second subnet topology, and a third subnet topology according to the second network topology, the information of the first layer, the information of the first ring, and the information of the second ring , the first subnet topology includes only nodes included in the first level, the second subnet topology includes nodes included in the first ring, and the third subnet topology includes nodes included in the second ring the node; Obtaining a first path according to the information about the second subnet topology and the first ring, where the first path is from the source node in the second subnet topology to the first subnet topology includes a path of a fifth node, the fifth node connecting one or more nodes in the second subnet topology; Obtaining a second path according to information about the third subnet topology and the second ring, where the second path is from the destination node in the third subnet topology to the first subnet topology includes The path of the sixth node of the sixth node, the sixth node is connected to one or more nodes in the third subnet topology; According to the first subnet topology, the fifth node, and the sixth node, a third path is obtained, and the third path is from the fifth node to the sixth node in the first subnet topology. A six-node path; Obtain the preferred route according to the first route, the second route and the third route, where the preferred route is obtained by splicing the first route, the second route and the third route path of. 15. The device according to claim 9, 10, 11 or 13, wherein the path obtaining unit is specifically used for: According to the routing conditions and the first network topology, a third network topology is obtained, and the third network topology is to filter out rings that do not meet the routing conditions and/or rings that do not meet the routing conditions on the basis of the first network topology. The network topology obtained after the links meeting the routing conditions; According to the third network topology, the information of the first layer, the information of the first ring, and the information of the second ring, obtain a fourth subnetwork topology, where the fourth subnetwork topology includes the first nodes included in a ring and nodes included in said second ring; Obtaining a preferred path according to the fourth subnetwork topology, the information of the first level, the information of the first ring, and the information of the second ring, where the preferred path is from the source node to the sink node path of. 16. The device according to claim 9, 10, 11 or 13, wherein the route selection condition further includes that the number of transverse links contained in the preferred route is less than a third preset value, and the route acquisition Units are used specifically for: Obtaining a fourth network topology according to the routing condition and the first network topology, where the fourth network topology is a network topology obtained after identifying one or more horizontal links on the basis of the first network topology; Obtain a fifth subnet topology, a sixth subnet topology, and a seventh subnet topology according to the fourth network topology, the information of the first layer, the information of the first ring, and the information of the second ring , the fifth subnet topology includes only nodes included in the first level, the sixth subnet topology includes nodes included in the first ring, and the seventh subnet topology includes nodes included in the second ring the node; Obtaining a fourth path according to the sixth subnet topology and the information of the first ring, where the fourth path is from the source node in the sixth subnet topology to the fifth subnet topology including a path of a seventh node, the seventh node connecting one or more nodes in the sixth subnet topology; Obtaining a fifth path according to the seventh subnet topology and the information of the second ring, where the fifth path is from the sink node to the fifth subnet topology in the seventh subnet topology includes The path of the eighth node, the eighth node is connected to one or more nodes in the seventh subnetwork topology, the number of horizontal links contained in the fifth path and the fourth path is smaller than that of the first Three preset values; According to the fifth subnet topology, the seventh node, and the eighth node, a sixth path is obtained, and the sixth path is from the seventh node to the fifth subnet topology in the fifth subnet topology. eight-node path; Obtain the optimal path according to the fourth path, the fifth path, and the sixth path, where the optimal path is obtained by splicing the fourth path, the fifth path, and the sixth path path of.