Simulation with convergence-detection skip-ahead
View Patent ↗A sub-system is provided to a discrete event simulator (DES) to expedite simulation execution by first detecting a non-quiescent steady-state condition in the simulated system, and when the steady-state condition is detected, the simulator determines a state, and subsequently simulates the system at a skip-ahead time using this determined state, or a predicted state based on the determined state. Convergence analysis is used to determine whether the system is at, or approaching, a steady-state condition. This convergence skip-ahead process achieves faster analysis by avoiding the computation that would conventionally be required to simulate the system behavior during the time interval that is skipped.
1. A method of simulation of a modeled system, comprising:
evaluating the modeled system in response to stimuli at a first time, to produce a subsequent state of the modeled system corresponding to a second time,
determining whether the modeled system is in a non-quiescent steady-state condition at the second time, and
if the modeled system is not in the non-quiescent steady-state condition:
evaluating the modeled system from the second time and beyond, based on the subsequent state; and
if the modeled system is in the non-quiescent steady-state condition:
defining an initial state of the modeled system at a skip-ahead time that differs from the second time, based on the non-quiescent steady-state condition, and
evaluating the modeled system from the skip-ahead time and beyond, based on the initial state,
wherein the non-quiescent steady-state condition includes:
at least one substantial change within the modeled system between the first time and the second time, and
a prediction state from which the initial state is determined.
2. The method of claim 1 , wherein
the skip-ahead time is dependent upon a next scheduled external event that is to be applied to the modeled system.
3. The method of claim 1 , further including
predicting the initial state, based on the non-quiescent steady-state condition.
4. The method of claim 1 , wherein
the initial state corresponds to a time-shift of the subsequent state.
5. The method of claim 1 , wherein
determining whether the modeled system is in the non-quiescent steady-state condition includes
collecting one or more statistics related to prior states of the modeled system, and
comparing the one or more statistics to one or more threshold values.
6. The method of claim 5 , wherein
the modeled system includes a node having a queuing element, and
the one or more statistics includes at least one of:
an average of queue measures of the queuing element, corresponding to prior states of the node, and
a variance of the queue measures of the queuing element.
7. The method of claim 6 , wherein
the queue measures include at least one of a queue length and a queuing delay.
8. The method of claim 6 , wherein
the node further includes a plurality of other queuing elements, and
the one or more statistics further include statistics based on queue measures associated with each of the other queuing elements.
9. The method of claim 1 , wherein
the modeled system comprises a plurality of elements that receive background-traffic and explicit-traffic, and
the stimuli include implicit events that are provided based on parameters of the background-traffic.
10. The method of claim 9 , wherein
the first time corresponds to a look-back period relative to a time of an explicit event of the explicit-traffic.
11. The method of claim 10 , wherein
the skip-ahead time corresponds to the time of the explicit event.
12. The method of claim 1 , wherein
determining whether the modeled system is in the non-quiescent steady-state condition includes
determining whether a parameter associated with the subsequent state is converging to a predictable value.
13. A simulator comprising:
an external event processor that is configured to provide input stimuli to a modeled system,
an evaluator that is configured to evaluate elements of the modeled system based on scheduled input events, and to produce therefrom changes of state of one or more elements, and output events,
a scheduler that is configured to receive scheduled external events corresponding to the input stimuli, and the output events from the evaluator, and to provide therefrom the scheduled input events to the evaluator,
a controller that is configured to manage and provide a simulation time measure to the scheduler, for determining the appropriate scheduled input events that are provided to the evaluator, and
a steady-state determinator that is configured to determine whether one or more elements of the modeled system are in a non-quiescent steady-state condition,
wherein:
the non-quiescent steady-state condition of the one or more elements includes:
at least one substantial change at the one or more elements, and
a prediction state from which future state information can be determined, and
if the one or more elements are in the non-quiescent steady-state condition:
the scheduler is further configured to provide the future state information corresponding to the state of the one or more elements at a skip-ahead time, and
the evaluator is further configured to evaluate the one or more elements, based on the state information corresponding to the state of the one or more elements at the skip-ahead time.
14. The simulator of claim 13 , wherein
the scheduler is further configured to adjust one or more of the scheduled input events relative to the skip-ahead time, based on whether the one or more elements are in the non-quiescent steady-state condition.
15. The simulator of claim 14 , further including
an input/output processor that is configured to receive user input related to the input stimuli and the modeled system, and to provide an output related to one or more of the output events.
16. The simulator of claim 13 , wherein
the skip-ahead time is based on a time of an event of the scheduled external events.
17. The simulator of claim 13 , wherein
the steady-state determinator determines whether the modeled system is in the non-quiescent steady-state condition based on one or more statistics related to prior states produced by the evaluator.
18. The simulator of claim 17 , wherein
the modeled system comprises a plurality of elements, and
the one or more statistics includes at least one of:
an average of a measure related to prior states of an element of the plurality of elements, and
a variance of the measure.
19. The simulator of claim 17 , wherein
at least one of the plurality of elements includes a queuing element, and
the measure includes at least one of a queue length and a queue time.
20. The simulator of claim 19 , wherein
the at least one of the plurality of elements further includes a plurality of other queuing elements, and
the one or more statistics further include statistics based on queue measures associated with each of the other queuing elements.
21. The simulator of claim 13 , wherein
the modeled system comprises a plurality of elements that receive background-traffic and explicit-traffic, and
the external event processor is further configured to provide scheduled implicit events to the scheduler, based on parameters of the background-traffic.
22. The simulator of claim 21 , wherein
the external event processor provides the scheduled implicit events based on a look-back period relative to a time of an explicit event of the explicit-traffic.
23. The simulator of claim 22 , wherein
the skip-ahead time corresponds to the time of the explicit event.
24. The simulator of claim 13 , wherein
the steady-state determinator is configured to determine whether one or more elements of the modeled system are in the non-quiescent steady-state condition based upon whether a parameter associated with the changes of state are converging to a predictable value.
25. A computer program on a media suitable for operating on a computer system, which, when executed by the computer system, causes the computer system to:
evaluate a modeled system in response to stimuli at a first time, to produce a subsequent state of the modeled system corresponding to a second time,
determine whether the modeled system is in a non-quiescent steady-state condition at the second time, and
if the modeled system is not in the non-quiescent steady-state condition:
evaluate the modeled system from the second time and beyond, based on the subsequent state; and
if the modeled system is in the non-quiescent steady-state condition:
define an initial state of the modeled system at a skip-ahead time that differs from the second time, based on the non-quiescent steady-state condition, and
evaluate the modeled system from the skip-ahead time and beyond, based on the initial state,
wherein the non-qulescent steady-state condition includes:
at least one substantial change within the modeled system, and
a prediction state from which the initial state is determined.
26. The computer program of claim 25 , wherein the program is configured to cause the computer system to determine whether the modeled system is in the non-quiescent steady-state condition based on
a comparison of one or more statistics related to prior states of the modeled system to one or more threshold values.
27. The computer program of claim 26 , wherein
the modeled system includes a node having a queuing element, and
the one or more statistics includes at least one of:
an average of queue measures of the queuing element, corresponding to prior states of the node, and
a variance of the queue measures of the queuing element.
28. The computer program of claim 27 , wherein
the queue measures include at least one of a queue length and a queue time.
29. The computer program of claim 28 , wherein
the node further includes a plurality of other queuing elements, and
the one or more statistics further include statistics based on queue measures associated with each of the other queuing elements.
30. The computer program of claim 25 , wherein
the modeled system comprises a plurality of elements that receive background-traffic and explicit-traffic, and
the stimuli include implicit events that are provided based on parameters of the background-traffic.
31. The computer program of claim 30 , wherein
the first time corresponds to a look-back period relative to a time of an explicit event of the explicit-traffic.
32. The computer program of claim 31 , wherein
the skip-ahead time corresponds to the time of the explicit event.
33. A module for use in a computer program, which, when executed on a computer system, causes the computer system to
determine whether a simulated element in a modeled system is in a non-quiescent steady-state condition, to facilitate:
a determination of an initial state of the simulated element at a skip-ahead time, and
a subsequent simulation of the simulated element at the skip-ahead time, based on the initial state of the simulated element at the skip-ahead time,
wherein
the non -quiescent steady-state condition includes:
at least one substantial change at the simulated element, and
a prediction state from which the initial state of the simulated element is determined.
34. The module of claim 33 , wherein the module is configured to cause the computer system to determine whether the simulated element is in the non-quiescent steady-state condition based on
a comparison of one or more statistics related to prior states of the simulated element to one or more threshold values.
35. The module of claim 34 , wherein
the simulated element includes a queuing element, and
the one or more statistics includes at least one of:
an average of queue measures of the queuing element, corresponding to prior states of the simulated element, and
a variance of the queue measures of the queuing element.
36. The module of claim 35 , wherein
the queue measures include at least one of a queue length and a queue time.
37. The module of claim 36 , wherein
the simulated element further includes a plurality of other queuing elements, and
the one or more statistics further include statistics based on queue measures associated with each of the other queuing elements.