一种公平输入排队调度算法  

A Scheduling Algorithm for Input Queued Switch with Guaranteed Fairness

作　　者：周卫华[1] 朱新宁[1] 武穆清[1] 丁炜[1] 

机构地区：[1]北京邮电大学宽带通信网络实验室,北京100876

出　　处：《电子与信息学报》2005年第3期341-345,共5页Journal of Electronics & Information Technology

基　　金：华为科技基金项目"太比特路由器交换结构及调度算法研究"教育部博士学科点专项科研基金(No.20020013011)资助课题

摘　　要：输入排队交换结构以其良好的可扩展性被越来越多的高速交换机和路由器所采用。当前的调度算法大都以牺牲公平性来换取最大的吞吐量。但随着对QoS支持的要求增强,适用于输入排队交换结构的高效、公平的调度算法成为迫切需要解决的问题。该文提出了一种具有公平性保证的基于虚服务量的公平调度算法。理论分析和计算机仿真都表明算法在信元时延和公平性方面都能提供较好的保证。算法还具有与iSLIP相同的较低通信开销,以及和iLQF相同的算法复杂度。因此,算法具有较好的实用性。The input queued switch fabric, because of its scalability, has been implemented in more and more high speed switches and routers. Existing scheduling algorithms attempt to get the maximum throughput at the expense of fairness. As the need for Quality of Service (QoS) becomes stronger, the efficient scheduling algorithm with guaranteed fairness for Input Queued (IQ) switch has become an urgent problem. In this paper a virtual service based fair scheduling algorithm with guaranteed fairness for IQ is proposed. Theoretical analysis and computer simulation show that this algorithm can provide better performance in respects of fairness and cell delay. With the same low communication cost as iSLIP and the same computing complexity as iLQF, this algorithm has better practicability.

关 键 词：输入排队 公平性 QOS 统一服务量 

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