Hard deadline queueing system with application to unified messaging service

We consider a queueing system with jobs having hard deadlines. This is motivated by recent emerging unified messaging service applications. The service time of a job is assumed to be known upon arrival. A job will be lost if not being served by its deadline. For the single-server system, we propose an on-line ED-Push algorithm that is easy to implement and can achieve near-optimal performance in terms of minimizing the loss probability. Performance analyses for the underlying M/M/1+D and G/D/1+D systems are then provided. We also give approximation on the loss probability for the system with multiple servers under least workload routing scheme. The numerical results show that ED-Push algorithm performs well.