Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/13791
Title: Analysis of priority-based packet schedulers for proportional delay diferentiation
Authors: TAN CHEE WEI
Keywords: Quality of Service, Packet scheduling, Relative delay differentiation, Proportional delay differentiation, Network processor implementation
Issue Date: 6-Apr-2004
Source: TAN CHEE WEI (2004-04-06). Analysis of priority-based packet schedulers for proportional delay diferentiation. ScholarBank@NUS Repository.
Abstract: In this thesis, priority-based packet schedulers are analyzed in order to provide relative and proportional delay differentiation. We investigate a Probabilistic Priority (PP) scheduler that provides relative delay differentiation to different classes. We present an integer PP algorithm and show that PP is a special scheme of applying lottery scheduling to bandwidth allocation in a strict priority sense. We then propose a Multi-winner PP (MPP) scheduler using multi-winner lottery scheduling to improve the throughput and response time accuracy and a flexible ticket transfer algorithm to improve the deadline violation probability in probabilistic scheduling. Finally, we investigate the issue of parameter assignment for an MPP scheduler and use our techniques to implement a prototype Assured Forwarding (AF) mechanism in a network processor. Proportional Delay Differentiation (PDD) has stricter requirement than relative delay differentiation. We study the schedulability conditions of the Waiting Time Priority (WTP) packet scheduler on achieving multi-class PDD under load variation. Based on a necessary condition for positive scheduler parameters in general N-class WTP, we derive a sufficient condition for WTP to achieve PDD. The sufficiency therefore implies that PDD delay dynamics can be readily employed. Hence, using these results, we can determine and re-adjust the load spacings that have passed the necessary condition for positive scheduler parameters. The results obtained also quantify the maximum operational target ratio achievable in WTP for a given load distribution and allow us to relate results for WTP to the PDD model for general N-class in a precise manner. Next, based on an inequality relationship between scheduler parameters and target ratios, we propose a dynamic adjustment control technique to efficiently enhance the computation of scheduler parameters that uses iterative methods. We then evaluate the performance of this adjustment control mechanism. Lastly, we show that WTP can achieve both PDD and absolute QoS requirements under certain schedulability conditions by appropriate selection of scheduler parameters.
URI: http://scholarbank.nus.edu.sg/handle/10635/13791
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
last.png29.91 kBimage/png

OPEN

NoneThumbnail
View/Download
MSTHESIS.PDF442.14 kBAdobe PDF

OPEN

NoneView/Download

Page view(s)

254
checked on Jan 22, 2018

Download(s)

32
checked on Jan 22, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.