Method of determining the topology of a network of objects

• US 5,933,416 A
• Filed: 02/09/1996
• Issued: 08/03/1999
• Est. Priority Date: 11/16/1995
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Loran Network Systems LLC (HP Inc.)
• Inventors: Slavitch, Michael, Schenkel, David, Dawes, Nicholas
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US08/599,310
• Time in Patent Office: 1,271 Days
• Field of Search: 370/254-258, 370/248, 370/249, 370/253, 370/241, 395/200.53
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/065 related to network devices
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/70 Routing based on monitoring results

Abstract

A method of determining network topologies comprising monitoring traffic received by devices connected in the network and traffic emitted out of the devices, correlating traffic out of the devices with traffic into the devices, indicating a network communication path between a pair of the devices in the event that the correlation of traffic out of one of the pair of the devices and into another of the pair of the devices is in excess of a predetermined threshold.

Claims

1. A method of determining the topology of a network comprising:

(a) transmitting a signal from a source device to a destination device,

(b) monitoring devices in said network including the destination device for reception of said signal,

(c) defining a sequence of devices within the network by sensing a sequence of reception of said signal in said devices from the source device toward the destination device,

(d) transmitting a further signal from the destination device to the source device in the event said sequence of devices apparently terminates at an incomplete link between the source device and the destination device,

(e) defining a reverse sequence of devices within the network by indicating a reverse sequence of reception of said further signal from the destination device toward the source device to the incomplete link, and

(f) indicating a cloud device linking the first sequence of devices to the second sequence of devices across the incomplete link.

2. A method as defined in claim 1 in which the signal is comprised of a sequence of packets.

3. A method as defined in claim 1 in which the signal is comprised of a sequence of bursts of PING packets.

4. A method of determining the topology of a network comprising:

(a) transmitting a signal from a source device to a destination device,

(b) monitoring devices in said network including the destination device for reception of said signal,

(c) defining a sequence of devices within the network by sensing a sequence of reception of said signal in said devices from the source device toward the destination device, and

(d) monitoring a drop rate from devices in said network and suspending transmitting said signal in the event the drop rate is in excess of a predetermined threshold.

7. A method as defined in claim 4, in which at least one device does not provide monitoring data, and indicating said sequence using said one device identified as a cloud which is connected to devices in the network which have an immediately earlier and earliest later reception of said signal.

5. A method of determining the topology of a network comprising:

(a) transmitting a signal from a source device to a destination device,

(b) monitoring devices in said network including the destination device for reception of said signal,

(c) defining a sequence of devices within the network by sensing a sequence of reception of said signal in said devices from the source device toward the destination device,

(d) in which the signal is a burst of a sequence of packets which is significantly longer than any change in traffic on said network within a preceding predetermined number of sampling periods.

6. A method as defined in claim 5 including suspending transmitting said signal for a predetermined period of time in the event the burst is in excess of predetermined length.

8. A method as defined in claim 5, in which at least one device does not provide monitoring data, and indicating said sequence with said one device identified as a cloud connected to devices in the network having an immediately earlier and earliest later reception of said signal.

9. A method as defined in claim 5, in which at least one device does not provide monitoring data, and indicating said sequence using said one device identified as a cloud which is connected to devices in the network which have an immediately earlier and earliest later reception of said signal.

10. A method as defined in claim 5, in which step (c) includes

(i) defining a top device having a highest level (n) in a sequence of devices,

(ii) choosing all devices that connect to a next lower sequence level n-1 and which have undefined sequence levels, and allocate a lower sequence level, and

(iii) repeating step (ii) until no more devices can be allocated.