
August 18  21, 2010
FieldsMITACS 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
Cosponsors: 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.5hour 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,
Kortewegde Vries Institute for Mathematics, University
of Amsterdam and CWI
Masakiyo
Miyazawa, Tokyo University
of Science
Michel Mandjes
Levydriven 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 alphastable 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 Levydriven
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 onesided 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 Levydriven queueing networks (for instance
tandems) can be found.
The second part of my tutorial will be on the transient
behavior of Levydriven queues. Relying on martingale
arguments (for the spectrally positive case), or scale
functions (spectrallynegative 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 largedeviation techniques.
This tutorial includes joint work with P. Glynn, K. Debicki,
P. Lieshout, A. EsSaghouani.

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.

Onehour research speakers
Yuliy Baryshnikov,
AlcatelLucent Bell Labs
Search on the edge of chaos.
Search on the halfline 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
StateDependent 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 statedependent 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 measurevalued
process that keeps track of the residual service times of all
buffered jobs. The state descriptor of the fluid model is a
measurevalued 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 twosided
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
LightTailed 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 Integraltype Functionals
for Continuoustime Markov Chains
In this talk, we will consider subgeometric ergodicity for
a general continuoustime 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 integraltype 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.
Wednesday August 18: 

1:001:30pm (Coffee/Registration)
1:303:00pm (Tutorial 1)
3:003:15pm Coffee/Tea
3:154:45pm (Tutorial 2) 
Thursday August 19 

8:309:00am (Coffee/Registration)
9:0010:30am (Tutorial 1)
10:3010:45am Coffee/Tea
10:45am12:15pm (Tutorial 2)
12:151:00pm (Lunch, provided)
1:005:00pm (Research talks)
6:00pm (Dinner) 
Friday August 20 

8:309:00am (Coffee/Registration)
9:0010:30am (Tutorial 1)
10:3010:45am Coffee/Tea
10:45am12:15pm (Tutorial 2)
12:151:00pm (Lunch, provided)
1:005:00pm (Research talks) 
Saturday August 21 

8:309:00am (Coffee/Registration)
9:0010:30am (Tutorial 1)
10:3010:45am Coffee/Tea
10:45am12:15pm (Tutorial 2)
12:151:00pm (Lunch, provided)
1:005: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 
NBIFrance 
Haddad, JeanPaul 
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

