ABSTRACT
FILTER SCHEDULING FUNCTION MODEL IN INTERNET SERVER:
RESOURCE CONFIGURATION, PERFORMANCE EVALUATION AND
OPTIMAL SCHEDULING
by
MINGHUA XU
August 2010
Advisor: Dr. Cheng-Zhong Xu
Major: Computer Engineering
Degree: Doctor of Philosophy
Internet traffic often exhibits a structure with rich high-order statistical properties like selfsimilarity
and long-range dependency (LRD). This greatly complicates the problem of
server performance modeling and optimization. On the other hand, popularity of Internet
has 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 servers
is playing central role in satisfying service level agreement (SLA) and achieving savings
and efficiency in operations. The increasing popularity of high-volume performance critical
Internet 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 analysis
under the assumption of simplified traffic structures.
Considering the fact that most Internet applications can tolerate a small percentage of
deadline misses, we define a decay function model characterizes the relationship between
the request delay constraint, deadline misses, and server capacity in a transfer function
based filter system. The model is general for any time-series based or measurement based
processes. Within the model framework, a relationship between server capacity, scheduling
policy, and service deadline is established in formalism. Time-invariant (non-adaptive)
resource allocation policies are design and analyzed in the time domain. For an important
class of fixed-time allocation policies, optimality conditions with respect to the correlation
of input traffic are established. The upper bound for server capacity and service level are derived
with general Chebshev's inequality, and extended to tighter boundaries for unimodal
distributions by using VysochanskiPetunin's inequality.
For traffic with strong LRD, a design and analysis of the decay function model is done
in the frequency domain. Most Internet traffic has monotonically decreasing strength of
variation functions over frequency. For this type of input traffic, it is proved 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. With an integration of
the 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 results
in shift of variation strength from high frequency to lower frequency bands, leading to a
degradation of the service quality.
The model is also extended to support server with different deadlines, and to derive
an optimal time-variant (adaptive) resource allocation policy that minimizes server load
variances and server resource demands. Simulation results show time-variant scheduling
algorithm indeed outperforms time-invariant optimal decay function scheduler.
Internet traffic has two major dynamic factors, the distribution of request size and the
correlation of request arrival process. When applying decay function model as scheduler
to random point process, corresponding two influences for server workload process is revealed
as, first, sizing factor--interaction between request size distribution and scheduling
functions, second, correlation factor--interaction between power spectrum of arrival process
and scheduling function. For the second factor, it is known from this thesis that convex
scheduling function will minimize its impact over server workload. Under the assumption
of homogeneous scheduling function for all requests, it shows that uniform scheduling is
optimal for the sizing factor. Further more, by analyzing the impact from queueing delay
to scheduling function, it shows that queueing larger tasks vs. smaller ones leads to less
reduction in sizing factor, but at the benefit of more decreasing in correlation factor in the
server workload process. This shows the origin of optimality of shortest remain processing
time (SRPT) scheduler.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Xu, Minghua"],"institution":null,"degree_name":"Ph.D.","degree_level":"Open Access Dissertation","degree_discipline":"Electrical and Computer Engineering","degree_department":null,"school":null,"contributors":["Cheng-Zhong Xu"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-01-01T08:00:00Z","date_published":"2010-01-01T08:00:00Z","updated_at":"2026-07-24T05:58:35Z","subjects":["Filter design","Frequency domain analysis","Internet Server","Resource Allocation","Scheduling","Computer Engineering","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.wayne.edu/oa_dissertations/70","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Cheng-Zhong Xu"]},{"key":"dc:creator","label":"Author","values":["Xu, Minghua"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2010-09-23T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical and Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Open Access Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Filter design","Frequency domain analysis","Internet Server","Resource Allocation","Scheduling","Computer Engineering","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.wayne.edu/oa_dissertations/70"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["ABSTRACT
FILTER SCHEDULING FUNCTION MODEL IN INTERNET SERVER:
RESOURCE CONFIGURATION, PERFORMANCE EVALUATION AND
OPTIMAL SCHEDULING
by
MINGHUA XU
August 2010
Advisor: Dr. Cheng-Zhong Xu
Major: Computer Engineering
Degree: Doctor of Philosophy
Internet traffic often exhibits a structure with rich high-order statistical properties like selfsimilarity
and long-range dependency (LRD). This greatly complicates the problem of
server performance modeling and optimization. On the other hand, popularity of Internet
has 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 servers
is playing central role in satisfying service level agreement (SLA) and achieving savings
and efficiency in operations. The increasing popularity of high-volume performance critical
Internet 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 analysis
under the assumption of simplified traffic structures.
Considering the fact that most Internet applications can tolerate a small percentage of
deadline misses, we define a decay function model characterizes the relationship between
the request delay constraint, deadline misses, and server capacity in a transfer function
based filter system. The model is general for any time-series based or measurement based
processes. Within the model framework, a relationship between server capacity, scheduling
policy, and service deadline is established in formalism. Time-invariant (non-adaptive)
resource allocation policies are design and analyzed in the time domain. For an important
class of fixed-time allocation policies, optimality conditions with respect to the correlation
of input traffic are established. The upper bound for server capacity and service level are derived
with general Chebshev's inequality, and extended to tighter boundaries for unimodal
distributions by using VysochanskiPetunin's inequality.
For traffic with strong LRD, a design and analysis of the decay function model is done
in the frequency domain. Most Internet traffic has monotonically decreasing strength of
variation functions over frequency. For this type of input traffic, it is proved 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. With an integration of
the 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 results
in shift of variation strength from high frequency to lower frequency bands, leading to a
degradation of the service quality.
The model is also extended to support server with different deadlines, and to derive
an optimal time-variant (adaptive) resource allocation policy that minimizes server load
variances and server resource demands. Simulation results show time-variant scheduling
algorithm indeed outperforms time-invariant optimal decay function scheduler.
Internet traffic has two major dynamic factors, the distribution of request size and the
correlation of request arrival process. When applying decay function model as scheduler
to random point process, corresponding two influences for server workload process is revealed
as, first, sizing factor--interaction between request size distribution and scheduling
functions, second, correlation factor--interaction between power spectrum of arrival process
and scheduling function. For the second factor, it is known from this thesis that convex
scheduling function will minimize its impact over server workload. Under the assumption
of homogeneous scheduling function for all requests, it shows that uniform scheduling is
optimal for the sizing factor. Further more, by analyzing the impact from queueing delay
to scheduling function, it shows that queueing larger tasks vs. smaller ones leads to less
reduction in sizing factor, but at the benefit of more decreasing in correlation factor in the
server workload process. This shows the origin of optimality of shortest remain processing
time (SRPT) scheduler.
"]},{"key":"dc:title","label":"Title","values":["Filter Scheduling Function Model In Internet Server: Resource Configuration, Performance Evaluation And Optimal Scheduling"]}]}],"canonical_facts":{"dc:contributor":["Cheng-Zhong Xu"],"dc:creator":["Xu, Minghua"],"dc:date.available":["2010-09-23T07:00:00Z"],"dc:description.abstract":["ABSTRACT
FILTER SCHEDULING FUNCTION MODEL IN INTERNET SERVER:
RESOURCE CONFIGURATION, PERFORMANCE EVALUATION AND
OPTIMAL SCHEDULING
by
MINGHUA XU
August 2010
Advisor: Dr. Cheng-Zhong Xu
Major: Computer Engineering
Degree: Doctor of Philosophy
Internet traffic often exhibits a structure with rich high-order statistical properties like selfsimilarity
and long-range dependency (LRD). This greatly complicates the problem of
server performance modeling and optimization. On the other hand, popularity of Internet
has 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 servers
is playing central role in satisfying service level agreement (SLA) and achieving savings
and efficiency in operations. The increasing popularity of high-volume performance critical
Internet 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 analysis
under the assumption of simplified traffic structures.
Considering the fact that most Internet applications can tolerate a small percentage of
deadline misses, we define a decay function model characterizes the relationship between
the request delay constraint, deadline misses, and server capacity in a transfer function
based filter system. The model is general for any time-series based or measurement based
processes. Within the model framework, a relationship between server capacity, scheduling
policy, and service deadline is established in formalism. Time-invariant (non-adaptive)
resource allocation policies are design and analyzed in the time domain. For an important
class of fixed-time allocation policies, optimality conditions with respect to the correlation
of input traffic are established. The upper bound for server capacity and service level are derived
with general Chebshev's inequality, and extended to tighter boundaries for unimodal
distributions by using VysochanskiPetunin's inequality.
For traffic with strong LRD, a design and analysis of the decay function model is done
in the frequency domain. Most Internet traffic has monotonically decreasing strength of
variation functions over frequency. For this type of input traffic, it is proved 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. With an integration of
the 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 results
in shift of variation strength from high frequency to lower frequency bands, leading to a
degradation of the service quality.
The model is also extended to support server with different deadlines, and to derive
an optimal time-variant (adaptive) resource allocation policy that minimizes server load
variances and server resource demands. Simulation results show time-variant scheduling
algorithm indeed outperforms time-invariant optimal decay function scheduler.
Internet traffic has two major dynamic factors, the distribution of request size and the
correlation of request arrival process. When applying decay function model as scheduler
to random point process, corresponding two influences for server workload process is revealed
as, first, sizing factor--interaction between request size distribution and scheduling
functions, second, correlation factor--interaction between power spectrum of arrival process
and scheduling function. For the second factor, it is known from this thesis that convex
scheduling function will minimize its impact over server workload. Under the assumption
of homogeneous scheduling function for all requests, it shows that uniform scheduling is
optimal for the sizing factor. Further more, by analyzing the impact from queueing delay
to scheduling function, it shows that queueing larger tasks vs. smaller ones leads to less
reduction in sizing factor, but at the benefit of more decreasing in correlation factor in the
server workload process. This shows the origin of optimality of shortest remain processing
time (SRPT) scheduler.
"],"dc:identifier":["https://digitalcommons.wayne.edu/oa_dissertations/70"],"dc:subject":["Filter design","Frequency domain analysis","Internet Server","Resource Allocation","Scheduling","Computer Engineering","Computer Sciences"],"dc:title":["Filter Scheduling Function Model In Internet Server: Resource Configuration, Performance Evaluation And Optimal Scheduling"],"thesis:degree_discipline":["Electrical and Computer Engineering"],"thesis:degree_level":["Open Access Dissertation"],"thesis:degree_name":["Ph.D."]},"updated_at":"2026-07-24T05:58:35Z"}