中文摘要：

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