Method of determining the topology of a network of objects

• US 6,046,988 A
• Filed: 02/10/1999
• Issued: 04/04/2000
• 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:
  US09/248,010
• Time in Patent Office: 419 Days
• Field of Search: 370/229, 370/230, 370/232, 370/233, 370/234, 370/235-237, 370/254-258
• US Class Current: 370/254
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/024 by adaptive sampling
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/02 Topology update or discovery

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 network topologies comprising:

(a) monitoring traffic received by devices connected in the network and traffic emitted out of said devices,

(b) correlating traffic out of said devices with traffic into said devices,

(c) indicating a network communication path between a pair of said devices in the event that the correlation of traffic out of one of said pair of said devices and into another of said pair of said devices is in excess of a predetermined threshold,

(d) the step of correlation being comprised of time aligning said monitored traffic to form a pair of sequences having the same time interval and a common beginning and end time, normalizing said sequence, and substantially analyzing said normalized sequence to obtain a correlation value, and

(e) at least one of the steps of;

(i) curtailing monitoring said traffic between further pairs of devices which includes one of said pair of devices in the event a correlation is in excess of a said predetermined threshold,

(ii) avoiding monitoring said traffic between further pairs of devices which include any device of said pair of devices for which a correlation was previously determined to be in excess of said predetermined threshold,

(iii) curtailing monitoring said traffic between further pairs of devices which includes one of said pair of devices in the event a correlation is unlikely to reach said predetermined threshold,

(iv) monitoring said traffic between pairs of similar devices prior to monitoring said traffic between the other pairs of devices,

(v) avoiding monitoring said traffic between pairs of devices of which one device of said pair is in a class sufficiently different from another device of said pair that the devices of said pair are unlikely to be in communication,

(vi) monitoring said traffic with a small number of traffic measurements and then monitoring said traffic further with a significantly larger number of traffic measurements only in the event that a determined correlation is not in excess of said predetermined threshold,

(vii) monitoring said traffic with a small number of traffic measurements and then monitoring said traffic further with a significantly larger number of traffic measurements only in the event that a determined correlation is in excess of said predetermined threshold,

(viii) monitoring and correlating said traffic between pairs of devices contained within each of separate parts of said network, and monitoring and correlating said traffic between said separate pairs of said network,

(ix) monitoring and correlating said traffic separately between pairs of devices contacted within each of separate parts of said network, and indicating network communication paths between said separate parts of said network, and

(x) monitoring devices to determine their mean traffic, sorting the devices by said mean traffic so as to rank the devices and correlating said traffic between pairs of devices only should their relative ranks be compatible with a possibly better correlation than that already established for either of the pair of devices or than a predetermined cutoff.

2. A method of determining network topologies comprising:

(a) monitoring traffic received by devices connected in the network and traffic emitted out of said devices,

(b) correlating traffic out of said devices with traffic into said devices,

(c) indicating a network communication path between a pair of said devices in the event that the correlation of traffic out of one of said pair of said devices and into another of said pair of said devices is in excess of a predetermined threshold,

(d) the step of correlation being comprised of time aligning said monitored traffic to form a pair of sequences having the same time interval and a common beginning and end time, normalizing said sequence, and substantially analyzing said normalized sequence to obtain a correlation value, and

(e) at least one of the steps of;

(i) curtailing monitoring said traffic between further pairs of devices which includes one of said pair of devices in the event a correlation is in excess of a said predetermined threshold,

(ii) avoiding monitoring said traffic between further pairs of devices which include any device of said pair of devices for which a correlation was previously determined to be in excess of said predetermined threshold,

(iii) curtailing monitoring said traffic between further pairs of devices which includes one of said pair of devices in the event a correlation is unlikely to reach said predetermined threshold,

(iv) monitoring said traffic between pairs of similar devices prior to monitoring said traffic between the other pairs of devices,

(v) avoiding monitoring said traffic between pairs of devices of which one device of said pair is in a class sufficiently different from another device of said pair that the devices of said pair are unlikely to be in communication,

(vi) monitoring said traffic with a small number of traffic measurements and then monitoring said traffic further with a significantly larger number of traffic measurements only in the event that a determined correlation is not in excess of said predetermined threshold,

(vii) monitoring said traffic with a small number of traffic measurements and then monitoring said traffic further with a significantly larger number of traffic measurements only in the event that a determined correlation is in excess of said predetermined threshold,

(viii) monitoring and correlating said traffic between pairs of devices contained within each of separate parts of said network, and monitoring and correlating said traffic between said separate pairs of said network,

(ix) monitoring and correlating said traffic separately between pairs of devices contacted within each of separate parts of said network, and indicating network communication paths between said separate parts of said network, and

(x) monitoring devices to determine their mean traffic, sorting the devices by said mean traffic so as to rank the devices and subsequently monitoring devices in order of rank so that devices with similar mean traffic have greatly reduced time alignment of differences.