Filter Scheduling Function Model In Internet Server: Resource Configuration, Performance Evaluation And Optimal Scheduling

<p>ABSTRACT</p> <p>FILTER SCHEDULING FUNCTION MODEL IN INTERNET SERVER:</p> <p>RESOURCE CONFIGURATION, PERFORMANCE EVALUATION AND</p> <p>OPTIMAL SCHEDULING</p> <p>by</p> <p>MINGHUA XU</p> <p>August 2010</p> <p>Advisor: Dr. Cheng-Zhong Xu</p> <p>Major: Computer Engineering</p> <p>Degree: Doctor of Philosophy</p> <p>Internet traffic often exhibits a structure with rich high-order statistical properties like selfsimilarity</p> <p>and long-range dependency (LRD). This greatly complicates the problem of</p> <p>server performance modeling and optimization. On the other hand, popularity of Internet</p> <p>has created numerous client-server or peer-to-peer applications, with most of them,</p> <p>such as online payment, purchasing, trading, searching, publishing and media streaming,</p> <p>being timing sensitive and/or financially critical. The scheduling policy in Internet servers</p> <p>is playing central role in satisfying service level agreement (SLA) and achieving savings</p> <p>and efficiency in operations. The increasing popularity of high-volume performance critical</p> <p>Internet applications is a challenge for servers to provide individual response-time guarantees.</p> <p>Existing tools like queuing models in most cases only hold in mean value analysis</p> <p>under the assumption of simplified traffic structures.</p> <p>Considering the fact that most Internet applications can tolerate a small percentage of</p> <p>deadline misses, we define a decay function model characterizes the relationship between</p> <p>the request delay constraint, deadline misses, and server capacity in a transfer function</p> <p>based filter system. The model is general for any time-series based or measurement based</p> <p>processes. Within the model framework, a relationship between server capacity, scheduling</p> <p>policy, and service deadline is established in formalism. Time-invariant (non-adaptive)</p> <p>resource allocation policies are design and analyzed in the time domain. For an important</p> <p>class of fixed-time allocation policies, optimality conditions with respect to the correlation</p> <p>of input traffic are established. The upper bound for server capacity and service level are derived</p> <p>with general Chebshev's inequality, and extended to tighter boundaries for unimodal</p> <p>distributions by using VysochanskiPetunin's inequality.</p> <p>For traffic with strong LRD, a design and analysis of the decay function model is done</p> <p>in the frequency domain. Most Internet traffic has monotonically decreasing strength of</p> <p>variation functions over frequency. For this type of input traffic, it is proved that optimal</p> <p>schedulers must have a convex structure. Uniform resource allocation is an extreme case</p> <p>of the convexity and is proved to be optimal for Poisson traffic. With an integration of</p> <p>the convex-structural principle, an enhance GPS policy improves the service quality significantly.</p> <p>Furthermore, it is shown that the presence of LRD in the input traffic results</p> <p>in shift of variation strength from high frequency to lower frequency bands, leading to a</p> <p>degradation of the service quality.</p> <p>The model is also extended to support server with different deadlines, and to derive</p> <p>an optimal time-variant (adaptive) resource allocation policy that minimizes server load</p> <p>variances and server resource demands. Simulation results show time-variant scheduling</p> <p>algorithm indeed outperforms time-invariant optimal decay function scheduler.</p> <p>Internet traffic has two major dynamic factors, the distribution of request size and the</p> <p>correlation of request arrival process. When applying decay function model as scheduler</p> <p>to random point process, corresponding two influences for server workload process is revealed</p> <p>as, first, sizing factor--interaction between request size distribution and scheduling</p> <p>functions, second, correlation factor--interaction between power spectrum of arrival process</p> <p>and scheduling function. For the second factor, it is known from this thesis that convex</p> <p>scheduling function will minimize its impact over server workload. Under the assumption</p> <p>of homogeneous scheduling function for all requests, it shows that uniform scheduling is</p> <p>optimal for the sizing factor. Further more, by analyzing the impact from queueing delay</p> <p>to scheduling function, it shows that queueing larger tasks vs. smaller ones leads to less</p> <p>reduction in sizing factor, but at the benefit of more decreasing in correlation factor in the</p> <p>server workload process. This shows the origin of optimality of shortest remain processing</p> <p>time (SRPT) scheduler.</p>

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Open Access Dissertation

Discipline thesis:degree_discipline

Electrical and Computer Engineering

Year dc:date.available

2010

Author dc:creator

• Xu, Minghua

Contributors dc:contributor

• Cheng-Zhong Xu

• Filter design
• Frequency domain analysis
• Internet Server
• Resource Allocation
• Scheduling
• Computer Engineering
• Computer Sciences

Repository record dc:identifier

https://digitalcommons.wayne.edu/oa_dissertations/70

OAI identifier oai:identifier

oai:digitalcommons.wayne.edu:oa_dissertations-1069