Journal of Software:2016.27(8):2086-2098

(总参第63研究所, 江苏 南京 210007;北京交通大学 计算机与信息技术学院, 北京 100080)
Topology Discovery with Incomplete Address Forwarding Table
ZHANG Bin,DIAO Xing-Chun,SUN Yan-Tao,DING Kun,YAN Hao
(The 63rd Research Institute, Nanjing 210007, China;School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100080, China)
Chart / table
Similar Articles
Article :Browse 1534   Download 1149
Received:October 08, 2014    Revised:March 23, 2015
> 中文摘要: 网络物理拓扑发现对网络管理与规划、性能预测、网络模拟与安全等都有很重要的意义和作用,基于地址转发表的物理拓扑发现是目前学术界研究的热点问题.定义了单子网和多子网交换域的最小约束,并证明了所提出的AFT基本推导规则BRR的完备性.此外,还对基于不完整AFT进行拓扑发现的NP难问题进行了讨论,深入剖析了任意实际的局域网络的不完整AFT通过BRR推导完成后的各种可能情况,并分析了单纯依靠AFT进行拓扑发现的局限性.该工作对于基于AFT进行物理拓扑发现具有重要的理论指导意义,同时,也为进一步发掘新的物理拓扑发现方法奠定了坚实的理论基础.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61371196,61462009);江苏省博士后科研资助项目(1402138C) 国家自然科学基金(61371196,61462009);江苏省博士后科研资助项目(1402138C)
Foundation items:National Natural Science Foundation of China (61371196, 61462009); Jiangsu Post-Doctor Research Fund of China (1402138C)
Reference text:


ZHANG Bin,DIAO Xing-Chun,SUN Yan-Tao,DING Kun,YAN Hao.Topology Discovery with Incomplete Address Forwarding Table.Journal of Software,2016,27(8):2086-2098