Transcript Optimizing the quality of scalable video streams on p2p networks

Optimizing the quality of
scalable video streams on p2p
networks
Raj Kumar Rajendran
Dan Rubenstein
DNA Group, Columbia University
Motivation

Multimedia Streams on P2P networks are
growing in popularity


P2P streams account for large fraction of TCP
traffic!
Our Goal: support live streaming. However
bandwidth


Varies widely with time
Is often insufficient for high-quality video
[email protected], DNA Lab, Columbia University
Known Solutions


Use buffering (pre-fetching)
Divide stream into layers

Facilitates multiple-peer downloads
[email protected], DNA Lab, Columbia University
Using Layered Coding
Use Fine-Grained
Scalable coding



Required small
base-layer
Optional large
enhancement layers
Divide stream into
M equally sized
layers
Bitrate

Video bitrate
M
Enhancement Layers
2
1
Base Layer
Time t
[email protected], DNA Lab, Columbia University
Question



Viewer’s available
bandwidth fluctuates
How do we download?
The two extremes:



Present
Bandwidth
Video layers
Emphasize present
quality
Ensure future first
Future
The tradeoff


Bandwidth utilization vs
Variation in quality
New
Bandwidth
Current time
[email protected], DNA Lab, Columbia University
Structure




Model
Problem Formulation
Ideal solution (offline)
Online Solutions



Naïve Solutions
Hill-climbing Solutions
Results
[email protected], DNA Lab, Columbia University
Discretizing the Video

Like to deal with video
in constant sized units





But video is variable
rate
Divide time into
variable-length epochs
Size epochs to have
same number of video
bits S
Each layer of each
epoch is termed a
chunk
All chunks are of the
same size (S/M bits)
Playback Bitrate
Epoch 0
Epoch 1
Equal Areas (S bits)
Equal Areas (S/M
bits)
M=3
C1
C2
C3
Pre-fetch
Epoch
Time t
[email protected], DNA Lab, Columbia University
The Model(2)

The number of
chunks of video
downloaded in each
epoch varies



Available Bandwidth
(3 chunks)
Epoch lengths vary
Bandwidth varies
2
Bandwidth of
current epoch is
used to download
video chunks for
future epochs
3
4
Downloaded
chunks
Current
Epoch
1
7
6
5
Time t
[email protected], DNA Lab, Columbia University
Discrete Model

Bandwidth


Input: W=<w0,w1,…,wT-1>
the bandwidth vector

wi is the #chunks of
bandwidth available at
epoch i
Playback

Output: A=<a1,a2,…aT> the
allocation vector


ai is the total #chunks
allocated to epoch i
0 ≤ ai ≤ M
0 wi  k 1 ai
k
W=<3,5,1,4,2>
A=<1,2,2,4,4>
Bandwidth
0
1
T
Allocation
2
3
4
1
[email protected], DNA Lab, Columbia University
An Example

Which future chunk should be downloaded with a
chunk of bandwidth currently available ?
Bandwidth
0
Example 1
1
2
3
4
waste
Example 2
M=3
1
Good
Bad
Even quality, Little waste
Varying quality, wasted bandwidth
2
3
4
5
1
[email protected], DNA Lab, Columbia University
Metrics of Performance

Waste





Waste
Unused bandwidth (all
future chunks already
downloaded)
Σwi- Σ ai
Variability

Variance from maximum
possible quality (layers)

Σ(M – ai)2
Variability
Smoothness

Absolute change in quality

ΣAbs(ai-1-ai)
Goal: Minimize these
metrics
Smoothness
[email protected], DNA Lab, Columbia University
Needed

Given:


Produce:



Bandwidth vector <w0,w1,…,wT-1>
Allocation vector <a1,a2,…,aT> that
Minimizes Waste, Smoothness, Variability
Under Constraints



0  ai  M
Quality:
k
T
w

Bandwidth/Time: 0 i k 1 ai
Online: wi needs to be allocated before wi+1
[email protected], DNA Lab, Columbia University
Structure




Model
Problem Formulation
Ideal solution (offline)
Online Solutions



Naïve Solutions
Hill-climbing Solutions
Results
[email protected], DNA Lab, Columbia University
The optimal solution (offline)




5
Is Given all of W
4
Allocates bandwidth 3
2
of last epoch wT
1
first and works its
way back to epoch 1
Allocates wi to the
4
smallest, latest non- M=3
3
full (aj<M) epoch
2
Proved to minimize
1
waste, smoothness
and variability in
paper
Bandwidth
0
1
1
2
2
3
3
4
4
5
[email protected], DNA Lab, Columbia University
Structure




Model
Problem Formulation
Ideal solution (offline)
Online Solutions



Naïve Solutions
Hill-climbing Solutions
Results
[email protected], DNA Lab, Columbia University
Online Solutions (naïve)


Online algorithms make
decisions about wi purely
based on wj,0≤j<i
M=4
Same-Index



W:<3,5,1,4,2>
Allocates all bandwidth
to earliest future epoch
Non-smooth, highvariability, low-waste
Smallest Bin



Allocates all bandwidth
to most empty epoch
Downloads all of layer-1,
then all of layer-2, etc.
Smoother, high-waste
Waste(2)
M=4
1
2
3
4
5
[email protected], DNA Lab, Columbia University
Hill-climbing online solutions


Solution: smooth and low-waste
Guideline


Experiments: Viewers extremely sensitive to
abrupt lowering of video quality.
Solution: algorithms that


Bound the downhill slope of allocations
(decrease in quality)
Then maximize current quality
[email protected], DNA Lab, Columbia University
Largest-Hill



Maximize
current quality
but ensure
gentle fall in
quality
Allocates such
that aj-aj+1<C
Produces hills
with gentle
downhill slopes
Bandwidth
0
1
2
4
4
C=1
M=4
1
2
3
4
4
[email protected], DNA Lab, Columbia University
Structure




Model
Problem Formulation
Ideal solution (offline)
Online Solutions



Naïve Solutions
Hill-climbing Solutions
Results
[email protected], DNA Lab, Columbia University
Results from simulation
How do the algorithms
perform under strain

Waste (%chunks)
Video bitrate approach
bandwidth
Bandwidth fluctuation
increases

Draw bandwidth from Uniform
and Normal distributions

600 epochs

100 runs
10
Best
Same Index
8
Smallest Bin
6
Large Hill
4
Mean Hill
2
Wide Hill
0
0.5
1.5
2.5
Stdandard Deviation
3.9
2.5
2
Smoothness

12
Best
Same Index
1.5
Smallest Bin
Large Hill
1
0.5
Variability

3.7
Base
3.5
Same Index
3.3
Smallest Bin
Large Hill
3.1
Mean Hill
2.9
Wide Hill
2.7
Mean Hill
Wide Hill
2.5
0
0.5
1.5
2.5
Standard Deviation
0.5
1.5
2.5
Standard Deviation
[email protected], DNA Lab, Columbia University
Results from bandwidth
traces
Trace lasted 11,682 secs
Downloaded 80 Mb video
1,2 or more servers
Performance as function of
epoch-lengths (1,2,4,..,128)
secs




3.9
3.8
Same Index
3.6
Smallest Bin
3.5
Large Hill
3.4
Mean Hill
3.3
Wide Hill
3.2
3.1
1.5
2
2.5
3
Standard Deviation
0.7
3.9
0.6
Base
3.7
Same Index
3.6
Smallest Bin
3.5
Large Hill
3.4
Mean Hill
3.3
Wide Hill
3.2
Smoothness
3.8
Variability
Base
3.7
Variability
Bandwidth traces from DSL
Line

Base
0.5
Same Index
0.4
Smallest Bin
0.3
Large Hill
0.2
Mean Hill
Wide Hill
0.1
0
3.1
1.5
2
2.5
Standard Deviation
3
1.5
2
2.5
3
Standard Deviation
[email protected], DNA Lab, Columbia University
Conclusion


A solution that allows live video streaming
on P2P networks
Uses scalable-coding to overcome
insufficient-bandwidth problem


slice stream into lower-bandwidth streams
Clever pre-fetching ensures consistent
high-quality


Provide optimal offline solution
Our online-algorithms performs close to optimal
[email protected], DNA Lab, Columbia University