TL;DR
This paper analyzes two-level processor-sharing (TLPS) scheduling disciplines, like PS+PS and FB+PS, for internet traffic. They show that these disciplines can significantly reduce mean job delay compared to standard processor sharing (PS), especially when job sizes have decreasing hazard rates, offering a practical way to prioritize shorter flows.
What Problem Does This Paper Address?
The internet's traffic patterns are characterized by a mix of very short and very long data flows. Standard scheduling algorithms like Processor Sharing (PS) treat all jobs equally, leading to long delays for short jobs caught behind long ones. While more advanced algorithms exist, like Foreground Background (FB), which can be optimal under certain conditions, their applicability and performance in more complex, multi-level scenarios are not fully understood. This paper aims to analyze the performance of two-level scheduling disciplines, which offer a practical way to differentiate between short and long flows by classifying them into priority levels, and to determine their effectiveness in reducing mean job delay, particularly in the context of M/G/1 queues.
Methods
The core of the paper's methodology lies in analyzing the "unfinished truncated work" (UTW) of jobs in the system. This metric represents the sum of remaining service times for jobs that have not yet reached a certain service threshold. The authors develop a framework that connects the UTW to the mean delay. Specifically, they show that if one scheduling discipline consistently has a lower mean UTW than another, it will also result in a lower mean delay, especially when the job size distribution has a decreasing hazard rate. They use both meanwise (expected value) and pathwise (realization-by-realization) arguments to compare different disciplines. The analysis is extended to general Multilevel Processor Sharing (MLPS) disciplines, not just two-level ones.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and uses synthetic service time distributions (e.g., bounded Pareto) for numerical examples.
Key Insights and Ideas
- UTW as a Predictor of Mean Delay: The paper establishes a strong link between the mean unfinished truncated work (UTW) and the mean delay. A lower UTW generally implies a lower mean delay, especially under certain hazard rate conditions. This provides a powerful analytical tool for comparing scheduling policies.
- Two-Level Scheduling for Prioritization: Two-level scheduling disciplines (TLPS), like PS+PS and FB+PS, offer a practical mechanism to differentiate between short and long flows. By classifying jobs based on their attained service, these policies can effectively prioritize shorter jobs.
- Hazard Rate Matters: The performance comparison of scheduling disciplines is highly dependent on the hazard rate of the job size distribution. Decreasing hazard rates favor policies that prioritize shorter jobs, while increasing hazard rates can lead to different optimal choices.
- PS+PS Outperforms PS: For decreasing hazard rates, the PS+PS discipline is shown to be consistently better than standard PS in terms of mean delay. This suggests that a simple two-priority system can significantly improve performance.
- FB's Pathwise vs. Meanwise Optimality: The paper highlights a subtle but important distinction: while FB might be optimal in a pathwise sense for minimizing unfinished untruncated work, it's not necessarily optimal for the truncated work, which is more directly related to mean delay. This clarifies some previous research findings.
Key Results
- Decreasing Hazard Rate: Under a decreasing hazard rate, the mean delay order is: FB < FB+PS < PS+PS < PS. This means FB is the best, followed by the two-level disciplines, and PS is the worst.
- Increasing and Bounded Hazard Rate: Under an increasing and bounded hazard rate, the order is reversed: FB > FB+PS > PS+PS > PS.
- PS+PS vs. PS: The PS+PS discipline is shown to be better than PS in reducing mean delay, with potential reductions of up to 40% observed in numerical examples.
- MLPS Disciplines: The paper generalizes these findings to multilevel processor sharing (MLPS) disciplines, providing a clear ordering based on the hazard rate and the specific scheduling policy used at each level.
Limitations and Future Work
- Poisson Arrival Assumption: The initial analysis relies on the assumption of Poisson arrivals. While pathwise arguments are used to relax this, further work could explore more general arrival processes.
- Specific Hazard Rate Conditions: The results are strongly tied to whether the hazard rate is decreasing or increasing and bounded. Analyzing disciplines under more complex or non-monotonous hazard rate behaviors would be valuable.
- Other Performance Metrics: The paper focuses on mean delay. Future research could investigate other performance metrics like slowdown, throughput, or fairness for these MLPS disciplines.
- Implementation Complexity: While TLPS disciplines are presented as practical, the paper acknowledges that implementing FB-like policies at the packet level can be complex. Further work on practical implementation strategies for these differentiated services would be beneficial.
Summary updated