Non-intrusive measurement of end-to-end network properties

• US 6,738,349 B1
• Filed: 03/01/2000
• Issued: 05/18/2004
• Est. Priority Date: 03/01/2000
• Status: Expired due to Term

• Current Assignee: Tektronix Incorporated (Fortive Corp.)
• Original Assignee: Tektronix Incorporated (Fortive Corp.)
• Inventors: Cen, Shanwei
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US09/516,649
• Time in Patent Office: 1,539 Days
• Field of Search: 370/231, 370/235, 370/252, 370/253, 370/401, 370/412, 370/413, 370/474, 710/29, 709/224, 709/228, 709/223, 700/32
• US Class Current: 370/231
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/06 Generation of reports
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps

Abstract

A method and apparatus for non-intrusive measurement of end-to-end properties of network flows uses a passive approach. An ingress monitor non-intrusively intercepts data units as they enter a network path through a network. Likewise an egress monitor non-intrusively intercepts the same data units as they leave the same network path. Each monitor generates a time stamp for each intercepted data unit using a common clock and derives a unique signature for each data unit such that the same data unit has the same signature at the entry as at the exit. Additionally each monitor counts the number of packets received from the network flow at the ingress and egress respectively. The signature, time stamp and packet counter value form an entry which is retained in an entry queue in each monitor. A data correlator coupled to an out-of-band network to which the monitors also are coupled periodically pulls a list of entries from each monitor and correlates the lists by matching signatures. The time stamps for the entries from the respective lists having the same signature are processed to obtain end-to-end latency of the network path, and the difference in counts over a given time period provides end-to-end packet loss measurements.

Claims

1. A method of non-intrusive measurement of end-to-end properties of a network flow, the network flow being a session of data units flowing from an ingress to an egress of a network path, comprising the steps of:

sampling the data units at the ingress using an ingress monitor;

generating a unique signature and input measurement data for each sampled data unit at the ingress monitor;

sampling the data units from the network flow at the egress using an egress monitor;

generating the unique signature and output measurement data for each sampled data unit at the egress monitor;

correlating entries from each of the ingress and egress monitors, the entries being in the form of a list for each monitor and each entry having the unique signature and associated measurement data for one of the data units, by matching the unique signatures from entries between the two lists; and

determining from the input and output measurement data for the matched entries the end-to-end properties of the network flow, wherein the input and output measurement data include counts of the numbers of data units received by the ingress and egress monitors respectively so far.

2. The method as recited in claim 1 wherein the input and output measurement data are timestamps indicating the time of receipt of the data units at the ingress and egress monitors, the timestamps being derived from a common clock.

3. The method as recited in claim 1 further comprising the step of subsampling the data units prior to the generating steps such that the ingress and egress monitors select the same subsampled data units with a random additive distribution.

4. The method as recited in claim 3 wherein the subsampling step comprises the step of masking of the unique signature such that only if the least significant portion of the unique signature has a specific given value is the data unit selected by the ingress and egress monitors.

5. A system for non-intrusive measurement of end-to-end properties of a network flow comprising:

an ingress monitor coupled to the input of the network flow for intercepting data units flowing through a network path, the ingress monitor identifying a unique signature and generating input measurement data for each data unit;

an egress monitor coupled to the output of the network flow for intercepting the data units flowing through the network path, the egress monitor identifying the unique signature and generating output measurement data for each data unit; and

a data correlator coupled to an out-of-band network to which the ingress and egress monitors are also coupled, the data correlator pulling lists of entries from the ingress and egress monitors, the entries containing the unique signature and measurement data for each data unit, correlating the lists of entries based on the unique signatures, and determining from the input and output measurement data of data units having the same unique signatures the end-to-end properties for the network flow.

6. The system as recited in claim 5, wherein the input and output measurement data are timestamps for the data units derived from a common clock indicating the time of arrival at the ingress and egress monitors respectively.

7. The system as recited in claims 5 or 6 wherein the input and output measurement data are counts of the number of data units received at the ingress and egress monitors respectively so far.

8. The system as recited in claim 5 wherein the ingress and egress monitors subsample the data units prior to generating measurement data, the data units selected being the same at the ingress and egress monitors with a random additive distribution.

9. The system as recited in claim 8 wherein the data units are subsampled based upon a given value for a least significant portion of the unique signature.