一种支持DiffServ模型的全分布式调度算法  

A Distributed DiffServ Supporting Scheduling Algorithm

作　　者：伊鹏[1] 扈红超[1] 于婧[1] 汪斌强[1] 

机构地区：[1]国家数字交换系统工程技术研究中心,河南郑州450002

出　　处：《软件学报》2008年第7期1847-1855,共9页Journal of Software

基　　金：the National Natural Science Foundation of China under Grant No.60572042(国家自然科学基金);the National High-Tech Research and Development Plan of China under Grant No.2005AA121210(国家高技术研究发展计划(863));the National Basic Research Program of China under Grant No.2007CB307102(国家重点基础研究发展计划(973))

摘　　要：调度算法设计对于网络路由设备实现区分服务(DiffServ)模型的单跳行为(per hop behavior,简称PHB)至关重要.现有支持DiffServ模型的调度算法普遍基于输出排队(output queued,简称OQ)或是输入排队(input queued,简称IQ)交换结构进行设计,均无法在高速环境下提供高性能的调度.基于联合输入/交叉节点排队(combinedinput-crosspoint-queued,简称CICQ)交换结构提出一种支持DiffServ模型的全分布式调度算法DDSS (distributed DiffServ supporting scheduling),并通过理论分析对其公平性进行了验证.DDSS算法采用基于预约带宽的逐级流量控制机制实现所有预约带宽在快速转发(expedited forwarding,简称EF)业务与确保转发(assured forwarding,简称AF)业务之间的分配,采用优先级调度机制为EF业务提供低延迟服务,算法复杂度为O(log N).仿真结果表明,DDSS算法具有良好的时延性能和公平特性,与现有算法相比,能够更好地支持DiffServ模型.Scheduling algorithm is very important for network design to implement per hop behaviors （PHBs） in DiffServ model. Most of the presented DiffServ supporting scheduling algorithms are based on output queued （OQ） switches or input queued （IQ） switches, which are not suitable to be used in high speed network. This paper proposes a distributed DiffServ supporting scheduling （DDSS） algorithm based on combined input-crosspoint -queued （CICQ） switches. Theoretical analysis illuminates that the DDSS algorithm can obtain good fairness. The DDSS algorithm adopts a two-stage flow control mechanism based on periodic statistic to achieve fair bandwidth allocation for expedited forwarding （EF） and assured forwarding （AF） traffic, and uses a priority scheduling mechanism to provide lower delay for EF traffic. The time complexity of the DDSS algorithm is only O（log N）, hence is practical and scalable for high speed network. Simulation results show that DDSS algorithm can obtain good fairness and delay performance. It is more appropriate to be used to support the DiffServ model.

关 键 词：区分服务模型 服务质量 调度 流量控制 带缓存交叉开关 

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