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

作者：孙书韬; 贺思敏; 郑燕峰; 高文

来源：计算机学报, 2006, (06): 875-883.

• 交换
• 调度
• 输入排队
• 匹配算法
• 加权服务 switching
• scheduling
• input queuing
• matching algorithm
• weighted service

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

• 出版日期2006
• 单位中国传媒大学; 中国科学院大学; 中国科学院计算技术研究所