Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1999-01-22
2002-06-11
Ngo, Ricky (Department: 2664)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
C370S257000, C370S351000, C709S220000
Reexamination Certificate
active
06404744
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
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.
2. Description of Related Art
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
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.
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.
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.
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.
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.
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.
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.
SUMMARY OF THE INVENTION
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.
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.
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.
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.
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.
REFERENCES:
patent: 5508999 (1996-04-01), Cox, Jr. et al.
patent: 5831610 (1998-11-01), Tonelli et al.
patent: 6141318 (2000-10-01), Miyao
patent: 6185193 (2001-02-01), Kawakami et al.
patent: 6223220 (2001-04-01), Blackwell et al.
patent: 6330005 (2001-12-01), Tonelli et al.
“Restoration Strategies and Spare Capacity Requirements in Self-Healing ATM Networks”, by Yijun Xiong, et al., Infocom '97, Apr. 1997.
NEC Corporation
Ngo Ricky
Scully Scott Murphy & Presser
Tran Phuc
LandOfFree
Method for designing a communication network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for designing a communication network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for designing a communication network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2973854