Optimal scheduling and admission control in communication networks.

Abstract

With the current rapid progress in telecommunications, especially in cellular networks, an understanding of how to efficiently schedule, allocate and control access to shared resources has become increasingly important. Unfortunately, due to the difficulties involved in characterizing an optimal policy for realistic networks, research in the above networks has mainly concentrated on the performance analysis of ad hoc policies rather than on optimization. The goal of this research is to provide an increased understanding of some of the fundamental issues pertaining to the optimal design of the above networks. First, the multi-armed bandit problem with switching penalties is investigated. This problem deals with the optimal single-server scheduling of tasks (messages, projects, jobs) in the presence of switching penalties (costs or delays) that incur when the server switches from one class of tasks to another. It is shown that under an optimal policy, decisions about the server allocation need to be made only at those stopping times that achieve an appropriate index, such as either the well known Gittins index or a new switching index that is defined to account for switching costs and delays. Sufficient conditions for optimality of allocation policies, based on limited lookahead, are also established. Next, the handoff scheduling problem in cellular networks is addressed. In cellular networks, handoffs ensure continuity of any call while a mobile user moves from one cell to another. The handoff scheduling problem is formulated as a stochastic optimization problem with switching penalties, and properties of optimal policies are derived. Simulation results are included to illustrate how this formulation yields a systematic unified framework, within which different performance criteria and policies proposed in the literature can be compared and contrasted. Finally, the optimal acceptance of new calls in cellular networks is formulated as an admission control problem in interconnected queues with more than one controllable arrival streams. The nature of an optimal policy is determined under certain conditions on the rates of arrivals and handoffs.