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

Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (2): 131-134.

Previous Articles Next Articles

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

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

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

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

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

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

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

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

[1]	LI Jun. Improved Social Force Crowd Evacuation Simulation Model Combined with Shortest Path [J]. Computer Engineering and Applications, 2021, 57(8): 264-270.
[2]	YE Yingshi, WEI Fuyi, CAI Xianzi. Research on Fast Dijkstra Algorithm Based on Parallel Computing [J]. Computer Engineering and Applications, 2020, 56(6): 58-65.
[3]	LI Yan, WANG Yangyang, ZHANG Hongyan, WU Youxi. Fast Pruning Algorithm for Unreachable Vertices and Its Application in Solving Shortest Path Problem [J]. Computer Engineering and Applications, 2020, 56(15): 51-57.
[4]	MA Xuan, LIU Dong, HU Jiaxin. Particle Swarm Optimization for Solving Problem of k-Shortest Paths via Designated Points [J]. Computer Engineering and Applications, 2019, 55(20): 89-94.
[5]	ZHANG Xin, YAN Pei, GUO Yang, WANG Huihui. K-Shell Shortest Path Approximation Algorithm for Complex Networks [J]. Computer Engineering and Applications, 2019, 55(14): 54-60.
[6]	ZHANG Linxia, HE Liwen, HUANG Jun. Route of security device research based on SDN Network [J]. Computer Engineering and Applications, 2018, 54(4): 103-109.
[7]	GAO Zunhai, GAO Ying, CHENG Guo. Weighted path matrix of graph and all pairs shortest path problem [J]. Computer Engineering and Applications, 2017, 53(9): 47-50.
[8]	YING Wenjie, XU Kai, XU Shaoping. Multi-objective trajectory planning of manipulator for badminton robot [J]. Computer Engineering and Applications, 2017, 53(3): 258-265.
[9]	DONG Yuehua, ZHOU Yongxin. Selective sorting algorithm over a set of necessary nodes [J]. Computer Engineering and Applications, 2017, 53(20): 43-49.
[10]	YAO Bo1, FENG Hongwei1, GAO Yuan2, MA Jiali1, FENG Jun1. Dynamic pruning search algorithm that must go through certain node set [J]. Computer Engineering and Applications, 2017, 53(15): 57-62.
[11]	YANG Nan1, CHEN Yuanbo2, WANG Yanjie2, LI Qing2. Multipath transmission protocol based on degree-constrained shortest path tree [J]. Computer Engineering and Applications, 2017, 53(11): 126-130.
[12]	YUAN Yabo, LIU Yi, WU Bin. Solving shortest path problem with modified ant colony algorithm [J]. Computer Engineering and Applications, 2016, 52(6): 8-12.
[13]	HOU Xiaoqin1, HU Zhihua1, GAO Chaofeng1, LUO Xunjie2. Priority-based genetic algorithm for routing automated guided vehicles for traversing blocks in warehouse aisles [J]. Computer Engineering and Applications, 2016, 52(12): 31-36.
[14]	WU Xingliang, TU Fenghua. Personalized tag recommendation method using graph-model [J]. Computer Engineering and Applications, 2015, 51(9): 142-146.
[15]	HUANG Shuli, HU Dasha, JIANG Yuming. Algorithm for finding shortest path which must go through specified intermediate node set [J]. Computer Engineering and Applications, 2015, 51(11): 41-46.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics