Stochastic Networks: Analysis and Control

University Of California-San Diego, La Jolla CA

Investigators

Abstract

The aim of this project is to study mathematical problems associated with controlling and analyzing the performance of stochastic networks. Since the complexity and heterogeneity of these networks usually preclude exact analysis, the focus here is on approximate models. Two levels of approximation are considered: first order (functional law of large numbers) approximations called fluid models, and second order (functional central limit theorem) approximations, which are frequently diffusion models. The interplay between these two levels is an important subtheme throughout. Three main topics are addressed: (i) Dynamic scheduling for stochastic processing networks, (ii) Analysis of processor sharing networks, (iii) Congestion control for modern communication networks. The stochastic network models considered under these topics are considerably more general than conventional multiclass queueing networks operating under a head-of-the-line (HL) service discipline. Although there is a fairly well developed theory of stability and heavy traffic diffusion approximation for the latter, there are many challenging open problems associated with the control and analysis of the more general stochastic network models being studied here. Some of the stochastic process aspects are that topic (i) involves the analysis and interpretation of the solution of an approximating constrained diffusion control problem, topic (ii) uses measure-valued processes to keep track of residual service times of all jobs in the network, and topic (iii) involves reflected Levy processes when document sizes have heavy tails. This grant funds research on mathematical problems motivated by applications in the disciplines of operations research, computer science and electrical engineering. Specifically, problems associated with the control and analysis of stochastic networks are being studied. Such networks are used as models for complex manufacturing, telecommunications and computer systems. Two fundamental problems for such networks are (a) to understand the effects of common policies on congestion and delay, and (b) to design 'good' controllers for these systems. The networks under study are substantially more general than those that have been rigorously studied to date. Through their complexity and heterogeneity, these networks present challenging mathematical problems. The project involves the development of new theory for stochastic processes and uses techniques from a variety of mathematical disciplines. Collaborations with researchers familiar with areas of application and the training of graduate student researchers are integral parts of the project.