摘要： 在串行RapidIO传输过程中，路由选路算法是影响传输性能的重要因素之一。针对串行高速输入-输出（SRIO）网络深度优先搜索分配路径非最优问题，提出一种负载均衡最短路径路由算法。通过广度优先搜索对SRIO网络中的节点进行枚举并建立网络拓扑信息，以路由跳数定义路由的成本，根据改进Floyd-WarShall算法计算并保存交换节点间的K最短路径。给出预期负载的概念和链路上的路由路径数量来定义链路的负载，采用负载均衡算法从K最短路径中进行选路，建立SRIO网络最短路径约束的负载均衡路由。实验结果表明，与深度遍历路由算法、最小跳数算法相比，该算法在网络传输平均跳数、链路平均负载和链路负载均衡方面有更好的表现，能够有效提升SRIO路由网络的稳定性。

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

Abstract: 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.

Key words: load balancing, dynamic programming, Serial Rapid Input and Output(SRIO), Breadth First Search(BFS), K shortest path

中图分类号: 

• TP311