改进的多队列VC调度算法模型

Improved Multi-queued Algorithm Model for VC

在分析VC(VirtualClock)和GPS/PGPS(GeneralizedProcessorSharing/Packet by packetGeneralizedPro cessorSharing)分组调度算法的优点和缺点的基础上,提出了一种结合GPS调度算法特性的改进VC调度算法模型———多队列VC调度算法MQVC(Multi QueuedVirtualClock)。阐述了MQVC的设计目标、改进措施,并给出了MQVC算法模型和算法描述,通过定理和引理证明了该模型与单队列VC和PGPS调度算法模型相比,分组排序复杂度由原来O(mnlog(mn))降为O(mlogm),使实现复杂度、系统调度性能和包丢失等方面均有明显改善。

Based on the analysis of VC(Virtual Clock) and GPS/PGPS(Generalized Processor Sharing/Packet-by-packet Generalized Processor Sharing), a new scheduling algorithm is proposed,which is an improved virtual clock packet scheduling algorithm model with GPS scheduling algorithm's characteristics, and named as is MQVC(Multi-Queued Virtual Clock). The design objectives,improving methods,MQVC model and algorithm description in pseudo code are presented. It is proved theoretically that this model is much better than single-queued VC and PGPS scheduling algorithm model in such aspects as implementation complexity, system scheduling performances and packet loss.