A combined splitting-cross entropy method for rare-event probability estimation of queueing networks

摘要

We present a fast algorithm for the efficient estimation of rare-event (buffer overflow) probabilities in queueing networks. Our algorithm presents a combined version of two well known methods: the splitting and the cross-entropy (CE) method. We call the new method SPLITCE. In this method, the optimal change of measure (importance sampling) is determined adaptively by using the CE method. Simulation results for a single queue and queueing networks of the ATM-type are presented. Our numerical results demonstrate higher efficiency of the proposed method as compared to the original splitting and CE methods. In particular, for a single server queue example we demonstrate numerically that both the splitting and the SPLITCE methods can handle our buffer overflow example problems with both light and heavy tails efficiently. Further research must show the full potential of the proposed method.