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

(54) Title: Method, a computer program product and a carrier for specifying one-way latency in a computer network (56) Publications cited: - (47) Summary:

Here is described 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 measurement step, a post-synchronization step, an interpolation step, and generation of a latency profile. The present invention also relates to a computer software product comprising the method, a carrier comprising the computer software product, and a method for indicating the server functionality based on the first aspect.

<img file="SE528374C2_D0001.tif" />

<img file="SE528374C2_D0002.tif" />

SUMMARY

Here is described 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 measurement step, a post-synchronization step, an interpolation step, and generation of a latency profile. The present invention also relates to a computer software product comprising the method, a carrier comprising the computer software product, and a method for indicating the server functionality based on the first aspect.

(Fig. 1)

528 574

TECHNICAL FIELD

According to a first aspect, the present invention relates to a method for indicating one-way latency in a data network without continuous clock synchronization between a first node and a second node.

In a second aspect, the present invention relates to a computer software product comprising the first aspect.

According to a third aspect, the present invention relates to a carrier comprising the computer program product.

According to a fourth aspect, the present invention relates to a method for specifying server functionality based on the first aspect.

BACKGROUND OF THE INVENTION

According to the technology, it is possible to perform real-time one-way latency measurements using synchronized clocks such as GPS technology. It is possible to use standard NTP protocols to achieve a level of synchronization between nodes, as described in Mills, D. "Network Time Protocol (Version 3) specification, implementation and analysis", IETF RFC 1305, University of Delaware, March 1992 However, the NTP mechanism does not have very high precision.

IUS2003 / 0048811 A1, entitled "Methods, systems and computer program products for synchronizing clocks of nodes on a computer network, describes an algorithm for clock synchronization between two nodes using virtual clocks, a generalization of the clock synchronization for many nodes and the use of many round-trip delays to calculate average one-way delay. One

The 52S 374 key feature of the invention described in the US document is that each node controls a virtual clock for each other node it synchronizes with.

DISCLOSURE OF THE INVENTION

According to the present invention and a first aspect, a method for specifying one-way latency in a data network without continuous clock synchronization between a first node and a second node is described. The method includes:

- a pre-synchronization step

- a measurement step

- a post-synchronization step

- an interpolation step, and

- generation of a latency profile.

Based on the present invention, there is also disclosed a computer software product that can be loaded into a computer's internal memory, comprising code portions of the software to implement the method, a carrier comprising the computer software product, and a method for indicating the server functionality. This means that the present invention can be used for measurement and monitoring, the characteristics of a server.

The present invention, in accordance with the present invention, presents a number of advantages over prior art. For example, the precision of the measurements of the present invention is higher than the precision of the NTP mechanism. The present invention relates to a method of making real-time one-way latency measurements with high precision between nodes interconnected by a message transmitting network where clock synchronization with that precision is not available, which is in contrast to the prior art briefly described above. The method can also offer individual latency values ​​per data packet. The present invention performs with high precision latency measurements of data packets that pass between two nodes for a limited period of time. Since latencies can be asymmetric, RTT calculation cannot be used but must be based on absolute and synchronous time. Continuous clock synchronization needs

528 374 thus neither installed nor maintained. Instead, the present invention makes two synchronizations (before and after) with the sole aim of interpolating the measurement results.

According to a preferred embodiment, the pre-synchronization step comprises transmitting a predetermined message from the first node to the second node. A predetermined message sent by the second node is then received at the first node. The next step is to calculate an offset according to ((T2 - Ti) + (T3 - T4)) / 2, where I) is the transmission time from the first node, T2 is the reception time at the second node, T3 is the transmission time at the second node and T4 is the receiving time at the first node. Then a clock differential is set for the offset. An absolute clock is also set for T4.

In a preferred embodiment, the presynchronization step comprises transmitting the predetermined message N times and the predetermined message is received N times. However, there may be occasions when all N messages are not received. In such cases, there will be differences in the correspondence between transmitted and received data. This can be handled by not using the measured values ​​associated with the missing messages. Then N, or a number of less than N, is generated and return time values ​​/ RTT values. This is done according to Tj, 4 - Ti, 1 - (Ty - Ty), where i is in the interval [1 ... N]. N offsets, or a number of offsets less than N, are generated as described above. The smallest RTT value is picked up and the clock difference is set to the offset that relates to the smallest RTT value, and the absolute clock is set to Ty so that you get the smallest RTT value.

According to a preferred embodiment, the method further comprises the step of measuring the redundancy to make measurements at the transmitter.

According to a preferred embodiment, the method further comprises the step of measuring the redundancy for carrying out measurements at the receiver.

According to a preferred embodiment, the measurement step comprises transmitting a predetermined message from the first node to the second node and storing

52S 374 transmission time of transmission. The predetermined message is received at the second node, the reception time of the reception is stored.

In a preferred embodiment, the measurement step comprises chronologically equidistant transmission of a predetermined message from the first node to the second node N times, and the transmission time for each transmission is stored. The predetermined message is received at the second node, the reception time for each reception is stored. Hopefully the message is received N times at the other node. Otherwise, this can be handled as described above.

In a preferred embodiment, the post-synchronization step is the pre-synchronization step as defined above.

In a preferred embodiment, the interpolation step comprises calculating the one-way latency in the data network between a first node and a second node under the following conditions:

velocity difference - (post-synchronization step offset - presynchronization step offset) / (absolute post-sync step 20 absolute presynchronization clock), and latency = the time at which the second node received the predetermined message - (the time at which the first node sent the predetermined message + the presynchronization step offset + (the time at which the first node sent the predetermined message - the absolute bell for the predetermined message) )) -.

In a preferred embodiment, the interpolation step comprises calculating the one-way latency in the data network between a first node and a second node as above for messages transmitted between the first and second nodes.

528 374

In a preferred embodiment, the method further comprises a redundancy time corresponding to the redundancy for making measurements at at least one of the first and second nodes, and the one-way latency in the data network between a first node and a second node is calculated as follows:

latency = the time at which the second node received the predetermined message - (the time at which the first node sent the predetermined message + the offset of the presynchronization step + the rate difference (the time at which the first node sent the predetermined message - the absolute message) the pre-synchronization step)) - the redundancy time.

According to a preferred embodiment, in the interpolation step, the one-way latency in the data network is calculated between a first node and a second node as above for N messages sent between the first and second nodes. In the event that not all N messages are received, this is alternatively done for the received messages.

It is also within the scope of the present invention that it is possible to operate in relation to more than one node. Of course, the present invention can be used to work against a plurality of nodes.

BRIEF DESCRIPTION OF THE DRAWINGS

Fig. 1 shows schematically an embodiment with two nodes, A and B, connected via a network N.

Fig. 2 shows schematically an embodiment of a node structure.

Fig. 3 shows schematically an embodiment of network module.

Fig. 4 is a schematic representation of a flowchart for pre-synchronizing a client note.

Fig. 5 is a schematic representation of a flow diagram for presynchronizing a response node.

Fig. 6 is a schematic representation of a flowchart for the requesting node / client node in the measurement phase.

In Fig. 7, a flow diagram of the responding node / response node is shown schematically in the measurement phase.

Fig. 8 is a schematic representation of a flow diagram of the interpolation method.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

According to a first embodiment, Fig. 1 shows a system with two nodes A and B interconnected by a communication network N. The nodes communicate by transmitting messages (packets) over the network N. A measurement is carried out from a node A to a node B, whereby A is called client node and B is called response node. Each node can work both as client node and response node. A node can also perform measurements with more than one other node. For example, A can simultaneously perform a measurement with a third node C (not shown in Fig. 1). The network N can be an internal network running the IP protocol. This allows vaqe nodes in an IP interface and an IP protocol stack to communicate with each other via N.

In Fig. 2 an embodiment of a node is shown. The computer mode is equipped with a network card that can communicate using IP. Such a node has a CPU, memory buses, disks etc. which allows it to work 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 operating in an operating system for such a node.

Fig. 3 shows an embodiment of a network module. The software module that implements the method described in this document needs access to a network module. The network module shown in Fig. 3 usually consists of a network interface card, a controller, an IP stack and a socket API. The network card allows the node to physically connect to an access network. The controller contains software that provides IP stack access to network services on the network card. The IP stack contains full implementation of the communication protocol that enables the node to communicate over the Internet. This can be a set of protocols referred to as TCP / IP. The socket API is a functional interface that the system module can access to send and receive packets to and from the network.

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

The nodes communicate with messages over the network. There are two types of messages:

• Synchronization messages • Measurement messages

Both types of message can be encapsulated via the IP protocol using the UDP / IP transport protocol or some other unreliable datagram service. In one embodiment, both types of message are encoded with the RTP protocol.

A synchronization message is either a request (sync request) or a response (sync response). The request message is sent by the client node and received by a response node. A response is sent by a reply node when it receives a sync request message. The sync response message is received by the client node.

The sync request message contains the following fields: a sequence number and a time stamp T1.

The sync response message contains the following fields: a sequence number and three timestamps: T1, T2 and T3.

The semantics of the message fields are as follows:

• Sequence Number - The client node sets the sequence number incrementally (0.1,2 etc.). The respondent copies the sequence number from a sync request to a sync response message. The sequence number is used to detect packet loss, reorder or duplicate on the network.

528 374 • Timing TI. The time when the sync request message is sent by the client node.

• Timing T2. The time when the sync request message was received by the reply node.

• Timing T3. The time when the sync response message is sent by the reply node.

The measurement messages are sent only from the client node to the response node.

The measurement messages contain a sequence field and a time marking field T1. The semantics of the message fields are as follows:

• The sequence number. The client node sets the sequence number incrementally (0.1,2 etc.).

• Timing T1. The time when the measurement message is sent by the client node.

With reference to the method according to the invention, both nodes have high precision clocks that are not synchronized with each other. High precision means that they are linear relative to each other for a limited period of time in minutes and that they have high resolution, at least up to 1 microsecond. This means that the clocks have different speeds but the speed difference is constant over time.

The method is divided into five steps:

• P1 - Synchronization 1 • P2 - Measurement • P3 - Synchronization 2 • P4 - Interpolation, and • Generation of a latency profile.

Table 1 below gives a design of constants used to parameterize the method. The values ​​given for the constants are just one example; the method can also be used for other values.

<img file="SE528374C2_D0003.tif" />

rn $ f

Table 1

<td>constant Name</td><td>Description</td><td>example values</td>

<td>SNR</td><td>Number of sync request sent messages</td><td> 50</td>

<td>NM</td><td>Number of sent measurement messages</td><td> 10000</td>

<td>DT</td><td>Delay between transmission of measurement messages</td><td>20 ms</td>

Table 2 below explains variables used in this method. Table 2

<td>variable Name</td><td>Description</td>

<td>NSREQ</td><td>Number of sync request sent messages</td>

<td>NSRESP</td><td>Number of received sync response messages</td>

<td>TI</td><td>Time when message was sent by client node.</td>

<td>T2</td><td>Time when message was received by reply node.</td>

<td>T3</td><td>Time when message was sent by reply node.</td>

<td>T4</td><td>Time when message was received by client node.</td>

<td>RTT</td><td>Return and return time</td>

<td>RTTMIN</td><td>The minimum RTT value during a synchronization phase</td>

<td>CABSO</td><td>Wall clock for a synchronization message in the P1 phase.</td>

<td>CDIFFO</td><td>Difference / displacement between the two clocks at one synchronization message in the P1 phase.</td>

<td>CABS1</td><td>Wall clock for a synchronization message in the P3 phase.</td>

<td>CDIFF2</td><td>Difference / displacement between the two clocks at one synchronization message in the P3 phase.</td>

<td>SEQ</td><td>Sequence number set by client node.</td>

<td>A []</td><td>Vector containing TI for all measurement messages.</td>

<td>B []</td><td>Vector containing T2 for all measurement messages.</td>

<td>L []</td><td>Vector containing the resulting one-way latencies or latency profile.</td>

<td>Ks</td><td>Redundancy for sending a message</td>

<td>kr</td><td>Redundancy for receiving a message</td>

<img file="SE528374C2_D0004.tif" />

RATE BIAS

VALID []

Difference in speed between the two clocks

Vector for boolean values ​​that determine the validity of the inputs of A [], B [] and L []

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

Fig. 4 is a schematic representation of a flowchart for pre-synchronizing a client note. The node sends a sync request to the response node. It sets the sequence number and the T1 time tag in the sync request message. It then waits for a response to come back from the answer node or for a timeout to occur. If a sync request message is received, a timestamp T4 is recorded when the sync response message is received. Together with the three time markers T1, T2, T3, the module attempts to find the message with the smallest RTT value. This message is used to find the two values ​​CABSO and CDIFFO and is used in the interpolation method P4. The method uses two variables NSREQ and NSRESP to record the number of sent sync request messages and received sync response messages, respectively. These variables are used as a final condition. If the module sends 2SNR sync request messages without receiving SNR sync response message, then this is an error. As soon as the module receives SNR sync response messages, it proceeds to the next phase, P2A. SNR is a predefined constant, usually 50 messages. The method can also use the variables RTT and RTT_MIN. RTT_MIN is set to a large value in advance and is used to find the sync request / sync response with the smallest RTT value. This measurement is then used to calculate the CABS and CDIFF values. In other words, we argue that the best measurement is the one with the smallest RTT. Many other methods use the mean. Note that the method described in Fig. 4 can be implemented somewhat differently. For example, sending and receiving messages can be done simultaneously, not sequentially as shown in the figure. In that case, two processes are created, one that sends sync request messages regularly and one that waits for sync response messages. In that case, no timeout need be made. Instead, a delay between sending sync request messages must be introduced.

yes

a. / ·, 7

Μ / * Τ

Fig. 5 is a schematic representation of a flow diagram for presynchronizing a response node. The node is waiting for a sync request from the client node. When such a message is received, it creates a sync response message, copies the sequence number and T1 from the sync request message, records T2 and T3, and sends the sync response message back to the client node. If the received message is not a sync request message, it is assumed to be a measurement message handled in P2B. The size of the vectors is equal to the number of sent measurement messages.

The measurement phase consists of the client node periodically sending measurement messages to the response node. The reply node records the time marks for the time of transmission and the time for receiving messages in two vectors A [] and B [], respectively. The size of the vectors is equal to the number of sent measurement messages, NM. Both vectors are later used in P4.

Fig. 6 is a schematic representation of a flowchart of the client node in the measurement phase. The client node sends NM messages (eg 10,000) at intervals DT between each packet (eg 20 ms). Each sync request message will contain SEQ, sequence number, and T1, at the time the message is sent. The redundancy for sending a message Ks is initially calculated. This is the difference in time from when the time tag was taken and when the message was actually sent. Ks can be set to 0 if the node is unable to calculate this time.

Fig. 7 shows a design of a flow diagram for the response node. The response node stores the sending time tag T1 in a vector A and the receiving time tag T2 in the vector B. The sequence number is used as an index in the vector. The redundancy for sending a message Kr is initially calculated. This is the difference in time from when the time tag was taken and when the message was actually sent. Kr can be set to 0, if the node is unable to calculate this time.

The second synchronization phase in this embodiment is equal to phase P1 as described above. The differences are as follows:

528 374

1st Both processes are called P3A and P3B instead of PIA and P1B, respectively.

2nd The resulting variables are called CABS1 and CDIFF1 instead of CABSO and CDIFFO, respectively.

3rd After successfully completing the processes, both flow charts go to P4 instead of P2A and P2B.

In the interpolation phase, the measurements collected in phase P2 in vectors A [] and B [] as well as the synchronization values ​​CABSO, CDIFFO, CABS1 and CDIFF1 in phases P1 and P3 are used to interpolate a sequence of one-way latency values. This method can itself be performed on the client node, the response node or any other node and can be performed at any time after the other three phases. For example, this phase can be made as a step after processing in a server. However, the data must be transferred to the location where the method is implemented. The end result for this method is a vector L [], ie the latency profile, of the size NM containing the actual one-way latency values ​​for the measurement between the client and response nodes.

Fig. 8 is a schematic representation of a flow diagram of the interpolation method. First, the differences in rate RATEBIAS are calculated as follows:

RATEBIAS = (CDIFF1 - CDIFFO) / (CABS1 - CABSO),

The method repeatedly calculates the values ​​of the one-way latency vector L [] from aggregated or calculated values ​​as follows:

L [i] = B [i] - (A [i] + CDIFFO + RATEBIAS * (A [i] - CABSO)) - Ks - Kr; 328 374