CN102316390B - The method and device of path computing efficiency under constraints is improved using virtual topology - Google Patents
The method and device of path computing efficiency under constraints is improved using virtual topology Download PDFInfo
- Publication number
- CN102316390B CN102316390B CN201110263390.8A CN201110263390A CN102316390B CN 102316390 B CN102316390 B CN 102316390B CN 201110263390 A CN201110263390 A CN 201110263390A CN 102316390 B CN102316390 B CN 102316390B
- Authority
- CN
- China
- Prior art keywords
- wavelength
- constraint
- route
- link
- cost
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 36
- 238000004891 communication Methods 0.000 claims description 12
- 238000010586 diagram Methods 0.000 description 5
- 238000006243 chemical reaction Methods 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 230000003287 optical effect Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 238000013459 approach Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000001914 filtration Methods 0.000 description 1
- 238000011084 recovery Methods 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/12—Shortest path evaluation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L45/00—Routing or path finding of packets in data switching networks
- H04L45/62—Wavelength based
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
The invention discloses a kind of method and device that path computing efficiency under constraints is improved using virtual topology, methods described includes：The route virtual topology for being adapted to the route restriction condition is generated according to route restriction condition；The minimum route of link cost is selected in the route virtual topology；The Wavelength Assignment virtual topology being route according to selected by the generation of wavelength constraints；The wavelength sequence of wavelength connection Least-cost is selected from the Wavelength Assignment virtual topology.The present invention route virtual topological sum Wavelength Assignment virtual topology by generating, solve the problems, such as that router-level topology result validity is relatively low and Wavelength Assignment process efficiency is not high, improve the hit rate of router-level topology and the efficiency of wavelength assignment, it is ensured that the agility of path computing.
Description
Technical Field
The invention relates to the field of optical communication, in particular to a method and a device for improving path calculation efficiency under constraint conditions by using virtual topology.
Background
At present, a common way for calculating a path in an ASON (automatic Switched Optical Network) system is to divide the whole path calculation into: r (Routing, route calculation), WA (Wavelength Assignment). Where route calculation is the selection of an appropriate route and wavelength assignment is the assignment of an available wavelength for that route.
Various constraints are often required to be satisfied in path computation. The constraint conditions of the routing calculation in the prior art mainly include: through a node or link; avoiding a node or link; shared risk link group separation; separating from the designated node or link (the above constraint conditions support must constraint and try-to-do constraint, wherein the must constraint means fails when not satisfied, and the try-to-do constraint means can give up the constraint when not satisfied to guarantee the success of calculation); link hop count first, cost first, etc. The constraints of wavelength allocation are mainly: certain wavelength is not used or necessary, certain wavelength is multiplexed, a designated relay is used, and the like.
In the prior art, route calculation usually includes determining and selecting whether a path result satisfies a constraint after the path result is calculated. The traditional constraint as much as possible is processed by using a gradual release constraint mode, for example, for a constraint condition which passes through a specified node or link as much as possible, a route is calculated according to necessary constraint, and if the calculation fails, the constraint is abandoned for calculation to obtain a final result. This approach makes the route calculation process very blind, and for many cases of best constraints, multiple attempts to release the constraints can slow the route calculation process.
In wavelength allocation, the existing process is to select a wavelength according to specific constraints after calculating all available wavelengths. This separate processing of the wavelength calculation and selection process greatly affects the efficiency of the wavelength assignment process.
Disclosure of Invention
The invention aims to provide a method and a device for improving path calculation efficiency under constraint conditions by using virtual topology, which can better solve the problems of low validity of a route calculation result and low efficiency of a wavelength allocation process.
According to an aspect of the present invention, there is provided a method for improving path computation efficiency under constraint conditions by using a virtual topology, the method comprising:
generating a routing virtual topology suitable for the routing constraint condition according to the routing constraint condition;
selecting a route with the minimum link cost in the route virtual topology;
generating a wavelength allocation virtual topology of the selected route according to the wavelength constraint condition;
and selecting the wavelength sequence with the minimum wavelength connection cost from the wavelength allocation virtual topology.
Wherein,
the routing constraint conditions comprise must-avoid constraint, contain constraint as much as possible and exclude constraint as much as possible;
the wavelength constraint conditions comprise multiplexing wavelength constraint, certain wavelength constraint, wavelength constraint as much as possible and wavelength constraint as little as possible.
The step of generating the routing virtual topology comprises the following steps:
and removing the necessary-avoiding nodes and the necessary-avoiding links in the necessary-avoiding constraint condition from the acquired network topology, wherein when the necessary-avoiding nodes are removed, the links connected with the necessary-avoiding nodes are removed simultaneously.
Wherein, the step of generating the route virtual topology further comprises:
in the network topology with the removed must avoid nodes and must avoid links, reducing the link cost of the links as much as possible in the try to include constraint, and reducing the link cost of the links connected with the try to include nodes in the try to include constraint;
in the network topology with the must-avoid node and the must-avoid link removed, the link cost of the link which is as much as possible excluded in the try-to-exclude constraint is increased, and the link cost of the link which is connected with the try-to-exclude node in the try-to-exclude constraint is increased.
Wherein the step of generating a wavelength allocation virtual topology comprises:
setting the state of the multiplexing wavelength in the multiplexing wavelength constraint to be available in the route with the minimum link cost;
in the route with the minimum link cost, setting the states of the rest wavelengths except the certain wavelength in the certain wavelength constraint as unavailable;
and in the route with the minimum link cost, setting the state of the certain unused wavelength in the certain unused wavelength constraint as unavailable.
Wherein the step of generating a wavelength allocation virtual topology further comprises:
reducing wavelength connection cost related to the best-effort wavelength in the best-effort wavelength constraint in the selected route with the minimum link cost;
and in the route with the minimum link cost, increasing the wavelength connection cost related to the less-used wavelength in the less-used wavelength constraint.
Wherein the step of determining the sequence of wavelengths comprises:
and in the wavelength allocation virtual topology, selecting each wavelength with the minimum sum of wavelength connection costs in each node in the wavelength allocation virtual topology as a wavelength sequence.
According to another aspect of the present invention, there is provided an apparatus for improving path computation efficiency under constraint conditions by using a virtual topology, the apparatus comprising:
the route virtual topology generation module is used for generating a route virtual topology suitable for the route constraint condition according to the route constraint condition;
a route determining module, configured to select a route with the smallest link cost from the route virtual topology;
the wavelength distribution virtual topology generation module is used for generating the wavelength distribution virtual topology of the selected route according to the wavelength constraint condition;
and the wavelength sequence determining module is used for selecting the wavelength sequence with the minimum wavelength communication cost from the wavelength distribution virtual topology.
Wherein the routing virtual topology generation module comprises,
a removing unit, configured to remove a must-avoid node and a must-avoid link in the must-avoid constraint condition from the acquired network topology, wherein when the must-avoid node is removed, a link connected to the must-avoid node is removed at the same time;
a link cost reduction unit, configured to reduce, in a network topology in which a must-avoid node and a must-avoid link are removed, a link cost of a link included as much as possible in the try-to-include constraint, and a link cost of a link connected to the try-to-include node in the try-to-include constraint;
and an increase link cost unit, configured to increase, in a network topology in which the must-avoid node and the must-avoid link are removed, a link cost of a link that is as much as possible excluded from the try-to-exclude constraint, and a link cost of a link connected to the try-to-exclude node from the try-to-exclude constraint.
Wherein the wavelength allocation virtual topology generation module comprises:
a state setting unit, configured to set, in a route with a minimum link cost, a state of a multiplexing wavelength in the multiplexing wavelength constraint as available, set states of other wavelengths except a certain wavelength in the certain wavelength constraint as unavailable, and set a state of a certain unused wavelength in the certain unused wavelength constraint as unavailable;
a wavelength reduction cost unit, configured to reduce a wavelength connectivity cost associated with a best-effort wavelength in the best-effort wavelength constraint in a route with a smallest selected link cost;
and the wavelength cost increasing unit is used for increasing the wavelength connection cost related to the least used wavelength in the least used wavelength constraint in the selected route with the smallest link cost.
Compared with the prior art, the invention has the beneficial effects that: in the path calculation, the routing result meeting the preset constraint condition can be calculated quickly and effectively, the hit rate of the routing calculation and the efficiency of wavelength assignment are improved, and the quickness of the path calculation is ensured.
Drawings
Fig. 1 is a flowchart of a method for improving path computation efficiency under constraint conditions by using virtual topology according to an embodiment of the present invention;
fig. 2 is a flowchart of a process of generating a routing virtual topology according to an embodiment of the present invention;
FIG. 2a is a diagram illustrating an original inter-node link topology according to an embodiment of the present invention;
fig. 2b is a schematic diagram of a routing virtual topology provided by the embodiment of the present invention;
fig. 3 is a flowchart of a wavelength allocation virtual topology generation process provided by an embodiment of the present invention;
FIG. 3a is a schematic diagram of an original intra-node wavelength connectivity topology provided by an embodiment of the present invention;
FIG. 3b is a schematic diagram of a wavelength allocation virtual topology according to an embodiment of the present invention;
fig. 4 is a schematic structural diagram of an apparatus for improving path computation efficiency under constraint conditions by using virtual topology according to an embodiment of the present invention.
Detailed Description
The preferred embodiments of the present invention will be described in detail below with reference to the accompanying drawings, and it should be understood that the preferred embodiments described below are only for the purpose of illustrating and explaining the present invention, and are not to be construed as limiting the present invention.
Fig. 1 is a flowchart of a method for improving path computation efficiency under constraint conditions by using virtual topology according to an embodiment of the present invention, and as shown in fig. 1, the method includes the following steps:
step S101, generating a routing virtual topology suitable for the routing constraint condition according to the routing constraint condition;
and obtaining the network topology, cutting and modifying the whole network topology by using the given routing constraint condition, and finishing the routing calculation process on the modified topology.
Step S102, selecting a route with the minimum link cost in the route virtual topology;
step S103, generating a wavelength allocation virtual topology of the selected route according to the wavelength constraint condition;
and generating topology aiming at the wavelength allocation process according to the routing result and the wavelength constraint, so that the result meeting the constraint condition can be obtained only through the wavelength calculation process.
And step S104, selecting a wavelength sequence with the minimum wavelength communication cost from the wavelength distribution virtual topology.
The wavelength allocation principle is a minimum cost principle, wherein the minimum cost means that the sum of wavelength connection costs in the selected routing node is minimum. The wavelength allocation virtual topology only comprises resource information of nodes in the route with the minimum determined link cost in the route virtual topology, and the application of the constraint is completed by changing the wavelength state and the communication cost in the topology.
Fig. 2 is a flowchart of a process for generating a routing virtual topology according to an embodiment of the present invention, and as shown in fig. 2, the process for generating the routing virtual topology includes the following steps:
step S201, checking whether constraint conditions have conflicting constraint;
the constraint conditions of the routing calculation mainly include passing through a certain node or link, avoiding the certain node or link, namely avoiding the constraint, separating a shared risk link group, separating the node or link from a specified node or link, prioritizing link hop number, prioritizing cost, including the constraint as much as possible, excluding the constraint as much as possible and the like.
There may be conflicts in constraints in the routing virtual topology. Such as a node or link that is set to both have to pass constraints and have to avoid constraints. If a conflict exists in the constraint conditions, the flow is ended, otherwise, step S202 is executed.
For example, the obtained network topology is as shown in fig. 2a, and it is assumed that node a is used as a source node and node C is used as a destination node. Assume that the preset link cost is as follows: the cost of the a-B link is 25, the cost of the a-D link is 15, the cost of the B-C link is 10, the cost of the D-C link is 30, the cost of the a-E link is 10, the cost of the B-E link is 5, the cost of the C-E link is 9, and the cost of the D-E link is 10. Assume that the set constraints are: links a-D must be avoided, excluding node E as much as possible. If the constraint conditions are checked to be not in conflict, step S202 is executed.
Step S202, filtering out nodes and links in the inevitable constraints from the topology;
removing nodes and links in the must-avoid constraint from the routing virtual topology, wherein the removal of nodes comprises removal of links connected to the nodes. For example, in fig. 2a, the links that must be avoided in the set constraints are a-D, so the a-D links are removed from fig. 2a, and the removed routing virtual topology is shown in fig. 2 b.
Step S203, link cost of related links in constraint is reduced as much as possible;
in the network topology with the avoidance nodes and the avoidance links removed, the cost of the links as much as possible is reduced, and the cost of the links connected with the avoidance nodes as much as possible is reduced. According to the formula dnew＝dminthe/N adjusts the link cost, where dnewTo reduce the link cost, dminFor the minimum link cost in the current topology, N is the number of nodes in the topology. Therefore, the nodes or links contained as much as possible can be preferentially selected, and a plurality of constraints contained as much as possible can be simultaneously met.
In fig. 2b, the preset constraint conditions do not include as many constraints as possible, and no processing is performed here.
Step S204, link cost of related links in the constraint is increased to be excluded as much as possible.
In a network topology in which the must-avoid node and the must-avoid link are removed, the cost of excluding the link as much as possible increases, and the cost of excluding the link connected to the node as much as possible increases. According to the formula dnew＝dold+dmaxN, wherein dnewFor enlarged chainsRoad cost, doldAs an initial cost of the link, dmaxAnd N is the maximum link cost in the current topology, and is the number of nodes in the topology. This ensures that nodes or links that are as exclusive as possible are always selected last.
For example, in FIG. 2b, the most exclusive node in the constraint is E, so the cost of the link A-E, B-E, C-E, D-E connected to node E is according to formula dnew＝dold+dmaxIncreasing by N, where N is 5, dmaxIs 30, dold10, 5, 10, 9, respectively, calculated dnew160, 155, 160, 159 respectively.
At this point, a routing virtual topology has been generated, as shown in FIG. 2 b. And the next step is to calculate the path on the generated route virtual topology to determine the proper route, and the route result meeting the constraint is the route result with the minimum link cost. In fig. 2B, the cost of each link is shown in table 1, and the route with the smallest link cost is a-B-C.
| Serial number | Available routing | Link cost |
| 1 | A-B-C | 35 |
| 2 | A-E-C | 320 |
| 3 | A-E-B-C | 325 |
| 4 | A-B-E-C | 340 |
| 5 | A-E-D-C | 349 |
| 6 | A-B-E-D-C | 369 |
TABLE 1
Fig. 3 is a flowchart of a wavelength allocation virtual topology generation process provided in an embodiment of the present invention, and as shown in fig. 3, the process includes the following steps:
in step S301, whether or not there is a conflicting constraint is checked.
The constraints of wavelength allocation are mainly: multiplexing wavelength constraints, certain no wavelength constraints, wavelength constraints as much as possible, and wavelength constraints as little as possible. And when the wavelength constraint conditions conflict, directly ending the process, otherwise, executing the step S302.
For example, in fig. 3a, the wavelength resource information of the node A, B, C and the wavelength constraint are obtained. Hypothesis obtainThe obtained wavelength resource information comprises lambda of the node A entering direction1、λ2、λ3、λ4λ of node A out direction1、λ2、λ3λ of node-B in the direction of node-B entry1、λ3、λ4λ of node B outgoing direction1、λ2、λ3、λ4λ of C node in the incoming direction1、λ4λ of C node out direction1、λ2、λ4. Assuming the constraints are as follows: the source node A incoming direction uses the wavelength lambda as much as possible3The outgoing direction of the source node A must not use the wavelength lambda4The destination node C must not use the wavelength lambda in the incoming direction2The wavelength lambda is used as much as possible in the outgoing direction of the destination node C1. Checking that the wavelength constraint condition does not find a conflict, executing step S302.
Step S302, the state of the multiplexing wavelength constraint is set to be available.
Multiplexing refers to changing a wavelength that is originally in an unavailable state to be available. The specific scenarios in which this occurs are: when a connection fails, the connection is recovered, and before the recovery is successful, the wavelength resources occupied by the connection are not released, that is, are not available, so that when the path calculation for recovering the connection is performed, in order to avoid the failure of the path calculation due to the absence of the available wavelength, the states of the wavelength resources need to be set to be available states.
There is no wavelength multiplexed in fig. 3a, and no arrangement here.
Step S303, the remaining wavelengths except the certain wavelength constraint are set as unavailable.
The constraint status of all other wavelengths than the mandatory wavelength constraint is set as unavailable.
In fig. 3a, no wavelength is necessarily used, and is not provided here.
Step S304, the state of the certain unused wavelength is set as unavailable.
For example, in FIG. 3a, the constraint is that the source node A must not be pointed out at the wavelength λ4The destination node C must not use the wavelength lambda in the incoming direction2Thus, the wavelength λ of the outgoing direction of the source node A4Set as unusable, wavelength lambda of destination node C in direction2Is set as unavailable.
Step S305, constructing a wavelength distribution virtual topology and initializing a connection cost.
And constructing a wavelength allocation virtual topology in the node according to the current resource state, and initializing wavelength connection cost in the wavelength allocation virtual topology. Wherein the cost of wavelength conversion is greater than the cost of wavelength straight-through.
For example, in fig. 3a, the virtual topology of wavelength allocation inside the node A, B, C is constructed according to the current resource state, and the connection cost of the wavelength direct connection is initialized to 3, and the connection cost of the wavelength conversion is 4. Wherein, the resource status is the status of the wavelength, such as the wavelength is available or unavailable.
And step S306, reducing the communication cost of the wavelength used as much as possible in the node.
The communication cost associated with trying to use wavelength is reduced. According to the formula dnew＝dminN to perform wavelength connection cost adjustment, wherein dnewTo reduce the wavelength connection cost, dminFor the minimum wavelength connectivity cost in the topology, N allocates the number of routing nodes in the virtual topology to the wavelength.
For example, in FIG. 3a, the constraint is that the ingress direction of the source node A uses the wavelength λ as much as possible3The wavelength lambda is used as much as possible in the outgoing direction of the destination node C1. Will enter the direction wavelength lambda with the source node A3Correlation of communication cost and direction lambda of destination node C1The related connection cost is according to the formula dnew＝dminthe/N is reduced. Wherein the wavelength λ of the incoming direction of the source node A3The associated connection cost of (A) is the wavelength λ in the A direction3Wavelength λ in A-out direction3The wavelength λ of the destination node C in the direction1In (2) correlation ofThe communication penalty is the wavelength λ in the C-in direction1Wavelength λ in the direction of C1. The reduced wavelength connection costs calculated according to the formula are 1, respectively, wherein dminIs 3, and N is 3.
And step S307, increasing the communication cost of the wavelength which is as unnecessary as possible in the node.
The connection cost associated with trying to eliminate wavelengths increases. According to the formula dnew＝dold+dmaxN, where dnewFor increased wavelength connectivity cost, doldInitial cost of connectivity for a wavelength, dmaxAnd allocating the maximum wavelength connectivity cost in the virtual topology to the wavelength, and allocating the number of routing nodes in the virtual topology to the wavelength by N.
In fig. 3b, if the wavelength is not used as much as possible, the cost of connectivity is not increased.
To this end, a wavelength allocation virtual topology has been generated, as shown in fig. 3 b. The available wavelength sequences were calculated on the topology of fig. 3b, and the results are shown in table 2. The smallest of these is the wavelength assignment that satisfies the constraint, i.e., λ3-λ3-λ1-λ1。
| Serial number | Sequence of usable wavelengths | Connected cost |
| 1 | Λ1-λ1-λ1-λ1 | 7 |
| 2 | Λ3-λ3-λ1-λ1 | 6 |
| 3 | Λ4-λ3-λ1-λ1 | 9 |
TABLE 2
Fig. 4 is a device for improving path computation efficiency under constraint conditions by using virtual topology according to an embodiment of the present invention, where the device includes: the device comprises a route virtual topology generation module, a route determination module, a wavelength distribution virtual topology generation module and a wavelength sequence determination module. The route virtual topology generation module comprises a removal unit, a link cost reduction unit and a link cost increase unit; the wavelength allocation virtual topology generation module comprises: the device comprises a state setting unit, a wavelength cost reducing unit and a wavelength cost increasing unit.
And the route virtual topology generation module is used for generating a route virtual topology suitable for the route constraint condition according to the route constraint condition. The removing unit is used for removing the inevitable nodes and inevitable links in the inevitable constraints from the acquired network topology, and removing the links connected with the inevitable nodes when removing the inevitable nodes; a link cost reduction unit, configured to reduce, in a network topology in which a must-avoid node and a must-avoid link are removed, a link cost of a link included as much as possible in the try-to-include constraint, and a link cost of a link connected to the try-to-include node in the try-to-include constraint; and an increase link cost unit, configured to increase, in a network topology in which the must-avoid node and the must-avoid link are removed, a link cost of a link that is as much as possible excluded from the try-to-exclude constraint, and a link cost of a link connected to the try-to-exclude node from the try-to-exclude constraint.
And the route determining module is used for selecting the route with the minimum link cost in the route virtual topology.
And the wavelength allocation virtual topology generation module is used for generating the wavelength allocation virtual topology of the selected route according to the wavelength constraint condition. The state setting unit is configured to set, in a route with the minimum link cost, a state of a multiplexing wavelength in the multiplexing wavelength constraint as available, set states of other wavelengths except a certain used wavelength in the certain used wavelength constraint as unavailable, and set a state of a certain unused wavelength in the certain unused wavelength constraint as unavailable; a wavelength reduction cost unit, configured to reduce a wavelength connectivity cost associated with a best-effort wavelength in the best-effort wavelength constraint in a route with a smallest selected link cost; and the wavelength cost increasing unit is used for increasing the wavelength connection cost related to the least used wavelength in the least used wavelength constraint in the selected route with the smallest link cost.
And the wavelength sequence determination module is used for selecting the wavelength sequence with the minimum wavelength connection cost from the wavelength allocation virtual topology.
In summary, the present invention determines the route with the minimum link cost by generating the route virtual topology, and generates the wavelength allocation virtual topology on the determined route and determines the wavelength path with the minimum wavelength communication cost, so that the route result meeting the predetermined constraint condition can be quickly and effectively calculated in the path calculation, instead of determining and selecting whether the constraint is met after the result is calculated, the problems of low validity of the route calculation result and low efficiency of the wavelength allocation process are solved, the hit rate of the route calculation and the efficiency of wavelength assignment are improved, and the quickness of the path calculation is ensured.
Although the present invention has been described in detail hereinabove, the present invention is not limited thereto, and various modifications can be made by those skilled in the art in light of the principle of the present invention. Thus, modifications made in accordance with the principles of the present invention should be understood to fall within the scope of the present invention.
Claims (10)
1. A method for improving path computation efficiency under constraint conditions by using virtual topology is characterized by comprising the following steps:
generating a routing virtual topology suitable for the routing constraint condition according to the routing constraint condition;
selecting a route with the minimum link cost in the route virtual topology;
generating a wavelength allocation virtual topology of the selected route according to the wavelength constraint condition;
selecting a wavelength sequence with the minimum wavelength communication cost from the wavelength allocation virtual topology;
the step of generating a wavelength allocation virtual topology comprises: the state of the multiplexed wavelength in the multiplexed wavelength constraint is made available in the route with the lowest link cost selected.
2. The method of claim 1,
the routing constraint conditions comprise must-avoid constraint, contain constraint as much as possible and exclude constraint as much as possible;
the wavelength constraint conditions comprise multiplexing wavelength constraint, certain wavelength constraint, wavelength constraint as much as possible and wavelength constraint as little as possible.
3. The method of claim 2, wherein the step of generating a routing virtual topology comprises:
and removing the necessary-avoiding nodes and the necessary-avoiding links in the necessary-avoiding constraint condition from the acquired network topology, wherein when the necessary-avoiding nodes are removed, the links connected with the necessary-avoiding nodes are removed simultaneously.
4. The method of claim 3, wherein the step of generating a routing virtual topology further comprises:
in the network topology with the removed must avoid nodes and must avoid links, reducing the link cost of the links as much as possible in the try to include constraint, and reducing the link cost of the links connected with the try to include nodes in the try to include constraint;
in the network topology with the must-avoid node and the must-avoid link removed, the link cost of the link which is as much as possible excluded in the try-to-exclude constraint is increased, and the link cost of the link which is connected with the try-to-exclude node in the try-to-exclude constraint is increased.
5. The method according to any of claims 2-4, wherein the step of generating a wavelength allocation virtual topology further comprises:
in the route with the minimum link cost, setting the states of the rest wavelengths except the certain wavelength in the certain wavelength constraint as unavailable;
and in the route with the minimum link cost, setting the state of the certain unused wavelength in the certain unused wavelength constraint as unavailable.
6. The method of claim 5, wherein the step of generating a wavelength allocation virtual topology further comprises:
reducing wavelength connection cost related to the best-effort wavelength in the best-effort wavelength constraint in the selected route with the minimum link cost;
and in the route with the minimum link cost, increasing the wavelength connection cost related to the less-used wavelength in the less-used wavelength constraint.
7. The method of claim 6, wherein the step of determining the sequence of wavelengths comprises:
and in the wavelength allocation virtual topology, selecting each wavelength with the minimum sum of wavelength connection costs in each node in the wavelength allocation virtual topology as a wavelength sequence.
8. An apparatus for improving path computation efficiency under constraint conditions using virtual topology, the apparatus comprising:
the route virtual topology generation module is used for generating a route virtual topology suitable for the route constraint condition according to the route constraint condition;
a route determining module, configured to select a route with the smallest link cost from the route virtual topology;
the wavelength distribution virtual topology generation module is used for generating the wavelength distribution virtual topology of the selected route according to the wavelength constraint condition;
the wavelength sequence determination module is used for selecting a wavelength sequence with the minimum wavelength communication cost from the wavelength distribution virtual topology;
wherein the step of generating a wavelength allocation virtual topology comprises: the state of the multiplexed wavelength in the multiplexed wavelength constraint is made available in the route with the lowest link cost selected.
9. The apparatus of claim 8, wherein the routing virtual topology generation module comprises,
a removing unit, configured to remove a must-avoid node and a must-avoid link in a must-avoid constraint condition from the acquired network topology, wherein when the must-avoid node is removed, a link connected to the must-avoid node is removed at the same time;
a link cost reduction unit, configured to reduce, in a network topology in which the must-avoid node and the must-avoid link are removed, a link cost of a link included as much as possible in a constraint included as much as possible, and a link cost of a link connected to the node included as much as possible in the constraint included as much as possible;
and an increase link cost unit, configured to increase, in a network topology in which the must-avoid node and the must-avoid link are removed, a link cost of a link that is as much as possible exclusive in the try-to-exclude constraint and a link cost of a link connected to the try-to-exclude node in the try-to-exclude constraint.
10. The apparatus of claim 9, wherein the wavelength assignment virtual topology generation module comprises:
a state setting unit, configured to set, in a route with the minimum link cost, a state of a multiplexing wavelength in the multiplexing wavelength constraint as available, set states of other wavelengths except a certain wavelength in the certain wavelength constraint as unavailable, and set a state of a certain unused wavelength in the certain unused wavelength constraint as unavailable;
a wavelength reduction cost unit, configured to reduce a wavelength connection cost associated with the best-effort wavelength in the best-effort wavelength constraint in the route with the smallest selected link cost;
and increasing a wavelength cost unit for increasing the wavelength connection cost related to the least used wavelength in the least used wavelength constraint in the selected route with the least link cost.
Priority Applications (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110263390.8A CN102316390B (en) | 2011-09-07 | 2011-09-07 | The method and device of path computing efficiency under constraints is improved using virtual topology |
| PCT/CN2012/073733 WO2012155720A1 (en) | 2011-09-07 | 2012-04-10 | Method and device for enhancing path computation efficiency under constraint using virtual topology |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201110263390.8A CN102316390B (en) | 2011-09-07 | 2011-09-07 | The method and device of path computing efficiency under constraints is improved using virtual topology |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN102316390A CN102316390A (en) | 2012-01-11 |
| CN102316390B true CN102316390B (en) | 2018-03-02 |
Family
ID=45429148
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201110263390.8A Active CN102316390B (en) | 2011-09-07 | 2011-09-07 | The method and device of path computing efficiency under constraints is improved using virtual topology |
Country Status (2)
| Country | Link |
|---|---|
| CN (1) | CN102316390B (en) |
| WO (1) | WO2012155720A1 (en) |
Families Citing this family (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102316390B (en) * | 2011-09-07 | 2018-03-02 | 中兴通讯股份有限公司 | The method and device of path computing efficiency under constraints is improved using virtual topology |
| CN102893563B (en) * | 2012-07-02 | 2014-12-24 | 华为技术有限公司 | Business route determining method and related device |
| CN104348722B (en) | 2013-07-31 | 2017-12-12 | 华为技术有限公司 | Determine content obtaining path, the methods, devices and systems of request processing |
| EP3059912B1 (en) * | 2013-11-18 | 2017-09-06 | Huawei Technologies Co., Ltd. | Path calculation method and apparatus for ason |
| CN108650163B (en) * | 2018-04-23 | 2020-09-08 | 首都师范大学 | Tunnel connection method and device for hierarchical non-fully connected virtual topology |
| CN110011913B (en) * | 2019-03-20 | 2021-01-26 | 烽火通信科技股份有限公司 | Path calculation method and system |
| CN113014407B (en) * | 2019-12-19 | 2025-03-28 | 中兴通讯股份有限公司 | Business resource analysis method, electronic device and storage medium |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1303160A2 (en) * | 2001-07-19 | 2003-04-16 | Innovance Inc. | Wavelength routing and switching mechanism for a photonic transport network |
| CN1863135A (en) * | 2005-05-12 | 2006-11-15 | 中兴通讯股份有限公司 | Path selecting method of regulating link cost |
| CN101640817A (en) * | 2009-09-02 | 2010-02-03 | 中兴通讯股份有限公司 | Method and device for route finding and wavelength assignment in optical network |
| CN101998187A (en) * | 2009-08-18 | 2011-03-30 | 株式会社日立制作所 | Information communication device and information communication method |
| CN102158417A (en) * | 2011-05-19 | 2011-08-17 | 北京邮电大学 | Method and device for optimizing multi-constraint quality of service (QoS) routing selection |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN100472996C (en) * | 2003-03-07 | 2009-03-25 | 中兴通讯股份有限公司 | Device and method for realizing dynamic channel power balance control of optical network nodes |
| US8665749B2 (en) * | 2008-02-04 | 2014-03-04 | Zte Corporation | Method and apparatus for realizing source routing in a blocking cross network |
| CN102316390B (en) * | 2011-09-07 | 2018-03-02 | 中兴通讯股份有限公司 | The method and device of path computing efficiency under constraints is improved using virtual topology |
-
2011
- 2011-09-07 CN CN201110263390.8A patent/CN102316390B/en active Active
-
2012
- 2012-04-10 WO PCT/CN2012/073733 patent/WO2012155720A1/en active Application Filing
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1303160A2 (en) * | 2001-07-19 | 2003-04-16 | Innovance Inc. | Wavelength routing and switching mechanism for a photonic transport network |
| CN1863135A (en) * | 2005-05-12 | 2006-11-15 | 中兴通讯股份有限公司 | Path selecting method of regulating link cost |
| CN101998187A (en) * | 2009-08-18 | 2011-03-30 | 株式会社日立制作所 | Information communication device and information communication method |
| CN101640817A (en) * | 2009-09-02 | 2010-02-03 | 中兴通讯股份有限公司 | Method and device for route finding and wavelength assignment in optical network |
| CN102158417A (en) * | 2011-05-19 | 2011-08-17 | 北京邮电大学 | Method and device for optimizing multi-constraint quality of service (QoS) routing selection |
Also Published As
| Publication number | Publication date |
|---|---|
| CN102316390A (en) | 2012-01-11 |
| WO2012155720A1 (en) | 2012-11-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN102316390B (en) | The method and device of path computing efficiency under constraints is improved using virtual topology | |
| JP7088368B2 (en) | Multilayer network system | |
| EP1473887A2 (en) | Protection scheme for a communications network under multiple failures | |
| EP2453607A1 (en) | Method and device for calculating k-shortest paths | |
| JP7062956B2 (en) | Optical network controller and optical node device | |
| CN103797738A (en) | Allocation of spectral capacity in a wavelength-division multiplexing optical network | |
| Kosaka et al. | Shared protected elastic optical path network design that applies iterative re-optimization based on resource utilization efficiency measures | |
| WO2012019404A1 (en) | Path calculating method and device | |
| CN113193996B (en) | Power optical transmission network optimization method, device, equipment and storage medium | |
| CN103391258B (en) | Resource distribution method and device based on distributed fragment concentration ratios | |
| CN115103245B (en) | Optical network fault analysis method and device | |
| JP6264747B2 (en) | Network design apparatus and network design method | |
| CN110062301B (en) | Routing method, apparatus, device and storage medium | |
| US10447399B2 (en) | Method and system for restoring optical layer service | |
| CN112995797A (en) | OTN service management method, device, network equipment and readable storage medium | |
| CN107248952B (en) | Method and system for determining service alternative route | |
| EP3043521A1 (en) | Method and device for sending crossover command | |
| CN109428813B (en) | Rerouting method, rerouting device and storage medium | |
| JP5904892B2 (en) | A method for energy efficient reoptimization of optical networks | |
| Duran et al. | Advantages of using cognition when solving impairment-aware virtual topology design problems | |
| CN101711002B (en) | Wavelength routing method and system based on wavelength division multiplexing optical network | |
| Terada et al. | Residual capacity aware dynamic control of GRE-based routing optical path networks under traffic growth model | |
| CN111093120B (en) | Routing planning method and system for service group | |
| US20060159022A1 (en) | Routing method | |
| Fujii et al. | Path division method for fairness in dynamic elastic optical path networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |