Admission Control and Routing Issues in Data Networks

Abstract

In modern telecommunication and computer networks, there is an increasing demand to provide simultaneously a variety of services to heterogeneous traffic types with diverse characteristics and performance requirements. This has led to a need for understanding the basic structure that characterizes policies for efficiently allocating network resources, such as link capacity, to the various users. In this dissertation, we address some aspects of admission control and routing - key issues arising in the design and operation of integrated communication and computer networks. We begin by considering the problem of optimal admission control of messages arriving at a circuit-switched node. Next, the asymptotic behavior of such networks is investigated when the arrival intensities and the capacities of the network links are increasingly large. Finally a "combined" optimal admission- routing scheme at a simple network node is presented. A description of these problems is given below.Two communication traffic streams with Poisson statistics arrive at a network node on separate routes. These streams are to be forwarded to their destinations via a common trunk. The two links leading to the common trunk have capacities C 1 and C 2 bandwidth units, respectively, while the capacity of the common trunk is C bandwidth units, where C < C 1 + C 2. Calls of either traffic type that are not admitted at the node are assumed to be discarded. An admitted call of either type will occupy, for an exponentially distributed random time, one bandwidth unit on its forwarding link as well as on the common trunk. Our objective is to determine a scheme for the optimal dynamic allocation of available bandwidth among the two traffic streams so as to minimize a weighted blocking cost. The problem is formulated as a Markov decision process. By using dynamic programming principles, the optimal admission policy is shown to be of the "bang-bang" type, characterized by appropriate "switching curves." The case of a general circuit-switched network, as well as numerical examples, are also presented.Markov decision processes arise in a natural way in the optimal control of queuing systems in some of the problems considered in this thesis. In many cases the convexity of an optimal discounted cost associated with such processes plays a key role in the analysis. A method that ascertains the convexity of such optimal discounted costs is presented. The procedures relies on a straightforward examination of all possible state transitions of the underlying Markov decision process.Next, the asymptotic behavior of circuit- switched networks is addressed. We first consider a class of simple circuit-switched nodes in the limiting situation where the link capacities and the offered traffic intensities are increased at the same rate. We assume that an incoming message is given access to the network only if none of the links constituting its route is saturated in capacity. The process of the normalized number of messages on each route is shown to converge in probability to a solution of a system of differential equations which possesses a unique stable point. Next, the difficulties encountered in extending this method to arbitrary circuit- switched networks are discussed. The usefulness of the method lies in its ability to provide a transient analysis of the limiting network and to determine its "most likely" steady state. A conjecture for a strong approximation concerning the limiting behavior of an arbitrary circuit-switched network is also given.Finally, a problem of determining simultaneously optimal admission and routing policies at a data network node is considered. Specifically, a message arriving at the buffer of a node in a data network is to be transmitted over one of two channels with different propagation times. Under suitably chosen criteria, two decisions have to be made: whether or not to admit an incoming message into the buffer, and under what conditions should the slower channel be utilized. A discounted infinite- horizon cost as well as an average cost are considered which consist of a linear combination of the blocking probability and the queuing delay at the buffer.