Method of detecting drift between two clocks

[0001] The invention relates to data transport between data network nodes in support of data streaming services, and in particular to methods and apparatus for detection of drift between clocks.

[0002] Widely known streaming services include: the station-to-station audio communications otherwise known as the telephone service, many-to-many communications otherwise known as audio conferencing, one-way playback communications such as voice-mail, etc. These legacy streaming services are typically provided at very high Quality-of-Service (QoS) levels afforded by the Public Switched Telephone Network (PSTN). The PSTN is a collection of data links and special purpose line switching nodes which interwork to provide circuit-switched dedicated connections between end stations. The high levels of QoS are provided over the PSTN at the expense of sub-optimal use of available data transport bandwidth over a relatively expensive, redundant, inflexible infrastructure when compared to packet-switched networks.

[0003] Packet-switching data transport networks, as opposed to the PSTN, are relatively more efficient in utilizing data transport bandwidth: by sharing the available data link bandwidth between multiple communication sessions using a comparatively economical infrastructure. In their infancy, packet-switched data transport networks were used to convey data without making any data transport guarantees and the term best-effort data transport was ascribed to them. In spite of the label, the demand for best-effort services, such as electronic mail and web-browsing, provided such a substantial revenue stream that service providers were providing circuit-switched (voice) and packet-switched (data) services in parallel to the same customers.

[0004] Revenues generated from the fulfilled demand for data transport services fuelled the development of advanced packet-switched data transport networks rivaling the QoS of circuit-switched networks. Streaming data services may be provided over data transport networks such as but not limited to: internet radio (broadcast audio streaming), audio/video conferencing, internet newscasts (on demand audio/video playback), etc. The success of packet-switched data transport technologies coupled with the demand for data services as well as the pressure to minimize service provisioning costs led to a market push to deliver legacy data streaming services over newer, more modem, more flexible infrastructure of the packet-switched data transport networks.

[0005] The migration of legacy data streaming services from circuit-switched technologies to packet-switched technologies is not without challenges. Key differences exist between the two technologies in providing QoS guarantees.

[0006] A data streaming service offering having a high QoS benefits from a minimum amount of jitter. Jitter is the variation in the interarrival of data packets at a receiving station. In circuit-switched networks, a dedicated connection is set-up between stations and therefore a minimum amount of jitter can easily be guaranteed. In packet-switched data transport networks however, jitter is incurred as a side effect of processing data packets to ensure efficient utilization of the data transport bandwidth. High levels of jitter leads to discontinuous playback of a data stream.

[0007] Data stream playback is further affected by data sampling and playback clock rates. Clock signals used in sampling and playback typically drift due to a variety of factors including but not limited to: inability to minimize tolerances in manufacturing processes, temperature variation, age of the clock, etc. Over time, discrepancies between these clock pacing rates can lead to data overflow/underflow conditions evidenced by a low perceived QoS. Severe discrepancies may ultimately lead to severe data loss.

[0008] Another key difference between circuit-switched and packet-switched data networks relates to the topology of the infrastructure. Typically circuit-switched networks have a hierarchical topology, whereas packet-switched networks are for the most part flat.

[0009] In a hierarchical topology provisioning environment, master clock signals may be distributed hierarchically. It is customary to use Cesium based time references as the costs involved in provisioning a small number of such expensive units at the top of the interconnection hierarchy can be leveraged over many service subscriptions.

[0010] However, in a flat topology provisioning environment, the distribution of master clock signals is a problem which remains unresolved. The flat topology of the packet switched data transport networks tends to suffer from an inability to route master clock signals effectively. A variety of master clock signal distribution protocols have been developed, with others still under development.

[0011] Although global time standards exist, such as the Greenwich Mean Time, once clocks are set by it, the clocks will drift necessitating further calibrations. Other solutions include the use of timing signals provided for example by the Global Positioning System (GPS). Such solutions are highly impractical to implement in end stations due to a variety of factors including implementation and deployment cost. GPS receivers also require an unobstructed view of a large sector of the sky which would severely restrict the use of communications equipment implementing such solutions.

[0012] There therefore is a need to address problems associated with clock drifts between multiple clocks in supporting data streaming services.

[0013] In accordance with an aspect of the invention, a clock drift evaluator is provided. The hardware implementation of the evaluator includes a group of components. A time stamp extractor is used to extract time stamp values from each received data packet of a data stream. An arithmetic unit provides a time difference value between the extracted time stamp value and a current local time value for each received data packet. Comparison means are used to compare the time difference value against a reference time value to determine whether each received data packet is one of: an early received packet, an on-time received packet, and a late received packet. Means for providing an evaluation of clock drift based on indications of an extent of early and late packet arrivals.

[0014] In accordance with another aspect of the invention, a clock drift evaluation methods provided. The method includes a sequence of steps. A time stamp value generated by a source clock is extracted downstream from the source clock from each received data packet of a monitored data stream. A time difference value is derived between the extracted time stamp value and a current local time value provided by a local clock. A determination is made as to whether each received data packet is one of: an early received packet, an on-time received packet, and a late received packet. A clock drift determination between the source clock ad the local is made by comparing degrees of late and early packet arrivals against an adjustment threshold level.

[0015] The detection of drift between clocks provides support for service level guarantees in provisioning data streaming services.

[0016] The features and advantages of the invention will become more apparent from the following detailed description of the preferred embodiments with reference to the attached diagrams wherein:

[0017] FIG. 1 is a schematic diagram showing a comparison between ideal and typical packet arrival rates at a receiver;

[0018] FIG. 2 is a schematic diagram showing elements implementing a clock drift detection in accordance with a preferred embodiment of the invention;

[0019] FIG. 3 is a schematic diagram showing a normalization table used in accordance with a preferred embodiment of the invention;

[0020] FIG. 4 is another schematic diagram showing a normalization table used in accordance with an alternative embodiment of the invention; and

[0021] FIG. 5 is a schematic diagram showing a comparison between ideal and corrected playback in accordance with the preferred embodiment of the invention.

[0022] It will be noted that in the attached diagrams like features bear similar labels.

[0023] The subject matter of the invention will be presented herein with respect to Voice-over-Internet Protocol (VoIP) technologies which include protocols and hardware adapted to sample, generate, convey and play back telephone quality audio streams. The invention is not limited by the presented embodiments; persons of ordinary skill in the art would recognize that the techniques presented herein may be used for processing other data streams

[0024] The Internet Protocol (IP) is an Open Systems Interconnection (OSI) Layer 3 protocol used for conveying packets over packet-switched data networks end-to-end. The VoIP technologies interwork with the IP protocol to provision the conveyance of telephone quality audio streams end-to-end.

[0025] Depending on the VoIP implementation, end-to-end data transport may be provisioned over the OSI Layer 4 connectionless Universal Datagram Protocol (UDP) or the connection-oriented Transport Control Protocol (TCP).

[0026] In of itself the IP protocol does not make any guarantees as to the delivery of data packets, nor does it have support for providing service level guarantees. Typically VoIP implementations make use of other data transport protocols to provide support for service level guarantees. Many such data transport protocols have been devised, most of which are still under development. The Real-Time Protocol (RTP) is an example of a data transport protocol attempting to control transport latencies in conveying data packets over packet-switched data transport networks.

[0027] The subject matter presented herein will be described making reference to the RTP protocol used in combination with the UDP/IP data transport protocols. The combination provides for the conveyance of RTP/UDP/IP encapsulated data packets at reduced overheads. Other combinations of protocols may be used without limiting the invention.

[0028] In order to convey data streams in support of real-time communications, it is important for sender and receiver stations (with respect to a data stream) to agree on audio signal sampling and playback rates. In the absence of reliance on a master clock signal, the use of the RTP protocol provides for the inclusion of time stamp values encapsulated with data stream samples in the data packets conveyed.

[0029] The following issues must be taken into account in sampling, generating, conveying and playing back voice samples for telephone service provisioning:

[0030] Typical telephone sessions include: playback-only where the receiving station listens to voice prompts for example, station-to-station in which both stations generate and convey voice samples, and audio-conferences in which a stream of voice samples generated at one of the stations is multicasted to all other participant stations in the audio-conference. Therefore multiple clock signal sources exist;

[0031] It is preferred that each sampling source clock use a different, randomly selected, starting time value from which to advance the sampling clock values in order to prevent data encryption attacks. The RTP protocol provides a packet sequence number which also increments from a randomly generated starting value to prevent data encryption attacks. Encryption when necessary in communications is provided by a higher layer protocol outside the scope of the subject matter described herein;

[0032] The sampling and playback clocks must agree on, and be aware of, a unit of time used to express values of the time stamp conveyed in the RTP header. The time stamp value is typically expressed in terms of integer stamping intervals, each sampling interval having a duration of 125 s; and

[0033] Correct playback timing can only be ensured if the sampling rate and the playback rate are substantially the same (i.e. well within tolerances of the human hearing system). The sampling and playback rates, in the absence of a master clock are dependent on the respective pacing rates thereof.

[0034] A person of ordinary skill in the art would understand that both the sampling clock and the playback clock may develop a slightly different pacing rate. The development of a slightly different pacing rate by a clock is referred to, in the art, as clock drift.

[0035] Regardless of which one of the sampling or playback clocks develops the slightly different pacing rate, it is more convenient to regard the sampling clock as an absolute clock while the playback clock is regarded as the one deviating from the absolute. Only relative clock drift is important. Making this choice, reduces each one of the above presented telephone session configurations to a combination of playback-only telephone sessions. A station-to-station telephone session corresponds to two playback-only telephone sessions. In an audio-conference, sampled audio data can be regarded as being sent to each one of the other participants in the audio-conference in individual playback-only telephone sessions.

[0036] Therefore clock drift detection is to be performed downstream of the VoIP source stations by devices including, but not limited to, VoIP receiving station related equipment.

[0037] Therefore only three relevant pieces of information are available at a data network node providing VoIP services downstream from a source:

[0038] the sequence number of the VoIP-RTP data packet (IP packets are not necessarily conveyed in sequence);

[0039] the time stamp value held in the RTP header representative of the relative time at which the data samples were generated (expressed in multiples of 125 s); and

[0040] the current time value of the data network node at which voice sample data packets are received (expressed in multiples of 125 s).

[0041] FIG. 1 is a diagram showing a comparison between an ideal and typical pacing of two clocks relative to one another as observed at a station receiving a data stream for real-time playback.

[0042] FIG. 1A is representative of the ideal situation in which no perceptible relative drift exists between the sampling and the playback clock. The graph 100 shows a monotonically increasing variation of received timestamp values with each received packet ni in the data stream.

[0043] The graph 110 is representative of a variation in the interarrival time between received packets ni of a data stream as measured in 125 s clock ticks at the receiving station. The graph 110 is not smooth due to jitter being incurred by the packets ni while in transport between the source and the receiving station. It is possible, as mentioned above, for the packets associated with the stream to arrive out of sequence. This is schematically shown in the diagram wherein the n2 packet has arrived before the n1 packet.

[0044] On a small time scale, the level of jitter overshadows the clock drift as the jitter variation level may be much greater than the degree of clock drift. The jitter is assumed to be generated by packet processing which, for stable packet-switched data transport equipment and therefore packet-switched data transport networks has a bound average value.

[0045] Therefore, by monitoring received packet arrival times over the long term, relative clock pacing rate variations may be determined. A running average of the arrival times of the packets ni can be calculated at the receiving end. The graph 120 corresponds to the running average associated with the arrival times of the packets ni. In the ideal scenario shown, there is no perceptible relative clock drift, the graphs 100 and 120 are parallel and distanced apart by a constant time duration labeled d_ref.

[0046] FIG. 1B is representative of a scenario in which the source clock is perceived at the receiver station to run faster due to a perceived fast receipt of packets. A fast receipt of packets may be determined from a shallower slope of the graph 120 compared to that of graph 100. This of course may also be due to an actual slow running clock associated with the receiving end. As mentioned above, regardless which clock drifts, the source clock is assumed to be absolute and the receiver clock is assumed to run comparatively slower.

[0047] In such a case, if the receiver clock is used to play back the audio stream, the playback would tend to be slow in comparison with the rate at which the samples were generated and therefore would tend to play back less samples then are received per unit time. The situation may lead to saturation of the data stream and buffer overflow conditions. The listener would be experiencing a relatively slow playback interspersed with discontinuous choppy speech as packets are dropped from overflown buffers and therefore absent from the playback. As mentioned above, the human hearing system is tolerant to some extent but severe clock drifts can lead to discomfort.

[0048] FIG. 1C is representative of a scenario in which the source clock is perceived by the receiver end to run slow due to a perceived slow receipt of packets. A slow receipt of packets may be determined from a steeper slope of the graph 120 compared to that of graph 100. This of course may also be due to an actual fast running clock associated with the receiving end. As mentioned above, regardless which, source clock is assumed to be absolute and the receiver clock is assumed to run comparatively faster.

[0049] In such a case, if the receiver clock is used to play back the audio stream, the playback would tend to be fast in comparison with the rate at which the data stream samples were generated and therefore the receiver would tend to play back more samples then are received per unit time. The situation may lead to starvation of the data stream and buffer underflow conditions. The listener would be experiencing relatively fast playback interspersed with relatively long periods of uncomfortable silence as subsequently received packets catch up with the playback. The human hearing system is tolerant to some extent but severe clock drifts can lead to discomfort.

[0050] In accordance with the invention, an attempt is made at detecting, with the intent of subsequently correcting for, clock signal drift between the source clock and the playback clock. The description herein will focus on detecting clock drift while only providing reference to methods of correcting for clock drift. Correcting for clock signal drift is a topic of research onto its own. Methods and apparatus of detecting the clock drift will be presented hereinbelow.

[0051] FIG. 2A is a schematic diagram showing elements implementing clock drift detection. In accordance with the preferred embodiment of the invention a hardware clock drift evaluator 200 is provided.

[0052] Persons of ordinary skill in the art are well aware that the running average alluded to above as well as performing divisions in calculating the average are hard to implement in hardware. In making use of a running average, the provided result would: give an indication that a relative clock drift exists, the type of drift, and the extent of the clock drift.

[0053] In accordance with the preferred embodiment of the invention, implementing a running average provides more information than is necessary as the extent of the clock drift is to be contained by detecting indications of, and the type of, clock drift as soon as possible.

[0054] In accordance with an exemplary hardware implementation of the evaluator 200 presented herein, a relatively long time interval referred to as an epoch is chosen to include in the evaluation a number of received packets in order to smooth out the jitter in evaluating clock drifts. Typical voice sampling methods generate a voice sample every 125 s. Human hearing tolerances mentioned above are in the order of 1 ms. If the epoch evaluation period is too short, then the output provided by the evaluator 200 is highly correlated to and in effect measures the jitter. If the epoch evaluation period is too long, then the playback is subject to the discomfort mentioned above. Field trials have shown that epoch times of 1-2 s strike a balance between a comfortable playback under general prevailing conditions while minimizing clock drift detection computational overheads incurred. In accordance with another embodiment of the invention the duration of each epoch may be chosen to optimize QoS parameters.

[0055] In accordance with a preferred embodiment of the invention, the clock drift is evaluated based on detected discrepancies between d_ref, and calculated differences d between the time stamp value and the arrival time of each received packet of a data stream monitored by the evaluator 200.

[0056] A packet stream 202 is received at a data network equipment evaluating clock drifts via an input port 204. The packet stream 202 is distinguished from other data packets conveyed via the port 204 using preferable methods described in co-pending United States patent application bearing Ser. No. 10/033,498 entitled Generic Header Parser Providing Support for Data Transport Protocol Independent Packet Voice Solutions filed by the Applicant on Dec. 27^th, 2001. The corresponding time stamp value 208 is extracted 206 from each received data packet in the stream 202.

[0057] A playback timer 210 provides the current playback time 212. The current playback time 212 may be derived from a system clock 214.

[0058] Based on the time stamp value 208 and the current playback time 212, a subtractor 216 computes the difference d 218 therebetween for each received packet.

[0059] The hardware implementation makes use of a group of counters all of which are reset to zero on start up as well as at the expiration (240) of each epoch. The group of counters includes:

[0060] an epoch counter 220 whose roll over condition signals the end of an epoch,

[0061] a counter 222 associated with the extraction step 206 tallying the total number of packets received during an epoch,

[0062] a counter 224 tallying the number of packets received early during an epoch, and

[0063] a counter 226 tallying the number of packets received late during an epoch.

[0064] In accordance with the preferred embodiment of the invention, the indication of the clock drift is derived from:

[0065] the percentage of packets received late during an epoch normalized to the total number of received packets during the epoch, and

[0066] the percentage of packets received early during an epoch normalized to the total number of received packets during the epoch.

[0067] The value d (128) is provided, preferably in parallel, to decision blocks 230 and 232. For each newly calculated value d: the decision block 230 determines whether the corresponding packet has been received early, and decision block 232 determines whether the corresponding packet has been received late.

[0068] The decision that the packet was received early, that is d<d_ref, is used to increase 234 the counter 224 by one. The decision that the packet was received late, that is d>d_ref, is used to increase 236 the counter 226 by one. Packets arriving on time (dd_ref) contribute only to the total number of packets received during the epoch counted by counter 222.

[0069] The process of inspecting packets continues for the duration of each epoch until the epoch time counter 220 rolls over.

[0070] The value of counter 222 holding the total number of packets received during the epoch is used as an index into a table 300. The table 300 is used to provide normalized adjustment thresholds to generate an indication of clock drift. The table includes: a group of values R0 to R_m representative of amounts of total number of packets typically received during an epoch, and a related group of values T0 to T_m1 representative of corresponding normalized adjustment thresholds. Different implementations may be used as shown at 300 in FIG. 3 and at 400 in FIG. 4. A balance must be struck between the number of table entries related to implementation cost and the accuracy of the normalization provided.

[0071] In accordance with the invention, the normalization with respect to the total number of packets received, takes into account periods of time in which no samples are conveyed in connection with the monitored data stream due to silence at the originating station.

[0072] In accordance with a preferred implementation of the invention, on the roll over event 240, the value of the counter 222 is loaded in parallel to a group of comparators 242. A comparator 242 is used for each R entry in the table 300. Each comparator 242 determines whether the total number of received packets during the epoch just completed, is greater than the corresponding R value. Consequently, a sequential number of comparators 242 will output a logic high value and a remaining sequential number of comparators 242 will output a logic low value.

[0073] The output of the comparators 242 are provided to a bank of AND gates 244 in sequential pairs. One of the inputs of each AND gate 244 is negated such that only one the AND gate 244 will output a logic high value. The AND gate 244 which outputs the logic high value corresponds to immediately higher and immediately lower R values about the total number of packets received during the epoch just elapsed.

[0074] The outputs of the AND gates 244 are ANDed 246 with corresponding T values and the resulting outputs are ORed together 248. Because only one AND gate 244 outputs a logic high signal, the corresponding T value is output 250 by the OR gate 248.

[0075] In accordance with another implementation of the invention, the granularity of the entries in table 400 is specified by single R entries having omitted least significant digits. A range of total number of received packets (222) would correspond to an R entry. As shown in FIG. 2B, the comparators 242 would match the total number of received packets to an R entry directly (i.e. the most significant digits of the respective binary representations thereof would match) therefore not necessitating the use of AND gates 244.

[0076] The arrangement of comparators, gates and table registers described in the above implementations provides the correct normalized adjustment threshold T value in one clock cycle derived from the roll over event 240.

[0077] The normalized adjustment threshold value T (250), corresponding to the total number of received packets for the epoch just elapsed, is provided to two decision blocks 252 and 254. Each one of the decision blocks 252/254 determines 256/258 whether the number of early/late received packets exceeds the adjustment threshold T respectively.

[0078] The outputs 256 and 258 are provided to a clock drift compensation block 260 to perform the necessary adjustments in playing back the audio stream.

[0079] A copy of the roll over event 240 is delayed and subsequently used to initialize all counters to zero to ready the evaluator 200 for the next epoch.

[0080] A variety of compensation techniques may be implemented including: adjusting the pacing rate of the playback timer 210, signaling a playback stream generator 270 when to drop or add samples to the output stream 272, dropping/inserting packets in a packet buffer 274, etc. The compensation of clock drifts is beyond the scope of the present description and may even include providing a feedback to the source.

[0081] FIG. 5 is a schematic diagram showing a comparison between an ideal and corrected playback in accordance with the preferred embodiment of the invention.

[0082] FIG. 5A is representative of the case in which no perceptible clock drift exists between the sampling clock and the playback clock where the variations in received time stamp values 100 and playback times 500 have parallel linear graphs.

[0083] FIG. 5B is representative of corrected fast playback 500 due to clock drift which is adjusted, in accordance with the example shown, every other epoch.

[0084] FIG. 5C is representative of corrected slow playback 500 due to clock drift which is adjusted, in accordance with the example shown, every fourth epoch.

[0085] The value of d_ref must be provided in order to use the above presented methods and apparatus. A multitude of methods may be used to derive the value of d_ref without departing from the spirit of the invention.

[0086] In accordance with an exemplary embodiment of the invention, an average d ref value is obtained from the first couple of calculated d values. A simple way of implementing such an average d_ref value is to accumulate 2{circumflex over ()}n d values and shift the binary representation of the result n times to discard least significant bits. Situations may arise in which the selected d values for the calculation of d_ref are severely contaminated by jitter in which case the resultant d_ref value is inappropriate. The calculation of d_ref may be performed on the first packets received after clock drift adjustments to eventually settle on a d_ref value. Care must be taken so as not to create conditions for positive feedback.

[0087] In accordance with another embodiment of the invention, the value of d_ref is determined from ping times between the data network equipment performing the clock drift evaluation and the data network equipment encapsulating time stamps in the data packets of the monitored data stream. Again averaging of ping times may be performed without division by shifting n times binary representations of 2{circumflex over ()}n accumulated ping times.

[0088] As mentioned above, it is to be understood that although the invention was presented with respect to the processing of a one-way data stream, the invention applies equally well to all call scenarios.

[0089] Further it is understood that any number of devices may be used between the data stream generation station and the playback station including data stream mixers. In many instances the data stream mixers re-stamp the data packets with new time stamp values generated by source clocks at the mixing device. The invention therefore need not necessarily be limited to monitoring sampling and playback clock pacing rates and may also be used to monitor source clock pacing rates. The invention need not necessarily be implemented only in equipment associated with a receiving station; an input end of other devices such as mixers may also use the apparatus and implement methods presented herein. As such clock drift determination may be performed between any source clock and a local clock associated with the evaluator 200.

[0090] The embodiments presented are exemplary only and persons skilled in the art would appreciate that variations to the above described embodiments may be made without departing from the spirit of the invention. The scope of the invention is solely defined by the appended claims.