一种SRIO网络负载均衡最短路径路由算法  

A Load Balancing Shortest Path Routing Algorithm for SRIO Network

作　　者：李嘉伟 张激[1] 赵俊才 丁如艺 LI Jiawei;ZHANG Ji;ZHAO Juncai;DING Ruyi(The 32nd Research Institute of China Electronics Technology Group Corporation,Shanghai 201808,China)

机构地区：[1]中国电子科技集团公司第三十二研究所,上海201808

出　　处：《计算机工程》2020年第3期214-221,228,共9页Computer Engineering

基　　金：DSP软件二次开发环境技术项目(GS90073)。

摘　　要：在串行RapidIO传输过程中,路由选路算法是影响传输性能的重要因素之一。针对串行高速输入-输出(SRIO)网络深度优先搜索分配路径非最优问题,提出一种负载均衡最短路径路由算法。通过广度优先搜索对SRIO网络中的节点进行枚举并建立网络拓扑信息,以路由跳数定义路由的成本,根据改进Floyd-WarShall算法计算并保存交换节点间的K最短路径。给出预期负载的概念和链路上的路由路径数量来定义链路的负载,采用负载均衡算法从K最短路径中进行选路,建立SRIO网络最短路径约束的负载均衡路由。实验结果表明,与深度遍历路由算法、最小跳数算法相比,该算法在网络传输平均跳数、链路平均负载和链路负载均衡方面有更好的表现,能够有效提升SRIO路由网络的稳定性。Routing selection algorithms are one of the important factors affecting transmission performance during serial RapidIO transmission.Aiming at the non-optimal allocation path of Serial Rapid Input and Output(SRIO)network depth search,this paper proposes a load balancing shortest path routing algorithm.The algorithm enumerates the nodes in the SRIO network by Breadth First Search(BFS),establishes network topology information,and defines the cost of routing by routing hops.The improved Floyd-WarShall algorithm is used to calculate and save the K shortest path between switching nodes.The load of the link is defined by giving the concept of the expected load and the number of routing paths on the link.The load balancing is used to select the path from K shortest path,so as to establish the load balancing routing with the shortest path constraint of the SRIO network.Experimental results show that compared with algorithms such as deep traversal routing configuration and minimum hops,the proposed algorithm has better performance in terms of average network transmission hops,link average load and link load balancing,and can effectively improve the stability of SRIO network.

关 键 词：负载均衡 动态规划 串行高速输入-输出 广度优先搜索 K最短路径 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]