队列长度加权服务的输入排队交换结构匹配算法

摘要：

针对输入排队交换结构调度问题,提出了队列长度加权服务匹配的思想.基本思路是匹配求解基于实现极大匹配的并行迭代算法,但对于每一个输入输出匹配,一次可以保持超过一个时隙的一段时间,其长度为对应的虚拟输入队列长度的加权函数.依据这一思想,设计了一种基于轮转仲裁器的队列长度加权服务匹配算法.通过实现复杂性的分析与性能评估,给出了优选的权重函数.所提方案以极大尺寸匹配算法近似的复杂性,取得与极大权重匹配算法近似的性能,在非均匀流量模式下也能达到接近100%的吞吐效率,明显优于iSLIP和EiSLIP算法,适合于高性能输入排队路由器的应用.

关键词：交换、调度、输入排队、匹配算法、加权服务

所属期刊栏目：29

分类号：TP393(计算技术、计算机技术)

资助基金：中国科学院知识创新工程项目KGCXZ-103;中国科学院资助项目69983008;中国科学院基础研究项目20056090

在线出版日期：2006-06-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：875-883