ORIE Colloquium: Chaitanya Bandi (MIT) - Robust Queueing Theory - A theory of Stochastic Analysis via Robust Optimization
Thursday, February 7, 2013 at 3:00pm
Frank H. T. Rhodes Hall, 253
Abstract: Modern probability theory, whose foundation is based on the axioms set forth by Kolmogorov, is currently the major tool for performance analysis in stochastic systems. While it offers insights in understanding such systems, probability theory is really not a computationally tractable theory in high dimensions. Correspondingly, some of its major areas of application remain unsolved when the underlying systems become multidimensional (which is often the case in practice): Queueing networks, network information theory, pricing multi-dimensional financial contracts, auction design in multi-item, multi-bidder auctions among others.
We propose a new approach to analyze stochastic systems based on robust optimization, which we have applied to solve some of the key problems in these application domains. The key idea is to replace the Kolmogorov axioms as primitives of probability theory, with some of the asymptotic implications of probability theory: the central limit theorem and law of large numbers and to define appropriate robust optimization problems to perform performance analysis. In this way, the performance analysis questions become highly structured optimization problems (linear, conic, mixed integer) for which there exist efficient, practical algorithms that are capable of solving truly large scale systems.
In this talk, we present this approach in the context of analyzing multi-server queueing systems with heavy tailed processes. Specifically, we present closed form expressions for the waiting times in multi-server queues with heavy-tailed arrival and service processes in both the steady-state and transient domain that characterize real-world queueing systems such as data centers and call centers. These closed form expressions allow us to get a qualitative feel for how the key performance measures depend on the system parameters. We also develop an exact calculus for analyzing the steady-state behavior of a network of queues with feedback, multiple servers and heavy tailed arrival and service processes that performs significantly better than the Queueing Network Analyzer (QNA) proposed in Whitt (1983), and is to a large extent insensitive to the number of servers per queue, the network size, degree of feedback, and traffic intensity.
Joint work with Dimitris Bertsimas and Nataly Youssef.
Bio: Chaithanya Bandi is a doctoral candidate in the Operations Research Center at MIT, under the supervision of Professor Dimitris Bertsimas. He has a bachelor’s degree in computer science from the Indian Institute of Technology, Madras. He is broadly interested in stochastic modeling and analysis, as well as their applications in various business and engineering domains.