CA2256203A1 - A method for determining computer network topologies - Google Patents

Abstract

The topology of a computer network including data-relay devices and node devices is determined, based on comparing the source addresses heard by the various data-relay devices. A source address table is compiled for each port of each data-relay device. Such ports are then classified as up or down. Up ports connect directly or indirectly to other data-relay devices which report source address tables while down ports do not. Up ports can be recognised since their source address tables intersect the tables on two or more ports on a single other data-relay device. Moreover, source addresses in the tables of down ports are not duplicated in the table of any other 'down' port but are duplicated in the tables of up ports that directly or indirectly connect to the data-relay device that contains that down port. After classification as down or up, each source address in each up port table is replaced by the source address of the data-relay devices containing the down port whose table contains that source address. The up port tables now contain only data-relay addresses and the addresses of non table reporting devices indirectly connected to up ports. The tables of pairs of 'up' ports are compared by intersection and the minimal intersection defines the most probable connection for each up port. The source addresses of devices in the table of a down ports are directly or indirectly connected to that 'down' port. The method can be applied repeatedly and the probabilities aggregated to provide arbitrary accuracy. A variety of methods are used to remove invalid source addresses and the addresses of devices that have moved during the collection of the source address tables.

Description

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 communications devices.
BACKGROUND TO THE INVENTION
Operators of many data communications networks are ignorant of their topologies. However, the operators need to know the topologies in order to properly manage the networks. Accurate diagnosis and correction of many faults requires such knowledge.
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 (for example, as described in U.S. patent 5,727,157 and PCT publication WO 95/06989, both invented by Orr et al and assigned to Cabletron, and the Loran traffic method, as described in United States Patent Application Serial No. 08/558,729 filed November 16, 1995 and entitled METHOD OF DETERMININING TOPOLOGY OF A
NETWORK OF OBJECTS WHICH COMPARES THE SIMILARITY OF THE
TRAFFIC SEQUENCES/VOLUMES OF A PAIR OF DEVICES. Data protocols used are described in a text by Stallings, "SNMP, SNMPv2 and CMIP, The Practical Guide to Network Management Standards", Addison-Wesley, 1993, and updates.
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.
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. They method require 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 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 by the AI methods has to be guided by expert humans for them to be successful, and even then there are many classes of topology they 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 device. Should the volume of traffic be counted periodically as it leaves the first device and as it arrives at the second device, the two sequences of measurements of the volumes will tend to be very similar.

2 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 one both devices. In practise some devices do not report any information at all , let alone traffic. Other devices report incorrect values of traffic.
The Cabletron method referred to above 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 their method even with this very limited goal:
(a) problems with invalid source addresses and addresses of moved objects. This makes that method unusable under many conditions since it gives contradictory and wrong results.
(b) 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 that method.
(c) the 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 significantly undesireable requirement.
In contrast, in the present invention the only use made

3 of the addresses of reporting data-relay devices being directly available in tables is to define more up ports when it already knows some.
(d) total inability to deal with the existence of unmanaged devices lying between managed devices.
(e) computational complexity in very large networks requires the Cabletron method to take so long to run that the network may well have changed before the calculations are complete.
(f) inability to deal with multiple connections between devices, for example between a switch and a segmented repeater.
A method described in U.S. patent 5,450,408 dated Sep 12, 1995 to Phall et al and assigned to the 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 method of the present invention SUMNLA_RY OF THE INVENTTnN
The Loran traffic method referred to above determines connections between network objects. These can complement the method described in this application, for example in helping to define up and down ports.
However the method described in this application does not rely on the previous method to any degree.
The present invention uses bridge table, arp table 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

4 devices which report tables, down ports do not. This concept dramatically reduces the computational complexity and greatly increases the accuracy of connection determination.
In addition, another embodiment of the invention is a novel method for distinguishing up and down.
An embodiment of the invention is 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 dependance on data-relay devices seeing the source addresses of other data-relay devices directly, in contrast to the systems described in U.S. patent 5,527.157 and PCT publication WO 95/06989.
The removal of invalid and moved source addresses from the table data is an embodiment of the present invention, as are the methods for doing so. This makes the methods of the present invention approximately 100 fold less prone to error than the prior art. This increased accuracy becomes increasingly necessary as the use of portable computers becomes more widespread.
In accordance with another embodiment of the invention, there is an explicit tradeoff of the accuracy of connections against the rapidity with which changes in the network are tracked.
The present invention determines whole families of topologies previously only handled by traffic patterns in the Loran traffic method, e.g.. multiple connections between switches and segmented hubs. The present invention is thus very useful when the traffic data is unavailable or is misreported by devices.
The present invention is entirely automatic and requires no operator intervention or manual assistance.
This is quite unlike the methods described in the

5 Cabletron references noted above, which require a human expert to help it by restricting its search.
In accordance with an embodiment of the invention, a method of determining the topology of a data network comprised of network devices including data relay devices, comprises:
(a) obtaining table data including bridge table and arp table data and source address capture data from the data relay devices, (b) producing for each port of each data relay device a set of source addresses perceived by each said port over a period of time, (c) determining as up ports those of said ports which have carried frames of data transmitted through devices with said tables, which devices have other ports than a port under consideration, and determining remaining ports as down ports, (d) determining connections to down ports from devices seen from a down port, and (e) determining connections between up ports and between up and down ports from the source addresses.
In accordance with another embodiment, the aforenoted method further comprises determining a connection between a device having a down port and an up port by seeing an object connected to a down port and thereby inferring a connection to the device.
BRT_EF INTRODUCTION TO THE DRAWINGS
A better understanding of the invention will be obtained with reference to the detailed description below, in conjunction with the following drawings, in which:
Figure 1 is a block diagram of a representative network, and Figure 2 is an example of a detail of the network

6 of Figure 1.
DETAILED DESCRIPTION OF EMBODIMENTS OF THE INVENTTnN
A known discovery program determines a list of devices in the network. A known poller program extracts bridge table, arp table, source address capture and other table data from data-relay devices and produces for each port the set of source addresses perceived by that port over a given period of time.
In an embodiment of the present invention, those ports which see frames transmitted through other devices with tables, is first determined. These ports are termed up ports. The remaining ports with tables are termed down ports. The up ports see addresses seen by two or more ports on a single other device. The method then divides the problem of determining the topology into two:
determining connections to down ports and determining connections between up ports. All objects seen off a down port are directly or indirectly connected to that down port. Any up port seeing an object connected to a down port on device B must be seeing frames passed through device B, so it must see device B. The sets of objects like device B seen in this manner by up ports are now compared. The pairs of up ports for which the intersections of these sets are minimal are defined as connected. The existence of non-zero intersections or multiple zero intersections for a single port indicate the existence of a non table reporting object connected to that port and that its connections to other up ports lie through that object.
Thus an embodiment of the invention is comprised of dividing the ports into up ports and down ports, and then exploiting the results from down connections to solve the problems for up connections.

7 DEFINITIONS
Port i is in device A.
Data-relay device: a device that receives frames of data on one or more ports and retransmits them on one or more ports.
Device: a network device communicates via ports with one or more other network devices. Examples of devices are workstations, repeaters, switches and routers. The latter three are data-relay devices.
NS(Aa~j~: the number of members in the set formed by the intersection of S(Ai) and S(Bj). It counts how many devices are seen by both Ai and Bj .
Ny~.~Ss"~: the number of members in the set formed by the intersection of V(Ai) and V(Bj). It counts how many table providing devices are seen by both Aiand Bj.
Port: a port is an interface by which the device may send or receive communications.
Source address: a unique label assigned to each hardware device by the manufacturer. Often called MAC addresses.
S(A~~: the set of source addresses recorded from frames that entered that port over the table collection period.
the set of all network devices which have source address tables.
If device A is in set T and Ai connects directly or indirectly to one or more devices in set T then port Ai is up. Down ports are not up.
y: The visible set V(Ai) for up port Ai is the set of all devices with tables that Ai sees. V(Ai) includes B if NS (Ai, Bj ) > 0 for any j .
x: The set of all down ports in the network.
y: The set of all devices in the network seen by down port ports.
The invention will be described with reference to a representative network shown in Figure 1. In this

8 network there are four data-relay devices (A,C,D,E) which report tables and one (B) which does not. There are also eight workstations (n,m,p,q,r,s,t,u) which are connected to ports off these devices. The port numbers are shown for the devices which report tables. Device B does not report any information so its ports are unknown. Note that the source addresses of the managed devices A,C,D
and E and of the unmanaged device B are not available in any table.
The source addresses in the tables from each port are as follows:
S(A1) - m,n,u,t,s,r S (A2 ) - p S(A3) - q S(C1) - p,q,s,r,m S(C2) - u,t S(C3) - n S(D1) - n,m,p,q,r,s S(D2) - t S(D3) - a All the ports with tables are evaluated periodically to determine which ports are up and which are down. Generally if a port sees only one device it will be down, but there are three other methods for recognising up ports. The first and second methods work on the first and all subsequent evaluations. The third method works on the second and all subsequent evaluations.
If NS (Ai, Bi) > 0 and NS (A;, Bk~j) > 0 then Ai is defined as an up port. This means that if Ai sees devices seen on port Bj and also sees devices seen on port Bk~j then Ai must be an up port.
As may be seen in the network of Figure 1, A1 is an up port because NS (A1, EZ) > 0 and NS (A1, E3) > 0.

9 If the intersection of S(Ai) and T is not zero, then A1 is an up port. This means that if Ai sees the source addresses of any up port then it must be an up port. This rather rarely occurs but is included for completeness. If Bj is a down port and Bj # Ai, then Ai is an up port if NS(Ai, Bj) >= 1. In other words, only up ports can see devices which are seen by down ports.
The method can be refined by requiring that only if a port is not defined as up over several evaluations can it be defined as down and therefore in set Y. This overcomes problems in sparse sets.
The method can be made even more robust by requiring that NS(Ai, Y#Ai) >= K, where K is > 1.
However, this is at the cost of failing to identify some up ports, or taking longer to do so.
This method is computationally cheaper if the ports in Y are sorted by the size of their sets and the smallest compared first.
Thus, in the example shown in Figure 1, A1 is up port because NS (A1, CZ) + NS (A1, C3) + NS (A1, D2) + NS (Al, D3 ) . . >= 1.
All devices whose source addresses are in the table of a down port are connected directly or via one or more unmanaged devices to that port since no other table reporting device can be in this table. If there is only one device in the table of a down port, it is directly connected to Ai. If there is more than one device, then all these devices are connected indirectly via a cloud to device Ai. The cloud represents one or more connected and unmanaged or improperly reporting devices. The Loran traffic method referred to above describes other methods for making connections which can override these table defined connection suggestions.
Up ports are directly or indirectly connected only to other up ports. Moreover only devices with up ports need be considered in determining how up ports are interconnected. Finally, if an up port sees the source address of an device which is also seen by a down port, this up port can be considered to seeing the device which includes that down port. Exploitation of these three definitions leads to three very important effects provided by the present invention: greater accuracy in making connections, the computational effort is enormously reduced and the existence and placement of unmanaged devices can be accurately deduced.
The proportion of up ports to down ports in a network is typically at least 1:10. The number of managed devices with up ports in a network is typically less than 10% of all devices in the network. Almost all devices with tables have at least one up port so that proportion of devices with tables is also 10% of all devices in the network.
The probability of making a mistake in an up port connection is therefore reduced by a factor of up to 100 in comparison to any method that does not consider up port conditions, since the number of possible choices is very greatly reduced. Moreover, the probability of a down port seeing other devices with down ports is immensely greater through the mapping from down ports than by seeing their source addresses directly.
Experiments have shown this probability to be at least 10 times and is often substantially greater.
Each up port has created for it a table of the devices with up ports that it can see. The overlap of these tables is assessed. This process is order NzM where N is the number of up ports and M is the number of devices with tables. Since only up ports are considered, N is 1/10 of that if all ports were considered. Since only devices with tables are considered, M is only 1/10 that if all devices were considered. Computational effort is therefore reduced by a factor of 1000.
The third major effect is the ability to deduce the existence of unmanaged devices lying between up ports. The way in which this is done is described below, and is also a major advance in the art.
The set of up ports which lie between port Ai and any other device in T and which includes Ai is the set for which NV(Ai, Bj) is minimal for either Ai or Bi. The determination of the sets has three steps:
1: determine the set V for each up port;
2: determine NV(Ai, Bj) for pairs of ports which can be compared;
3: determine the minimum NV(Ai, Bj) for all ports.
The set V(Ai) describes all devices with up ports that up port Ai definitely sees. V(Ai) also includes A.
The set V(Ai) for contains all devices B for which one of the following four conditions is true:
1: B - A
2: NS(Ai, Bj) > 0 and NS(Ai, Bk~j) > 0 3 : S (Ai) includes B
4: S(Bj) includes A
An example will be given below with reference to Figure 1:
V (A1) - A, C, E , D
V (Cl) - A, C, E
V (CZ) - C, D
V (Dl) - A, C, E , D
V(El) - A, C, E ,D
NV(Ai, Bj) for pairs of ports which can be compared is then determined as follows:
If NV(Ai, Bj) - NV(Ai, Cj) and C has one up port while B has more than one, then the connection is probably Ai- Bi and not Ai-Cj . Therefore the determination of NV(Ai, Bj) is done in four passes and the comparisons done in each pass depend on the multiplicity of up ports in devices compared. This will be explained in more detail later. When the set of values of NV(Ai, Bj) is complete it is checked to make sure connections forbidden in the spanning tree are rejected as will also be described in more detail below. The most probable connections are those with the lowest definition of UN:
how many up ports exist on each device.
UN(A) is the number of up ports on device A. In the example in Figure 1, the values of UN are as follows.
UN (A) - 1 UN (C) - 2 UN (D) - 1 UN (E) - 1 To determine NV(Ai, Bj), multiple passes are undertaken.
For example, this can be done in three passes. In each pass devices are selected as being comparable only if they meet the criteria for that pass. Comparisons made in earlier passes and which have the same NV value are more probable.
pass: source target 1: UN(A)> 1 UN (B) > 1 2: UN(A)> 1 UN(B) - 1 3: UN(A)= 1 UN(B) - 1 Checking The validity of the comparison of V(Ai) and V(B~) is then checked. Multiple connections between two devices are forbidden in many networks (ie: spanning tree between two switches) . Therefore if NV (Ai, Bj) - NV (Ai, Bk#j) the validity of all NV(Ai, Bj) is checked as f O110WS .
All the NV(Ai, Bj) are discarded unless:
either A or B (or both) are segmented devices:
and NS(Ai, Bx~j) > 0 such that k is in the same segment as j or NS (Bj, Ak,~i) > 0 such that k is in the same segment as i.
As an example, with reference to Figure 2:
Both NV (A1, Bl:l) and NV (Al, BZ:1) - 0:
Al is connected to segment 1 of B and so:
NS (Ai, Bl:z) > 0 so NV (A1, B1:1) is legal .
NS (Ai, B2:n) - 0 for n=2 , 3 , 4 so NV (Al, BZ:l) is discarded.
The minimum NV(Ai, Bj). for all ports is then determined. Connections are made to Aifrom all Bi such that NV(Ai, Bj) <= NV(Q, Bj) for any Q. The presence of multiple connections to a single port Ai indicates the existence of one or more unmanaged devices between the various up ports attempting to connect to Ai. This unmanaged device or devices is represented as a single cloud to which is connected Ai and all the Bjfor which connections to Ai are suggested.
Once the connection of a set of up ports F is determined, the intersection of all the S(F) defines the set of devices to be interconnected, such that the ports of devices with up ports have been defined but the ports of devices without tables may, if the source address in the S(F) is not unique to a port on that device, the port will be defined as unknown.
In operation, firstly all pairs of up ports for which NV(Ai, Bj)=0 are connected. Almost always these will be direct connections. However, if in Figure 1 the unmanaged device B was directing traffic to A only from E
and from C only to E, then NV (A1, El) and NV (C1, El) would both equal 0. Under these conditions a cloud would represent B and the correct ports on A, B and C connected to this cloud.
Next all pairs of ports for which NV(Ai, Bj) is non zero are considered. Rings of connections are found such that NV (Ai, Bj ) - NV (Ai, Ck) . These rings are suggestions of the set of the up ports to be interconnected. Figure 1 has the ring Al, C1 and El. The intersected set of S(Al), S(Cl) and S(El) - m. Therefore this method produces the connections of these three up ports and the device m, all connected to a single cloud which represents one or more interconnected and unmanaged devices. In this example this cloud just represents the device B.
In dealing with ports on devices without tables, if a device has a source address which is only used on one port, then it possible for the two methods described above to uniquely identify the port for a connection. If the source address occurs on more than one port on that device, then the port to which the connection should make is unknown, unless further data is used and this connection is the only one suggested to a downport. The data is used to determine which of the possible ports is the most probable candidate by comparing the candidate port to the downport. This data includes any quality measurable on the ports in question: eg: frame rate, byte rate, collision rate, broadcast rate, line status flag, line interface type, line speed etc. Several of these have been explained in detail in the aforenoted Loran traffic method.
Connections proposed by down ports and by up ports are based on data which is not current and may have been collected over many hours or even days. Also the data is almost always incomplete, due to sampling considerations for source address capture tables and due to aging for bridge and arp tables. Therefore the probability that the connection suggested is correct depends on the completeness of the data available and on the stability of the network. The following describes how to trade off the accuracy of connections against the rapidity with which changes in the network are tracked.
Since the methods are performed periodically, they can produce somewhat different results even with a completely static network topology, depending on the sparseness of the table data collected.
Suppose a connection is suggested from port Ai to B~ by one of these two methods and that Ai has a table of non zero size (S(Ai) > 0).
Define C: as the probability that a connection suggestion is correct.
P1: as the probability a connection will be correct and will be confirmed.
P2: as the probability a suggested connection will be correct.
R: as how often in succession this same new suggestion has been made for Aiand Bj T: as how many times the previous connection of Ai to X
and Bj to Y have failed to be confirmed (if there are any connections to Ai or B~). The minimum of either is chosen.
The probability that the previous connection to Ai or Bj is correct = (1-P1)T ........... 1.1 The probability that the suggested connection of Ai to Bj is wrong = (1-P2)R ..............1.2 The probability that inserting the new connection is wrong = (1-P1)T(1-P2)R ..............1.3 As an example:
Let P1 =0.7, P2=0.6, T= 3 and R=2 The probability of inserting the new connection is wrong = 0.004.

By choosing T and R and by measuring P1 and P2 the method can be made to trade off accuracy of topology changes against how rapidly it makes them. P1 can be measured by the recent history of confirmations by the method of its previous suggestions. P2 is measured by determining how frequently suggestions are rejected with T=0 and R=1.
The longer the period of time over which table data is collected, the higher the probability that any suggested connection for a connection which has not been moved will be correct. Since the probabilities are measurable, the method can either aggregate reports over a period of time until the connections are sufficiently believable, or the result can be ignored until the.
probability has improved due to network conditions returning to normal.
Average networks have been found to have around a 1% level of incorrect table data. Bad networks can have levels as high as 10%. This incorrect table data needs to be identified and then removed from the tables. The methods described below reduce the level of incorrect by more than 100 fold. In most networks this means practically no faulty data gets through to the connection methods described above. In turn this greatly improves the accuracy and hence the rapidity with which the topology can be determined. This concept of removing noise from the source address table data is novel as are the methods for doing so.
There are five reasons why the table data can be wrong. For each of the reasons a corresponding method is described which detects and removes the faulty data.
1: Movement of devices in the network. When a device is moved from one place to another, its address will, for a while, turn up as if it were in both places at the same time. Test boxes which are put in many places during a day often have multiple apparent locations.
2: Invalid source addresses. The device reporting the table data has collected invalid source addresses in its table or misreports them. These addresses do not refer to any device. This will be rather common in busy ports on some repeaters.
3: Duplicate source address. The same source address is used in more than one device at the same time. This is forbidden by the standards but happens due to poor manufacturing quality control.
4: Old addresses not being removed from the table. The device should remove addresses periodically from the tables. Sometimes the software in the device fails to do so.
5: Operator mistakes. The network operator can program some devices to permanently remember some addresses.
Should the device then be moved these addresses will be wrong.
Moving a device from one place to another can cause the same device to appear in incompatible tables, since the table data is collected over a long period of time. The following move detector logic detects moves and removes all data about moved devices from the tables in consideration. There are three algorithms that detect movement. When a device has been defined as moved, all tables that could overlap in time when that move was detected have this device removed.
There is one exception to this. If the movement is to a down port, then the address is left in the table of this down port only. Obviously if multiple down ports see the same address, then the last to see it will claim the connection.
A device A has moved if its connection has been determined to have changed. This determination could be done by one of the methods in this specification or otherwise, for example by one of the methods described in the aforenoted Loran traffic method or otherwise.
With regard to a device being seen on an up and a down port both on the same device, a device is defined as moved i f A exists in both S (Bi) and S (Bk~,i) and Bi is an up port and Bk is a down port in device B.
However, if B is a segmented repeater with more than one up port then both these B ports must be in the same segment or must share the same output traffic pattern (as defined in the methods of the aforenoted Loran traffic method.
With regard to a device being seen on two down ports.
A device A is defined as moved if:
A exists in both S (Bi) and S (Ck) and both Bi and Ck are down ports.
A special case of this exists where A exists in both S(Bi) and S(Bk) where k#i, which does not lead to any consideration that Biand Ck might now be up ports.
Invalid source addresses do not refer to any real device and are often created by bit rotations of valid source addresses. The following methods detect valid addresses.
(a) A source address is valid if it has been reported by a down port which sees only this source address.
(b) A source address is valid if it has ever been reported by two or more ports within a given period of time.
(c) A source address is valid if it has ever been successfully used in an SNMP query.
Some networks of N objects may generate as many as N/10 different invalid source addresses a day.
Duplicate source addresses exist if the same source address is used in more than one device at the same time. This is detected by the same source being labeled by more than one TCP/IP address. In more detail, should source X be seen with TCP/IP A, and then should source X be seen with TCP/IP B and then again seen with TCP/IP A all within the same period of time, then source X is being used both in device A and in device B. This period is chosen to be less than the time in which an IP
can be changed automatically (by DHCP) or manually.
Duplicate source addresses are removed from all tables.
It is possible that old addresses are not removed from the table. When the function called aging fails in switches, the tables the switch retains may never change.
Therefore these tables refer to the past and can cause many problems. However, aging failure almost always results in some of the devices seen by the switch being only seen by the switch (as they have now been removed from the network).
For example, let:
D= the number of devices in the set of all tables seen on A that have not been seen elsewhere for a week.
N = the number of devices in the set of all tables seen on A.
Then if D/M > a threshold then A probably has aging problems.
An alternative method counts how many devices seen on A have been moved, and when this ratio exceeds some threshold then A probably has aging problems.
A futher alternative combines the count of D and the count of moved devices and applies a threshold to this or its percentage of N.
Operators sometimes program in static information into a table for an device A and forget to remove the static information when they move A. This can be detected either by the move detector or when the source address of the mistaken device lies outside the TCP/IP
subnet of any subnet supported by the same port of the router that supports the subnet of A. This method therefore handles VLAN subnetting.
The present invention has been subjected to three classes of tests, those in simulated networks, those in customer networks whose topology is known and those in networks where the topology is unknown.
Simulations have been carried out to determine the validity of the logic for a wide variety of different topological structures (e. g.. a switch connected by many redundant links to a segmented repeater). These simulations also verified the robustness in the face of incorrect and sparse table data.
Tests in networks where the customer knows the topology allowed more practical tests. Typically network connections in networks of 3000 objects were 95~ complete using 36 hours of data. All were correct. The remaining connections required more data to determine the network exactly. The methods described in this specification typically required less than 2 minutes of P180 processor processing to perform this task.
Finally in networks in which the topology was unknown, connections found in accordance with the present invention which are directly between objects were crosschecked by the methods of traffic which is the subject of the aforenoted Loran traffic method, which method now has an extensive history and well determined accuracy. These results verified the accuracy and processor efficiency of the present invention.
A person understanding the above-described 2~

invention may now conceive of alternative designs, using the principles described herein. All such designs which fall within the scope of the claims appended hereto are considered to be part of the present invention.

Claims (2)

I claim:

1. A method of determining the topology of a data network comprised of network devices including data relay devices, comprising:
(a) obtaining table data including bridge table and arp table data and source address capture data from the data relay devices, (b) producing for each port of each data relay device a set of source addresses perceived by each said port over a period of time, (c) determining as up ports those of said ports which have carried frames of data transmitted through devices with said tables, which devices have other ports than a port under consideration, and determining remaining ports as down ports, (d) determining connections to down ports from devices seen from a down port, and (e) determining connections between up ports and between up and down ports from the source addresses.

2. A method as defined in claim 1 comprising determining a connection between a device having a down port and an up port by seeing an object connected to a down port and thereby inferring a connection to the device.