Method for designing a communication network

[0002] 1. Field of the Invention

[0003] The present invention relates to communication network design techniques, and in particular to a method for designing a communication network to cope with demand variations and network faults.

[0004] 2. Description of Related Art

[0005] As for a communication network design method conventionally used to cope with demand variations and network faults, there has been proposed a method of designing path and link capacities for a given specific demand by using linear programming. For example, “Restoration Strategies and Spare Capacity Requirements in Self-Healing ATM Networks,” has been proposed by Yijun Xiong and Lorne Mason (INFOCOM '97, April 1997). Here, the linear programming refers to a method for handling a problem of finding a maximal or minimal value of a linear objective function under. conditions of linear equalities and inequalities

[0006] In a conventional communication network design method, paths of respective demands for respective fault states are set so that the communication may be maintained even at the time of conceivable link fault, and the link capacity is designed to be able to accommodate those paths at the time of the link fault.

[0007] As shown in FIG. 1, as input date, a network topology, a demand, a link cost coefficient, and conceivable fault states are given. Providing with the input data, an optimization reference generator 11 generates an objective function for minimizing the cost concerning the link. A path accommodation condition generator 12 generates a constraint formula representing that the sum of capacities assigned to path candidates is equal to the requested capacity of the demand.

[0008] A link accommodation condition generator 13 generates a constraint formula representing that the capacity of that link is larger than the total of capacities of paths passing through each link in each state. In succession, an optimization section 14 solves a linear programming problem generated by the optimization reference generator 11, the path accommodation generator 12, and the link accommodation condition generator 13 to determine the capacities of the paths and links. In general, a linear programming problem refers to a problem of maximizing or minimizing an objective function represented by a linear equation under a constraint condition represented by some linear equalities or inequalities.

[0009] In the above described conventional communication network design method, there is developed a problem that an optimum design is conducted only for a given determinate demand pattern, where “demand pattern” refers to a set of demands requested between all nodes.

[0010] For a given determinate demand pattern, optimization is conducted by using mathematical programming. Therefore, after ensuring that the demand pattern can be accommodated, an optimum network minimizing the cost is designed. In other words, there is no assurance for a pattern different from that demand pattern.

[0011] In actual communication networks, however, the demand pattern differs depending upon time zone, day of a week, season, and so on, and is varied by events and the like. Even if the season, the day of week, and the time zone are the same, it is hardly to be supposed that completely the same demand pattern is brought about. Furthermore, it is also possible that the demand pattern significantly changes according to the wide spread of new communication service or introduction of a new technique.

[0012] In the conventional network centering on the existing telephone network, forecast of the demand was possible to some degree. In multimedia networks of recent.years, however, demand forecast has become very difficult.

[0013] An object of the present invention is to solve the above described problems, and to provide a communication network design method that is capable of accommodating traffic varying due to variations in demand pattern.

[0014] According to the present invention, a communication network composed of a plurality of nodes and links each connecting two nodes is designed by the following steps: a) inputting network data including a requested capacity of a demand as a random variable following a predetermined probability distribution between any two nodes and path candidates of the demand for accommodating the requested capacity of the demand; b) generating an objective function representing a total cost of the nodes and the links from the network data; c) generating a predetermined set of stochastic constraints by using the requested capacity of the demand to produce a stochastic programming problem including the objective function and the stochastic constraints; d) converting the stochastic programming problem into an equivalent determinate programming problem on condition of the predetermined probability distribution; and e) solving the determinate programming problem to determine capacities of the nodes and the links so that the objective function is minimized.

[0015] The step c) may include the steps of: c-1) generating a stochastic path accommodation constraint for causing the requested capacity of the demand to be accommodated in the path candidates; c-2) generating a link accommodation constraint for causing capacities assigned to path candidates to be accommodated in the links; and c-3) generating a stochastic node accommodation constraint for causing a total of capacities of path candidates passing through a node to be accommodated in the node.

[0016] The step c) may include the steps of: c-1) generating a path accommodation constraint for causing the requested capacity of the demand to be accommodated in the path candidates; c-2) generating a stochastic link accommodation constraint for causing capacities assigned to path candidates to be accommodated in the links; and c-3) generating a stochastic node accommodation constraint for causing a total of capacities of path candidates passing through a node to be accommodated in the node.

[0017] According to the present invention, the stochastic constraints are generated by using the requested capacity of the demand to produce a stochastic programming problem and then the stochastic programming problem is converted into an equivalent determinate programming problem on condition of the predetermined probability distribution. The determinate programming problem is solved to determine capacities of the nodes and the links so that the objective function is minimized. This brings about an effect that traffics can be accommodated even if a demand pattern changes to some degree. In other words, the stochastic programming problem regarding the paths, the links and the nodes is generated and then the equivalent determinate programming problem is determined. Therefore, traffics can be accommodated even if a demand pattern changes to some degree, resulting in reduced cost for network construction.

[0018] FIG. 1 is a block diagram showing the configuration of a conventional communication network design circuit;

[0019] FIG. 2 is a block diagram showing the configuration of a communication network design system for implementing a first embodiment of a network design method according to the present invention;

[0020] FIG. 3 is a flow chart showing a network design method according to the first embodiment of the present invention;

[0021] FIG. 4 is a block diagram showing the configuration of a communication network design system for implementing the following embodiments of a network design method according to the present invention;

[0022] FIG. 5 is a flow chart showing a network design method according to a second embodiment of the present invention;

[0023] FIG. 6 is a flow chart showing a network design method according to a third embodiment of the present invention;

[0024] FIG. 7 is a flow chart showing a network design method according to a fourth embodiment of the present invention;

[0025] FIG. 8 is a flow chart showing a network design method according to a fifth embodiment of the present invention; and

[0026] FIG. 9 is a flow chart showing a network design method according to a sixth embodiment of the present invention.

[0027] First of all, symbols to be used in first to third embodiments according to the present invention will be described hereinafter.

[0028] l: a link number in the range of 1, . . . , L.

[0029] n: a node number in the range of 1, . . . , N.

[0030] p: a demand number in the range of 1, . . . , P.

[0031] i_p: a candidate number of a demand p in the range of 1, . . . , I_p, where a path candidate i_pof a demand p is an arbitrary path between an originating node and a terminating node of a demand p.

[0032] ω_l: a cost coefficient of a link l.

[0033] ε: a cost coefficient of a node.

[0034] g_ip/l: an indicator indicating l when a path 1_pof a demand p passes through a link l (as represented by ip/l) and indicating 0 otherwise.

[0035] h_l/n: an indicator indicating l when a link l passes though node n (as represented by l/n) and indicating 0 otherwise.

[0036] o_p/n:an indicator indicating l when a demand p terminates at a node n (as represented by p/n) and indicating 0 otherwise.

[0037] λ: the capacity of a unit of link. For example, in a light-wave network, λ represents the number of wavelength paths accommodated in one optical fiber.

[0038] ν: the capacity of a unit of node. For example, in a light-wave network, ν represents the number of wavelength paths accommodated in one optical cross-connect.

[0039] v_p: requested capacity (random variable) of a demand p.

[0040] α: a probability (path accommodation probability) that the requested capacity v_pof a demand p is assigned to path candidates of the demand p.

[0041] β: a probability (link accommodation probability) that the total of capacities of paths i_ppassing through a link l can be accommodated in the link l.

[0042] γ: a probability (node accommodation probability) that the total of capacities of links terminating at a node n and capacities of paths i_pterminating at the node n can be accommodated in the node n.

[0043] c_ip: a capacity (integer variable) assigned to a path candidate i_pof a demand p.

[0044] r_ip: a ratio (real number variable) assigned to a path candidate i_pwhen it is assumed that a requested capacity of a demand p is 1.

[0045] d_l: a capacity (integer variable) assigned to a link l.

[0046] e_n: a capacity (integer variable) assigned to a node n.

[0047] Referring to FIG. 2, the communication network design system implements a first embodiment of the present invention with hardware or software. In the preferred embodiment, a network design procedure according to the first embodiment is implemented by a computer running a network design program thereon. The network design program according to the first embodiment is previously stored in a read-only memory (ROM), a magnetic storage, or the like (not shown).

[0048] Necessary input data is supplied to an optimization reference generator 101, a stochastic path accommodation constraint generator 102, a link accommodation constraint generator 103, and a stochastic node constraint generator 104. The optimization reference generator 101 produces an objective function and the other generators 102-104 produce stochastic constraints to produce a stochastic programming problem. The stochastic programming problem is transformed to an equivalent determinate programming problem by an equivalent determinate programming problem transformer 105. An optimization section 106 optimizes the objective function under the equivalent determinate programming problem to produce an optimized network design as an output. The details of network design procedure according to the first embodiment will be described hereinafter.

[0049] Referring to FIG. 3, the system is first provided with a network topology, demands each having a requested capacity given by probability distribution, path candidates of respective demands, cost coefficients of link/nodes, path accommodation probabilities, and node accommodation probabilities (step S301).

[0050] On the basis of the above input data, the optimization reference generator 101 generates an objective function represented by the following expression (step S302). $\begin{array}{cc}\mathrm{Minimize}\left[\sum _{l-1}^L{\omega }_{1}d+ϵ\sum _{n-1}^N{e}_n\right]& \left(1\right)\end{array}$

[0051] The expression (1) means minimization of the cost concerning the links and the cost concerning the nodes.

[0052] The stochastic path accommodation condition generator 102 generates the following constraint expression for paths to accommodate the requested capacity of a demand (step S302). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{i_p-1}^{\mathrm{Ip}}{c}_{\mathrm{ip}}\ge v_p\right]\ge \alpha \left(p=1,\cdots ,P\right)& \left(2\right)\end{array}$

[0053] where, Prob [ ] represents the probability that the condition in [ ] is satisfied. The expression (2) represents the accommodation condition of the path, and means that the probability that the total of capacities assigned to path candidates i_pof a demand p exceeds a requested capacity v_pof the demand p is at least α.

[0054] The link accommodation condition generator 103 generates the following constraint expression for a link to accommodate capacities assigned to paths (step S303). $\begin{array}{cc}\sum _{p-1}^P\sum _{i_p-1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{c}_{\mathrm{ip}}\le \lambda d_1\left(1=1,\cdots ,L\right)& \left(3\right)\end{array}$

[0055] The expression (3) means that the capacity d_lof a link l exceeds the total of capacities of paths i_ppassing through the link l.

[0056] The stochastic node accommodation condition generator 104 generates the following constraint expression for a node to accommodate the capacities assigned to paths (step S304). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{i=1}^L{h}_{l/n}{d}_1+\sum _{p-1}^P{o}_{p/n}{v}_p/\lambda \le v{e}_n\right]\ge \gamma \left(n=1,\cdots ,N\right)& \left(4\right)\end{array}$  (n=1, . . . , N)  (4)

[0057] The expression (4) means that the probability that the capacity of a node n exceeds the termination capacities of the links l and the termination capacities of the demands p is at least γ.

[0058] The expression (1) of the objective function and the constraint expressions (2), (3) and (4) respectively generated by the optimization reference generator 101, the stochastic path accommodation constraint generator 102, the link accommodation constraint generator 103, and the stochastic node accommodation constraint generator 104 form a stochastic programming problem.

[0059] The equivalent determinate programming problem transformer 105 transforms the stochastic programming problem into an equivalent determinate programming problem (step 305). If it is assumed that the requested capacity v_pfollows a normal distribution having a mean μ_pand a variance σ_p, the expression (2) can be transformed as follows: $\begin{array}{cc}\stackrel{\mathrm{Ip}}{\sum _{i_p-1}}{c}_{\mathrm{ip}}\ge {\mu }_p+t\left(\alpha \right){\sigma }_p\left(p=1,\cdots ,P\right)& \left(5\right)\end{array}$

[0060] where t(α) is a safety coefficient of a standard normal distribution satisfying α.

[0061] In succession, the equivalent determinate programming problem transformer 105 transforms the expression (4). If it is assumed that the sum total of o_p/nv_pfor p=1, . . . , P follows a normal distribution having a mean μ_nand a variance σ_p, the mean μ_nand the variance σ_nare derived by the following expressions (6) and (7), because the requested capacities v_prespectively have independent distributions. $\begin{array}{cc}{\mu }_n=\sum _{p=1}^P{o}_{p/n}{\mu }_p\left(n=1,\cdots ,N\right)& \left(6\right)\end{array}$ $\begin{array}{cc}{\left({\sigma }_n\right)}^2=\sum _{p-1}^P{o_{p/n}\left({\sigma }_p\right)}^2\left(n=1,\cdots ,N\right)& \left(7\right)\end{array}$

[0062] By using the mean μ_nand the variance ρ_n, the expression (4) can be transformed as follows: $\begin{array}{cc}v{e}_n-\sum _{i=1}^L{h}_{l/n}{d}_1\ge {\mu }_n+t\left(\gamma \right){\sigma }_n\left(n=1,\cdots ,N\right),& \left(8\right)\end{array}$  (n=1, . . . , N)  (8),

[0063] where t(γ) is a safety coefficient of a standard normal distribution satisfying γ.

[0064] A linear programming problem obtained by the transformation processing conducted by the equivalent determinate programming problem transformer 105 is formed by the expression (1) of the objective function and the constraint expressions (3), (5), (6), (7) and (8). The optimization section 106 solves this linear programming problem, and obtains the capacities of respective links and the capacities of respective nodes (step S306).

[0065] Referring to FIG. 4, the communication network design system implements a second embodiment of the present invention with hardware or software, where symbols to be used in the second embodiment are the same as in the first embodiment.

[0066] Necessary input data is supplied to an optimization reference generator 201, a path accommodation constraint generator 202, a stochastic lint accommodation constraint generator 203, and a stochastic node constraint generator 204. The optimization reference generator 201 produces an objective function and the other generators 202-204 produce stochastic constraints to produce a stochastic programming problem. The stochastic programming problem is transformed to an equivalent determinate programming problem by an equivalent determinate programming problem transformer 205. An optimization section 206 optimizes the objective function under the equivalent determinate programming problem to produce an optimized network design as an output. The details of network design procedure according to the second embodiment will be described hereinafter.

[0067] Referring to FIG. 5, as input data, the system according to the second embodiment is first provided with a network topology, demands each having a requested capacity given by probability distribution, path candidates of respective demands, cost coefficients of link/nodes, link accommodation probabilities, and node accommodation probabilities (step S501).

[0068] On the basis of the provided data, the optimization reference generator 201 generates the objective function represented by the following expression (step S502): $\begin{array}{cc}\mathrm{Minimize}\left[\sum _{i-1}^L{\omega }_1{d}_1+ϵ\sum _{n-1}^N{e}_n\right].& \left(9\right)\end{array}$

[0069] The expression (9) means minimization of the cost concerning the links and the cost concerning the nodes.

[0070] The path accommodation condition generator 202 generates the following constraint expression for paths to accommodate the requested capacity of a demand (step S503). $\begin{array}{cc}\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{r}_{\mathrm{ip}}\geqq 1\left(p=1,\cdots ,P\right)& \left(10\right)\end{array}$

[0071] The expression (10) represents the accommodation condition of paths. The expression (10) means that the total of ratios of capacities assigned to path candidates i_pof the demand p is at least 1 when it is assumed that the requested capacity is 1.

[0072] The stochastic link accommodation condition generator 203 generates the following constraint expression for a link to accommodate the capacities assigned to paths (step S504). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{p-1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{v}_p{r}_{\mathrm{ip}}\le \lambda d_1\right]\ge \beta \left(1=1,\cdots ,L\right)& \left(11\right)\end{array}$

[0073] The expression (11) means that the probability that the capacity d_lof the link l exceeds the total of capacities of paths i_ppassing through the link l is at least β.

[0074] The stochastic node accommodation condition generator 204 generates a constraint expression for a node to accommodate capacities assigned to paths (step S505). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{i-1}^L{h}_{l/n}{d}_1+\sum _{p-1}^P{o}_{p/n}{v}_p/\lambda \le v{e}_n\right]\ge \gamma \left(n=1,\cdots ,N\right)& \left(12\right)\end{array}$  (n=1, . . . , N)  (12)

[0075] The expression (12) means that the probability that the capacity of a node n exceeds the termination capacities of the links l and the termination capacities of the demands p is at least γ.

[0076] The expression (9) of the objective function and the constraint expressions (10), (11) and (12) respectively generated by the optimization reference generator 201, the path accommodation condition generator 202, the stochastic link accommodation condition generator 203, and the stochastic node accommodation condition generator 204 form a stochastic programming problem.

[0077] The equivalent determinate programming problem transformer 205 transforms this stochastic programming problem into an equivalent determinate programming problem (step S506). It is assumed that the requested capacities v_pfollow mutually independent probability distributions, and each probability distribution has mean μ_pand a variance value σ_p.

[0078] If it is assumed that the sum total of g_lp/lv_pr_ipfor p=l, . . . , P, i=l, . . . , i_pfollows probability distribution having a mean μ_land a variance σ_l, the mean μ_land the variance σ_lare derived by the following expressions (13) and (14), because the requested capacities v_pare respectively independent. $\begin{array}{cc}{\mu }_1=\sum _{p-1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{r}_{\mathrm{ip}}{\mu }_p\left(l=1,\cdots ,L\right)& \left(13\right)\\ {\left({\sigma }_1\right)}^2=\sum _{p-1}^p\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g_{\mathrm{ip}/1}\left(r_{\mathrm{ip}}\right)}^2{\left({\sigma }_p\right)}^2\left(l=1,\cdots ,L\right)& \left(14\right)\end{array}$  (l=1, . . . , L)  (14)

[0079] If it is now assumed that the sum total of g_lp/lv_pr_ipfor p=1, . . . , P, i=1, . . . , i_pfollows a normal distribution, the expression (11) can be transformed as follows:

[0080] λd_l≧μ_l+t(β)σ_l(l=1, . . . , L)  (15)

[0081] where t(β) is a safety coefficient of a standard normal distribution satisfying β.

[0082] In succession, the equivalent determinate programming problem transformer 205 transforms the expression (12). Since the requested capacities v_pare respectively independent, the mean μ_nand the variance σ_nof the sum total of o_p/nv_pfor p=1, . . . , P are derived as follows: $\begin{array}{cc}{\mu }_n=\sum _{p-1}^P{o}_{p/n}{\mu }_p\left(n=1,\cdots ,N\right)& \left(16\right)\\ {\left({\sigma }_n\right)}^2=\sum _{p-1}^P{o_{p/n}\left({\sigma }_p\right)}^2\left(n=1,\cdots ,N\right)& \left(17\right)\end{array}$

[0083] If it is assumed that the sum total of g_ip/lv_pfor p=1, . . . , P follows a normal distribution, the expression (12) can be transformed as follows: $\begin{array}{cc}v{e}_n-\stackrel{L}{\sum _{l-1}}{h}_{l/n}{d}_1\ge {\mu }_n+t\left(\gamma \right){\sigma }_n\left(n=1,\cdots ,N\right)& \left(18\right)\end{array}$  (n=1,. . . , N)  (18)

[0084] where t(γ) is a safety coefficient of standard normal distribution satisfying γ.

[0085] A linear programming problem obtained by the transformation processing conducted by the equivalent determinate programming problem transformer 205 is formed by the expression (9) of the objective function and the constraint expressions (10), (13), (14), (15), (16), (17) and (18). The optimization means 206 solves this linear programming problem, and obtains the capacities of respective links and the capacity of the node (step S507).

[0086] Referring to FIG. 6, the communication network design system implements a third embodiment of the present invention with hardware or software, where symbols to be used in the third embodiment are the same as in the first embodiment except that c_ipis a capacity [variable of a stochastic programming problem (random variable)] assigned to a path candidate i_pfor the requested capacity of a demand p. The basic configuration of the system for implementing the third embodiment is the same as in the second embodiment as shown in FIG. 4.

[0087] As input data, the system according to the third embodiment is first provided with a network topology, demands each having a requested capacity given by probability distribution, path candidates of respective demands, cost coefficients of link/nodes, link accommodation probabilities, and node accommodation probabilities (step S601).

[0088] On the basis of the provided data, the optimization reference generator 201 generates the objective function represented by the following expression (step S602): $\begin{array}{cc}\mathrm{Minimize}\left[\sum _{i-1}^L{\omega }_1{d}_1+ϵ\sum _{n-1}^N{e}_n\right].& \left(19\right)\end{array}$

[0089] The expression (19) means minimization of the cost concerning the links and the cost concerning the nodes.

[0090] The path accommodation condition generator 202 generates the following constraint expression for paths to accommodate the requested capacity of a demand (step S603): $\begin{array}{cc}\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{c}_{\mathrm{ip}}\geqq v_p\left(p=1,\cdots ,P\right),& \left(20\right)\end{array}$

[0091] where c_ipis a capacity (a variable of a stochastic programming problem or a random variable] assigned to a path candidate i_pfor the requested capacity of a demand p.

[0092] The expression (20) represents the accommodation condition of paths. The expression (20) means that the total of capacities assigned to path candidates i_pof the demand p is at least the requested capacity v_pof the demand p.

[0093] The stochastic link accommodation condition generator 203 generates the following constraint expression for a link to accommodate the capacities assigned to paths (step S604). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{p-1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{c}_{\mathrm{ip}}\le \lambda d_1\right]\ge \beta \left(1=1,\cdots ,L\right)& \left(21\right)\end{array}$  (l=1, . . . , L)  (21)

[0094] The expression (21) means that the probability that the capacity d_lof the link l exceeds the total of capacities of paths i_ppassing through the link l is at least β.

[0095] The stochastic node accommodation condition generator 14 generates the following constraint expression for a node to accommodate capacities assigned to paths (step S605). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{l-1}^L{h}_{l/n}{d}_1+\sum _{p=1}^P{o}_{p/n}{v}_p/\lambda \le v{e}_n\right]\ge \gamma \left(n=1,\cdots ,N\right)& \left(22\right)\end{array}$  (n=1, . . . , N)  (22)

[0096] The expression (22) means that the probability that the capacity of a node n exceeds the termination capacities of the links l and the termination capacities of the demands p is at least γ.

[0097] The expression (19) of the objective function and the constraint expressions (20), (21) and (22) respectively generated by the optimization reference generator 201, the path accommodation condition generator 202, the stochastic link accommodation condition generator 203, and the stochastic node accommodation condition generator 204 form a stochastic programming problem.

[0098] The equivalent determinate programming problem transformer 205 transforms this stochastic programming problem into an equivalent determinate programming problem (step S606). If it is assumed that the requested capacities v_pfollow mutually independent probability distributions each having mean μ_pand a variance σ_p, the mean μ_ipand the variance σ_ipof a random variable c_ipcan be represented as follows: $\begin{array}{cc}\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{\mu }_{\mathrm{ip}}={\mu }_p\left(p=1,\cdots ,P\right)& \left(23\right)\end{array}$ $\begin{array}{cc}\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{\left({\sigma }_{\mathrm{ip}}\right)}^2={\left({\sigma }_p\right)}^2\left(p=1,\cdots ,P\right)& \left(24\right)\end{array}$

[0099] In succession, the equivalent determinate programming problem transformer 205 transforms the expression (21). If it is assumed that the random variables c_ipare mutually independent, the mean μ_land the variance σ_lof the sum total of g_ip/lc_ip, p=1, . . . , P, i_p=1, . . . , I_pare derived as follows: $\begin{array}{cc}{\mu }_1=\sum _{p-1}^P\sum _{\mathrm{ip}=1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{\mu }_{\mathrm{ip}}\left(l=1,\cdots ,L\right)& \left(25\right)\\ {\left({\sigma }_1\right)}^2=\sum _{p=1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g_{\mathrm{ip}/1}\left({\sigma }_{\mathrm{ip}}\right)}^2\left(l=1,\cdots ,L\right)& \left(26\right)\end{array}$

[0100] If it is assumed that the sum total of g_ip/lcip, p=1, . . . , P, i_p=1, . . . , I_pfollows normal distribution, the expression (21) can be transformed as follows:

[0101] λd_i≧μ_l+t(β)σ_l(l=1, . . . , L)  (27)

[0102] where t(β) is a safety coefficient of standard normal distribution satisfying β.

[0103] If it is assumed that the sum total of o_p/nv_pp=l, . . . , P follows a normal distribution and each of the requested capacities v_phas independent distribution, the mean μ_nand the variance σ_nbecome as follows: $\begin{array}{cc}{\mu }_n=\sum _{p-1}^P{o_{p/n}\left({\sigma }_n\right)}^2\left(n=1,\cdots ,N\right)& \left(28\right)\\ {\left({\sigma }_n\right)}^2=\sum _{p-1}^P{o_{p/n}\left({\sigma }_n\right)}^2\left(n=1,\cdots ,N\right)& \left(29\right)\end{array}$

[0104] By using the mean μ_nand the variance σ_n, the expression (22) can be transformed as follows; $\begin{array}{cc}v{e}_n-\sum _{l=1}^L{h}_{l/n}\ge {\mu }_n+t\left(\gamma \right){\sigma }_n\left(n=1,\cdots ,N\right)& \left(30\right)\end{array}$

[0105] where t(γ) is a safety coefficient of standard normal distribution satisfying γ.

[0106] A nonlinear programming problem obtained by the transformation processing conducted by the equivalent determinate programming problem transformer 205 is formed by the expression (19) of the objective function and the constraint expressions (23), (24), (25), (26), (27), (28), (29) and (30). The optimization means 206 solves this nonlinear programming problem, and obtains the capacities of respective links and the capacity of the node (step S607).

[0107] First of all, symbols to be used in fourth to sixth embodiments according to the present invention will be described hereinafter.

[0108] l: a link number in the range of 1, . . . , L.

[0109] n: a node number in the range of 1, . . . , N.

[0110] p: a demand number in the range of 1, . . . , P.

[0111] s: a network state in the range of 0, . . . , S, where 0 represents a normal state where no fault occurs, and each of 1, . . . , S represents a fault state in which there is a fault on some link.

[0112] i_p: a path candidate number in a demand p in the range of 1, . . . , I_p, where a path candidate i_pof the demand p is an arbitrary path between an originating node and a terminating node of the demand p, and is provided as an input.

[0113] ω_l: a cost efficient of a link l.

[0114] ε: a cost efficient of a node.

[0115] g_ip/l: an indicator indicating l when a path i_pof a demand p passes through a link l (as represented by i_p/l) and indicating 0 otherwise.

[0116] h_l/n: an indicator indicating l when a link l passes through a node n (as represented by l/n) and indicating 0 otherwise.

[0117] o_p/n: an indicator indicating l when a demand p terminates at a node n (as represented by p/n), and indicating 0 otherwise.

[0118] λ: a capacity of a unit of link. For example, in a light-wave network, λ represents the number of wavelength paths accommodated by one optical fiber.

[0119] ν: a capacity of a unit of node. For example, in a light-wave network, ν represents the number of wavelength paths accommodated by one optical cross-connect.

[0120] v_p: a requested capacity of a demand p indicating a random variable having mean μ_pand a variance σ_p.

[0121] f_l/a: an indicator indicating 0 when a link l is faulty, and indicating 1 when the link l is normal. In the normal state represented as s=0, f_l/a=1 in every link l.

[0122] α: a probability (path accommodation probability) that a requested capacity v_pof a demand p is assigned to path candidates of the demand p.

[0123] β: a probability (link accommodation probability) that the total of capacities of paths i_ppassing through a link l can be accommodated by the link l.

[0124] γ: a probability (node accommodation probability) that the total of capacities of links terminating at a node n and a capacity of paths i_pterminating at the node n can be accommodated in the node n.

[0125] c_ipa: capacity (integer variable) assigned to a path i_pof a demand p in a state s.

[0126] r_ipε: a ratio (real number variable) assigned to a path candidate i_pwhen it is assumed that a requested capacity of a demand p is 1.

[0127] d_l: a capacity (integer variable) assigned to a link l.

[0128] e_n: a capacity (integer variable) assigned to a node n.

[0129] Referring to FIG. 7, the communication network design system implements a fourth embodiment of the present invention with hardware or software. In the preferred embodiment, a network design procedure according to the first embodiment is implemented by a computer running a network design program thereon. The network design program according to the first embodiment is previously stored in a read-only memory (ROM), a magnetic storage, or the like (not shown) The basic configuration of the system for implementing the fourth embodiment is the same as in the first embodiment as shown in FIG. 2.

[0130] As input data, the system is first provided with a network topology, demands each having a requested capacity given by probability distribution, path candidates of the respective demands, cost coefficients of link/nodes, link accommodation probabilities, node accommodation probabilities, and a conceivable fault scenario (step S701). Here, the fault scenario is a set of fault scenarios in the case where a set of simultaneously occurring link faults is defined as one fault scenario.

[0131] On the basis of the provided data, the optimization reference generator 101 generates the objective function represented by the following expression (step S702): $\begin{array}{cc}\mathrm{Minimize}\left[\sum _{l-1}^L{\omega }_1{d}_1+ϵ\sum _{n-1}^N{e}_n\right]& \left(31\right)\end{array}$

[0132] The expression (31) means minimization of the cost concerning the links and the cost concerning the nodes.

[0133] The stochastic path accommodation condition generator 102 generates the following constraint expression for paths to accommodate the requested capacity of a demand (step S702). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{c}_{\mathrm{ips}}\le v_p\right]\ge \alpha \left(p=1,\cdots ,P,s=0,\cdots ,S\right)& \left(32\right)\end{array}$  (p=1, . . . , P, s=0, . . . ,S)  (32)

[0134] The expression (32) means that the probability that the total of capacities assigned to path candidates i_pof a demand p exceeds a requested capacity v_pof the demand p in the state s is at least α.

[0135] The link accommodation condition generator 103 generates the following constraint expression for a link to accommodate capacities assigned to paths (step S704). $\begin{array}{cc}\sum _{p-1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{c}_{\mathrm{ip}ϵ}\le \lambda d_1\left(l=1,\cdots ,L,s=0,\cdots ,S\right)& \left(33\right)\end{array}$  (1=l, . . . , L, s=0, . . . , S)  (33)

[0136] The expression (33) means that the capacity d_lof a link l exceeds the total of capacities of paths i_ppassing through the link l in a state s.

[0137] The stochastic node accommodation condition generator 104 generates the following constraint expression for a node to accommodate the capacities assigned to paths (step S705). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{l-1}^L{h}_{l/n}{d}_1+\sum _{p=1}^P{o}_{p/n}{v}_p/\lambda \le v{e}_n\right]\ge \gamma \left(n=1,\cdots ,N\right)& \left(34\right)\end{array}$  (n=1, . . . , N)  (34)

[0138] The expression (34) means that the probability that the capacity of a node n exceeds the termination capacities of the links l and the termination capacities of the demands p is at least γ.

[0139] The expression (31) of the objective function and the constraint expressions (32), (33) and (34) respectively generated by the optimization reference generator 101, the stochastic path accommodation constraint generator 102, the link accommodation constraint generator 103, and the stochastic node accommodation constraint generator 104 form a stochastic programming problem.

[0140] The equivalent determinate programming problem transformer 105 transforms this stochastic programming problem into an equivalent determinate programming problem (step S706). If it is assumed that the requested capacities v_pfollow normal distributions each of which has mean μ_pand variance σ_pand which are mutually independent, the expression (32) can be transformed as follows: $\begin{array}{cc}\sum _{\mathrm{ip}=1}^{\mathrm{Ip}}{c}_{\mathrm{ip}e}\ge {\mu }_p+t\left(\alpha \right){\sigma }_p\left(p=1,\cdots ,P,s=0,\cdots ,S\right)& \left(35\right)\end{array}$  (p=1, . . . , P, s=0, . . . , S)  (35)

[0141] where t(α) is a safety coefficient of standard normal distribution satisfying α.

[0142] In succession, the equivalent determinate programming problem transformer 105 transforms the expression (34). If it is assumed that the sum total of o_p/nv_pfor p=1, . . . , P follows a normal distribution having mean μ_nand variance σ_nand each of the requested capacities v_phas independent distribution, the mean μ_nand the variance σ_nare derived as follows: $\begin{array}{cc}{\mu }_n=\sum _{p-1}^P{o}_{p/n}{\mu }_p\left(n=1,\cdots ,N\right)& \left(36\right)\\ {\left({\sigma }_n\right)}^2=\sum _{p=1}^P{o_{p/n}\left({\sigma }_p\right)}^2\left(n=1,\cdots ,N\right)& \left(37\right)\end{array}$

[0143] By using the mean μ_nand the variance σ_n, the expression (34) can be transformed as follows: $\begin{array}{cc}v{e}_n-\sum _{l-1}^L{h}_{l/n}{d}_1\ge {\mu }_n+t\left(\gamma \right){\sigma }_n\left(n=1,\cdots ,N\right)& \left(38\right)\end{array}$  (n=1, . . . , N)  (37)

[0144] where t(γ) is a safety coefficient of standard normal distribution satisfying γ.

[0145] A linear programming problem obtained by the transformation processing conducted by the equivalent determinate programming problem transformer 109 is formed by the expression (31) of the objective function and the constraint expressions (33), (35), (36), (37) and (38). The optimization means 106 solves this linear programming problem, and obtains the capacities of respective links and the capacity of the node (step S707).

[0146] The communication network design system implements a fifth embodiment of the present invention with hardware or software. In the preferred embodiment, a network design procedure according to the fifth embodiment is implemented by a computer running a network design program thereon. The network design program according to the fifth embodiment is previously stored in a read-only memory (ROM), a magnetic storage, or the like (not shown). The basic configuration of the system for implementing the fifth embodiment is the same as in the second embodiment as shown in FIG. 4. The network design method according to the fifth embodiment is capable of coping with link faults in the second embodiment. Symbols to be used in the fifth embodiment are the same as in the fourth embodiment.

[0147] Referring to FIG. 8, as input data, the system is first provided with a network topology, demands each having a requested capacity given by probability distribution, path candidates of respective demands, cost coefficients of link/nodes, link accommodation probabilities, node accommodation probabilities, and conceivable faults (step S801).

[0148] On the basis of the provided data, the optimization reference generator 201 generates the objective function represented by the following expression (step S801): $\begin{array}{cc}\mathrm{Minimize}\left[\sum _{l=1}^L{\omega }_1{d}_1+ϵ\sum _{n=1}^N{e}_n\right]& \left(39\right)\end{array}$

[0149] The expression (39) means minimization of the cost concerning the links and the cost concerning the nodes.

[0150] The path accommodation condition generator 202 generates the following constraint expression for paths to accommodate the requested capacity of a demand (step S802). $\begin{array}{cc}\sum _{\mathrm{ip}=1}^{\mathrm{Ip}}{r}_{\mathrm{ip}e}\geqq \left(p=1,\cdots ,P,s=0,\cdots ,S\right)& \left(40\right)\end{array}$

[0151] The expression (40) represents the accommodation condition of paths. The expression (40) means that the total of capacities assigned to path candidates i_pof the demand p is at least 1 with respect to the requested capacity.

[0152] The stochastic link accommodation condition generator 203 generates the following constraint expression for a link to accommodate the capacities assigned to paths (step S804). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{p=1}^P\sum _{\mathrm{ip}=1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{v}_p{r}_{\mathrm{ip}ϵ}\le f_{1/ϵ}\lambda d_1\right]\geqq \beta \left(l=1,\cdots ,L,s=0,\cdots ,S\right)& \left(41\right)\end{array}$  (l=1, . . . , L, s=0, . . . , S)  (41)

[0153] The expression (41) means that the probability that the capacity d_lof the link l exceeds the total of capacities of paths i_ppassing through the link l in the state s is at least β.

[0154] The stochastic node accommodation condition generator 204 generates the following constraint expression for a node to accommodate capacities assigned to paths (step S805). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{l=1}^L{h}_{l/n}{d}_1+\sum _{p-1}^P{o}_{p/n}{v}_p/\lambda \le v{e}_n\right]\ge \gamma \left(n=1,\cdots ,N\right)& \left(42\right)\end{array}$  (n=1, . . . , N)  (42)

[0155] The expression (42) means that the probability that the capacity of a node n exceeds the termination capacities of the links l and the termination capacities of the demands p is at least γ.

[0156] The expression (39) of the objective function and the constraint expressions (40), (41) and (42) respectively generated by the optimization reference generator 201, the path accommodation condition generator 202, the stochastic link accommodation condition generator 203, and the stochastic node accommodation condition generator 204 form a stochastic programming problem.

[0157] The equivalent determinate programming problem transformer 205 transforms this stochastic programming problem into an equivalent determinate programming problem (step S806). If it is assumed that the requested capacities v_pfollow mutually independent normal distributions each having mean μ_pand variance σ_p, then the mean μ_land the variance σ_lof the sum total of g_ip/lv_pr_ipafor p=1, . . . , P, i_p=1, . . . , I_pcan be derived as follows: $\begin{array}{cc}{\mu }_1=\sum _{p-1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{r}_{\mathrm{ip}e}{\mu }_p\left(l=1,\cdots ,L\right)& \left(43\right)\\ {\left({\sigma }_1\right)}^2=\sum _{p=1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g_{\mathrm{ip}/1}\left(r_{\mathrm{ip}ϵ}\right)}^2{\left({\sigma }_p\right)}^2\left(l=1,\cdots ,L\right)& \left(44\right)\end{array}$  (l=1, . . . , L)  (44)

[0158] If it is now assumed that the sum total of g_ip/lv_pr_ipε for p=1, . . . , P, i=1, . . . , I_pfollows a normal distribution, the expression (41) can be transformed as follows:

[0159] λd_l≧μ_l+t(β)σ_l(l=1, . . . , L)  (45)

[0160] where t(β) is a safety coefficient of standard normal distribution satisfying β.

[0161] In succession, the equivalent determinate programming problem transformer 205 transforms the expression (42). Since the requested capacities v_pare respectively independent, the mean μ_nand the variance σ_nof the sum total of o_p/nv_pfor p=1, . . . , P derived as follows: $\begin{array}{cc}{\mu }_n=\sum _{p-1}^P{o}_{p/n}{\mu }_p\left(n=1,\cdots ,N\right)& \left(46\right)\\ {\left({\sigma }_n\right)}^2=\sum _{p-1}^P{o_{p/n}\left({\sigma }_p\right)}^2\left(n=1,\cdots ,N\right)& \left(47\right)\end{array}$

[0162] If it is assumed that the sum total of o_p/nv_pfor p=1, . . . , P follows a normal distribution, the expression (52) can be transformed as follows: $\begin{array}{cc}v{e}_n-\sum _{l-1}^L{h}_{l/n}\ge {\mu }_n+t\left(\gamma \right){\sigma }_n\left(n=1,\cdots ,N\right)& \left(48\right)\end{array}$

[0163] where t(γ) is a safety coefficient of standard normal distribution satisfying γ.

[0164] A nonlinear programming problem obtained by the transformation processing conducted by the equivalent determinate programming problem transformer 205 is formed by the expression (39) of the objective function and the constraint expressions (40), (43), (44), (45), (46), (47) and (48). The optimization section 206 solves this nonlinear programming problem, and obtains the capacities of respective links and the capacity of the node (step S807).

[0165] The communication network design system implements a sixth embodiment of the present invention with hardware or software. In the preferred embodiment, a network design procedure according to the sixth embodiment is implemented by a computer running a network design program thereon. The network design program according to the sixth embodiment is previously stored in a read-only memory (ROM), a magnetic storage, or the like (not shown). The basic configuration of the system for implementing the sixth embodiment is the same as in the second embodiment as shown in FIG. 4. The network design method according to the sixth embodiment is capable of coping with link faults in the second embodiment. Symbols to be used in the sixth embodiment are the same as in the fourth embodiment except that c_ipε is a capacity [variable of a stochastic programming problem (random variable)] assigned to a path i_pin a state s with respect to a requested capacity of a demand p.

[0166] Referring to FIG. 9, as input data, the system is first provided with a network topology, demands each having a requested capacity given by probability distribution, path candidates of the respective demands, cost coefficients of link/nodes, link accommodation probabilities, node accommodation probabilities, and conceivable faults (step S901).

[0167] On the basis of the input data, the optimization reference generator 201 generates the objective function represented by the following expression (step S902): $\begin{array}{cc}\mathrm{Minimize}\left[\sum _{l=1}^L{\omega }_1{d}_1+ϵ\sum _{n-1}^N{e}_n\right]& \left(49\right)\end{array}$

[0168] The expression (49) means minimization of the cost concerning the links and the cost concerning the nodes.

[0169] The path accommodation condition generator 202 generates the following constraint expression for paths to accommodate the requested capacity of a demand (step S903). $\begin{array}{cc}\sum _{\mathrm{ip}=1}^{\mathrm{Ip}}{c}_{\mathrm{ip}ϵ}\ge v_p\left(p=1,\cdots ,P,s=0,\cdots ,S\right)& \left(50\right)\end{array}$

[0170] The expression (50) represents the accommodation condition of paths. The expression (50) means that the total of capacities assigned to path candidates i_pof the demand p in the state s is at least the requested capacity v_pof the demand p.

[0171] The stochastic link accommodation condition generator 203 generates the following constraint expression for a link to accommodate the capacities assigned to paths (step S904). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{p-1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{c}_{\mathrm{ips}}\le \lambda f_{l/s}{d}_1\right]\ge \beta \left(l=1,\cdots ,L,s=0,\cdots ,S\right)& \left(51\right)\end{array}$  (l=1, . . . , L, s=0, . . . , S)  (51)

[0172] The expression (51) means that the probability that the capacity d_lof the link l exceeds the total of capacities of paths i_ppassing through the link l in the state s is at least β.

[0173] The stochastic node accommodation condition generator 204 generates the following constraint expression for a node to accommodate capacities assigned to paths (step S905). $\begin{array}{cc}\mathrm{Prob}\left[\sum _{l=1}^L{h}_{l/n}{d}_1+\sum _{p=1}^P{o}_{p/n}{v}_p/\lambda \le v{e}_n\right]\ge \gamma \left(n=1,\cdots ,N\right)& \left(52\right)\end{array}$

[0174] The expression (52) means that the probability that the capacity of a node n exceeds the termination capacities of the links l and the termination capacities of the demands p is at least γ.

[0175] The expression (49) of the objective function and the constraint expressions (50), (51) and (52) respectively generated by the optimization reference generator 201, the path accommodation condition generator 202, the stochastic link accommodation condition generator 203, and the stochastic node accommodation condition generator 204 form a stochastic programming problem.

[0176] The equivalent determinate programming problem transformer 205 transforms this stochastic programming problem into an equivalent determinate programming problem (step S906). If it is assumed that the requested capacities v_pfollow mutually independent normal distributions each having mean μ_pand variance σ_p, then the mean μ_ipsand the variance σ_ipsof the random variable c_ipscan be derived as follows: $\begin{array}{cc}\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{\mu }_{\mathrm{ip}ϵ}\le {\mu }_p\left(p=1,\cdots ,P,s=0,\cdots ,S\right)& \left(53\right)\\ \sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{\left({\sigma }_{\mathrm{ip}ϵ}\right)}^2={\left({\sigma }_p\right)}^2\left(p=1,\cdots ,P,s=0,\cdots ,S\right)& \left(54\right)\end{array}$  (p=1, . . . , P, s=0, . . . , S)  (54)

[0177] In succession, the equivalent determinate programming problem transformer 205 transforms the expression (51). If it is assumed that the random variables c_ipshave mutually independent distributions, the mean value μ_laand the variance value σ_lsof the sum total of g_ip/lc_ipsfor p=1, . . . , P, i_p=1, . . . , I_pcan be derived as follows: $\begin{array}{cc}{\mu }_{\mathrm{ls}}=\sum _{p-1}^P\sum _{\mathrm{ip}-1}^{\mathrm{Ip}}{g}_{\mathrm{ip}/1}{\mu }_{\mathrm{ip}ϵ}\left(p=1,\cdots ,P,s=0,\cdots ,S\right)& \left(55\right)\end{array}$ $\begin{array}{cc}{\left({\sigma }_{1ϵ}\right)}^2=\sum _{p-1}^P\sum _{\mathrm{ip}=1}^{\mathrm{Ip}}{g_{\mathrm{ip}/1}\left({\sigma }_{\mathrm{ip}ϵ}\right)}^2\left(p=1,\cdots ,P,s=0,\cdots ,S\right)& \left(56\right)\end{array}$  (p=1, . . . , P, s=0, . . . , S)  (56)

[0178] If it is assumed that the sum total of g_ipc_ipsfor p=1, . . . , P, i_p=1, . . . , I_pfollows a normal distribution, the expression (51) can be transformed as follows:

[0179] λf_l/s≧μ_ls+t(β)σ_ls(l=1, . . . , L, s=0, . . . , S)  (57)

[0180] where t(β) is a safety coefficient of standard normal distribution satisfying β.

[0181] Furthermore, If it is now assumed that each of the requested capacities v_phas an independent distribution, the mean value μ_pand the variance σ_nof the sum total of o_p/nv_pfor p=1, . . . , P are derived as follows: $\begin{array}{cc}{\mu }_n=\sum _{p-1}^P{o}_{p/n}{\mu }_p\left(n=1,\cdots ,N\right)& \left(58\right)\\ {\left({\sigma }_n\right)}^2=\sum _{p-1}^P{o_{p/n}\left({\sigma }_p\right)}^2\left(n=1,\cdots ,N\right)& \left(59\right)\end{array}$

[0182] If it is assumed that the sum total of o_p/nv_pfor p=1, . . . P follows a normal distribution, the expression (52) can be transformed as follows: $\begin{array}{cc}v{e}_n-\sum _{l-1}^L{h}_{l/n}\ge {\mu }_n+t\left(\gamma \right){\sigma }_n\left(n=1,\cdots ,N\right)& \left(60\right)\end{array}$

[0183] where t(γ) is a safety coefficient of standard normal distribution satisfying γ.

[0184] A nonlinear programming problem obtained by the transformation processing conducted by the equivalent determinate programming problem transformer 205 is formed by the expression (49) of the objective function and the constraint expressions (53), (54), (55), (56), (57), (58), (59) and (60). The optimization means 206 solves this nonlinear programming problem, and obtains the capacities of respective links and the capacity of the node (step S907).

[0185] As described above, such a stochastic programming problem as to minimize the cost under given stochastic accommodation conditions concerning capacities of paths, links and nodes is set by the optimization reference generator 101 or 201, the stochastic pass accommodation constraint generator 102 or the path accommodation condition generator 202, the link accommodation condition generator 103 or the stochastic link accommodation condition generator 203, and the stochastic node accommodation constraint generator 104 or the stochastic node accommodation condition generator 204. This stochastic programming problem is transformed to an equivalent determinate programming problem by the equivalent determinate programming problem transformer 105 or 205. The equivalent determinate programming problem is solved by the optimization section 106 or 206. As a result, it is possible to design a network which can accommodate traffics even if the traffic pattern changes to some degree and which can be constructed at a low cost.

[0186] As described above, according to the present invention a predetermined set of stochastic constraints are generated by using the requested capacity of the demand to produce a stochastic programming problem and then the stochastic programming problem is converted into an equivalent determinate programming problem on condition of the predetermined probability distribution. The determinate programming problem is solved to determine capacities of the nodes and the links so that the objective function is minimized. This brings about an effect that the traffics can be accommodated even if a demand pattern changes to some degree.