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

IP网络物理拓扑发现通常依据设备的地址转发表(AFT, Address Forward Table)实现,相关数据通过简单网管协议(SNMP, Simple Network Management Protocal)获取.但在实际网络中,由于各种因素这种方法发现的结果往往不精确甚至有错误.提出基于网络流量特征的拓扑发现算法.首先将网络设备接口流量随时间的变化看作随机过程,给出接口速率的相关函数定义;然后证明了物理直连的设备接口间的网络流量具有最高的线性相关性;进而提出了基于接口流量线性相关性的IP网络物理拓扑直连关系的发现算法,实现对物理拓扑的最似然估计.最后,在实际网络中对该算法进行了验证.

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

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.