k-ary n-cube网络中跨区域适应性路由算法

Quadrant Crossing Adaptive Routing Algorithm in k-ary n-cube Networks

针对k-ary n-cube网络,提出一种无死锁、无活锁、负载均衡的跨区域路由算法(Q uadran tC ross ing R ou ting,QCR).算法按照分组源目的节点相对位置将网络划分路由区域,并给予这些区域不同的权重,同时设定跨区域规则,允许分组根据网络负载状态跨区域路由,这样就使得网络的流量分布更均衡.网络的负载程度由输出端口等待分组请求的时间间隔的大小决定.最后,利用OPNET对所提算法在不同流量模式下进行仿真.结果表明:相比已有的同类算法,如维序路由算法(D im ens ion O rder R ou ting,DOR),Duato及GAL等,QCR表现出较好的时延、吞吐性能.

A new quadrant crossing routing （QCR） algorithm for k-ary n-cube networks is proposed, which is load balanced, deadlock-free and livelock-free. According to the source and destination node of each packet, the network is divided into several quadrants with various weights. QCR sets quadrant crossing rule and allows packets tO cross quadrants based on network state, which makes traffic distribution more balanced. Network state is determined by the time interval between the last two requests to the same output. Finally, performance of the proposed routing algorithm is evaluated by OPNET under various traffic modes. The simulation results show that QCR outperforms the previously published routing algorithms, such as dimension order routing （DOR）, Duato＇s algorithm and GAL.