Determining physical topology across repeaters and bridges in a computer network

• US 5,297,138 A
• Filed: 04/30/1991
• Issued: 03/22/1994
• Est. Priority Date: 04/30/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Company (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Black, Chuck A.
• Primary Examiner(s): Chin, Wellington
• Application Number:
  US07/693,980
• Time in Patent Office: 1,057 Days
• Field of Search: 370/94.3, 370/94.1, 370/94.2, 370/85.13, 370/85.14, 370/97, 370/60, 370/60.1, 370/65.5, 340/825.03, 340/825.02
• US Class Current: 370/254
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

The physical topology of devices on a network is determined. All the devices on the network are identified. A first device is selected. For each port of the first device a connection structure is recursively determined for all devices which communicate to the first device through the port.

Claims

1. A method for determining physical topology of a plurality of devices in an extended computer network, each device in the plurality of devices having at least one port, the method comprising the steps of:

(a) choosing a particular device from the plurality of devices as a starting reference, and

(b) recursively determining network device connections on each port of the particular device.

2. A method for determining physical topology of a plurality of devices on a network, each device in the plurality of devices having at least one port, the method comprising the steps of:

(a) identifying all the devices on the network;

(b) selecting a first device from the plurality of devices;

(c) determining a connection structure for all devices from the plurality of devices which communicate to the first device through each port of the first device wherein for a first port of the first device, step (c) includes the substeps of

(c.1) determining which devices from the plurality of devices which communicate to the first device through the first port are not directly connected to the first device through the first port, substep (.1) including for every second device from the plurality of devices which communicates to the first device through the first port, marking the second device as not directly connected to the first device when any third device from the plurality of devices which communicates to the first device through the first port is detected communicating to the second device through any port of the third device which is different from a first port of the third device through which the third device communicates to the first device, and

(c.2) determining which devices are directly connected to the first device through the first port.

3. A method as in claim 2 wherein step (c) additionally includes the substep of:

(c.3) determining a connection structure for all devices from the plurality of devices connected to a first port of a fourth device from the plurality of devices, wherein there is no direct connection to the first device from the first port of the fourth device and the fourth device is determined in substep (c.2) to be directly connected to the first device through the first port of the first device.

4. A method for determining physical topology of a plurality of devices on a network, the method comprising the steps of:

(a) discovering identities of each device in the plurality of devices;

(b) selecting a first device from the plurality of devices;

(c) determining, by the first device for every other device in the plurality of devices, on which port the first device communicates with each of the other devices; and

,

(d) determining which devices are not directly connected to any port of the first device including the substeps of

(d.1) selecting a second device from the plurality of devices which communicates with the first device through a first port of the first device, and

(d.2) for every third device in the plurality of devices to which the first device communicates through the first port, performing the following substeps;

determining whether the second device communicates to the third device through a same port of the second device as the second device communicates with the first device, and

when the second device is detected communicating to the third device through a different port of the second device from which the second device communicates with the first device, marking the third device as not connected to the first device.