Rhonda Righter is a Professor and past Chair of the Department of Industrial Engineering and Operations Research at the University of California, Berkeley, where she earned her PhD. Before joining the Berkeley faculty she was a Professor of Operations Management and Information Systems in the Leavey School of Business at Santa Clara University. Her primary research and teaching interests are in the general area of stochastic modeling and optimization, especially as applied to service, manufacturing, computer communication, and cloud computing systems. She has won awards for her teaching, research, and service. She is an associate editor for the Journal of Scheduling, Queueing Systems, and the INFORMS Service Science Journal, and was the founding Chair of the Applied Probability Society of INFORMS.
Kristy Gardner is an Assistant Professor in the computer science department at Amherst College. She was awarded her PhD from Carnegie Mellon University in 2017. Her research focuses on performance modeling, developing mathematical solutions that predict system performance and inform system design.
Recent years have seen a surge of interest in two distinct, but related queueing models featuring multiple classes of customers that differ in the set of servers at which they can be served. In one view of these systems, each arriving job joins the queue at all servers at which it can be served. In the “cancellation on start” (CoS) model, a job’s extra copies are cancelled as soon as its first copy enters service, whereas in the “cancellation on completion” (CoC) model, a job's extra copies are cancelled as soon as its first copy completes service. Both models can also be viewed as having a single FCFS queue with either collaborative (CoC) or noncollaborative (CoS) service. The two systems are quite closely related mathematically, and surprisingly, under appropriate exponentiality assumptions, both yield a product-form stationary distribution. In this tutorial, we will discuss several different state-space descriptors for the two models, the product-form stationary distributions that result, and performance metrics that can be derived from the stationary distributions. We will also present new results comparing the performance of the two models, and we will discuss generalizations and related models, open questions, and directions for future research.
Devavrat Shah, Massachusetts Institute of Technology, USA
Devavrat Shah is a Professor in the Department of Electrial Engineering and Computer Science at Massachusetts Institute of Technology and is an Adjunct Professor at Tata Institute of Fundamental Research. He has received the ACM Sigmetrics Rising Star Award (2008), the Erlang prize from the INFORMS Applied Probability Society (2010), the INFORMS Applied Probability Society Best Publication Award (2012) and the Distinguished Young Alumni Award from the Indian Institute of Technology, Bombay (2015). His current research focus is social data processing with a particular interest in practical algorithms for statistical inference.
Approximately Reversible Stochastic Processing Networks
The property of (quasi-)reversibility of Markov chains have led to elegant characterization of steady-state distribution for complex queueing networks, e.g. celebrated Jackson networks, BCMP (Baskett, Chandi, Muntz, Palacois) and Kelly theorem. In a nutshell, despite the complicated interaction, in the steady-state, the queues in such networks exhibit independence and subsequently lead to explicit calculations of distributional properties of the queuing network that may seem impossible at the outset.
The model of stochastic processing network (cf. Harrison 2000) captures variety of dynamic resource allocation problems including the flow-level networks used for modeling bandwidth sharing in the Internet, switched networks (cf. Shah, Wischik 2006) for modeling packet scheduling in the Internet router and wireless medium access, and hybrid flow-packet networks for modeling job-and-packet level scheduling in data centers. Unlike before, an appropriate resource allocation or scheduling policy is required in such networks to achieve good performance. Given the complexity, asymptotic analytic approaches such as fluid model or Lyapunov-Foster criteria to establish positive-recurrence and heavy traffic or diffusion approximation to characterize the scaled steady-state distribution became method of choice. A remarkable progress has been made along these lines over the past few decades, but there is a need for much more to match the explicit calculations in the context of reversible networks.
In this tutorial, we will present an alternative to this approach that leads to non-asymptotic, explicit characterization of steady-state distribution akin BCMP / Kelly theorems. This involves (a) identifying a "relaxation" of the given stochastic processing network in terms of an appropriate (quasi-)reversible queueing network, and (b) finding a resource allocation or scheduling policy of interest that "emulates" the "relaxed" networks within "small error". The proof is in the puddling -- we will present three examples of this program: (i) distributed scheduling in wireless network, (ii) scheduling in switched networks, and (iii) flow-packet scheduling in a data center. The notion of "baseline performance" (cf. Harrison, Mandayam, Shah, Yang 2014) will naturally emerges as a consequence of this program. We will discuss open questions pertaining multi-hop networks and computation complexity.
- Shah, Shin, "Randomized scheduling algorithm for queueing networks". The Annals of Applied Probability, 2012.
- Shah, Walton, Zhong, "Optimal queue-size scaling in switched networks". The Annals of Applied Probability, 2014.
- Harrison, Mandayam, Shah, Yang, "Resource sharing networks: Overview and an open problem". Stochastic Systems. 2014.
- Shah, Xie, "Centralized congestion control and scheduling in a data-center". Under revision. 2018.