Analysis of the EDF family of schedulers.
Loading...
Date
2009
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Modern telecommunications companies are moving away from conventional circuit-switched
architectures to more versatile packet-switched infrastructures. Traditional First-In-FirstOut
(FIFO) queues that are currently multiplexing IP traffic are not able to meet the
strict Quality-of-Service (QoS) requirements of delay sensitive real-time traffic.
Two main solution families exist that separate heterogeneous traffic into appropriate
classes. The first is known as Generalized Processor Sharing (GPS), which divides the
available bandwidth among the contending classes, proportionally to the throughput guarantee
negotiated with each class. GPS and its myriad of packetised variants are relatively
easy to analyse, as the service rate of individual classes is directly related to its throughput
guarantee. As GPS splits the arriving traffic into separate queues, it is useful for best-effort
traffic, supplying each class of traffic with either a maximum or minimum amount
of bandwidth that it deserves.
The second solution is the Earliest Deadline First (EDF) scheduler, also known as Earliest
Due Date (EDD). Each traffic class has a delay deadline, by which the individual packets
need to be served in order to meet their heterogeneous QoS requirements. EDF selects
packets that are closest to their deadline. It is therefore primarily useful for delay sensitive
real-time traffic. Although this is a simple algorithm, it turns out to be surprisingly difficult
to analyse. Several papers attempted to analyse EDF. Most of them found either discrete
bounds, which lie far away from the mean, or stochastic bounds which tend to capture
the delay behaviour of the traffic more accurately.
After the introductory first chapter, this thesis simulates a realistic cellular environment,
where packets of various classes of service are transmitted across an HSDPA air interface.
The aim is to understand the behaviour of EDF and its channel aware Opportunistic EDF
scheduler compared to other scheduling families commonly used in HSDPA environments.
In particular, Round Robin is simulated as the most simplistic scheduler. Max ell chooses
packets solely based on the best channel conditions. Finally, PF -T is a scheme that tries
to maximise the overall transmission rate that packets experience, but this metric gets
divided by the throughput that each class already achieved. This introduces a form of
long-term fairness that prevents the starvation of individual classes.
The third chapter contains the main analysis, which uses Large Deviation principles and
the Effective Bandwidth theory to approximate the deadline violation probability and the
delay density function of EDF in a wired network. A definition for the fairness of EDF is
proposed. The analysis is extended to approximate the stochastic fairness distribution.
In the fourth chapter of the thesis an opportunistic EDF scheduler is proposed for mobile
legs of a network that takes advantage of temporary improvements in the channel conditions.
An analytical model is developed that predicts the delay density function of the
opportunistic EDF scheduler. The channel propagation gain is assumed to be log-normally
distributed, which requires graphical curve fitting, as no closed-form solution exists
Description
Thesis (Ph.D.)-University of KwaZulu-Natal, Durban, 2009.
Keywords
Real-time data processing., Computer network protocols., Computer scheduling., Theses--Electronic engineering.