Method for designing a communication network

US 6,404,744 B1
Filed: 01/22/1999
Issued: 06/11/2002
Est. Priority Date: 01/22/1998
Status: Expired due to Fees

First Claim

Patent Images

1. A method for designing a communication network composed of a plurality of nodes and links each connecting two nodes, comprising the steps of:

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.

View all claims

2 Assignments

Timeline View

Assignment View

0 Petitions

Accused Products

Abstract

A method for designing a communication network that can cope with variations in demand pattern is disclosed. Stochastic constraints are generated by using the requested capacity of a demand to produce a stochastic programming problem. 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.

45 Citations

View as Search Results

45 Claims

1. A method for designing a communication network composed of a plurality of nodes and links each connecting two nodes, comprising the steps of:
- 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.
- View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27)
- - 2. The method according to claim 1, wherein the step c) comprises the steps of:
3. The method according to claim 2, wherein, in the step c-1), the stochastic path accommodation constraint causes a probability that a total of capacities assigned to path candidates of a demand is not smaller than the requested capacity of the demand to be at least a predetermined path accommodation probability,in the step c-2), the link accommodation constraint causes a total of capacities of path candidates passing through a link to be accommodated in the link, and in the step c-3), the stochastic node accommodation constraint causes a probability that a capacity assigned to a node exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
4. The method according to claim 3, wherein the stochastic path accommodation constraint generated in the step c-1) is represented by:
- $Prob [\sum_{i_{p} = 1}^{Ip} c_{ip} \geq v_{p}] \geq α (p = 1, \dots, P),$ whereProb [ ] represents a probability that the condition in [ ] is satisfied, p is a demand number, i_pis a candidate number of a demand p in the range of 1, . . . , I_pwhere a path candidate i_pof a demand p is an arbitrary path between an originating node and a terminating node of a demand p, c_ipis a capacity (integer variable) assigned to a path candidate i_pof a demand p, v_pis a requested capacity (random variable) of a demand p, and α
  
  is a probability (path accommodation probability) that the requested capacity v_pof a demand p is assigned to path candidates of the demand p;
  
  the link accommodation constraint generated by the step c-2) is represented by;
  
  $\sum_{p - 1}^{P} {\sum_{i}}_{p - 1}^{Ip} g_{ip / 1} c_{ip} \leq λ d_{1} (l = 1, \dots, L)$ wherel;
  
  is a link number, g_ip/lis an indicator indicating l when a path candidate i_pof a demand p passes through a link l (as represented by ip/l) and indicating 0 otherwise, d_lis a capacity (integer variable) assigned to a link l, and λ
  
  is a capacity of a link, and the stochastic node accommodation constraint generated by the step c-3) is represented by;
  
  $Prob [\sum_{l = 1}^{L} h_{l / n} d_{1} + \sum_{p = 1}^{P} o_{p / n} v_{p} / λ \leq v e_{n}] \geq γ (n = 1, \dots, N),$
  
  (n=1, . . . , N)wheren is a node number, h_l/nis an indicator indicating l when a link l passes though node n (as represented by l/n) and indicating 0 otherwise, o_p/nis an indicator indicating l when a demand p terminates at a node n (as represented by p/n) and indicating 0 otherwise, ν
  
  is a capacity of a node, e_nis a capacity (integer variable) assigned to a node n, and γ
  
  is 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.
5. The method according to claim 4, wherein the step d) comprises the steps of:
- d-1) converting the stochastic path accommodation constraint to a determinate path accommodation constraint on condition that the requested capacity of the demand follows a normal distribution having a mean μ
  
  _pand a variance σ
  
  _p, wherein the determinate path accommodation constraint is represented by;
  
  $\sum_{i_{p} = 1}^{Ip} c_{ip} \geq μ_{p} + t (α) σ_{p} (p = 1, \dots, P)$
  
  where t(α
  
  ) is a safety coefficient of a standard normal distribution satisfying α
  
  ; and
  
  d-2) converting the stochastic node accommodation constraint to a determinate node accommodation constraint on condition that a sum of o_p/nv_pfor p=1, . . . , P follows a normal distribution having a mean μ
  
  _nand a variance σ
  
  _n, wherein the mean μ
  
  _nand the variance σ
  
  _nare represented by;
  
  $μ_{n} = \sum_{p - 1}^{P} o_{p / n} μ_{p} (n = 1, \dots, N) {and (σ_{n})}^{2} = \sum_{p - 1}^{P} {o_{p / n} (σ_{p})}^{2} (n = 1, \dots, N), respectively,$
  
  and the determinate node accommodation constraint is represented by;
  
  $v e_{n} - \sum_{l - 1}^{L} h_{l / n} d \geq μ_{n} + t (γ) σ_{n} (n = 1, \dots, N),$
  
  (n=1, . . . , N), where t(γ
  
  ) is a safety coefficient of a standard normal distribution satisfying γ
  
  .
6. The method according to claim 5, wherein the equivalent determinate programming problem consists of:
- the objective function represented by;
  
  $\sum_{l = 1}^{L} ω_{1} d_{1} + ɛ \sum_{n = 1}^{N} e_{n}$
  
  where ω
  
  _lis a cost coefficient of a link l and ε
  
  is a cost coefficient of a node, and the determinate constraints consisting of;
  
  the determinate path accommodation constraint represented by;
  
  $\sum_{i_{p} - 1}^{Ip} c_{ip} \geq μ_{p} + t (α) σ_{p} (p = 1, \dots, P),$ the link accommodation constraint represented by;
  
  $\sum_{p = 1}^{P} \sum_{i_{p} - 1}^{Ip} g_{ip / 1} c_{lp} \leq λ d_{1} (1 = 1, \dots, L), and$ the determinate node accommodation constraint represented by;
  
  $v e_{n} - \sum_{l = 1}^{L} h_{l / n} d_{1} \geq μ_{n} + t (γ) σ_{n} (n = 1, \dots, N) .$
7. The method according to claim 1, wherein the step c) comprises 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.
8. The method according to claim 7, wherein,in the step c-1), the path accommodation constraint causes a total of ratios of capacities assigned to path candidates of a demand to be at least 1 when it is assumed that the requested capacity of the demand is 1, in the step c-2), the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds the total of capacities of path candidates passing through the link to be at least a predetermined link accommodation probability, and in the step c-3), the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
9. The method according to claim 8, wherein the path accommodation constraint generated in the step c-1) is represented by:
- $\sum_{ip = 1}^{Ip} r_{ip} ≧ 1 (p = 1, \dots, P)$ wherep is a demand number, i_pis 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, and r_ipis a ratio (real number variable) assigned to a path candidate i_pwhen it is assumed that a requested capacity of a demand p is l, the stochastic link accommodation constraint generated by the step c-2) is represented by;
  
  $Prob [\sum_{p - 1}^{P} \sum_{ip - 1}^{Ip} g_{ip / 1} v_{p} r_{ip} \leq λ d_{1}] \geq β$
  
  (l=1, . . . , L)whereProb [ ] represents a probability that the condition in [ ] is satisfied. l;
  
  a link number, g_ip/lis an indicator indicating l when a path candidate i_pof a demand p passes through a link l (as represented by ip/l) and indicating 0 otherwise, d₁is a capacity (integer variable) assigned to a link l, λ
  
  is a capacity of a link, v_pis a requested capacity (random variable) of a demand p, and β
  
  ;
  
  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, and the stochastic node accommodation constraint generated by the step c-3) is represented by;
  
  $Prob [\sum_{l - 1}^{L} h_{l / n} d_{1} + \sum_{p - 1}^{P} o_{p / n} v_{p} / λ \leq v e_{n}] \geq γ$
  
  (n=1, . . . , N)wheren is a node number, h_l/nis an indicator indicating l when a link l passes though node n (as represented by l/n) and indicating 0 otherwise, o_p/nis an indicator indicating l when a demand p terminates at a node n (as represented by p/n) and indicating 0 otherwise, ν
  
  is a capacity of a node, e_nis a capacity (integer variable) assigned to a node n, and γ
  
  is 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.
10. The method according to claim 9, wherein the step d) comprises the steps of:
- d-1) converting the stochastic link accommodation constraint to a determinate link accommodation constraint on condition that the requested capacity of the demand follows a normal distribution having a mean μ
  
  _pand a variance σ
  
  _p, and a sum of g_ip/lv_pr_ipfor p=1, . . . , P, i=1, . . . , i_pis follows probability distribution having a mean μ
  
  _land a variance a σ
  
  _lthat are represented by;
  
  $μ_{1} = \sum_{p - 1}^{P} \sum_{ip - 1}^{Ip} g_{ip / 1} r_{lp} μ_{p} (l = 1, \dots, L) {and (σ_{1})}^{2} = \sum_{p = 1}^{P} \sum_{ip - 1}^{Ip} {g_{ip / 1} (r_{ip})}^{2} {(σ_{p})}^{2} (l = 1, \dots, L),$ respectively, and further on condition that a sum of g_ip/lv_pr_ipfor p=1, . . . , P, i_p=1, . . . , I_pfollows a normal distribution,wherein the determinate link accommodation constraint is represented by;
11. The method according to claim 10, wherein the equivalent determinate programming problem consists of:
- the objective function represented by;
  
  $\sum_{l = 1}^{L} ω_{1} d_{1} + ɛ \sum_{n = 1}^{N} e_{n}$ where ω
  
  _lis a cost coefficient of a link l and ε
  
  is a cost coefficient of a node, and the determinate constraints consisting of;
  
  the path accommodation constraint represented by;
  
  $\sum_{ip - 1}^{Ip} r_{ip} ≧ 1 (p = 1, \dots, P),$ the determinate link accommodation constraint represented by;
12. The method according to claim 7, wherein,in the step c-1), the path accommodation constraint causes a total of capacities assigned to path candidates of a demand to be at least the requested capacity of the demand, in the step c-2), the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds a total of capacities of paths passing through the link to be at least a predetermined link accommodation probability, and in the step c-3), the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
13. The method according to claim 12, wherein the path accommodation constraint generated in the step c-1) is represented by:
- $\sum_{ip - 1}^{Ip} c_{lp} ≧ v_{p} (p = 1, \dots, P),$ wherep is a demand number, i_pis 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, c_ipis a capacity as a random variable assigned to a path candidate i_p, and v_pis a requested capacity (random variable) of a demand p, the stochastic link accommodation constraint generated by the step c-2) is represented by;
  
  $Prob [\sum_{p - 1}^{P} \sum_{ip = 1}^{Ip} g_{ip / 1} v_{p} r_{ip} \leq λ d_{1}] \geq β (l = 1, \dots, L)$ whereProb [ ] represents a probability that the condition in [ ] is satisfied, l;
  
  a link number, g_ip/lis an indicator indicating l when a path candidate i_pof a demand p passes through a link l (as represented by ip/l) and indicating 0 otherwise, d_lis a capacity (integer variable) assigned to a link λ
  
  is a capacity of a link, v_pis a requested capacity (random variable) of a demand p, and r_ipis a ratio (real number variable) assigned to a path candidate i_pwhen it is assumed that a requested capacity of a demand p is l, β
  
  ;
  
  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, and the stochastic node accommodation constraint generated by the step c-3) is represented by;
  
  $Prob [\sum_{l = 1}^{L} h_{l / n} d_{1} + \sum_{p = 1}^{P} o_{p / n} v_{p} / λ \leq ν e_{n}] \geq γ (n = 1, \dots, N)$ wheren is a node number, h_l/nis an indicator indicating l when a link l passes though node n (as represented by l/n) and indicating 0 otherwise, o_p/nis an indicator indicating l when a demand p terminates at a node n (as represented by p/n) and indicating 0 otherwise, ν
  
  is a capacity of a node, e_nis a capacity (integer variable) assigned to a node n, and γ
  
  is 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.
14. The method according to claim 13, wherein the step d) comprises the steps of:
- d-1) converting the stochastic link accommodation constraint to a determinate link accommodation constraint on condition that the requested capacity of the demand follows a normal distribution having a mean μ
  
  _pand a variance σ
  
  _p, wherein a mean μ
  
  _ipand a variance σ
  
  _ipof a random variable c_ipis represented by;
  
  $\sum_{ip - 1}^{Ip} μ_{ip} = μ_{p} (p = 1, \dots, P) and$ $\sum_{ip - 1}^{Ip} {(σ_{ip})}^{2} = {(σ_{p})}^{2} (p = 1, \dots, P), respectively, and$
  
  a sum of g_ip/lv_pr_ipfor p=1, . . . , P and i_p=1, . . . , I_pfollows a probability distribution having a mean μ
  
  _land a variance σ
  
  _lthat are represented by;
  
  $μ_{1} = \sum_{p - 1}^{P} \sum_{ip = 1}^{Ip} g_{ip / 1} μ_{lp} (l = 1, \dots, L) {and (σ_{1})}^{2} = \sum_{p - 1} \sum_{ip = 1}^{Ip} {g_{ip / 1} (σ_{ip})}^{2} (l = 1, \dots, L), respectively,$
  
  and further on condition that a sum of g_ip/lv_pr_ipfor p=1, . . . , P and i_p=1, . . . , I_pfollows a normal distribution, wherein the determinate link accommodation constraint is represented by;
15. The method according to claim 14, wherein the equivalent determinate programming problem consists of:
- the objective function represented by;
  
  $\sum_{l - 1}^{L} ω_{1} d_{1} + ɛ \sum_{n - 1}^{N} e_{n}$ where ω
  
  _lis a cost coefficient of a link l and ε
  
  is a cost coefficient of a node, and the determinate constraints consisting of;
  
  the path accommodation constraint represented by;
  
  $\sum_{ip = 1}^{Ip} c_{ip} ≧ v_{p} (p = 1, \dots, P),$ the determinate link accommodation constraint represented by;
  
  λ
  
  d_l≧
  
  μ
  
  _l+t(β
  
  )σ
  
  _l(l=1, . . . , L)andthe determinate node accommodation constraint represented by;
  
  $ν e_{n} - \sum_{l - 1}^{L} h_{l / n} d_{1} \geq μ_{n} + t (γ) σ_{n} (n = 1, \dots, N) .$
16. The method according to claim 2, wherein,in the step c-1), the stochastic path accommodation constraint causes a probability that a total of capacities assigned to path candidates of a demand in a network state is not smaller than the requested capacity of the demand to be at least a predetermined path accommodation probability, wherein the network state indicates one of a normal state and fault states for some link, in the step c-2), the link accommodation constraint causes a total of capacities of path candidates passing through a link in the network state to be accommodated in the link, and in the step c-3), the stochastic node accommodation constraint causes a probability that a capacity assigned to a node exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
17. The method according to claim 16, wherein the stochastic path accommodation constraint generated in the step c-1) is represented by:
- $Prob [\sum_{i_{p} - 1}^{Ip} c_{ip ɛ} \geq v_{p}] \geq α (p = 1, \dots, P, and s = 0, \dots, S),$ whereProb [ ] represents a probability that the condition in [ ] is satisfied, p is a demand number, i_pis 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, s is 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, c_ipε;
  
  a capacity (integer variable) assigned to a path i_pof a demand p in a state s, v_pis a requested capacity (random variable) of a demand p, and α
  
  is a probability (path accommodation probability) that the requested capacity v_pof a demand p is assigned to path candidates of the demand p;
  
  the link accommodation constraint generated by the step c-2) is represented by;
  
  $\sum_{p - 1}^{P} \sum_{i_{p} - 1}^{Ip} g_{ip / 1} c_{ip ɛ} \leq λ d_{1} (l = 1, \dots, L, and s = 0, \dots, S)$
  
  (l=1, . . . , L, and s=0, . . . , S)wherel;
  
  a link number, g_ip/lis an indicator indicating l when a path candidate i_pof a demand p passes through a link l (as represented by ip/l) and indicating 0 otherwise, d_lis a capacity (integer variable) assigned to a link l, and λ
  
  is a capacity of a link, and the stochastic node accommodation constraint generated by the step c-3) is represented by;
  
  $Prob [\sum_{l = 1}^{L} h_{l / 1} d_{1} + \sum_{p = 1}^{P} o_{p / n} v_{p} / λ \leq ν e_{n}] \geq γ (n = 1, \dots, N)$ wheren is a node number, h_l/nis an indicator indicating l when a link l passes though node n (as represented by l/n) and indicating 0 otherwise, o_p/nis an indicator indicating l when a demand p terminates at a node n (as represented by p/n) and indicating 0 otherwise, 84 is a capacity of a node, e_nis a capacity (integer variable) assigned to a node n, and γ
  
  is 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.
18. The method according to claim 17, wherein the step d) comprises the steps of:
- d-1) converting the stochastic path accommodation constraint to a determinate path accommodation constraint on condition that the requested capacity of the demand follows a normal distribution having a mean μ
  
  _pand a variance σ
  
  _p, wherein the determinate path accommodation constraint is represented by;
  
  $\sum_{i_{p} = 1}^{Ip} c_{ip ɛ} \geq μ_{p} + t (α) σ_{p} (p = 1, \dots, P, s = 0, \dots, S)$
  
  where t(α
  
  ) is a safety coefficient of a standard normal distribution satisfying α
  
  ; and
  
  d-2) converting the stochastic node accommodation constraint to a determinate node accommodation constraint on condition that a sum of o_p/nv_pfor p=1, . . . , P follows a normal distribution having a mean μ
  
  _nand a variance σ
  
  _n, wherein the mean μ
  
  _nand the variance σ
  
  _nare represented by;
  
  $μ_{n} = \sum_{p - 1}^{P} o_{p / n} μ_{p} (n = 1, \dots, N) {and (σ_{n})}^{2} = \sum_{p = 1}^{P} {o_{p / n} (σ_{p})}^{2} (n = 1, \dots, N), respectively,$ and the determinate node accommodation constraint is represented by;
  
  $ν e_{n} - \sum_{l - 1}^{L} h_{l / n} d_{1} \geq μ_{n} + t (γ) σ_{n} (n = 1, \dots, N),$
  
  (n=1, . . . , N),where t(γ
  
  ) is a safety coefficient of a standard normal distribution satisfying γ
  
  .
19. The method according to claim 18, wherein the equivalent determinate programming problem consists of:
- the objective function represented by;
  
  $\sum_{l - 1}^{L} ω_{1} d_{1} + ɛ \sum_{n - 1}^{N} e_{n}$ where ω
  
  _lis a cost coefficient of a link l and ε
  
  is a cost coefficient of a node, and the determinate constraints consisting of;
  
  the determinate path accommodation constraint represented by;
  
  $\sum_{i_{p} = 1}^{Ip} c_{ipe} \geq μ_{p} + t (α) σ_{p} (p = 1, \dots, P, s = 0, \dots, S),$ the link accommodation constraint represented by;
  
  $\sum_{p - 1}^{P} \sum_{i_{p} = 1}^{Ip} g_{ip / 1} c_{ip} \leq λ d_{1} (l = 1, \dots, L, and s = 0, \dots, S), and$ the determinate node accommodation constraint represented by;
  
  $ν e_{n} = \sum_{l - 1}^{L} h_{l / n} d_{1} \geq μ_{n} + t (γ) σ_{n} (n = 1, \dots, N) .$
20. The method according to claim 7, wherein,in the step c-1), the path accommodation constraint causes a total of ratios of capacities assigned to path candidates of a demand to be at least l when it is assumed that the requested capacity of the demand is 1, in the step c-2), the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds the total of capacities of path candidates passing through the link in a network state to be at least a predetermined link accommodation probability, wherein the network state indicates one of a normal state and fault states for some link, and in the step c-3), the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
21. The method according to claim 20, wherein the path accommodation constraint generated in the step c-1) is represented by:
- $\sum_{ip = 1}^{Ip} r_{ip ɛ} ≧ 1 (p = 1, \dots, P)$ wherep is a demand number, i_pis 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, r_ipsis a ratio (real number variable) assigned to a path candidate i_pwhen it is assumed that the requested capacity of a demand p is l in a state s, and s is 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, the stochastic link accommodation constraint generated by the step c-2) is represented by;
  
  $Prob [\sum_{p - 1}^{P} \sum_{ip = 1}^{Ip} g_{ip / 1} v_{p} r_{ip ɛ} \leq f_{l / s} λ d_{1}] \geq β$
  
  (l=1, . . . , L, and s=0, . . . , S)
  
  where Prob [ ] represents a probability that the condition in [ ] is satisfied, l is a link number, g_ip/lis an indicator indicating l when a path candidate i_pof a demand p passes through a link l (as represented by ip/l) and indicating 0 otherwise, d_lis a capacity (integer variable) assigned to a link l, f_l/ε is an indicator indicating 0 when a link l is faulty, and indicating l when the link l is normal, wherein in the normal state represented as s=0, f_l/ε=1 in every link l. λ
  
  is a capacity of a link, v_pis a requested capacity (random variable) of a demand p, and β
  
  ;
  
  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, and the stochastic node accommodation constraint generated by the step c-3) is represented by;
  
  $Prob [\sum_{l - 1}^{L} h_{l / n} d_{1} + \sum_{p - 1}^{P} o_{p / n} v_{p} / λ \leq ν e_{n}] \geq γ (n = 1, \dots, N)$
  
  (n=1, . . . , N)wheren is a node number, h_l/nis an indicator indicating l when a link l passes though node n (as represented by l/n) and indicating 0 otherwise, o_p/nis an indicator indicating l when a demand p terminates at a node n (as represented by p/n) and indicating 0 otherwise, ν
  
  is a capacity of a node, e_nis a capacity (integer variable) assigned to a node n, and γ
  
  is 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.
22. The method according to claim 21, wherein the step d) comprises the steps of:
- d-1) converting the stochastic link accommodation constraint to a determinate link accommodation constraint on condition that the requested capacity of the demand follows a normal distribution having a mean μ
  
  _pand a variance σ
  
  _p, and a sum of g_ip/lv_pr_ipsfor p=1, . . . , P, i=1, . . . , i_pfollows probability distribution having a mean μ
  
  _land a variance σ
  
  _lthat are represented by;
  
  $μ_{1} = \sum_{p - 1}^{P} \sum_{ip - 1}^{Ip} g_{ip / 1} r_{ip ɛ} μ_{p} (l = 1, \dots, L) {and (σ_{1})}^{2} = \sum_{p - 1}^{P} \sum_{ip - 1}^{Ip} {g_{ip / 1} (r_{ip ɛ})}^{2} {(σ_{p})}^{2} (l = 1, \dots, L),$ respectively, and further on condition that a sum of g_ip/lv_pr_ipsfor p=1, . . . , P, i_p=1, . . . , I_pfollows a normal distribution,wherein the determinate link accommodation constraint is represented by;
23. The method according to claim 22, wherein the equivalent determinate programming problem consists of:
- the objective function represented by;
  
  $\sum_{l - 1}^{L} ω_{1} d_{1} + ɛ \sum_{n - 1}^{N} e_{n}$ where ω
  
  _lis a cost coefficient of a link l and ε
  
  is a cost coefficient of a node, and the determinate constraints consisting of;
  
  the path accommodation constraint represented by;
  
  $\sum_{ip = 1}^{Ip} r_{ips} ≧ 1 (p = 1, \dots, P, and s = 0, \dots, S),$ the determinate link accommodation constraint represented by;
  
  λ
  
  d_l≧
  
  μ
  
  _l+t(β
  
  )σ
  
  _l(l=1, . . . , L),andthe determinate node accommodation constraint represented by;
  
  $ν e_{n} - \sum_{l = 1}^{L} h_{l / n} d_{1} \geq μ_{n} + t (γ) σ_{n} (n = 1, \dots, N) .$
24. The method according to claim 7, wherein,in the step c-1), the path accommodation constraint causes a total of capacities assigned to path candidates of a demand in a network state to be at least the requested capacity of the demand, wherein indicates one of a normal state and fault states for some link, in the step c-2), the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds a total of capacities of paths passing through the link in the network state to be at least a predetermined link accommodation probability, and in the step c-3), the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
25. The method according to claim 24, wherein the path accommodation constraint generated in the step c-1) is represented by:
- $\sum_{ip = 1}^{Ip} c_{ip ɛ} ≧ v_{p} (p = 1, \dots, P) .$ wherep is a demand number, i_pis 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, s is 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, c_ips;
  
  a capacity (integer variable) assigned to a path i_pof a demand p in a state s, and v_pis a requested capacity (random variable) of a demand the stochastic link accommodation constraint generated by the step c-2) is represented by;
  
  $Prob [\sum_{p = 1}^{P} \sum_{ip - 1}^{Ip} g_{ip / 1} c_{ip ɛ} \leq f_{1 / s} λ d_{1}] \geq β (l = 1, \dots, L, and s = 0, \dots, S)$
  
  (l=1, . . . , L, and s=0, . . . , S)whereProb [ ] represents a probability that the condition in [ ] is satisfied, l;
  
  a link number, g_ip/lis an indicator indicating 1 when a path candidate i_pof a demand p passes through a link l (as represented by ip/l) and indicating 0 otherwise, d_lis a capacity (integer variable) assigned to a link l, f_l/sis an indicator indicating 0 when a link l is faulty, and indicating l when the link l is normal, wherein in the normal state represented as s=0, f_l/s=1 in every link l, λ
  
  is a capacity of a link, β
  
  ;
  
  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, and the stochastic node accommodation constraint a generated by the step c-3) is represented by;
  
  $Prob [\sum_{l - 1}^{L} h_{l / n} d_{1} + \sum_{p - 1}^{P} o_{p / n} v_{p} / λ \leq ν e_{n}] \geq γ (n = 1, \dots, N)$ wheren is a node number, h_l/nis an indicator indicating l when a link l passes though node n (as represented by l/n) and indicating 0 otherwise, o_p/nis an indicator indicating l when a demand p terminates at a node n (as represented by p/n) and indicating 0 otherwise, ν
  
  is a capacity of a node, e_nis a capacity (integer variable) assigned to a node n, and γ
  
  is 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.
26. The method according to claim 25, wherein the step d) comprises the steps of:
- d-1) converting the stochastic link accommodation constraint to a determinate link accommodation constraint on condition that the requested capacity of the demand follows a normal distribution having a mean μ
  
  _pand a variance σ
  
  _p, wherein a mean μ
  
  _ipaand a variance a σ
  
  _ipε of a random variable c_ipsis represented by;
  
  $\sum_{ip = 1}^{Ip} μ_{ip ɛ} = μ_{p} (p = 1, \dots, P and s = 0, \dots, S)$ $and$ $\sum_{ip - 1}^{Ip} {(σ_{ip ɛ})}^{2} = {(σ_{p})}^{2} (p = 1, \dots, P and s = 0, \dots, S),$ respectively, and a sum of g_ip/lc_ipsfor p=1, . . . , P and i_p=1, . . . , I_pfollows a probability distribution having a mean μ
  
  _lsand a variance σ
  
  _lε that are represented by;
  
  $μ_{1 c} = \sum_{p = 1}^{P} \sum_{ip - 1}^{Ip} g_{ip / 1} μ_{ip ɛ} (l = 1, \dots, L and s = 0, \dots, S)$ ${and (σ_{1})}^{2} = \sum_{p - 1}^{P} \sum_{ip = 1}^{Ip} {(g_{ip / 1} (σ_{ip ɛ}))}^{2}$ (l=1, . . . , L and s=0, . . . , S), respectively, and further on condition that a sum of g_ip/lc_ipsfor p=1, . . . , P and i_p=1, . . . , I_pfollows a normal distribution, wherein the determinate link accommodation constraint is represented by;
27. The method according to claim 26, wherein the equivalent determinate programming problem consists of:
- the objective function represented by;
  
  $\sum_{l - 1}^{L} ω_{1} d_{1} + ɛ \sum_{n - 1}^{N} e_{n}$ where ω
  
  _lis a cost coefficient of a link l and ε
  
  is a cost coefficient of a node, and the determinate constraints consisting of;
  
  the path accommodation constraint represented by;
  
  $\sum_{ip = 1}^{Ip} c_{ips} ≧ v_{p} (p = 1, \dots, P and s = 0, \dots, S),$ the determinate link accommodation constraint represented by;

28. A system for designing a communication network composed of a plurality of nodes and links each connecting two nodes, comprising:
- an input means for 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;
  
  a first generator for generating an objective function representing a total cost of the nodes and the links from the network data;
  
  a second generator for 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;
  
  a converter for converting the stochastic programming problem into an equivalent determinate programming problem on condition of the predetermined probability distribution; and
  
  an optimizing means for solving the determinate programming problem to determine capacities of the nodes and the links so that the objective function is minimized.
- View Dependent Claims (29, 30, 31, 32, 33, 34, 35, 36)
- - 29. The system according to claim 28, wherein the second generator generates a stochastic path accommodation constraint for causing the requested capacity of the demand to be accommodated in the path candidates, generates a link accommodation constraint for causing capacities assigned to path candidates to be accommodated in the links, and generates a stochastic node accommodation constraint for causing a total of capacities of path candidates passing through a node to be accommodated in the node.
  - 30. The system according to claim 29, wherein
- 31. The system according to claim 28, wherein the second generator generates a path accommodation constraint for causing the requested capacity of the demand to be accommodated in the path candidates, generates a stochastic link accommodation constraint for causing capacities assigned to path candidates to be accommodated in the links, and generates a stochastic node accommodation constraint for causing a total of capacities of path candidates passing through a node to be accommodated in the node.
- 32. The system according to claim 31, wherein,the path accommodation constraint causes a total of ratios of capacities assigned to path candidates of a demand to be at least 1 when it is assumed that the requested capacity of the demand is 1, the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds the total of capacities of path candidates passing through the link to be at least a predetermined link accommodation probability, and the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
- 33. The system according to claim 31, wherein,the path accommodation constraint causes a total of capacities assigned to path candidates of a demand to be at least the requested capacity of the demand, the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds a total of capacities of paths passing through the link to be at least a predetermined link accommodation probability, and the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
- 34. The system according to claim 29, wherein,the stochastic path accommodation constraint causes a probability that a total of capacities assigned to path candidates of a demand in a network state is not smaller than the requested capacity of the demand to be at least a predetermined path accommodation probability, wherein the network state indicates one of a normal state and fault states for some link, the link accommodation constraint causes a total of capacities of path candidates passing through a link in the network state to be accommodated in the link, and the stochastic node accommodation constraint causes a probability that a capacity assigned to a node exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
- 35. The system according to claim 31, wherein,the path accommodation constraint causes a total of ratios of capacities assigned to path candidates of a demand to be at least 1 when it is assumed that the requested capacity of the demand is 1, the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds the total of capacities of path candidates passing through the link in a network state to be at least a predetermined link accommodation probability, wherein the network state indicates one of a normal state and fault states for some link, and the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
- 36. The system according to claim 31, wherein,the path accommodation constraint causes a total of capacities assigned to path candidates of a demand in a network state to be at least the requested capacity of the demand, wherein indicates one of a normal state and fault states for some link, the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds a total of capacities of paths passing through the link in the network state to be at least a predetermined link accommodation probability, and the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.

37. A recording medium storing a network designing control program which causes a computer to designing a communication network composed of a plurality of nodes and links each connecting two nodes, the network designing control program comprising the steps of:
- 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.
- View Dependent Claims (38, 39, 40, 41, 42, 43, 44, 45)
- - 38. The recording medium according to claim 37, wherein the step c) comprises the steps of:
39. The recording medium according to claim 38, whereinthe stochastic path accommodation constraint causes a probability that a total of capacities assigned to path candidates of a demand is not smaller than the requested capacity of the demand to be at least a predetermined path accommodation probability, the link accommodation constraint causes a total of capacities of path candidates passing through a link to be accommodated in the link, and the stochastic node accommodation constraint causes a probability that a capacity assigned to a node exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
40. The recording medium according to claim 37, wherein the step c) comprises the steps of:
- generating a path accommodation constraint for causing the requested capacity of the demand to be accommodated in the path candidates;
  
  generating a stochastic link accommodation constraint for causing capacities assigned to path candidates to be accommodated in the links; and
  
  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.
41. The recording medium according to claim 40, wherein,the path accommodation constraint causes a total of ratios of capacities assigned to path candidates of a demand to be at least 1 when it is assumed that the requested capacity of the demand is 1, the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds the total of capacities of path candidates passing through the link to be at least a predetermined link accommodation probability, and the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
42. The recording medium according to claim 40, wherein,the path accommodation constraint causes a total of capacities assigned to path candidates of a demand to be at least the requested capacity of the demand, the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds a total of capacities of paths passing through the link to be at least a predetermined link accommodation probability, and the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
43. The recording medium according to claim 38, wherein,the stochastic path accommodation constraint causes a probability that a total of capacities assigned to path candidates of a demand in a network state is not smaller than the requested capacity of the demand to be at least a predetermined path accommodation probability, wherein the network state indicates one of a normal state and fault states for some link, the link accommodation constraint causes a total of capacities of path candidates passing through a link in the network state to be accommodated in the link, and the stochastic node accommodation constraint causes a probability that a capacity assigned to a node exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
44. The recording medium according to claim 40, wherein,the path accommodation constraint causes a total of ratios of capacities assigned to path candidates of a demand to be at least 1 when it is assumed that the requested capacity of the demand is 1, the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds the total of capacities of path candidates passing through the link in a network state to be at least a predetermined link accommodation probability, wherein the network state indicates one of a normal state and fault states for some link, and the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.
45. The recording medium according to claim 40, wherein,the path accommodation constraint causes a total of capacities assigned to path candidates of a demand in a network state to be at least the requested capacity of the demand, wherein indicates one of a normal state and fault states for some link, the stochastic link accommodation constraint causes a probability that a capacity of a link exceeds a total of capacities of paths passing through the link in the network state to be at least a predetermined link accommodation probability, and the stochastic node accommodation constraint causes a probability that a node capacity exceeds a total of termination capacity of a link and termination capacity of the demand to be at least a predetermined node accommodation probability.

Specification

Resources

Litigation Campaign Assessment

Current Assignee
Juniper Networks Incorporated
Original Assignee
NEC Corporation
Inventors
Saito, Hiroyuki
Primary Examiner(s)
Ngo, Ricky
Assistant Examiner(s)
TRAN, PHUC H

Application Number

US09/235,733
Time in Patent Office

1,236 Days
Field of Search

370/254, 370/255, 370/468, 370/257, 370/258, 370/352, 370/353, 370/354, 370/355, 370/356, 370/400, 370/401, 370/464, 370/465, 370/546, 370/901, 370/908, 370/912, 370/351, 703/1, 703/2, 716/1, 716/12, 716/14, 709/220, 345/733, 345/734, 345/735
US Class Current

370/255
CPC Class Codes

H04L 41/0896   Bandwidth or capacity manag...

H04L 41/142   using statistical or mathem...

H04L 41/145   involving simulating, desig...

Method for designing a communication network

First Claim

2 Assignments

0 Petitions

Accused Products

Abstract

45 Citations

45 Claims

Specification

Solutions

Use Cases

Quick Links

Method for designing a communication network

First Claim

2 Assignments

Subscription Required

Subscription Required

0 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

45 Citations

45 Claims

Specification

Subscription Required

Solutions

Use Cases

Quick Links