Transcript Video Source Traffic Modeling

Χαρακτηρισμός και Μοντελοποίηση
Πηγών Video
Characterization and Modeling
of Video Sources
Γαβαλάκης Πέτρος
Πέμπτη, 22 Μαρτίου 2001
TUC Information and Network Lab
Video Source Traffic Modeling
1
Presentation Flow









Uncompressed Video Characteristics
Compression Techniques
Compressed Video Semantics
Burstiness
Statistical Multiplexing
Need for Video Source Modeling
Basic Modeling Methods
General classification
Conclusions
TUC Information and Network Lab
Video Source Traffic Modeling
2
Video Semantics






A typical video sequence is usually described as a collection of
independent video shots called scenes.
Each scene is an ordered set of video frames depicting a realtime continuous action
Except from static real-world scenes, a typical video sequence
consists of various artificial effects (e.g. camera movement ,
zooming,picture in picture,graphics etc.)
The assumption of scene independence does not seem to hold in
most video sequences
The scenes are in fact correlated.There is a low probability of
having a short scene while the probability of having long ones
decades relatively slow
On the contrary to the scene complexity, the scene length seems
to be not correlated
TUC Information and Network Lab
Video Source Traffic Modeling
3
Video Semantics(2)
TUC Information and Network Lab
Video Source Traffic Modeling
4
Uncompressed Video Streams

The nature of video information sources varies widely
depending on:







Content of video per scene
Scene details and object or camera movement
Quality required
Various video streams (e.g. videophone,movie,news,etc.)
have different statistics (e.g. scene length duration)
Bandwidth requirements for uncompressed video
100-240 Mbps
Uncompressed HDTV streams require around 1Gbps for
proper delivery
Redundancy – need for compression
TUC Information and Network Lab
Video Source Traffic Modeling
5
Video Compression Techniques


Compression is achieved by removing redundancy
Redundancy types in video signal:
• within a video frame (intra-frame): spatial
• between frames in close proximity (inter-frame) : temporal

Compression methods:
• Lossless or lossy
• Exact recovery or not
• Symmetric or asymmetric
• Same amount of computational effort in coder and decoder or not

MPEG-1
• Quality similar to that of a VHS
• Bit-rate approximately 1.2 Mbps

MPEG-2
• Broadcast quality video
• Bit-rate: 4-6 Mbps
• Wide range for rate and resolution
TUC Information and Network Lab
Video Source Traffic Modeling
6
Characteristics of compressed video





Statistical behavior is described by using histograms and
correlation functions
Correlations arise as a consequence of visual similarities
between consecutive images (or parts of images) in video
streams
Compression results in a reduction in these correlations
Compressed stream still contains considerable amount of
correlations
Correlation along with different information content of
each frame leads to burstiness
TUC Information and Network Lab
Video Source Traffic Modeling
7
Classification of compressed video
variability

Interframe variability:



Intrascene variability:




Discontinuous variation before and after change of scene
Long term
Short term
Smooth variation with temporal correlations
Occasional large variations due to subject and camera motion
Intraframe variability:
Variations that have periodicity due to image scanning
and block processing by encoding techniques
 Usually smoothed by the use of pre-buffers during encoding
and packetization

TUC Information and Network Lab
Video Source Traffic Modeling
8
Burstiness


One simple definition: Ratio between peak and average bit
rate (PAR)
Burstiness indicates the presence of non-negligible positive
correlations between cell inter-arrival times
TUC Information and Network Lab
Video Source Traffic Modeling
9
Other Bit-Rate Burstiness Measures

Bit-rate distribution




Autocorrelation Function




Expresses temporal variations
Coefficient of Variation


Average bit-rate
Peak bit-rate
Variance
Uncorrelated streams have fixed CoV
Useful when measuring multiplexing characteristics when VBR
signals are buffered and statistically multiplexed
Scene duration distribution
Average duration of peaks

Useful to estimate probability of buffer overflow
TUC Information and Network Lab
Video Source Traffic Modeling
10
Burstiness – Network issues


“If much of the traffic is bursty it results in poor network
performance”
The above is true when deterministic multiplexing is used
by the network:




Each connection is allocated its peak bandwidth
Large amounts of bandwidth is wasted for bursty connections
If burstiness is adequately reflected in network
management it can lead to multiplexing gain
Need for statistical multiplexing
TUC Information and Network Lab
Video Source Traffic Modeling
11
Statistical Multiplexing 1/2

The statistical multiplexer can be seen as a finite capacity
queueing system with buffer size B (in cells) and one
server with service rate C
TUC Information and Network Lab
Video Source Traffic Modeling
12
Statistical Multiplexing Model 2/2





In statistical multiplexing, a VBR connection is allocated its
“statistical” bandwidth (less than its peak but more than its
average bit rate)
The statistical bandwidth of a connection depends not only on its
own stochastic behavior but also strongly on the characteristics
of existing connections
Bandwidth gain is attained by allowing the sum of the peak rates
of the input streams exceed the service rate of the multiplexer
This results in queuing and possible buffer overflow
Need for estimates for a number of independent multiplexed
signals:






Total statistical transmission bandwidth
Resulting utilization
Required buffer size
Probability of buffer overflow
Rate of packet discard
Distribution of packet delay
TUC Information and Network Lab
Video Source Traffic Modeling
13
Why model video signals


To help user define requirements for network QoS ->
contract
Aid for designing future communication networks using
statistical multiplexing (ATM) – Performance evaluation

Predict:
• Delay arising from statistical multiplexing
• Buffer size required for statistical multiplexing
• Bandwidth required for multiplexed streams


Results used in conjuction with traffic analyses of voice and
data signals to design averall bandwidth.
Admission and policing algorithms to effectively allocate
dynamic resources(buffers,bandwidth) to streams
TUC Information and Network Lab
Video Source Traffic Modeling
14
Effective bandwidth and buffer



One purpose of modeling is determining the “effective”
bandwidth and buffer size
Definition: the minimum amounts of bandwidth and buffer
needed to guarantee a certain level of QoS for the
multiplexed streams
Ways of calculation/prediction



Simulations based on actual data
Problem: In regions of extremely low probability (fore
example estimation of maximum delay)
Mathematical analysis
• Construction of approximate mathematical models
• Models are used to help analysis in low probability regions
• Numerically or by explicit expressions
TUC Information and Network Lab
Video Source Traffic Modeling
15
Traffic models used so far…

Data signals:

Assumptions
• Random packet arrival
• No correlations between arrivals

Speech signals:



Model speech an silence interval durations
On-Off model (mini source)
During “on” fixed inter-arrival time
TUC Information and Network Lab
Video Source Traffic Modeling
16
Modeling difficulties 1/2





For modeling purposes a network can be viewed as a
collection of queues
A server corresponds to a transmission link and there is a
finite buffer associated with each server
Even if incoming traffic is characterized satisfactorily it’s
impossible to solve these queuing problems numerically in
real-time
A well-known approach is to decompose the network into
individual queues and analyze each one in isolation
Even with this assumption that the arrival process of a
connection has the same stochastic with the source,the
solution is still unfeasible if the number of the multiplexed
arrival streams is very large
TUC Information and Network Lab
Video Source Traffic Modeling
17
Modeling Difficulties 2/2




Difficulty to apply in a multi-hop scenario
Useful to Offline dimensioning problems via simulations
Even if feasible, the queuing analysis is done over an
infinite time and for very large buffers which is unrealistic
The use of video models in online traffic control is still an
open research issue
TUC Information and Network Lab
Video Source Traffic Modeling
18
Different approaches for video source
modeling

Use detailed stochastic source models



Matching various statistics of video source
Content-based approach
Different approach for Real-time video sources

Use stochastic bounds to characterize a source

Characterize each video source by a deterministic timeinvariant traffic envelope
TUC Information and Network Lab
Video Source Traffic Modeling
19
Noticed features of coded video




The distribution of bit-rate variations is bell-shaped
The auto-correlation is close to a decaying exponential
function
Coefficient of variation increases duo to positive correlation
of the bit-rate distribution
When multiplexing a series with no temporal correlations
less data accumulates in the buffer than would with a real
video signal
TUC Information and Network Lab
Video Source Traffic Modeling
20
Basic Modeling Methods Overview

AR Model
•
•
•
•

(1/2)
Zero-order -> random series
Simulation method
Doesn’t model scene changes
Tries to match statistics with parameters of model
Maglaris Markov model
• FSM:Each state corresponds to a possible packet rate level
• intra-scene bit-rate variations are smooth ->only transitions to
adjacent states are generated ->birth/date Markov model
• Analytic form for determining SM effects for N sources
• Doesn’t model scene changes:

Simple Scene Change Model
TUC Information and Network Lab
Video Source Traffic Modeling
21
Basic Modeling Methods Overview

Sen Markov Model
•
•
•
•

(2/2)
Markov Modulated Poisson Process model
Two levels {high,low} for bit-rate
Analytic
Models scene changes
Yamada Markov Model
• Analytic
• Two-dimensional
• Attempts to model rapid increase in bit-rate at a scene change
TUC Information and Network Lab
Video Source Traffic Modeling
22
Equivalent Bandwidth method

Each source is of “on-off” type

Parameters of the model
•
•
•
•




Peak traffic rate during “on”
Average length of “on”
Average length of “off”
Source activity
Closed form of the source’s equivalent bandwidth
Realistic when using leaky-bucket
The result is often highly conservative
The useful admission region for many types of sources can
be significantly larger than this estimate
TUC Information and Network Lab
Video Source Traffic Modeling
23
Gaussian Approximation



Each connection is characterized by the average and the
standard deviation of its bit-rate
The method is based on the simplifying assumption that if
the number of sources multiplexed is large,total traffic
behaves as a Gaussian process with mean and variance
the sum of the means and variances of the sources,
respectively
Closed form for two useful estimates




Overflow probability
Upper bound for cell loss probability
It treats all connections as if they have the same cell loss
requirements
It doesn’t take the buffer size into consideration
TUC Information and Network Lab
Video Source Traffic Modeling
24
Compromise approach


A traffic stream with peak rate R,mean rate λ and
equivalent bandwidth C feeding into a buffer of size B is
equivalent to an on-off stream with peak rate C and mean
rate λ, feeding into a buffer of size zero
Results show that this approach can be overoptimistic
when buffer size is small and may lead to higher cell loss
ratios than the user’s desired QoS requirements
TUC Information and Network Lab
Video Source Traffic Modeling
25
Content-based approach





This approach is not based only on matching the various
statistics of the original source but rather it includes
characterization of video content
Need for models to capture both real video styles and
various compression techniques used
Since the encoded video stream is a combination of scene
characteristic and coding algorithm specific mapping,it is
desirable to separate them by identifying the independent
descriptor variable characterizing the scene,frame anf
objects.
Such descriptors may be the scene length,the scene
complexity and the scene motion…
To model intrascene objects,each scene can be further
divided in subscenes and modeled using the same model
TUC Information and Network Lab
Video Source Traffic Modeling
26
General Classification of Video Source models

Short-range models- Burstiness is significantly decreased
when using SM

Renewal models
• No correlations

Markovian and auto-regressive models (AR)
• Exponentially decaying autocorrelations / inter-arrival times

Sub-exponential models
• The decay of the autocorrelations is slower than exponential but
faster than a power function

Long-range dependent (LRD) models –SM can even
increase burstiness


Autocorrelations decay as a power function
Slower decay -> significant correlations even for large lags
TUC Information and Network Lab
Video Source Traffic Modeling
27
Modeling Conclusions (1/2)



Utilization:sum of the average bit-rates to channel capacity
Definition
Results from simulation indicate that there is an
improvement in cell loss performance as more video
streams are multiplexed when using both the actual data
and the corresponding model.(close performance)
TUC Information and Network Lab
Video Source Traffic Modeling
28
Modeling Conclusions (2/2)



Parameters are difficult to estimate in real-time
Usually a training sequence of video streams is used to
estimate parameters for a category (based on content) of
videos
Effectiveness of statistical multiplexing:


The average delay is smaller for larger number of multiplexed
signals
Estimating the appropriate traffic descriptors for VBR video
is a challenging research issue that awaits further work…
TUC Information and Network Lab
Video Source Traffic Modeling
29
References






Admission Control and Bandwidth Allocation in High-Speed
Networks as a System Theory Control Problem by
Ephremides,Wieselthier,Barnhart
Modeling video sources for real-time scheduling by
Lazar,Pacifici,Pendarakis
Traffic Models in Broadband Telecommunication Networks
by Abdelnaser Adas
Statistical Multiplexing by Marwan Krunz
A traffic model for MPEG-coded VBR streams by Marwan
Krunz,Herman Hughes
A content-based approach to VBR Video Source Modeling
by Bocheck,Chang
TUC Information and Network Lab
Video Source Traffic Modeling
30