ABSTRACTFILTER SCHEDULING FUNCTION MODEL IN INTERNET SERVER:RESOURCE CONFIGURATION, PERFORMANCE EVALUATION ANDOPTIMAL SCHEDULINGbyMINGHUA XUAugust 2010Advisor: Dr. Cheng-Zhong XuMajor: Computer EngineeringDegree: Doctor of PhilosophyInternet traffic often exhibits a structure with rich high-order statistical properties like selfsimilarityand long-range dependency (LRD). This greatly complicates the problem ofserver performance modeling and optimization. On the other hand, popularity of Internethas created numerous client-server or peer-to-peer applications, with most of them,such as online payment, purchasing, trading, searching, publishing and media streaming,being timing sensitive and/or financially critical. The scheduling policy in Internet serversis playing central role in satisfying service level agreement (SLA) and achieving savingsand efficiency in operations. The increasing popularity of high-volume performance criticalInternet applications is a challenge for servers to provide individual response-time guarantees.Existing tools like queuing models in most cases only hold in mean value analysisunder the assumption of simplified traffic structures.Considering the fact that most Internet applications can tolerate a small percentage ofdeadline misses, we define a decay function model characterizes the relationship betweenthe request delay constraint, deadline misses, and server capacity in a transfer functionbased filter system. The model is general for any time-series based or measurement basedprocesses. Within the model framework, a relationship between server capacity, schedulingpolicy, and service deadline is established in formalism. Time-invariant (non-adaptive)resource allocation policies are design and analyzed in the time domain. For an importantclass of fixed-time allocation policies, optimality conditions with respect to the correlationof input traffic are established. The upper bound for server capacity and service level are derivedwith general Chebshev's inequality, and extended to tighter boundaries for unimodaldistributions by using VysochanskiPetunin's inequality.For traffic with strong LRD, a design and analysis of the decay function model is donein the frequency domain. Most Internet traffic has monotonically decreasing strength ofvariation functions over frequency. For this type of input traffic, it is proved that optimalschedulers must have a convex structure. Uniform resource allocation is an extreme caseof the convexity and is proved to be optimal for Poisson traffic. With an integration ofthe convex-structural principle, an enhance GPS policy improves the service quality significantly.Furthermore, it is shown that the presence of LRD in the input traffic resultsin shift of variation strength from high frequency to lower frequency bands, leading to adegradation of the service quality.The model is also extended to support server with different deadlines, and to derivean optimal time-variant (adaptive) resource allocation policy that minimizes server loadvariances and server resource demands. Simulation results show time-variant schedulingalgorithm indeed outperforms time-invariant optimal decay function scheduler.Internet traffic has two major dynamic factors, the distribution of request size and thecorrelation of request arrival process. When applying decay function model as schedulerto random point process, corresponding two influences for server workload process is revealedas, first, sizing factor--interaction between request size distribution and schedulingfunctions, second, correlation factor--interaction between power spectrum of arrival processand scheduling function. For the second factor, it is known from this thesis that convexscheduling function will minimize its impact over server workload. Under the assumptionof homogeneous scheduling function for all requests, it shows that uniform scheduling isoptimal for the sizing factor. Further more, by analyzing the impact from queueing delayto scheduling function, it shows that queueing larger tasks vs. smaller ones leads to lessreduction in sizing factor, but at the benefit of more decreasing in correlation factor in theserver workload process. This shows the origin of optimality of shortest remain processingtime (SRPT) scheduler.
