Optimal Bandwidth Assignment for

Multiple-Description-Coded Video
by
Pengye Xia
A Thesis Submitted to
The Hong Kong University of Science and Technology
in Partial Fulllment of the Requirements for
the Degree of Master of Philosophy
in Computer Science and Engineering
August 2010, Hong Kong
Copyright by Pengye Xia 2010
Authorization
I hereby declare that I am the sole author of the thesis.
I authorize the Hong Kong University of Science and Technology to lend
this thesis to other institutions or individuals for the purpose of scholarly research.
I further authorize the Hong Kong University of Science and Technology
to reproduce the thesis by photocopying or by other means, in total or in part,
at the request of other institutions or individuals for the purpose of scholarly
research.
Pengye Xia
ii
Optimal Bandwidth Assignment for
Multiple-Description-Coded Video
by
Pengye Xia
This is to certify that I have examined the above MPhil thesis
and have found that it is complete and satisfactory in all respects,
and that any and all revisions required by
the thesis examination committee have been made.
Dr. Shueng-Han Gary Chan, Thesis Supervisor
Prof. Mounir Hamdi, Head of Department
Department of Computer Science and Engineering
24 August, 2010
iii
Acknowledgments
First and foremost I oer my sincerest gratitude to my supervisor, Profes-
sor Shueng-Han Gary Chan. Thank him for patiently guiding, encouraging and
inspiring me with his knowledge and wisdom in the scientic research throughout
all these years. It has been a great honor to work with him.
I also would like to thank Professor Lin Gu and Professor Qian Zhang for
kindly participating in my thesis examination committee and providing insightful
comments.
As always, I am heartily grateful to my parents and my wife. Thank them
for encouraging and supporting me all the time.
Lastly, I oer my regards and blessings to all of those who supported me
in any respect during the completion of this thesis.
iv
TABLE OF CONTENTS
Title Page i
Authorization Page ii
Signature Page iii
Acknowledgments iv
List of Figures vi
List of Tables vii
Abstract viii
Chapter 1 Introduction 1
Chapter 2 Related Work 5
2.1 Multiple Description Coding 5
2.2 Simulated Annealing 6
Chapter 3 Problem Formulation 8
Chapter 4 Algorithms for Optimal Assignment of Description Bandwidths 12
4.1 A Threshold and the Exact Solution 12
4.2 SAMBA 14
Chapter 5 Illustrative Simulation Results 17
5.1 Simulation Environment and Parameters 17
5.2 Illustrative Results 19
Chapter 6 Conclusion 26
Bibliography 27
Appendix 30
v
LIST OF FIGURES
1.1 Video streaming using MDC to heterogeneous users. 2
3.1 The optimization model for MDC bandwidth assignment. 9
5.1 Example bandwidth requirement distribution c N
T
(10, 5). 18
5.2 Overall satisfaction (S) versus heterogeneity factor h given dier-
ent schemes. 19
5.3 Overall satisfaction (S) versus mean value () given dierent schemes. 20
5.4 Overall satisfaction (S) versus description number (m) given dif-
ferent schemes. 21
5.5 Overall satisfaction (S) versus description number (m) given . 22
5.6 Overall satisfaction (S) versus description number (m) given k. 23
5.7 Individual satisfaction (S) versus receiving bandwidth with c
N
T
(0, 10). 23
5.8 Individual satisfaction (S) versus receiving bandwidth with c
N
T
(50, 10). 24
5.9 Individual satisfaction (S) versus receiving bandwidth with c
N
T
(100, 10). 24
vi
LIST OF TABLES
3.1 Major symbols used in the paper and their explanations. 11
vii
Optimal Bandwidth Assignment for
Multiple-Description-Coded Video
by
Pengye Xia
Computer Science and Engineering
The Hong Kong University of Science and Technology
Abstract
In video streaming over multicast network, user bandwidth requirement
is often heterogeneous possibly with orders of magnitude dierence (say, from
hundreds of kb/s for mobile devices to tens of Mb/s for high denition TV).
Multiple description coding (MDC) can be used to address this bandwidth het-
erogeneity issue. In MDC, the video source is encoded into multiple independent
descriptions. A receiver, depending on its available bandwidth, joins dierent
descriptions to meet their bandwidth requirements.
An important but challenging problem for MDC video multicast is how to
assign bandwidth to each description in order to maximize overall user satisfac-
tion. In this paper, we investigate this issue by formulating it as an optimization
problem, with the objective to maximize user bandwidth experience by taking
into account the encoding ineciency due to MDC.
We prove that the optimization problem is in general NP-hard. However,
if the description number is larger than or equal to a certain threshold (for a band-
width heterogeneity of a factor of 100, such threshold is 7 descriptions), there is an
viii
exact and simple solution to achieve maximum user satisfaction, i.e. meeting all
the receiving bandwidth requirements. For the case when the description number
is smaller, we present an ecient heuristic called SAMBA (Simulated Annealing
for MDC Bandwidth Assignment) to assign bandwidth to each description given
the distribution of user bandwidth requirement.
We evaluate our algorithm using simulations. SAMBA achieves virtu-
ally the same optimal performance based on exhaustive search. By comparing
with other assignment algorithms, SAMBA signicantly improves user satisfac-
tion. We also show that, if the coding eciency decreases with the number of
descriptions, there is an optimal description number to achieve maximal user
satisfaction.
ix
1
Introduction
With the penetration of broadband Internet access and advances in video com-
pression techniques, there has been increasing interest in both stored and live
video services. Websites like YouTube and MSN Video have oered numerous
on-demand video clips. Online live TV streaming with the use of IP multicast
or peer-to-peer (P2P) technology have also been widely deployed (e.g., AT&T
IPTV, PPLive, GridMedia, Sopcast and TVants) [1] [2].
To stream video to a large group of users, meeting heterogeneous band-
width requirements presents a challenging problem. Such bandwidth requirement
may dier by orders of magnitude, from hundreds of kbits/s for mobile devices to
tens of Mbits/s for high-denition TV. In order to serve all the users, obviously
it is not ecient nor feasible for the server to transcode the stream to each of
the user bandwidths. A simple approach is to encode the video into a number
of streams of dierent bitrates, which users join to best match their bandwidth
requirements. Given the wide range of bandwidth requirements and limited num-
ber of video streams, this approach is clearly not satisfactory, resulting in many
receivers getting a stream substantially lower than their bandwidth requirements.
A much better approach is to use multiple description coding (MDC),
which encodes the video into multiple independent descriptions of dierent
1
Access Network
MDC video server and
description bandwidth
assignment
d
1
d
2
d
m
descriptions

Figure 1.1: Video streaming using MDC to heterogeneous users.

bandwidth [36]. The descriptions can be arbitrarily combined to best match
users bandwidth requirement. Such approach provides many more options of
video bitrates to meet dierent user requirements e.g., m descriptions provide up
to 2
m
dierent video bitrates [5].
1
A user chooses to receive a set of descriptions,
where the sum of their bandwidth best matches the user bandwidth requirement.
We illustrate in Figure 1.1 video streaming using MDC to heterogeneous
users. The video is encoded into m descriptions with bitrates d
1
, d
2
, . . . , d
m
. The
users, depending on their access bandwidth, get the descriptions that best match
their bandwidth requirements so as to maximize their video quality.
In this paper, we study optimal bandwidth assignment for descriptions
given heterogeneous bandwidth requirements. We expect an optimal assignment
because of the following: if description bandwidths are set too high, the low-
bandwidth receivers may not benet from them (as joining them may exceed
their bandwidth), leading to low video quality. On the other hand, if description
1
In this paper, we use user and receiver interchangeably.
2
bandwidths are set too low, those high-bandwidth receivers may not be able
to fulll their bandwidth by joining them, leading again to low video quality.
Therefore, we expect optimal description bandwidths to achieve the best overall
video quality.
The contributions of our work are as follows:
1. Problem formulation and complexity analysis: Given heterogeneous user
bandwidth requirements, we formulate an optimization problem assigning
bandwidth to each description so as to maximize overall user satisfaction.
The user satisfaction is a function of coding eciency as well as bandwidth
requirement. We prove that the optimization problem is in general NP-
hard.
2. An exact solution for description number larger than a certain threshold:
Our problem is in general NP-hard. However, when the number of descrip-
tions is larger than or equal to a certain value (for a bandwidth heterogene-
ity factor of 100, such threshold is 7), we show that the problem can be
solved exactly and eciently. Our solution takes only O(m) computational
time to set m description bandwidths with all user bandwidth requirements
fully matched. In other words, maximum overall user satisfaction can be
achieved in this case.
3. An ecient heuristic for smaller description number: For the case where m
is lower than the threshold, we present an ecient heuristic called SAMBA
(Simulated Annealing for MDC Bandwidth Assignment) to set the descrip-
tion bandwidths. SAMBA is shown to be ecient, and virtually matches
the optimum based on exhaustive search. As compared with other simple
assignment algorithms, our algorithm can achieve much higher user sat-
isfaction. Using SAMBA, we further show that, if the coding eciency
decreases with the description number, there is an optimal m to achieve
maximum user satisfaction. Such m is typically small (in the range of 3-5).
3
This paper is organized as follows. We review related work in Chapter 2,
and describe our problem formulation in Chapter 3. In Chapter 4, we show an
exact assignment method given description number not lower than the threshold,
and SAMBA to solve the general problem. Illustrative simulation results and
comparisons are presented in Chapter 5. We conclude in Chapter 6.
4
2
Related Work
In Section 2.1, we introduce the related work on MDC bandwidth assignment. In
Section 2.2, we give a brief introduction on simulated annealing, which is used as
optimization technique in the later chapters.
2.1 Multiple Description Coding
Multiple description coding (MDC) has found numerous applications in video
streaming [711]. Much of these previous work on MDC only focus on its error
resilient techniques to ensure transmission robustness, and have not considered
the assignment of description bandwidth to achieve system performance as inves-
tigated in this paper.
Other methods used in multirate video multicast include layered coding
(or scalable video coding), where higher layer can be joined only if all the lower
layers have been chosen. Performance analysis of layered coding and compar-
isons with MDC can be found in [1214]. In contrast to layered coding, each
description in MDC can be joined or left independently. This exibility makes
MDC a very good candidate to match heterogeneous video streaming rate re-
5
quirements. Furthermore, because the descriptions are not coupled as tightly
as in layered coding, MDC can achieve better error containment in case pack-
ets are lost. There has been work on optimal bandwidth assignment for layered
coding [15]. However, the techniques used for layered coding cannot be directly
applied to MDC because the complexity MDC optimization is much higher due
to the combinatorial nature of the problem. MDC has higher coding ineciency
as compared with layered coding [8, 1618]. There has been seldom work on how
to optimally assign description bandwidth with such eciency consideration. We
study this issue here.
The work in [19, 20] have addressed optimal bandwidth assignment prob-
lem for MDC. We dier here in several major ways. Firstly, our paper provides
more general formulation with coding eciency consideration. Furthermore, we
show that when the description number is no less than a certain threshold, there
is a simple and ecient algorithm to achieve exact optimum which matches all
the receiving bandwidths in the network. We also show that there is an optimal
description number to achieve the best user satisfaction, which has never been
studied in the literature before. Our approach based on simulated annealing is
ecient and achieves performance close to exhaustive search.
2.2 Simulated Annealing
Simulated annealing was rst proposed by Kirkpatrick et al in 1983 as an ap-
proach to nd approximate solution for dicult combinatorial optimization prob-
lems [21]. This approach takes the concept from statistical mechanics and is
inspired by the behavior of physical systems in the annealing process
1
.
Given a combinatorial problem, we try to nd a solution with lowest cost
dened by a cost function. A local optimization technique iteratively improves an
1
Annealing is a process of heating and slowly cooling down to toughen a subject and reduce
its brittleness.
6
initial solution by making small local alternations. The cost is lowered down after
each iteration and a local optimum is found if the cost can not be lowered any
further. Simulated annealing is one of the local optimization techniques, however,
it advances in its ability to approach global optimum by randomizing the process.
The randomization is done by occasionally allowing a solution with higher cost
in order to avoid being trapped in the local optima. The degree of randomization
(i.e., intuitively, the probability of accepting a higher cost solution) is gradually
lowered down to ensure the algorithm converges a local optimum. This process
is analogous to the process of slowly cooling down in annealing. It is proved
that simulated annealing can nd the global optimum by carefully decreasing the
degree of randomization [22].
Simulated annealing has been applied to various areas to solve combinato-
rial optimization problems. In [23, 24], an experimental studies are conducted on
using simulated annealing to solve graph partitioning, graph coloring and number
partitioning problems. In [22], simulated annealing is applied to image segmen-
tation using Markov-Random-Field model. A generic framework of solving an
optimization problem using simulated annealing is provided in [23]. In this pa-
per, we apply simulated annealing to solve the bandwidth assignment problem
for MDC.
7
3
Problem Formulation
Consider a video stream to be accessed by a large pool of users with heterogeneous
bandwidth requirements. In Figure 2, we show the optimization being done at
the server. The server encodes the stream into multiple descriptions, given the
description number m, user bandwidth requirement c
j
and its importance (in term
of a weight value w
j
). Users employ a greedy approach in joining the descriptions
to maximize their video quality, i.e., they join the descriptions so that the total
bandwidth best matches the bandwidth requirement without overowing. The
user can use exhaustive search to nd the best combination of descriptions, which
is simple due to small search space.
Denote the bandwidth of description i by d
i
. Then

d is m-dimensional
vector (sorted in the increasing order) and represents a particular bandwidth
assignment for the descriptions. The total joined video bandwidth v
j
is the sum
of received description bandwidths. Clearly we need
v
j
c
j
. (3.1)
Let K
ij
{0, 1} be a binary number with 1 indicating that user j chooses de-
8
Optimization
Input Output
Optimal
description
bandwidth
assignment
(d
1
, d
2
, , d
m
)
description
number m
bandwidth
requirement
and weight
information
(c
j
, w
j
) for
each user j
Figure 3.1: The optimization model for MDC bandwidth assignment.
scription i. We have
v
j
=
m

i=1
K
ij
d
i
. (3.2)
We consider that bandwidth is normalized to some unit (say, 50 kb/s), and hence
c
j
and d
i
are integral. The heterogeneity factor h is dened as the dierence
between maximum and minimum user bandwidth requirement, i.e.,
h = max
j
c
j
min
j
c
j
+ 1. (3.3)
Dene r
j
the bandwidth matching factor given by the ratio of v
j
and c
j
, i.e.,
r
j
=
v
j
c
j
. (3.4)
Dene
m
(0, 1] as the coding eciency factor given m descriptions,
which decreases with m. We model user individual satisfaction as a monotonically
increasing function f in terms of r
j

m
. The individual satisfaction of user j, is
9
hence given by
S
ind
(

d, c
j
) = f (
m
r
j
) . (3.5)
Let n be the number of users in the network. The overall network satis-
faction is hence given by
S(

d) =

n
j=1
w
j
S
ind
(

d, c
j
)

n
j=1
w
j
. (3.6)
Our objective is then to nd optimal bandwidth assignment

d

so as to maximize
Equation (3.6) subject to Equations (3.1), (3.2), (3.4) and (3.5), i.e.,
S

= S(

) = max

d
S(

d). (3.7)
The problem is NP-hard (shown in the Appendix, by nding a polynomial
reduction from the subset sum problem).
10
Table 3.1: Major symbols used in the paper and their explanations.
Symbol Explanation
d
i
i
th
description bandwidth
m description number
n number of users
h heterogeneity factor
c
j
bandwidth requirement for user j
v
j
total joined video bandwidth
r
j
bandwidth matching factor, dened as
the ratio of v
j
and c
j
w
j
weight for user j, which represents the
user importance

m
coding eciency factor given mdescrip-
tions
base factor used to model coding e-
ciency factor

d description bandwidth assignment vec-

tor
S
ind
individual satisfaction given description
bandwidths and user bandwidth re-
quirement
S overall network satisfaction given de-
scription number and bandwidth as-
signment
S

optimal overall satisfaction

f individual satisfaction function, which
is a function of r
j
and
m
K matrix when K
ij
=1 if and only if user
i joins description j
11
4
Algorithms for Optimal
Assignment of Description
Bandwidths
In Section 4.1, we present the threshold value for description number. We show
that when the description number is no less than the threshold, there is a simple
and ecient assignment algorithm to match all the user bandwidth requirements.
In Section 4.2, we present an ecient heuristic SAMBA to to assign description
bandwidth for the more general case.
4.1 A Threshold and the Exact Solution
Consider that user bandwidth requirement ranges in [a, b], where a and b are
the maximum and minimum bandwidth requirement, i.e., a = min
j
c
j
and b =
max
j
c
j
.
Lets rst consider the simple case where a is equal to one (i.e. equal to
the basic unit). All the values in [a, b] can be converted to a binary number by
12
changing base to 2. The number of binary digits for a particular value is bounded
by the number of digits of b in binary form, which is clearly log
2
b + 1.
A binary number can be regarded as a linear combination of 2s powers
with coecients either 0 or 1. For example, the binary form of 25 is 11001. If
the description bandwidth is assigned to be a power of 2 (i.e., 1, 2, 2
2
, . . . , 2
m1
),
then the binary form of the bandwidth requirement represents exactly the joining
choice, with coecient 1 to join the corresponding description and 0 otherwise.
As in the example above, the user with bandwidth requirement of 25 units will
choose to join descriptions with bandwidth 16, 8 and 1 units. The maximum
number of binary digits indicates the description number, which is log
2
b + 1.
From above, it is clear that if m log
2
b +1, all the bandwidth require-
ments can be fully matched, because their values can be expressed as 0-1 linear
combination of the description bandwidths.
Now consider a to be any integer larger than one. In this case, bandwidth
requirement can be expressed as (a1)+x, where x [1, ba+1]. By the previous
argument, x can be written in binary form with at most log
2
(b a + 1) + 1
digits. Then any bandwidth requirement can be expressed as a linear combination
of a description bandwidth (a 1) and the binary expression for x. According to
the denition of heterogeneity factor in Equation (3.3), we have h = b a + 1.
Therefore, the threshold value for the description number in terms of h is
log
2
h + 2. (4.1)
If m is no less than this value, the description bandwidths are hence {(a
1), 2
0
, 2
1
, ..., 2
log
2
h
}. With this assignment, all the bandwidth requirements can
be fully matched.
It simply takes O(m) computations to decide the bandwidths for the de-
scriptions, given m is no less than the threshold.
13
4.2 SAMBA
In this section, we present an ecient heuristic SAMBA (Simulated Annealing
for MDC Bandwidth Assignment) in order to solve the general problem when
description number m is no larger than the threshold given by Equation (4.1).
If m is less than the threshold, the problem is to search in an m dimensional
integer space for the optimal description bandwidths. The search space is discrete
and nite, because each description can only take integral bandwidth no larger
than the maximum bandwidth requirement in the network. This condition makes
it feasible to adopt simulated annealing algorithm to solve the problem, which is
the core part of SAMBA [21].
In SAMBA, a state is dened as a vector

d of description bandwidths
(sorted in the increasing order). Each state is associated with an internal en-
ergy, which is dened to be the negative of the satisfaction value (as in simulated
annealing we seek to minimize an objective function). SAMBA starts with an
initial state and iteratively transits to other state seeking for lower internal energy
(and hence higher user satisfaction).
Each state has a neighborhood given by a radius r. By saying state

d
1
is a
neighbor of state

d
2
, we mean
_
_
_

d
1


d
2
_
_
_ < r (we use l
1
-norm in the simulation).
At each iteration, SAMBA randomly picks a neighbor of the current state as the
target state, and decides whether or not to make the transition according to a
transition probability p.
We further dene a temperature T, which gradually decreases as the al-
gorithm iterates. The higher T is, the larger is the neighborhood radius r.
We then dene transition probability as follows. Denote the current state
by

d and target state by

d
t
. The energy dierence between the two states is given
by the dierence of their satisfaction value, i.e., S(

d) S(

d
t
). If S(

d) S(

d
t
) < 0,
14
the transition probability p is dened as 1. Otherwise, p is a decreasing function
of (S(

d) S(

d
t
))/T with initial value close to 1. Therefore, given T, the lower
the satisfaction of the target state is, the smaller is the transition probability.
Further, with large T, any target state has transition probability near 1.
At the early iterations when the temperature is high, SAMBA picks the
target state from a large neighborhood. Because the transition probability to
any picked state is high, the algorithm randomly moves among the states. As
the algorithm iterates, the temperature gets lower. SAMBA picks the target
state from a smaller neighborhood and the transition probability to a state of
lower satisfaction decreases. In other words, the algorithm gradually settles to a
neighborhood with locally-optimal satisfaction. By running SAMBA with dier-
ent initial states, we have great chance to nd the global optimum. The whole
algorithm can hence be summarized in the following steps:
Step 0: For the rst iteration, set the initial temperature value and the
initial state

d
0
. Find out initial satisfaction S
0
. Then set the highest satis-
faction S
max
= S
0
and its associated state

d
max
=

d
0
.
Step 1: Decrease the temperature value.
Step 2: Find a target state

d
t
in the neighborhood and evaluate its satis-
faction S. If S > S
max
, assign

d
t
and S to

d
max
and S
max
, respectively.
Step 3: Make the transition decision according to the transition probability.
Step 4: Repeat Steps 2 to 3 for a number C times.
Step 5: Set current state to

d
max
and repeat Steps 1 to 4 for a number K
iterations. Return S
max
and

d
max
.
The computational complexity of our algorithm is as follows. According
to Step 4 and Step 5, Steps 1 to 3 are repeated for KC times. The rst and the
third steps take constant computations while Step 2 has to calculate the overall
15
satisfaction for the target state. According to Equation (3.6), S is a weighted
sum of individual satisfactions S
ind
. Given

d and c
j
, evaluating each S
ind
becomes
an integer Knapsack problem and takes at most O(2
m
) time. Therefore, given n
users, Step 2 takes O(n2
m
) time. Thus the whole algorithm runs in O(KCn2
m
)
time.
In contrast, the exhaustive search has to evaluate S for all the states in
order to decide the optimal overall satisfaction. Each state (

d in sorted order) is
a combination of m integers in [1, max
j
c
j
]. The number of such combinations is
lower bounded by (max
j
c
j
)
m
/m!. Given Equation (3.3), we can further bound
the number of states by
(max
j
c
j
)
m
m!

h
m
m!
=
m

i=1
h
i
. (4.2)
SAMBA evaluates S for KC times, which is in general much smaller than

m
i=1
(h/i)
(e.g., K 100, C 10, h 100 and m = 4). This is why SAMBA is much more
ecient than exhaustive search.
So far, we are given the description number m. There is in fact an optimal
m to achieve maximum user satisfaction among all ms. This is expected as
m
is
a decreasing function in m (due to decreasing coding eciency) while r
j
is an in-
creasing function in m (due to better bandwidth requirement matching). Because
all the bandwidth requirements are fully matched if m is larger than the threshold
as given in Equation (3.5), the optimal m to achieve maximum user satisfaction
is bounded by the threshold. To search for the optimal description number, we
can run SAMBA for increasing m up to the threshold in the simulation.
16
5
Illustrative Simulation Results
In this section, we present illustrative simulation results to show the eciency of
our algorithm. In Section 5.1, we describe simulation environment. In Section 5.2,
we compare SAMBA with other bandwidth assignment schemes and examine the
inuence of some important factors.
5.1 Simulation Environment and Parameters
In our simulation, we have compared SAMBA with exhaustive search, which
always achieves the optimum. Besides, we have also compared SAMBA with
other simple bandwidth assignment schemes, which include uniform assignment
(in which all the descriptions have the same bandwidth), linear assignment (in
which the description bandwidths is linearly increased), and random assignment
(which randomly assigns bandwidth for each description).
We consider a simple user individual satisfaction function given by f (
m
r
j
) =
(
m
r
j
)
k
, where k R
+
. The function is reasonable as it is strictly increasing in
[0, 1] and the minimum and maximum are 0 and 1, respectively. For concreteness,
we consider coding eciency as
m
=
m1
, where < 1 (the value of depends
17
5 10 15 20 25 30 35 40 45 50
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.1
c
P
r
o
b
a
b
i
l
i
t
y


Figure 5.1: Example bandwidth requirement distribution c N
T
(10, 5).
on the underlying MDC techniques used).
We consider that the number of users of bandwidth requirement c is pro-
portional to some distribution given by N(c). We use a simple truncated normal
curve as the bandwidth requirement distribution, i.e., c N
T
(,
2
). Figure 5.1
show a truncated normal c N
T
(10, 5).
Each user has its importance, with weight w(c) as a function of band-
width requirement. According to Equation (3.6), simulation on w(c) with uniform
bandwidth requirement distribution is equivalent to simulation on N(c) with con-
stant weight. Therefore, we only focus on the inuence of N(c) and expect the
similar result for w(c).
Unless otherwise stated, we use baseline parameters k = 2, = 1, m = 3
and c
j
uniformly distributes in [1, 100]. The parameters in SAMBA are set as
follows. We have K = 100 and C = 10. The temperature T exponentially decays
18
10 20 30 40 50 60 70 80 90 100
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
h
S


SAMBA or Exhaustive Search
Uniform Rate
Random Rate
Linear Rate
Figure 5.2: Overall satisfaction (S) versus heterogeneity factor h given dierent
schemes.
with the number of iteration, i.e.,
T = e
i/K
e
1
, (5.1)
where i is the current number of iterations. The transition probability from state

d to a target state

d
t
is given by
p(

d,

d
t
) =
_
_
_
1, if S(

d
t
) > S(

d);
e
S(

d
t
)S(

d)
T
, otherwise.
(5.2)
5.2 Illustrative Results
Figure 5.2 plots the overall satisfaction S versus heterogeneity factor h given
dierent bandwidth assignment schemes. The satisfaction S is decreasing with h.
This is because it becomes more dicult to match the bandwidth requirements
if heterogeneity factor gets higher. In the graph, for each h, overall satisfaction
19
5 10 15 20 25 30 35 40 45 50
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1

S


SAMBA or Exhaustive Search
Uniform Rate
Linear Rate
Random Rate
Figure 5.3: Overall satisfaction (S) versus mean value () given dierent schemes.
given by SAMBA overlaps with that given by exhaustive search, and is much
better than those given by the other schemes. SAMBA performs virtually the
same as exhaustive search.
Figure 5.3 plots the overall satisfaction S versus the mean value given
dierent bandwidth assignment schemes. If a scheme is robust to the variation
of bandwidth requirement distribution, its overall satisfaction should not change
much with dierent . From the graph, S given by SAMBA overlaps with that
given by exhaustive search and is not aected by the changes of . However,
S given by the other schemes is lower when is small. The comparison shows
SAMBA performs as well as exhaustive search and is robust when the bandwidth
requirement distribution changes.
Figure 5.4 plots the overall satisfaction S versus number of descriptions
m given dierent bandwidth assignment schemes. The overall satisfaction S
increases with m. This is because more descriptions can provide more options
of bitrates to meet dierent user bandwidth requirements. For each m, SAMBA
20
1 2 3 4 5 6 7 8 9 10
0
0.2
0.4
0.6
0.8
1
m
S


SAMBA or Exhaustive Search
Uniform Rate
Random Rate
Linear Rate
Figure 5.4: Overall satisfaction (S) versus description number (m) given dierent
schemes.
performs as well as exhaustive search
1
and much better than the other schemes.
The satisfaction of SAMBA nally settles to a value, because all the bandwidth
requirements are fully matched after m reaches the threshold.
We next examine the inuence of coding eciency. Figure 5.5 plots the
overall satisfaction S versus number of descriptions m given dierent . Given
decreasing coding eciency ( less than 1), the overall satisfaction rst increases
with m and then decreases with m. The reason is as follows. When m is small,
satisfaction is low because the bandwidth requirements are badly matched (i.e.,
r
j
is small). When m is large, satisfaction is also low because the coding eciency
is low (i.e.,
m
is small). Therefore, we expect the optimal m when the eect
of decreasing coding eciency and the eect of better bandwidth requirement
matching balances with each other. From the gure, we observe that the optimal
m becomes smaller when coding eciency decreases faster (i.e., is smaller). In
1
Due to high computational complexity, it becomes infeasible to nd overall satisfaction
using exhaustive search when m is large. Therefore, we only plot S given by exhaustive search
for m 3, which overlaps with S given by SAMBA.
21
1 2 3 4 5 6 7 8 9 10
0
0.2
0.4
0.6
0.8
1
m
S


beta= 1
beta= 0.95
beta= 0.9
beta= 0.85
beta= 0.8
Figure 5.5: Overall satisfaction (S) versus description number (m) given .
the MDC implementation, m should be chosen according to .
We then examine the inuence of k (the coecient to model satisfaction
function f). Figure 5.6 plots the overall satisfaction S versus description number
m given dierent k. S rst increases with m then decreases with m. This is due
to decreasing coding eciency (with = 0.85). And the optimal m is depending
on the choice of k. The reason is as follows. Function f has dierent convexity
with dierent k. When f is convex (k = 2), the satisfaction increases more
rapidly when the bandwidth matching factor r
j
approaches 1. In this case, users
emphasize more on high quality service. In the other case, when f is concave
(k = 0.5), the satisfaction increases more rapidly when r
j
is small, which implies
users emphasize more on the availability of the content. As a result, optimal m
may change given dierent k. For each m, satisfaction is lower if k = 2, because
x
2
x
0.5
for any x [0, 1].
We nally examine the inuence of bandwidth requirement distribution.
Figure 5.7, 5.8 and 5.9 plot the individual satisfaction S
ind
values for each band-
22
1 2 3 4 5 6 7 8 9 10
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
m
S


k= 0.5
k= 2
Figure 5.6: Overall satisfaction (S) versus description number (m) given k.
10 20 30 40 50 60 70 80 90 100
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
c
S
i
n
d
Figure 5.7: Individual satisfaction (S) versus receiving bandwidth with c
N
T
(0, 10).
23
10 20 30 40 50 60 70 80 90 100
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
c
S
i
n
d
Figure 5.8: Individual satisfaction (S) versus receiving bandwidth with c
N
T
(50, 10).
0 10 20 30 40 50 60 70 80 90 100
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
c
S
i
n
d
Figure 5.9: Individual satisfaction (S) versus receiving bandwidth with c
N
T
(100, 10).
24
width requirement c given dierent distributions c N
T
(0, 10), c N
T
(50, 10)
and c N
T
(100, 10) respectively. From the gures, users with bandwidth require-
ments around have higher individual satisfaction. The reason is as follows. The
number of users N(c) is larger, if c is closer to . According to the Equation (3.6),
if N(c) is larger, S
ind
(

d, c) has greater inuence on S. Therefore, SAMBA satises

users of bandwidth requirement c with higher precedence to maximize S. Further,
we expect the inuence of w(c) is similar (the users of bandwidth requirement c
get higher individual satisfaction if their weight w(c) is larger).
25
6
Conclusion
In this paper, we study how to optimally assign description bandwidth for MDC
for video streaming to large group, so that their heterogeneous bandwidth re-
quirements can be best satised. We formulate the problem as an optimization
problem and propose algorithms to address it.
We have proved that the formulated optimization problem is NP-hard, by
nding a polynomial reduction to the problem from the subset sum problem. We
show that when the description number is no smaller than a certain threshold,
simple and ecient assignment algorithm of run-time complexity of O(m) can
fully match all the bandwidth requirements. For the general case when m is less
than the threshold, we have proposed and studied the heuristic SAMBA, which
uses simulated annealing to eciently nd the optimal description bandwidth
assignment. Furthermore, there exists an optimal choice for description number
to achieve maximum user satisfaction.
Simulation results have shown that SAMBA performs much better user
satisfaction than other assignment methods and closely matches the optimum
based on exhaustive search. With the consideration of coding eciency, we show
that indeed there is an optimal description number to achieve maximum user
satisfaction.
26
Bibliography
[1] Y. Tang, J.-G. Luo, Q. Zhang, M. Zhang, and S.-Q. Yang, Deploying P2P
networks for large-scale live video-streaming service, IEEE Commun. Mag.,
vol. 45, no. 6, pp. 100106, Jun. 2007.
[2] Y.-F. Chen, Y. Huang, R. Jana, H. Jiang, M. Rabinovich, B. Wei, and
Z. Xiao, When is p2p technology benecial for iptv services? in Proc.
ACM NOSSDAV 2007, Jun. 2007.
[3] V. Padmanabhan, H. Wang, P. Chou, and K. Sripanidkulchai, Distribut-
ing streaming media content using cooperative networking, in Proc. ACM
NOSSDAV 2002, May 2002.
[4] M. Castro, P. Druschel, A.-M. Kermarrec, A. Nandi, A. Rowstron, and
A. Singh, SplitStream: High-bandwidth multicast in cooperative environ-
ments, in Proc. ACM SOSP 2003, Oct. 2003.
[5] B. Li and J. Liu, Multirate video multicast over the internet: An overview,
IEEE Network, vol. 17, no. 1, pp. 2429, Jan. 2003.
[6] M.-T. Lu, J.-C. Wu, K.-J. Peng, P. Huang, J. Yao, and H. Chen, Design and
evaluation of a p2p iptv system for heterogeneous networks, IEEE Trans
Multimedia, vol. 9, no. 8, pp. 15681579, Dec. 2007.
[7] E. Akyol, A. Tekalp, and M. Civanlar, A exible multiple description cod-
ing framework for adaptive peer-to-peer video streaming, IEEE Journal of
Selected Topics in Signal Processing, vol. 1, no. 2, pp. 231245, Aug. 2007.
27
[8] T. Tillo and G. Olmo, Data-dependent pre- and postprocessing multiple
description coding of images, IEEE Trans. Image Processing, vol. 1, no. 5,
pp. 12691280, May 2007.
[9] M. Ma, O. Au, L. Guo, S.-H. G. Chan, and P. Wong, Error concealment for
frame losses in mdc, IEEE Trans. Multimedia, vol. 10, no. 8, pp. 16381647,
Dec. 2008.
[10] M. Firooz, K. Ronasi, M. Pakravan, and A. Avanaki, Wavelet-based unbal-
anced un-equivalent multiple description coding for p2p networks, in Proc.
IEEE ICT-MICC 2007, May 2007.
[11] G. Wang, S. Futemma, and E. Itakura, Fec-based scalable multiple descrip-
tion coding for overlay network streaming, in Proc. IEEE CCNC 2005, Jan.
2005.
[12] M. Wien, H. Schwarz, and T. Oelbaum, Performance analysis of svc, IEEE
Trans. Circuits and Systems for Video Technology, vol. 17, no. 9, pp. 1194
1203, Sep. 2007.
[13] Y. Zhou and W.-Y. Chan, Performance comparison of layered coding and
multiple description coding in packet networks, in Proc. IEEE Globecom
2005, Dec. 2005.
[14] Y.-C. Lee, Y. A. J. Kim, and R. Mercereau, Performance comparisons of
layered and multiple description coded video streaming over error-prone net-
works, in Proc. IEEE ICC 2003, May 2003.
[15] J. Liu, B. Li, and Y.-Q. Zhang, A hybrid adaptation protocol for tcp-
friendly layered multicast and its optimal rate allocation, in Proc. IEEE
INFOCOM 2002, Jun. 2003.
[16] V. Goyal, Multiple description coding: compression meets the network,
IEEE Signal Processing Magazine, vol. 18, no. 5, pp. 7493, Sep. 2001.
[17] H. Witsenhausen and A. Wyner, Source coding for multiple descriptions ii:
A binary source, Bell Syst. Tech. J., vol. 60, no. 10, pp. 22812292, Dec.
1981.
28
[18] R. Venkataramani, G. Kramer, and V. Goyal, Multiple description coding
with many channels, IEEE Trans. Inf. Theory, vol. 49, no. 9, pp. 21062114,
Sep. 2003.
[19] B. Li, J. Liu, J. Xu, B. Li, and X. Caol, Bandwidth provisioning for multiple
description coding based video distribution, Wireless Personal Multimedia
Communications 2002, vol. 2, pp. 802806, Oct. 2002.
[20] P. Xia, X. Jin, and S.-H. Chan, Optimal bandwidth assignment for multiple
description coding in media streaming, in Proc. IEEE CCNC 2009, Jan.
2009.
[21] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated
annealing, Science, vol. 220, no. 4598, pp. 671680, May 1983.
[22] S.Geman and D. Geman, Stochastic relaxation, gibbs distributions and the
bayesian restoration of images, IEEE Transactions on Pattern Analysis and
Machine Intelligence, vol. 6, no. 6, pp. 721741, Nov. 1984.
[23] D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, Optimization
by simulated annealing: An experimental evaluation; part i, graph partition-
ing, Operation Research, vol. 37, no. 6, pp. 865892, Nov. 1989.
[24] , Optimization by simulated annealing: An experimental evaluation;
part ii, graph coloring and number partitioning, Operation Research, vol. 39,
no. 3, pp. 378406, May 1991.
29
Appendix: NP-hard Proof
In this section, we prove our problem is NP-hard. We nd a polynomial reduction
from the subset sum problem L
c
to our problem L. In order to have L
c

P
L,
we prove any input of L
c
can be transformed into input of L in polynomial time.
Also the output of L is equivalent to that of L
c
and can be transformed back in
polynomial time as well.
The input of L
c
is (x
1
, x
2
, . . . , x
m
, t), with all x
i
and t positive integers. The
output is a yes or no to decide whether t is sum of a subset of {x
i
}. We assume
x
i
= 0, because after excluding zeros the problem is still equivalent to the original
one. We construct the input for L in the form of (x
1
, x
2
, . . . , x
m
,

i
x
i
, t, m),
where the rst m+2 elements are user bandwidth requirements and the last one
is the description number. We further set (m) = 1 and let all users have the
same weight. Till this point, we have transformed the input of L
c
to that of L,
which obviously takes polynomial time.
The output of L is (d
1
, d
2
, . . . , d
m
, S), where d
i
is description bandwidth
and S is the optimal overall satisfaction. According to Equation (3.6), maximum
of S is 1 when all the bandwidth requirements are fully matched i.e., S 1. If t
is a subset sum in L
c
, t can be expressed as a linear combination of x
i
with zero
or one coecients. Then if we let descriptions have bandwidths (x
1
, x
2
, . . . , x
m
),
all the bandwidth requirements in L are fully matched. We thus have S = 1. In
other word, (x
1
, x
2
, . . . , x
m
, 1) must be one of the solutions of L. If we show it is
also the only solution, we can prove the equivalence between the outputs of L
c
30
and L, i.e., t is subset sum in L
c
L has output (x
1
, x
2
, . . . , x
m
, 1).
Now let d = (d
1
, d
2
, . . . , d
m
)
T
be the optimal descriptions bandwidth as-
signment for L. There exists a (m + 2) by m matrix A with each element a
ij
be
zero or one, such that
Ad =
_
_
_
_
_
_
_
_
_
_
_
_
_
_
x
1
x
2
.
.
.
x
m

x
i
t
_
_
_
_
_
_
_
_
_
_
_
_
_
_
. (6.1)
By adding the rst m rows together, we have the following equation:
_
m

i=1
a
i1
,
m

i=1
a
i2
, . . . ,
m

i=1
a
im
_

_
_
_
_
_
_
_
_
d
1
d
2
.
.
.
d
m
_
_
_
_
_
_
_
_
=
m

i=1
x
i
. (6.2)
We claim that none of the

a
ij
equals zero. Because if it is true, we must
have a column of zero in A and a d
j
without any user joining it. In this case, we
can simply remove the column and the description. Then we have,
m

i=1
a
ij
1, (6.3)
for all j. And using the (m + 1)
th
row of matrix A, we have
m

i=1
x
i
(6.4)
31
=
_
a
(m+1)1
, a
(m+1)2
, . . . , a
(m+1)m
_

_
_
_
_
_
_
_
_
d
1
d
2
.
.
.
d
m
_
_
_
_
_
_
_
_
(6.5)
(1, 1, . . . , 1)
_
_
_
_
_
_
_
_
d
1
d
2
.
.
.
d
m
_
_
_
_
_
_
_
_
(6.6)

_
m

i=1
a
i1
,
m

i=1
a
i2
, . . . ,
m

i=1
a
im
_

_
_
_
_
_
_
_
_
d
1
d
2
.
.
.
d
m
_
_
_
_
_
_
_
_
(6.7)
=
m

i=1
x
i
, (6.8)
which implies, after some manipulations,
a
(m+1)j
= 1, (6.9)
and
m

i=1
a
ij
= 1, j. (6.10)
Since

m
i=1
a
ij
is the sum of rst m rows for column j, if it equals one,
theres exactly one entry a
ij
in this column with value one. Because there are
m such columns (or less than m if zero columns are removed), there are at most
m entries of value one in the top m rows of matrix A. Now if there is one row
containing two entries with value one, there must be at least one row with all zero
entries. It is equivalent to say that one of x
i
is zero, which is contradicting to our
assumption. Therefore, each row must contain exactly one entry with value one
(If the number of columns is less than m, there must be one row with all zero
entries leading to the same contradiction). By looking at the top m by m matrix,
32
we can conclude that
(d
1
, d
2
, . . . , d
m
) = (x
i
1
, x
i
2
, . . . , x
i
m
) , (6.11)
where the right hand side is a permutation of x
i
. In other word, the set x
i
is the
only solution which fully matches all the bandwidth requirements. Therefore, we
have proved the equivalence between output of L and L
c
. The transformation
between the outputs is obviously in polynomial time.
Therefore we conclude that there exists polynomial reduction from L
c
to
L and our problem L is NP-hard.
33