Apparatus and method for determining a computer network topology

Claim 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.

Claim 2

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.

Claim 4

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

Claim 5

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.

Claim 8

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.

Claim 9

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

Claim 15

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.

Claim 16

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.

Claim 18

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

Claim 19

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.

Claim 20

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.

Claim 21

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

Claim 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 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.

Claim 30

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.

Claim 31

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.

Claim 32

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.

Claim 33

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.

Claim 34

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.