一种基于子树交汇点的多子网拓扑发现算法

摘要

准确、及时的网络拓扑信息对网络管理、协议设计和网络安全等领域工作具有重要意义。针对包含哑设备的大型、异构多子网拓扑发现问题，提出一种基于子树交汇点的物理拓扑发现算法。算法通过围绕子树交汇点，利用改进的连接信息扩展规则进行连接判定与信息推理补完，自顶向下的进行拓扑发现。理论分析与实验结果表明，该算法能够利用不完整的地址转发表构建出整个网络拓扑结构，在发现效率和准确性等方面都有了较大提高。%Accurate and up-to-date network topology information plays a crucial role in network management, protocol design and network security, etc.To discover the problems targeting at the large and heterogeneous multiple subnets that may include dumb network elements, we propose a new multi-subtree intersection-based physical topological discovery algorithm.Around the intersection of multi-subtree, the algorithm uses the improved connection information extension rules to carry out the connection discriminant and the reasoning and finishing up of information, as well as the top-down topology discovery.It is demonstrated by theoretical analysis and experimental results that this algorithm can construct an entire network topology with the incomplete AFTs, and improves a great deal in both discovery efficiency and accuracy.