Optimal scheduling of interactive and noninteractive traffic in telecommunication systems

Heterogeneous traffic types 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, which is assumed to be infinite. The traffic types are partitioned into two groups: interactive and noninteractive, and the average delay of each of the interactive types is required 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. An optimal policy is constructed and is shown to have many appealing properties