System for establishing and maintaining a clock reference indicating one-way latency in a data network

Abstract

A method for indicating one-way latency in a data network, with continuous clock synchronization, between first and second node having clocks that are not synchronized with each other includes a continuous synchronization session and a measurement session. The method repetitively sends predetermined synchronization messages from the first node to the second node and from the second node to the first node, calculates a round trip time for each message at the first node, updates a synchronization point if the calculated round trip time is smaller than a previously calculated round trip time, stores the updated synchronization points of a synchronization window, and calculates a virtual clock from the updated synchronization points of the synchronization window. The measurement session collects multiple measurements of one-way latency between the first and second nodes using the virtual clock, and generates a latency profile by interpolating the multiple measurements.

Claims

1. A method of adapting to clock offsets in a network, the method comprising: establishing a plurality of virtual clocks at a responding node, each of the plurality of virtual clocks associated with one of a plurality of requesting nodes; transmitting a plurality of synchronization requests from the responding node to each of the plurality of requesting nodes; responding to each of the plurality of synchronization requests received by each of the plurality of requesting nodes by transmitting a synchronization response back to the responding node; for each of the plurality of synchronization responses received by the responding node, calculating a plurality of round trip delay measurements at the responding node, utilizing the plurality of round trip delay measurements to produce a plurality of synchronization points for each of the plurality of requesting nodes; and and utilizing the round trip delay to determine a latency profile for each of the plurality of requesting nodes.

2. The method of claim 1 wherein each of the plurality of synchronization points associated with each of the plurality of requesting nodes is produced using the minimum of the plurality of round trip delay measurements between the responding node and the associated one of the plurality of requesting nodes.

3. The method of claim 1 wherein the plurality of synchronization points are periodically updated using an additional plurality of round trip delay measurements.

4. The method of claim 1 wherein the number of the plurality of synchronization requests is predetermined.

5. The method of claim 1 wherein the plurality of synchronization points is produced by calculating a sum of least-squared method.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The invention may best be understood by reference to the following description taken in conjunction with the accompanying drawings.

(2) FIG. 1 depicts two nodes interconnected by a network and the various components and sessions involved.

(3) FIG. 2 depicts more details for a synchronization session between two nodes.

(4) FIG. 3 shows the makeup of synchronization bursts and synchronization windows.

(5) FIG. 4 a network module is schematically depicted.

(6) FIG. 5 shows possible programmable data structures for the system.

(7) FIG. 6 is a synchronization session flowchart for the measurement responding node in a 1-way measurement session.

(8) FIG. 7 shows the handling of a new Synchronization Point for a new synchronization window.

(9) FIG. 8 depicts the calculation of a new virtual clock.

(10) FIG. 9 depicts more details for a measurement session between two nodes.

(11) FIG. 10 is a flowchart of the measurement requesting node in the measurement phase.

(12) FIG. 11 is of a flowchart of the measurement responding node in the measurement phase.

(13) FIG. 12 is a flowchart of the measurement responding node in the interpolation phase.

DETAILED DESCRIPTION OF ILLUSTRATED EMBODIMENTS

(14) Although the invention will be described in connection with certain preferred embodiments, it will be understood that the invention is not limited to those particular embodiments. On the contrary, the invention is intended to cover all alternatives, modifications, and equivalent arrangements as may be included within the spirit and scope of the invention as defined by the appended claims.

(15) A method for indicating one-way latency in a data network, with continuous clock synchronization between a first node and a second node is disclosed. The method comprises the exchange of clock synchronization information between a pair of network nodes via a synchronization session. This synchronization session sends synchronization messages at regular intervals and is separate from other management, measurement or user traffic. Synchronization messages do not need to use the same path as other traffic between the pair of nodes. The network node is equipped with a network interface card that can communicate using the Internet Protocol (IP). Such a node has a CPU, memory buses, disks, etc, that enable 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.

(16) FIG. 1 depicts a system with a measurement requesting node 102 and a measurement responding node 100, interconnected by a communication network 101. The nodes 100, 102 communicate by sending messages (packets) over the network 101. A software module 107 is used to implement the embodiment in the measurement requesting node 102, and another software module 108 is used to implement the embodiment in the measurement responding node 100. A measurement is performed from a measurement requesting node 102 to a measurement responding node 100. A measurement requesting node 102 can also perform measurements with more than one other node at the same time. The network 101 may be LAN (Local Area Network) or WAN (Wide Area Network) running the IP protocol. This enables any nodes 100, 102 with an IP-interface and an IP protocol stack to communicate with each other over the network 101.

(17) The nodes 100, 102 communicate with messages over the network 101. There are two kinds of messages: Synchronization messages Measurement messages

(18) Both types of messages may be encapsulated over the IP protocol using the UDP/IP transport protocol or another datagram service. In an embodiment, both types of messages are encoded with the RTP protocol.

(19) Measurement sessions 103 use a synchronized virtual clock 104 by measurement responding node 100 to timestamp the measurement packets received from measurement requesting node 102. The virtual clock 104 between the two nodes needs to be established and maintained by the measurement responding node 100 of a measurement session. A measurement responding node 100 will maintain a separate virtual clock for each measurement requesting node 102.

(20) A synchronization session 106 comprises sending a number of times a predetermined message sequence from the measurement responding node 100 to the measurement requesting node 102 which then sends a response message back to the measurement responding node 100.

(21) FIG. 2 is a more detailed description of the synchronization session 106. Both nodes 100, 102 have high accuracy clocks 201, 200 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.

(22) A synchronization message is either a synch request 202 or synch response 203. The synch request 202 is sent by the measurement responding node 100 and received by a measurement requesting node 102. A synch response 203 is sent by a measurement requesting node 102 in response to a synch request 202. The synch response 203 is received by the measurement responding node 100.

(23) The synch request 202 message contains the following fields: a sequence number and a time-stamp T1 204.

(24) The synch response 203 contains the following fields: a sequence number and three timestamps: T1 204, T2 205, and T3 206. The semantics of the message fields are as follows:

(25) Sequence number—The measurement responding node 100 sets the sequence number incrementally (for example: 0, 1, 2, etc). The measurement requesting node 102 copies the sequence number from a synch request 202 to the synch response 203. The sequence number is used by the nodes 100, 102 to detect packet loss, reordering or duplication on the network.

(26) Timestamp T1 204. The time when the synch request 202 was sent by the measurement responding node 100.

(27) Timestamp T2 205. The time when the synch request 202 was received by the measurement requesting node 102.

(28) Timestamp T3 206. The time the synch response 203 was sent by the measurement requesting node 102.

(29) The next step is for the measurement responding node 100 to calculate an offset item 208 according to ((T2−T1)+(T3−T4))/2, where T1 204 is the sending time of the synch request 202 from the measurement responding node 100, T2 205 is the receiving time of the synch request 202 at the measurement requesting node 102, T3 206 is the sending time of the synch response 203 at the measurement requesting node 102, and T4 207 is the receiving time of the synch response 203 at the measurement responding node 100. The time T4 207 is set to the current time of the high accuracy clock 200.

(30) FIG. 3 details how the offset for virtual clock 104 is set. The synchronization session 106 comprises sending at regular intervals the synch request 202 and synch response 203 in bursts of N messages 300. However, there may be cases where not all of the N messages in a burst 300 are received. In such cases, there will be gaps in the correspondence of the data sent and received. This may be handled by not using the measured values associated to the missing messages. Then N or a number less than N, round-trip-time times 305 are generated. This is done according to T.sub.i4−T.sub.i1−(T.sub.i3−T.sub.i2), where i is in the interval [1 . . . N]. N offset items 208, or a number of offset items 208 less than N, as described above are generated. The offset item 208 with the minimum round-trip-time 305 is retrieved and is used as the next synchronization point 301 in the synchronization window 302.

(31) Once the synchronization window 302 includes a minimum number of synchronization points 301, 304 (experimentation indicates that 4 entries are a good minimum number of entries), the offset for the virtual clock 104 for the measurement responding node 100 can be calculated using the least square method applied to the most recent V synchronization points 301, 304 (where V is typically set to a value between 4 and 12) in the synchronization window 302. Using the least square method yields better results than simply computing an average value. Once an initial value for the offset for the virtual clock 104 of the measurement responding node 100 is calculated, the synchronization session 106 remains active to obtain other values for the offset for the virtual clock 104 and refreshing the offset for the virtual clock 104 using the V most recent values (or less than V if not enough synchronization points 301, 304 have been established to date) to recalculate the offset for the virtual clock 104 using the least square method.

(32) Measurement messages are sent from the measurement requesting node 102 to the measurement responding node 100. The measurement messages contain a sequence field and a timestamp field T1.

(33) The semantic of the message fields are as follows: Sequence number. The measurement requesting node 102 sets the sequence number incrementally (for example: 0, 1, 2, etc). Timestamp T1. The time (from the high accuracy clock 200) when the measurement message was sent by the measurement requesting node 102.

(34) The measurement step comprises calculating the one-way latency in the network 101 between a measurement requesting node 102 and a measurement responding node 100 according to the following relations:
latency=the time at which the measurement responding node 100 received the measurement message−(T1+(the offset for the virtual clock 104 calculated for the measurement responding node 100×calculated skew)).

(35) An overhead amount corresponding to the overhead for making measurements at one of the nodes 100, 102 can be subtracted from the above amount.

(36) It is possible to operate in relation to more nodes than a single one. The present embodiment may be used to operate against a plurality of nodes by maintaining a synchronization window 302 and an associated virtual clock 104 at a measurement responding node 100 for each measurement requesting node 102 via synchronization sessions 106 with each of a plurality of measurement requesting nodes 102.

(37) In FIG. 4, an incarnation of a network module 400 is shown. The software modules 107, 108 implementing the embodiment need to have access to a network module 400. The network module 400 typically consists of a network interface card 404, a device driver 403, an IP stack 402 and a socket API 401. The network interface card 404 enables the node 405 to physically connect to an access network. The device driver 403 contains software enabling the IP stack 402 to access the network services on the network interface card 404. The IP stack 402 contains a full implementation of the communication protocols that enables the node 405 to communicate over the internet. This may be the set of protocols referred to as TCP/IP. The socket API 401 is a functional interface that the software module can access in order to send and receive packets to and from the network.

(38) The software module implementing the embodiment 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. In another embodiment, the software module may be implemented as a kernel application.

(39) The method is divided into two steps: On-going Clock Synchronization Measurement: requires that clock synchronization has been achieved between the measurement responding node 100 and the measurement requesting node 102.

(40) FIG. 5 is a table of constants used to parameterise the software modules 107, 108. The values given to the constants are merely an example.

(41) In FIG. 6, an on-going synchronization session 106 is schematically depicted. A synchronization session is established between each pair of nodes 100, 102. The synchronization session 106 is used to initially build a synchronization window 302 of at least 4 entries and up to 12 entries in order to hold synchronization points 301 to be used in the calculation of the synchronization line representing the virtual clock 104. At regular intervals, a burst 300 of synchronization requests are sent from the measurement responding node 100 that needs to setup a virtual clock 104 since it will handle measurement requests in measurement sessions 103 (once a virtual clock 104 is synchronized on the measurement responding node 100) for a measurement requesting node 102 (this is the node that will initiate a measurement session).

(42) Each burst 300 of synch requests 202 (SyncReq) starts by resetting the number of synch request and number of synch response (NSREQ and NSRSP) counters to a default value of zero (0) and setting the round trip time minimum (RTTMIN) value to a high value 600. For the duration of a synchronization burst 300, the sending node will send SyncReq messages 601 and will wait for a SyncRSP reply 602. Each SyncReq message includes a T1 timestamp 204 and the SyncRsp repeats the original T1 timestamp and adds the T2 205 and T3 206 timestamps. The T4 timestamp 207 is set internally for each SyncRsp received back at the sending node.

(43) If a timeout is received, processing goes to 601 (see ahead).

(44) Whenever a valid SyncRsp is received 603, the Round-Trip-Time (RTT) 305 is calculated by subtracting T1 204 from T4 207 and further subtracting the delay to prepare the SyncRsp reply represented by the difference between T3 206 and T2 205. This yields the current RTT 305 value 604.

(45) If this RTT 305 value is smaller than the current RTTMIN value 605, the RTTMIN candidate value for the current synchronization point (SyncPoint) 301 is updated to reflect the current RTT 305.

(46) The Clock Difference (CDIFF) for the candidate SyncPoint 301 is calculated as the sum of the delay in each direction divided by 2. This is represented by the formula: CDIFF=(T2−T1+T3−T4)/2. The absolute value of the virtual clock 104 (CABS) for the candidate SyncPoint 301 is set to the time when the current SyncRsp 203 was received (T4 207). This is represented by the formula CABS=T4.

(47) If the RTT value 305 is not smaller than the current RTTMIN. Processing goes to 606 (see ahead).

(48) The number of sent synchronization requests NSREQ in the current burst 300 is then checked 606. If the value of NSREQ has not yet reached the maximum defined for the SyncBurst, another SyncReq is sent 601.

(49) Otherwise, the desired number of SyncRsp messages has been received 607 and the Virtual Clock 104 can be updated taking into account the most recent SyncPoint 301. The update of the Virtual Clock 104 is discussed in more details below as per FIG. 7.

(50) Once a SyncPoint 301 is established, the NSREQ and NSRSP counters and RTTMIN are reset in order to allow for another SyncBurst to take place 608.

(51) The SyncBurst will be delayed for a longer period (in the order of 6 seconds in this embodiment) once a valid Virtual Clock 104 has been established. Otherwise, a more aggressive SyncBurst period (set to 2 seconds in this embodiment) will be used 609.

(52) As per FIG. 7, the update of the Virtual Clock 104 takes place when a new SyncPoint has been obtained 700.

(53) The size of the SyncWindow is checked 701. If it is not full processing goes to 703 (see ahead).

(54) Otherwise the maximum size of the SyncWindow has been reached 702 and, the oldest SyncPoint shall be removed from the SyncWindow and no longer used when calculating the Virtual Clock 104.

(55) The number of SyncRsp NSRP is checked 703. If none have been received, the new SyncPoint is not valid and the processing goes to 705 (see ahead).

(56) A SyncPoint will be declared valid as long as at least one (1) SyncRsp has been received 703 and the syncWindow is updated 704.

(57) The number of SyncPoints in the SyncWindow SyncWindowSize is checked 705. If it is not at least 4 then the process reverts back to the steps in FIG. 6 with a new SyncBurst.

(58) Once the SyncWindow includes at least four (4) SyncPoint, the Virtual Clock 104 representing the Virtual Clock can be computed 706. This is covered in more details in FIG. 8. Once the updating of the Virtual Clock 104 is completed, the process reverts back to the steps in FIG. 6 with a new SyncBurst.

(59) As per FIG. 8, the calculation of the Virtual Clock 104 tuple relies on the Sum of Least Square Method to smooth out the variations in the SyncPoint value in the SyncWindow. The virtual clock 104 for a specific measurement requesting node 102 is defined by the following tuple:

(60) SKEW: this is the variation (sometimes referred to as the jitter) of the clock between the measurement responding node 100 and the measurement requesting node 102

(61) CABS: this is the absolute value or wall clock value of the measurement requesting node 102

(62) CDIFF: difference (or offset) between the clock of the measurement responding node 100 and the clock of the measurement requesting node 102.

(63) The calculation of the virtual clock 104 involves the steps defined in FIG. 8 and are discussed in further details below:

(64) Step 1 800: in order to obtain the Sum of the Least Square value for the virtual clock 104, a mean CABS value is obtained using each valid SyncPoint in the SyncWindow and a mean CDIFF value is obtained using each valid SyncPoint in the SyncWindow as follows:
CABSmean=SUM(CABS for each valid SyncPoint)/Number of valid SyncPoint
CDIFFmean=SUM(CDIFF for each valid SyncPoint)/Number of valid SyncPoint

(65) Step 2 801: Calculate the sum of differences above and below the slope of the SyncWindow as follows:

(66) For each valid SyncPoint in the SyncWindow,
ABOVE=SUM((CABS−CABSmean)×CDIFF)
BELOW=SUM((CABS−CABSmean)×(CABS−CABSmean)

(67) Using the mean value for CABS and CDIFF and the ABOVE and BELOW values, it is now possible to update the tuples making up the Virtual Clock 104 per these remaining steps.

(68) Step 3 802: the updated SKEW is obtained by dividing the value of ABOVE by the value of BELOW:
SKEW=ABOVE/BELOW

(69) Step 4 803: the new difference between the clocks of the measurement responding node 100 and of the measurement requesting node 102 involved in this Synchronization Session is obtained by subtracting the mean value of the CABS multiplied by the SKEW from the mean CDIFF value calculated in step 1.
CDIFF=CDIFFmean−(SKEW*CABSmean)

(70) Step 5 804: the new wall clock value of the measurement requesting node 102 is set to the mean value of the wall clock value of each valid SyncPoint in the SyncWindow calculated in step 1 above:
CABS=CABSmean

(71) Finally, in step 6 805, the clock difference from the initial reference point for the Synchronization Session (also called time zero) is obtained by adding the product of the new CABS value multiplied by the SKEW to the value of CDIFF obtained in Step 4 803 above.

(72) In summary, the process illustrated by FIG. 8 updates the virtual clock 104 tuple made up of the CABS, CDIFF and SKEW value obtained from the valid SyncPoints in the current SyncWindow.

(73) FIG. 9 depicts a measurement session 103. A measurement session 103 consists of the measurement requesting node 102 periodically sending measurement request messages 901 to the measurement responding node 100. T1 902 is the timestamp when the message leaves the measurement requesting node 102. T2 904 is the timestamp for when the measurement request 901 message is received by the measurement responding node 100. In the case of a two-way measurement request, a measurement response 902 is needed. If so, T3 is the timestamp for when the measurement response 902 message leaves the measurement responding node 100. The virtual clock 104 is used in these timestamps to synchronize the times between the two nodes. T4 is the timestamp for the measurement requesting node 102 receiving the measurement response 902.

(74) FIG. 10 is a flowchart of a measurement session 103. The measurement responding node 100 records the timestamps T1 903 of the time of sending stored in a measurement request 901 message in the vector A[ ] and the timestamp T2 904 of receiving of the measurement request 901 in vector B[ ]. The size of the vectors is equal to the number of measurement messages 901 sent, NM. The two vectors A[ ] and B[ ] are later used in the interpolation phase.

(75) The measurement requesting node 102 sends NM messages (for example 10000) with interval DT between each packet (for example 20s). Each measurement request 901 message will contain SEQ (the sequence number) initially set to 0 1000 and the time T1 903 the measurement request 901 was sent as per the measurement requesting node 102 high accuracy clock 200. The overhead of sending a measurement request 901 Ks is computed initially 1001. This is the difference in time from when the timestamp T1 903 was taken and when the measurement request 901 was actually sent. Ks may be set to 0 if the measurement requesting node 102 lacks the capability to compute this time. The next measurement request 901 is sent after the appropriate period of time and the sequence number SEQ is incremented 1002. The measurement requesting node 102 then checks to see if the sequence number SEQ is less than the number of measurement request 901 NM to be sent 1003. If it is, then it goes back around to 1002. Once the sequence number SEQ and number of messages to be sent NM are the same, all of the measurement requests 901 for a measurement session 103 have been sent and the processing on the measurement requesting node 102 is complete.

(76) FIG. 11 shows a flowchart of the handling of a measurement session by the measurement responding node 100. The measurement responding node 100 stores the sending timestamp T1 903 in a vector A for each measurement request 901 it receives, and the receiving timestamp T2 904 in a vector B. A flag in the vector VALID is set to indicate that the collected metrics (T1 903 and T2 904) collected for this measurement request can be used to calculate the latency profile of this measurement session 103. The sequence number SEQ is used as an index in the vectors A, B and VALID and is initially set to 0 1100. Kr, the overhead of receiving a measurement request 901 is computed initially 1101. This is the difference in time from when the T2 timestamp 904 was taken and when the measurement request 901 was actually received. Kr may be set to 0 if the measurement responding node 100 lacks the capability to compute this time. The measurement responding node 100 waits 1102 for the next measurement request 901. After receiving 1103 a measurement request 901, the value of the sending timestamp T1 903 is extracted from the measurement request 901 and stored in vector A and the timestamp T2 904 for the received measurement request 901 is stored in vector B. The corresponding VALID flag is set to indicate that the measurement request is valid and the SEQ value is incremented. At 1104, a check is made to determine if there are more measurement requests to be received. If this is the case, the processing resumes at 1102, otherwise the last measurement request 901 in the measurement session 103 has been received and the latency profile can now be measured during the interpolation phase.

(77) FIG. 12 is a flowchart describing the interpolation phase. The measurements collected during the measurement phase 1102 in the vectors A [ ] and B [ ] along with the value of CABS and CDIFF for the current virtual clock 104 are used to interpolate a sequence of one-way latency values 1103. The method itself can be performed on the measurement requesting node 102, the measurement responding node 100, or some other node, and can be performed at any time after a measurement session 103 is completed. For example, the interpolation phase can take place as a post processing stage in a server. However, the measurements collected during the measurement phase 1102 must be transferred to the device where the interpolation phase is implemented. The end result of the interpolation phase is a latency profile (vector L [ ]), with NM entries containing the precise one-way latency values of the measurements requests 901 between the measurement requesting node 102 and measurement responding node 100. A latency profile is calculated by analysing the measurement information collected during the measurement session 103. A loop is used to iterate through all of the collected measurements in vectors A and B. In 1200, the validity of the measurement metric is verified. If they are valid, then a latency profile is calculated and stored in vector L [ ] in 1201 as follows: L[i]=B[i]−A[i]+CDIFF−Ks−Kr and the index used to cycle through the collected measurements is incremented in 1202. In 1203, a check is made to determine if the entire set of collected measurements has been analysed or not. If there is more measurement to analyse, processing resumed at step 1200. Otherwise, the latency profile L [ ] is available.

(78) While particular embodiments and applications of the present invention have been illustrated and described, it is to be understood that the invention is not limited to the precise construction and compositions disclosed herein and that various modifications, changes, and variations may be apparent from the foregoing descriptions without departing from the spirit and scope of the invention as defined in the appended claims.