Universität Stuttgart Fakultät Informatik Fakultät Informatik Institut für Parallele und Verteilte Höchstleistungsrechner Universität Stuttgart Breitwiesenstraße 20 - 22 D-70565 Stuttgart An Adaptive Stream Synchronization Protocol Kurt Rothermel, Tobias Helbig An Adaptive Stream Synchronization Protocol Kurt Rothermel, Tobias Helbig CR-Klassifikation: C.2.2, C.4, D.4.4, D.4.8 Fakultätsbericht 14/1994 Technical Report December 1994 5th International Workshop on Network and Operating System Support for Digital Audio and Video April 18-21, 1995 Durham, New Hampshire, USA Abstract Protocols for synchronizing data streams should be highly adaptive with regard to both changing network conditions as well as to individual user needs. The stream synchronization protocol we are going to describe in this paper supports any type of distribution of the stream group to be synchronized. It incorporates buffer level control mechanisms allowing an immediate reaction on overflow or underflow situations. Moreover, the proposed mechanism is flexible enough to support a variety of synchronization policies and allows to switch them dynamically during presentation. Since control messages are only exchanged when the network conditions actually change, the message overhead of the protocol is neglectable. Keywords: distributed system, multimedia, synchronization protocol, time-sensitive data, quality of service 1 INTRODUCTION 2 1 INTRODUCTION In multimedia systems, synchronization plays an important role at several levels of abstraction. At the data stream level, synchronization relationships are defined among temporally related streams, such as a lip-sync relationship between an audio and a video stream. To ensure the synchronous play-out of temporally related streams, appropriate stream synchronization protocols are required. Solutions to the problem of data stream synchronization seem to be quite obvious, especially if clocks are synchronized. Nevertheless, designing an efficient synchronization protocol that is highly adaptive with regard to both changing network conditions and changing user needs is a challenging task. If the network cannot guarantee reasonable bounds on delay and jitter, or a low end-to-end delay is of importance, the protocol should operate on the basis of the current network conditions rather than some worst case assumptions, and should be able to automatically adapt itself to changing conditions. Moreover, the protocol should be flexible enough to support various synchronization policies, such as `minimal end-to-end delay' or `best quality'. This kind of flexibility is important as different applications may have totally different needs in terms of quality of service. In a teleconferencing system, for example, a low end-to-end delay is of paramount importance, while a degraded video quality may be tolerated. In contrast, in a surveillance application, one might accept a higher delay rather than a poor video quality. Protocols for synchronizing data streams can be classified into those assuming the existence of synchronized clocks and those making no such assumption. The Adaptive Synchronization Protocol (ASP), we are going to propose in this paper, belongs to the first class and has the following characteristics: - ASP supports any kind of distribution of the group of streams to be synchronized, i.e. the sources of the streams as well as their sinks may reside on different nodes. Streams may be point-to-point or point-to-multipoint. - ASP incorporates buffer level control mechanisms and by this is able to react immediately on changing network conditions. It allows a stream's play-out rate to be adapted immediately when the stream becomes critical, i.e. when it runs the risk of a buffer underflow or overflow. If changing network conditions cause several streams to become critical at the same time, each stream may immediately initiate the required adaption, independent from all other streams. Note that this property may improve the intrastream synchronization quality substantially. 2 RELATED WORK 3 - ASP monitors the network conditions indirectly by means of the local buffer level control mechanism and performs rate adaptions only if they are actually required, i.e. only when a stream becomes critical. Due to this fact, the overhead for exchanging control messages is almost zero if the streams' average network delay and jitter are rather stable. - ASP supports the notion of a master stream, where the master controls the advance of the other streams, called slaves. The role of the master is assigned in accordance with the chosen synchronization policy and can be changed dynamically during the presentation if needed. - ASP is a powerful and flexible mechanism that forms the base for various synchronization policies. It is powerful in the sense that the realization of a desired policy is a simple task: A policy is determined by setting a set of parameters and assigning the master role appropriately. For a chosen policy ASP can be tuned individually to achieve the desired trade-off between end-to-end delay and intrastream synchronization quality. This tuning and even the applied policy can be changed dynamically during the presentation. The remainder of this paper is structured as follows. After a discussion of related work in the next section, the basic assumptions and concepts of ASP are introduced in Sec. 3. Then, Sec. 4 presents ASP by describing its protocol elements for start-up, buffer control, master/slave synchronization and master switching. We show in Sec. 5, how different synchronization policies can be efficiently realized on top of the proposed synchronization mechanism, and provide some simulation results illustrating the performance of ASP in Sec. 6. Finally, we conclude with a brief summary. 2 RELATED WORK The approaches to stream synchronization proposed in the literature differ in the stream configurations supported. Some of the proposals require all sinks of the synchronization group to reside on the same node (e.g. Multimedia Presentation Manager [IBM92], ACME system [AnHo91]). Others assume the existence of a centralized server, which stores and distributes data streams. The scheme proposed by Rangan et al. [RaRa92], [RRK93] plays back stored data streams from a server. Sinks are required to periodically send feedback messages to the server, which uses these messages to estimated the temporal state of the individual streams. Since clocks are not assumed to be synchronized, the quality of these estimations depends on the jitter of feed-back messages, which is assumed to be bound. A similar approach has been described 3 BASIC ASSUMPTIONS AND CONCEPTS 4 in [AgSo94], which requires no bounded jitter but estimates the difference between clocks by means of probe messages. Both the Flow Synchronization Protocol [EPD94] and the Lancaster Orchestration Service [CCGH92] assume synchronized clocks and support configurations with distributed sinks and sources. However, neither of the two protocols allows a sink to react immediately when its stream becomes critical. Moreover, the former protocol does not support the notion of a master stream, which excludes a number of synchronization policies. Finally, both schemes do not provide buffer level control concepts at their service interfaces, which makes the specification of policies more complicated than for ASP. Some buffer level control schemes have been proposed also. The scheme described in [KM94] aims at intrastream synchronization only. In [KHMS94], stream quality is defined in terms of the rate of data loss due to buffer underflow. A local mechanism is proposed that allows either to minimize the stream's end-to-end delay or to optimize its quality. 3 BASIC ASSUMPTIONS AND CONCEPTS The set of streams, which are to be played out in a synchronized fashion is called synchronization group (or sync group for short). The Adaptive Synchronization Protocol (ASP) distinguishes between two kinds of streams, the so-called master and slave streams. Each sync group comprises a single master stream and one or more slave streams. While the rate of the master stream can be individually controlled, the ones of the slave streams are adapted according to the progress of the master stream. The master and slave role can be switched dynamically as needed. For each sync group there exists a single synchronization server and several clients, two for each stream. The server is a software entity that maintains state information and performs control operations concerning the entire sync group. In particular, it controls the start-up procedure and the switching of the master role. Moreover, it is this entity that enforces the synchronization policy chosen by the user. The server communicates with the clients, which are software entities controlling individual streams. Each stream has a pair of clients, a sink client and a source client, which are able to start, stop, slow-down or speed-up the stream. Depending on the type of stream it is controlling, a sink client either acts as a master or slave. To achieve interstream synchronization, the master communicates with its slaves according to an orchestration protocol. 3 BASIC ASSUMPTIONS AND CONCEPTS 5 ASP supports arbitrarily distributed configurations: A sync group's sources may reside on different sites, and the same holds for the sinks. The location of the server may be chosen freely, e.g. it may be located on the node that hosts the most sink clients. We will assume that control messages are communicated reliably and hence are never lost. The required level of reliability is typically provided by virtual circuits or reliable datagrams. Further, it is assumed that the system clocks of the nodes participating in a sync group are approximately synchronized to within e of each other, i.e. no clock value differs from any other by more than e. Well-established protocols, such as the Network Time Protocol [Mill90], achieve clock synchronization with e in the lower milliseconds range. The basic principle of interstream synchronization adopted by ASP and various other protocols based on the notion of global time (e.g. [EPD94]) is very simple: Each data unit of a stream is associated with a timestamp, which defines its media time. To achieve synchronous presentations of streams, the streams' media time must be mapped to global time, such that data units with the same timestamp will be played out at the same (global) time. Similarly, the sources exploit the existence of synchronized clocks: data units with the same timestamp are sent at the same (global) time. Different transmission delays that may exist between different streams are equalized by buffering data units appropriately at the sink sites. Our model of stream transmission and buffering is depicted in Fig. 1. The data units of a stream are produced by a source with a nominal rate R1 and are transmitted to one or more sinks via an unidirectional transmission channel. The transmission channel introduces a certain delay and jitter, resulting in a modified arrival rate R1'. At the sink's site, data units are buffered in a play-out buffer, from which they are released with a release rate R2. The release rate, which determines how fast the stream's presentation advances, is directly controlled by ASP to manipulate the fill state of the play-out buffer and to ensure synchrony. Figure 1 : Data Stream and Delay Model Transmission Channel R3 Play-out Buffer s/d Buffer dT dB R1' R2 R1 M(t) Source Sink 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 6 A data unit that is released from the buffer is transferred to the so-called s/d-buffer, which can hold a single data unit only. From this buffer, it is read by the sink device with consumption rate R3. The s/d-buffer decouples the actual consumption rate of the sink device from the release rate and by this models a simple skipping or duplicating mechanism in the case R2 differs from R3. This may happen, for example, if the consumption rate is fixed. For many devices, however, R2 will never differ from R3, in which case the s/d-buffer is not needed at all. On its way from generation to play-out, a data unit is delayed at several stages. It takes a data unit a transmission delay dT until it arrives in the buffer at the sink's site. This includes all the times for generation, packetization, network transmission and transfer into the buffer. In the buffer, a data unit is delayed by a buffering delay dB before it is removed by the sink device. In the sink, of course, a data unit may experience a further delay before it is actually presented. For the sake of simplicity, however, we will assume that this delay is neglectable.1 The media time M(t) specifies the stream's temporal state of play-out and can be determined by reading the timestamp of the data unit in the s/d-buffer at time t. However, the granularity of media time were too coarse would it simply be based on the read timestamps without interpolation of intermediate values. Due to this fact, media time is actually modelled as a partially linear, continuous function M(t), which delivers the media time at real time t. 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL This section presents the Adaptive Synchronization Protocol (ASP), which can be separated into four rather independent subprotocols. After a general overview, the start-up protocol, buffer control protocol, master/slave synchronization protocol, and master switching protocol are introduced. It is important to mention, that this section concentrates on mechanisms, while possible policies exploiting these mechanisms will be discussed in the next section. 4.1 Overview of the Protocols The start-up protocol initiates the processing of the sinks and sources in a given sync group. In particular, it ensures that the sources synchronously start the transmission and the sinks syn- 1 Additional delays, resulting from devices that buffer a certain amount of data internally or from differing rates R2 and R3, may easily be handled in ASP. It only requires to offset buffering delays and state information of play-out by a fixed or variable amount. However, a detailed description is beyond the scope of this paper. 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 7 chronously start the presentation. Start-up is coordinated by the server, which derives start-up times from estimated transmission times, selects an initial master stream depending on the chosen synchronization policy and sends control messages containing the start-up times to clients. The buffer control protocol is a purely local mechanism, which keeps the fill state of the master stream's play-out buffer in a given target area. The determination of the target area depends on the applied synchronization policy and thus is not subject to this mechanism. Whenever the fill state moves out of the given target area, the buffer control protocol regulates the progress of the master stream by manipulating release rate R2 accordingly. The master/slave synchronization protocol ensures interstream synchronization by adjusting the progress of slave streams to the advance of the master stream. Processing of this protocol only involves a sync group's sink clients, one of them acting as master and the other ones acting as slaves. Whenever the master changes release rate R2, it computes for some future point in time, say t, the master's media time M(t), taking into account the modified value of R2. Then, M(t) and t are propagated in a control message to all slaves. When a slave receives such a control message, it locally adjusts R2 in a way that its stream will reach M(t) at time t. Obviously, this protocol ensures that all streams are in sync again at time t, within the margins of the accuracy provided by clock synchronization. Notice that this protocol does not involve the server and is only initiated when the buffer situation or - in other words - the network conditions have changed. The master switching protocol allows to switch the master role from one stream to another at any point in time. The protocol involves the server and the sink clients, whereas the server is the only instance that may grant the master role. Switching the master role may become necessary when the user changes its synchronization policy or some slave stream enters a critical state, i.e. runs the risk of having a buffer underflow or overflow. A nice property of this protocol is that a critical slave can react immediately: It becomes a so-called tentative master, which is allowed to adjust R2 accordingly. The protocol takes care of the fact that there may be a master and several tentative masters at the same point in time and makes sure that the sync group eventually ends up with a single master. After this brief overview, we will now consider the four protocols in more detail. 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 8 4.2 Start-up Protocol Our start-up procedure is very similar to that described in [EPD94]. The server initializes the synchronous start-up of a sync group's data streams by sending Start messages to each sink and source client. Each Start message contains besides other information a start-up time. All source clients receive the same start-up time, at which they are supposed to start transmitting data units. Similarly, all sink clients receives the same start-up time, which tells them when to start the play-out process. Starting clients simultaneously requires the Start messages to arrive early enough. The start-up time t0 of sources is derived from the current time tnow, the message transmission delay dm experienced by Start messages, and processing delays dproc at the server site: t0 = tnow + dm + dproc. Start-up of sinks is delayed by an additional time to allow the data units to arrive at the sinks' locations and to preload buffers. This delay, called expected delay dexp, is computed from average delays dave,i of the sync group's streams and the buffer delay dpre caused by preloading: dexp = max (dave,i) + dpre, where dpre,i primarily depends on stream i's jitter characteristic. We assume some infrastructure component that provides access to the needed jitter and delay parameters. A Start message sent to a source client (at least) contains start time t0 and the nominal rate R1. Start received by a sink encompasses the start time t0 + dexp, the release rate R2 = R1 and a flag assigning the initial role (i.e. master or slave). Furthermore, it includes some initial parameters concerning the play-out buffer: the low water mark, high water mark and - in case of the master stream - the initial target area (see below). Each client starts stream transmission or play-out at the received start-up time. Therefore, the start-up asynchrony is bounded by the inaccuracy of clock synchronization provided Start messages arrive in time. However, even if some Start messages are too late, ASP is able to immediately resynchronize the `late' streams. 4.3 Buffer Control Protocol Before describing the protocol, we will take a closer look at the play-out buffer (see Fig. 2). The parameter dB(t) denotes the smoothed buffer delay at current time t. The buffer delay at a given point in time is determined by the amount of buffered data. In order to filter out short-term fluctuations caused by jitter, some smoothing function is to be applied. ASP does not require a dis- 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 9 tinct smoothing function. Some examples are the geometric weighting smoothing function [Post81]: dB(ti) = a dB(ti-1)+ (1-a) ActBufferDelay(t), or the Finite Impulse Response Filter as used in [KM94]. For each play-out buffer a low water mark (LWM) and high water mark (HWM) is defined. When dB(t) falls under LWM or exceeds HWM, there is the risk of underflow or overflow, respectively. Therefore, we will call the buffer areas below LWM and above HWM the critical buffer regions. As will be seen below, ASP takes immediate corrective measures when dB(t) moves into either one of the critical buffer regions. Note that the quality of intrastream synchronization is primarily determined by the LWM and HWM values (for details see Sec. 5). For example, a reasonable value for LWM is j/2, where j denotes the jitter of the incoming data stream. The buffer control protocol is executed locally at the sink site of the master stream. Its only purpose is the keep dB(t) of the master stream in a so-called target area, which is defined by an upper target boundary (UTB) and a lower target boundary (LTB). Clearly, the target area must not overlap with a critical buffer region. The location and width of the target area is primarily determined by the chosen synchronization policy. For example, to minimize the overall delay the target should be close to LWM (for details see Sec. 5). The buffer delay dB(t) may float freely between the lower and upper target boundary without triggering any rate adaptions. Changing transmission delays (or a modification of the target area requested by the server) may cause dB(t) to move out of the target area. When this happens, the master enters a so-called adaption phase, whose purpose is to move dB(t) back into the target area. Figure 2 : Play-out Buffer of a Sink High Water Mark Low Water Mark Upper Target Boundary Lower Target Boundary R1' R2 Target Area dB(t) 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 10 At the beginning of the adaption phase, release rate R2 is modified accordingly. The adapted release rate is R2 + Rcorr, where Rcorr = (dB(t) - (LTB + (UTB-LTB)/2)) / L. Length L of the adaption phase determines how aggressive the algorithm reacts. At the end of the adaption phase, it is checked whether or not dB(t) is within the target area. If it is in the target area, R2 is set back to its previous value, the nominal stream rate. Otherwise, the master immediately enters a new adaption phase. In order to keep the slave streams in sync, each adaption of the master stream has to be propagated to the slave streams. This is achieved by the protocol described in the next section. 4.4 Master/Slave Synchronization Protocol The master/slave synchronization protocol ensures that the slave streams are played out in sync with the master stream. This protocol is initialized whenever the master (or a tentative master as will be seen in the next section) modifies its release rate. Protocol processing involves all sink clients, each of which acts either as master or slave. Whenever it enters an adaption phase, the master performs the following operations. First, it computes the so-called target media time for this adaption phase, which is defined to be the media time the master stream will reach at the end of this phase. Assume that the adaption phase starts at real time ts and is of length L. Then the target media time is M(ts+L) = M(ts) + L*(R2 + Rcorr). Subsequently, the master propagates an Adapt message to each slave in the sync group. This message includes the following information: end time te=ts+L of the adaption phase, target media time M(te) at the end of the adaption phase, and a structured timestamp for ordering competing Adapt messages (see next section). When a slave receives an Adapt message, it immediately enters the adaption phase by modifying its release rate R2 according to the received target media time (see Fig. 4). The modified release Figure 3 : Buffer Delay Adaption Buffer Delay dB(t) dB(t) Time t s Target Area ts+L UTB LTB Adaption Phase 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 11 rate is R2= (M(te)-M (ta)) / (te - ta), where ta denotes the time at which the slave received Adapt. At time te (i.e. at the end of the adaption phase), R2 is set back to its previous value, the nominal stream rate. Obviously, this protocol ensures that at the end of each adaption phase all streams in the sync group reach the same target media time at the same point in real time. Between two adaption phases, streams stay in sync as their nominal release rates are derived from global time. As with all synchronization schemes based on the notion of global time, skew among sinks is introduced by the inaccuracy of synchronized clocks, which is assumed to be bounded by e. In our protocol, an additional source of skew is the adaption of release rates at different points in time. The worst case skew Smax during the adaption phase of the master depends on transfer time dm of the Adapt message and master stream's correction rate Rcorr: Smax = dm*|Rcorr| + e. Between adaption phases, the skew is bounded by e. The skew among data streams synchronized by ASP is mainly determined by the inaccuracy of synchronized clocks. Table 1 shows skew estimations among data streams that are played out on the same node as well as on separate nodes in a local and in a wide area network. We assume Figure 4 : Master/Slave Synchronization Sink Clients Estimated Message Transfer Time dm Inaccuracy e of Clocks Expected Skew Smax Same Node < 20 ms 0 ms < 0.4 ms LAN < 50 ms < 10 ms (NTP) < 11 ms WAN 100 .. 1000 ms 10 .. 100 ms [Mill90] 12 .. 120 ms Table 1: Skew During Adaption Phases M(te) M(ta) Message Transfer Time Time t ts te Media Time M(t) Master Stream Maximum Skew before Reaction Adaption Interval ta Slave Stream 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 12 rate corrections of up to 2% of the nominal rate, which is derived from simulation results in Sec. 6. For simplicity, we assume the data units to originate at the same node, i.e. there is no additional skew due to timestamps based on differing clocks. 4.5 Master Switching Protocol In our protocol, we distinguish between two types of master switching. The first type of switching, called policy-initiated, is performed whenever (a change in) the synchronization policy requires a new assignment of the master role. In this case, the server, which enforces the policy, performs the switching just by sending a GrantMaster message to the new master and a Quit- Master message to the old master. GrantMaster specifies the target buffer area of the new master, which is determined by the server depending on the chosen policy. With this simple protocol it may happen that for a short period of time there exist two masters, which both propagate Adapt messages. Our protocol prevents inconsistencies by performing Adapt requests in timestamp order (see below). The second type of switching is recovery-initiated. The slave initiates recovery when its stream becomes critical. A stream is called critical if its current buffer delay is in a critical region and (locally) no rate adaption improving the situation is in progress. A very attractive property of our protocol is that a slave can immediately react when its stream becomes critical. Recovery goes as follows: First, the slave makes a transition to a so-called tentative master (or t-master for short) and informs the server about this by sending an IamT-Master message. Then - without waiting on any response - it enters an adaption phase, in which it adapts release rate R2 in a way that its buffer delay can be expected to move out of the critical region. In order to keep the other streams in sync, it propagates an Adapt request to all other sink clients, including the master. At the end of the adaption phase, a t-master falls back in the slave role. Should the stream still be critical by this time, then the recovery procedure is initiated once more. Obviously, our protocol allows multiple instances to propagate Adapt concurrently, which may cause inconsistencies leading to the loss of synchronization if no care is taken. As already pointed out above, policy-initiated switching may cause the new master to send Adapt messages while the old master is still in place. Moreover, at the same point in time, there may exist any number of t-masters propagating Adapt requests concurrently. It should be clear that stream synchronization can be ensured only if Adapt messages are performed in the same order at each client. This requirement can be fulfilled by including a timestamp in Adapt requests and performing these requests in timestamp order at the client sites. The latter means that a client 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 13 accepts an Adapt request only if it is younger than all other requests received before. Older requests are just discarded. However, performing requests in some timestamp order is not sufficient. Assume, for example, that the master and some t-master propagate Adapt requests at approximately the same time, and the former requests an increase of the release rate, while the latter requests a decrease. For some synchronization policies, this might be a very common situation (see for example the minimum delay policy described in the next section). If the timestamps were solely based on system time and the master would perform the propagation slightly after the t-master, then the t-master's request would be wiped out, although it is the reaction on a critical situation and hence is more important. The stability of the algorithm can only be guaranteed if recovery actions are performed with the highest priority.2 Consequently, the timestamping scheme defining the execution order of Adapt requests must take into account the `importance' of requests. The precedence of Adapt requests sent at approximately the same time is given by the following list in increasing order: (1) requests of old masters (2) requests of the new master (3) requests of t-masters. We apply a structured timestamping scheme to reflect this precedence of requests. In this scheme, a timestamp has the following structure: , where ER denotes a recovery epoch, EM designates a master epoch, and T is the real time when the message tagged with this timestamp was sent. A new recovery epoch is entered when a slave performs recovery, while a new master epoch is entered whenever a new master is selected. So, a recovery epoch may have seen several master epochs. As will be seen below, entering a new recovery epoch requires a new master to be selected. Each control message contains a structured timestamp, which is generated before the message is sent on the basis of two local epoch counters and the local (synchronized) clock. The server and the clients keep track of the current recovery and master epoch by locally maintaining two epoch counters. Whenever they accept a message whose timestamp contains an epoch value greater than the one recorded locally, the corresponding counter is set to the received epoch value. Moreover, a client increments its local recovery epoch counter when it performs recovery, i.e. the IamT-Master message sent to the server already reflects the new recovery period. The server increments its master epoch counter when it selects a new master, i.e. the GrantMaster message already indicates the new master epoch. 2 We assume that at no point in time there exist two t-masters that try to adapt the release rate in contradicting directions, i.e. one tries to increase the rate while the other tries to decrease it. This is achieved by dimensioning the play-out buffer appropriately. 4 THE ADAPTIVE SYNCHRONIZATION PROTOCOL 14 Adapt requests are accepted only in strict timestamp order. Should a client receive two requests with the same timestamps, total ordering is achieved by ordering these two request according to the requestors' unique identifiers included in the messages. As a slave performing recovery enters a new recovery epoch, all Adapt request generated by some master in the previous recovery epoch are wiped out. Similarly, selecting a new master enters a new master epoch, and by this wipes out all Adapt request from former masters. When a master receives an Adapt request indicating a younger master or recovery epoch, it can learn from this message that there exists a new master or a t-master performing recovery, respectively. In both cases, it immediately gives up the master role and becomes a slave. As already mentioned above, a critical slave sends an IamT-Master message when it becomes a t-master. When the server receives such a message indicating a new recovery epoch, it must select a new master. Which stream becomes the new master, primarily depends on the synchronization policy chosen. For example, the originator of the IamT-Master message establishing a new recovery epoch may be granted the master role. All other messages of this type belonging to the same recovery epoch are just discarded upon arrival (see Fig. 5). In summary, in an adaption phase a t-master or master may receive an Adapt or GrantMaster message. They are only accepted if they are younger than all other control messages of the same type received before. If an Adapt request is accepted, a new adaption phase is started based on the target media time included in the accepted request. As mentioned above, a master accepting an Adapt message immediately becomes a slave. If GrantMaster is accepted, the recipient becomes master and acts accordingly. A t-master that has not received GrantMaster by the end Figure 5 : Recovery-initiated Master Switching GrantMaster Server Client 2 Client 3 SLAVE T-MASTER MASTER discard message grant master Client 1 critical critical IamT-Master IamT-Master Adjust Adjust Adjust Adjust 5 SYNCHRONIZATION POLICIES 15 of the adaption phase goes back in the slave role. Of course, if it is still critical by this time, it initiates recovery again. The worst case skew Smax among sinks can be observed when master and a t-master decide to adapt their release rates in opposite directions at approximately the same time. Smax can be shown to be dm*(|Rcorr, master| + |Rcorr, t-master|) + e, where dm denotes the transmission delay of Adapt messages. 5 SYNCHRONIZATION POLICIES The ASP has many parameters for tuning the protocol to the characteristics of the underlying system as well as to the quality of service expected by the given application. A discussion of all these parameters would go far beyond the scope of this paper. Therefore, we will focus on the most important parameters, in particular those influencing the synchronization policy: the low and high water mark, the width of the target area and its placement in the play-out buffer, as well as the rules for granting the master role. The intrastream synchronization quality in terms of data loss due to underflow or overflow is primarily influenced by the LWM and HWM values. A good rule of thumb for the width of the critical regions defined by these two parameters is j/2 for each, where j denotes the jitter of the corresponding data stream. Increasing LWM also increases the quality as the probability of underflow is reduced. On the other hand, this modification may also increase the overall delay, which might be critical for the given application. ASP allows to modify LWM and HWM values while the presentation is in progress. For example, it is conceivable that a user interactively adjusts the stream quality during play-out. Alternatively, an internal mechanism similar to the one described in [KHMS94] may monitor the data loss rate and adjusts the water marks as needed. The width of the target buffer area determines aggressiveness of the buffer control algorithm. The minimum width of this area depends on the smoothing function applied to determine dB(t). The larger the width of the target area, the less adaptions of the release rate are required. Rather constant release rates require almost no communication overhead for adapting slaves. On the other hand, with a large target area there is only limited control over the actual buffer delay. If, for example, the actual buffer delay has to be kept as close as possible to the LWM to minimize the overall delay, a small target area is the better choice. 5 SYNCHRONIZATION POLICIES 16 The location of the target area in the buffer together with the way how the master role is granted are the major policy parameters of ASP. This will be illustrated by the following two examples, the minimum delay policy and the dedicated master policy. The goal of the minimum delay policy is to achieve the minimum overall delay for a given intrastream synchronization quality. To reach this goal the stream with the currently longest transmission delay is granted the master role, and this stream's buffer delay is kept as close as possible to LWM. The target area for the master is located as follows: LTB = LWM and UTB = LWM + D, where D is the jitter of dB(t) after smoothing. Due to changing network conditions it may happen that the transmission delay of a slave stream surpasses the one of the master. This will cause the slave's buffer delay to fall below its LWM triggering recovery. When the server receives an IamT-Master message it grants the master role the originator of this message. If it receives multiple IamT-Master messages originated in the same recovery epoch only the first one is accepted, all the other ones are discarded. In the long run, this strategy ensures that the stream with the longest transmission delay eventually becomes master. The overall delay at time t amounts to the longest transmission delay at t plus LWM, which obviously is the minimal overall delay that can be achieved at t. The possibility of dynamically tuning LWM makes this policy very powerful. By increasing the LWM value the quality but also the overall delay is increased. Conversely, the quality and delay is decreased if LWM is decreased. Consequently, by tuning LWM the user may (interactively) determine the appropriate trade-off between delay and intrastream synchronization quality. The dedicated master policy dedicates the master role to a certain stream. This is typically a stream that is played out at a sink device with a fixed consumption rate R3, such as an audio device. Obviously, the best intrastream synchronization quality for such a stream is achieved if its release rate R2 equals R3, allowing it to operate without duplicating and skipping. The dedicated master policy ensures that R2 and R3 may differ only if some stream in the sync group is critical. During the start-up procedure, the dedicated stream is granted the master role, and the target area is set to its maximum size (LTB = LWM and UTB = HWM), reducing the necessity of rate adaptions to a minimum. When a slave gets critical, it becomes t-master and performs recovery. After recovery, however, the dedicated stream is granted the master role again by the server. 6 SIMULATION RESULTS 17 Not only individual parameters but the entire policy can be changed during presentation. For example, the server may start with the dedicated master policy and later on switch to the minimum delay policy when the overall delay gets unacceptable. When changing the policy, the server may require knowledge about the state of the play-out buffers (e.g. current buffer delay, LWM, HWM). For that purpose, the ASP provides services for requesting buffer state information from clients. In our opinion, the two synchronization policies described above are the most important ones in practice. However, other policies are conceivable as well. 6 SIMULATION RESULTS The section presents some simulation results showing the behavior of ASP. In our simulations, we have used both measured and synthetically generated delays. First, the behavior of the buffer control protocol is shown, afterwards results of the master/slave interstream synchronization protocol including role switches among master and slave. The simulation of the master control protocol is based on delay data measured on the Internet. Incoming data units have an average delay between 300 and 400 ms (see Fig. 7). The data units are buffered in the play-out buffer of the master stream. Its target area is first set to 300-500 ms. The buffer delay is smoothed by the geometric weighting smoothing function with a set to 0.9. The buffering leads to a nearly constant release rate R2 (see Fig. 6), which most of the time Figure 6 : Buffer Delay and Release Rate of a Master Stream Master Release Rate R2 Time [ms] R2 [DU/sec] 9.5 9.6 9.7 9.8 9.9 10 10.1 10.2 10.3 800 3700 6599 9488 12386 15286 18186 21086 23986 26886 29796 32721 35621 38521 41392 44250 47126 49991 52891 55791 58708 61613 64513 67413 70313 73213 76113 79013 Master Current(t) Time [ms] Current(t) [ms] 0 100 200 300 400 500 600 800 3700 6599 9488 12386 15286 18186 21086 23986 26886 29796 32721 35621 38521 41392 44250 47126 49991 52891 55791 58708 61613 64513 67413 70313 73213 76113 79013 Buffer Delay Release Rate Release Rate [DU/s] Buffer Delay [ms] Upper Target Boundary Lower Target Boundary Modification of Target Area 6 SIMULATION RESULTS 18 equals the nominal rate of 10 frames per second. Nearly no data loss due to late arrival could be observed (see Fig. 7). As mentioned before, ASP supports the adaption of target levels even when a presentation is in progress. By moving the target area to 100-400 ms, the overall delay of the played out data units could be reduced by 100 ms (see Fig. 7). However, the quality of the stream was degraded. The loss rate of data units discarded due to late arrivals is higher. Results of a simulation of the master/slave synchronization and the master switching protocol are shown in Fig. 8 and Fig. 9. The delay of data units are synthetically generated with a mean Figure 7 : Delay and Losses of Data Units Figure 8 : Buffer Delays of Stream 1 and Stream 2 Data Losses Time [ms] Sum of Lost Data Units 0 5 10 15 20 25 30 800 3600 6399 9191 11986 14786 17586 20386 23186 25986 28786 31621 34421 37221 40021 42763 45530 48307 51091 53891 56691 59513 62313 65113 67913 70713 73513 76313 79113 End-to-End Delay Time [ms] Delay [ms] 0 100 200 300 400 500 600 700 800 900 1000 800 3700 6599 9488 12386 15286 18186 21086 23986 26886 29796 32721 35621 38521 41392 44250 47126 49991 52891 55791 58708 61613 64513 67413 70313 73213 76113 79013 Delay [ms] End-to-End-Delay Delay (released data units) Delay (incoming data units) Data Losses Sum of Lost Data Units Modification of Target Area Current(t) Stream 2 Time [ms] Current(t) [ms] 0 10 20 30 40 50 60 70 80 150 3046 5947 8851 11752 14652 17554 20454 23355 26255 29155 32056 34956 37856 40756 43656 46556 49456 52356 55256 58156 61056 63956 66856 69757 72657 75557 78457 Current(t) Stream 1 Time [ms] Current(t) [ms] 0 10 20 30 40 50 60 70 80 150 3046 5947 8851 11752 14652 17554 20454 23355 26255 29155 32056 34956 37856 40756 43656 46556 49456 52356 55256 58156 61056 63956 66856 69757 72657 75557 78457 Buffer Delay [ms] Buffer Delay [ms] Buffer Delay 1 Buffer Delay 2 7 SUMMARY 19 delay of 100 ms and 120 ms, respectively. Low and high water marks are set to 29 ms and 79 ms, respectively. The master's target area is between 29 ms and 49 ms. Initial master stream is stream 1. As shown in Fig. 8, the master role is switched to stream 2 when the buffer delay of the stream falls below the low water mark the first time. Stream 2 remains master until the end of the simulation. The master stream influences the slave's rate the same way as influencing its own by setting target stream times. However, rate adaptions of both streams are seldom. In Fig. 9, the synthetically generated network delay of data units and the resulting end-to-end delay of both streams are shown. Obviously, the resolution of the graphic does not allow to depict any skew while altering delays of both streams. The curves of their end-to-end-delays lie directly over one another. 7 SUMMARY In distributed multimedia applications, synchronization protocols are required to restore temporal relationships among data streams that were transmitted over separate communication channels. The protocols must be able to deliver a intrastream and interstream quality that is appropriate for the particular application scenario, even under changing network conditions. The ASP achieves interstream synchronization in distributed environments. It adapts to changing network conditions and allows to tune the quality of data streams to application requirements by supporting a wide range of synchronization policies. Stream quality is improved by Figure 9 : Network and End-to-End-Delay of Data Units Sync Delay / Skew Time [ms] Delay [msec] 140 142 144 146 148 150 152 154 156 158 150 3046 5947 8851 11752 14652 17554 20454 23355 26255 29155 32056 34956 37856 40756 43656 46556 49456 52356 55256 58156 61056 63956 66856 69757 72657 75557 78457 Network Delays Time [ms] Delay [msec] 0 20 40 60 80 100 120 140 160 150 3046 5947 8851 11752 14652 17554 20454 23355 26255 29155 32056 34956 37856 40756 43656 46556 49456 52356 55256 58156 61056 63956 66856 69757 72657 75557 78457 Delay [ms] Network Delays Sync Delay/Skew Delay [ms] 8 ACKNOWLEDGEMENTS 20 reacting on critical situations immediately. Furthermore, by limiting reactions to critical situations, a considerably low message overhead is achieved. The simulation results show good performance even when there is no guaranteed quality of the underlying communication system. The design of the ASP was conducted in the context of the CINEMA project [RBH94], [RoHe94]. CINEMA is an environment to establish and control multimedia applications in distributed environments. The next step will be the integration of the Adaptive Synchronisation Protocol into the CINEMA architecture. This will allow us to experiment with the ASP in real-world applications, gather more experience with its behavior and verify our simulation results. 8 ACKNOWLEDGEMENTS We would like to thank Markus Bader for contributing many ideas and the fruitful discussions we had with him. 9 REFERENCES [AgSo94] Nipun Agarwal and Sang Son. Synchronization of Distributed Multimedia Data in an Application-Specific Manner. In 2nd International Conference on Multimedia, San Francisco, USA, pages 141?148, 10 1994. [AnHo91] David P. Anderson and George Homsy. Synchronization Policies and Mechanisms in a Continuous Media I/O Server. Report No. UCB/CSD 91/617, Computer Science Division (EECS), University of California, Berkeley, CA, 2 1991. [CCGH92] Andrew Campell, Geoff Coulson, Francisco Garcia, and David Hutchison. A Continuous Media Transport and Orchestration Service. In SIGCOMM'92 Conference Proceedings Communications Architectures and Protocols, pages 99? 110, 8 1992. [EPD94] Julio Escobar, Craig Partridge, and Debra Deutsch. Flow Synchronization Protocol. IEEE Transactions on Networking, 1994. [IBM92] IBM Corporation. Multimedia Presentation Manager Programming Reference and Programming Guide 1.0, IBM Form: S41G-2919-00 and S41G-2920-00, 3 1992. [KHMS94] Thomas Käppner, Falk Henkel, Michael Müller, and Andreas Schröer. Synchronisation in einer verteilten Entwicklungs- und Laufzeitumgebung für multimediale Anwendungen. In Innovationen bei Rechen- und Kommunikationssystemen, pages 157?164, 1994. [KM94] Daniel Köhler and Harald Müller. Multimedia Playout Synchronization Using Buffer Level Control. 2nd International Workshop on Advanced Teleservices and 9 REFERENCES 21 High-Speed Communication Architectures, Heidelberg, Germany, 9 1994. [Mill90] David L. Mills. On the Accuracy and Stability of Clocks Synchronized by the Network Time Protocol in the Internet System. Computer Communications Review, pages 65?75, 1990. [Post81] Postel. Transmission Control Protocol, DARPA Internet Program, Protocol Specification. RFC 793, 9 1981. [RaRa92] Srinivas Ramanathan and P. Venkat Rangan. Continuous Media Synchronization in Distributed Multimedia Systems. In 3nd International Workshop on Network and Operating System Support for Digital Audio and Video, 11 1992. [RBH94] Kurt Rothermel, Ingo Barth, and Tobias Helbig. Architecture and Protocols for High-Speed Networks, chapter CINEMA - An Architecture for Distributed Multimedia Applications, pages 253?271. Kluwer Academic Publishers, 1994. [RoHe94] Kurt Rothermel and Tobias Helbig. Clock Hierarchies: An Abstraction for Grouping and Controlling Media Streams. Technical Report 2/94, University of Stuttgart/IPVR, 4 1994. [RRK93] P. Venkat Rangan, Srinivas Ramanathan, and Thomas Käppner. Performance of Inter-Media Synchronization in Distributed and Heterogeneous Multimedia Systems. Computer Networks and ISDN Systems, 1993.