保证速率的核心无状态分组调度算法  

Rate-Guaranteed Core-Stateless Packet Scheduling Algorithm

作　　者：秦岩[1] 史美林[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《北京理工大学学报》2006年第5期433-437,共5页Transactions of Beijing Institute of Technology

基　　金：国家自然科学基金资助项目(60273010)

摘　　要：提出一种新的核心无状态分组调度算法VCSVC(G)(vector core-stateless virtual clock).该算法在边界节点为分组计算理想模型下各节点对应的虚拟延迟,组成虚拟延迟矢量带在分组头中,是核心节点排序的依据,其长度上限G利用局部平均法实现.证明了VCSVC(G)与VC(virtual clock)具有相同延迟保证能力,计算了实际算法与理想模型速率保证精度的误差上限,并与两种核心无状态代表算法进行了比较分析.结果表明,通过调节参数G,算法可达到开销与速率保证精度的理想折衷,适用于广泛的用户需求.A new core-stateless packet scheduling algorithm, VCSVC（G） （vector core-stateless virtual clock）, is proposed. When a packet arrives at the edge of a network of VCSVC（G） servers, the ingress node computes the virtual delays for each packet at every node it traverses under the corresponding ideal single-flow system and encodes them into a virtual delay vector carried by the packet itself. The virtual delay vector is used for packets sorting at core nodes, and the upper bound G on its length is achieved by partial average technique. It is proved that VCSVC（ G ） has the same delay properties as the virtual clock （VC）. The maximum difference on the accuracy of rate guarantee between a network of VCSVC（ G ） servers and the corresponding ideal single-flow system is calculated. The algorithm is finally compared with two well-known core-stateless algorithms. From these results, it can be concluded that the balance between packet overhead and the accuracy of rate guarantee can be achieved by setting the parameter G appropriately, meaning that VCSVC（G） can meet a wide range of QoS requirements.

关 键 词：速率与延迟保证 核心无状态 可扩展性 虚拟延迟矢量 端到端延迟限制 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]