Abstract Network physical topology discovery is the key issue for network management and application, the physical topology discovery based on Address Forwarding Table (AFT) is a hot topic on current study. This paper defines three constraints of AFTs, and proposes a tree chopping algorithm based on AFTs satisfying down constraint, which can discover the physical topology of a subnet accurately. The proposed algorithm decreases the demand for AFT integrity dramatically, and is the loosest constraint for discovering physical topology which just relies on AFTs of down ports. The proposed algorithm can also be used in the switch domain of multiple subnets.

References

[1] Bierman A. and Jones K., Physical Topology MIB, Internet RFC-2922, 2000.

[2] Black R., Donnelly A., and Fournet C., Ethernet Topology Discovery Without Network Assistance, in Proceedings of the 12th IEEE International Conference on Network Protocols, Berlin, pp. 328- 339, 2004.

[3] Breitbart Y., Garofalakis M., Martin C., Rastogi R., Seshadri S., and Silberschatz A., Topology Discovery in Heterogeneous IP Networks, in Proceedings of Computer Communications 19th Annual Joint Conference of the IEEE Computer and Communications Societies, Tel Aviv, pp. 265-274, 2002.

[4] Breitbart Y., Garofalakis M., Jai B., Martin C., Rastogi R., and Silberschatz A., Topology Discovery in Heterogeneous IP Networks: The NetInventory System, IEEE/ACM Transactions on Networking, vol. 12, no. 3, pp. 401-414, 2004.

[5] Bejerano Y., Breitbart Y., Garofalakis M., and Rastogi R., Physical Topology Discovery for Large Multi-Subnet Networks, in Proceedings of 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, SanFrancisco, pp. 342-352, 2003.

[6] Bejerano Y., Taking the Skeletons Out of the Closets: A Simple and Efficient Topology Discovery Scheme for Large Ethernet Lans, in Proceedings of 25th IEEE International Conference on Computer Communications, Barcelona, pp. 1-13, 2006.

[7] Bejerano Y., Taking the Skeletons out of the Closets: A simple and Efficient Topology Discovery Scheme for Large Ethernet Lans, IEEE/ACM Transactions on Networking, vol. 17, no. 5, pp. 1385-1389, 2009.

[8] Breitbart Y. and Gobjuka H., Characterization of Layer-2 Unique Topologies, Information Processing Letters, vol. 105, no. 2, pp. 52-57, 2008.

[9] Dawes N., Schenkel D., and Slavitch M., Method of Determining the Topology of a Network of Objects, U.S. Patent 6,231,997, 2002.

[10] Fu C., Jiahai Y., and Yang Y., New Algorithms on IP Network Topology Discovery and Its Implement, Acta Electronica Sinica, vol. 36, no. 8, pp. 1620-1625, 2008.

[11] Gobjuka H. and Breitbart Y., Characterization of Layer-2 Unique Topologies in Multisubnet Local Networks, in Proceedings of Conference on Local Computer Networks, Tampa, pp. 540- 542, 2006.

[12] Gobjuka H. and Breitbart Y., Ethernet Topology Discovery for Networks with Incomplete Information, in Proceedings of 16th International Conference on Computer Communications and Networks, Honolulu, pp. 631-638, 2007.

[13] Gobjuka H. and Breitbart Y., Finding Ethernet- Type Network Topology is not Easy, Technical Report, 2007.

[14] Gobjuka H. and Breitbart Y., Discovering Network Topology of Large Multisubnet Ethernet Networks, in Proceedings of 32nd IEEE Conference on Local Computer Networks, Dublin, pp. 428-435, 2007.

[15] Gobjuka H. and Breitbart Y., Ethernet Topology Discovery for Networks with Incomplete Information, IEEE/ACM Transactions on Networking, vol. 18, no. 4, pp. 1220-1233, 2010.

[16] Kef M., Chergui L., and Benmohammed M., Self-organization and Topology's Control for Mobile Ad-hoc Networks, The International Arab Journal of Information Technology, vol. 8, A Physical Topology Discovery Method Based on AFTs of Down Constraint 1059 no. 3, pp. 227-234, 2011.

[17] Lin Q., Jianzhong Z., and Gongyi W., Reaearch of Physical Network Topology Discovery at Layer 2 Based on Octets, Computer Engineering and Application, vol. 22, pp. 171- 172, 2002.

[18] Lowekamp B., O Hallaron D., and Gross T., Topology Discovery for Large Ethernet Networks, in Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, San Diego, pp. 428-435, 2011.

[19] Siamwalla R., Sharma R., and Keshav S., Discovering Internet Topology, Techical Report, 1999.

[20] Schenkel D., Slavitch M., and 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,98,462, 1999.

[21] Son M., Joo B., Kim B., and Lee J., Physical Topology Discovery for Metro Ethernet Networks, Electronics and Telecommunications Research Institute Journal, vol. 27, no. 4, pp. 355-366, 2005.

[22] Yantao S., Zimei W., and Ziqiang S., A Method of Topology Discovery for Switched Ethernet Based on Address Forwarding Tables, Journal of Software, vol. 17, no. 12, pp. 2565-2576, 2006.

[23] Zheng H. and Zhang G., An algorithm for physical Network Topology Discovery, Journal of Computer Research and Development, vol. 39, no. 3, pp. 264-268, 2002. Bin Zhang received his Ph.D. degree in Department of Computer Science and Technology, Tsinghua University, China in 2012. He received the Bachelor degree in computer software from Zhengzhou University, China in 1998 and the Master's degree in network information security from Shanghai Jiaotong University, China, in 2005. During his Ph.D. career, he publish more than 20 papers in refereed international conferences (NOMS, IM, LCN, IWQoS, APNOMS, etc) and journals (the Computer Journal, JCST, Journal of Software). He is a post doctor in Nanjing Telecommunication Technology Institute Nanjing, China. His current research interests focus on Internet architecture and its protocols, IP routing technology, network measurement, network management, etc., Xingchun Diao is the headmaster and also a professor in Nanjing Telecommunication Technology Institute Nanjing, China. He has published more than 100 articles in refereed international conferences and journals, and two books on data quality and management. Xinchun's research interests include big data processing, data quality, network measurement, network management, etc., He also serves as a TPC member for several international conferences. Donghong Qin received his Ph.D. degree in Department of Computer Science and Technology, Tsinghua University, China in 2013. He publish more than 20 papers in refereed international conferences and journals. He is a professor in School of Information Science and Engineering, GuangXi University for Nationalities, Nanning, China. His current research interests focus on Internet architecture and its protocols, IP routing technology, network management, etc., Yi Liu received his Ph.D. degree in Institute of Command and Control Engineering, Army Engineering University of PLA, China in 2018. He received the Bachelor degree in network engineering from Xi an University of Posts & Telecommunications, China in 2011 and the Master's degree in computer applications from PLA University of Science and Technology, China, in 2014. He has published about 15 papers in refereed international conferences (ICIQ, ICRIS, BIC-TA, CCF Bigdata etc.) and journals (MPE, Systems Engineering and Electronics, Journal of Software etc.). He is now a assistant professor in National Innovation Institute of Defense Technology, Beijing, China. His current research interests include Evolutionary algorithms, Data quality, Robot operating system, computer network, etc. Yun Yu received the Bachelor degree in College of Telecommunications & Information Engineering from Nanjing University of Posts and Telecommunications, China in 2003 and the Master's degree in Software Engineering from University Of Electronic Science And Technology Of China, in 2010. He publish more than 10 papers in refereed international conferences (ICEMC, etc) and journals (High Performance Computing Technology, Journal of Modern Militart Communications, etc). He is now an engineer in The Sixty-third Research Institute,National University of Defense Technology, Nanjing, China. His current research interests focus on networking protocol, IP routing technology, network measurement, etc.