SCIENTIFIC PROGRAMS AND ACTIVITIES

September 28, 2016

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:
 Online Registration is now closed. On-site Registration Aug. 18 A map of the Carleton Campus is available here Schedule Participant List Directions to Carleton Accommodation Resources

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 Miyazaw
a, Tokyo University of Science

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