Apparatus and method for determining a computer network topology

• US 5,727,157 A
• Filed: 12/19/1996
• Issued: 03/10/1998
• Est. Priority Date: 09/17/1990
• Status: Expired due to Term

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Cabletron Systems Incorporated (Extreme Networks, Inc.)
• Inventors: Orr, Timothy L., Gray, Eric W.
• Primary Examiner(s): Geckil, Mehmet B.
• Application Number:
  US08/770,696
• Time in Patent Office: 446 Days
• Field of Search: 395/20.11, 395/200.16, 395/200.59, 395/200.53, 395/200.75, 395/200.68, 395/837, 370/94.1, 370/60, 370/301
• US Class Current: 709/224
• CPC Class Codes: G06F 11/2257 using expert systems
• CPC Class Codes: G06F 11/3006 where the computing system is distributed, e.g. networked systems, clusters, multiprocessor systems multiprogramming arrangements G06F9/46; allocation of resources G06F9/50
• CPC Class Codes: G06F 11/3051 Monitoring arrangements for monitoring the configuration of the computing system or of the computing system component, e.g. monitoring the presence of processing resources, peripherals, I/O links, software programs verification or detection of system hardware configuration G06F11/2247
• CPC Class Codes: G06F 11/32 with visual or acoustical indication of the functioning of the machine
• CPC Class Codes: G06F 11/3447 Performance evaluation by modeling
• CPC Class Codes: H04L 41/00 Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]

Abstract

An apparatus and method for determining the topology of a computer network including data-relay devices and node devices, based on a comparison of source adddresses heard by the various data relay-devices. A source address table is compiled for each port of each data-relay device, and for each select pair of ports the addresses in the source tables are compared to determined whether there is an intersection of heard devices. In order to account for directed transmissions which are not heard at every port, further comparison is made of all of the other ports of the device, eliminating the ports for which the intersection is the empty set. From the determined connections, a topology of the network is graphed showing direct and transitive connections. In cases where there is both a direct and transitive connection, the redundant direct connection is eliminated.

Claims

1. A method of determining a topology of a computer network including node devices and data-relay devices coupled to one another by a multi-drop line, each data-relay device having at least one port, the method including the steps of:

acquiring a list of the data-relay devices in the computer network,

acquiring a source address table for each at least one port of each data-relay device in the list, the source address table being a compilation of source addresses of packets received from respective node devices and source addresses of management response packets received from other respective data-relay devices on the respective at least one port of the respective data-relay device,

selecting a unique ordered pair of different data-relay devices X and Y;

(a) selecting a pair of ports X_i and Y_j on the selected different data-relay devices X and Y, respectively, where i represents a specific port of device X and j represents a specific port of device Y;

(b) determining whether the source address table of port X_i includes an entry for device Y and whether the source address table of port Y_j includes an entry for device X, and when the answer to both is affirmative, establishing a connection between ports X_i and Y_j in the topology; and

(c) repeating the above selecting and determining steps (a) and (b) for each different pair of ports of the data-relay devices X and Y;

(d) for each pair of ports X_i and Y_j wherein the source address table of port Y_j does not include an entry for device X, determining whether there is some intersection of the entries of the source address tables for port Y_r and port X_q where r is not equal to j, and q is not equal to i, and when the answer is affirmative, establishing a connection between port X_i and port Y_r in the topology; and

(e) repeating the second determining step (d) for each pair of ports X_i and Y_j for which the source address table of port Y_r does not include an entry for device X;

(f) repeating the above selecting and determining steps (a)-(e) for each unique ordered pair of different data-relay devices X and Y in the network; and

(g) generating a display of the established connections between the data-relay devices to show the network topology.

2. The method of claim 1, further including:

removing direct connections between X_i and Y_j from the network topology display when there is a transitive connection between X_i and Y_j.

3. The method of any one of claims 1 and 2, wherein the data-relay devices send directed transmissions.

4. The method of any one of claims 1 and 2, wherein the network includes a network management system which communicates with the data-relay devices.

5. The method of claim 4, wherein the network management system has a virtual network of models representing node devices and data-relay devices, and wherein the models have means for comparing the source address tables to determine whether there is some intersection.

6. The method of claim 4, wherein the data-relay devices transmit directed responses to management requests only on the port where a management request was received.

7. The method of any one of claims 1 and 2, wherein the network topology is provided to a user by a display unit connected to the network.

8. The method of any one of claims 1 and 2, wherein the display includes connections between the data-relay devices and the node devices.

9. The method of claim 3, wherein the network topology is used by the network management system for one or more of controlling traffic on the network, optimizing network resources, security, and isolation of network faults.

10. The method of claim 1, wherein the data-relay devices include bridges, repeaters, and hubs.

11. The method of claim 1, wherein the node devices transmit packets which include the source address of the transmitting node device.

12. The method of claim 1, wherein the data-relay devices are logically connected in a spanning tree.

13. The method of claim 1, wherein the data-relay devices include three-port data-relay devices which provide branch connections.

14. A system for determining a topology of a computer network having node devices mad data-relay devices coupled to one another by a multi-drop line, means for storing a source address table for an associated port of each data-relay device, the source address table being a compilation of source addresses of packets received from respective node devices and source addresses of management response packets received from other respective data-relay devices on the associated port, the system including:

means for processing the addresses in the source address tables of different pairs of ports of different data-relay devices to determine whether there is a connection between the respective ports, the processing means comprising;

means for selecting a unique ordered pair of different data-relay devices X and Y;

(a) means for selecting a pair of ports X_i and Y_j on the selected different data-relay devices X and Y, respectively, where i represents a specific port of device X and j represents a specific port of device Y;

(b) means for determining whether the source address table of port X_i includes an entry for device Y and whether the source address table of port Y_j includes an entry for device X, and when the answer to both is affirmative, establishing a connection between ports X_i and Y_j in the topology;

(c) means for repeating operation of the above selecting and determining means (a) and (b) for each different pair of ports of the data-relay devices X and Y;

(d) for each pair of ports X_i and Y_j wherein the source address table of port Y_j does not include an entry for device X, means for determining whether for all q not equal to i, there is some intersection of the entries of the source address tables for port X_q and port Y_r, for all r not equal to j, and when the answer is affirmative, establishing a connection between port X_i and port Y_r in the topology;

(e) means for repeating operation of the second determining means (d) for each pair of ports X_i and Y_j for which the source address table of port Y_j does not include an entry for device X;

(f) means for repeating operation of the above selecting and determining means (a)-(e) for each unique ordered pair of different data-relay devices X and Y in the network; and

(g) means for generating a display of the established connections between the data-relay devices to show the network topology.

15. The system of claim 14, further including means for removing direct connections between X_i and Y_j from the network topology display when there is a transitive connection between X_i and Y_j.

16. The system of any one of claims 14 and 15, wherein the data-relay devices have means for sending directed transmissions.

17. The system of any one of claims 14 and 15, wherein the network includes a network management system which communicates with the data-relay devices.

18. The system of any one of claims 14 and 15, further including a display unit connected to the network wherein the network topology is provided to a user.

19. The system of any one of claims 14 and 15, wherein the display includes connections between the data-relay devices and the node devices.

20. The system of claim 17, wherein the network management system has a virtual network of models representing node devices and data-relay devices, and wherein the models have means for comparing the source address tables to determine whether there is some intersection.

21. The system of claim 17, wherein the network topology is used by the network management system for one or more of controlling traffic on the network, optimizing network resources, security, and isolation of network faults.

22. The system of claim 17, wherein the data-relay devices transmit directed responses to management requests only on the port where a management request was received.

23. The system of claim 14, wherein the data-relay devices include bridges, repeaters, and hubs.

24. The system of claim 14, wherein the node devices transmit packets which include the source address of the transmitting node device.

25. The system of claim 14, wherein the data-relay devices are logically connected in a spanning tree.

26. The system of claim 14, wherein the data-relay devices include three-port data-relay devices which provide branch connections.

27. A method of determining a topology of a computer network including node devices and data-relay devices coupled to one another by a multi-drop line, each data-relay device having at least one port, each at least one port having associated with it a source address table including source addresses of packets received from respective node devices and source addresses of management response packets received from other respective data-relay devices on the respective port, the method comprising steps of:

acquiring a list of data-relay devices;

selecting a unique ordered pair of data-relay devices X, Y from the list;

for the selected pair of data-relay devices;

(a) for each at least one port X_i on device X;

(b) determining whether the source address table for port X_i includes an entry for device Y; and

(c) when the source address table for port X_i includes an entry for device Y, for each port Y_j on device Y;

(d) determining whether the source address table for port Y_j includes an entry for device X, establishing a connection between ports X_i and Y_j ; and

(e) when the source address table for port Y_j includes an entry for device X, establishing a connection between ports X_i and Y_j ; and

(f) when no port Y_j on device Y has a source address table with an entry for device X, determining whether any source address table of any port Y_r other than port Y_j intersects with any source address table of any port of device X other than port X_i and when there is an intersection found, establishing a connection between port X_i and port Y_r ; and

repeating steps (a)-(f) for each unique ordered pair of data-relay devices X, Y; and

(g) generating a display of the established connections between the data-relay devices to show the network topology.

28. A method of determining a topology of a computer network including node devices and data-relay devices coupled to one another by a multi-drop line, each data-relay device having at least one port, each at least one port having associated with it a source address table including source addresses of packets received from respective node devices and source addresses of management response packets received from other respective data-relay devices on the respective port, the method comprising the steps of:

selecting a unique ordered pair of first and second data-relay devices;

for the selected pair of first and second data-relay devices;

(a) for each respective port on the first data-relay device;

(b) determining whether the source address table for the respective port on the first data-relay device includes an entry for the second data-relay device; and

(c) when the source address table for the respective port on the first data-relay device includes an entry for the second data-relay device, determining, for each respective port on the second data-relay device, whether the source address table for the respective port on the second data-relay device includes an entry for the first data-relay device and when the source address table for the respective port on the second data-relay device includes an entry for the first data-relay device, establishing a connection between the respective port of the first data-relay device and the respective port of the second data-relay device;

(d) when the respective port on the first data-relay device includes an entry for the second data-relay device and no port on the second data-relay device has a source address table with an entry for the first data-relay device, determining whether any source address table entries of any of the ports on the second data-relay device intersect with any source address table entries of any of the ports on the first data-relay device except for the respective port on the first data-relay device; and

when such an intersection is found, establishing a connection between the respective port on the second data-relay device and the port on the first data-relay device which has an entry for the second data-relay device in its source address table; and

repeating steps (a)-(d) for each unique ordered pair of first and second data-relay devices; and

generating a display of the established connections between the data-relay devices to show the network topology.

29. A method of determining a topology of a computer network including node devices and data-relay devices coupled to one another by a multi-drop line, each data-relay device having at least one port, each at least one port having associated with it a source address table including source addresses of packets received from respective node devices and source addresses of management response packets received from other respective data-relay devices on the respective port, the method comprising the steps of:

selecting a unique ordered pair of first and second data-relay devices;

for the selected pair of first and second data-relay devices;

(a) determining whether the source address table for a respective port of the first data-relay device includes an entry for the second data-relay device;

(b) when the source address table for the respective port of the first data-relay device includes an entry for the second data-relay device;

(c) determining whether the source address table for a respective port of the second data-relay device includes an entry for the first data-relay device and, if so, establishing a connection between the respective port of the second data-relay device and the respective part of the first data-relay device;

(d) repeating step (c) for each port on the second data-relay device;

(e) when no source address table in the second data-relay device has been determined to include an entry for the first data-relay device;

(f) determining whether the source address table for a respective port of the second data-relay device intersects with a source address table for any port on the first data-relay device except for the respective port of the first data-relay device determined in step (a) and, if so, establishing a connection between the respective port of the second data-relay device and the respective port of the first data-relay device which has an entry for the second data-relay device in its source address table as determined in step (a); and

(g) repeating step (f) for each port on the second data-relay device;

(h) repeating steps (a)-(g) for each port on the first data-relay device; and

repeating steps (a)-(h) for each unique ordered pair of first and second data-relay devices; and

generating a display of the established connection between the data-relay devices to show the network topology.