This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Puhalskii, A. A. Articles by Vladimirov, A. A. Search for Related Content

A Large Deviation Principle for Join the Shortest Queue

University of Colorado, Denver, U.S.A. and Institute of Information Transmission Problems, Moscow, Russia
Institute of Information Transmission Problems, Moscow, Russia
anatolii.puhalskii{at}cudenver.edu, http://www-math.cudenver.edu/puhalski/
vladim{at}iitp.ru

We consider a join-the-shortest-queue model, which is as follows. There are K single FIFO servers and M arrival processes. The customers from a given arrival process can be served only by the servers from a certain subset of all servers. The actual destination is the server with the smallest weighted queue length. The arrival processes are assumed to obey a large deviation principle while service is exponential. A large deviation principle is established for the queue-length process. The action functional is expressed in terms of solutions to mathematical programming problems. The large deviation limit point is identified as a weak solution to a system of idempotent equations. Uniqueness of the weak solution follows by trajectorial uniqueness.

Key Words: join-the-shortest-queue; large deviations; idempotent probability; discontinuous dynamics
History: Received: December 31, 2005; revision received: September 10, 2006;

This article has been cited by other articles:

				P. Dupuis, K. Leder, and H. Wang Importance Sampling for Weighted-Serve-the-Longest-Queue Mathematics of Operations Research, August 1, 2009; 34(3): 642 - 660. [Abstract] [PDF]