Data processing: artificial intelligence – Neural network – Learning task
Reexamination Certificate
1999-12-20
2002-10-15
Davis, George B. (Department: 2121)
Data processing: artificial intelligence
Neural network
Learning task
C706S021000
Reexamination Certificate
active
06466925
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates to a method for simulation of communication systems and networks of such systems. The technique is based on the use of importance sampling and aims to speed up the process of simulating so called rare events.
DESCRIPTION OF RELATED ART
Simulation of communication systems and networks of such systems is an area of increasing importance. Simulation is normally used in order to find out the behavior and performance bottlenecks before product design, but also for real time network configurations and performance predictions to maintain, administer and optimize network resources. These simulations take a number of traffic sources of varying statistical models as input to the system. The aim is to analyze performance metrics of such systems in terms of e.g. time delays, delay variations, loss or corruption of data or probability to enter a certain state. The statistical nature of the traffic sources implies that the focus of such studies is in what a skilled person in the art would refer to as rare events. To capture such rare events with an acceptable confidence, however, requires very long simulation times unless the problem is transformed in some way.
Importance sampling is a known technique to speed up the simulations very much. In order to achieve that, it is necessary to “bias” the statistics of the traffic sources. To find optimal such biases, however, is a very time consuming process, taking longer time than the actual importance sampling itself. Although the net result is still much faster than ordinary simulation, the difficulty of importance sampling lies in obtaining good biases.
In the simulation of a communication system (or element), traffic sources and other random inputs of the system are modeled by properly chosen stochastic processes. Parameters of such stochastic processes are set so that the processes mimic the desired behaviour of the corresponding (real or assumed) traffic sources as close as possible. In conventional simulation the system model is executed with the fitted processes until sufficient amount of statistical data has been collected, enough to estimate performance parameters with the desired precision. The simulation time required to achieve that precision can, however, become prohibitively long when the estimated parameter involves some rare events.
In importance sampling (IS) simulation, the fitted stochastic processes are artificially altered such that the time between rare events can be substantially reduced. To compensate for the alteration of the inputs, proper statistical adjustments of the simulation outcomes are applied during and after the simulation in a way that the resulting estimates remain statistically correct (unbiased).
As of today, one of the crucial problems of IS remains, and that is how to alter the input processes to achieve sufficient speedup, thus reducing the simulation time from “prohibitively long” to “feasible”. The simulation must not either be too short since the variance then becomes too big to properly reflect actual scenarios. There are several scientifically interesting approaches presented in the literature, but only a few of them can be considered general enough to be considered for practical implementation. The most promising approaches are based on so called parametric biasing, where a systematic alteration of all involved sources are performed according to some functions of very few (typically one or two) key parameters, also called bias parameters. In such an approach, finding the optimal alteration of the inputs is reduced to finding the optimal values of the bias parameters. The parametric biasing approach can be found in e.g. M. Devetsikiotis and J. K. Townsend, “Statistical Optimization of Dynamic Importance Sampling Parameters for Efficient Simulation of Communication Networks”, IEEE/ACM Trans. Networking, Vol. 1, No. 3, pp. 293-305, June 1993. Another piece of prior art is to be found in Q. Wang and V. S. Frost, “Efficient Estimation of Cell Blocking Probability for ATM Systems”, IEEE/ACM Trans. Networking, Vol. 1, No. 2, pp. 230-235, 1993.
To search for optimal bias parameters, a statistical optimization based on short repetitive simulations is suggested in M. Devetsikiotis article. Finally, when an optimal setting is found, a longer simulation with the optimally set importance sampling parameters is run to generate data for the final estimate in order to get the so called “target parameters”, i.e. the wanted parameters of interest.
To obtain large speed-up factors in simulation run time using importance sampling, the modification or bias of underlying probability measures must be carefully chosen. Analytically or numerically minimizing the variance of the simulation result with respect to the biasing parameters or finding the optimal exponential change of measure is only possible under certain conditions. Optimization of the bias parameters requires today typically two orders of magnitude more simulation cycles than the final run (with the optimal parameters) to get the target estimates. Therefore, the great possibility of reducing the total time for a successful simulation lies in reducing the time spent in optimizing the bias parameters.
Today, no reliable and efficient solutions to that problem exist.
SUMMARY
The problem addressed in this invention is therefore not to find what bias parameters to be used, but rather how to find an effective bias scheme with optimal bias parameters in a much faster way than what is hitherto done and then use them in the final simulation. It could be described as a rapid way of mathematically trying to find the right alteration of the input parameters in order thereafter to perform an accurate and adequate simulation. These alterations should of course imply that the time between rare events is significantly reduced.
Slow simulation methods will in the end affect end users if not, as a result, the communication system is adequately tested in every aspect. When the customer runs the system in real time the parameters in system components must be predicted so to e.g. guarantee certain QoS for different types of traffic.
Some observations have been made which motivated the invention:
Optimization of the bias parameters requires today typically two orders of magnitude more simulation cycles than the final run (with the optimal parameters) to get the target estimates.
Importance sampling accepts a certain tolerance in the precision of the bias parameters i.e. the close neighbourhood of the optimal parameters serve practically almost as well as the optimal point itself.
Due to the above tolerance, a bias point found optimal for a given input configuration, A, can be used as a quasi-optimal bias point for another input configuration, B, provided that A and B are “sufficiently similar”. That is, knowing the optimal bias point for configuration A and knowing that configuration B is very similar to A, one can skip the optimization step, thus jumping directly to the target estimation.
The solution proposed according to the core of the invention relates to the method and means for simulation of a communication system using Importance sampling and employing an Artificial Neural Network (ANN) to speed up the process by “learning” the relationship between system configurations and their associated optimal bias points. When trained, such an ANN proves to be able to provide quasi-optimal biases for new configurations. Hence, the invention helps in the process of simulation by speeding up the first part of the simulation, i.e. the preparation of the optimal bias vector for a certain input parameter vector. That is, the trained ANN then “hints” the “final” IS simulator about the bias vectors to be used for given input parameter vectors.
An ordinary Statistical Bias Optimizer that is here used to train the ANN, has after the training completed its task and is subsequently redundant. The second part of the simulation, i.e. the final estimate of performance parameters in the IS simulator is not affected by the invention.
Consequentl
Harald Brandt
Zsolt Haraszti
Davis George B.
Jenkens & Gilchrist P.C.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Method and means for simulation of communication systems 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 and means for simulation of communication systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and means for simulation of communication systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2954859