Method of determining the topology of a network of objects

• US 6,411,997 B1
• Filed: 11/15/1996
• Issued: 06/25/2002
• 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): Maung, Zarni
• Application Number:
  US08/749,671
• Time in Patent Office: 2,048 Days
• Field of Search: 709/228, 709/300, 709/301, 709/227, 709/224
• US Class Current: 709/224
• 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/0829 Packet loss
• 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/38 Flow based routing

Abstract

A method of determining a connection between a data emitting device and a network device which may carry the data, wherein the network device is comprised of a store for a data source address of a last frame transmitted to the network device and an input traffic count comprising (a) periodically reading the data source address, (b) periodically reading the input traffic count, (c) determining whether the data source address has always stayed the same, (d) in the event the data source address has always stayed the same, determine whether the traffic count has exceeded a predetermined threshold, (e) in the event the result of step (d) is true, indicate that the data source address identifies with acceptable probability a data emitting device directly connected to the network device.

Claims

1. A method of determining a connection between devices comprising:

(a) determining the probability of said connection using a method which would indicate said connection with highest acceptable probability,

(b) in the event step (a) fails, determining the probability of said connection using a method having a lower acceptable probability,

(c) in the event step (b) fails, continuously repeating step (b) using methods having successively lower acceptable probabilities of indicating said connection, until a connection is indicated.

2. A method as defined in claim 1, in which step (a) is comprising of defining W=Q/L*, where

L* is a number of measurements used in comparing two sequences of data, one being transmitting by one device and one being received by a receiving device, and

Q is probability of similarity computed, for example by an incomplete gamma function f(Q,L− 1) and indicating an acceptable probability of said connection in the case of W<

0.1 and L*>

=45.

3. A method as defined in claim 2 in which steps (b) and (c) are, in order of most probability to least probability

(i) determining a direct connection by sending a signal from a source to a destination while watching for traffic caused by this signal in all objects which could be on the path,

(ii) determining an indirect connection by sending a signal from a source to a destination while watching for traffic caused by this signal in all objects which could be on the path,

(iii) I. over at least 45 measurements of traffic indicated frames of data at an input port of a network device, periodically reading a data source address in a network device which stores an address of a data source which has transmitted a last frame entering the network device,

II. periodically reading a traffic count of data entering the network device,

III. determining whether the data source address has always stayed the same,

IV. in the event the data source address has always stayed the same, determine whether the traffic count has exceeded a predetermined threshold,

V. in the event the result of step (IV) is true, indicate that the data source address identifies with acceptable probability a data emitting device directly connected to the network device,

VI. in the event the result of step III is false, indicate that a device identified by the data source address is indirectly connected to the network device,

(iv) use an address resolution table of the network device as the store,

(v) establish a mask field in a management information base of the network device for all devices in a subset which passes data through the network device having a property