基于流量线性相关的IP网物理拓扑发现算法

金毅; 沈曾伟; 周刚

基于流量线性相关的IP网物理拓扑发现算法

1.
北京航空航天大学软件开发环境国家重点实验室, 北京 100083
2. 赛门铁克中国研发中心, 北京 100084

基金项目: 国家973计划资助项目(2005CB321901)

详细信息

中图分类号: TP 393
计量
- 文章访问数: 3214
- HTML全文浏览量: 33
- PDF下载量: 1380
- 被引次数: 0
出版历程
- 收稿日期: 2006-10-26
- 网络出版日期: 2007-11-30

Physical topology discovery algorithms based on inear dependency of traffics in IP network

1.
State Key Laboratory of Software Development Environment, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
2. China Development Centre, Symantec Corporation, Beijing 100084, China

摘要

摘要: IP网络物理拓扑发现通常依据设备的地址转发表(AFT, Address Forward Table)实现,相关数据通过简单网管协议(SNMP, Simple Network Management Protocal)获取.但在实际网络中,由于各种因素这种方法发现的结果往往不精确甚至有错误.提出基于网络流量特征的拓扑发现算法.首先将网络设备接口流量随时间的变化看作随机过程,给出接口速率的相关函数定义;然后证明了物理直连的设备接口间的网络流量具有最高的线性相关性;进而提出了基于接口流量线性相关性的IP网络物理拓扑直连关系的发现算法,实现对物理拓扑的最似然估计.最后,在实际网络中对该算法进行了验证.
- 拓扑发现 /
- 网络流量 /
- 随机过程 /
- 线性相关
Abstract: In IP network, general physical topology discovery algorithms are based on the network devices- AFT (address forward tables) which are obtained through SNMP (simple network management protocol). Unfortunately, the results of such algorithms are usually not exact or correct in practical networks for many factors. To solve this problem, a new physical topology discovery algorithm based on the traffics- characteristic was proposed. First, interface-s input rate and output rate were considered as random variables, and the linear correlation function of two rates was difined. Secondly it was proved that the correlation function of the rates of two interfaces which connect each other directly had the max value. Then the topology discovery algorithm was proposed based on the previous conclusion. The algorithm could achieve a most likelihood result based on the rates- linear correlation. At last, the algorithm was tested in a practical network.
- topology discovery /
- network traffic /
- random processes /
- linear dependency

HTML全文

参考文献(1)

[1] Bejerano Y, Breitbart Y, Garofalakis M, et al. Physical topology discovery for large multi-subnet networks Proc IEEE INFOCOM. San Francisco: IEEE Press, 2003: 342-352 [2] Breitbart Y, Garofalakis M, Martin C C, et al. Topology discovery in heterogeneous IP networks Sidi M, Sengupta B. Proc of the INFOCOM 2000. New York: IEEE Press, 2000: 265-274 [3] Lowekamp B, O- Hallaron D R, Gross T. Topology discovery for large Ethernet networks Govindan R. Proc of ACM SIGCOMM 2001. New York: ACM Press, 2001:237-248 [4] 郑海,张国清.物理网络拓扑发现算法的研究[J]. 计算机研究与发展,2002,39(3):264-268 Zheng Hai, Zhang Guoqing. An algorithm for physical network topology discovery[J]. Journal of Computer Research and Development, 2002, 39(3):264-268 (in Chinese) [5] 刘玉华,余胜生,周敬利,等.基于AFT的链路层自动拓扑发现算法[J]. 小型微型计算机系统,2004,25(12):2211-2214 Liu Yuhua, Yu Shengsheng, Zhou Jingli, et al. Link layer automatic topology discovery algorithm based on AFT [J]. Journal of Mini-Micro System, 2004, 25(12): 2211-2214 (in Chinese)  [6] Case J. A simple network management protocol (SNMP), RFC1157 . 1990 .http://www.rfc-editor.org/rfc/rfc1157.txt [7] Decker E, Langille P, Rijsinghani A, et al. Definitions of managed objects for Bridges . 1993 . http://www.rfc-editor.org/rfc/rfc1493.txt [8] McCloghrie K Rose M. Management information base for Network management of TCP/IP-based internets . 1988 . http://www.rfc-editor.org/rfc/rfc1066.txt [9] 邱林,张建忠,吴功宜. 基于端口流量的物理网络拓扑发现方法研究[J]. 计算机工程与应用,2002,22:171-172 Qiu Lin, Zhang Jianzhong, Wu Gongyi. Research of physical network topology discovery at layer 2 based on octets [J]. Journal of Computer Engineering and Applications, 2002, 22:171-172(in Chinese) [10] 张福渊,郭绍建,萧亮壮,等. 概率统计及随机过程[M] .北京:北京航空航天大学出版社,2000:148-149 Zhang Fuyuan, Guo Shaojian, Xiao Liangzhuang, et al. Probability, statistics and stochastic processes [M]. Beijing: Beijing University of Aeronautics and Astronautics Press, 2000: 148-149 (in Chinese)

施引文献

资源附件(0)

访问统计