Optimal scheduling for an M/G/1 queueing system with multiple constraints

Heterogeneous traffic types (interactive messages, file transfers, facsimile, etc.) compete for access to a shared resource (satellite channel, bus, etc.). If a packet is not immediately given access to the resource, it waits in a buffer. We assume that the buffer capacity is infinite, that the traffic types arrive according to independent Poisson processes and that the period over which a packet occupies the resource has an arbitrary type-dependent distribution. The traffic types are partitioned into two groups: interactive and noninteractive. The average delay of each of the interactive types is required to below given thresholds. The problem of finding an optimal scheduling policy that minimizes a linear combination of the average delays for the noninteractive types while meeting the design constraints is considered. Simple necessary and sufficient conditions are derived for the existence of a policy that satisfies the constraints. An algorithm is given that decomposes the traffic types into an ordered arrangement of groups, and the existence of a policy that gives strict priority accordingly is established. Under weak conditions on the costs and rates, it is shown that all optimal policies must have this structural property. Sensitivity and aggregation analyses are given. Finally, exploiting the above decomposition, an optimal policy is constructed and is shown to have many appealing properties.