摘要
针对输入排队交换结构调度问题,提出了队列长度加权服务匹配的思想.基本思路是匹配求解基于实现极大匹配的并行迭代算法,但对于每一个输入输出匹配,一次可以保持超过一个时隙的一段时间,其长度为对应的虚拟输入队列长度的加权函数.依据这一思想,设计了一种基于轮转仲裁器的队列长度加权服务匹配算法.通过实现复杂性的分析与性能评估,给出了优选的权重函数.所提方案以极大尺寸匹配算法近似的复杂性,取得与极大权重匹配算法近似的性能,在非均匀流量模式下也能达到接近100%的吞吐效率,明显优于iSLIP和EiSLIP算法,适合于高性能输入排队路由器的应用.
Input queued switching architecture has attracted more attention. Due to its good scalability, it has become predominant in high performance switches and touters. In this paper, the concept of matching with queue length weighted service （MQWS） is presented to handle the scheduling problem for input queued switches. In the scheme the matching between inputs and outputs is established by parallel iteration algorithms usually used to implement maximal size matching, however, a matching of an input-output pair will be kept for a certain period after it was established and the length of the period is a function of the occupancy of the corresponding VOQ. Based on round robin arbiters, an implantation scheme of MQWS algorithm is proposed. And then an extensive evaluation of the presented scheme is carried out. According to their implementation complexity and the results of the performance evaluation, the preferential weighted functions are proposed. With the complexity similar to maximal size matching, MQWS achieves comparable performance of maximal weight matching, i.e. throughput approaching 100% under both uniform and nonuniform traffic, even by single iteration. This result obviously outperforms those of iSLIP and EiSLIP. Hence, the scheme presented in this paper is more suitable for high performance input queued switches and routers.
出处
《计算机学报》
EI
CSCD
北大核心
2006年第6期875-883,共9页
Chinese Journal of Computers
基金
中国科学院知识创新工程项目基金(KGCXZ-103)
国家自然科学基金(69983008)
中国科学院计算技术研究所基础研究基金(20056090)资助
关键词
交换
调度
输入排队
匹配算法
加权服务
switching, scheduling
input queuing
matching algorithm
weighted service
