On a conservation law and the achievable region for waiting time tail probabilities in 2-class M/G/1 queueing systems

Conservation laws and the related achievable region for mean waiting times are important concepts in multi-class queues. The nice geometric polytope structure of this region driven by the conservation law is exploited extensively for dynamic control of multi-class queues. Such control problems have wide range of applications in computers, communication networks and manufacturing systems. Tail probability of each class´s waiting time is another important performance measure in any multi-class queue. This paper studies an approximate conservation law, the related achievable region and completeness of the tail probability of waiting time of each class in two class M/G/1 queues. We use completeness of the recently introduced relative priority scheme for mean waiting time vector as well as a suitable partition of the stability region of the queue to show that this approximate achievable region for tail probabilities is enclosed in a trapezium. We also study the tightness of bounds based on this decomposition of the stability region.