CN100518382C - Method and device for finding shortest path under multi-constraint conditions in automatic switched optical network - Google Patents

Abstract

The apparatus comprises: an index unit and a comparison unit. Wherein, said index unit is used in calculating and saving the index values of all network nodes by using SPF; the comparison unit is used for sequentially comparing the index value of each node according to multi constrain conditions to get the nodes with shortest connection path, and establishing the connection between two nodes.

Description

Method and device for finding shortest path under multi-constraint conditions in automatic switched optical network

technical field

The invention relates to a method for establishing the shortest path in a network, in particular to a method and a device for finding the shortest path between two points in ASON (Automatically Switched Optical Network) when there are various constraints.

Background technique

In the transmission of network data, it is hoped that the data from the data source to the destination can arrive in the shortest time, and it is also hoped that less resources are occupied in data transmission. Therefore, the devices in the network can be regarded as points, the communication channel between devices can be regarded as a point-to-point link, and the transmission characteristics of the communication channel between devices can be regarded as a metric. The problem of determining the shortest (minimum metric) path between two points on a topological graph (including points and links).

SPF (Shortest Path First) algorithm (also known as Dijkstra algorithm) is the most commonly used algorithm for calculating the shortest path, such as OSPF (Open Shortest Path First) protocol of IGP (Interior Gateway Protocol) protocol, ISIS (Intermediate System to Intermediate System ) protocols, after obtaining the current network topology, the router uses the SPF algorithm to calculate the shortest path tree with itself as the root, and then generates the corresponding routing forwarding table. The traditional SPF algorithm uses metric to generate the shortest path tree.

In the ASON network, there are more requirements for the utilization of network resources. The shortest path between two points puts forward various constraints, such as the nodes that must pass through, the links that must be avoided, and the minimum link Bandwidth, etc., are collectively referred to as multiple constraints. In the multi-constraint, there will be the following constraints, such as requiring the minimum number of hops (hops), requiring the maximum total bandwidth of all links, requiring the maximum percentage of available bandwidth of all links, etc. For such constraints, the traditional SPF algorithm, Only the calculation method of the shortest path under the existence of a certain constraint is given. When there are multiple constraints at the same time, the current calculation method cannot calculate the optimal path at one time.

To sum up, there is a need for a technical solution for finding the shortest path between two points when there are various constraints.

Contents of the invention

The technical problem to be solved by the present invention is to provide a method and device for searching the shortest path under multi-constraint conditions in an automatic switched optical network, which solves the current problem that the optimal path cannot be calculated at one time, saves the number of calculations, and improves the speed.

In order to solve the above problems, the present invention provides a shortest path search device under multi-constraint conditions in an automatic switched optical network, including an index unit and a comparison unit, wherein,

The index unit is used to calculate and store the index values of all nodes in the network through SPF;

The comparison unit is used to sequentially compare the corresponding index values of each node in the index unit according to the order of the index according to various constraints, to obtain the node with the shortest path connected to this node, and to establish a connection between two points.

Further, the above-mentioned device may further include that when the comparison unit performs the comparison, the constraint condition of the first index is set as a priority, and the constraints are decremented sequentially.

Further, the above-mentioned device may further include, when the comparing unit performs the comparison, if there are multiple nodes with the same index priority, all multiple nodes with the same index priority and the current node shall establish a connection between each two points .

Further, the above-mentioned apparatus may further include that the node of the shortest path connected to the present node is a plurality of index-first nodes.

The present invention also provides a method for searching the shortest path under multi-constraint conditions in an automatic switching optical network, comprising the following steps:

a. Obtain multiple index values from this node to all neighbor nodes through SPF calculation;

b. According to various constraints, compare the corresponding index values of each node in sequence according to the order of the index, get the node with the shortest path connected to this node, and establish a connection between two points

Further, the above method may further include, in the step b, prioritizing the constraint condition of the first index during the comparison, and decrementing in order.

Further, the above method may further include, in the step b, if there are multiple nodes with the same index priority, establishing connections between all the multiple nodes with the same index priority and the current node.

Further, the above method may further include, in the step b, the node of the shortest path connected to the current node is a plurality of index-first nodes.

Compared with the prior art, the application of the present invention calculates the shortest path by introducing a multi-index method, that is, the shortest path is obtained through one SPF calculation, which saves the number of calculations and improves the speed.

Description of drawings

Fig. 1 is a schematic network topology diagram;

Fig. 2 is the flowchart of the shortest path search method in the embodiment of the present invention;

Fig. 3 is under the multi-constraint (metric and link available bandwidth percentage maximum) condition in the specific embodiment of the present invention, for the network topology shown in Fig. 1, adopt the process decomposition diagram of the shortest path search method;

Fig. 4 is an exploded view of the process of using the shortest path search method for the network topology shown in Fig. 1 under the condition of multiple constraints (metric and hop number) in the specific embodiment of the present invention.

Detailed ways

The specific embodiments of the present invention will be further described below in conjunction with the accompanying drawings.

Figure 1 is a schematic network topology diagram, in which the link attribute represents the metric of the link and the percentage of the available bandwidth of the link to the total bandwidth.

In the specific implementation of the present invention, when SPF calculates and obtains the next hop node, the concept of multiple indexes (or key values) is introduced, that is, the first index (K ₁ ), the second index (K ₂ )... The Nth index (K _n ), when selecting the next item, calculates the value of the multi-index, and then compares the multi-indexes to select the optimal next hop.

Multi-index For the multi-constraints of the user, the multi-constraints here have priority levels. The first index constraint must be satisfied first, and the order is reduced. The multi-index comparison method can use the functional relationship y=f(K ₁ , K ₂ . . . K _n ), where y represents the comparison result, that is, the final selected next-hop node. For example, an available multi-index comparison method is: compare the first index, and the node with the first index is superior; if the first index is equal, compare the second index, and the node with the second index is superior... According to This process, until the last index entry, if all indexes are all the same, then two nodes have the same priority. To illustrate with an example of actual constraints: the user wants to find the path with the smallest total metric (metric) and the smallest number of hops (number of hops), then the first index is the metric, and the second index is the number of hops. When a path with the same metric appears, Then select the path with the smallest number of hops. If the metric and the number of hops are equal, the two nodes have the same priority.

Under the situation of multiple constraints, as shown in Figure 2, the shortest path search method in the specific embodiment of the present invention, the steps are as follows:

Step 210, obtain multiple index values from this node to all neighbor nodes through SPF calculation;

The multiple index values of the present node may all be set to 0.

Step 220: Compare the corresponding index values of each node according to the order of the index according to various constraint conditions, obtain the node with the shortest path connected to this node, and establish a connection between the two points.

When making comparisons, the constraints of the first index are given priority, descending in order.

The constraints include the smallest metric, the largest percentage of available link bandwidth, or the smallest number of hops.

The node with the shortest path connected to this node is a node with multiple index priority.

If there are multiple nodes with the same index priority, establish connections between all the nodes with the same index priority and this node.

A shortest path search device under multi-constraint conditions in an automatic switched optical network, including an index unit and a comparison unit, wherein,

The index unit is used to calculate and store index values of all nodes in the network through SPF;

The comparison unit is used to compare the corresponding index values of each node in the index unit according to various constraints;

Multiple index values from this node to all neighbor nodes are obtained through the index unit, and the comparison unit compares the corresponding index values of each node in the index unit according to the index order according to various constraints, and obtains Nodes are connected by the nodes of the shortest path, establishing a connection between two points.

When the comparing unit performs the comparison, the constraint condition of the first index is set as the priority, and the constraints are decremented successively.

In the specific embodiment of the present invention, according to the search method of multi-index, when performing multi-constraint routing calculation, the shortest path tree is generated according to the multi-index, and the specific implementation steps are as follows:

Step 1: Add this node to the shortest path tree. The multi-index value is 0, and the next hop is itself. This node is the root node of the SPF tree.

Step 2: Obtain the next hop node, find the neighbor nodes of all nodes in the shortest path tree, calculate the multi-index value from the root node to all neighbor nodes, and take the multi-index priority node and link according to the multi-index comparison method , add nodes and links to the shortest path tree; if there are paths with the same priority in multiple indexes, add nodes and links with the same priority to the shortest path tree.

Step 3: Repeat step 2 until all nodes in the network topology are in the shortest path tree.

The present invention will be further described below in conjunction with specific examples.

First concrete instance,

As shown in FIG. 3 , when obtaining the path with the largest metric and link bandwidth percentage, the calculation process of the shortest path search method is adopted.

First: Add node A to the shortest path tree, A is the root node, the next hop is A, the metric is 0, the percentage of available link bandwidth is 0, identified as, and recorded as {A.A.(0,0)}, where The first digit represents the current node, the second digit represents the next hop node, and the third digit represents the metric value and link bandwidth percentage from the current node to the root node.

Get the adjacent nodes of node A, including B, C, and E. According to the multi-index rule, the multi-index value from B, C to A is (1, 10%), and the multi-index value from E to A is (3, 15%) %), according to the multi-index comparison rule, add B and C to the shortest path tree, and the result is {A.A.(0, 0)}, {B.A.(1, 10%)}, {C.A.(1, 10%) }.

Execute the SPF calculation again to find the neighbor nodes of A, B, and C. There are nodes D and E, where the multi-index values are respectively, D passes through B to A (3, 20%), E passes through C to A (3, 10%) ), E goes directly to A (3, 15%), according to the multi-index comparison rule, then D is added to the shortest path tree from B to A, and the result is {A.A.(0, 0)}, {B.A.(1, 10 %)}, {C.A. (1, 10%)}, {D.A. (3, 20%)}.

Then, execute the SPF calculation again to find the neighbor nodes of A, B, C, and D, and there is an E node, where the multi-index values are respectively, E passes through D to A (4, 20%), E passes through C to A (3, 20%), E goes directly to A (3, 15%), according to the multi-index comparison rule, then E is added to the shortest path tree from C to A, and the result is {A.A.(0, 0)}, {B.A.(1 , 10%)}, {C.A. (1, 10%)}, {D.A. (2, 20%)}, {E.A. (3, 20%)}.

All the nodes are in the shortest path tree, the calculation is completed, and the results refer to Figure 3.

The second specific example,

As shown in Figure 4, when obtaining the path with the smallest metric and hop number, the calculation process of the shortest path search method is adopted.

First: Add node A to the shortest path tree, A is the root node, the next hop is A, the metric is 0, the number of hops is 0, the identification is, and the record is {A.A.(0, 0)}, where the first Represents the current node, the second digit represents the next hop node, and the third digit represents the metric value and hop number from the current node to the root node.

Get the adjacent nodes of node A, including B, C, and E. According to the multi-index rule, the multi-index value from B, C to A is (1, 1), and the multi-index value from E to A is (3, 1) , according to the multi-index comparison rule, add B and C to the shortest path tree, and the result is {A.A.(0, 0)}, {B.A.(1, 1)}, {C.A.(1, 1)}.

Execute the SPF calculation again to find the neighbor nodes of A, B, and C. There are nodes D and E, where the multi-index values are respectively, D passes through B to A(3,2), E passes through C to A(3,2), E directly to A (3, 1), according to the multi-index comparison rule, then add E directly to A into the shortest path tree, the result is {A.A.(0, 0)}, {B.A.(1, 1)}, { C.A.(1,1)}, {E.A.(3,1)}.

Then, execute the SPF calculation again to find the neighbor nodes of A, B, C, and E, and there is D node, where the multi-index values are respectively, D passes C to A(3,2), D passes E to A(4,2 ), according to the multi-index comparison rule, add D to A through C into the shortest path tree, and the result is {A.A.(0, 0)}, {B.A.(1, 1)}, {C.A.(1, 1)} , {E.A.(3, 1)}, {D.A.(3, 2)}.

All the nodes are in the shortest path tree, the calculation is completed, and the results refer to Figure 4.

The above is only a preferred embodiment of the present invention, but the scope of protection of the present invention is not limited thereto. Any person familiar with the technology can easily think of changes or replacements within the technical scope disclosed in the present invention. , should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be determined by the protection scope of the claims.

Claims (8)

1, shortest path searching device under the multi-constraint condition in a kind of ASON is characterized in that, comprises indexing units, comparing unit, wherein,

Described indexing units is used for calculating a plurality of index values of this node to all neighbor nodes of this node by SPF SPF, and the index value of all nodes in the storage networking;

Described comparing unit is used for according to multiple constraints the order of the corresponding index value of each node of described indexing units according to index being compared successively, and the node of the shortest path that obtains linking to each other with this node is set up the connection between 2.

2, device as claimed in claim 1 is characterized in that, described comparing unit is made as the constraints of first index preferentially when comparing, and successively decreases successively.

3, device as claimed in claim 1 is characterized in that, described comparing unit when comparing, if a plurality of index in order successively relatively after, have the node of equal priority, then with the node of equal priority all as current shortest path.

4, device as claimed in claim 1 is characterized in that, the described node that links to each other shortest path with this node is the preferential nodes of a plurality of index.

5, shortest path searching method under the multi-constraint condition in a kind of ASON is characterized in that, may further comprise the steps:

A, calculate a plurality of index values of this node to all neighbor nodes of this node by SPF SPF;

B, according to multiple constraints the order of the corresponding index value of each node according to index compared successively, the node of the shortest path that obtains linking to each other with this node is set up the connection between 2.

6, method as claimed in claim 5 is characterized in that, among the described step b, when comparing, the constraints of first index is made as preferentially, successively decreases successively.

7, method as claimed in claim 5 is characterized in that, among the described step b, if a plurality of index in order successively relatively after, have the node of equal priority, then with the node of equal priority all as current shortest path.

8, method as claimed in claim 5 is characterized in that, among the described step b, the described node that links to each other shortest path with this node is the preferential nodes of a plurality of index.

Images