分组交换中基于权值动态补偿的公平调度算法

Fair Scheduling Algorithm Based on Dynamic Weight Compensation in Packet Switching Networks

针对WFQ (WeightedFairQueueing) 和WF2Q (Worst caseFairWeightedFairQueueing) 对某些会话欠公平的问题, 通过GPS(GeneralizedProcesorSharing) 公平性的定义, 在保证长期公平性的前提下引入了补偿模型, 以优化短期公平性, 提出一种新的基于权值动态补偿的分组公平调度算法CWFQ (Compensation basedWeightedFairQairQueueing)。该算法在考虑虚拟时间标签的选择条件下加入了最小化公平度量因子约束, 记录已经服务的服务量, 按会话权值有比例地对参照GPS系统的权值进行微调, 使CWFQ的短期公平性得到优化。而且通过模拟调度和定理证明发现, 新算法能够对会话的延迟和吞吐量提供与GPS近似的性能保证。

WFQ(Weighted Fairness Queueing) algorithm and WF^2Q are approximations of GPS(Generalized Procesor Sharing) in packets-based switching environment. After analyzing the unfairness in WFQ and WF^2Q respectively, and according to the definition of GPS fairness, this paper proposes a new scheme named CWFQ(Compensation-based Weighted Fair Qair Queueing) which dynamically modifies every session's weighted value based on proportional compensation judged by completed service and weighted values during scheduled time slots and introduce compensation model and minimum Fairness Index into virtual time tags to optimize short-term fairness reserving the long-term fairness. The scheduling simulation and theorems proved results demonstrate the new scheme can provide approximative delay and throughput bound for every session.