Multiplex communications – Network configuration determination – Using a particular learning algorithm or technique
Reexamination Certificate
1999-07-08
2003-07-01
Rao, Seema S. (Department: 2666)
Multiplex communications
Network configuration determination
Using a particular learning algorithm or technique
Reexamination Certificate
active
06587440
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to the field of data communication systems, and in particular to a method for determining the physical topology of a network of data communication devices.
BACKGROUND TO THE INVENTION
Operators of many data communications networks are ignorant of its topology. However, the operators need to know the topology in order to properly manage the network. Accurate diagnosis and correction of many faults requires such knowledge. This is described in the article “Network Diagnosis By Reasoning in Uncertain Nested Evidence Spaces”, by N. W. Dawes, J. Altoft and B. Pagurek, IEEE Transactions on Communications, February 1995, Vol 43,2-4: pp 466-476.
Network management teams that do know the very recent topology of their network do so by one of three methods: an administrative method, an approximate AI method as described in U.S. Pat. No. 5,727,157 issued Mar. 10, 1998, invented by Orr et at, and PCT publication WO 95/06,989, but assigned to Cabletron, and the Loran traffic method as described in U.S. Pat. No. 5,926,462 issued Jul. 20, 1999 and entitled “Method of Determining Topology of A Network of Objects Which compares the Similarity of the Traffic Sequences/Volumes of a Pair of Devices”. The data protocols the latter two use are described in the text “SNMP, SNMPv2 and CMIP. The Practical Guide to Network Management Standards”. W. Stallings, Addison-Wesley, 1993 and updates.
The 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 the data base which the operators use to display or examine the network topology. However, in almost all such systems the actual topology 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, but has the 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 Cabletron method theoretically provides only one of the necessary elements for a method of determining network topologies: the deduction of a possible direct or transitive connection. However there are at least six problems with the Cabletron method even with this very limited goal.
1: problems with invalid source addresses and addresses of moved objects. This makes this method unusable under many conditions as it gives contradictory and incorrect results.
2: the requirement that network management reporting by devices be done by the device itself, not by a proxy agent which will reply using a different source address. Although not common, this makes any network with such a device unmappable by this method.
3: requirement that the source addresses of reporting devices appear commonly in network traffic, so that each reporting device has a reasonable chance of picking up the addresses of all the reporting devices it can. This is a major problem. In direct contrast, the only use the method of the present invention makes of the addresses of reporting data-relay devices directly available in tables is to define more up ports when it already knows some (see below).
4: a total inability to deal with the existence of unmanaged devices lying between managed devices.
5: computational complexity in very large networks means the Cabletron method takes so long to run that the network may well have changed before the calculations are complete.
6: the inability to deal with multiple connections between devices, for example between a switch and a segmented repeater.
The approximate AI methods use routing/bridging information available in various types of devices (eg: data routers 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 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 and very accurate knowledge about the internal tables and operations of all data communications devices in the network. These requirements make these 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. Finally the search of the AI methods has to be guided by expert humans for it to be successful, and even then there are many classes of topology it cannot determine. Consequently the approximate AI methods are not in general use.
The Loran traffic method exploits the fact that traffic flowing from one device to another device can be measured both as the output from the first and as the input to the second. Should the volume of traffic be counted periodically as it leaves the first and as it arrives at the second, the two sequences of measurements of the volumes will tend to be very similar. The sequences of measurements of traffic leaving or arriving at other devices will, in general, tend to be different because of the random (and fractal) nature of traffic. Therefore, the devices which have the most similar sequences will be most 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. However it depends on reasonably accurate measurements of traffic being made in both devices. In practice some devices do not report any information at all, let alone traffic. Other devices report incorrect values of traffic.
A method described in U.S. Pat. No. 5,450,408 issued Sep. 12, 1995, invented by Phall et al and assigned to Hewlett Packard Company relies on monitoring the source and destination of packets on lines in the network. From the sets of to and fro addresses the topology is eventually deduced. This requires hardware packet detectors to be added to many of the lines in the network and has nothing in common with the present invention.
SUMMARY OF THE INVENTION
An embodiment of the invention uses any source address to port mapping information in a device. Examples are bridge table, arp table, link training and source address capture data to determine classes of network topologies never previously determinable. In particular, the classes of topologies where one or more non reporting devices exist between sets of reporting devices are correctly determined. It includes a novel concept of up and down ports. Up ports interconnect devices which report tables, down ports do not. This concept dramatically reduces the computational complexity and greatly increases the accuracy of connection determination. The methods for distinguishing up and down are novel.
An embodiment of the invention also includes the novel determination that if an up port sees a source address also seen in a down port table then the up port sees the source address of the data-relay device with the down port. This removes entirely the dependence on data-relay devices seeing the source addresses of other data-relay devices directly, which undesirable dependence is essential to the Cabletron methods.
An embodiment of the invention involves removal of invalid and moved source addresses from the table data and is novel and so are all the methods for doing so. This makes the method approximately 100 fold less prone to error. It is more and more necessary as the use of portable computers becomes more widespread.
An embodiment of the invention provides for the explicit tradeoff of the accuracy of connections against the rapidity with which changes in the network are tracked is novel.
An embodiment of
Abelson Ronald
Baker Harold C.
Cohen Shapiro
Haszko Dennis R.
Loran Networks Management Ltd.
LandOfFree
Method for determining computer network topologies 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 for determining computer network topologies, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining computer network topologies will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3051117