Apparatus and Methods Achieving Multiparty Synchronization for Real-Time Network Application

1. Field of the Invention

The present invention relates to a method and an apparatus for synchronizing packets arriving at a receiver (a computer host in the network, which may be a regular participant or a central host) from other hosts, and those packets when "played back" at the receiver (played back for voice packets; displayed for video packets) have to conform to certain timing relations among them. The determination of the set of packets that are to be played back together, are defined as "fusion sets". In addition, an apparatus/method for synchronizing multimedia packets emanating from a single source at the receiver.

2. Description of the Prior Art

Herein apparatus and methods for multiparty synchronization in the presence of noncontinuous periodic traffic in real-time applications that determine the fusion sets of the packets for playback are presented. Packets, one from each source, that belong to the same fusion set, will be played back (or mixed for the purpose of playback) at the same time at the receiver. The proposed multimedia synchronization methods are based on statistically evaluating the reference times or expected arrival times of the packets from each participant in each connection. Once the reference times are estimated, synchronization is achieved not according to the generation times of the packets but according to their expected arrival times. This concept has lots of merits, particularly the merit that it permits the receiver to decouple the synchronization dealing with packets arriving from one participant from the synchronization dealing with packets arriving from the other participants. In addition, for the same reason it exhibits the optimum delay. To clarify these points more, suppose a multimedia conference is held among three participants. One of them is located in New York, another in New Jersey, and the third in California. Then packets arriving from New Jersey to the participant located in New York, will only experience the average time delay expected in the connection from New Jersey to New York. Similarly, packets arriving from California will only experience the average time delay expected in the connection from California to New York. This has as an end result that the case of Interparticipant synchronization can logically be broken into M parts (assuming M participants in a multimedia conference), one for each participant.

In "Communication Architectures and Algorithms for Media Mixing in Multimedia Conferences" by Rangan et al. Appeared in IEEE/ACM Transactions on Networking, pp. 20-47, Feb. 93 (›1!), and in "Adaptive Feedback Techniques for Synchronized Multimedia Retrieval over Integrated Networks" by Ramanathan et al. appeared in IEEE/ACM Transactions on Networking, pp 246-260, April 1993 (›2!), their methods were achieving synchronization according to the generation times of the packets. This means, that if packets were generated at the same time (or within a very small time window), they were played back together at the receiver. To find out whether packets were generated it the same time, feedback packets in order to estimate the actual time delay of the packets of each participant were used. Or, the assumption of global network clock was assumed, which means that the generation times of the packets were known to the receiver by simply carrying their generation timestamp. There are many disadvantages of their methods. Their methods require feedback packets in order for the actual time delays to be estimated, or a global clock is needed. In addition, packets emanating from sources nearest to the receiver are punished with extra time delay so that their playback times become equal with the packets emanating from the source which is the furthest away from the receiver.

In U.S. Pat. No. 3,843,930 by Burnsweig, U.S. Pat. No. 5,526,353 by Branstad et al., and U.S. Pat. No. 5,533,021 by Henley et al., descriptions of methods and apparatus for synchronizing multimedia and/or voice data packets emanating from a single source are presented. However, the present invention describes a method and an apparatus for synchronizing packets emanating from different sources. In addition, the present invention describes methods and apparatus for sending packets to a receiver non-continuously but periodically, and the receiver accepting packets from such a source.

Although it is been one year from the time of publication of "Statistical synchronization among participants in a real-time multimedia conference" by Zarros et al. in the proceedings of IEEE Infocom '94, pp 912-919 (›3!), many improvements based upon the contents of this paper are presented here. Some of the improvements are contained in my Ph.D. Thesis "Multimedia Network Synchronization In Real Time Applications", the Graduate Center of the City University of New York, June 1995(›4!), but many of them do not appear anywhere else. The improvements that are contained in my Ph.D. Thesis are: 1) The use of feedback to reduce the reference interval at the receiver; 2) the traffic is non-continuous periodic; and 3) sources generate packets with period that can be an integer multiple of a fundamental period T. Improvements that do not appear anywhere else are the following: 1) the reference interval, when no feedback is used, is reduced to the minimum theoretical value; and 2), the use of the zeta times, and a special case of those the individual playback times. The zeta times are constructed from the reference times, and they are a generalization of the reference times.

We have presented a multiparty synchronization method and an apparatus for real-time network applications, such as multimedia conferencing. Specifically we have presented the following. We have provided a mechanism at the receiver to estimate the playback time of the packets using the concept of the reference times or average arrival times. This was achieved by modeling the traffic of the voice (or video) packets as noncontinuous periodic. This means that at the sender, even if packets will be generated aperiodically, we will insert "empty" data in the packet to make the generation times of the packets periodic. If the silent interval exceeds the time length of one packet, then the sender might not send any packets at all. For this reason, we call the traffic noncontinuous periodic. Once the traffic is such as described, the receiver can easily determine the reference times of the packets. Once again, reference time of a packet is the time that the packet would arrive at the receiver, if only had experienced the average time delay that packets in this connection experience. Given the reference times of the packets, then we can also easily determine the individual playback times of the packets from each source (t.sub.pb,n.sup.i =t.sub.ref,n.sup.i +.DELTA..sub.max.sup.i +.sub.T). A generalization of the reference times are the zeta times, that can be constructed from the reference times of the packets by adding a constant time interval X.sup.i to each reference time from a common source, but this constant time interval might be different for different sources. The zeta times are defined as follows t.sub.z,n.sup.i =X.sup.i +t.sub.ref,n.sup.i.

Subsequently, improvements and extensions to more than one period of the interparticipant synchronization method presented in "Statistical synchronization among participants in a real-time multimedia conference", by Zarros et al. in the proceedings of IEEE Infocom '94, pp 912-919, were presented. In the basic method in "Statistical synchronization among participants in a real-time multimedia conference", by Zarros et al. in the proceedings of IEEE Infocom '94, pp 912-919, packets from different sources were found to belong to the same set for playback at the receiver, only if their reference times were within the same reference interval of length T, where T is the common generation time of the packets for all the sources. Three basic types of improvements were made. First, instead of using the reference times, it is shown that we get better results by using the playback times. That means, that we group packets from different sources together if their playback times (t.sub.pb,n.sup.i =t.sub.ref,n.sup.i +.DELTA..sub.max.sup.i +.sub.T) were within the same reference interval T. We immediately have a gain equal to the difference of max.sub.i {.DELTA..sub.max.sup.i }-.DELTA..sub.max.sup.i, where i is any of the sources. For different applications that have various time delay constraints, we can use the zeta times in a similar way.

A second improvement is achieved when, instead of using as a reference interval the common generation period T, we use the minimum theoretical value that guarantees us that the reference time or playback time of one packet from each source will be within this interval. This minimum theoretical value is ##EQU1## where M is the number of sources. Immediately we see that the gain in the waiting time for playback is ##EQU2## which is considerable large if M=3 or 4. The first and the second improvement can be combined to lead to a better improvement.

The third improvement has to do with feedback. By using feedback, we can eliminate further the reference interval, either this T or ##EQU3## This improvement can be used when either the reference times or the playback times are used to determine the set of packets that have to be played back together at the receiver. In case there is a mechanism that permits the receiver to estimate the frequency offsets between the clocks at the source and at the receiver, the length of the reference interval becomes .vertline.N(T.sup.j -T.sup.R).vertline., where j is the source that exhibits the maximum frequency offset with respect to the clock at the receiver, i.e. (T.sup.j -T.sup.R) is maximum. In case the receiver could only determine the direction of the frequency offset of the clocks and not the actual value, i.e. whether the clock of a source is faster or slower than its own clock, then the reference interval achieved would be .vertline.N(T.sup.S -T.sup.R).vertline., where s is a hypothetical source in the network that exhibits the maximum frequency offset from the receiver's clock.

Feedback can also be used when no mechanism that estimates the frequency offsets of the clocks with respect to the clock at the receiver exists. In this case, the minimum reference interval that can be achieved is 2.vertline.N(T.sup.S -T.sup.R).vertline., where s is a hypothetical source in the network that exhibits the maximum frequency offset from the receiver's clock. We immediately see the improvements in the waiting time for playback, which for the case the initial reference interval was T=T.sup.R, the improvements will be T.sup.R -.vertline.N(T.sup.j -T.sup.R).vertline., T.sup.R -.vertline.N(T.sup.S -T.sup.R).vertline., and T.sup.R -2.vertline.N(T.sup.S -T.sup.R).vertline. respectively. A typical value of (T.sup.S -T.sup.R) will be 10.sup.-3 T.sup.R.

An expansion to the apparatus and method to cover cases of sources generating packets with integer multiple of a fundamental period T.sub.F were also presented. We have presented the cases where the reference times and the playback times are used. These cases can be combined with the improvement which has to do with using as a reference interval the window ##EQU4## The feedback schemes presented for the singular case (one common period) can also be used for the case of sources transmitting packets with periods which are integer multiples to a fundamental period. The traffic generating from the sources is not necessary to be continuous, but it can have "silent" intervals in between, i.e. the methods/apparatus are shown to work also when traffic is non-continuous periodic.

FIG. 1 Representing the traffic as noncontinuous periodic.

FIG. 2 Definition of the network jitter.

FIG. 3 Sequence numbering and transmission of packets at the sender.

FIG. 4 Example of a typical interaction between sender and receiver for synchronization.

FIG. 5 Waiting time for playback using the reference times and reference interval T.

FIG. 6 Waiting time for playback using the individual playback times of the sources and reference interval the minimum theoretical interval ##EQU5## where M=3.

FIG. 7 Determination of the distances d.sup.i the reference time of each source i has to be readjusted after the reception of a feedback packet.

FIG. 8 Waiting time for sources with multiple packet generation periods using the reference times of the packets and reference interval T.

In FIG. 1, a graphical representation of a voice traffic being modeled as noncontinuous periodic is displayed. The shaded regions represent talkspurt intervals. Voice packets are generated at the sender exactly at the points indicated in the graph with the vertical lines. This means that a voice packet which is at the front or at the end of a talkspurt interval may only be partially filled with voice data. This modeling of the voice traffic wastes on the average one voice packet per talkspurt interval, but it has many advantages related to multimedia synchronization that will become obvious as we go along. In addition, a sequence number representing the sequence number of the time period the packet was generated at the sender will be attached to the packet. As a result, the packet generated at the time period (slot) between the vertical lines 2 and 3 will be assigned the sequence number 2, the second the number 3, and the sixth the number 8 since a silent interval of one period intervenes. The ordered set of the sequence numbers of all the arrived packets will be denoted as and the elements will be ordered in sequence from small to high according to their values. This implies that in a situation where a packet arrived out of sequence, the entry in the set will be corrected according to the ordering rule.

The video traffic can also be viewed as periodic when the requirement that a video frame (packet) will only be generated at the beginning of a period holds.

As shown in FIG. 2, the sender periodically transmits packets with nominal period T. However, due to frequency mismatches between the clock at the sender and the clock at the receiver, the actual transmission period of the sender as seen with the receiver's clock will be T.sup.S. The average delay time packets experience to arrive at the receiver from the sender is denoted as D. If there were no variation in the delay and each packet were experiencing a constant delay D, then packets would be arriving at points indicated in the graph as t.sub.ref,n. These points are called the reference times and they satisfy the following condition ##EQU6## If the exact location of the arrival time of one packet, let us say packet n.sub.1, which experienced exactly the average delay D could be found, then the reference time of any other packet n.sub.2 is given by the following expression

If the actual packet arrivals are denoted as t.sub.n, then the network jitter each packet experiences is defined as the difference of the actual arrival time minus the corresponding reference time

As noted previously, the model of the traffic is noncontinuous periodic. This model encompasses also the case of a source generating packets continuously and periodically, and therefore no specific treatment for the latter case will be made. In order for the reference times of the packets arriving from the same source to be estimated, firstly the time X where the time offset contributions of all the packets cancel out needs to be found. Let be the set of all the packets arrived at the receiver .sub.E be a subset of such as .A-inverted.n.epsilon..sub.E t.sub.n .ltoreq.X, and .sub.L be the complimentary subset of such as .A-inverted.n .epsilon..sub.L t.sub.n >X. Notice also that if the number of the elements in set .sub.E is N.sub.E and the number of the elements of the set .sub.L is N.sub.L, then their sum equals the total number of the received packets N.sub.E +N.sub.E =N. The set is a proper subset of the set of integers from 1 to N+k.OR right.{1,2, . . . , N+k}, and ={1,2, . . . , N} iff k=0. When k=0, this means that there is not an empty time slot, and there have arrived as many packets as time slots of duration T. Then the time X can be determined as follows ##EQU7##

The next step is finding which packet arrival time t.sub.n exhibits the minimum (in absolute value) distance to time X. If we name the arrival time for this packet t.sub.x, where x is an integer and .chi..epsilon., then the network jitter this packet has experienced will equal to ##EQU8## where is the time offset acquired in time (X-t.sub.x). In case t.sub.x and X coincide, the error in Eq. (5) is approximately zero, while when X.notident.t.sub.x the error is given by the following ##EQU9## The last relation in Eq. (6) comes when the time X is represented as a function of the sequence number of the time slot that a packet with arrival time the time X would have attached by the sender. If this hypothetical sequence number is represented as n.sub.x and the maximum and minimum values of the network jitter are denoted as .DELTA..sub.min and .DELTA..sub.max, then it is easy to see that ##STR1## since X>>.DELTA..sub.min and X>>.DELTA..sub.max.

With .DELTA..sub.x available, the reference time of the x'th packet is computed using Eq. (3), i.e. t.sub.ref,x =t.sub.x -.DELTA..sub.x. Then the reference times of the other packets are obtained as

Using the Chernoff bound, it can be easily shown that the estimation of the reference times can be achieved very fast, within 20 to 50 packets, depending on the accuracy required.

The maximum and minimum bounds of the network jitter are estimated as follows ##EQU10##

The second terms in Eqs (9) and (10) are due to the unknown error which appears in Eq. (8). Since the maximum or minimum jitter can occur in any of the received packets, we can bound the error (n-n.sub.x)(T.sup.S -T.sup.R) by considering the worst case situation which is max{n.sub.x, N+k-n.sub.x }. In the same way we can bound the second factor of the second term, i.e. the factor .vertline.T.sup.S -T.sup.R .vertline. by assuming that the maximum rate of the time offset that anybody can observe in the network cannot exceed a certain value, i.e. .vertline.T.sup.S -T.sup.R .vertline..ltoreq.10.sup.-V T.sup.R, where v is a small integer (3 to 6).

For point-to-point communication considering only one medium, the synchronization function at the receiver should simply be the inverse of the maximum delay. Packets should wait exactly so much time, as much as it is estimated that all packets will give within this waiting time interval. If a packet does not come within this interval, then the packet will be considered lost. Therefore, the waiting time for point-to-point network communication will be ##EQU11##

Synchronization between sender and receiver is achieved with the transmission of a p.sub.1 -bit sequence number. At the sender site, as shown in FIG. 3, every time interval T a counter increments its value and executes modulo 2.sup.p.sbsp.1. The result is the p.sub.1 -bit sequence number for this time interval. If there is a useful data to be sent through the network, then these p.sub.1 bits are sent over the network along with the packet. If there is no useful data to be sent, i.e. the sender is on a silence time interval, the counter is simply incremented and then executes modulo 2.sup.p.sbsp.1. The above procedure is repeated till the end of the conference.

Upon the reception of the packet, there are two processes that proceed in parallel by the receiver. The first process involves the post-processing of the arrival times of the packets. By exploiting the information of the arrival times of the packets alone, the receiver is able to determine the bounds of the network jitter, the expected average arrival time of the packets (the reference times), and the frequency offset between its clock and the clock at the sender. An additional advantage of this method is that the sender is not required to transmit the generation time of the packet (time stamp) in order for the frequency offset to be determined by the receiver.

The second process is directly involved with the synchronization of the arrived packet by determining its correct playback time. In order for the second process to operate properly, the reference times, bounds of the network jitter, and frequency offset must be known to the receiver by the first process. Because all of the above parameters need a certain number of pre-received packets, it is assumed that during the connection-setup time a few packets, let us say N, were sent prior to the execution of the synchronization method/apparatus. With their help, a rough estimation of the of the last packet sent during the setup time t.sub.ref,O is made. These N packets sent by the sender carried among other useful information their own sequence numbers explicitly into their user field. This implies that the mapping t.sub.n n between the packet arrival times and the sequence numbers already exists for these N packets, and therefore the receiver using Equations (3), and (5) can find the reference time of the last packet N t.sub.ref,N, which from now on we will call it t.sub.ref,O for convenience.

The actions of the two processes at the receiver are as follows. In order for the second process to determine the sequence number of each arriving packet, the reference time of this packet must be known to the second process. However, in order for the first process to estimate the reference time of the arriving packet, the first process must have knowledge of the sequence number of the arriving packet. This is achieved with a feedback loop from the second process to the first.

There are two counters at the receiver: one infinite counter whose value starts incrementing every T seconds right after the end of the setup time t.sub.ref,O, and a finite counter whose value is repeated after a pre-determined number 2.sup.p.sbsp.1. In other words, current=(previous+1)mod 2.sup.p.sbsp.1. The determination of the correct phase of the finite counter will be shown now. There is a p.sub.1 -bit sequence number associated with every packet which was attached to it by the sender during its departure. This same p.sub.1 -bit sequence number will be used to denote the arrival time of each packet at the receiver as long as the packet has experienced exactly the average delay. In other words, if the reference time of a packet n could be known to the receiver, then the reference time, and along with it the time interval ›t.sub.ref,n,t.sub.ref,n +T!, will be assigned the p.sub.1 -bit sequence number this packet n carries with it. Then, since the network jitter the x'th packet experiences can be estimated using Equation (5), the receiver can determine the p.sub.1 -bit sequence number of the reference time of the x'th packet as follows (:=is the assignment operator)

(x)p.sub.1, is the p.sub.1 -bit sequence number attached to packet x at the sender. Then the p.sub.1 -bit sequence number of the following k'th interval away from t.sub.ref,n, i.e. the interval ›t.sub.ref,x +kT,t.sub.ref,x +(k+1)T!, can be determined by the following operation

Once the reference times are mapped into p.sub.1 -bit sequence numbers, the p.sub.1 -bit sequence number of the current reference interval is compared with the p.sub.1 -bit sequence number of the packet that arrived within this time interval and needs to be synchronized. Synchronization now translates into a problem of finding the correct mapping between the arriving packet and its reference time. The reference time of the arriving packet is the beginning of the nearest interval T whose p.sub.1 -bit sequence number agrees with the p.sub.1 -bit sequence number of the arriving packet. The number .delta. of intervals T the reference time of the arrived packet is away from the beginning of the current interval is given by the following statement.

Statement 1.

Suppose an entire axis is divided into equally spaced intervals T. Each interval T is represented by a p.sub.1 -bit sequence number, such that the sequence number of the next interval is related to the previous by the following relation: next =(previous+1)mod 2.sup.p.sbsb.1. A packet which carries an arbitrary p.sub.1 -bit sequence number falls into an arbitrary interval T. Given the p.sub.1 -bit sequence numbers of the packet A=A.sub.p.sbsb.1, A.sub.p.sbsb.1-1 . . . A.sub.1 and that of the interval T B=B.sub.p.sbsb.1 B.sub.p.spsb.1-1 . . . B.sub.2 B.sub.1 which fell into, then the nearest interval T whose p.sub.1 -bit sequence number C=C.sub.p.sbsb.1 C.sub.p.sbsb.1-1 . . . C.sub.2 C.sub.1 exactly matches the p.sub.1 -bit sequence number of the packet is located .delta. intervals away (ahead-, behind+) from the current interval. .delta. satisfies the condition A=(B+.delta.)mod 2.sup.p.sbsp.1 =C and is given by the following relation ##EQU12##

The proof of Eq. (14) can be easily determined by the truth tables of AB-AB. Once .delta. is found, the proper time that the arrived packet should be played back is determined as follows

where current.sub.ref-time is the beginning of the interval the arrived packet fell into. The meaning of Eq. (15) is that the playback time of the packet is W seconds after its estimated reference time, or .delta.T+W seconds after the beginning of the reference interval the packet fall into. To clarify the involved implementation, an example follows.

In the example shown in FIG. 4, let us have T=6 ms,p.sub.1 =3, and the maximum jitter from the average observed in the network .DELTA..sub.max is 12 ms. Allowing 2.5 ms for the estimation error and the uncertainty in the time offset, the waiting time from the reference time becomes W=14.5 ms. If the current 3-bit sequence number of the reference time at the receiver shows 100 and during this time slot a packet arrived with 3-bit sequence number 101, then using Equation (14), A.sub.3 A.sub.2 A.sub.1 =101, B.sub.3 B.sub.2 B.sub.1 =100, and .delta.=(11-11) 2.sup.2 +(00-00) 2.sup.1 +(10-10)2.sup.0 =-1. This makes the reference time of the arriving packet one time slot into the future from the beginning of the current interval. It follows that the playback time is simply W=14.5 ms away into the future from the reference time of the packet t.sub.ref,6.

Summary of the Synchronization Method

Here, the maximum error allowable in the synchronization of packets from different sources will be designated .sub.T. As it will be shown later, the error .sub.T will be composed from two components: one error component due to the finite number of packets used to estimate the reference times .sub.R, and another due to the time offset acquired in the time interval NT (.sub.f.) The total error will be designed in such a way so that it satisfies the packet loss criteria of the designer of the real-time application. For instance, the total error might be designed in such a way that the packet loss is strictly less than one packet out of 1000 or 10,000 received. Summary of the synchronization method is provided now.

Main Method

The steps below are executed every new N packets received from each source i. Synchronization is shown to be achieved for the next N received packets.

1. Determine the reference time and maximum value of the network jitter (.DELTA..sup.i.sub.max) for each source i.

2. a. Divide time at the receiver in equally spaced intervals of duration T. These intervals are named the reference intervals, and packets whose reference times fall into the same reference interval belong to the same set.

b. In case the time window that is used is T ##EQU13## a slight modification is required. We still divide time at the receiver in equally spaced intervals of duration T. At the beginning (or at the end) of these intervals, we reserve a time window of length T ##EQU14## This is now the reference interval, and packets whose reference times fall into the same reference interval belong to the same set.

3. Determine the additional time delay after the end of the current reference interval that the receiver has to wait in order to receive one packet from each source, i.e. to receive all packets belonging to the current set. This delay time for each set is the time measured from the end of its reference interval to its playback time.

4. Group the packets according to their reference times. Wait for the time interval found in step 3 and then play them back together.

Feedback

Feedback can be employed both before or after the estimation of the frequency offsets between the clocks at the sources and the clock at the receiver. Employing feedback reduces the waiting/delay time that each packet experiences to the minimum. The basic steps of the feedback method/apparatus are:

1. Determine the distance in time that the reference time of each source i is away from a point M (we chose it to be the middle of the reference interval with duration T, but any other point will do) and send this information back to each source i.

2. Upon reception of the feedback packet, the source i either pauses time d.sup.i or inserts noisy data of time duration d.sup.i in the first packet depending on whether its clock is faster or slower than the clock at the receiver.

During the conference setup time, we may allow the error to be larger than . By allowing a larger error, the number of packets N needed for a certain level of accuracy is decreased geometrically. However, if a need to compute the reference times fast is needed, we may even allow feedback packets that will permits us faster accuracy of the reference times.

Minimum Waiting Time for Playback

The minimum time window required for the reception of one packet from each source (i.e. 1 packet from source 1, 1 packet from source 2, . . . , and 1 packet from source M) generating packets with period T in the absence of network jitter is T. This is due to the phase differences among the sources. Using induction, we van show that the smallest time window during which all M sources are guaranteed to generate packets is ##EQU15## However, in practice due to the frequency drifts of the clocks, we will see that this minimum time window requires constant movement at the receiver which is not desired because of complexity in implementing the method. Here is the usefulness of the reference time which is relatively immune to the network jitter and therefore indicates with high probability of confidence whether a packet received belongs to the set whose reference time is within a time window or not. Packets with reference times belonging to the same time window T will be assigned to the same group when played back at the receiver. In contrast to the reference time, actual packet arrival time varies due to the network jitter. A packet from source i with its reference time at the end of the time window T and having maximum jitter .DELTA..sup.i.sub.max, might arrive as late as T+.DELTA..sup.i.sub.max. The total delay time to receive one packet from each source can be shown to be ##EQU16## D.sup.i is the average time delay for a packet to arrive from source i to the receiver. x.sup.i is the length in time that the reference time of source i is away from the late edge in the time window T. The fifth term is due to the maximum time offset we expect from the different clocks at a particular situation. Since the worst case situation is to have the reference time to be at the early edge of the reference interval, then the ##EQU17## is the reference interval, and the minimum waiting time is ##EQU18##

As shown in FIG. 5, the minimum waiting time consists of two intervals. Interval AB(=T) and interval BC. Interval AB is due to the phase offset and is the interval which often will be referred to as the reference interval, and interval BC is function of both the network variation in the delay and the frequency differences of the clocks between sender and receiver. Note that interval BC overlaps with the next interval BD. A packet whose reference time is in interval AB and arrives at interval BC will be played back at time C. However, a packet whose reference time is in interval BD and arrives at interval BC will be played back at time E.

An improvement to the apparatus/method is as follows. To each reference time t.sub.ref,n.sup.i, we add its maximum value of the jitter observed in its connection .DELTA..sub.max.sup.i, plus ##EQU19## If each connection were considered as a point-to-point connection, these points would be the individual playback times of the packets for this connection (source i). Let us call those points the individual playback points or times for the connection for source i, t.sub.pb,n. Then, the following relation is valid:

(In the remaining of the paper, we might use interchangeably the terms individual playback times or playback times. Most of the time we will be using the term playback times, and if there is a need to distinguish with the playback time of all the packets in a fusion set, we will use the term individual playback times.)

With the same analysis as with the reference times, we are guaranteed that in a time window T, we will be receiving one packet from each source whose "playback" time t.sub.pb,n.sup.i will be within this time window T. Of course, as noted also above, the smallest time window is smaller ##EQU20## where M is the total number of participants. But neglecting this for the moment, the total delay time for playback for packets from source i at the receiver will be ##EQU21## and y.sup.i is the length in time that the playback time of source i is away from the late edge in the time window T. The y.sup.i 's are not the same as the x.sup.i 's, but their average value will be the same. Because the probability distribution of the y.sup.i 's and the x.sup.i 's are the same, since the y.sup.i 's are a shifted version of the x.sup.i 's by .DELTA..sub.max.sup.i +.sub.T. We see now that there is an average improvement in the waiting time for each source equal to the difference of ##EQU22## There will also be one more improvement. If the reference time of a packet from a particular source is very close at the early edge of the time window T, then it might happen that this improvement ##EQU23## might make its playback time now to belong to an earlier set (Fusion set) for playback. In that case, the gain in time for the waiting time for this source will be the length of the time window, T. The probability that this will happen is G/T, and therefore the total improvement (on the average) will be ##EQU24## We would like also to note here, that even for the case that the source k has the maximum observable jitter in the observable time interval NT of all the sources, i.e. ##EQU25## the improvement ##EQU26## will still be valid on the average.

The second improvement has to do with taking into account the minimum theoretical time window that we are guaranteed to receive the reference times or the playback times of the packets. The improvements in the waiting times of the packets, especially for two (2) or three (3) sources, will be ##EQU27## and ##EQU28## The description of how can this be achieved, keeping in mind that the reference times time (during the time (during the time interval NT that the interparticipant method is re-executed), follows. Our method has an error in estimating the reference times of the packets, .sub.R, and an error due to the frequency offsets between the clocks at the sources and the clock at the receiver. Unless we have a mechanism to estimate the frequency offsets among the clocks, we have to assume the maximum possible difference, i.e. ##EQU29## The time window that we are guaranteed that one of the reference or playback times from each source is within this time interval is ##EQU30## Then, the total delay time for packet from source i, in case we are using the playback times (see FIG. 6), is

The z.sup.i is the length in time that the playback time of source i is away from the late edge in the time window ##EQU31## The following relation holds between the average values of the z.sup.i 's and the ##EQU32## The total delay time for packet from source i, in case we are using the reference times is ##EQU33## The w.sup.i is the length in time that the reference time of source i is away from the late edge in the time window ##EQU34## The following relation holds between the average values of the w.sup.i 's and the ##EQU35##

When the time window is ##EQU36## in either case (reference or playback times), the start of the time window needs to be moved when the synchronization method is executed (time interval NT). To find the new starting point of the time window, we take the following steps.

1. We find the average time delay and the maximum time delay for each source, D.sup.i and D.sup.i +.DELTA..sub.max.sup.i.

2. For each of the reference/playback times of the sources, we repeat steps 3,4, and 5.

3. We take as the end of the time window the reference/playback time of this source.

4. We subtract time ##EQU37## from the reference/playback time. This takes us to the beginning of the time window.

5. We check to see if one reference/playback time from each source is within this time window. If this is true, we note down the source. This is the source that we took it to be the end of the time window (or the late edge).

6. From all the sources that their reference/playback times satisfy the condition to be the late edge of the time window, we take this source with the largest average time delay for the case of the reference times, and the source with the maximum time delay for the case of the playback times.

By executing step 6 above, we sort of equalizing the time delays. Because the source with the maximum time delay gets to be at the late edge of the time window, and therefore it does not wait any other extra time in order to be played back.

It is obvious that the time delay obtained with Eqs (16), (19), (21) and (22) is not the optimum. A source i with reference time at the beginning of the reference interval T (or ##EQU38## will be delayed an additional time ##EQU39## in order for the packets from source i to be played back. Since the length of the reference interval can be as large as one or two times the maximum jitter experienced in the network, quality of service will be degraded due to excessive delay. While the terms in the equation with the waiting time which have to do with the maximum jitter and the error cannot be minimized further, the term related to the reference interval (x, or y, or z, or w) can be minimized if feedback is employed. As a reminder, this term (x, or y, or z, or w) has to do with the phase offsets existing among the different participants of a conference. We will distinguish two cases depending on whether an estimation of the rate of the time offset is available. One case when there is no estimation of the frequency offsets, and another case when estimations of the frequency offsets exist.

Since the estimation of the reference times is performed every NT seconds, a feedback packet from the receiver to source i need to be sent every NT seconds. There will be a delay from the moment the feedback packet is sent to the moment it arrives at the source and takes effect. The packets that arrive at the receiver during this delay cannot be used towards the estimation of the next reference time.

Feedback when no estimation of the frequency offsets exist

During this period of time, we do not have an estimation of the rates of the time offsets and it is impossible to predict the exact time offsets acquired during the time interval NT between the clock at the receiver and the clock at the sender. Nevertheless, as we have done in Eqs (16), (19), (21), and (22), we assume that in a time interval NT the maximum possible time offset two clocks in the network can experience is N(T.sup.S -T.sup.R). s is the imaginary source which gives the maximum frequency drift measured against the receiver clock. To compare the reference times of the different sources, we arbitrarily choose to measure their time distances from the midpoint M of their current reference interval. Thus, when the reference times are estimated, their distances d.sup.i to point M will be computed as well. A distance will be called positive when the reference time of the source is at the left to the point M, and negative when it is at the right. If the feedback packet carries the value d.sup.i to each source i, and the source i readjusts itself properly, the reference time for source i for the next NT seconds will be very close to point M, and actually will be within the interval ›M-.vertline.N(T.sup.S -T.sup.R).vertline.,M+.vertline.N(T.sup.S -T.sup.R).vertline.!. Source i will either pause time d.sup.i if d.sup.i is positive, or precede the following data of time duration (T-d.sup.i) with noisy data of duration d.sup.i, if d.sup.i is negative. The total delay time for packets from source i will now be ##EQU40## x.sub.F.sup.i is the length in time that the reference time of source i is away from the late edge of the time window ›M-.vertline.N(T.sup.S -T.sup.R).vertline.,M+.vertline.N(T.sup.S -T.sup.R).vertline.!=2.vertline.N(T.sup.S -T.sup.R).vertline.. In other words, feedback has reduced the length of the reference interval from T to 2.vertline.N(T.sup.S -T.sup.R).vertline..

In case the variation of the main method with the individual playback times is used, the total delay time for packets from source i will be ##EQU41## y.sub.F.sup.i is the length in time that the playback time of source i is away from the late edge of the time window ›M-.vertline.N(T.sup.S -T.sup.R).vertline.,M+.vertline.N(T.sup.S -T.sup.R).vertline.!=2.vertline.N(T.sup.S -T.sup.R).vertline.. M is now the middle point of the reference interval which is constructed with the playback times of the packets. In the case that the reference interval is ##EQU42## and feedback is applied, we get no better results than the ones shown in Eqs (23) and (24).

Feedback When Estimation of the Frequency Offsets are Available

Let us assume that accurate estimates of the rates of the time offsets between the clocks at the sources and the clock at the receiver are obtained. Let us assume that the size of the maximum rate of the time offset occurs for source. In NT seconds, this will lead to a maximum time offset. Let d.sup.i be the distance of the reference time for source j to the midpoint M of the reference interval. The feedback packet brings this information to source j and source j readjusts itself so that its new reference time is at point M. After time NT the reference time for source j will move to new point, point Z. We have .vertline.M-Z.vertline.=.vertline.N(T.sup.j -T.sup.R).vertline.=.vertline.T.sup.j.sub.off .vertline.. Point Z will be to the left of point M if the time offset is negative, i.e. the clock at the source j is slower than the clock at the receiver, and to the right of point M if it is positive, i.e. the clock at the source j is faster than the clock at the receiver. Without loss of generality, let us assume that the clock for source j is faster is faster than that of the receiver and consequently point Z will be at the right of point M as shown in FIG. 7. Then we compute the distances for the rest of the sources as follows: a) for the sources with positive time offsets (source 1 in FIG. 7), the distances will be computed from their reference times to point M. b) for the sources with negative time offsets (source 2 in FIG. 7), the distances will be computed from their reference times to point Z. The distances defined in this way will be sent back with the feedback packets to the corresponding source, i.e. distance d.sup.i to source i. When the sources receive the feedback packets, they will readjust the generation times of the packets so that their respective reference times (or playback times) to coincide with either point M or point Z at the receiver. Since we have used the maximum possible clock offset of any of the sources, the reference times are guaranteed to be within the interval ›M,Z! during the next time interval NT. The total delay time for packets from source i will now be ##EQU43## when the main method with the reference times is used, and

when the main method with the individual playback times is used. u.sub.i is the length in time that the reference/playback time of source i is away from the late edge of the time window .vertline.N(T.sup.j -T.sup.R).vertline..

The same procedure can also be used when the signs of the frequency offsets with respect to the clock at the receiver are known, although not the actual frequency offsets. The only difference will be that the point Z will be computed from point M by subtracting the maximum frequency offset that we pre-assumed for the network. For example, we might say that no clock of a source in the network may exhibit a frequency offset with any other clock by more than 10.sup.-3 T. Then, instead of the term T.sup.j -T.sup.R we will use this term 10.sup.-3 T, and point Z will be found by subtracting time interval equal to N10.sup.-3 T.

Minimum waiting time for sources with different periods

Here we modify the minimum waiting time that will permit the use of sources transmitting packets with different periods. The periods are assumed to be integer multiples of the shortest packet generation period T.sub.f . The subset of sources transmitting packets with period T.sub.f will be referred to as the fundamental subset f. The total delay time for packets from source i for playback will be ##EQU44## x.sup.i is the length in time that the reference time of source i is away from the late edge of the time window T.sub.f. The worst case (i.e. the maximum value x.sup.i can have is T.sub.f ), and therefore the minimum waiting time will be ##EQU45##

The validity of Eq. (28) is deduced from the following syllogism. It is clear that in the absence of other sources with multiple packet generation periods, Eq. (28) holds at least for subset f. The reference time of a source with larger packet generation period, let us say nT.sub.f , has to fall within one interval T.sub.f of subset f. The next packet is not expected to arrive until a time interval nT.sub.f has elapsed. Consider for each reference interval T.sub.f all the sources that their reference times fall into. With the exception of the range i, which will have to be a member only from the sources with reference times within this interval, the minimum waiting time will be as defined in Eq. (28). By repeating the above until all sources have been exhausted, a different source i can be found for different reference intervals. Different i will cause a problem when the reference time of a source falls into another reference interval and this is the reason for considering i to be any source in Eq. (28).

The first line in FIG. 8 shows sources with period T.sub.f , while in the two lines below that, there are sources with periods 2T.sub.f . So sources with period 2T.sub.f and reference times falling within time interval ›a,b! are played back at time c(=C). If their reference times fall within time interval ›b,d!, they are played back at time e(=E).

The same improvements that were discussed for the case of sources generating packets with only one nominal period are also valid for the case of sources generating packets with periods that are integer multiple of a fundamental period T.sub.f. The first improvement where the playback times are used instead of the reference times is clearly valid. The total delay time for playback for packets from each source i is

where y.sup.i is the length in time that the playback time of source i is away from the late edge of the time window T.sub.f . T.sub.f is the time window that guarantees us that the playback time of source i of the subset f will be within this interval, plus for any other source's playback time with multiple generation period (nT.sub.f)t.sup.j.sub.pb, one of the following times is within this time interval T.sub.f : t.sub.pb.sup.j, t.sub.pb.sup.j -T.sub.f,t.sub.pb.sup.j -2T.sub.f, . . . , t.sub.pb.sup.j -(n-1)T.sub.f, where j is any source with multiple generation period.

The second improvement deals with the minimization of the reference interval, which for this case will be ##EQU46## where M is the number of al the sources. (Note: we cannot use M.sub.n, where M.sub.n is the number of sources that their playback times fall into time interval ##EQU47## because we will end up with waiting times different for each period T.sub.f). Clearly, for sources with packet generation period nT.sub.f, where n>1, we cannot guarantee that their reference or playback times will be within a time interval ##EQU48## However, what we really mean for the packets of these sources is that one of the following times, t.sub.pb.sup.j,t.sub.pb.sup.j -T.sub.f,t.sub.pb.sup.j -2T.sub.f , . . . , t.sub.pb.sup.j -(n-1)T.sub.f, is within the time window ##EQU49## is any source with multiple generation period.

The total delay time for packets of each source in the case the reference times are used is as follows ##EQU50## The w.sup.i is the length in time that the reference time of source i (whose reference time is within the time window ##EQU51## is away from the late edge of the time window ##EQU52## The following relation holds between the average values of the w.sup.i 's and the ##EQU53##

The total delay time for packets of each source in the case the playback times are used is as follows

The z.sup.i is the length in time that the playback time of source i (whose playback time is within the time window ##EQU54## is away from the late edge of the time window ##EQU55## The following relation holds between the average values of the z.sup.i 's and the ##EQU56##

Similarly with the case of a single generation period of the packets for all the sources, for the multiple case too, when the time window for the reference interval used is ##EQU57## in either case (reference times or playback times), the start of the time window needs to be moved when the synchronization method is executed (time interval NT). To find the new starting point of the time window, we take the same steps as for the case of a single generation period of the packets for all the sources.

The same feedback method used for the case of a single generation period of the packets can also be applied to the case of sources generating packets with multiple periods (with respect to a fundamental).

Determination of the time to change the waiting time of the packets

Anytime the method is re-executed (time interval NT), it is very possible that the waiting time for the packets needs to be changed. If the length of the new waiting time is larger than the currently used waiting time, then the receiver will only need to find a silent interval (for voice packets). Once the silent interval is found, any data after this time interval is played according with the new waiting time.

In case the length of the new waiting time is smaller than the currently used waiting time, then the receiver has to find a silent interval whose length is larger than the difference of the two waiting times.

The Zeta Times

We have concentrated ourselves only on apparatus and methods that use the reference times of the packets or the individual playback times for the determination of the fusion sets of the packets. Here we will generalize the concept of the reference times, and the name for these new times will be the zeta times. Zeta times will be constructed from the reference times of the packets by adding a constant time X.sup.i to each reference time from a common source, but this constant time might be different for different sources. Therefore, the zeta times will be defined as

It is easily seen that the reference times can be derived from the zeta times if for all sources i, X.sup.i =0, and the individual playback times can be derived by the zeta times if for each source i, X.sup.i =.DELTA..sub.max.sup.i +.sub.T, and in this case we can easily see that t.sub.z,n.sup.i =t.sub.pb,n.sup.i.

Zeta times will be very useful because they will enable us to determine the fusion sets of the packets for playback also to network applications that need various time delay constraints. Because there might be applications that require packets from specific source(s) to be delayed a specific amount of delay than from certain other sources. This of course might require the determination of the exact time delays of the packets, but the point is that the same concept, i.e. dividing the time at the receiver into reference intervals, and then the packets that their corresponding zeta times fall within this reference interval belong to the same fusion set for playback.

While the present invention has been described with reference to the details of the embodiments enclosed, these details are not intended to limit the scope of the invention as claimed in the appended claims.