Heavy Traffic Approximations of a Queue with Varying Service Rates and General Arrivals

Abstract

Heavy traffic limit theorems are established for a class of single server queueing models including those with heavy-tailed or long-range dependent arrivals and time-varying service rates. The models are motivated by wireless queueing systems for which there is an increasing evidence of the presence of heavy-tailed or long-range dependent arrivals, and where the service rates vary with the changes in the wireless medium.

The main focus of the paper is to obtain the different possible limit processes that can arise depending on the relationship between scalings for both the arrival and departure processes. The limit processes obtained here are driven by either Brownian motion (when the contribution from the departure process dominates the limit) or the limits of properly scaled arrivals (when the contribution from the arrival process dominates the limit), typical examples being stable Lévy motion or fractional Brownian motion. In particular, for the case where arrival process is given by the infinite source Poisson process, this relationship, which determines the type of the limiting queue-length process, is a simple condition involving the heavy tail exponent, arrival rate and channel variation parameter in the wireless medium model.

To establish these limit results, two approaches are studied. In one approach, when the limit is driven by Brownian motion, the perturbed test function method is extended to incorporate reflection. In contrast, the second approach allows for non-Markovian and/or non-Gaussian driving processes in the limit. Both approaches involve averaging in the drift term arising from random service rates at the departures. In the second approach, this averaging is carried out directly and pathwise, thus sidestepping the assumption of driving Brownian motion used in the perturbed test function method.

Keywords:

• Averaging
• Brownian motion
• Fractional Brownian motion
• Heavy traffic limit theorems
• Heavy tails
• Long-range dependence
• Perturbed test function method
• Reflection
• Stable Lévy motion
• Wireless queueing systems

Mathematics Subject Classification:

• Primary 60F05, 60K25
• Secondary 60G18, 60G52, 90B18

ACKNOWLEDGMENT

The authors would like to thank anonymous referees for many useful comments and suggestions.

The authors were supported in part by the NSF grants DMS-0608669 at North Carolina State University, DMS-0608634 at Iowa State University, and DMS-0608663 at University of North Carolina at Chapel Hill.