Campuses:

On the Resource/Performance Tradeoff in Large Scale Queueing Systems

Thursday, October 22, 2015 - 10:15am - 11:05am
Keller 3-180
David Gamarnik (Massachusetts Institute of Technology)
Queueing systems exhibit a fundamental tradeoff between the availability of resources and performance, such as delays and queue lengths. Typically such resources include the number and the speed of servers, but other resources, for example, the availability of a common buffer and the amount of information exchange, can also have a first order impact on the performance. We consider two examples of such tradeoffs, both in the context of large scale parallel queueing systems.

First, we compare the performance of the Join-the-Shortest Queue (JSQ), the design of which requires only server individual buffers, with the performance of the M/M/N queueing system, which achieves the best possible queueing delay, but at the expense of the availability of one common buffer for all servers. We consider the JSQ system in the Halfin-Whitt heavy traffic regime and establish convergence to a certain two-dimensional Ornstein–Uhlenbeck process. Using this result we establish that the average queueing delay is of the same order of magnitude as the one of M/M/N system. Thus the performance loss of JSQ vs the M/M/N queue is very minimal.

Second we consider a parallel server queueing system with a global router containing a limited memory space, which exchanges messages with individual servers. We consider a particular natural routing scheme and establish fluid limit asymptotics of the average delay for this scheme. In particular, we show that the average delay is bounded away from zero in the limit. Then we show that as long as the memory of the router is at most logarithmic in the number of servers, any (appropriately defined) symmetric routing scheme leads to a delay which is bounded away from zero in the limit, regardless of the details of the policy.

Joint work with Patrick Eschenfeldt, John Tsitsiklis and Martin Zubeldia.
MSC Code: 
68M20
Keywords: