Lehrstuhl Für Informatik 4 Kommunikation Und Verteilte Systeme

Lehrstuhl für Informatik 4
Kommunikation und verteilte Systeme
Chapter 2: Basics
Chapter 3: Multimedia Systems – Communication Aspects and Services
• Multimedia Applications
and Communication
• “Multimedia” Transfer
and Control Protocols
• Quality of Service and
Resource Management 3.4: Synchronization
• Synchronization • Computer Clocks
• Multimedia • Network Time Protocol
Operating Systems • One-way Delay
Chapter 4: Multimedia Systems Measurements
– Storage Aspects • Synchronization of Media
Streams
Chapter 5: Multimedia Usage
Chapter 3.4: Synchronization Page 1

Why Synchronization?
Necessity:
• Synchronization of different media streams, e.g. in videoconferencing: audio and
video are transmitted as two independent streams: synchronization has to take
place when streams are played
• Furthermore: distributed operations must be coordinated for in-time data delivery
and buffer management
• Most media synchronization schemes demand for knowledge about temporal
relations between source and sink(s) → accurate global time scale required
Example: Audio/Video presentation
with multiple sources Clock offset Source A: Network
• Presentation at sink A ↔ C: OAC Audio delay DAC
must start at TC
• Sources A and B must
start at TC - OAC - DAC Sink C
and TC - OBC - DBC
• Problem: OAC, OBC, Clock offset Source B: Network
DAC, DBC unknown B ↔ C: OBC Video delay DBC
Computer Clocks
Problem of synchronization System

• Universal Coordinated Time (UCT): Processor
International time and frequency standard, based on
synchronized Caesium clocks (accuracy about 10-12 sec)
• Investigation of 20.000 clocks of Internet hosts: Clock
50% show offset > 2 minutes (with respect to UCT), counter
10 % show offset > 4 hours, some several weeks!
Reasons Ticks / tick adjust
• Clock adjustment usually via wrist watch of operator
Prescaler
• Differences in the oscillator frequencies (clock drift)
(e.g. 100 Hz)
→ clocks tend to wander from the exact time
• Drift in parts per million (ppm) sometimes as high as
a few hundred ppm (or some seconds per day)
• Further problems: Clock resolution (as bad as 10 ms), Oscillator
non real-time operating systems (e.g., UNIX) (e.g., quarz)

Computer Clocks / Hardware Oscillators
Typical stability and drift values:
Oscillator type Stability (per day) Drift

Caesium beam 3⋅10-7 ppm 3 ⋅10-6 ppm (per year)
Rubidium cell 5⋅10-6 ppm 3⋅10-5 ppm (per year)
Quarz (digital) 0.05 ppm 0.001 ppm (per day)
Quarz (analog) 0.5 ppm 0.003 ppm (per day)
Quarz (standard) up to 1 ppm up to several 100 ppm (per day)
i.e. up to ≈ 1 ms / day
• Atomic clocks are far too expensive for common use

• Alternative: transmitting time information from hosts with atomic clocks
→ Software-based clock synchronization methods needed

Clock Synchronization in the Internet

Network Time Protocol (NTP) (RFC 1119):
GPS
Atomic clock Synchronized

• Secondary LAN cluster
• servers
Primary Backup path Stratum-4

servers
Stratum-1 Client
Stratum-2 Stratum-3
• Exchange of timestamps between time servers and clients via UDP

• Virtual hierarchy of synchronized Internet hosts
NTP Hierarchy
Primary servers are connected to UCT

sources
Secondary servers are synchronised to primary servers
(Synchronization subnet )
Lowest level servers in users’
More accurate time 1
computers, synchronised to
secondary servers
Note: this is
2 2 only an
example, there
can be more
3 3 3 than three
layers
• The synchronisation subnet can reconfigure if failures occur, e.g.

– a primary that loses its UCT source can become a secondary
– a secondary that loses its primary can use another primary
• Modes of synchronisation: Multicast, Procedure call, Symmetric – depending on the
needed accuracy
NTP Algorithm (Symmetric)

Client sends requests, time server answers with current time ti,2
Client Time server
ti,0 = 15.00.00.000 Delay: 17 ms

ti,1 = 17.00.00.017
ti,2 = 17.00.00.018
ti,3 = 15.00.00.051 Delay: 33 ms
tsrc tdest
Client computes estimated time offset as:
θ iest : =
(t i ,1 − ti ,0 ) − ( t i ,3 − ti ,2 )
=
2.00.00.017 − ( −1.59.59.967 )
= 1.59.59.992 = θ i +
εi
2 2 2
where εi = difference between packet delays on forward and return path

θi = true offset of the two clocks 17 − 33
θ i = 2; ε i = ⋅ 10 −6
2
NTP Algorithm
A B
ti,0
me
ssa
ge
t i ,0 + t i ,3 1
2
θiest = estimation of
offset between A and B
ti,3
me s
sage
2 ti,1
t i ,1 + t i ,2
2
ti,2
time time
NTP Algorithm
Impact of different propagation delays:

• Let tci,1 = time of receiver when message 1 was sent
→ ti,1 = tci,1 + εSi (where εSi = propagation delay from sender to receiver)
• Let tci,3 = time of receiver when message 2 was sent
→ ti,1 = tci,3 + εRi (where εRi = propagation delay from receiver to sender)
→ θ iest =
(t i ,1 − ti ,3 ) − ( ti ,0 − t i ,2 )
2
=
( t c
i ,1 − t ic,3 ) (
− ( t i ,0 − ti ,2 ) + ε iS − ε iR )
2
ε iS − ε iR
= θi +
2

Applicability of NTP
Problems
• Estimated time depends on packet delays, which are mostly non-symmetric
→ Accuracy drops in case of asymmetric routing and high network load
• Typical precision in the order of a few tens of ms (even for time servers!)
• Errors propagate through the synchronization network
• Slow clock adaptation by tick adjustment of client clock counter
→ Oscillations with amplitudes as high as 10 ms
Still: Sufficient accuracy for most multimedia applications ...
... but not for delay measurements:
• Mean one-way delays in national WANs (e.g. GWIN) usually well below 20ms
→ NTP’s “long-term” accuracy not sufficient here
→ New measurement approach needed

One-Way Delay Measurements
• Approach:
Delay measurement to first synchronize oscillator frequencies
Correction of timestamps by measured drift
Subsequent estimation of clock offset
• Drift influence on delays: 1000 probe packets, 10 s interdeparture delay
cisco-rz.rz.rwth-aachen.de rcs2.urz.tu-dresden.de
80
Measured delays [ms]

200
Measured drift [ms]
100 Round-Trip 60
0 Forward path 40
Return path
-100 20
-200 0
0 1000 2000 3000 4000 5000 0 1000 2000 3000 4000 5000
Time [seconds] Time [seconds]

• Drift estimation:
Measured latencies show clear linear behavior, errors due to delay variances
Running minimum approach to eliminate delay fluctuations
Linear regression on first derivate yields estimator for relative drift
• Running minima: minimum calculated for a window size of 50 packets (500 s)

200 50
Measured drifts [ms]
100 Round-Trip 40
Forward path 30
0
Return path 20
-100
10
-200 0
0 1000 2000 3000 4000 5000 0 1000 2000 3000 4000 5000
Results of drift estimation:

• Aachen: Forward path: -33.93 ppm
Return path: +34.15 ppm
• Dresden: Forward path: +2.001 ppm
Return path: -2.001 ppm
• Adaptation of sender or receiver timestamps possible
• Correction of timestamps by mean fdrift of the two estimators, e.g. for sender:
t inew
,o = t i ,0 + fdrift ⋅ ( t i ,0 − t 0 ) and t new
i ,3 = t i ,3 + fdrift ⋅ ( t i ,3 − t 0 )
adaptation of sender
where t0 indicates the start of the sampling period
times ti,0 and ti,3 by
• Goodness of estimation indicators: average drift
Equal drift amount on both paths
First derivate of running minima is a constant function
• Several enhancements of this basic algorithm are possible
Estimation of clock offset:

• Assumption: Equal minimum delays on both paths within sampling period
• More general than assuming equal delays for each measurement packet
→ Shift of measured empirical distributions to common minimum:
New distribution offset =

{
min t inew
,3 } {
− t i ,2 + min t i ,1 − t inew
,0 }
2
• Clock offset: difference between sender and receiver clock for arbitrary packet j:
Offset at tj,3: θestj = tj,2 + estimated delay of packet j on return path
• Algorithm performs better than NTP
• Drawback: Higher overhead due to more measurement packets

Results: Empirical one-way delay distributions for Aachen and Dresden
1 1

0.8 0.8
Round-Trip
0.6 0.6
Forward path
0.4 Return path 0.4
0.2 0.2
0 0
-5 0 5 10 15 20 0 10 20 30 40 50 60 70
Example benefits:
• Computation of jitter distribution at the receiver (→ buffer requirements)
• Detection of network bottlenecks (compare forward vs. return path to Dresden)
Quality of Service for Media Objects
Synchronization in principle also is part of QoS, related to the playout of multimedia data:
• QoS specification of single Logical Data Units (LDUs), e.g.
Image Video Audio

Color Depth Color Depth Sampling Method
Resolution Resolution Sampling Size
Frame rate Sample rate
Jitter Jitter
Error rate Error rate
• QoS specification concerning two related media objects:

Acceptable skew between presentation of different objects
Production level synchronization: QoS guaranteed prior to presentation (e.g.
prefetching of video frames and playback with synchronized audio)
Human perception of synchronization
Quality of Service for Media Objects
Guidelines for human perception of synchronization:
Media combination Mode, Application QoS

Video / Animation Correlated ± 120 ms
Video / Audio Lips synchronization ± 80 ms
Video / Image Overlay ± 240 ms
Non-overlay ± 500 ms
Video / Text Overlay ± 240 ms
Non-overlay ± 500 ms
Audio / Animation Event correlation e.g., dancing ± 80 ms
Tightly coupled (e.g., stereo) ± 10 ms
Audio / Audio Tightly coupled (e.g., stereo) ± 10 ms
Loosely coupled (e.g., background music) ± 500 ms
Audio / Image Tightly coupled (e.g., music with scores) ± 5 ms
Loosely coupled (e.g., slide show) ± 500 ms
Audio / Text Text annotation ± 240 ms

QoS for Multiple Related Media Objects
Example of skew specification:

• Video with audio parallel in English and Spanish
• Requirements:
1. max skew(video ahead_of audio-english): 80 ms
2. max skew(audio-english ahead_of video): 80 ms
3. max skew(video ahead_of audio-spanish): 80 ms
4. max skew(audio-spanish ahead_of video): 80 ms
5. max skew(audio-english ahead_of audio-spanish): 400 ms
6. max skew(audio-spanish ahead_of audio-english): 400 ms
In shortened from:
1+2: V-AE ∈ [-80:80]
3+4: V-AS ∈ [-80:80]
5+6: AS-AE ∈ [-400:400]
The first requirements cannot be satisfied if AS-AE ∉ [-160:160]
This results in the following modification of the requirements
QoS for Multiple Related Media Objects
Modified requirements:
1. max skew(video ahead_of audio-english): 80 ms

2. max skew(audio-english ahead_of video): 80 ms
3. max skew(video ahead_of audio-spanish): 80 ms
4. max skew(audio-spanish ahead_of video): 80 ms
5. max skew(audio-english ahead_of audio-spanish): 160 ms
6. max skew(audio-spanish ahead_of audio-english): 160 ms
AE-V ∈ [-80:80]
→ AE - AS = (AE-V) + (V-AS) ∈ [-160:160]
V-AS ∈ [-80:80]

Synchronization Specification
Describes all temporal dependencies of the included objects in a multimedia

environment:
• Time relations between presentation units
(e.g., spacing between succeeding video frames: 40 ms)
• QoS descriptions of media objects
(e.g., maximum jitter of 125 ms for audio frames)
• Time relations between different media objects
(e.g., lip synchronization in an audio/video sequence: ± 80 ms)
• QoS descriptions between different media objects
(e.g., maximum jitter of audio in a slide presentation: 500 ms)
→ Synchronization specification is an essential part of the description of a
multimedia object!

Synchronization Specification
Requirements
• Treatment of each media object as a single logical unit
• Abstraction of the media object contents
• Easy description of all types of synchronization
• Integration of time-dependent and time-independent media objects
• Handling of user interaction
• Definition of QoS requirements
• Support of hierarchical levels of synchronization (for complex scenarios)
Methods
• Interval-based specification
• Axes-based synchronization
• Control flow-based synchronization
Hierarchical specification
Specification via reference points
Timed Petri Networks
• Event-based synchronization
• Scripts
Synchronization Specification Example

time
A Interaction
RI
A2 P4
V P1 P2 P3
AN1 AN2 AN3
α β γ ε χ
α: A lip synchronized audio/video sequence is shown

β: A recorded user interaction
γ: 3 pictures
δ: An animation which is partially audio commented
ε: An interaction, e.g. a multiple choice question is shown until the user has made a selection
χ: A final picture is presented after the user has made his choice
Interval-based Specification
Presentation duration is represented as interval

• Basic types of temporal relations between objects:
A B A meets B A B
A before B
A A during B A
A overlaps B
B B
A A finishes B A
A starts B
B B
A equals B A
Enhanced interval-based method:
B • 29 interval relations can be specified
• 10 operations defined to handle these
temporal relations
(before, cobegin, coend, overlaps, while, ...)
• Interval operations have one, two or three parameters

• Operations with one Delay Parameter
A A A A
δ1 δ1 δ1
δ1
B B B B
before(δ1) beforeendof(δ1) cobegin(δ1) coend(δ1)
• Operations with two Delay Parameters
A A A A A
δ1 δ2 δ2 δ2 δ2 δ2
δ1 δ1 δ1 δ1
B B B B B
while(δ1, δ2) delayed(δ1, δ2) startin(δ1, δ2) endin(δ1, δ2) cross(δ1, δ2)

• Operation with three Delay Parameters
A
δ2
δ1 δ3
B
overlaps(δ1, δ2, δ3)
A before(3) B ˆ end of A is 3 time units before the start of B

=
A beforeendof(7) B ˆ A starts 7 time units before end of B
=
B while(3,5) A ˆ A starts 3 time units after start of B and ends 5 time
=
units after start of B

Interval-based Specification - Example
A2
A1
I
RI
P1 P2 P3 P4
V
Audio1 cobegin(0) Video
Animation
Audio1 coend(0) Video /* i.e., Lip synchronization
*/ AN1 AN2 AN3
Audio1 before(0) RecordedInteraction
RecordedInteraction before(0) Picture1
Picture1 before(0) Picture2
Picture2 before(0) Picture3
Picture3 before(0) Interaction
Picture3 before(0) Animation
Animation while(2,5) Audio2
Chapter 3.4: Synchronization
Interaction before(0) Picture4 Page 26
Advantages:
• Easy to handle open (i.e., non-predictable) LDUs (closed LDU: predictable duration,
open LDU: non-predictable duration, typical for live sources, e.g. objects which include
an user interaction)
→ easy to handle user interaction
• Possibility of specifying additional indeterministic temporal relations by defining
intervals for durations and delays
• Disjunction of operators supported (e.g., “not parallel“)
→ Flexible model that supports many run-time presentation variations
Disadvantages:
• Model does not include skew specifications
• No direct specification of relations between subunits of media objects possible
• Flexible specification leads to possible inconsistencies
Example: (A not in parallel with B) & (A while(2,3) User Interaction) &
(User Interaction before(0) B)
→ Conflict: B must be started at end of interaction, but A may still run!
Axes-based Synchronization
Synchronization is based on global timing:
• All objects are attached to a time axis representing an abstraction of real-time, which
is shared among all objects
• Removing one object does not affect other objects
• Synchronization of objects only based on fixed points of time → very good for closed
LDUs, several problems with open LDUs
RI Interaction
unknown duration
A1 P1 P2 P3
Animation
V
P4
A2
?
Time unknown!
Different possibilities:
1. Global timer: all objects attached to a global time axis
2. Virtual time axis: coordinate systems with user defined measurement units;
possibly several time axes are used simultaneously, e.g. for musical notes Page 28
Control Flow-based Synchronization
Basic hierarchical specification:

• Flow of concurrent presentation threads is synchronized in predefined points of the
representation
• Serial and parallel synchronization of “atomic” and “compound” actions
• Atomic actions handle presentation of single-media objects, user input or delay
• Compound actions are combinations of synchronization operators and atomic
actions
• Basic examples for serial and parallel presentations:
Pic. 1 Pic. 2 Pic. 3 Audio Video

Slide sequence Lip synchronization
serial parallel

Specification example: other representation
of previous example
Rec. Pic. 1 Pic. 2 Pic. 3

Interaction
Audio1 Video User Pic. 4

Interaction
An1 An2 Audio2 An3
Advantages Disadvantages
• Easy to understand • Synchronization only possible at the beginning or at
• Natural support of hierarchies the end, thus a split of “Animation“ into AN1, AN2,
• Integration of interactive objects AN3 was necessary
• Skew QoS not definable
• Presentation durations must be added
• Some synchronization scenarios cannot be described
Synchronization via Reference Points:

• Time-dependent media objects are regarded as sequence of closed LDUs
• Start and stop times of media objects: “Reference Points”
• Synchronization between objects by connecting reference points; a set of connected
reference points is a “Synchronization Point”
→ Approach specifies temporal relations between objects without explicit reference
to time
• Example: Slide show with audio sequence (slides are control points)
Slide 1 Slide 2 Slide 3 Slide 4
Audio


The previous example with “Synchronization by reference points”
Rec. Interaction User Interaction
Audio 1 P1 P2 P3 Audio 2 P4
Animation
Video
Animation 1
Animation 2
Problems:
Animation 3
• Requires mechanism for detecting inconsistencies
• Does not allow specification of delays
• Possible solution: Inclusion of a global timer as a reference axis Page 32
Timed Petri Networks

• Directed bipartite graph formalism for specifying state machines, dynamic extension
into the time domain
• Simple Petri Networks consist of places (circles) and transitions (bars),
interconnected by directed arcs (arrows)
• Places can contain tokens (black filled circles)
• Transitions “fire“, if all input places contain tokens: Remove one token from each
input place, add one token to each output place
• Places or transitions consume time, i.e. tokens are delayed
Transition T1
Input Output
Place Place
of T1 of T1
Token Arcs
Control Flow Specification with Timed Petri Networks:

• Places represent LDUs, synchronization is modeled by transitions
• Example: Lip synchronization of audio and video streams
11 ms 11 ms 11 ms 11 ms 11 ms
V1 V2 V3 V4 V5
V1 V1
33 ms 33 ms
• Petri Networks allow all kind of synchronization specifications

• Problems:
Complex specifications
Insufficient abstraction from media contents

Our previous example with Petri Nets: 5s

I P4
A1/V RI P1 P2 P3
A2
60s 20s 5s 5s 5s
AN1 AN3
AN2
Places can be refined to subnets of finer time granularity

Example: 20 sec
5 sec 5 sec 10 sec 0 sec
AN2
0 sec α1 α2 α3 D
=
ˆ D
Event-based Synchronization
Presentations are initiated by synchronization events:
• Examples: start / stop / prepare a presentation
• Events that initiate representations may be external (e.g., timer-based) or internal
(e.g., media object reaching a specific LDU)
• Advantage: Easy integration of interactive objects
• Disadvantages:
Difficult to handle Event Audio1 Timer1
Start ...
Complex specification Object Stop Ready
Skew QoS cannot be defined Audio1 start
No hierarchies
Video start
Maintenance very difficult
Pic.1 start
Timer1 start(3)
Pic.2 start
action
Scripts
• Elements: Activities and subscripts
• Often: Full programming language, extended by timing operations
• Different specification methods can be supported
• Example:
Script based on basic hierarchical method, which supports serial (“>>“-operator),
parallel (“&“-operator) and repeated presentation (“n“ denotes n-fold repetition):
Definition of activities: Script:

activity DigAudio Audio(„video.au“); script Lipsynch AV = Audio&Video;
activity SMP Video(„video.smp“); script Multimedia Example {
activity Xrecorder Record(„window.rec“); AV >>
activity Picture Picture1(„picture1.jpeg“); Record >>
... 3Pictures >>
activity StartInteraction Selection; ((UserInteraction>>Picture4)&AA)
activity RTAnima Animation(„animation.ani“); }
• 3Pictures = Picture1.Duration(5) >> Picture2.Duration(5) >> Picture3.Duration(5)

• AA = Animation & Audio2.Delayed(2)
Scripts
Advantages:
• Powerful and flexible programming environment
• Support of hierarchies and logical objects
• Easy integration of time-independent and interactive objects
Disadvantages:
• Difficult to handle: Procedural approach instead of declarative
• Complex specification
• Implicit usage of common timers necessary
• Special constructs for skew QoS necessary

Conclusions
Synchronization specification methods:

• Different specification capabilities and differing user friendliness
• Proposed methods are just different “views” of the same problem
• Selection of a method depends on target application and environment, there is no
best or worst solution
Examples:
• Simple presentations without user interaction:
Global timer seems best solution (but requires exact clock synchronization!)
• Complex structure with interaction:
Reference point models more suitable
→ Different standards use different specification methods

Lehrstuhl Für Informatik 4 Kommunikation Und Verteilte Systeme

Uploaded by

Copyright:

Available Formats

Lehrstuhl Für Informatik 4 Kommunikation Und Verteilte Systeme

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lehrstuhl Für Informatik 4 Kommunikation Und Verteilte Systeme

Uploaded by

Copyright:

Available Formats

Lehrstuhl für Informatik 4

Kommunikation und verteilte Systeme

Chapter 3.4: Synchronization Page 1

Problem of synchronization System

Chapter 3.4: Synchronization Page 3

Computer Clocks / Hardware Oscillators

Typical stability and drift values:

Oscillator type Stability (per day) Drift

• Atomic clocks are far too expensive for common use

Chapter 3.4: Synchronization Page 4

Clock Synchronization in the Internet

Atomic clock Synchronized

Primary Backup path Stratum-4

• Exchange of timestamps between time servers and clients via UDP

Primary servers are connected to UCT

• The synchronisation subnet can reconfigure if failures occur, e.g.

NTP Algorithm (Symmetric)

ti,0 = 15.00.00.000 Delay: 17 ms

Client computes estimated time offset as:

where εi = difference between packet delays on forward and return path

Impact of different propagation delays:

Chapter 3.4: Synchronization Page 9

Chapter 3.4: Synchronization Page 10

One-Way Delay Measurements

Measured delays [ms]

Chapter 3.4: Synchronization Page 11

One-Way Delay Measurements

Measured delays [ms]

One-Way Delay Measurements

Results of drift estimation:

One-Way Delay Measurements

Estimation of clock offset:

New distribution offset =

Chapter 3.4: Synchronization Page 14

One-Way Delay Measurements

Results: Empirical one-way delay distributions for Aachen and Dresden

Measured delays [ms]

Quality of Service for Media Objects

Image Video Audio

• QoS specification concerning two related media objects:

Quality of Service for Media Objects

Guidelines for human perception of synchronization:

Media combination Mode, Application QoS

Chapter 3.4: Synchronization Page 17

QoS for Multiple Related Media Objects

Example of skew specification:

QoS for Multiple Related Media Objects

1. max skew(video ahead_of audio-english): 80 ms

Chapter 3.4: Synchronization Page 19

Describes all temporal dependencies of the included objects in a multimedia

Chapter 3.4: Synchronization Page 20

Synchronization Specification Example

α: A lip synchronized audio/video sequence is shown

Presentation duration is represented as interval

• Interval operations have one, two or three parameters

• Operations with two Delay Parameters

Chapter 3.4: Synchronization Page 24

• Operation with three Delay Parameters

A before(3) B ˆ end of A is 3 time units before the start of B