A Simple Diffusion Limit for Flows in Stable Multi-Class Queueing Networks

Host Institution:

La Trobe University

Title of Seminar:

A Simple Diffusion Limit for Flows in Stable Multi-Class Queueing Networks

Speaker's Name:

Dr. Yoni Nazarathy

Speaker's Institution:

Swinburne University of Technology

Time and Date:

Friday 17 June 2011 at 11:00 am (AEST)

Seminar Abstract:

This talk is intended for a general statistical/mathematical audience.

Multi-Class Queueing Networks are often used as abstract models for communication, computing, road traffic, human services and logistics in manufacturing networks. Explicit results of queue lengths and/or waiting time distributions are often difficult to come by, yet methodologies for establishing stability properties of networks and policies are well studied. In addition, Brownian (diffusion) approximations of networks under heavy load have been a prime focus allowing to approximate the performance of queueing networks where all servers are under near-critical load. The book Fundamentals of queueing networks: performance, asymptotics, and optimization by Hong Chen and David D. Yao, 2001 provides a clear comprehensive summary of the basic results and literature.

A major obstacle in explicitly quantifying the performance of queueing networks lies in the inability to decompose queueing networks into subnetworks without imposing independence assumptions which are often without ground. In this respect, the "Parametric Network Decomposition" methodologies, pioneering by the 1983 paper, The Queueing Network Analyzer by Ward Whitt approximate subnetworks (often individual nodes), analyzing each subnetwork in isolation and treating each subnetwork as an input-output operator on the sequence of customer arrival times - most often ignoring correlations between different customer streams.  While this type of analysis most often lacks solid analytical grounds and justification, next to Monte-Carlo simulation it is the predominant tool in use by network planners (e.g. in logistics of manufacturing).

Our contribution is in presenting simple matrix formulas which under certain regularity conditions, explicitly compute the asymptotic variance rates of customer flows within a stable queueing network.  The asymptotic variance rate is the rate at which the variance function of counting processes grows with time (under regularity conditions the variance grows asymptotically linearly with time). Our formulas rely on standard functional central limit theorems for renewal process and utilize standard methodology for finding limiting processes (e.g. Chen and Yao 2001) by means of a continuous mapping, yet to the best of our knowledge our simple results have not been documented previously. Our formulas may in essence be used to refine parametric network decomposition schemes allowing to take correlations of different streams into account yielding exact values for asymptotic variance rates as opposed to approximate ones.

This is joint work with Gideon Weiss, The University of Haifa.

Seminar Convenor:

This email address is being protected from spambots. You need JavaScript enabled to view it.

AGR IT support:

This email address is being protected from spambots. You need JavaScript enabled to view it.