微信服务号

微信订阅号

2025-4-13- 5
Home > Archive>Volume 27, Issue 8, 2016 >2086-2098. DOI:10.13328/j.cnki.jos.004835
PDF HTML XML Export Cite reminder
Topology Discovery with Incomplete Address Forwarding Table
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61371196, 61462009); Jiangsu Post-Doctor Research Fund of China (1402138C)

  • Article
    • | |
  • Metrics
    • |
  • Reference [26]
    • |
  • Related [20]
    • |
  • Cited by
    • | |
  • Comments
    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.

    Reference
    [1] Siamwalla R, Sharma R, Keshav S. Discovering internet topology. In: Proc. of the IEEE Infocom. 1999. 1-16.
    [2] Sun YT, Wu ZM, Shi JQ. A method of topology discovery for switched ethernet based on address forwarding tables. Ruan Jian Xue Bao/Journal of Software, 2006,17(12):2565-2576 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/2565. htm
    [3] Gobjuka H, Breitbart Y. Ethernet topology discovery for networks with incomplete information. IEEE/ACM Trans. on Networking, 2010,18(4):14-153. [doi: 10.1109/TNET.2009.2039757]
    [4] Bierman A, Jones K. Physical Topology MIB. Internet RFC-2922, 2000.
    [5] Dawes N, Schenkel D, Slavitch M. Method of determining the topology of a network of objects. U.S. Patent 6,411,997 B1, 2002.
    [6] Schenkel D, Slavitch M, Dawes N. Method of determining topology of a network of objects which compares the similarity of the traffic sequences/volumes of a pair of devices. U.S. Patent 5,926,462, 1999.
    [7] Qiu L, Zhang JZ, Wu GY. Physical topology discovery method study based on ports traffic. Computer Engineering and Application, 2002,22(4):171-172 (in Chinese with English abstract).
    [8] Son MH, Joo BS, Kim BC, Lee JY. Physical topology discovery for metro ethernet networks. ETRI Journal, 2005,9(4):175-186. [doi: 10.4218/etrij.05.0104.0167]
    [9] Black R, Donnelly A, Fournet C. Ethernet topology discovery without network assistance. In: La Porta T, Ramjee R, Koenig H, Effelsberg W, eds. Proc. of the 12th IEEE Int'l Conf. on Network Protocols (ICNP 2004). Los Alamitos: IEEE Computer Society, 2004. 130-159. [doi: 10.1109/ICNP.2004.1348122]
    [10] Breitbart Y, Garofalakis M, Martin C, Rastogi R, Seshadri S, Silberschatz A. Topology discovery in heterogeneous IP networks. In: Sidi M, Sengupta B, eds. Proc. of the INFOCOM 2000. New York: IEEE Press, 2000. 85-94. [doi: 10.1109/INFCOM.2000.8321 96]
    [11] Breitbart Y, Garofalakis M, Jai B, Martin C, Rastogi R, Silberschatz A. Topology discovery in heterogeneous IP networks: The NetInventory system. IEEE/ACM Trans. on Networking, 2004,12(3):221-234. [doi: 10.1109/TNET.2004.828963]
    [12] Bejerano Y, Breitbart Y, Garofalakis M, Rastogi R. Physical topology discovery for large multi-subnet networks. In: Bauer F, Roberts J, Shroff N, eds. Proc. of the IEEE INFOCOM 2003. New York: IEEE Press, 2003. 162-172. [doi: 10.1109/INFCOM.2003. 1208686]
    [13] Zheng H, Zhang GQ. An algorithm for physical network topology discovery. Journal of Computer Research and Development, 2002,39(3):264-268 (in Chinese with English abstract).
    [14] Chen F, Yang JH, Yang Y. New algorithms on IP network topology discovery and its implement. Acta Electronica Sinica, 2008, 36(8):1620-1625 (in Chinese with English abstract).
    [15] Lowekamp B, O'Hallaron DR, Gross TR. Topology discovery for large ethernet networks. In: Govindan R, ed. Proc. of the ACM SIGCOMM 2001. New York: ACM Press, 2001. 57-68. [doi: 10.1145/964723.383078]
    [16] Bejerano Y. Taking the skeletons out of the closets: A simple and efficient topology discovery scheme for large multisubnet networks. In: Proc. of the IEEE INFOCOM. 2006. 1-13. [doi: 10.1109/INFOCOM.2006.237]
    [17] Bejerano Y. Taking the skeletons out of the closets: A simple and efficient topology discovery scheme for large ethernet lans. IEEE/ACM Trans. on Networking, 2009,17(2):1205-1218. [doi: 10.1109/TNET.2009.2022264]
    [18] Gobjuka H, Breitbart Y. Characterization of layer-2 unique topologies in multisubnet local networks. In: Proc. of the IEEE LCN. 2006. 540-542. [doi: 10.1109/LCN.2006.322160]
    [19] Gobjuka H, Breitbart Y. Ethernet topology discovery for networks with incomplete information. In: Proc. of the IEEE ICCCN. 2007. 613-620. [doi: 10.1109/ICCCN.2007.4317888]
    [20] Gobjuka H, Breitbart Y. Finding ethernet-type network topology is not easy. Technical Report, TR-KSU-CS-207-03, Kent State University, 2007.
    [21] Gobjuka H, Breitbart Y. Discovering network topology of large multisubnet ethernet networks. In: Proc. of the IEEE LCN. 2007. 230-237. [doi: 10.1109/LCN.2007.25]
    附中文参考文献:
    [2] 孙延涛,吴志美,石志强.基于地址转发表的交换式以太网拓扑发现方法.软件学报,2006,17(12):2565-2576. http://www.jos.org. cn/1000-9825/17/2565.htm
    [7] 邱林,张建忠,吴功宜.基于端口流量的物理网络拓扑发现方法研究.计算机工程与应用,2002,22(4):171-172.
    [13] 郑海,张国清.物理网络拓扑发现算法的研究.计算机研究与发展,2002,39(3):264-268.
    [14] 陈福,杨家海,杨扬.网络拓扑发现新算法及其实现.电子学报,2008,36(8):1620-1625.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

张宾,刁兴春,孙延涛,丁鲲,严浩.不完整地址转发表的拓扑发现方法.软件学报,2016,27(8):2086-2098

Copy
Share
Article Metrics
  • Abstract:3266
  • PDF: 4415
  • HTML: 1341
  • Cited by: 0
History
  • Received:October 08,2014
  • Revised:March 23,2015
  • Online: August 08,2016
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2034795Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063