不完整地址转发表的拓扑发现方法∗

摘要

Physical network topology discovery is a key issue for network management and planning, performance forecasting, network simulation and security; and how to discover a physical network topology based on address forwarding table (AFT) is a hot topic in current studies. This paper defines minimal constrains on AFT Tables for a switched area of a single subnet or multiple subnets to deducing its physical topology, and proves the completeness of the basic reasoning rule (BRR) proposed in the previous work. Furthermore, the paper analyzes the NP hard problem of AFT based methods, thoroughly discusses all kinds of possible situations deduced by BRR for any local network, and further investigates the limits solely based on AFT topology discovery. This work provides very important theoretical guidance in physical topology discovery based on AFT, and at the same time lays a solid theoretical foundation for new topology discovery methods.%网络物理拓扑发现对网络管理与规划、性能预测、网络模拟与安全等都有很重要的意义和作用，基于地址转发表的物理拓扑发现是目前学术界研究的热点问题。定义了单子网和多子网交换域的最小约束，并证明了所提出的AFT基本推导规则BRR的完备性。此外，还对基于不完整AFT进行拓扑发现的NP难问题进行了讨论，深入剖析了任意实际的局域网络的不完整AFT通过BRR推导完成后的各种可能情况，并分析了单纯依靠AFT进行拓扑发现的局限性。该工作对于基于 AFT 进行物理拓扑发现具有重要的理论指导意义，同时，也为进一步发掘新的物理拓扑发现方法奠定了坚实的理论基础。