SCIENTIFIC PROGRAMS AND ACTIVITIES

August 18 - 21, 2010 Fields-MITACS Workshop on Approximations, Asymptotics and Resource Management for Stochastic Networks School of Mathematics and Statistics, Herzberg Building, HP 4351 Carleton University Organizers: Minyi Huang and Yiqiang Q. Zhao Co-sponsors: Laboratory for Research in Statistics and Probability (LRSP)	Supported by:

OVERVIEW

This workshop is a continuation of a series in Applied Probability held at Carleton University with the intention to cover topics as suggested by the title of the workshop as well as important themes in diverse areas of applied probability, such as asymptotics, performance, rare event simulation, stochastic modelling, queueing theory, internet traffic, wireless network resource allocation, and optimization algorithms.

The workshop consists of two short tutorial courses, each containing four (4) 1.5-hour lectures, provided by leading researchers Michel Mandjes and Masakiyo Miyazawa, and several research talks provided by invited speakers, researchers, students and PDFs. We expect that the workshop will stimulate new interaction and strengthen collaboration between researchers, and in particular appeal to graduate students and postdoctoral fellows, who will benefit from the presence of a number of experts from other countries.

Confirmed Tutorial lecturers

Michel Mandjes, Korteweg-de Vries Institute for Mathematics, University of Amsterdam and CWI
Masakiyo Miyazawa, Tokyo University of Science

Michel Mandjes Levy-driven queues (PDF available here) In this tutorial I will address theory on queueing systems with Levy input. These form a natural extension of the traditional M/G/1 queues, but allow for a substantial additional generality, as they also include refelected Brownian motion and queues with alpha-stable input. Models of this type are applicable in a wide range of domains, including communication networking and finance. I'll start with a detailed description of the Levy-driven queue, in terms of the associated Skorokhod problem. Then I present results on the corresponding stationary workload, in terms of Laplace transforms, primarily focusing on the spectrally one-sided case (that is, allowing either only positive jumps, or only negative jumps). I'll also show under what conditions the Laplace transform of the joint workload in Levy-driven queueing networks (for instance tandems) can be found. The second part of my tutorial will be on the transient behavior of Levy-driven queues. Relying on martingale arguments (for the spectrally positive case), or scale functions (spectrally-negative case), the double transform of the transient distribution can be determined explicitly. We use these results to study the correlation function of the workload process. We also present simulation techniques to efficiently estimate this correlation function. In the last part of the tutorial I will consider asymptotics of the workload. Starting with those corresponding to the stationary workload, we then focus on transient asymptotics, and joint asymptotics in tandem networks. The results of this part heavily rely on large-deviation techniques. This tutorial includes joint work with P. Glynn, K. Debicki, P. Lieshout, A. Es-Saghouani.

Masakiyo Miyazawa Light Tail Asymptotics for Stochastic Networks We are interested in evaluating the stationary probabilities of rare events which occur in stochastic networks, provided they are stable. Their state spaces are multidimensional and have boundaries, and it is hard to get their stationary distributions except for a few. This is a problem of so called large deviations, for which a firm framework has been established. However, it requires a profound mathematical background: a big wheel for taking up a specific answer. We only consider the light tailed case, that is, when the tail probabilities of the stationary distributions decay exponentially fast, and look at the problems in a different way. This is enabled in limiting to the case that has a homogeneous transition structure such as a random walk except for the boundaries of state spaces. We aim to introduce useful thoughts and feasible procedures for finding asymptotic behaviors of the rare events in such multidimensional (mainly two dimensional) processes. This tutorial lecture starts with finding renewal structure in a simple example. We then discuss basic tools such as the renewal theorem, change of measure and censoring technique to represent the stationary distributions using occupation measures. With help of them, we consider the asymptotic tail probabilities through their moment generating functions. Those moment generating functions have multidimensional variables, and can not be generally obtained in a closed form. Thus, we have to listen to low voice from them, and figure out asymptotic behaviors of the tail probabilities. We here use some elementary results from complex and convex analysis. For better understanding, we will discuss examples and consider applications of theoretical results.

One-hour research speakers

Yuliy Baryshnikov, Alcatel-Lucent Bell Labs
Search on the edge of chaos.
Search on the half-line is one of the simplest instances of the search problems, going back to Bellman '63 and Beck '64. Deceptive simplicity of the average case of this problem hides behind it an intricate structure - namely that of a Hamiltonian mapping with coexisting chaotic and regular dynamics, unbounded invariant domains and other unexpected pathologies. (Joint work with Vadim Zharnitsky, UIUC)

Doug Down, McMaster University
State-Dependent Response Times via Fluid Limits in Shortest Remaining Processing Time Queues
We consider a single server queue with renewal arrivals and i.i.d. service times, in which the server employs the shortest remaining processing time policy. We discuss a fluid model (or formal law of large numbers approximation) for this system, including existence and uniqueness results for fluid model solutions, and a scaling limit theorem that justifies the fluid model as a first order approximation of the stochastic model. The foremost payoff of our fluid model is a fluid level approximation for the state-dependent response time of a job of arbitrary size, that is, the amount of time it spends in the system, given an arbitrary system configuration at the time of its arrival. To describe the evolution of this queue, we use a measure-valued process that keeps track of the residual service times of all buffered jobs. The state descriptor of the fluid model is a measure-valued function whose dynamics are governed by certain inequalities in conjunction with the standard workload equation. In particular, these dynamics determine the evolution of the left edge (infimum) of the state descriptor's support, which is the key to our analysis of response times. We characterize the evolution of this left edge as an inverse functional of the arrival rate, service time distribution, and initial condition. The initial condition, or fluid model state at time zero, is interpreted as the system configuration encountered by the arriving job for which a response time analysis is sought. Our characterization reveals the manner in which the growth rate of the left edge depends on the service time distribution. It is shown that the rate can vary from logarithmic to polynomial by considering various examples. In addition, it is shown that this characterization implies that critical fluid models for which the service time distribution has unbounded support converge to the empty queue as time approaches infinity, a perhaps unexpected result since the workload remains constant.

Peter Glynn, Stanford University
Explicit Computation and Asymptotics for Finite Buffer Models
We consider a finite buffer queue that is modeled as a two-sided reflection map fed by Brownian input and, more generally, Levy input. The local time at the upper boundary then corresponds to the loss process for the queue. We show how stochastic calculus can be used to compute both the typical behavior of the loss process, as characterized by laws of large numbers and central limit theorems, as well as extremal behavior as determined by large deviations for the loss process. Conditional limit laws, analogous to Boltzmann's law, are also derived in the presence of conditioning on the large deviation. We also will discuss the nature of the corresponding computations in the context of more complex stochastic networks. This work is joint with Soren Asmussen and Xiaowei Zhang.

Hui Li, Mount Saint Vincent University
Light-Tailed Behaviour for Random Walks in the Quarter Plane
In this talk, we present analysis of exact tail asymptotics for random walks in the quarter plane (also called doubly QBD process with infinitely many background (phase)). Applying kernel methods and the theory of Riemann surfaces on generating functions of the joint state stationary distributions, we give, under a given condition, a complete characterization of the regions of system parameters for exact tail asymptotics along a coordinate direction as well as the three corresponding types of exact tail asymptotics: exact geometric decay, geometric multiplied by a power function with power -1/2 or geometric multiplied by a power function with power -3/2. We also apply the results obtained to some queueing systems. This talk is based on the results of the joint research with Dr. Y. Zhao at Carleton University.

Yuanyuan Liu, Central South University
Subgeometric Ergodicity and Integral-type Functionals for Continuous-time Markov Chains
In this talk, we will consider subgeometric ergodicity for a general continuous-time Markov chains. Several equivalent conditions, based on the first hitting time or the drift function, are introduced as the main theorem. In its corollaries, practical drift criteria are given for $\ell$-ergodicity and computable bounds on subgeometric convergence rates are obtained for stochastically monotone Markov chains. One basic tool to analyze the first hitting time is the theory of integral-type functionals, which is also of its own interests in investigating the Central Limit Theorem. These results are illustrated by some examples.

Ravi R. Mazumdar, University of Waterloo
Congestion in large balanced fair links
File transfers compose much of the traffic of the current Internet. The main measures of the quality of service for this type of traffic are the transfer rates and duration of the file transfer. File transfers are modeled as a fluid elastic flow, whose transmission rates are adaptable depending on the network congestion or the number of other flows that share the link. There are many models for sharing the available bandwidth on a link and the most common model is that of processor sharing. Such a model assumes that the flows sharing the link are homogeneous. However, in practice, flows have different bandwidth requirements. A major concern is how to share the bandwidth at links in a network fairly when it is accessed by heterogeneous flows. A key notion of fairness that has been studied in the context of rate control of elastic flows is the notion of {\em proportional fairness} introduced by Kelly that corresponds to a Nash bargaining solution. Proportional fairness can be well approximated by using a balanced fair server bandwidth allocation scheme. Balanced fairness is a sharing policy introduced by Bonald and Proutiere and has the attractive advantage of being both tractable to flow level analysis and insensitive. Tractability means that we can develop analytical results to determine the performance of systems using balanced fairness.

The talk will focus on congestion in links that operate under a balanced fair allocation scheme for heterogeneous flows with differing maximum or peak bandwidth requirements. In particular we address how various performance measures can be explicitly computed in systems where the links are accessed by a large number of independent flows using ideas from local limit large deviations of convolution
measures associated with multirate Erlang systems.

 

Schedule (see details)

Wednesday August 18:
	1:00-1:30pm (Coffee/Registration) 1:30-3:00pm (Tutorial 1) 3:00-3:15pm Coffee/Tea 3:15-4:45pm (Tutorial 2)
Thursday August 19
	8:30-9:00am (Coffee/Registration) 9:00-10:30am (Tutorial 1) 10:30-10:45am Coffee/Tea 10:45am-12:15pm (Tutorial 2) 12:15-1:00pm (Lunch, provided) 1:00-5:00pm (Research talks) 6:00pm (Dinner)
Friday August 20
	8:30-9:00am (Coffee/Registration) 9:00-10:30am (Tutorial 1) 10:30-10:45am Coffee/Tea 10:45am-12:15pm (Tutorial 2) 12:15-1:00pm (Lunch, provided) 1:00-5:00pm (Research talks)
Saturday August 21
	8:30-9:00am (Coffee/Registration) 9:00-10:30am (Tutorial 1) 10:30-10:45am Coffee/Tea 10:45am-12:15pm (Tutorial 2) 12:15-1:00pm (Lunch, provided) 1:00-5:00pm (Research talks)
	There will be a dinner on Thursday evening at Mother Tucker's at 6pm.

List of Confirmed Participants as of August 12, 2010:

Full Name	University Name
Almehdawe, Eman	University of Waterloo
Bhattacharja, Bonane	UBC Okanagan
Cai, Qishu	University of Waterloo
Down, Douglas	McMaster University
Gao, Yanfei	Carleton University
Glynn, Peter W.	Stanford University
Gomis, Tony	NBI-France
Haddad, Jean-Paul	University of Waterloo
Hosseini, Reza	AAFC and Simon Fraser University
Huang, Minyi	Carleton University
Jiang, Yiming	Nankai University
Khanchi, Aziz	Carleton University
Kulik, Rafal	University of Ottawa
Li, Hui	Mount Saint Vincent University
Li, Jun	Communications Research Centre
Liu, Yuanyuan	Central South University
Miscoi, Gheorghe	Free International University of Moldova
Miyazawa, Masakiyo	Tokyo University of Science
Nguyen, Bao	Defence R&D Canada
Nkurunziza, Sévérien	University of Windsor
Panario, Daniel	Carleton University
Pehlivan, Lerna	Carleton University
Rabinovitch, Peter	Carleton University
Sahba, Pedram	University of Toronto
Shirani, Rostam	Carleton University
Szeto, Kwok Yip	Hong Kong University of Science and Technology
Tai, Yongming	Carleton University
Tavakoli, Javad	UBC Okanagan
Timusk, Peter	Statistics Canada
Wang, Ge	Carleton University
Wei, Wanxia	DRDC
Xu, Chen	Carleton University
Zhan, Lina	Carleton University
Zhang, Guichang	University of Saskatchewan
Zhang, Zhidong	University of Saskatchewan
Zhao, Yiqiang	Carleton University
TO BE CONFIRMED:
Haxhiaj, Blendi	PUT University
Wang, Yinghui	McMaster University
Zeng, Qingsheng	University of Ottawa

 

Top