Physical topology discovery algorithms based on inear dependency of traffics in IP network
Jin Yi1, Shen Zengwei2, Zhou Gang1*
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
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.