作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (3): 214-221,228. doi: 10.19678/j.issn.1000-3428.0056116

• 体系结构与软件技术 • 上一篇    下一篇

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

李嘉伟, 张激, 赵俊才, 丁如艺   

  1. 中国电子科技集团公司第三十二研究所, 上海 201808
  • 收稿日期:2019-09-25 修回日期:2019-11-07 发布日期:2019-11-12
  • 作者简介:李嘉伟(1994-),男,硕士研究生,主研方向为嵌入式操作系统;张激,研究员;赵俊才,博士;丁如艺,硕士研究生。
  • 基金资助:
    DSP软件二次开发环境技术项目(GS90073)。

A Load Balancing Shortest Path Routing Algorithm for SRIO Network

LI Jiawei, ZHANG Ji, ZHAO Juncai, DING Ruyi   

  1. The 32 nd Research Institute of China Electronics Technology Group Corporation, Shanghai 201808, China
  • Received:2019-09-25 Revised:2019-11-07 Published:2019-11-12

摘要: 在串行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

中图分类号: