System and method for clock synchronization over packet-switched networks

[0001] This application takes priority from U.S. Application to Fellman entitled “METHOD FOR CLOCK SYNCHRONIZATION OVER PACKET-SWITCHED NETWORKS” filed Jul. 19, 2004, Ser. No. 60/521,904 is hereby incorporated herein by reference. U.S. Application to Fellman entitled “METHOD AND SYSTEM FOR PROVIDING SITE INDEPENDENT REAL-TIME VIDEO TRANSPORT OVER PACKET-SWITCHED NETWORKS” filed Jul. 7, 2004, Ser. No. 60/521,821 is hereby incorporated herein by reference. U.S. application to Fellman entitled “METHOD AND SYSTEM FOR PROVIDING SITE INDEPENDENT REAL-TIME MULTIMEDIA TRANSPORT OVER PACKET-SWITCHED NETWORKS” filed Jul. 7, 2005, Ser. No. 11/177,507 is hereby incorporated herein by reference.

[0002] 1. Field of the Invention

[0003] Embodiments of the invention relate generally to synchronizing clocks over packet switched networks, such as the Internet. More specifically, but not by way of limitation, embodiments of the invention relate to minimizing the effects of queuing delays on a transmitted timing signal.

[0004] 2. Description of the Related Art

[0005] The advent of low-cost broadband Internet connections has created a demand for packet-switched networks, including the Internet itself, for the transport of audio, video, and other time-sensitive real-time signals. Systems that receive live or real-time signals over packet-switched networks, such as live audio and video streaming servers, video conferencing systems, or distributed real-time computing systems, require access to a local time clock that can maintain phase and frequency synchronization to the remote transmitter's clock. Such a synchronized local clock provides a reference against which a time stamp, either embedded within the real-time signal itself or stamped within an encapsulating packet, can determine an appropriate play-out time for an audio or video rendering engine at the receiver. However, the large queuing delays that arise in packet-switched networks, such as the Internet, induce significant packet timing jitter. Such jitter has traditionally been an impediment to live Internet streaming.

[0006] Traditionally, Internet streaming media applications employ large amounts of spooling, on the order of 10 seconds to over a minute, to handle Internet jitter. Unfortunately, live interactive audio and video applications require that end-to-end latency be under 500 milliseconds, and preferably less than 100 milliseconds. The reduction of latency to such low levels requires the use of precision clock synchronization. Precision clock synchronization enables the minimization of jitter queue size. The problem is that traditional clock recovery mechanisms for clock synchronization, such as phase-locked loops (PLLs), generally cannot handle such large Internet jitter levels.

[0007] The technical literature contains many references to phase and frequency locked loops and other clock recovery techniques for synchronizing a local clock to a remote clock with high precision and low jitter, provided that the jitter of the input signal does not exceed the design parameters of the clock recovery mechanism.

[0008] Unfortunately, congestion in packet-switched networks induces queuing delays that often add substantial jitter to these real-time signals. (We define jitter as the maximum variation in inter-packet arrival time.) The resulting jitter may impair the operation of standard clock recovery mechanisms and rendering engines. Consequently, standard real-time clock recovery mechanisms often do not work well when synchronizing to a timing signal transmitted across a packet-switched network, such as the Internet.

[0009] Buffering the input packet stream can eliminate jitter problems at the rendering engine. Buffering incoming packets with an input queue can eliminate network packet jitter, provided that the input queue is large enough to absorb all of the jitter, and that the packets are read out of the input queue at a constant rate that matches the average rate at which incoming packets are received. As long as this jitter removal queue neither overflows with packet loss, nor underflows to interrupt the smooth flow of data, then the rendering engine can function properly. However to prevent queue underflow or overflow, the use of such a de-jitter queue requires a synchronized local play-out clock that substantially tracks the frequency and phase of the remote clock generating the packetized data. Here again, jitter can impair the ability of a clock recovery mechanism to provide a synchronized clock for the jitter removal buffer.

[0010] One recent patent titled, “Minimizing the effect of jitter upon the quality of service operation of networked gateway devices” (U.S. Pat. No. 6,704,329, Martin, G.), claims a method to reduce the effects of network jitter that involves filtering a phase error by a minimum-delay filter to generate a control signal to control the frequency of a variable-frequency oscillator as part of a clock recovery mechanism. While this may produce a stable, low-jitter recovered clock from a high-jitter timing signal, it does not guarantee a low phase error. The slow response of a filtered control signal to adjust the frequency of a reference oscillator is generally a slow process that may allow significant phase drift in the reference clock. Furthermore, if the goal is to simply remove jitter so that a standard PLL can later recover the clock, then the additional step of generating a digital control signal is superfluous and adds implementation cost and complexity.

[0011] An embodiment of the invention provides a simplified mechanism for synchronizing a local clock to a remote clock over a packet-switched network comprising significant packet jitter. A shortest-delay offset generator attenuates the effects of network jitter on transmitted timing data to allow the adaptation of standard clock recovery and jitter removal mechanisms, and facilitates the replacement of more traditional circuit-switched communications with packet-switched transport and Internet links. The synchronization of a local timing reference to a remote clock facilitates the use of a de-jitter queue and other such buffer mechanisms to provide basic quality of service filtering, such as jitter removal, packet reordering, and error correction, to improve the ability of a packet-switched network to handle live time-sensitive signal streams.

[0012] In one application of the invention, the simple addition of the jitter-filtered phase offset to a local free-running clock provides a clock adequate to drive quality-of-service (QoS) packet processing buffers, including queues for jitter removal, restoring packet order, and error correction. By constraining a phase offset adjustment so that it does not change too quickly, this clock recovery mechanism can provide a clock in applications that need higher resolution, such as video and audio playback.

[0016] FIG. 1 shows an embodiment of the invention that provides a simplified mechanism for synchronizing a local clock 3a in a receiver to a remote clock 1a at a transmitter over a packet-switched network 2 comprising significant network packet jitter. FIG. 2 provides more detail for an embodiment of a clock recovery mechanism 3c and quality of service (QoS) mechanisms 3b. In this embodiment, the clock recovery mechanism 3c uses a shortest-delay offset generator 31 to attenuate the effects of network jitter on transmitted timing data to allow the effective implementation of quality of service mechanisms 3b and standard clock recovery techniques. An effective implementation of QoS mechanisms 3b can mitigate the adverse effects of packet-switched communications networks and thereby facilitate the replacement of more traditional circuit-switched communications with packet-switched transport and Internet links. Effective synchronization of a local timing reference 3c to a remote clock 1a also facilitates the use of a de-jitter queue 35, error correction mechanisms 36, and other such QoS mechanisms to provide basic quality of service filtering, such as jitter removal, packet reordering, and error correction, to improve the ability of a packet-switched network to handle live time-sensitive signal streams.

[0017] In order to understand how a shortest-delay offset generator can provide an efficient mechanism for jitter filtering, we model the end-to-end network transport delay as the sum of a constant propagation delay plus a variable queuing delay. The constant propagation delay comprises the sum of the speed-of-light propagation delay of the individual links plus the (approximately constant, unqueued) processing time at each node. This constant propagation delay factor excludes any queuing effects and thereby represents the minimum propagation delay through the network.

[0018] Queuing delay at each node adds a variable amount of delay to this minimum propagation time. Thus for an unloaded network, a packet will not experience any queuing delays as it propagates from the source to its destination. Such packets will arrive at the destination after traveling through the network for the minimum propagation delay time. We define the fundamental network propagation delay as the propagation delay time for a packet that travels from source to destination without encountering any queuing delay.

[0019] As the loading on this network increases, packets begin to experience varying amounts of queuing delay. In a lightly loaded network most packets will not experience any queuing delay. Furthermore we will assume that as long as the network does not overload, such that the sum of the arrival rate of all packets entering a node, and bound for a particular egress link, does not exceed the link rate of their egress link, nor exceed the packet processing rate of the node itself, then a significant percentage of packets will not experience any queuing delays. Further assuming equal priority for all packets entering a node in this case, those packets that do experience delays will generally only wait, at most, a single packet transmit time per queue at each node where they might be delayed. Restating this observation another way: if the probability for a packet to encounter queuing delay at any given node is less than one, then the probability of a packet being delayed at multiple nodes decreases exponentially as the number of nodes of delay increases.

[0020] Timing diagrams 2a and 2b in FIG. 1 show the effect of queuing-induced jitter on packets carrying timing information. Timing diagram 2a shows how four packets, P₁ through P₄, enter the network without jitter. In other words, they each have a constant delay T between them. Upon emerging from the network, timing diagram 2b shows packet P₂ having incurred an additional delay of ΔT₂ and packet P₃ incurring an additional ΔT₃ of delay. As a result of this network jitter, three of these timing packets, P₂ through P₄, arrive at the receiver in a burst.

[0021] The mechanism for clock recovery 3c of one embodiment of the invention comprises determining the constant fundamental propagation delay of the network and using this delay as a constant phase offset 33 to a local reference clock 3a having nearly the same frequency as the source clock 1a. Because the probability distribution of incoming packets favors those packets with smaller delays, and because the propagation time for packets with the shortest delay most closely matches the constant network propagation delay, we can use the delay time of packets with the shortest delay as an estimate of the fundamental network propagation delay. Thus, delay times for packets filtered by a shortest-delay offset generator 31 can be used to estimate the phase offset 33 for local clock recovery.

[0022] One embodiment of the shortest-delay offset generator 31 takes the difference 30 between the local clock 3a time and the incoming packet timestamp to generate raw phase offset values. FIG. 3 shows one embodiment of the shortest-delay offset generator in more detail. The raw phase offsets sequentially enter a sliding window buffer 310 of a shortest-delay filter mechanism 31a. A comparator 312 determines the minimum value among all values in the sliding-window 310 and stores this minimum value in memory or a register 311. In one embodiment of the invention, the minimum value is found by means of a linear search. The shortest-delay filter 31a outputs said minimum value, where it can be either used directly to produce filtered offset correction 33 or it can be fed to an averaging filter or to a ramp-rate limiter to constrain the rate of offset adjustment to smooth out residual jitter variations. If 31b is used, then the output of 31b produces a filtered offset correction 33.

[0023] Another embodiment of the minimum value generator 312 feeds the values of the sliding window buffer 310 to create a balanced binary tree within 312, where the tree node's contents are an offset and a reference counter. Balanced binary trees are well known in the art. One reference that teaches their implementation is: “Art of Computer Programming, Volume 3: Sorting and Searching, 2nd Edition” by Donald E. Knuth (ISBN: 0201896850, Publisher: Addison Wesley Professional). (We shall consider a balanced binary tree as having N nodes and Log₂N levels.) Because the distribution of queuing delay across a network 2 generally follows a Poisson or Exponential distribution, N can be much smaller than the number of offsets in the sliding window buffer. As a result, a sliding-tree embodiment of 312 for finding the minimum among the values stored in the sliding window 310 can be faster and more efficient than a linear search embodiment of 312.

[0024] For example, if the sliding window size is 100 and the number of nodes in the tree is 16, a linear search requires 100 comparisons whereas a tree search would require only traversing 4 nodes (a balanced binary tree has log₂N levels where N is the number of nodes in the tree). When offsets are inserted into the sliding window 310 they are also inserted into the tree in 312 and when offsets are deleted from the sliding window 310 they are also deleted from the tree in 312. When an offset is inserted into the tree in 312 for the first time, a new node is inserted into the tree and the reference count is 1. The insertion of each subsequent offset increments the reference count for a node having the same offset. When offsets are deleted the reference count is decremented. And, when the reference count becomes zero the node is deleted from the tree.

[0025] In a basic application of the invention, the simple addition 32 of the jitter-filtered phase offset 33 to a local free-running clock 3a provides a clock adequate to drive quality-of-service (QoS) packet processing buffers 3b, including queue 35 for jitter removal and restoring packet order, and error correction mechanism 36. By constraining a phase offset adjustment so that it does not change too quickly, this simple clock recovery mechanism can provide a clock in applications that need higher resolution, such as video and audio playback.

[0026] Embodiments of the invention utilized in QoS applications excel in environments comprising: 1) the frequency variation among local free-running time references 1a and 3a at multiple similar nodes across a network is relatively small; 2) the primary cause of network-induced jitter is packet queuing delay; and 3) the distribution of queuing delay across a network 2 generally follows a Poisson or Exponential distribution and therefore giving rise to the highest probability occurring when a packet experiences minimal queuing delays.

[0027] The clock synchronization mechanism 3c of the present invention adds a filtered phase offset 33, at regular time intervals, to a free-running local oscillator 3a to continuously align the phase of the local recovered clock 34 to that of a remote clock 1a. Directly adding the filtered phase offset 33 to a free-running clock 3a, rather than generating a control signal to indirectly adjust a clock's frequency, insures close phase alignment of the local clock reference and simplifies implementation.

[0028] The addition 32 of a filtered phase offset 33 to a local clock 3a at regular, but not necessarily periodic, time intervals creates a time reference at a receiver that continuously adjusts clock drift so that it also maintains substantial frequency synchronization to the remote clock of a transmitter communicating over a packet-switched network. If the local free-running clock 3a can be assumed to run at substantially the same clock frequency as the remote clock 1a at an audio/video source node, then the phase drift due to any mismatch between the local and remote clocks that might accumulate between successive phase adjustments is negligible.

[0029] As compared with other approaches that generate a control signal to control a variable-frequency oscillator, this embodiment has the advantages of quickly adjusting to phase errors, of not requiring the implementation or control of a variable-frequency oscillator, and quickly adapting to and eliminating phase drift errors in the recovered clock 34. Although the recovered clock 34 may exhibit larger jitter than approaches involving a control signal and a variable-frequency oscillator, however provided that jitter filter 31 includes a large enough window of data, our measurements show that the resulting jitter in recovered clock 34, over a wide range of typical Internet connections, is small enough such that subsequent standard clock recovery processing can effectively recover a stable clock.