Clock synchronization over data transmission networks

[0002] 1. Field

[0003] The following invention disclosure is generally concerned with the synchronization of receiver and transmitter time-bases in data transmission networks and specifically concerned with a least squares linear regression technique having a fast startup phase and improved jitter absorption.

[0004] 2. Prior Art

[0005] Recent developments and advances in information technologies have led to new and unanticipated problems. In particular, transfer of data from a server to a requesting client presents certain complication. In addition, the types and formats of data to be transferred have attributes which may further complicate matters. For example, video data comprises a series of still frames which must be played one after another in a predefined and well regulated time sequence. Accordingly, information relating to the image data must be transferred along with information relating to the timing of playback events. Proper transmission of video images requires a scheme to preserve signal timing attributes from a transmitting station to a receiving station.

[0006] For proper play-back, an audio-video signal is preferably played out at the same rate which it is transmitted. This is especially important in interactive systems where “real-time” properties are maintained. If a receiver clock is independent from a transmitter clock then the receiver may play frames slightly faster than it receives them and lead the system into a data starvation condition. Alternatively, if the receiver plays frames too slowly, then a data overflow condition may occur at a data buffer having a limited size.

[0007] In certain transmission networks a data stream is divided into many portions or “packets” and transmitted along various paths of the network. These packets may be subject to time delays which are random in length. Sometimes and herein referred to as “jitter”, random time delays are necessarily inherent in networks which transmit data in data subsets. Each data packet may arrive at a receiver with a total transmission time which may vary from packet to packet. Depending upon the network path and network congestion conditions, transmission time delays may be highly different between packets. For audio-video data to be useful, it must be transmitted through the packet network and played back in a manner where the time delays or network jitter does not show up as artifacts in the presentation level play back. In order to achieve this, it is necessary that a time base of the transmitting station be replicated at the receiver and thus the “clocks” of the terminal end are said to be synchronized.

[0008] Most popular processing devices of digital audio-video data, like TV decoders or PC video boards, define a syntax for coding, decoding, transport and storage of audio-video data streams. This scheme includes provision for a shared time-base between the terminal ends, i.e., the sender and the receiver. For proper processing of digital audio-video signals, it is necessary that a clock of the receiver be synchronized to a clock of the transmitter. Presently, digital audio-video signals are processed within systems which employ a phase-lock loop technique to synchronize a receiver clock to the transmitter clock. The technique is old and reliable and has made its way into many thousands of similar applications where a slave clock is necessarily coupled to a master clock. However, the technique suffers from problems which arise do to the nature of the feedback loop. A phase-locked loop may require many feedback cycles before the slave clock becomes locked to the master clock. This is especially true when the allowable error (clock cycle or frequency) is small. If the phase of the slave clock must be precisely matched with the master, then the lock may take a considerable amount of time to achieve. The period of time for the clocks to become in sync may be referred to as a “startup phase”. Accordingly, a phase-locked loop having high precision requirements may have a long startup phase. Transmission systems which employ phase-locked loop techniques are slow to realize the lock and perfect the transmission of audio-video data. While the startup phase is incomplete, an application may play audio-video data where timing artifacts show up at the presentation level.

[0009] In systems where the time to acquire a lock is short compared to the time in which a lock is held, the problem is not of serious consequence, however, for some systems the time extent of the signal is relatively short and the required lock time becomes problematic. For example, in real-time applications such as interactive teleconferencing. The first few seconds of each data exchange may suffer from a clock which is out of sync. Since the duration of any single transmission may only be of the order of a few seconds, startup phase errors due to phase-locked loop techniques become perceivable to the end user. Accordingly, it becomes desirable to find a scheme which locks a slave clock to a master clock where the time to obtain a lock is shorter than that which is associated with a phase-locked loop.

[0010] Yasuda teaches a modified phase-locked loop technique in U.S. Pat. No. 5,386,437 published Jan 31, 1995.

[0011] A primary objective of that teaching is a variable output which varies in relation to phase error to produce a desired characteristic during pull-in and during synchronization. The techniques provide for avoiding a step-like sudden change of clock frequencies. While being a significant improvement, the system remains a version of a phase-locked loop technique which has a long pull-in or start up period and is consequently not appropriate for applications requiring synchronization where the session length is short.

[0012] Inventors Witsaman et al disclose an apparatus for synchronizing a plurality of clocks in a simulcast network to a reference clock. U.S. Pat. No. 5,416,808 dated May 16, 1995 sets forth a scheme whereby a centralized reference clock keeps a time which is accessible over a large geographic area. Individual distributed clocks are manipulated in accordance with comparisons of their time with the time on the reference clock.

[0013] While the systems and inventions of the prior art are designed to achieve particular goals and objectives, some of those being no less than remarkable, these inventions have limitations which prevent their use in new ways now possible. These prior art inventions are not used and cannot be used to realize the advantages and objectives of the present invention.

[0014] Comes now, Raffaele Noro and Jean-Pierre Hubaux with an invention of apparatus and methods relating to clock synchronization over data transmission networks including a least squares linear regression technique and device for executing same, having fast startup phase and high jitter absorption. It is a primary function of these apparatus and methods to provide means of reducing the time required to reach a synchronized state while maintaining synchronization accuracy. It is a contrast to prior art methods and devices that those systems do not reach a synchronization lock without first enduring a long startup period. A fundamental difference between a phase-locked loop of the prior art and the instant invention can be found when considering handling of timing indicators which are coded onto a signal being transmitted.

[0015] In systems of the invention, an apparatus receives a data stream containing timing indicators, which are used in a least squares linear regression technique to synchronize the time-base of a transmitting station with that of a receiving station. Timing indicators, commonly called program clock references or PCRs, contain timing information and are generated at the transmitter end in accordance with a data transmission coding syntax. After data streams are received at an apparatus of the invention on a receiving end, the PCRs are separated from the base signal and are used to drive a modified least squares linear regression technique which produces timing information to reconstruct the time base of the transmitting station.

[0016] A conventional least squares linear regression approach is modified to reduce complexity and provide for implementation in a physical system. A mathematical modification relates to an assumption which may be made about the transmitter and receiver clocks which necessarily have frequencies which are close to each other. This simplification which is applicable to transmission systems reduces the computing overhead necessary to implement the method via standard hardware.

[0017] It is a primary object of the invention to provide apparatus and technique for synchronizing the time-bases of the terminal ends of a transmission network.

[0018] It is an object of the invention to provide an improved synchronization system in transmission networks used for transmission of time sensitive data having a reduced startup phase.

[0019] It is a further object to provide improved synchronization systems in transmission networks used for transmission of time sensitive data having high tolerance of jitter introduced by such transmission networks.

[0020] It is an object of the invention to provide synchronization systems for interactive applications where a short startup phase is required.

[0021] It is an object of the invention to provide an apparatus having a hardware implementation corresponding to the technique of least squares linear regression to slave a receiver time base to a sender or master time base, the sender or master sending time indicators over data networks and the receiver or slave receiving time indicators from the same data transmission networks.

[0022] A better understanding can be had with reference to the detailed description of Preferred Embodiments and drawing figure herefollowing. These embodiments represent particular ways to realize the invention and are not inclusive of all ways possible. Therefore, there may exist embodiments that do not deviate from the spirit and scope of this disclosure as set forth by the claims, but do not appear here as specific examples. It will be appreciated that a great plurality of alternative versions are possible.

[0023] These and other features, aspects, and advantages of the present invention will become better understood with regard to the following description, appended claims and drawing where:

[0024] FIG. 1 represents a preferred embodiment of the invention as a set of components that perform elementary operations on received time indicators, which are then processed to update the frequency adjustment {circumflex over (a)} and clock offset {circumflex over (b)}. (note: the symbol (−) indicates the sum of a negative number, i.e. subtraction)

[0025] To recreate the time-base of a transmitting station at a receiving station, one may consider the receipt of program clock references, determine a trend, and anticipate the future by fitting a line to the received events. This technique, in general, is sometimes preferred to as the method of least squares and was developed by Gauss. By fitting a regression curve to data received in the form of program clock references, it becomes possible to derive the time-base of the transmitter and create an identical time-base for the receiver and thus synchronizing the clocks respectively. This approach has the advantage that receipt of only a few program clock references suggests a good fitted line. Thus, in a very short time one may form a clock synchronized to the transmitter.

[0026] However, the method of least squares is mathematically complicated and may require significant computing power which is not required in phase locked loop systems. Recall that a phase-locked loop system may be easily implemented in hardware and does not require computations.

[0027] It has been discovered that mathematical equations describing a method of least squares is subject to simplification when certain assumptions relating to the particular problem at hand are valid. Therefore, the amount of computing may be reduced and made more favorable to implementation in real systems.

[0028] The following modified method of least squares linear regression, when applied to time indicators, for example those hosted by digitized and coded audio video data sets, serves well to provide basis upon which a receiver clock may by synchronized to a transmission station's clock.

[0029] Glossary of Terms

[0030] Throughout this disclosure, reference is made to some terms which may or may not be exactly defined in popular dictionaries as they are defined here. To provide a more precise disclosure, the following terms are presented with a view to clarity so that the true breadth and scope may be more readily appreciated. Although every attempt is made to be precise and thorough, it is a necessary condition that not all meanings associated with each term can be completely set forth. Accordingly, each term is intended to also include its common meaning which may be derived from general usage within the pertinent arts or by dictionary meaning. For purposes of this disclosure:

[0031] Audio (Video)

[0032] Audio (and video) refers to a data type including a collection of audible samples (respectively, still images) which may be played in a sequence highly regulated in time.

[0033] Phase-Locked Loop

[0034] Phase-locked loop is a technique where a local oscillator is coupled by way of feedback loop to a master oscillator which provides timing control for the local oscillator.

[0035] Jitter

[0036] Jitter refers to timing irregularities which accompany transfer of information through transmission networks.

[0037] Master and Slave clocks

[0038] A master clock is an independent clock which runs at a preset rate. A slave clock is a dependent clock which runs at a variable rate which is under influence of a master clock.

[0039] Packet

[0040] A packet is a data subset which contains a portion of a data stream. Packets are unitary data objects which may be transmitted through a network.

[0041] Startup phase

[0042] Startup phase refers to the period of time from which a synchronization system is initiated and to which a stable synchronization occurs.

[0043] Program Clock References

[0044] Program clock references are timing indicators which are embedded in some data formats which provide for information about program time.

[0045] Method of Least Squares

[0046] One will recall from Gauss the basic equation of the method of least squares:

[0047] μ(x)=α+βx

[0048] where μ(x) is the mean of y which is a function of x in the ordinary sense.

[0049] In preferred embodiments of the invention it is assumed that the sender and receiver of the data stream are related by the following equation:

[0050] T_s(t)=aT_r(t)+b

[0051] Respectively, T_s(t) and T_r(t) are the time functions of the sender and the receiver, and {circumflex over (a)} and {circumflex over (b)} are the frequency drift and time offset. It can be assumed also that T_r(t) is the measure of absolute time (i.e. T_r(t)≡t).

[0052] The PCR generation and arrival processes are represented as follows:

[0053] PCR_g={T_s(t_i):∀i=1,2,3, . . . }

[0054] PCR_a={t_i+ΔT₀+Δt_i:∀i=1,2,3, . . . }

[0055] where ΔT_ois the average end to end delay and Δt_i, the jitter, is a random variable.

[0056] Reconstruction of a sender's time-base can be carried-out with the least-square linear regression analysis: the linear regression is fitted so that the sum of the square of the distances of the points from the regression is at a minimum. Computation of baricentric point ({overscore (x)},{overscore (y)}) permits the estimation of {circumflex over (a)} and {circumflex over (b)} as follows: $\hat{a}=\frac{\sum _{i=1}^N{T}_s^2\left(t_i\right)-N·{\stackrel{\_}{y}}^2}{\sum _{i=1}^N{T}_s\left(t_i\right)·\left(t_i+\Delta T_0+\Delta t_i\right)-N·\stackrel{\_}{x}·\stackrel{\_}{y}}$ $\hat{b}=\stackrel{\_}{y}-\hat{a}\stackrel{\_}{x}$ $\stackrel{\_}{x}=\frac{\sum _{i=0}^N\left(t_i+\Delta T_0+\Delta t_i\right)}{N}$ $\stackrel{\_}{y}=\frac{\sum _{i=0}^N{T}_s\left(t_i\right)}{N}$

[0057] The equations above are quite complex when compared with conventional phase locked loop equations. The complexity accounts for considerable hindrance in applying least square linear regressive techniques to real decoder systems having finite computing resources. Therefore, it is considered an important part of the invention that the above equations be reduced to more manageable form.

[0058] Since it is a necessary condition that a transmitter clock frequency is close to a receivers clock frequency the following simplifications are implied. Making use of recursion, the mechanism is finally implemented as follows: $\sum _{k=0}^{N-1}{T}_s^2\left(t_i-t_k\right)=\sum _{k=1}^N{T}_s^2\left(t_{i-k}\right)+T_s^2\left(t_i\right)-T_s^2\left(t_{i-N}\right)$ $\begin{array}{c}\sum _{k=0}^N{T}_s\left(t_{i-k}\right)·\left(t_{i-k}+\Delta T_0+\Delta t_{i-k}\right)=\sum _{k=1}^N{T}_s\left(t_{i-k}\right)·(t_{i-k}+\Delta T_0+\\ \Delta t_{i-k})+T_s\left(t_i\right)·(t_i+\Delta T_0+\\ \Delta t_i)-T_s\left(t_{i-N}\right)·\\ \left(t_{i-N}+\Delta T_0+\Delta t_{i-N}\right)\end{array}$ $\frac{\sum _{k=0}^{N-1}{T}_s\left(t_{i-k}\right)}{N}=\frac{\sum _{k=1}^N{T}_s\left(t_{i-k}\right)+T_s\left(t_i\right)-T_s\left(t_{i-N}\right)}{N}$ $\begin{array}{c}\frac{\sum _{k=0}^{N-1}\left(t_{i-k}+\Delta T_0+\Delta t_{i-k}\right)}{N}=\frac{\sum _{k=1}^N\left(t_{i-k}+\Delta T_0+\Delta t_{i-k}\right)}{N}+\\ \frac{\left(t_i+\Delta T_0+\Delta t_i\right)-\left(t_{i-N}+\Delta T_0+\Delta t_{i-N}\right)}{N}\end{array}$ ${\hat{a}}_i=\frac{\sum _{k=0}^{N-1}{T}_s^2\left(t_{i-k}\right)-N·{\stackrel{\_}{y}}_i^2}{\sum _{k=0}^{N-1}{T}_s\left(t_{i-k}\right)·\left(t_{i-k}+\Delta T_0+\Delta t_{i-k}\right)-N·{\stackrel{\_}{x}}_i·{\stackrel{\_}{y}}_i}$ ${\hat{b}}_i={\stackrel{\_}{y}}_i-{\hat{a}}_i·{\stackrel{\_}{x}}_i$ ${\hat{T}}_s\left(t\right)=\hat{a}·t+\hat{b}$ ${\hat{T}}_s\left(t\right)={\hat{a}}_i·t+{\hat{b}}_i$ $t_i+\Delta T_0+\Delta t_i<t<t_{i+1}+\Delta T_0+\Delta t_{i+1}$

[0059] In view of the equations presented above, receipt of several program clock references produces a good and reliable output which forms basis for a receiver time-base. A receiver clock may then be set in accordance with these equations to yield a synchronized system.

[0060] In most instances, it is preferred to receive several tens or even hundreds of program clock references before execution of the equations. Of course, the duration of the startup phase is affected by choice of upon how many data points the calculation is based. Therefore this number will change as startup phase limitations vary from one application to another.

[0061] The equations about are fully implemented in hardware in accordance with drawing FIG. 1 where a block schematic diagram is shown.

[0062] An apparatus of the invention is comprised of electronic components coupled together to form a circuit and to perform the operations described above.

[0063] The block diagram of FIG. 1 sets forth the major elements necessary and shows the connections of these elements with respect to each other.

[0064] As inputs (1,2), a circuit of the invention includes t timing information from a local clock and T_stiming references from received signals. As outputs (3,4), the circuit has values which represent the frequency drift {circumflex over (a)} and time offset {circumflex over (b)}.

[0065] A product operator is performed at a multiplier 5. The values of the local time and the collected clock reference are multiplied together and placed into a buffer 6 and simultaneously an adder 7. The adder output is coupled to a memory 8 which stores the sum values and conveys them to the adder as an input in later operations. Elements 6,7, and 8, form a summation module 9.

[0066] In a separate summation module 10, a buffer and adder 12 receive a value equal to the square of the signal clock reference which is computed and a squaring operator 13. Similar to the adder 7, adder 12 has an output which is coupled to memory for use in following samples.

[0067] Another module 14 is arranged to similarly perform a summation operation on the signal clock references T_s.

[0068] A module 15 performs summation operations on the local time reference t.

[0069] Module 15 has an output which is multiplied at a multiplier 16 with {circumflex over (a)} and then added at adder 17 to the output of module 14. This sum is divided by the number of samples at divider 18 which has an output equal to the time offset {circumflex over (b)}.

[0070] Outputs of summation modules 14 and 15 are multiplied together at multiplier 19 having an output coupled to an input of adder 20. A second input of adder 20 is connected to the output of multiplier 21 which operates to multiply the output of summation module 9 by the number of samples N.

[0071] Output of module 10 is similarly multiplied by the number of samples at multiplier 22. Output of summation module 14 is squared at the squaring operator 23. The previous two results are added at adder 24 having an output which is divided by the output of adder 20 at divider 25 to yield a value for frequency drift {circumflex over (a)}.

[0072] The inputs of the circuit are coupled to the incoming timing indicators. The circuit also uses the arrival time of the indicators as measured in the receivers time base. Accordingly, the estimates of {circumflex over (a)} and {circumflex over (b)} are updated in accordance with the equations above via the circuit described.

[0073] If the collection of program clock reference data elements is considered a window, then it becomes possible to enable sophisticated techniques which yield further information about the transmission systems. For example, if program clock references are received and grouped in windows which are interleaved in time, then it becomes possible to detect changes of long term end-to-end delay which is caused when the transmission path has been rerouted.

[0074] The careful observer will note that on occasion, as is normal in some packet networks, a packet is lost or severely delayed due to a heavy congestion state of the network. In this instance, the program clock references associated with late packets may be discarded or weighted such that its questionable reliability is accounted for in any calculation.

[0075] In accordance with each of the preferred embodiments of the invention, there is provided a method of clock synchronization over data transmission networks. It will be appreciated that each of the embodiments described include a method and that the method of one preferred embodiment may be different than the method of another embodiment.

[0076] One will now filly appreciate how a modified least squares linear regression technique may be applied to program clock references to synchronize clocks at either end of a transmission network. Although the present invention has been described in considerable detail with clear and concise language and with reference to certain preferred versions thereof including the best mode anticipated by the inventor, other versions are possible. Therefore, the spirit and scope of the invention should not be limited by the description of the preferred versions contained therein, but rather by the claims appended hereto.