Join-the-Shortest-Queue (JSQ) is the scheduling policy of choice for many network providers, cloud servers, and traffic management systems, where individual queues are served under the processor sharing (PS) queueing discipline. A numerical solution for the response time distribution in two parallel PS queues with JSQ scheduling is derived for the first time. Using the generating function method, two partial differential equations (PDEs) are obtained corresponding to conditional response times, where the conditioning is on a particular traced task joining the first or the second queue. These PDEs are functional equations that contain partial generating functions and their partial derivatives, and therefore cannot be solved by commonly used techniques. We are able to solve these PDEs numerically with good accuracy and perform the deconditioning with respect to the queue-length probabilities by evaluating a certain complex integral. Numerical results for the density and the first four moments compare well against regenerative simulation.

Join-the-Shortest-Queue (JSQ) is the scheduling policy of choice for many network providers, cloud servers, and traffic management systems, where individual queues are served under processor sharing (PS) queueing discipline. A numerical solution for the response time distribution in two parallel PS queues with JSQ scheduling is derived for the first time. Using the generating function method, two partial differential equations (PDEs) are obtained corresponding to conditional response times, where the conditioning is on a particular traced task joining the first or the second queue. These PDEs are functional equations that contain partial generating functions and their partial derivatives, and therefore cannot be solved by commonly used techniques. We are able to solve these PDEs numerically with good accuracy and perform the deconditioning with respect to the queue-length probabilities by evaluating a certain complex integral. Numerical results for the density and the first four moments compare well against regenerative simulation with 500,000 regeneration cycles.

Response time density is obtained in a tandem pair of Markovian queues with both batch arrivals and batch departures. The method uses conditional forward and reversed node sojourn times and derives the Laplace transform of the response time probability density function in the case that batch sizes are finite. The result is derived by a generating function method that takes into account that the path is not overtake-free in the sense that the tagged task being tracked is affected by later arrivals at the second queue. A novel aspect of the method is that a vector of generating functions is solved for, rather than a single scalar-valued function, which requires investigation of the singularities of a certain matrix. A recurrence formula is derived to obtain arbitrary moments of response time by differentiation of the Laplace transform at the origin, and these can be computed rapidly by iteration. Numerical results for the first four moments of response time are displayed for some sample networks that have product-form solutions for their equilibrium queue length probabilities, along with the densities themselves by numerical inversion of the Laplace transform. Corresponding approximations are also obtained for (non-product-form) pairs of “raw” batch-queues—with no special arrivals—and validated against regenerative simulation, which indicates good accuracy. The methods are appropriate for modeling bursty internet and cloud traffic and a possible role in energy-saving is considered.