Method and apparatus for non-intrusive measurement of round trip delay in communications networks

• US 5,521,907 A
• Filed: 04/25/1995
• Issued: 05/28/1996
• Est. Priority Date: 04/25/1995
• Status: Expired due to Fees

• Current Assignee: Visual Networks Technologies, Inc.
• Original Assignee: Visual Networks, Inc. (Fortive Corp.)
• Inventors: Nisbet, Thomas R., Ennis, James D. Jr., Hasselkus, John E., Troutman, Robert
• Primary Examiner(s): Chin, Wellington
• Application Number:
  US08/429,217
• Time in Patent Office: 399 Days
• Field of Search: 370/13, 370/17, 370/15, 370/60, 370/60.1, 370/94.1, 370/94.2, 370/85.1, 370/85.2, 370/85.3, 370/85.4, 370/85.5, 375/224
• US Class Current: 370/253
• CPC Class Codes: H04L 2012/5619 Network Node Interface, e.g. tandem connections, transit switching
• CPC Class Codes: H04L 2012/5649 Cell delay or jitter
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 43/12 Network monitoring probes
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 43/55 Testing of service level quality, e.g. simulating service usage
• CPC Class Codes: H04L 67/561 Adding application-functional data or data for application control, e.g. adding metadata
• CPC Class Codes: H04L 67/564 Enhancement of application control based on intercepted application data
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Measurement of round-trip delay or travel time in a communications network during in-service operation is accomplished by use of two probes, situated at respective points of interest along the communication network, and a processor. The probes receive identifiable data patterns normally transmitted over the communications network and generate a time stamp when each pattern arrives at or leaves the respective point. Each probe further generates a pattern identifier based on the data in the pattern and stores the identifier and time stamp as a pair in a buffer internal to each probe. Once the internal buffer contents exceed a predetermined amount of data, the processor receives the data from the buffers and matches pattern identifiers between the buffers to locate the departure and arrival time stamps of each pattern traveling between the probe points. Thereafter, the processor calculates an average of round-trip delay or travel times based on the departure and arrival time stamps of several patterns traveling in both directions between the probe points.

Claims

1. Apparatus for measuring round-trip delay time of identifiable data patterns traversing a plurality of points in a communication network by monitoring identifiable data patterns traversing said network during in-service operation, said apparatus comprising:

first probe means, coupled to communication lines of said communication network and situated at a first point, for receiving identifiable data patterns representing information transmitted on said network, said first probe means comprising;

first time stamp means for generating a first probe time stamp representing a time at which each identifiable data pattern is received by said first probe means;

first identifier means for generating a pattern identifier for said each received identifiable data pattern based on data in said each identifiable data pattern; and

first buffer means for storing said first probe time stamps and said pattern identifier for each identifiable data pattern received at said first probe means;

second probe means, coupled to said communication lines and situated at a second point, for receiving identifiable data patterns representing information transmitted on said network, said second probe means comprising;

second time stamp means for generating a second probe time stamp representing a time at which each identifiable data pattern is received by said second probe means;

second identifier means for generating a pattern identifier for said each identifiable data pattern received by said second probe means and based on data in that identifiable data pattern; and

second buffer means for storing said second probe time stamps and said pattern identifiers for each identifiable data pattern received at said second probe means;

analysis means for analyzing data in said first and second buffer means and generating an analysis result; and

result means for determining from said analysis result a round-trip delay time for an identifiable data pattern traversing said first and second points;

wherein said first and second probe means, said analysis means and said result means collectively determine said round-trip delay time while said communication system is in-service processing identifiable data patterns during normal operating conditions.

2. The apparatus of claim 1 wherein said identifiable data pattern comprises a data packet.

3. The apparatus of claim 1 wherein said first and second identifier means comprise means for manipulating specified bits in received identifiable data patterns in a predetermined manner to derive said pattern identifiers.

4. The apparatus of claim 1 wherein said analysis means comprises means for comparing said pattern identifiers stored in said first buffer means to said pattern identifiers stored in said second buffer means to detect sequences of corresponding identifiable data patterns and their associated time stamps.

5. The apparatus of claim 4 wherein said result means comprises arithmetic means for mathematically combining said associated time stamps to calculate said round-trip delay time.

6. The apparatus of claim 5 wherein said arithmetic means comprises means for mathematically combining said time stamps of said associated time stamp pairs according to a relationship:

space="preserve" listing-type="equation">r=T.sub.2 -T.sub.1 -T.sub.3 +T.sub.4

where r is said round-trip delay time, T₁ is a time stamp for each identifiable data pattern received at said first point from a first transmission direction, T₂ is a time stamp for said each identifiable data pattern received at said second point from said first transmission direction, T₃ is a time stamp for each identifiable data pattern received at said second point from a second transmission direction, and T₄ is a time stamp for each identifiable data pattern received at said first point from said second transmission direction.

7. In a data communication network, a method for measuring transmission delay time of identifiable data patterns traversing the network past first and second monitor points, said method comprising the steps of:

(a) receiving identifiable data patterns at said first and second monitor points during in-service operation, of said communication system;

(b) generating a time stamp for each received identifiable data patterns signifying a time of reception of that identifiable data pattern;

(c) generating pattern identifiers from respective data in said received identifiable data patterns;

(d) storing said time stamps and pattern identifiers for each received identifiable data pattern;

(e) comparing said stored pattern identifiers and indicating a match when the same identifier is found to have been generated for an identifiable data pattern received at both said first and second monitor points; and

(f) determining the time difference between time stamps for each matched identifier;

wherein said steps (a)-(f) collectively determine the transmission delay time between said first and second monitor points while said communication system is in-service processing said identifiable data patterns during normal operating conditions.

8. The method of claim 7 further comprising the step of:

(g) determining the round-trip transmission delay time between said first and second monitor points by adding;

(i) the time difference determined in step (f) for at least one identifiable data pattern received at said first monitor point earlier than at said second monitor point, to

(ii) the time difference determined in step (f) for at least another identifiable data pattern received at said second monitor point earlier than at said first monitor point.

9. The method of claim 7 further comprising the steps of:

(g) locating from said matches a predetermined plurality of identifiable data patterns received at said first monitor point earlier than at said second monitor point;

(h) for the plurality of data points located in step (g), computing an average of the time differences determined in step (f);

(i) locating from said matches a predetermined plurality of identifiable data patterns received at said second monitor point earlier than at said first monitor point;

(j) for the plurality of data points located in step (i), computing an average of the time differences determined in step (f); and

(k) determining the round-trip transmission delay between said first and second monitor points by adding the average computed in step (h) to the average computed in step (j).

10. The method of claim 7 wherein said identifiable data pattern comprises a data packet.

11. The method of claim 7 wherein said step (e) comprises matching said pattern identifiers generated at said first monitor point and stored in a first buffer to said pattern identifiers generated at said second monitor point and stored in a second buffer to form sequences of associated time stamp pairs.

12. The method of claim 11 wherein said step (f) comprises mathematically combining time stamps of said associated time stamp pairs to calculate the round-trip transmission delay time between said monitor points.

13. The method of claim 12 wherein said step (f) comprises combining said time stamps of said associated time stamp pairs according to a relationship:

space="preserve" listing-type="equation">r=T.sub.2 -T.sub.1 -T.sub.3 +T.sub.4

where r is said round-trip delay time, T₁ is a time stamp for each identifiable data pattern received at said first monitor point from a first transmission direction, T₂ is a time stamp for said each identifiable data pattern received at said second point from said first transmission direction, T₃ is a time stamp for each identifiable data pattern received at said second point from a second transmission direction, and T₄ is a time stamp for each identifiable data pattern received at said first point from said second transmission direction.

14. In an identifiable data pattern transmission network of the type wherein information is transmitted in the form of a series of identifiable digital data patterns between two or more spaced locations, apparatus for measuring transmission delay between first and second monitor points in said network using the data patterns transmitted during on-line operation of the network without requiring special test signals to be transmitted on the network or that the network be taken out of service to perform measurements, said apparatus comprising:

first and second probes connected to said network at said first and second monitor points, respectively, for receiving said data patterns as they are transmitted past said first and second monitor points;

wherein each probe includes;

time stamp means for generating a time stamp for each received data pattern representing a time at which that data pattern is received;

identifier means responsive to each received data pattern for generating an identifier code derived as a function of specified bits in said data pattern to uniquely identify said each received data pattern; and

a first storage buffer for storing in sequence the time stamp and identifier for data patterns received in said sequence from a first direction along said network;

first comparator means for comparing data pattern identifiers stored in said first storage buffer of said first probe with data pattern identifiers stored in said first storage buffer of said second probe to locate a first direction match signifying the same identifier stored in both probes; and

first computing means responsive to each first direction match located by said comparator means for computing a first direction difference between times represented by the time stamps for the matched identifiers, wherein said first direction difference is a measure of transmission delay in said first direction between said monitor points of the data pattern identified by the identifier of said each first direction match.

15. The apparatus of claim 14 wherein said identifiable digital data pattern comprises a data packet.

16. The apparatus of claim 14 wherein said computing means includes means for computing an average of said first direction differences computed in response to a plurality of said located first direction matches, wherein said average of said first direction differences constitutes a measure of the transmission delay time through said network in said first direction between said monitor points.

17. The apparatus of claim 16 further comprising:

a second storage buffer for storing the time stamp and identifier for data patterns received in sequence from a second direction opposite said first direction along said network;

second comparator means for comparing data pattern identifiers stored in said second storage buffer of said first probe with data pattern identifiers stored in said second storage buffer of said second probe to locate a second direction match signifying the same identifier stored in both probes; and

second computing means responsive to each second direction match located by said comparator means for computing a second direction difference between times represented by the time stamps for the matched identifiers, wherein said second direction difference is a measure of transmission delay in said second direction between said monitor points of the data packet identified by the identifier of said second direction match.

18. The apparatus of claim 17 wherein said second computing means includes means for computing an average of said second direction differences computed in response to a plurality of said located second direction matches, wherein said average of said second direction differences constitutes a measure of the transmission delay time through said network in said second direction between said monitor points.

19. The apparatus of claim 18 further comprising summing means for adding the average of said first direction differences to the average of said second direction differences to provide a measure of the round-trip transmission delay between monitor points through said network.

20. The apparatus of claim 19 wherein said time stamp means at each probe comprises a source of clock pulses and a counter connected to count said clock pulses, wherein the repetition rate of said clock pulses from said source is substantially identical at each probe, and wherein said sources of clock pulses at said first and second probes are not synchronized in phase to one another.

21. The method of measuring round-trip transmission delay between first and second monitor points in an identifiable data pattern transmission network using identifiable data patterns transmitted during on-line operation of the network, and without requiring special test signals to be transmitted on the network or that the network be taken out of service to perform the measurements, said method comprising the steps of:

(a) measuring the delay between reception of at least one of said identifiable data pattern in the direction from said first monitor point to said second monitor point;

(b) measuring the delay between reception of at least another of said identifiable data patterns in a direction from said second monitor point to said first monitor point; and

(c) adding the delays measured in steps (a) and (b).

22. The method of claim 21 wherein step (a) includes the steps of:

(a.1) detecting that said at least one identifiable data pattern has been received at both said first and second monitor points;

(a.2) determining times of reception of said at least one identifiable data pattern at said first and second monitor points, respectively; and

(a.3) subtracting said times of reception, one from the other, as a measure of delay; and

wherein step (b) includes the steps of;

(b.1) detecting that said another identifiable data pattern has been received at both said first and second monitor points;

(b.2) determining times of reception of said another identifiable data pattern at said first and second monitor points, respectively; and

(b.3) subtracting said times of reception determined in step (b.2), one from the other, as a measure of said round-trip transmission delay.

23. The method of claim 21 wherein (a) includes the step of:

(a.4) measuring the delays between reception of a predetermined plurality of said identifiable data patterns in the direction from said first to said second monitor points, and computing an average value of those delays;

wherein step (b) further includes the step of;

(b.4) measuring the delays between reception of a predetermined plurality of said identifiable data patterns in a direction from said second to said first monitor points, and computing an average value of those delays; and

wherein step (c) includes the step of adding the average values computed in steps (a.4) and (b.4).

24. The method of claim 21 wherein said identifiable data pattern comprises a data packet.