Method and apparatus for measuring one-way delay at arbitrary points in network

• US 7,519,006 B1
• Filed: 03/09/2004
• Issued: 04/14/2009
• Est. Priority Date: 11/26/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Wing, Daniel G.
• Primary Examiner(s): Ngo; Ricky
• Assistant Examiner(s): Yuen; Kan
• Application Number:
  US10/797,520
• Time in Patent Office: 1,862 Days
• Field of Search: 370/241, 370/248, 370/249, 370/251, 370/253, 370/254, 370/352, 370/252
• US Class Current: 370/252
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 43/106 using time related information in packets, e.g. by adding timestamps
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/65 Network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP]
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 65/80 Responding to QoS

Abstract

Timestamps are inserted into trace packet expiration messages to identify delay in a network. A Time To Live (TTL) value in the trace packet is varied to intentionally cause an intermediate node in the network to discard the trace packet and send back the packet expiration message. The intermediate node sending the packet expiration message inserts a time value in the message indicating when the intermediate node received the trace packet. The time value is then used to determine the time required for the trace packet to reach the intermediate node.

Claims

1. A network processing device, comprising:

circuitry configured to decrement time to live values of received traffic prior to routing the traffic;

the circuitry configured to analyze the time to live values to identify those time to live values that are decremented below a predefined threshold;

if one of the decremented values are identified as being below the predefined threshold, the circuitry configured to extract from a corresponding packet of the traffic a timestamp inserted by a source endpoint, wherein the timestamp indicates when the corresponding packet was transmitted from the source endpoint;

the circuitry configured to identify a receipt time for the corresponding packet, the receipt time indicating when the corresponding packet was received at the network processing device;

the circuitry configured to determine a difference between the extracted timestamp and the identified receipt time; and

the circuitry configured to piggyback the determined difference in an unused field of a packet expiration notice that is generated for expired packets, the packet expiration notice corresponding to the expired packet, wherein the network processing device utilizes the packet expiration notice for communicating the determined difference back to an originating source of the corresponding packet.

2. The network processing device of claim 1, wherein the receipt time is generated using a same reference clock used to generate the inserted timestamp.

3. The network processing device of claim 1, wherein the circuitry is further configured to:

identify a predefined portion of the corresponding packet as containing trace route information;

extract the trace route information from the identified packet portion; and

append the extracted trace route information to the packet expiration notice to allow the source endpoint to correlate the determined difference with the corresponding packet.

4. The network processing device of claim 1, wherein the unused field is at least one selected from a group including a Destination Unreachable Message field, a Time Exceeded Message field, and a Source Quench Message field.

5. The network processing device of claim of claim 1, wherein the circuitry is further configured to:

generate a reporting packet that is different than the packet expiration notice, the reporting packet containing the determined difference; and

transmit the reporting packet to an endpoint other than the source endpoint.

6. An apparatus, comprising:

circuitry configured to generate packets having monotonically increasing values to trace a route through a network;

the circuitry configured to insert into each of the packets timestamps indicating a corresponding transmission time, and to transmit the packets having the timestamps;

the circuitry configured to receive back a packet expiration notice, wherein the packet expiration notice contains appended thereto a portion of data copied from a corresponding one of the transmitted packets, wherein the copied data portion includes information extracted from a trace packet payload or a trace packet header and is usable for correlating the packet expiration notice with the corresponding transmitted packet, and wherein the circuitry is configured to correlate the packet expiration notice to one of the transmitted packets according to the copied correlating data; and

the circuitry configured to extract a determined time difference from the packet expiration notice, the determined time difference based on one of the timestamps, wherein the determined difference represents a one way trip time used by the correlated transmitted packet to travel from the apparatus to an intermediary node that generated the packet expiration notice;

wherein the circuitry is further configured to extract the determined time difference from a predefined field of the packet expiration notice, wherein the predefined field is at least one selected from a group including a Destination Unreachable Message field, a Time Exceeded Message field, and a Source Quench Message field.

7. An apparatus, comprising:

circuitry configured to generate packets having monotonically increasing values to trace a route through a network, to address the packets to a common destination, and to transmit the generated packets;

the circuitry configured to locally store information indicating a time that each packet is transmitted, wherein the locally stored information is generated using a time reference;

the circuitry configured to receive back a packet expiration notice, wherein the packet expiration notice contains appended thereto a portion of data copied from a corresponding one of the transmitted packets, wherein the copied data portion includes information extracted from a trace packet payload or a trace packet header and is usable for correlating the packet expiration notice with the corresponding transmitted packet, and wherein the circuitry is configured to correlate the packet expiration notice to one of the locally stored transmission time information according to the appended correlating data; and

the circuitry configured to extract a receive time value from the packet expiration notice, wherein the receive time value is generated using the same time reference used to generate the locally stored information, wherein the receive time value indicates a time that an intermediary node received a corresponding one of the packets relative to the correlated transmission time information;

wherein the circuitry is configured to determine a difference between the extracted receive time value and the correlated transmission time information to identify a one way travel time for the corresponding packet to travel from the apparatus to the intermediary node.

8. The apparatus of claim 7, wherein the circuitry is further configured to upload the determined time difference to a remote device.

9. The apparatus of claim 8, wherein the circuitry is further configured to extract the receive time value from a predefined field of the packet expiration notice, wherein the predefined field is at least one selected from the group including a Destination Unreachable Message field, a Time Exceeded Message field, and a Source Quench Message field.