Filter Design and Analysis in Frequency Domain for Server Scheduling and Optimization

• Published in: IEEE transactions on parallel and distributed systems 2010-11, Vol.21 (11), p.1573-1585
• Main Authors: Cheng-Zhong Xu, Minghua Xu, Le Yi Wang, Yin, George
• Format: Article
• Language: English
• Subjects: Design optimization; filter design; Finite impulse response filter; Frequency domain analysis; Geographic information systems; Global Positioning System; Impulse response; Information filtering; Information filters; Internet; Internet server; Optimal scheduling; Optimization; Quality of service; resource allocation; Satellite navigation systems; Scheduling; Servers; Studies; Traffic control; Traffic engineering; Traffic flow; Value analysis; Web server
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2010.22

Internet traffic often exhibits a structure with rich high-order statistical properties like self-similarity and long-range dependency (LRD). This greatly complicates the problem of server performance modeling and optimization. Existing tools like queuing models in most cases only hold in mean value analysis under the assumption of simplified traffic structures. In this paper, we present a filter model to characterize the relationship among the factors of server capacity, request scheduling, and service quality for general input traffic. By the model, a server scheduler operates as an finite-duration impulse response (FIR) filter that transforms request processes into workload processes with the objective of minimizing load variation or overload probability, and meanwhile, without violating request response deadlines as defined in service-level agreements. We present a design and analysis of the filter for traffic with strong LRD in the frequency domain. Most Internet traffic has monotonically decreasing strength of variation functions over frequency. For this type of input traffic, we prove that optimal schedulers must have a convex structure. Uniform resource allocation is an extreme case of the convexity and is proved to be optimal for Poisson traffic. We integrate the convex structural principle with the Generalized Processor Sharing (GPS) discipline and show that the enhanced GPS policy improves the service quality significantly. Furthermore, we show that the presence of LRD in the input traffic results in shift of variation strength from high frequency to lower frequency bands and consequently leads to a degradation of the service quality.