摘要
在分析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.
出处
《吉林大学学报（信息科学版）》
CAS
2005年第1期86-91,共6页
Journal of Jilin University（Information Science Edition）
基金
吉林省自然科学基金资助项目(20030522 2)
关键词
队列
分组调度算法
VC
调度性能
复杂度
算法模型
包丢失
统调
GPS
优点
scheduling algorithm
virtual clock
multi-queued virtual clock(MQVC)
generalized processor sharing(GPS)
quality of service
