Electrical computers and digital processing systems: multicomput – Computer network managing – Computer network monitoring
Reexamination Certificate
1996-11-15
2002-06-25
Maung, Zarni (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer network managing
Computer network monitoring
C709S227000, C709S228000
Reexamination Certificate
active
06411997
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method of determining the topology of a network of objects, such as the physical topology of a network of data communications devices.
BACKGROUND TO THE INVENTION
Operators of many data communications networks are typically ignorant of the exact topology of the networks. The operators need to know the exact topology in order to properly manage the networks, for example, for the accurate diagnosis and correction of faults.
Network managers that do know the very recent topology of their network do so by one of two methods: an administrative method and an approximate AI (artificial intelligence) method.
Administrative methods require an entirely up to date record of the installation, removal, change in location and connectivity of every network device. Every such change in topology must be logged. These updates are periodically applied to a data base which the network operators use to display or examine the network topology. However, in most such systems the actual topology information made available to the operators is usually that of the previous day or previous days, because of the time lag in entering the updates. This method has the advantage that a network device discovery program need not be run to find out what devices exist in the network. This method has a disadvantage that it is almost impossible to keep the data base from which the topology is derived both free of error and entirely current.
The approximate AI methods use routing/bridging information available in various types of devices, for example, data routers typically contain routing tables. This routing information carries a mixture of direct information about directly connected devices and indirect information. The AI methods attempt to combine the information from all the devices in the network. This method requires that a network device discovery program be run to find out what devices exist in the network, or that such a list of devices be provided to the program. These approximate AI methods require massive amounts of detailed and very accurate knowledge about the internal tables and operations of all data communications devices in the network. These requirements make the AI methods complex, difficult to support and expensive. In addition, devices that do not provide connectivity information, such as ethernet or token ring concentrators must still be configured into the network topology by the administrative method.
One major problem with the Al methods is that inaccurate or incomplete information can cause their logic to deduce incorrect conclusions. The probabilistic methods described here are far less vulnerable to such problems.
SUMMARY OF THE INVENTION
The present invention exploits the fact that traffic flowing from a first device to a second device can be measured both as the output from the first device and as the input to the second device. The volume of traffic is counted periodically as it leaves the first device and as it arrives at the second device. With the two devices being in communication, the two sequences of measurements of the traffic volumes will tend to be very similar. The sequences of measurements of traffic leaving or arriving at other devices have been found in general, to tend to be different because of the random (and fractal) nature of traffic. Therefore, the devices which have the most similar sequences have been found to be likely to be interconnected. Devices can be discovered to be connected in pairs, in broadcast networks or in other topologies. This method is therefore extremely general. Various measures of similarity can be used to determine the communication path coupling. However the chi squared statistical probability has been shown to be robust and stable. Similarity can be established when the traffic is measured in different units, at different periodic frequencies, at periodic frequencies that vary and even in different measures (e.g. bytes as opposed to packets).
In accordance with an embodiment of the invention, a method of determining the existence of a communication link between a pair of devices is comprised of measuring traffic output from one device of the pair of the devices, measuring the traffic received by another device of the pair of devices, and declaring the existence of the communication link in the event the traffic is approximately the same.
Preferably the traffic parameter measured is its volume, although the invention is not restricted thereto.
In accordance with another embodiment of the invention, a method of determining network topologies is comprised of monitoring traffic received by devices connected in the network and traffic emitted out of the devices, correlating traffic out of the devices with traffic into the devices, indicating a network communication path between a pair of the devices in the event that the correlation of traffic out of one of the pair of the devices and into another of the pair of the devices is in excess of a predetermined threshold.
An embodiment of the present invention has been successfully tested on a series of operational networks. It was also successfully tested on a large data communications network deliberately designed and constructed to cause all other known methods to fail to correctly discover its topology.
REFERENCES:
patent: 5182750 (1993-01-01), Bales et al.
patent: 5430729 (1995-07-01), Rahnema
patent: 5450408 (1995-09-01), Phaal
patent: 5608659 (1997-03-01), Lin et al.
patent: 455402 (1991-06-01), None
patent: 0 265 106 (1993-11-01), None
patent: WO 94/19889 (1994-09-01), None
patent: WO 95/01030 (1995-01-01), None
patent: WO95/06989 (1995-03-01), None
patent: WO 96/13108 (1996-02-01), None
IEEE Network, vol. 3, New York, XP002027616: Soha, M., “A Distributed Approach to LAN monitoring Using Intellingent High Performance Monitors”, Jul. 1987.
IEEE Transactions on Communcations, vol. 42, New York, 1994. Yasuda, Y. et al., Automated Network Connection Tracing and Data Gathering Methods in the SDH Network.
IBM Technical Disclosure Bulletin, vol. 331, Armonk, 1988. (No author cited. Robust Method for Training Sequential Decision-Making for Artificial Intelligence System.
Dawes Nicholas
Schenkel David
Slavitch Michael
Baker Harold C.
Hendry Robert G.
Loran Network Systems LLC
Maung Zarni
Wilkes Robert A.
LandOfFree
Method of determining the topology of a network of objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of determining the topology of a network of objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of determining the topology of a network of objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2982413