| In this paper we present a new scheduler, the alpha-scheduler, which performs better on heavy trailed traffic than the Foreground-Background (FB) scheduler which is known to be optimal in scheduling traffic which has unknown characteristics. The alpha-scheduler is able to provide a closer approximation to the Shortest Remaining Processing Time (SRPT) scheduler which is known to provide optimal scheduling in the case when the length of the packets to be scheduled is known. We are able to improve our alpha-scheduler SRPT approximation by basing our expected remaining processing time on an estimate of the shape parameter, alpha, from the standard heavy tailed Pareto complementary probability distribution function, ct^-alpha. We review various methods of estimating alpha based on linear regression methods on the standard Log-Log Complement Distribution plot first proposed by Crovella in [5] and studied in more detail in [4]. We show that even using the standard sliding window least mean square estimator our scheduler exhibits improved performance over the FB scheduler. The particular scheduling problem we investigate in detail concerns the servicing of a number of ingress flows being fed by heavy tailed distributions. The egress channel is a bottleneck link, for example a shared wireless TDMA domain. Each flow is characterized as having a distinct shape parameter which may change (slowly) over time. While the scheduling is real time, the alpha estimation does not need to be. For example, the traffic pattern associated with a particular link might change when a user upgrades a software package which employs a new data communication model. We report on numerical experiments in which we schedule generated samples with the perfect knowledge of alpha and experiments in which we attempt to use our Pareto shape parameter estimation methods. We show that the scheduling QoS metrics introduced in [1], stochastically bound slowdown and response time, are improved with our scheduler versus the Foreground-Background scheduler reported on in [1]. |
| F. Dell Kronewitter is a senior member of technical staff at San Diego Research Center, Inc. He received the Ph.D., M.S., and B.S. degrees in mathematics from University of California San Diego, Irvine, and Santa Barbara respectively, completing his studies in 2000. His research interests include computer algebra, embedded systems, wireless networking, and network traffic engineering. |