Evaluating Rare Events in Mission Critical Dispatching Systems

Dispatching systems, where jobs are routed to servers immediately upon arrival, appear frequently in parallel computing systems. With a dynamic dispatching policy, the system is generally analytically intractable and performance evaluation is carried out by means of Monte Carlo simulations. A typical performance metric is the mean response time which is often easy to estimate. In contrast, we consider systems where events generating costs are extremely rare. In our reference system, jobs have deadlines for waiting time. When deadlines are loose when compared to the system's load, novel rare event simulation techniques must be applied. We consider both conditioning and importance sampling to this end. The proposed techniques are illustrated in numerical examples, where we discover interesting performance relationships among the classical dispatching policies; Random split (RND), Round-robin (RR), Join-the-shortest-queue (JSQ) and Least-work-left (LWL).