Abstract:
In a digital communications system having widely dispersed nodes  transmitg between each other, a method and apparatus for synchronizing the processing of data at a node. Data transmitted between nodes is stored in speed buffers. The output of each buffer at a node is connected to the nodal processor and is controlled by the nodal clock. Synchronization is accomplished by performing a periodic adjustment of the frequency of the nodal clock. This adjustment is arrived at by sampling the buffer content of each node and extracting an error signal which represents the buffer position relative to the half full buffer position. The error signal is suitably weighted by a control and summed with all other weighted buffer error signals to produce a total error signal, which is added linearly to the original initial condition of the nodal clock and converted to an equivalent frequency.

Description:
The invention described herein may be manufactured and used by or for the Government for governmental purposes without payment of any royalty thereon. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to a timing and synchronization by which a digital communication system, composed of many nodes interconnected by transmission paths characterized by various media, can be brought into synchronism. The signals on these transmission paths are asynchronous with respect to one another. The invention further relates to clock synchronization at system nodes especially but not exclusively to nodal subsystems that require a timing signal for operation, for example, time division multiplexers, modulation devices, security devices, or the nodal processors in communication switches. 
     2. Description of the Prior Art 
     For a multi-node digital communication, the maintainance of clock synchronism at all nodes is a formidable problem. The use of highly stable clocks, one at each system node, has been proposed as a solution to the problem, but this proposal appears to have certain deficiencies. The timing device would be expensive and the clock system would require periodic adjustment necessitating interruption of received transmission at a node caused by differences in the received transmission rates varying as a function of such physical transmission line characteristics as temperature, humidity and atmospheric disturbances. 
     Another proposed solution is a common timing signal transmitted from a single designated node to all other system nodes. This proposed solution appears to have certain deficiencies in that it would require an expensive timing signal transmission system to insure that the timing signal to all other nodes was not lost anywhere in the system. Furthermore, transmission path delay variations, as previously mentioned, would cause the nodes receiving the timing signals to respond to these variations and hence these clocks would exhibit timing transients which would result in abnormal nodal operation. Since timing of high bit rate digital streams is critical, a transient timing signal would make such time almost impossible. 
     A technique to achieve nodal synchrony is disclosed by J. S. Mayo in U.S. Pat. No. 3,136,861 issued on June 9, 1964. In accordance with that invention, each pulse signal to be multiplexed has its pulse repetition rate raised to a common repetition frequency by the insertion of control signals into the pulse signal. After multiplexing, transmission, demultiplexing and receiving the transmitted signals, predictive techniques are employed to remove the inserted control signals even in the presence of large transmission error rates. The predictive techniques determine when a control signal should have occurred in the transmitted signal, and when a control signal is lost due to transmission error. This determination is used to minimize the loss of information due to framing error. In addition, because of the composition of waveforms of higher frequency and the predictive techniques employed, there is no necessity for transmitting additional information regarding the composition of the signals of higher frequency. Because the control information is inserted into the original pulse signal at the originating node and transmitted to the receiving node, it must be received error free. If not, the necessary removal of the control information pulse may not occur, and though the control information is received correctly, it is used to delete pules from the data stream thereby creating gaps in the stream which must be smoothed to restore the pulse stream to its original form. This action must be accomplished before the pulse stream can be processed at the receiver node. For example, if the pulse stream were originated at a node and destined for a distant node and the path traversed several interim nodes, this addition and deletion of control information would be accomplished between every node path in the pulse stream path. 
     A disclosure in U.S. Pat. No. 3,042,751 issued to R. S. Graham on July 3, 1962 discloses a technique for achieving system synchrony that preceeded Mayo&#39;s disclosure. Although similar in structure, Graham&#39;s techniques used a variable delay insertion technique for control. However, unlike Mayo&#39;s disclosure, the delay was encoded and transmitted on a separate channel than that of the transmitted pulse signal being controlled. This technique reduces available channel capacity with respect to other pulse stream transmission. For this technique, the control information is subject to the same problems of error free transmission as with Mayo&#39;s, but in addition, the control channel must not fail. Otherwise, control information of the pulse stream would be completely lost. 
     Another technique to achieve network synchronization was disclosed by W. T. Deurdoth in U.S. Pat. No. 3,467,779 issued on Sept. 16, 1969. In this disclosure, a continuous correction derived from a pulse stream interim storage element under control of a master timing oscillator was used to increase or decrease the frequency of the master timing oscillator depending on the state of the storage element. Because of the continuous nature of the frequency correction applied to the master oscillator, any disruption of the pulse stream would cause immediate changes in the state of the storage element which would immediately cause the master oscillator to change frequency. But this would cause disruptive changes in the timing of other streams under the control of the master oscillator. This affect would propagate to other nodes through pulse streams timed by the master oscillator and a timing transient would result. 
     SUMMARY OF THE INVENTION 
     It is the object of the present invention to obviate the need for control pulses inserted into the pulse streams or control pulses transmitted on a separate channel to a node receiving the pulse streams to accomplish synchronization. 
     It is a related object of the present invention to eliminate the need to continuously correct a master oscillator that provides timing for nodal functions. 
     It is a further related object of this invention to diminish the suceptibility of the equipment providing nodal synchronization to transmission line anomalies, to line dropouts, or to the malfunction of nodes from which it receives pulse streams. 
     According to the present invention, the switching system of a digital communication network has a stable voltage controlled crystal oscillator (VCXO) to provide timing for functions such as TDM and modulation and demodulation, and nodal processor operation. Together with the VCXO interim storage devices are provided to accomplish link synchronization, into which the received demodulated pulse stream is read under the control of a recovered pulse stream timing signal. The VCXO provides the timing signal to read the pulses out of the storage device. Periodically at a node, all storage devices are sampled and error signals are derived, summed and weighted in a prescribed manner. This total error signal is then used to increase or decrease the frequency of the VCXO of the node. This sampling is performed periodically where the period for applied corrections may range over minutes to many hours and is a function of the number of nodes in the network, the storage device size, the VCXO specifications such as gain, setability, accuracy and drift, and transmission media anomalies. As a consequence of these periodic corrections, the VCXO will respond by increasing or decreasing its timing signal to provide the storage readout signal for the pulse stream to be input to the nodal processor. 
     This procedure for synchronizing a node in a digital communications system is further refined by using a control strategy that reacts to a rapid increase or decrease in the fill in an individual storage element. The control mechanism detects the rapid change in the state of the storage element indicative of a transmission path failure, or nodal failure and drops that line in the weighting process to derive a correction signal to the BCXO. The interim storage is sized to respond to transmission path variations, for example, those characterizing the troposcatter medium. As a result, this synchronization equipment is sensitive to failures of that part of the network from which it receives communication, a desired effect, but this sensitivity is used constructively to enhance nodal synchronization and so that system malfunctions are not propagated to other parts of the network. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The following detailed description will enable the invention to be more fully comprehended. A list of relevant figures accompanies the description in which: 
     FIG. 1 is a block diagram of a portion of a digital network in accordance with the invention; 
     FIG. 2 is a block diagram showing a nodal synchronizing apparatus used in a system with a multiplicity of incoming pulse streams; 
     FIG. 3 is a diagram of the timing recovery, interim storage and control subsystem of the invention; 
     FIG. 4 is a diagram of the clock control; 
     FIG. 5 is a diagram of the voltage controlled crystal oscillator; 
     FIG. 6 is a graph of the VCXO operational function; and 
     FIG. 7 is block diagram of a conventional logic switch used to periodically sample a circuit. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     A portion of a digital communication network in accordance with the presentinvention is shown in block diagram form in FIG. 1. Nodes of this network that could represent switching center 1, 2, . . ., 5 are interconnected bymeans of transmission paths of possibly various media types. These nodes are interpreted as being geographically separated. Pulse streams carried via the transmission media are input to each node. These streams may be ofdifferent rates and are considered to be asynchronous with respect to one another. In order that the node be able to process the streams simultaneously they are input to a synchronizing unit 6, 7, . . ., 10. These units place the streams into synchrony with respect to one another and then the streams are input to the nodal processors 11, 12, . . ., 15, where they are transmitted to some terminating device as to another node. 
     FIG. 2 shows a functional block diagram of the synchronization method in accordance with the present invention. Node i receives data streams. Thesestreams 16, 17 are demodulated and are input to timing recovery circuits 18, 19 and interim storage devices termed buffers 22, 23. The timing recovery circuits extract timing information from the received data streams in order to provide timing signals 20, 21 that the data streams may be read into the buffers. A buffer is provided for each incoming transmission line. Periodically, the buffers are sampled to provide signals 24, 25 that are input to the clock control mechanism 27. These signals are weighted and algebraically combined to provide a single signal29 in the form of an equivalent voltage that is input to a stable voltage controlled crystal oscillator (VCXO) 30. The oscillator accepts this signal and uses it to change its frequency, either increasing or decreasing it as appropriate. This new frequency 31 is then used as a buffer read timing signal to read the pulse streams 26, 28 from the buffer. This new frequency is also input to the nodal processor 32 to be used for timing purposes within this unit. The output of the processor is transmitted to either terminating devices 33, 34 or to other nodes 34, 36. 
     FIG. 3 shows a block diagram of the timing recovery, interim store element and control logic subsystem of the synchronization system in accordance with the present invention. The timing recovery circuit 18 is of the conventional type and can be a phase or frequency locking device. This recovery device accepts the incoming signal 37 and produces a timing signal 20 that is input to a phase comparator 38, which extracts the phaseof the timing signal and compares it with that of the node clock timing signal 39. The phase difference gates an up/down counter 40. The counter outputs a signal 41 to the storage control logic 44. This logic then movesa buffer pointer up or down in accordance with the counter signal. This buffer control uses the node clock timing signal 42 for its operation. Theinterim storage element 52 is a first in -- first out shift register where each cell of the register stores one element of the pulse stream. As new elements of this pulse stream enter the register, the elements occupying the register are advanced one position at a time. Thus each new element entering the register advances all the existing elements in the register one position. The storage control logic output 45 functions as the pointerto the leading element in the register. Each element in the register is read out under control of the local node clock signal 50. The initial setting of the buffer is at the half full position. If the phase of comparison of the recovered timing signal 20 and the local clock timing signal 39 is positive π radians, the pointer is retarded one cell. The position of the pointer in the register indicates the cell at which the elements are read out. If the pointer is stationary, the node will be in synchrony with the remaining network nodes. The storage 52 contains presetthresholds T 1 , T 2  at the low side 48 and at the high side 49. If the pointer moves below the T 1  threshold, a signal 46 is sent to the storage control logic 44 and outputed 43 to an inhibit gate 51. This gate passes timing 31 from the local node clock for storage read out signal 50.If it receives an inhibit signal 43 from the storage control logic 44 the gate 51 is enabled and read out from the storage ceases since timing 31 isnot passed. The same action occurs at threshold T 2  at the upper end ofthe register. To prevent a premature readout inhibit if the signal 47 is still present, the buffer is sized to account for nodal clock anomalies such as path delay variation that cause pointer excursion. Hence, these thresholds will be reached if the input signal 47 is lost or inhibited in any manner. Under normal operation the pointer will move up or down depending upon the up/down counter indicator. Under normal operation, however, it is a characteristic of a stable VCXO to drift in frequency in a slow manner. The buffer, however, is sized to account for this drift anomally so that it would not require resetting for extended time periods as are desired. 
     FIG. 4 shows the clock control unit that is part of this invention. The counters 58, 59 monitor the pointer position with respect to the half fullor zero buffer position. At a specific interval of T seconds these countersare sampled by logic switch 60 and the resulting digital signals are input 85, 86 to a digital to analog converter 61. The resulting analog signals are then individually weighted 62, 63 according to pre-determined weighting factors α and combined by summer 60 to form one analog signal. 
     The combined signal is amplified 65 and then output 29 to a voltage controlled crystal oscillator 30. The resulting signal from the oscillatoris used for necessary timing purposes as buffer readout, node processing and all logic timing. 
     Referring to FIG. 7, a conventional sampling circuit is illustrated. Counter outputs 83, 84 are connected to one of the inputs of standard AND gates 80, 82. To the other input of the AND gates 80, 82 are connected to trigger circuit 81 consisting of an integrated circuit with external resistor and capacitor components preset to pulse every T seconds. 
     Mathematically, the synchronization method is modeled at the ith node by the difference equation: ##EQU1##where n denotes the nth sample, n = 0, 1, 2, . . ., and f i  (O) is the initial frequency of operation at the time the ith node is set into operation. Considering all system nodes, then the equation in matrix form becomes: ##EQU2##where G is the accuracy gain factor of the nodal clock 30, where F(O) is the vector of initial condition and A is the matrix of weighting multiplied by the common gain-time product, and is given by: ##EQU3##Propagating equation (2) forward and collecting terms 
     
         F(nT) = [A + I]F(O) = [A + I].sup.n F(O)                   (4) 
    
     where I is the identity matrix of order n. Because the row sums of matrix [A + I] are unity, it is a singly stochastic matrix. For a stable system, all eigenvalues of A must be less than or equal to unity. Then it is a function of the stochastic matrix that in the steady state lim n  .sub.→  &#39;]A  + I] n  exists and if H = [1, 1, 1, ..., 1].sup.τ, where τ denotes the transpose of a matrix, then in steady state 
     
         lim.sub.n .sub.→ .sub.∞[A + I]F(O) = βH  (5) 
    
     where β is a scalar and is the weighted average of the initial condition frequencies of the network nodes. Equation (5) implies that one of the eigenvalues is unity and the remaining eigenvalues are less than unity. Since α ij , i and j = 1, 2, ..., n, and the GT product isfree to be chosen to achieve network stability, the range of their values to assure stability is investigated. 
     Let x i  (k) be the buffer level in each jth buffer at node i, and let x i  (k) be the composite buffer equal to Σx ij  (k) at the kth sample, then 
     
         x(k+l) = x(k) + TCF(k)                                     (6) 
    
     where C is the network connectivity matrix of ones and zeros. 
     Let GTα ij  = σ i  for i≠j, j=1, 2, ..., n. Then equation (1) is written as 
     
         f.sub.i (k+1) = f.sub.i (1) + σ.sub.i [x.sub.i (k=1) - x.sub.i (k)] (7) 
    
     where i = 1, 2, ..., n. 
     This set of equations forms the matrix equation 
     
         F(k=1) = F(k) + diag(σ.sub.1. . ., σ.sub.n)[x(k+1) - x(k)] = I + diag(σ.sub.1, ..., σ.sub.n)C[x(k+1) - x(k)] 
    
     or 
     
         F(k) = (I + AC).sup.k F(O) k ≧ O                    (8) 
    
     where A = diag(σ l , ..., σ n ). 
     Let λ 1 , . . ., λ n  be the eigenvalues of AC, with A and C symmetric. λ l , ..., λ n  are real. Let E = nσ i  I + AC and consider σ l  = max(σ i  : i =1, ..., n). Then AC = -nσ l  I + E. If θ 1 , ..., θ n  are eigenvalues of E, then λ i  = -nσ l  + σ i . This implies all of θ i  are real. From the definition of C with all λ i  positive, then e ij  = λ i  C ij  ≧ O, i≠j, and C ij  = ##EQU4##C ij  ≧ - (n-1). This implies e ii  = nσ i  + σ i  C ii  ≧ σ l  &gt; O, if all σ i  assumed &gt; O. Therefore, E is a non-negative square matrix in which row sums are nσ l , and |θ l  | ≦ nσ l , i = 1, 2, ..., n. Because C represents a connected network, it is irreducible and having assumed σ i  &gt; O, i = 1, 2,. . ., n, then AC and E are irreducible. This implies there exists only one θ i , say θ l , such that θ l  = nσ l . 
     Since σ i  ≠ O, i = 1, 2, ..., n, then √A = diag (√σ 1 , √σ 2 , ..., √σ n )is non-singular and (√A) -   1  = √A -   1  = diag (√σ 1   -   1 , ..., √σ n   -   1 ), Let D = (√A) -   1  E√A = nσ l  I + (√A)C√A. Now D is symmetric and has the same eigenvalues as those of E. Let there exist a vector y andconsider y.sup.τDy. 
     
         y.sup.τDy = nσ.sub.l (y.sup.τy) + ny.sup.τ(√A)C(√A)y                      (9) 
    
     Let c = -I + P where P is positive semi-definite. Then equation (9) is written: 
     
         yθDY = n ##EQU5##(σ.sub.1 - σ.sub.i) y.sub.i.sup.2 + n[√A(y) ]θD[√A(y)] ≧ O                        (10)  since σ.sub.1 = max (σ.sub.i) and P is positive semi-definite. Therefore, D is positive semi-definite with non-negative eigenvalues, and θ.sub.i ≧ O, i = 1, ..., n. Hence, θ.sub.l = nσ.sub.1 and O ≦ θ.sub.i &lt;  nσ.sub.l i = 2, ..., n. Now λ.sub.1 = O and -nσ.sub.l &lt; λ.sub.i &lt;0, i = 2, ..., n. Suppose β.sub.i are eigenvalues of [I + AC]. Then, β.sub.i = 1 + λ.sub.i, i =0 1, 2, ..., n or β.sub.l = l, 1 - nσ.sub.1 ≦ β.sub.i &lt; 1, i = 2, ..., n. 
    
     If O &lt; σ i  &lt; n/2, = 1,2, ..., n, then -1 &lt; 1 - nσ l  = 1 - n.sup.. max(σ i ) &lt; 1 and therefore, β l  = 1 and β i  &lt; 1, i = 2, ..., n. Now σ i  = GTα i  for the system. Hence, 
     
         O &lt; GTα.sub.i &lt; 2/n                                  (11) 
    
     establishes the stability bounds. That β 1  = 1 and β i  &lt; 1 i = 2, 3, ..., n indicates that the system has one and only one unit eigenvalue. Consequently, the network node frequencies will converge to a weighted average of the base frequencies as described by equation (5). 
     In order to perform the above analysis, a model of the VCXO 30 was assumed.This model is identified in FIG. 5. The input 29, which is in the form of avoltage, is connected to the input of the VCXO control 87. The voltage to frequency converter (VFC) 88 is a nonlinear device which converts the error input voltage 29 to an equivalent frequency 31. In effect, the inputvoltage 29 is used to adjust the operating frequency 31 of the VCXO. The error signal 29 from the clock control 27 is received by a delay circuit 69 which functions to pass the signal gradually over a given period of time which is much less than the correction period T. The delay circuit 69output is connected to the input of a holding circuit 90 which is a power supply having a continuous voltage output equal to the last received voltage input. Power supply 67 provides a continuous voltage signal which corresponds to the initial operating frequency. The outputs of the power supply 67 and the holding circuit 90 are added linearly to form an output voltage signal 89 which corresponds to the operating frequency 31. This signal 89 is fed into a voltage to frequency converter 88 which converts the signal to the equivalent operating frequency 31. 
     The VCXO in the invention does not function in the usual manner of a voltage controlled crystal oscillator. In the usual manner, the oscillatoroperating frequency, at the time of each correction, is used as a basis around which the correction is made. In this invention, the basic frequency around which the periodic correction is made is that stored in the power supply 87 as an equivalent voltage at the time the node is brought into operation and not the operating frequency of the oscillator at the correction time. 
     The VCXO function operation is shown in FIG. 6. The initial operating frequency, f i  (0) is maintained by the power supply 67 as an equivalent constant voltage. At time T seconds, the first correction is made. The voltage increment is ΔV i  (T) and is assumed positive.The conversion for ΔV i  (T) is Δf i  (T) which is added to f i  (O) to produce a new operating frequency f i  (T). As discussed, the addition does not produce f i  (T) immediately. Rather, the addition is carried out over a given time interval much less than the correction period T. The operating frequency f i  (T) is not changed until the next correction time approximately T seconds later. At that time, t = 2T, a new correction ΔV i  (2T), assumed negative, is made. The correction is not made to the operating frequency f i  (O) + Δf i  (T) but rather to f i  (O), the basic frequency. The newfrequency, f i  (2T) = f i  (O) + Δf i  (2T), is now used over the time period until the next correction at t = 3T seconds. If the oscillator were operating in the usual manner, the new operating frequencyat t = 2T would be f i  (2T) = f i  (O) + Δf i  (T) + Δf i  (2T). However, this usual operation is not evidenced in this invention. 
     In the ideal situation, when the steady state is reached, say at node i andtime t = ST, ΔV i  (ST) = O and f i  (ST) = f i  ((S-31 l)T). Since f i  (ST) = f i  (O) + Δf i  (ST) and f i  ((S-l)T) = f i  (O) + Δf i  ((S-l)T) then 
     
         Δf.sub.i (ST) = Δf.sub.i ((S-l)T)              (12) 
    
     equation 12 is accomplished by the apparatus through the function of the holding circuit 90. Since the holding circuit is a power supply with a continuous output equal to the input of the last voltage signal received by it, when the error input voltage 29 is zero at the steady state time t = ST, the holding circuit 90 continues to output the last signal received at time t = (S-l)T which results in Δf i  (ST) = Δf i  ((S-1)T). Therefore, f i  (ST) = f i  ((S-1)T) and the steady state operating frequency is maintained. 
     Because the synchronization scheme allows for the selection of the weighting factors α ij , j≠i, i=1, 2, ..., n, then by adjusting those factors, the synchronization can be configured as a master-slave system, an independent node system or a hierachical system. For a master-slave system, one node is designated the master, say node k, and if there are m input lines then α kj  O, k≠j, j=1, 2, ..., m. That is, the master node is not corrected but rather distributes its time to all other nodes which operate in the manner described in this invention. The result of the repeated corrections is that all other node frequencies in the system will approach the master node frequency and in steady state will equal this frequency. 
     In an independent node system all α ij  = O at each node indicating that no corrections are made to any clocks. Here the oscillators are independent and free running. For a hierachical system, some of the α ij  &#39;s at each node may be weighted more heavily than others. This indicates that certain nodes in the network are to be given more weight than others and have more influence on the weighted average steady state network operating frequency. Hence, a nodal hierachical structure may be super imposed on the network. In all cases, the stability constraint, O &lt; GTα ij  &lt; 2/n, must be satisfied for all weighting factors α ij  at all nodes in the system. 
     The mathematical development given here is predicated on the fact that all nodes must correct simultaneously and carry T seconds. For this invention,the more general case, nodes correcting approximately every T seconds and not all correcting simultaneously still has the stability boundary as derived, and the network will converge to a weighted average of the base frequencies. However, the convergence will take a greater time and more correction than that of simultaneous correction.