Patent Publication Number: US-7711009-B2

Title: Methods and apparatus for timing synchronization in packet networks

Description:
FIELD OF THE INVENTION 
   The present invention relates generally to packet transfer networks and, more particularly, to timing synchronization over packet transfer networks. 
   BACKGROUND OF THE INVENTION 
   During operation, telecommunication equipment requires timing synchronization for proper communication purposes. Traditional synchronization methods utilize expensive specialized circuits to provide synchronization signals. Currently, with the prevalence of packet networks, such as, for example, Ethernet, cost can be reduced for timing synchronization by transmitting timing synchronization signals between telecommunication equipment within the packet network. However, due to the store-and-forward operation of packet networks, the synchronization signals or messages will experience an uncertain delay, which will affect the accuracy of synchronization. This uncertainty in delay is commonly referred to as packet delay variation (PDV). To improve timing synchronization accuracy, it is necessary for such delay to be significantly reduced or eliminated. 
   There are two known categories of methods for providing timing synchronization with reduced PDV. These categories include probabilistic filtering algorithms and long time averaging. 
   A probabilistic filtering algorithm filters out any large packet delays and uses the small packet delays for calculation of correction factors and timing synchronization of a local clock of a receive node with a transmit clock of a transmit node. This method usually has high complexity. The process of obtaining satisfactory small delays for calculation is random, therefore, successful performance of the probabilistic filtering algorithms in the short-term is not guaranteed. 
   In a second category, long time averaging provides a method that averages the delay of multiple transferred packets in order to eliminate the PDV. However, in an actual system, obtaining an absolute time is difficult because the local clock of the receive node is not accurate and requires synchronization. Any adjustment of the local clock may adversely affect the result of the delay averaging. Moreover, this method is not flexible, in that the result of the averaging cannot be controlled. 
   SUMMARY OF THE INVENTION 
   The present invention provides a two-parameter low pass filter with feedback control that provides a simple and efficient way to filter PDV of transferred packets. 
   In accordance with one aspect of the invention, a method of synchronizing a first clock of a transmit node and a second clock of a receive node in a packet network is provided. Receive time stamps are generated for transferred packets at a receive node in accordance with the second clock. Propagation delay variation is filtered from receive time stamp intervals through a filter in accordance with a frequency of the second clock. The filtered receive time stamp intervals and transmit time stamp intervals of the transferred packets are input into a phase locked loop to generate a new frequency for the second clock. The filter and the second clock are updated in accordance with the new frequency for synchronization with the first clock of the transfer node. 
   In an illustrative embodiment, receive time stamp intervals may be determined in accordance with the receive time stamps and the second clock. The generating, filtering, inputting and updating steps may also be repeated for the continuously transferred packets. 
   In an additional embodiment, the filter may be a double exponentially weighted moving average filter having one or more weight factors, one or more delay blocks, and one or more state machines. Further, the phase locked loop may be a digital phase locked loop having a phase detector, a loop filter and a numerically controlled oscillator. 
   In accordance with another aspect of the present invention a receive node is provided having a clock generator for generating a first clock. A processor of the receive node is configured to generate receive time stamps for transferred packets at the receive node in accordance with the first clock. A filter of the receive node is configured to filter propagation delay variation from receive time stamp intervals in accordance with a frequency of the first clock. A phase locked loop of the receive node is configured to receive the filtered receive time stamp intervals and transmit time stamp intervals of the transferred packets and generate a new frequency for the first clock. The filter and the first clock are updated in accordance with the new frequency for synchronization with a clock of a transmit node, 
   These and other features and advantages of the present invention will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a diagram illustrating a packet transfer network, according to an embodiment of the present invention; 
       FIG. 2  is a diagram illustrating unidirectional time stamped packet transfer, according to an embodiment of the present invention; 
       FIG. 3  is a block diagram illustrating a clock synchronization system for a packet transfer network, according to an embodiment of the present invention; 
       FIG. 4  is a chart illustrating the power spectrum density of T+PDV; 
       FIG. 5  is a block diagram illustrating a low pass filter for a clock synchronization system in a packet transfer network, according to an embodiment of the present invention; and 
       FIG. 6  is a flow diagram illustrating a clock synchronization methodology in a packet transfer network, according to an embodiment of the present invention. 
   

   DETAILED DESCRIPTION 
   As will be described in detail below, the present invention in the illustrative embodiment relates generally to the field of packet transfer networks and, more particularly, to improved techniques for the synchronization of a first clock source and a second clock source over packet networks having propagation delay. The illustrative embodiment of the present invention introduces a two-parameter low pass filter with feedback control that provides a simple and efficient way to filter PDV of transferred packets. 
   Referring initially to  FIG. 1 , a diagram illustrates a packet transfer system, according to an embodiment of the present invention. A transmit node  102  includes a transmit clock  104 , or master clock, in communication with a transmit node processor  106 . Packets for transfer may be stored in a transfer queue of transmit node and time stamped at transmit node  102  in accordance with transmit clock  104  and transmit node processor  106 . The packets, which include data and timing information, are transferred through a network  108  to a receive node  110 . Receive node  110  includes a receive clock  112  , or slave clock, in communication with a receive node processor  114 . The packets are time stamped again at receive node  110  in accordance with receive clock  112  and receive node processor  114 . Time stamps are provided in accordance with the embodiments of the present invention which synchronize transmit clock  104  and receive clock  112  and eliminate PDV of the transferred packets. 
   Referring now to  FIG. 2  , a diagram illustrates unidirectional time stamped packet transfer, according to an embodiment of the present invention.  FIG. 2  allows for the synchronization of a clock of receive node B with a clock of transmit node A. At times t n  and t n+1 ,the n th  and (n+l) th  time stamped packets receive time stamp values S n  and S n+1  from in accordance with a clock of transmit node A. After some delay, these two time stamped packets arrive at receive node B at times t n +D n  and t n+1 +D n+1 . Receive node B then derives its own time stamps for the transferred packets in accordance with an arrival time of the local clock, R n  and R n+1 . The time stamps of the transferred packets are related to the frequency of transmit node A, f A , and the frequency of receive node B, f B , by the following equations:
 
Δ S   n+1   =S   n+1   −S   n   =f   A ( t   n+1   −t   n )= f   A   T    (1)
 
Δ R   n+1   =R   n+1   −R   n   =f   B ( t   n+1   +D   n+1   −t   n   −D   n )= f   B ( T+PDV   n+1 )   (2)
 
where PDV n+1 =D n+1 −D n .
 
   Let Δf=f B −f A  be the frequency offset between receive and transmit clocks at time t n+1 . If in equation (2), PDV is removed, the ratio of the frequencies of transmit node A and receive node B is then obtained by: 
   
     
       
         
           
             
               
                 
                   
                     f 
                     A 
                   
                   
                     f 
                     B 
                   
                 
                 = 
                 
                   
                     
                       
                         f 
                         B 
                       
                       + 
                       
                         Δ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         f 
                       
                     
                     
                       f 
                       B 
                     
                   
                   = 
                   
                     
                       1 
                       + 
                       
                         
                           Δ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           f 
                         
                         
                           f 
                           B 
                         
                       
                     
                     = 
                     
                       
                         Δ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           R 
                           
                             n 
                             + 
                             1 
                           
                         
                       
                       
                         Δ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           S 
                           
                             n 
                             + 
                             1 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 ( 
                 3 
                 ) 
               
             
           
         
       
     
   
   However, since PDV can be as large as 2 ms in packet networks such as those illustrated in  FIGS. 1 and 2 , huge errors may result if equation (3) is applied. 
   The existing averaging algorithms described above assume that the time stamp difference ΔR n+1  is known in terms of real time, T+PDV. Thus, by averaging ΔR n+1 , T is obtained as:
 
 T=E (Δ R   n )= E ( T+PDV )   (4)
 
since the average of PDV is equal to 0.
 
   If the ΔR n+1  is measured by local clock and the resulting frequency difference in equation (3) is used to adjust the local clock, the above averaging method will produce an unexpected result, such as, for example, the system becoming unstable. 
   This averaging may be regarded as a type of low pass filter, however it is in a fixed form without any parameter to control its behavior. When the filter has a small bandwidth, it has large time constant. Therefore, the adjustment in local frequency will take long time to be reflected in the output of this low pass filter. The consequence is that the local frequency f B  will be over-adjusted. The system will be in an unstable state with the f B  oscillating in a large range around its nominal frequency. 
   Referring now to  FIG. 3 , a block diagram illustrates a clock synchronization system for a packet transfer network, according to an embodiment of the present invention. Such as system is utilized in accordance with transferred time stamped packets and a local clock of the receive node. A receive time stamp, R n , is generated at block  302  for a transferred time stamped packet through the measurement of a receive time stamp interval using a local clock  304 . More specifically the receive time stamp is calculated for the transferred time stamped packet using the local clock as well as the last receive time stamp provided for the last transferred time stamped packet. 
   As described above, the continuously transferred time stamped packet intervals include PDV. Therefore, as receive time stamps for transferred time stamped packets are continuously provided, a double exponentially weighted moving average (D-EWMA) filter  306  is utilized to filter out the PDV from the receive time stamp intervals. D-EWMA filter  306  is a low pass filter (LPF). A LPF is utilized to filter out PDV due to the fact that most of the power of PDV is located in its high frequency range.  FIG. 4  is a chart that plots the power spectrum density of T+PDV. As a low pass filter, low frequencies are passed, but frequencies higher than a cutoff are attenuated or reduced. 
   The filtered receive time stamp intervals and a transmit time stamp interval  308  are input to a digital phase locked loop (DPLL)  310 . DPLL  310  is a closed-loop feedback control system that generates and outputs a signal in relation to a frequency and phase of an input signal. DPLL  310  responds both to the frequency and phase of the input signals, automatically raising or lowering the frequency of a controlled oscillator until it is matched to the reference in both frequency and phase. DPLL  310  includes a phase detector  312 , a loop filter  314  and a numerically controlled oscillator  316 . 
   DPLL  310  outputs an updated local clock frequency used to adjust local clock  304 . In order to overcome the problem of instability described above with regard to existing averaging algorithms, the output clock frequency from DPLL  310  is used to update the state of D-EWMA filter  306 , thereby providing a dynamic adjustment to the filter cutoff for PDV. The updated local clock frequency is also utilized in providing receive time stamps. 
   Referring now to  FIG. 5 , a block diagram illustrates a D-EWMA filter for a clock synchronization system in a packet transfer network, according to an embodiment of the present invention. An individual EWMA applies weighting factors that decrease exponentially. More specifically, the weighting decreases by a factor, or percentage, of the previous. A receive time stamp x(n) is fed into D-EWMA filter  500 , at time n. A first exponentially weighted moving average (EWMA) filter  502  continuously utilizes receive time stamps x(n), a weight a 1 , a state machine s(n), a delay block z −1  and a state update from DPLL to provide a result for use in a second EWMA filter  504 . Second filter utilizes a second weight a 2  in combination with a state machine u(n), a delay block z −1  and a state update from DPLL in a similar configuration to produce a receive time stamp interval output without PDV. The state update from the local clock frequency is provided to both EWMA filters  502 ,  504 . If the state update is ignored, the transfer function of D-EWMA is: 
   
     
       
         
           
             
               
                 
                   H 
                   ⁡ 
                   
                     ( 
                     z 
                     ) 
                   
                 
                 = 
                 
                   
                     
                       a 
                       1 
                     
                     ⁢ 
                     
                       a 
                       2 
                     
                   
                   
                     
                       
                         ( 
                         
                           1 
                           - 
                           
                             a 
                             1 
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         ( 
                         
                           1 
                           - 
                           
                             a 
                             2 
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         z 
                         
                           - 
                           2 
                         
                       
                     
                     + 
                     
                       
                         ( 
                         
                           
                             a 
                             1 
                           
                           + 
                           
                             a 
                             2 
                           
                           - 
                           2 
                         
                         ) 
                       
                       ⁢ 
                       
                         z 
                         
                           - 
                           1 
                         
                       
                     
                     + 
                     1 
                   
                 
               
             
             
               
                 ( 
                 5 
                 ) 
               
             
           
         
       
     
   
   Smaller a 1  and a 2  will result in smaller bandwidth. Choosing different parameters will result in different bandwidths, which also affects the system&#39;s dynamic response. 
   Suppose that the DPLL changes the local frequency f B  by:
 
 f   B ( n+ 1)= f   B ( n )·ζ  (6)
 
   The corresponding state update on the D-EWMA filter will be:
 
s(n) s(n)·ζ
 
u(n) u(n)·ζ  (7)
 
   The above update can be intuitively explained as constant component jump. In the ideal case, the output of low pass filter should only keep its constant component. With the change of local frequency, such constant component is then changed and must be immediately updated in the filter. A low pass filter alone will take long time to provide such an update as described above. Therefore, this state update forces the filter to make a sudden jump which will eliminate the oscillation of frequency adjustment. 
   Referring now to  FIG. 6 , a flow diagram illustrates a clock synchronization methodology in a packet network, according to an embodiment of the present invention. The methodology begins in block  602  where a transferred packets are continuously received at a receive node of a packet transfer network. In block  604 , a local clock provides receive time stamps for the transferred packets. In block  606 , receive time stamp intervals are determined for the transferred packets in accordance with the local clock and previous receive time stamps for previously transferred packets. 
   In block  608 , propagation variation delay of the receive time stamp intervals are filtered out through a D-EWMA filter. The D-EWMA filter is updateable in accordance with a frequency of the local clock. In block  610 , the filtered receive time stamp intervals and transmit time stamp intervals are input to a DPLL to output a new local clock frequency. In block  612 , the D-EWMA filter and the local clock are updated in accordance with the new local clock frequency. The methodology then returns to block  602  for repetition of the methodology in accordance with the updated local clock and D-EWMA filter for the continuously arriving transferred packets at the receive node. 
   The embodiment of the present invention illustrates the use of a D-EWMA filter with feedback control in unidirectional timing transport over packet networks. However, its utilization can be applied to any situation where the PDV is required to be filtered to update the frequency or phase of a local clock. The D-EWMA filter with feedback control has a simple implementation and provides efficient PDV filtering. 
   This embodiment of the present invention can be integrated into hardware (DPLL) without any interference from software. But due to the feedback update on the D-EWMA filter, the frequency of a transmit node may be intentionally changed to introduce large PDV, for observation of the output frequency at the receive node. 
   The present invention may be implemented in the form of one or more integrated circuits or computer programs. For example, a given system node in accordance with the invention may be implemented as one or more integrated circuits comprising at least one processor and at least one memory. Numerous other configurations are possible. 
   In such an integrated circuit implementation, a plurality of identical die is typically formed in a repeated pattern on a surface of a semiconductor wafer. Each die includes a device described herein, and may include other structures or circuits. The individual die are cut or diced from the wafer, then packaged as an integrated circuit. One skilled in the art would know how to dice wafers and package die to produce integrated circuits. Integrated circuits so manufactured are considered part of this invention. 
   Although illustrative embodiments of the present invention have been described herein with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various changes and modifications may be made therein by one skilled in the art without departing from the scope of the invention. It is also possible for the illustrative embodiments of the present invention to be implemented as a software program or any other logical method to process information.