COMPARISON AND OPTIMIZATION OF RESTART RUN-TIME STRATEGIES

The RESTART method with multiple steps or thresholds is one of the mos t general methods for the evaluation of rare events by simulation. Thi s method has had a revival due to its use in the evaluation of cell lo ss probabilities in Asynchronous Transfer Mode (ATM) networks. The mai n problem in applying this method is the choice of parameters: how man y steps and at which points or which levels should the steps be placed ? Previous work has given some formulas for these parameters, but, unf ortunately, the formulas contain values that are to be determined by t he simulation itself. This paper compares different approaches with th eir formulas and gives examples. Two different run time strategies are evaluated: the step-by-step and the global-step approaches. In the st ep-by-step approach, one step after the other is evaluated until the l ast step is completed. In this case, values that have been determined during the evaluation of a previous step can be used to determine para meters of the next step. The drawback of this method is that, in gener al, more system states have to be stored. In the global-step approach, all steps are fixed in advance so that every time a step is reached, this simulation run can be split into several runs. Here only one stat e per threshold has to be stored, but the thresholds and also the spli tting factors have to be fixed in advance. This paper shows how the tw o methods can be combined determining the optimal thresholds and param eters in a short pre-run with the step-by-step approach and gaining th e desired accuracy in a second longer run with the global-step approac h. Results for actual simulation runs using both run time strategies w ith the RESTART/LRE algorithm and the combined approach are given for some important queueing systems: M/M/1/N, M/D/1/N, SSMP(Geo,Geo)/D/1/N with a correlated input stream, and a tandem network. The obtained re sult is the complete complementary distribution function of the arriva l occupancy, which includes as a last value the loss probability of th e system.