基于最短路径的多子网链路层拓扑发现算法

计算机工程与应用 ›› 2016, Vol. 52 ›› Issue (2): 131-134.

基于最短路径的多子网链路层拓扑发现算法

孟颖翔1，高东怀2，许浩2，许卫中2

1.西北大学现代教育技术中心，西安 710069
2.第四军医大学网络中心，西安 710032

出版日期:2016-01-15 发布日期:2016-01-28

Link layer topology discovery for multi-subnet networks based on shortest path

MENG Yingxiang1, GAO Donghuai2, XU Hao2, XU Weizhong2

1.Contemporary Education Technology Center, Northwest University, Xi’an 710069, China
2.Network Center, Fourth Military Medical University, Xi’an 710032, China

Online:2016-01-15 Published:2016-01-28

摘要/Abstract

摘要： 针对当前基于地址转发表实现链路层拓扑发现的典型算法在复杂多子网环境下应用存在的问题，提出利用下行链路完整地址转发表构建并优化同一子网交换设备间的最短路径，实现链路层拓扑自动发现的算法。经理论和实际环境验证，证明该算法可以较好地发现复杂多子网链路层拓扑结构，具有较强的实践意义和推广价值。

关键词: 多子网, 链路层拓扑, 地址转发表, 下行链路, 最短路径

Abstract: The application of the typical link layer topology discovery algorithms based on address forwarding table is not ideal for multi-subnet networks. In view of the problem, this paper proposes a link layer topology discovery algorithm based on shortest path. Utilizing the complete downlink AFT, it constructs shortest paths which are between switch devices in the same subnet and then optimizes these paths to accomplish the algorithm. Verified by the theory and practice in actual network environment, the algorithm can discover the link layer topology for multi-subnet networks, it also has a strong practical significance and promotional value.

Key words: multi-subnet networks, link layer topology, address forwarding table, downlink, shortest path

孟颖翔1，高东怀2，许浩2，许卫中2. 基于最短路径的多子网链路层拓扑发现算法[J]. 计算机工程与应用, 2016, 52(2): 131-134.

MENG Yingxiang1, GAO Donghuai2, XU Hao2, XU Weizhong2. Link layer topology discovery for multi-subnet networks based on shortest path[J]. Computer Engineering and Applications, 2016, 52(2): 131-134.

[1]	李俊. 结合最短路径改进的社会力人群疏散仿真模型[J]. 计算机工程与应用, 2021, 57(8): 264-270.
[2]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[3]	李艳，王阳阳，张红岩，武优西. 不可达顶点剪枝算法及其在最短路径中的应用[J]. 计算机工程与应用, 2020, 56(15): 51-57.
[4]	张昕，严沛，郭阳，王慧慧. 基于k-shell的复杂网络最短路径近似算法[J]. 计算机工程与应用, 2019, 55(14): 54-60.
[5]	张林霞，何利文，黄俊. 基于SDN网络的安全设备路由研究[J]. 计算机工程与应用, 2018, 54(4): 103-109.
[6]	高遵海，高颖，程果. 图的赋权路径矩阵与所有点对最短路径问题[J]. 计算机工程与应用, 2017, 53(9): 47-50.
[7]	应文杰，徐开，徐少平. 羽毛球机器人机械臂运动轨迹多目标规划[J]. 计算机工程与应用, 2017, 53(3): 258-265.
[8]	姚博1，冯宏伟1，高原2，马佳丽1，冯筠1. 过必经节点集的动态剪枝搜索算法[J]. 计算机工程与应用, 2017, 53(15): 57-62.
[9]	袁亚博，刘羿，吴斌. 改进蚁群算法求解最短路径问题[J]. 计算机工程与应用, 2016, 52(6): 8-12.
[10]	韩建妙，刘业政. 基于遗传算法的超市最短导购路径推荐[J]. 计算机工程与应用, 2016, 52(4): 238-242.
[11]	侯晓琴1，胡志华1，高超峰1，罗勋杰2. 自动化仓库巷道网络AGV货区遍历优化——设计基于优先权遗传算法实现[J]. 计算机工程与应用, 2016, 52(12): 31-36.
[12]	吴幸良，涂风华. 采用图模型的个性化标签推荐方法[J]. 计算机工程与应用, 2015, 51(9): 142-146.
[13]	黄书力，胡大裟，蒋玉明. 经过指定的中间节点集的最短路径算法[J]. 计算机工程与应用, 2015, 51(11): 41-46.
[14]	耿显亚，许峰. 基于图论模型的一类集成电路布线算法[J]. 计算机工程与应用, 2015, 51(1): 21-25.
[15]	钱红昇1，葛文锋1，钟鸣2，葛铭1. 基于分层的改进[A*]算法在路径规划中的应用[J]. 计算机工程与应用, 2014, 50(7): 225-229.