Optimal admission control in tandem and parallel queueing systems with applications to computer networks

Queueing sytems;Markov Decision processes;Tandem queues;Stochastic systems;Stochastic dynamic programming;Authentication systems;Constrained Markov decision processes;Linear programming

Silva Izquierdo, Daniel F. ; Ayhan, Hayriye Industrial and Systems Engineering Goldberg, David A. Andradottir, Sigrun Dieker, Antonius Zhang, Bo ; Ayhan, Hayriye

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Queueing sytems;    Markov Decision processes;    Tandem queues;    Stochastic systems;    Stochastic dynamic programming;    Authentication systems;    Constrained Markov decision processes;    Linear programming;   

Others  :  https://smartech.gatech.edu/bitstream/1853/55661/1/SILVAIZQUIERDO-DISSERTATION-2016.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Modern computer networks require advanced, efficient algorithms to control several aspects of their operations, including routing data packets, access to secure systems and data, capacity and resource allocation, task scheduling, etc. A particular class of problems that arises frequently in computer networks is that of admission and routing control. Two areas where admission control problems are common are traffic control and authentication procedures. This thesis focuses on developing tools to solve problems in these areas. We begin the thesis with a brief introductory chapter describing the problems we will be addressing. Then, we follow this with a review of the relevant literature on the problems we study and the methodologies we use. Then, we have the main body of the dissertation, which is divided into three parts, described below.In the first part, we analyze a problem related to data routing in a network. Specifically, we study the problem of admission control to a system of two stations in tandem with finite buffers, Poisson arrivals to the first station, and exponentially distributed service times at both stations. We assume costs are incurred either when a customer is rejected at the time of arrival to the first station or when the second station is full at the time of service completion at the first station. We propose a Markov decision process formulation for this problem. Then, we use this model to show that, when one of the buffers has size one, the structure of the optimal policy is threshold and that only two particular policies can be optimal. We provide the exact optimality thresholds for small systems. For larger systems, we formulate heuristic policies and use numerical experiments to show that these policies achieve near-optimal performance. For the second part of this thesis, we investigate the system described above in a more general case, where the capacity of the buffers at both station is equal, finite and arbitrary. We focus on two specific, extremal policies, which we call the Prudent and Greedy policies. We derive a closed-form expression for the long-run average reward under the Prudent policy andprovide a necessary and sufficient threshold condition for it to be optimal. For the Greedy policy, we give a matrix-analytic solution for the long-run average reward and provide a sufficient condition for it to be optimal. We also prove that it is always optimal to admit customers in the states where the Prudent policy admits customers. Next, we use an example to illustrate that the optimal policy can have a complicated form. Finally, we propose two heuristic policies and use numerical experiments to show that they perform much better than the Prudent and Greedy policies, and in fact, achieve near-optimal performance. In the third and final part of this dissertation, we shift our attention to a different admission and routing control problem. We study a centralized system where requests for authentication arrive from different users. The system has multiple authentication methods available and a controller must decide how to assign a method to each request. We consider three different performance measures: usability, operating cost, and security. First, we model the problem using a cost-based approach, which assigns a cost to each measure of performance. Under this approach, we find that if each authentication method has infinitely many serversthe optimal policy is static and deterministic. On the other hand, if there is one method that has finite capacity and the rest have infinitely many servers, we show that the optimal policy is of trunk reservation form. Then, we model the problem using a constraint-based approach, which assumes hard constraints on some of the measures of performance. We show that if each method has infinitely many servers, the optimal policy is static and randomized. While, if one method has finite capacity and the rest have infinitely many servers, we show that the optimal policy has a 2-randomized trunk reservation form. Finally, we illustrate how to use our results to construct an efficient frontier of non-dominated solutions. We end this dissertation with a short recapitulation of our main contributions and a discussion on potential avenues for future research.