JP2005260729A - Bandwidth guaranteed optical VPN path design system, method and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently design a path in a band capable of guaranteeing the quality of a network service provided by a network operator.
In an optical VPN path setting device, a storage processing unit adds a link bandwidth and a required bandwidth as new constraints as constraints such as wavelength, cost, and distance in an optical network. The data processing unit 17 obtains an initial solution, obtains a local optimum solution from the allowable solution space based on the initial solution, and further obtains a suboptimal solution therefrom. To do.
[Selection] Figure 1

Description

  The present invention relates to a technology for efficiently setting an optical VPN (virtual private network) path in an optical network with a wavelength as a label, and in particular, in providing a bandwidth-guaranteed VPN service in an optical network. The present invention relates to a technique suitable for an operator to efficiently set up a VPN path.

  Currently, optical networks are being used as the network speeds up. However, when routing is performed by converting optical signals to electrical signals during routing, the overhead is large. GMPLS (Generalized MPLS) specifications including optical MPLS (Optical Multi Protocol Label Switching) are being studied as a technology for routing signals, and the wavelength of the optical signal is assigned instead of the MPLS label and the optical signal is routed as it is. Studies are underway for such processing. A normal electrical router uses a header as routing (path selection) information, whereas an MPLS router uses a short fixed-length identification sign called a “label”. In the optical network, the wavelength (λ) is used for this label.

  Hereinafter, an optical MPLS (photonic MPLS) network design technique and an optical MPLS network path (OLSP: Optical Label Switched Path) design technique will be described using the contents described in Non-Patent Document 1. The target network is based on Wavelength Division Multiplexing (WDM).

  As described above, research on MPLS technology in an optical transmission line called GMPLS including optical MPLS or the like is progressing. In MPLS, an identifier “label” is inserted into an IP packet, and an MPLS-compatible router on the IP network that manages the correspondence between the label and the route transfers the packet at a high speed using the label.

  The GMPLS router includes an MPLS router and an optical cross-connect function. This router exchanges IP-based control information with other routers, and based on this, the optical signal is routed on a wavelength basis by the optical cross-connect function. In other words, the “label” portion in MPLS corresponds to “wavelength”, and the router through which the routing is performed performs routing based on the wavelength.

  The path design of this GMPLS network will be described below. The path mentioned here is the connection between the router that is the start point and the router that is the end point. The path design is, for example, the current use of each path when given the network topology and the number of required paths to be set between routers. It is to determine a route and to determine a backup route to be switched when a failure occurs in the working route. The wavelength of each path at that time is also determined simultaneously.

  In this path design, there are specific constraints that must be considered in order to use an optical MPLS router and constraints that are implementation dependent. For example, since optical MPLS routers have both a wavelength switching function and those that do not, a conventional WDM network design technique cannot be applied. Therefore, the existing WDM network design technique cannot be applied as it is. The path design in such an optical MPLS network is performed as follows.

  First, the network topology is modeled by an undirected multiple graph. In addition, distance and cost are given to each link between routers. In the target network, each path has a unique wavelength. Each router routes the route according to its wavelength. In addition, there is a restriction that paths of the same wavelength cannot be accommodated on the same link. However, there are routers that can switch the path wavelength and those that cannot. From the viewpoint of cost and mounting, these are generally mixed in one GMPLS network.

  Accordingly, there may be a case where only one wavelength is given to one path, and there is a case where one path is constituted by a combination of paths of a plurality of wavelengths. In either case, each link cannot accommodate paths of the same wavelength. In the existing path design, only one wavelength is assigned to each path, or the wavelength is switched in all routers.

  However, in the path design in an actual GMPLS network, the case where optical MPLS routers are mixed must be considered.

  In the design of the working path, input information includes "router information (number of routers, upper limit of the number of wavelength switching of each router)", "link information (number of links, link capacity of each link, cost of each link) , Distance of each link) "," path information (router numbers at both ends of the path) "," wavelength information (number of wavelengths that can be used in the entire network) "," failure scenario information (failure pattern (failed router and link Set), scenario weight) "and the like.

Restrictions are: "All links must satisfy the link capacity", "The same path must not overlap on the same link", "The distance of each path must be less than the set length", "Wavelength If there is a router with a switching function, the number of wavelength switching of each router must not exceed the upper limit. "

  As the objective function, set the total cost of the path. This is because the path with the smallest total cost of the path is output from the set of paths that satisfy the constraint conditions. The final output information is the route router and link row of each path, and the wavelength on the via link of each path.

  As for the backup route design, the route is searched as described below. The backup route is a route that is prepared when a failure occurs in the working route (router and link string, and wavelength in the routed link). When a failure occurs, the routing is changed to this route. , It is possible to avoid the failure part.

  When considering this backup route, it is necessary to assume a failure scenario. A failure scenario is a set of routers and links that cannot be used due to simultaneous failures. Regardless of which failure scenario occurs, the backup path of each path is determined for each scenario so that it can be used continuously by switching to the backup path accordingly.

  Restrictions in the protection path design include “one of the working paths is subject to a failure scenario” and “not passing through a location (a set of routers and links) where the protection path has failed”.

  Then, the objective function is set to the total number of backup paths so that the required backup paths are minimized. The final output information is the wavelength on the working path, the backup path for each scenario, and the via link for each path.

  The design problem of the working path is a class of NP difficulty (a problem that is as difficult as, or more difficult than, a problem in which it can be determined in polynomial time whether or not it is a correct answer if an answer is given) Therefore, it is predicted that efficient solving is impossible. When the target network is quite small, it is not impossible to obtain an exact solution using the branch and bound method or the cutting plane method, but it is realistic because the calculation time increases dramatically as the network size increases. Can't be solved in time. Therefore, an approximate solution for outputting the best solution in a realistic time is required.

  As an approximate solution method, there is a method using a random multi-start local search method (Random Multi-start Local Search). In this technique, initial solutions are randomly generated and a local search is applied to each. The best solution among the obtained solutions is output. That is, by limiting the search range, a solution that can be executed in a short time can be obtained. An example of the procedure when the approximate solution is used for path design is as follows.

(1) First, a solution that satisfies the link capacity constraint is searched. Here, the wavelength is not considered, and a path satisfying the side capacity in all links is obtained.
(2) Next, a solution that satisfies the wavelength switching number constraint is searched. That is, based on the path obtained in (1), a path that satisfies the wavelength switching number at all nodes is obtained.

  Based on the above formulation and algorithm, the results of an evaluation experiment using the case where the current route is obtained by the exact solution and the case where the backup route is obtained by the approximate solution are as follows. As the network scale increases, the constraint condition increases exponentially, so the optimal solution may not be obtained in real time. However, in the approximate solution, the solution space (the range in which the solution is searched) is limited. This makes it possible to output a solution in a short time. That is, even in a large-scale network, it is possible to obtain a solution by using an approximate solution method.

  However, including this non-patent document 1, conventionally, there is no disclosed technique for optimizing a VPN path in an optical network while guaranteeing an end-to-end bandwidth.

  As a conventional technique for VPN, for example, there is a technique described in Patent Document 1, but this technique changes a VPN service condition in real time and sets a VPN path configuration. is not.

JP 2003-124986 A Masaki Tokuhisa, Yoshiyuki Chiba, Hiroka Tonami, Shinya Nogami “Path Design in Photonic MPLS Network”, NTT Technology Journal, June 2002, p. 69

  The problem to be solved is that the conventional technology cannot optimize the VPN path in the optical network while guaranteeing the end-to-end bandwidth.

  An object of the present invention is to solve such problems and to set up an optical VPN path efficiently in an optical network labeled with a wavelength, and in particular, to provide a bandwidth-guaranteed optical VPN service in the optical network. It is.

  In order to achieve the above object, in the present invention, as a constraint condition such as a wavelength, cost, and distance in an optical network, a link band and a required band are newly added as a constraint condition, and the design of an optical path is an integer programming problem. Formulate, find the initial solution, find the local optimal solution from the allowable solution space based on the initial solution, and further determine the sub-optimal solution from the local optimal solution. When obtaining a local optimum solution from this initial solution, first, for example, an initial solution that is the shortest path of each path is obtained by the Dijkstra method. However, the initial solution obtained here does not necessarily satisfy all the constraint conditions. Therefore, if there is a link that does not satisfy the constraint conditions in the obtained initial solution, such a link is selected at random, and a certain path passing therethrough is detoured so as to pass through another link. By repeating this, a local optimum solution that satisfies all the constraint conditions is obtained. Then, a path corresponding to the objective (objective function) is further selected from the obtained local optimum solution. As a result, the network operator can efficiently perform path design in a band that can guarantee the quality of the provided network service.

  According to the present invention, it is effective when a network operator operating or planning a VPN business in an optical network implements a bandwidth-guaranteed optical VPN service. That is, at present, SLA (Service Level Agreement), which is a contract that guarantees the user that the network service provider raises an index indicating the service quality and maintains the standard value, has been provided. It can be used as a mechanism to guarantee bandwidth, which is an important premise for protection.

  The best mode for carrying out the present invention will be described below with reference to the drawings.

  FIG. 1 is a block diagram showing a configuration example of an optical VPN path setting apparatus according to the present invention, FIG. 2 is a flowchart showing an example of a processing procedure of an optical VPN path setting method according to the present invention, and FIG. FIG. 4 is an explanatory diagram showing a numerical condition example, FIG. 5 is an explanatory diagram showing a first candidate solution example, and FIG. 6 is a second candidate solution example. It is explanatory drawing shown.

  1 includes a CPU (Central Processing Unit) 11, a memory 12, an input device 13 such as a mouse or a keyboard, an output device 14 such as an LCD or CRT, a program or data according to the present invention. Is a hardware configuration having an external storage device 15 composed of a hard disk or the like, a communication device 16 composed of a LAN (Local Area Network) card or a modem, etc., and a storage such as a CD-ROM via an optical disk drive device After the program and data recorded on the medium are installed in the external storage device 15, the data is read from the external storage device 15 into the memory 12 and processed by the CPU 11, whereby the graphing processing unit 17 a and the constraint condition processing in the data processing unit 17 are performed. Unit 17b, objective function processing unit 17c, optimum calculation processing unit 17d, and storage Graph data storage unit 18a in the processing section 18, the constraint condition storing section 18b, of the objective function storage unit 18c, to perform the functions according to the present invention.

  In the optical VPN path setting apparatus 10 of this example having such a configuration, the graphing processing unit 17a and the constraint condition processing unit 17b allow the “wavelength”, “link bandwidth”, “required bandwidth”, and “cost” in the optical network. In consideration of the “distance” and the like, the optical path design is formulated as an integer programming problem, and the optimal calculation processing unit 17d first obtains a local optimal solution from the allowable solution space based on the initial solution. A path is set by obtaining a sub-optimal solution that satisfies the objective function set by the function processing unit 17c.

  When the optimum calculation processing unit 17d obtains the local optimum solution from the initial solution, for example, first, (1): an initial solution that is the shortest path of each path is obtained by the Dijkstra method. However, the initial solution obtained here does not necessarily satisfy all the constraint conditions. Next, if there is a link that does not satisfy the constraints in the initial solution obtained in (2): (1), such a link is selected at random, and one path that passes through it is passed through another link. Detour. By repeating this, a local optimum solution that satisfies all the constraint conditions is constructed.

  When formulating an optical path design as an integer programming problem, the following constraints are required.

(A) A constraint condition indicating that the input / output balance in each router is balanced and that all paths exist. Here, “i, j: router number”, “k: path number”, “l: wavelength number”, “sk: source router number”, “tk: sink router number”,
(A-1) The following number 1 as a constraint expression when the target router is a source

（Ａ−２）対象ルータがシンクの場合の制約条件式としての下記数２

(A-2) The following number 2 as a constraint expression when the target router is a sink

(Ａ−３)上記以外のルータの場合の制約条件式としての下記数３

(A-3) The following number 3 as a constraint expression in the case of a router other than the above

  (B) The following number 4 as a constraint condition expression that wavelengths do not overlap on the same path and the same link:

  (C) The following number 5 as a constraint condition expression that paths do not overlap on the same wavelength and on the same link:

  (D) The following formula 6 as a constraint condition expression that all links satisfy the link capacity

  (E) The following equation 7 as a constraint condition expression for the length of each path to be equal to or less than the set value D (note that this set value D excludes redundant paths that repeatedly pass through the same route)

  Then, when the optical path design is formulated as an integer programming problem, the cost Cij of the link between routers is considered as an objective function. For example, the following equation 8 is required, and solution candidates satisfying the constraints A to E ( Among the local optimal solutions), a solution (sub-optimal solution) satisfying this objective function is defined.

  Note that the router may be either “source” or “sink” (bidirectional), or may be either one (one direction).

  In the optical VPN path setting apparatus 10 of this example, the graphing processing unit 17a makes the following description in order to treat the optical network as a graph problem.

For routers that make up the network,
“V = {v1, v2,..., Vnv}, total number of routers: nv”
And

For the requested path and its source (s) and sink (t):
"P-{(s1, t1), (s2, t2), ..., (snp, tnp)}, number of paths: np"
And

  The number of wavelengths that can be used is “nw”.

  The capacity in each link is “fij (i, j = 1, 2,..., Nv, i <j).

  The number of bands used in the path k is “Bk (k = 1, 2,..., Np)”.

  The cost for each link is “Cij = 1, 2,..., Nv, i <j”.

  The maximum path distance is “D”.

  The distance between the links is “dij (i, j = 1, 2,..., Nv, i <j)”.

  In addition, in order to make paths and links variable and handle them as mathematical expressions, the following description is made with the starting point number being “i”, the ending point number being “j”, the path number being “k”, and the wavelength number being “l”. .

x [j, i, k, l] ∈ {0, 1} (i, j = 1, 2,..., nv, k = 1, 2,..., np, l = 1, 2,. .., nw) "
When x [j, i, k, l] = 1: With path (k) When x [j, i, k, l] = 0: Without path (k)

  For example, the input device 12 inputs information necessary for setting the optical VPN path, such as the network topology of the optical VPN, the node that establishes the optical VPN path, and the required bandwidth, and the graph data storage unit in the storage processing unit 18 The information is stored in the external storage device 15 or the like by the 18a, the constraint condition storage unit 18b, and the objective function storage unit 18c.

  Using various information stored in the external storage device 15 or the like in this manner, the data processing unit 17 uses the graphing processing unit 17a, the constraint condition processing unit 17b, the objective function processing unit 17c, and the optimum calculation processing unit 17d to Perform an optimal calculation of the VPN path.

  The result calculated by the data processing unit 17 may be displayed on the monitor screen by the output device 14, or may be stored as a file in the external storage device 15 or the like.

  Further, the communication device 16 receives information for setting an optical VPN path and transmits a path calculation result through, for example, an intranet, a VPN, a dedicated line, etc., so that another optical path setting device or network operator is transmitted. It communicates with the computer apparatus which has.

In this example, the data processing unit 17 models the network topology with an undirected multigraph as shown in FIG. 3 by the graphing processing unit 17a. In FIG. 3, the circles represent routers 1-7, and the solid lines between the circles represent links 1a-9a. Each router 1-7 has a router number "1-7" in the circle, Link numbers “ 1 to 9 ” are assigned to the links. The constraint condition processing unit 17b sets numerical conditions as in the example shown in FIG. For example, the “capacity fij” diagram of FIG. 4 shows each link capacity, the “cost C amount fij” diagram of FIG. 4 shows the cost of each link, and the “distance dij” diagram of FIG. Shows the distance of each link.

  With the configuration shown in FIG. 1, the optical VPN path setting device 10 of this example executes computer processing based on a program, so that the storage processing unit 18 uses wavelengths, link costs, and links as constraints in optical network path design. The constraint condition information in which the distance and the like are formulated is input and stored in the memory 12, and the data processor 17 reads the constraint condition information from the memory 12, obtains an initial solution by an approximate solution to each formula, When the local optimum solution is obtained from the allowable solution space based on the solution, the semi-optimal solution is obtained from the obtained local optimum solution, and the optical path is set in the optical network, the storage processing unit 18 further formulates constraints As the condition information, a link bandwidth and a requested bandwidth are newly input and stored in the memory 12, and the data processor 17 The constraint condition information containing the requested bandwidth from the memory 12, by obtaining the initial solution and local optima and quasi-optimal solution, to set the optical VPN path to ensure the required bandwidth.

  For example, the data processing unit 17 obtains an initial solution that is the shortest path of each optical path by the Dijkram method, extracts a link as an initial solution that does not satisfy the constraint information in the obtained initial solution, and passes through the extracted link The path to be passed is detoured so as to pass through another link, and a local optimum solution that satisfies all the constraint information is obtained. Further, the link cost is used as an objective function used when obtaining a suboptimal solution, and a local optimum solution having a minimum link cost is set as a suboptimal solution.

  Hereinafter, as a specific example, the example of the path design between the routers 1, 3, and 7 will be described under the following constraints.

  (1) Since the number of routers is 7, it is assumed that “total number of routers V = {v1, v2,..., V7} = 7”.

  (2) There are three types of optical VPN paths to be calculated: “path 1: between routers 1 and 7”, “path 2: between routers 1 and 3”, and “path 3: between routers 3 and 7”, and “P = { (1,7), (1,3), (3,7)} ".

  (3) The bandwidths of the optical VPN path are “Path 1 is Band 3”, “Path 2 is Band 4”, and “Path 3 is Band 5”, “B1 = 3”, “B2 = 4”, “B3 = 5”.

  (4) There are two types of wavelengths that can be used in each path, and “nw = 2”.

  (5) As shown in “capacity fij” in FIG. 4, the capacity in the link is “1” for “between routers 3 and 4” and “between routers 4 and 7”, “10” for the others, and “f34”. = 1 ”,“ F47 = 1 ”, and other fij are“ fij = 10 (i, j = 1, 2,..., 7, i <j) ”.

  (6) As shown in “Cost Cij” in FIG. 4, the cost of the link is “2” for “between routers 2 and 6”, “10” for “between routers 3 and 7,” and “1” for the others. “C26 = 2”, “C37 = 10”, and other Cij are “Cij = 1 (i, j = 1, 2,..., 7, k <j)”.

  (7) The distances between links are all “1” as shown in “distance dij” in FIG. 4, and “dij = 1 (i, j = 1, 2,..., 7, k <j ) ”.

  (8) The maximum path distance is “10”, and “D = 10”.

  As for path and link variableization, if there is a path 3 with a wavelength number of 4 between the routers 1 and 2, “x [1,2,3,4] = 1” If there is no path 3 with a wavelength number of 4, “x [1, 2, 3, 4] = 0” is set.

  Regarding the formulation of the constraint conditions, “total number of routers nv = 7” and “number of usable wavelengths nw = 2” are exemplified below.

  (1) The formulation regarding the balance of human output at each router and the existence of all paths is as follows in the case where the target router is the source, the sink, and the other cases.

  (1a) When the target router is the source, the following formula 9 is obtained by formulating “path 2 (k = 2) of node 1 (sk = 1)”.

  (1b) When the target router is a sink and “path 2 (k = 2)” of “node 3 (tk = 3)” is formulated, the following formula 10 is obtained.

  (1c) In other cases, the following formula 11 is obtained by formulating “path 1 (k = 1)” of “node 5 (i = 6)”.

  (2) Regarding “path 1 (k = 1)” with respect to the fact that wavelengths do not overlap on the same path and link, for example, “between routers 1 and 5 (i = 1, j = 5)” The constraint condition is formulated as in the following equation (12).

  (3) Regarding “wavelength 2 (l = 2)” regarding “no wavelength overlap on the same wavelength and the same link”, “between routers 1 and 2 (i = 1, j = 2, i <j) For example, since there are three paths, the constraint condition is formulated as shown in Equation 13 below from “k = 3”.

  (4) Regarding all the links satisfying the link capacity, “between routers 6 and 7 (i = 6, j = 7)” is exemplified. “Between routers 6 and 7” has “link capacity f67” of “10. Therefore, the constraint condition regarding the number of used bands is formulated as the following Expression 14.

  Actually, since “Path 1” is “B1 = 3” and “Path 3” is “B3 = 5”, the required bandwidth is the following Expression 15, which is the required bandwidth of “Path 1” and “Path 3”. Is the sum of That is, since the constraint condition is satisfied, “path 1” and “path 3” can pass between “routers 6 and 7”.

  (5) Regarding the length of each path being equal to or less than the set value p, “path 3 (k = 3)” will be exemplified. Since “the number of routers is 7” and “the maximum path distance is 10 (D = 10)”, the constraint condition is formulated as in the following Expression 16.

  Actually, in “path 3”, “wavelength is 1 (l = 1)”. Therefore, the following equation 17 is obtained from the above equation 16. This number 17 represents the distance of “path 3”.

The formulation of the objective function is as follows.
Assuming that “the number of routers nw = 7”, “the number of paths np = 3”, and “the number of wavelengths nw = 2”, the objective function (the total cost of all paths) is

  Using the information such as each constraint condition formulated in this way (graphing), the data processing unit 17 uses the approximate solution method in the optical VPN by the optimum calculation processing unit 17d in the procedure shown in FIG. The candidate algorithm is obtained by executing the algorithm.

  That is, in FIG. 2, the number of routers “V”, number of paths “P”, number of wavelengths “nw”, link capacity “fij”, path bandwidth “Bk”, link cost “Cij”, path The maximum distance “D” and the inter-link distance “dij” are input and stored in the memory 12 (step 101).

  Next, a solution candidate search count (“internation”) is input (step 102). The counter is set and held (step 103). Then, a solution candidate that satisfies all the constraint conditions is searched using an approximate solution (step 104).

  In the search using this approximate solution, as described above, the optical path design is formulated as an integer programming problem with the wavelength, link bandwidth, required bandwidth, cost, distance, etc. in the optical network as constraints. Based on the solution, a local optimal solution is obtained from the allowable solution space. When obtaining a local optimum solution from this initial solution, first, for example, an initial solution that is the shortest path of each path is obtained by the Dijkstra method. Since the initial solution obtained here does not necessarily satisfy all the constraint conditions, if there is a link that does not satisfy the constraint conditions in the obtained initial solution, such a link is randomly selected and A path that passes is detoured to pass another link. By repeating this, a local optimum solution that satisfies all the constraint conditions is obtained.

  After this solution candidate search is repeated for the number of searches set in the counter (steps 105 and 106), a solution that minimizes the objective function is searched (step 107), and x [i, j, k, l], that is, "start point number i", "end point number j", "pass number k", and "wavelength number 1" are output (step 108).

  In the solution candidate search process in step 104, for example, when the number of times of obtaining candidate solutions is “2” (“internation = 2”), “pass 1” to “pass 3” shown in FIGS. 5 and 6 are obtained. It is done. In FIG. 5 and FIG. 6, the path length dij (maximum distance D), band Bk (capacity fij), wavelength nw, cost Cij are used as candidates for the optical VPN path between the routers (nodes) 1, 3 and 7. Path candidates obtained by an approximate solution that satisfies the constraints such as are shown. 5 and 6 are the same as “path 1” and “path 2”, but regarding “path 3”, in FIG. 5, between routers 3, 2, 1, 5, 6, and 7 The link between the routers 3, 2, 6, and 7 is selected in FIG.

  Regarding the link between the routers 3, 4, and 7, as shown in the drawing of the capacity fij in FIG. 4, the capacity is “1”, and the use (request) bandwidth condition is not satisfied. I can't get it. Further, regarding the link between the routers 3 and 7, as shown in the drawing of the cost Cij in FIG. 4, the cost is “10”, and the constraint condition is not satisfied, so it cannot be obtained as a candidate.

  In this manner, in the optical VPN network configuration shown in FIG. 3, the number of times that the candidate solution is obtained is “2”, and the first candidate solution, that is, the first candidate solution that satisfies all the constraint conditions is shown in FIG. Suppose that it was obtained as shown in passes 1-3). The value of the objective function in this case is “(1 + 1 + 1) + (1 + 1) + (1 + 1 + 1 + 1 + 1)” = “10” from the drawing relating to the cost in FIG.

  On the other hand, it is assumed that the second candidate solution satisfying all the constraint conditions is obtained as shown in FIG. 6 (paths 1 to 3). The value of the objective function in this case is “(1 + 1 + 1) + (1 + 1 + 1) + (1 + 2 + 1)” = “9” from the drawing relating to the cost in FIG. As a result, when the minimum solution is searched from all the obtained candidate solutions when the solution candidate search count (“internation”) “= 2” is completed, the value of the objective function is the second candidate solution. 6 is the minimum, so FIG. 6 is the final solution.

  As described above with reference to each figure, in this example, the optical path design is formulated as an integer programming problem with the wavelength, link bandwidth, required bandwidth, cost, distance, etc. in the optical network as constraints. An initial solution is obtained, a local optimum solution is obtained from the allowable solution space based on the obtained initial solution, and a sub-optimal solution is obtained therefrom. When obtaining a local optimum solution from this initial solution, first, for example, an initial solution that is the shortest path of each path is obtained by the Dijkstra method. However, the initial solution obtained here does not necessarily satisfy all the constraint conditions. Therefore, if there is a link that does not satisfy the constraint conditions in the obtained initial solution, such a link is selected at random, and a certain path passing therethrough is detoured so as to pass through another link. By repeating this, a local optimum solution that satisfies all the constraint conditions is obtained. Then, a path corresponding to the objective (objective function) is further selected from the obtained local optimum solution. As a result, the network operator can efficiently perform path design in a band that can guarantee the quality of the provided network service.

  In addition, this invention is not limited to the example demonstrated using each figure, In the range which does not deviate from the summary, various changes are possible. For example, in this example, the path design between the routers 1, 3, and 7 has been described with reference to FIG. 3, but it can also be applied to the path design between the routers 1, 4, 6, and 7, and FIG. The present invention is not limited to application to a router configuration as shown, but can be applied to a larger-scale network configuration. Further, regarding the program installation form in the computer configuration in this example, an optical disk is used as a recording medium, but an FD (Flexible Disk) or the like may be used as a recording medium, or via a network via a communication device. You can also download and install the program.

It is a block diagram which shows the structural example of the optical VPN path setting apparatus concerning this invention. It is a flowchart which shows the process sequence example of the optical VPN path setting method concerning this invention. It is explanatory drawing which shows the topology example of the network to which this invention is applied. It is explanatory drawing which shows a numerical condition example. It is explanatory drawing which shows the 1st candidate solution example. It is explanatory drawing which shows the candidate solution example of the 2nd time.

Explanation of symbols

  1-7: Router, 1a-9a: Link, 10: Optical VPN path setting device, 11: CPU, 12: Memory, 13: Input device, 14: Output device, 15: External storage device, 16: Communication device, 17 : Data processing unit, 17a: graphing processing unit, 17b: constraint condition processing unit, 17c: objective function processing unit, 17d: optimal calculation processing unit, 18: storage processing unit, 18a: graph data storage unit, 18b: constraint condition Storage unit, 18c: objective function storage unit.

Claims (9)

Storage processing means for inputting constraint condition information in which wavelength, link cost, link distance and the like as constraint conditions in path design of an optical network are formulated and storing them in a storage device;
Data that reads the above constraint information from the storage device, finds an initial solution by an approximate solution to each formula, finds a local optimum solution from the allowable solution space based on the obtained initial solution, and obtains a suboptimal solution from the obtained local optimum solution And a processing unit that executes computer processing based on a program and sets an optical path in the optical network,
The storage processing means has a function of newly inputting a link bandwidth and a required bandwidth as the formulated constraint condition information and storing them in the storage device,
The data processing means has a function of reading the constraint condition information including the link bandwidth and the required bandwidth, and obtaining the initial solution, the local optimal solution, and the semi-optimal solution,
A bandwidth-guaranteed optical VPN path design system characterized by setting an optical VPN path that guarantees a required bandwidth. The bandwidth-guaranteed optical VPN path design system according to claim 1,
The data processing means is
A function to obtain an initial solution which is the shortest path of each optical path by the Dijkstra method;
A function to extract a link as an initial solution that does not satisfy the constraint information in the obtained initial solution;
A band-guaranteed optical VPN path design system having a function of detouring a path passing through an extracted link so as to pass through another link and obtaining a local optimum solution satisfying all the constraint condition information. A bandwidth-guaranteed optical VPN path design system according to claim 1 or 2,
As the constraint information, from the following router number i, j, path number k, wavelength number l, router number sk as source, router number tk as sink, number of wavelengths nw, total number of routers nv, number of paths np A bandwidth-guaranteed optical VPN path design method characterized by including:
(1) The number 1 as the first constraint condition expression indicating that the input vin and the output vout are balanced in the router as the source and that all paths exist.

(2) The number 2 as the second constraint condition expression indicating that the input vin and the output vout are balanced in the router as the sink and that all paths exist.

(3) Expression 3 as a third constraint expression indicating that the input vin and the output vout in the router other than the source and the sink are balanced and that all paths exist.

(4) Number 4 as a fourth constraint condition expression indicating that wavelengths do not overlap on the same path and the same link

(5) Formula 5 as a fifth constraint condition expression indicating a constraint condition where paths do not overlap on the same wavelength and the same link

(6) Expression 6 as a fifth constraint condition expression indicating that all link bandwidths Bk satisfy the link capacity fij

(7) Expression 7 as a sixth constraint condition expression indicating that the length dij of each path is equal to or less than the set value D

The bandwidth-guaranteed optical VPN path design system according to any one of claims 1 to 3,
As the objective function used when obtaining the semi-optimal solution, the following equation 8 including the link cost Cij is used, and among the local optimum solutions, the one having the smallest link cost Cij is used as the semi-optimal solution. Bandwidth guaranteed optical VPN path design system.

By computer processing based on the program, input constraint condition information in which wavelength, link cost, link distance, etc. as constraint conditions in optical network path design are formulated and stored in a storage device,
Read the constraint information from the storage device, obtain an initial solution by an approximate solution method for each formula, obtain a local optimum solution from the allowable solution space based on the obtained initial solution, obtain a sub-optimal solution from the obtained local optimum solution, A method for setting an optical path in the optical network,
As a process executed by the computer,
A first step of newly adding and inputting a link bandwidth and a required bandwidth to the formulated constraint information, and storing the first bandwidth in the storage device;
A second step of reading the constraint condition information including the link bandwidth and the required bandwidth from a storage device, and obtaining the initial solution, the local optimal solution, and the semi-optimal solution;
A bandwidth-guaranteed optical VPN path design method characterized by setting an optical VPN path that guarantees a required bandwidth. The bandwidth-guaranteed optical VPN path design method according to claim 5,
In the first step,
Obtaining an initial solution which is the shortest path of each optical path by the Dijkstra method;
Extracting a link as an initial solution that does not satisfy the constraint information in the obtained initial solution;
And detouring a path passing through the extracted link so as to pass through another link to obtain a local optimum solution satisfying all the constraint condition information. A bandwidth-guaranteed optical VPN path design method according to any one of claims 5 and 6,
As the constraint information, from the following router number i, j, path number k, wavelength number l, router number sk as source, router number tk as sink, number of wavelengths nw, total number of routers nv, number of paths np A bandwidth-guaranteed optical VPN path design method characterized by including:
(1) Expression 9 as a first constraint expression indicating that the input vin and the output vout are balanced in the router as the source and that all paths exist.

(2) Expression 10 as a second constraint condition expression indicating that the input vin and the output vout are balanced in the router as a sink and that all paths exist.

(3) Expression 11 as a third constraint expression indicating that the input vin and the output vout in the router other than the source and the sink are balanced and that all paths exist.

(4) Expression 12 as a fourth constraint condition expression indicating that wavelengths do not overlap on the same path and the same link

(5) Expression 13 as a fifth constraint condition expression indicating a constraint condition where paths do not overlap on the same wavelength and the same link

(6) Expression 14 as a fifth constraint expression indicating that all link bandwidths Bk satisfy the link capacity fij

(7) Expression 15 as a sixth constraint condition expression indicating that the length dij of each path is equal to or less than the set value D

A bandwidth-guaranteed optical VPN path design method according to any one of claims 5 to 7,
The bandwidth guarantee type optical VPN characterized in that the following equation 16 is used as an objective function used for obtaining the sub-optimal solution, and the sub-optimal solution is the one having the smallest link cost Cij among the local optimal solutions. Path design method.

  The program for making a computer perform the process in each step in the band guarantee type | mold optical VPN path design method in any one of Claims 5-8.

Images