Browsing by Author "Scriba, Stefan Martin."

Now showing 1 - 2 of 2

Analysis of the EDF family of schedulers.
(2009) Scriba, Stefan Martin.; Takawira, Fambirai.
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
Scheduling in CDMA-based wireless packet networks.
(2003) Scriba, Stefan Martin.; Takawira, Fambirai.
Modern networks carry a wide range of different data types, each with its own individual requirements. The scheduler plays an important role in enabling a network to meet all these requirements. In wired networks a large amount of research has been performed on various schedulers, most of which belong to the family of General Processor Sharing (GPS) schedulers. In this dissertation we briefly discuss the work that has been done on a range of wired schedulers, which all attempt to differentiate between heterogeneous traffic. In the world of wireless communications the scheduler plays a very important role, since it can take channel conditions into account to further improve the performance of the network. The main focus of this dissertation is to introduce schedulers, which attempt to meet the Quality of Service requirements of various data types in a wireless environment. Examples of schedulers that take channel conditions into account are the Modified Largest Weighted Delay First (M-LWDF), as well as a new scheduler introduced in this dissertation, known as the Wireless Fair Largest Weighted Delay First (WF-LWDF) algorithm. The two schemes are studied in detail and a comparison of their throughput, delay, power, and packet dropping performance is made through a range of simulations. The results are compared to the performance offour other schedulers. The fairness ofM-LWDF and WFLWDF is determined through simulations. The throughput results are used to establish Chernoff bounds of the fairness of these two algorithms. Finally, a summary is given of the published delay bounds of various schedulers, and the tightness of the resultant bounds is discussed.