收稿日期: 2015-01-04
修回日期: 2016-06-02
网络出版日期: 2016-11-30
基金资助
国家自然科学基金（No.61462009）；中国博士后基金（No.2015M582832）；江苏省博士后科研基金（No.1402138C）；河南省高等学校重点项目基金（No.13B520337）；广西自然科学基金（No.2014GXNSFAA118358）资助
Fast Topology Discovery for Campus Network
Received date: 2015-01-04
Revised date: 2016-06-02
Online published: 2016-11-30
李晓歌, 王辉, 张宾, 秦董洪 . 快速园区网拓扑发现方法[J]. 应用科学学报, 2016 , 34(6) : 768 -777 . DOI: 10.3969/j.issn.0255-8297.2016.06.012
To obtain the topology of a network,scan of the entire network is necessary, which is time consuming in practice. The time needed in finding topology is long especially for small-scale campus network where a large number of IP addresses do not respond to the “ping” message. To solve the problem,this paper proposes a fast topology discovery method without scanning the network,but only based on the address forwarding table. Using a hierarchical traversal strategy,the proposed algorithm discovers the topology by searching devices starting from the outer rim to the center. Simulation results show that the proposed method can deduce the connection of a network including up to 80 nodes in one minute. Performance and effectiveness of the method are verified in practical applications.
[1] Siamwalla R,Sharma R,Keshav S. Discovering Internet topology [R]. Ithaca,NY: Cornell University,May 1999.
[2] Bierman A,Jones K. Physical topology MIB [M]. Internet RFC-114,2000.
[3] Dawes N,Schenkel D,Slavitch M. Method of determining the topology of a network of objects [P]. U.S. 6 231 997,2002-06-07.
[4] 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 [P]. U.S. 5 98 462,1999-07-02.
[5] 邱林,张建忠,吴功宜. 基于端口流量的物理网络拓扑发现方法研究[J]. 计算机工程与应用,2002,4: 171-172.Qiu L,Zhang J Z,Wu G Y. Research of physical network topology discovery at layer 2 based o octets [J]. Computer Engineering and Applications, 2002, 38(22): 171-172. (in Chinese)
[6] Son M H,Joo B S,Kim B C,Lee J Y. Physical topology discovery for metro Ethernet networks [J]. ETRI Journal,2005,9(4): 175-186.
[7] Black R,Donnelly A,Fournet C. Ethernet topology discovery without network assistance[C]// La Porta T,Ramjee R,Koenig H,Effelsberg W,eds. Proceedings of the 12th IEEE Int'l Conf. on Network Protocols (ICNP 204). Los Alamitos: IEEE Computer Society,2004: 130-159.
[8] Breitbart Y,Garofalakis M,Martin C,Rastogi R,Seshadri S,Silberschatz A. Topology discovery in heterogeneous IP networks [C]///Sidi M,Sengupta B,eds. IEEE International Conference on Computer Communications (IEEE INFOCOM). New York: IEEE Press,2000: 85-94.
[9] Breitbart Y,Garofalakis M,Jai B,Martin C,Rastogi R,Silberschatz A. Topology discovery in heterogeneous IP networks: the net inventory system [J]. IEEE/ACM Transactions on Networking,2014,12(3): 221-234.
[10] Bejerano Y,Breitbart Y,Garofalakis M,Rastogi R. Physical topology discovery for large multi-subnet networks [C]//Bauer F,Roberts J,Shroff N,eds. IEEE International Conference on Computer Communications (IEEE INFOCOM2003). New York: IEEE Press,2003: 162-172.
[11] 郑海,张国清. 物理网络拓扑发现算法的研究[J]. 计算机研究与发展,2002,39(3): 264-268. Zheng H,Zhang G Q. An algorithm for physical network topology discovery [J]. Journal of Computer Research and Development,2002,39(3): 264-268 (in Chinese).
[12] 陈福,杨家海,杨扬. 网络拓扑发现新算法及其实现[J]. 电子学报,2008,36(8): 1620-1625. Che F,Yang J H,Yang Y. New algorithms on IP network topology discovery and its implement[J]. Acta Electronica Sinica,2008,36(8): 1620-1625. (in Chinese)
[13] Lowekamp B,O'hallaron D R,Gross T R. Topology discovery for large Ethernet networks [C]//Govindan R,ed. Proceedings of the ACM SIGCOMM 2001. New York: ACM Press,2001: 57-68.
[14] 孙延涛,吴志美,石志强. 基于地址转发表的交换式以太网拓扑发现方法[J]. 软件学报, 2006,17(12): 2565-2576. Sun Y T,Wu Z M,Si Z Q. A method of topology discovery for switched Ethernet based on address forwarding tables [J]. Journal of Software,2006,17(12): 2565-2576. (in Chinese)
[15] Bejerano Y. Taking the skeletons out of the closets: a simple and efficient topology discovery scheme for large multisubnet networks [C]//IEEE International Conference on Computer Communications (IEEE INFOCOM),2006: 1-13.
[16] Bejerano Y. Taking the skeletons out of the closets: a simple and efficient topology discovery scheme for large Ethernet Lans [J]. IEEE/ACM Transactions on Networking,2009,17(2): 1205-1218.
[17] Gobjuka H,Breitbart Y. Ethernet topology discovery for networks with incomplete information[J]. IEEE/ACM Transactions on Networking,2010,18(4): 140-153.
[18] 荆栋,肖刚. 网络拓扑发现算法[J]. 重庆理工大学学报:自然科学版,2012,9: 90-95. Jing D,Xiao G. Network topology discovery algorithm [J]. Journal of Chongqing University of Technology: Natural Science Edition,2012,9: 90-95. (in Chinese)
[19] 孙克辉,陈艳山,程巍,张志强. 网络层与链路层综合拓扑发现算法及其实现[J]. 计算机工程与应用,2012,4: 107-110. Sun K H,Chen Y S,Cheng W,Zhang Z Q. Network layer and link layer topology discovery algorithm and its implementation [J]. Computer Engineering and Applications,2012,4: 107-110. (in Chinese)
[20] Suman P,Mi-Jung C,Young J W,James W H. SNMP-based enterprise IP network topology discovery [J]. International Journal of Network Management,2011,21(3): 169-184.
[21] Eriksson B,Dasarathy G,Barford P,Nowak R. Efficient network tomography for internet topology discovery [J]. IEEE/ACM Transactions on Networking,2011,20(3): 931-943.
[22] Jian X G,Wen Y X. Network layer network topology discovery algorithm research [J]. Applied Mechanics and Materials,2013,380: 1327-1332.
/
| 〈 |
|
〉 |
