Analysis of priority-based packet schedulers for proportional delay diferentiation

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.