一种两步迭代匹配算法及其性能分析

摘要

基于VOQ的 crossbar交换结构在高速互联网络中应用十分广泛。现有的VOQ调度算法以迭代方式工作，通常分为三步：请求、授权和接受。通过将仲裁合并到请求步骤，可以省略接受步骤，用来实现两步迭代匹配算法。提出了一种适用于两步迭代匹配算法的高效硬件实现结构，并进行了大量的仿真。仿真结果显示，两步迭代匹配算法可以达到与三步迭代匹配算法类似的性能。%Virtual output queued ( VOQ) crossbar switches have been widely used as high speed intercon-nects . Existing practical VOQ scheduling algorithms work in an iterative manner and each iteration usually includes three steps:request,grant and accept. By incorporating arbitration into the request step the ac-cept step can be eliminated,and two-step iterative matching can be achieved. We also propose a hard-ware efficient implementation for the two-step iterative matching algorithms,and conduct extensive simu-lations. The simulation results demonstrate that two-step algorithms have almost the same performance as that of three-step algorithms.