Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service

Reviewer: Carl Glen Ponder

This paper treats the problem of queueing packets that have an assigned expiration date. If a packet does not begin processing within the specified time limit, it is discarded as useless. The primary example is transmission of voice or video frames over a packet-switched network, where the illusion of real-time transmission is to be maintained. The occasional loss of a packet will reduce transmission quality, but the voice or video reception should remain intelligible. A shortest time to extinction (STE) policy services the customer nearest its completion deadline if no customer is already being serviced. A shortest time to extinction with inserted idle time (STEI) policy also services the customer nearest its completion deadline, though it may choose to sit idle before servicing the next customer. A scheduling policy is optimal within its class if it is minimal with respect to the expected number of discarded packets. The authors show that the following results hold. (1)For a continuous-time nonpreemptive queue with an exponential distribution of arrivals, a general distribution of service times, and a general distribution of deadlines ( M/ G/1 + G queue), the STE policy is optimal among policies not inserting idle times. (2)Under the assumptions in (1), except that inserted idle times are permitted, STEI policies will approach optimality. (3)For a discrete-time nonpreemptive queue with a general distribution of arrivals, unit service time, and a general distribution of deadlines ( G/ D/1 + G queue), the STE policy is optimal even with inserted idle times permitted. The proven results are supplemented by some approximations of the expected losses incurred by STE versus first-come, first-served (FCFS) and STEI under various parameters. The authors were unable to construct an STEI policy superior to STE. These results are of fundamental importance in queueing theory. The classes of queues and policies under consideration are quite basic, yet results in this field are scarce even under simple conditions. The fact that STE and STEI policies are optimal seems to be the intuitively most plausible result. Unfortunately the proofs require a significant amount of notation, even though the proof ideas are straightforward. The (un)readability is typical of papers in the Journal of the ACM, though a better presentation would be difficult. A less frivolous complaint is that the results do not extend further: Can one construct an STEI policy that is optimal for the M/ G/1 + G queue__ __ Result (2) uses an existence proof that can construct an STEI policy to match the performance of any other policy. No optimal policy is presented. Alternatively, one might show that some intuitively simple STEI policies are suboptimal. Regarding the original intent of the paper, the distribution of discarded packets is worth considering. The transmission will not be intelligible if the losses are clumped together.