Optimal load sharing in soft real-time systems: An on-line algorithm using likelihood ratio estimates

The likelihood ratio method is studied as a possible approach for sensitivity analysis of discrete event systems. A load sharing problem is considered for a multi-queue system in which customers have soft real-time constraints--if the waiting time of a customer exceeds a given random amount (called the laxity of the customer), then the customer is considered lost. A recursive optimization algorithm is formulated using likelihood ratio estimates to minimize the steady-state probability of loss with respect to the load sharing parameters, and almost sure convergence of the algorithm is proved. The algorithm can be used for on-line optimization of the real-time system, and does not require a priori knowledge of the arrival rate of customers to the system or the service time and laxity distributions. To illustrate the results, simulation examples are presented.