Method, a computer program product, and a carrier for indicating one-way latency in a data network

Abstract

Disclosed herein is a method, a computer program product, and a carrier for indicating one-way latency in a data network (N) between a first node (A) and a second node (B), wherein the data network (N) lacks continuous clock synchronization, comprising: a pre-synchronization step. A measuring step, a post-synchronisation step, an interpolation step, and generating a latency profile. The present invention also relates to a computer program product incorporating the method, a carrier comprising the computer program product, and a method for indicating server functionality based on the first aspect.

Claims

1. A system to determine a one-way latency between a first node and a second node in a network, comprising: a plurality of first sync messages comprising a first timestamp transmitted from the first node at a first time to the second node; a second sync message sent by said second node in response to receiving said first sync message at a second time, said second sync message comprising, said first timestamp, a second timestamp representing said second time and a third timestamp representing a third time at which said second sync message is transmitted from the second node to the first node; one or more sync values calculated upon reception of said second sync message at said first node at a fourth time, said sync values calculated based on said first timestamp, said second timestamp, said third timestamp and said fourth time; a plurality of measurement messages comprising a fifth time stamp representing a fifth time at which said measurement message is sent from the first to the second node; a memory for storing said fifth timestamp upon reception of said measurement message at said second node and for storing a sixth time at which said measurement message is received at said second node; and a one-way latency profile calculated based on a combination of the fifth and sixth timestamps and the one or more sync values.

2. The system of claim 1 further comprising: a first clock, wherein the first clock determines the first time, the fourth time and the fifth time; and a second clock, wherein the second clock determines the second time, the fourth time and the sixth time.

3. The system of claim 2 wherein the first clock and the second clock are not synchronized.

4. A method for determining a one-way latency between a first and a second nodes in a network, the method comprising: sending from the first node a plurality of first sync messages comprising a first timestamp representing a first time at which said first sync message is transmitted from the first node to the second node; sending from the second node a second sync message in response to receiving said first sync message at a second time, said second sync message comprising, said first timestamp, a second timestamp representing said second time and a third timestamp representing a third time at which said second sync message is transmitted from the second node to the first node; calculating one or more sync values upon reception of said second sync message at said first node at a fourth time, said sync values calculated based on said first timestamp, said second timestamp, said third timestamp and said fourth time; sending from said first node a plurality of measurement messages comprising a fifth time stamp representing a fifth time at which said measurement message is sent from the first to the second node; storing said fifth timestamp upon reception of said measurement message at said second node and storing a sixth time at which said measurement message is received at said second node; and calculating a one-way latency profile based on a combination of the fifth and sixth timestamps and the one or more sync values.

5. The method of claim 4 further comprising: determining the first value and the second value using a first clock; and determining the third value and the fourth value using a second clock.

6. The method of claim 4 wherein the first clock and the second clock are not synchronized.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) In FIG. 1, an embodiment of two nodes, A and B, interconnected by a network N are schematically depicted.

(2) In FIG. 2, an embodiment of an architecture of a node is schematically depicted.

(3) In FIG. 3, an embodiment of a network module is schematically depicted.

(4) In FIG. 4, an embodiment of a requestor node pre-synchronization flowchart is schematically depicted.

(5) In FIG. 5, an embodiment of a responder node pre-synchronization flowchart is schematically depicted.

(6) In FIG. 6, an embodiment of a flowchart of requesting node in the measurement phase is schematically depicted.

(7) In FIG. 7, an embodiment of a flowchart of the responding node in the measurement phase is schematically depicted.

(8) In FIG. 8, an embodiment of a flowchart of the interpolation method is schematically depicted.

DESCRIPTION OF PREFERRED EMBODIMENTS

(9) In a first embodiment, a system with two nodes A and B interconnected by a communication network N is depicted in FIG. 1. The nodes communicate by sending messages (packets) over the network N. A measurement is performed from a node A to a node B, where A is called a requesting node, and B is called a responding node. Each node may work both as a requesting node and a responding node. A node can also perform measurements with more than one other node. For example, A can perform a measurement with a third node C (not disclosed in FIG. 1) at the same time. The network N may be an inter-network running the IP protocol. This enables any nodes with an IP-interface and an IP protocol stack to communicate with each other over N.

(10) In FIG. 2, an embodiment of a node is shown. The computer node is equipped with a network interface card that can communicate using IP. Such a node has a CPU, memory buses, disks, etc, that enables it to operate as a computer. The node runs an operating system, in which the system software can be implemented. This embodiment is implemented as a software module running in an operating system of such a node.

(11) In FIG. 3, an embodiment of a network module is shown. The software module implementing the method described in this document needs to have access to a network module. The network module shown in FIG. 3 typically consists of a network interface card, a device driver, an IP stack and a socket API. The network interface card enables the node to physically connect to an access network. The device driver contains software enabling the IP stack to access the network services on the network interface card. The IP stack contains full implementation of the communication protocols that enables the node to communicate over the internet. This may be the set of protocols referred to as TCP/IP. The socket API is a functional interface that the system module can access in order to send and receive packets to and from the network.

(12) In an embodiment, a system module implementing the invention may be implemented as a user application in an operating system. It requires a socket API to access the network in order to send and receive packets over the network.

(13) The nodes communicate with messages over the network. There are two kinds of messages:

(14) Synchronization messages

(15) Measurement messages

(16) Both types of messages may be encapsulated over the IP protocol using the UDP/IP transport protocol or some other non-reliable datagram service. In an embodiment, both types of messages are encoded with the RTP protocol.

(17) A synchronization message is either a request (syncreq) or response (syncresp). The request message is sent by the requesting node and received by a responding node. A response is sent by a responding node when it receives a syncreq message. The syncresp message is received by the requesting node.

(18) The syncreq message contains the following fields: a sequence number and a timestamp T1.

(19) The syncresp message contains the following fields: a sequence number and three timestamps: T1, T2, and T3.

(20) The semantics of the message fields are as follows: Sequence number—The requesting node sets the sequence number incrementally (0, 1, 2, etc). The responder copies the sequence number from a syncreq to a syncresp message. The sequence number is used to detect packet loss, reordering or duplications on the network. Timestamp T1. The time when the syncreq message was sent by the requesting node. Timestamp T2. The time when the syncreq message was received by the responding node. Timestamp T3. The time the syncresp message was sent by the responding node.

(21) The measurement messages are sent from the requesting node to the responding node only. The measurement message contains a sequence field and a timestamp field T1.

(22) The semantic of the message fields are as follows: The sequence number. The requesting node sets the sequence number incrementally (0, 1, 2, etc). Timestamp T1. The time when the measurement message was sent by the requesting node.

(23) Now referring to the inventive method, both nodes have high accuracy clocks that are not synchronized with each other. High accuracy means that they are linear with respect to each other over a limited time period on the order of minutes, and that they have high resolution, at least to the level of 1 microsecond. That is, the clocks have different rates, but the rate difference is constant over time.

(24) The method is divided into five steps:

(25) P1—Synchronization1

(26) P2—Measurement

(27) P3—Synchronization2

(28) P4—Interpolation and

(29) Generating a latency profile.

(30) In Table 1 below an embodiment of constants used to parameterise the method are given. The values given to the constants are merely an example; the method can be used also for other values.

(31) TABLE-US-00001 TABLE 1 Constant Example name Description values SNR Number of syncreq messages sent. 50 NM Number of measurement messages sent. 10000 DT Delay between sending of measurement 20 ms messages.

(32) In Table 2 below, variables used in this method are explained.

(33) TABLE-US-00002 TABLE 2 Variable name Description NSREQ Number of syncreq messages sent. NSRESP Number of syncresp messages received. T1 Time when message was sent by requesting node. T2 Time when message was received by responding node. T3 Time when message was sent by responding node. T4 Time when message was received by requesting node. RTT Round-trip-time RTTMIN The smallest RTT value during a synchronization phase. CABSO Wall clock of a synchronization message in the P1 phase CDIFFO The difference/offset between the two clocks at a synchronization message in the P1 phase CABS1 Wall clock of a synchronization message in the P3 phase CDIFF2 The difference/offset between the two clocks at a synchronization message in the P3 phase SEQ Sequence number set by requesting node. A[ ] Vector containing T1 for all measurement messages. B[ ] Vector containing T2 for all measurement messages. L[ ] Vector containing the resulting one-way latencies, or the latency profile. Ks Overhead of sending a message Kr Overhead of receiving a message RATEBIAS Difference in rate between the two clocks VALID[ ] Vector of boolean value s determining the validity of the entries in A[ ], B[ ] and L[ ]

(34) The output of the present invention is a latency profile, which is the vector containing the resulting one-way latencies, or L[ ].

(35) In FIG. 4, an embodiment of a requestor node pre-synchronization flowchart is schematically depicted. The node sends a syncreq to the responding node. It sets the sequence number and the T1 timestamp in the syncreq message. Then it waits for a reply to come back from the responding node, or for a timeout to occur. If a syncreq message was received, a timestamp T4 is registered when the syncresp message was received. Together with the three timestamps T1, T2 and T3, the module tries to find the message with the smallest round-trip-time. This message is used to find the two values CABS0 and CDIFF0 and is used in the interpolation method P4. The method uses two variables NSREQ and NSRESP to record the number of sent syncreq messages and received syncresp messages, respectively. These variables are used as a terminating condition. If the module sends 2SNR syncreq messages without having received SNR syncresp messages, this is an error. As soon as the module has received SNR syncresp messages, it continues to the next phase, P2A. SNR is a predefined constant, typically 50 messages. The method may also use the variables RTT and RTT_MIN. RTT_MIN is preset to a large value, and is used to find the syncreq/syncresp pair with the smallest round-trip-time. This measurement is then used to compute the CABS and CDIFF values. In other words, we claim that the best measurement is the one with the smallest RTT. Many other methods use the mean value. Note that the method described in FIG. 4 may be implemented somewhat differently. For example, the sending and receiving of messages can be made concurrently, not sequentially as is shown in the figure. In that case, two processes are created, one that is sending syncreq messages regularly, and one that is waiting for syncresp messages. In that case, a timeout need not be made. Instead, a delay between the sending of syncreq messages need to be introduced.

(36) In FIG. 5, an embodiment of a responder node pre-synchronization flowchart is schematically depicted. The node waits for a syncreq from the requesting node. When such a message is received, it creates a syncresp message, copies the sequence number and T1 from the syncreq message, records T2 and T3, and sends the syncresp message back to the requesting node. If the received message is not a syncreq message, it is assumed that it is a measurement message which is handled in P2B. The size of the vectors is equal to the number of measurement messages sent.

(37) The measurement phase consists of the requesting node periodically sending measurement messages to the responding node. The responding node records the timestamps of the time of sending and the time of receiving the messages in two vectors A[ ] and B[ ], respectively. The size of the vectors is equal to the number of measurement messages sent, NM. The two vectors are later used in P4.

(38) In FIG. 6, an embodiment of a flowchart of requesting node in the measurement phase is schematically depicted. The requesting node sends NM messages (for example 10000) with interval DT between each packet (for example 20 ms). Each syncreq message will contain SEQ, the sequence number; and T1, the time the message was sent. The overhead of sending a message Ks is computed initially. This is the difference in time from when the timestamp was taken and when the message was actually sent. Ks may be set to 0 if the node lacks the capability to compute this time.

(39) In FIG. 7, an embodiment of a flowchart of the responding node is shown. The responding node stores the sending timestamp T1 in a vector A, and the receiving timestamp T2 in the vector B. The sequence number is used as an index in the vector. The overhead of sending a message Kr is computed initially. This is the difference in time from when the timestamp was taken and when the message was actually sent. Kr may be set to 0 if the node lacks the capability to compute this time.

(40) The second synchronisation phase is in this embodiment similar to phase P1 described above. The differences are as follows:

(41) 1. The two processes are called P3A and P3B instead of P1A and P1B, respectively.

(42) 2. The resulting variables are named CABS1 and CDIFF1 instead of CABS0 and CDIFF0, respectively.

(43) 3. After successful completion of the processes, both flowchart goes to P4 instead of to P2A and P2B.

(44) In the interpolation phase, the measurements collected in phase P2 in the vectors A[ ] and B[ ] and the synchronization values CABS0, CDIFF0, CABS1 and CDIFF1 in phases P1 and P3 are used to interpolate a sequence of one-way latency values. The method itself can be performed on the requesting node, the responding node, or some other node, and can be performed at any time after the other three phases. For example, this phase can be made as a post processing stage in a server. However, the data must be transferred to the place where the method is implemented. The end result of the method is a vector L[ ], i.e. the latency profile, with size NM containing the true one-way latency values of the measurement between the requesting and responding node.

(45) In FIG. 8, an embodiment of a flowchart of the interpolation method is schematically depicted. First the difference in rate RATEBIAS is computed as follows:
RATEBIAS=(CDIFF1−CDIFF0)/(CABS1−CABS0),

(46) The method iteratively computes the values of the one-way latency vector L[ ] from values collected or computed, as follows:
L[i]=B[i]−(A[i]+CDIFF0+RATEBIAS*(A[i]CABS0))−Ks−Kr