Open-loop video distribution with support of VCR Functionality.
Scalable video distribution schemes have been studied for quite some time. For very popular videos, open-loop broadcast schemes have been devised that partition each video into segments and periodically broadcast each segment on a different channel. Open-loop schemes provide excellent scalability as the number of channels required is independent of the number of clients. However, open-loop schemes typically do not support VCR functions. We will show for open-loop video distribution how, by adjusting the rate at which the segments are transmitted, one can provide VCR functionality. We consider deterministic and probabilistic support of VCR functions: depending on the segment rates chosen, the VCR functions are supported either 100% of the time or with very high probability. For the case of probabilistic support of PLAY and Fast-forward (FF) only, we model the reception process as a semi-Markov accumulation process. We are able to calculate a lower bound on the probability of successfully executing FF actions.
Introduction
1.1 Classication
VoD systems can be classied in open{loop systems [12] and closed{loop systems
[10,16]. In general, open loop VoD systems partition each video into
smaller pieces called segments and transmit each segment on a separate channel
at its assigned transmission rate. Those channels may be logical, implemented
with an adequate multiplexing. All segments are transmitted periodically
and indenitely. The rst segment is transmitted more frequently than
later segments because it is needed rst in the playback. In open{loop systems
there is no feedback from the client to the server, and transmission is completely
one{way. In closed-loop systems, on the other hand, there is a feedback
between the client and the server. Closed{loop systems generally open a new
unicast/multicast stream each time a client or a group of clients issues a re-
quest. To make better use of the server and network resources, client requests
are batched and served together with the same multicast stream.
Open-loop systems use segmentation in order to reduce the network bandwidth
requirements, which makes them highly scalable because they can provide
Near Video on Demand (NVoD) services at a xed cost independent of the
number of users. In this paper, we will show how open-loop NVoD schemes
can support VCR functions, which are dened as follows:
PLAY Play the video at the basic video consumption rate, b;
PAUSE Pause the playback of the video for some period of time;
SF/SB Slow forward/Slow backward: Playback the video at a rate equal to
some period of time. We have Y S <
FF/FB Fast forward/Fast backward: Playback the video at a rate equal to
some period of time. We have X F > 1.
1.2 Related Work
Most VoD systems do not support VCR functions. It is assumed that users
are passive and keep playing the video from the beginning until the end without
issuing any VCR function. However support of VCR functions makes a
VoD service much more attractive. Most research on interactive VoD focuses
on closed-loop schemes [1,6,15,13]. To support VCR functions such as Fast-Forward
all these schemes serve the client who issues a FF command via
a dedicated unicast transmission, referred to as contingency channel. When the
client returns into PLAY state, (s)he joins again the multicast distribution.
It is obvious that such a solution is not very scalable since it requires separate
contingency channels and also explicit interaction with the central server.
Thus, open-loop schemes are particularly well suited when: a) the number of
users grows large, or b) the communication medium has no feedback channel,
which is the case in satellite or cable broadcast systems.
Very little work has been done to support VCR functions in open-loop VoD
schemes [2,4,8,14]. Except for the paper by Fei et al. [8], all the other schemes
only consider PAUSE or discrete jumps in the video. Fei et al. propose a
scheme called \staggered broadcast" and show how it can be used together
with what they call \active buer" management to provide limited interac-
tivity. In staggered broadcast, the whole video of duration L is periodically
transmitted on N channels at the video consumption rate b. Transmission of
the video on channel i starts t later than channel i 1. Depending
on the buer content and the duration of the VCR action, the VCR
action may be possible or not. In the case that the VCR action is not possible,
it is approximated by a so-called discontinuous interactive function where the
viewing jumps to the closest (with respect to the intended destination of the
interaction) point of the video that allows the continuous playout after the
VCR action has been executed.
The big dierence between the related work and our scheme is that up to now,
the support of VCR functions either required a major extension of the transmission
scheme (e.g. contingency channels) or was very restricted (e.g. staggered
broadcast). We will demonstrate the feasibility of deterministic support
of VCR functions in open-loop VoD systems by increasing the transmission
rate of the dierent segments. While this idea looks very straightforward, it
has been, to the best of our knowledge, never proposed before.
The rest of the paper is organized as follows. We rst describe the so-called tailored
transmission scheme, then discuss how to adapt this scheme to support
VCR functions. For the case of PLAY and FF user interactions we develop an
analytical model that allows the computation of a lower bound on the probability
that a user interaction can be successfully executed and then provide
some quantitative results. The paper ends with a brief conclusion.
2.1

Introduction

Many dierent open-loop NVoD schemes have been proposed in the literature;
for a survey see [12]. These schemes typically dier in the way a video is
partitioned into segments and can be classied mainly in three categories:
Schemes that partition the video in dierent length segments and transmit
each segment at the basic video consumption rate [9,19];
Schemes that partition the video in equal-length segments and decrease the
transmission rate of each segment with increasing segment number [3];
Hybrid schemes that combine the two above methods [14,20].
In the following, we will present in more detail the scheme called tailored transmission
scheme that was proposed by Birk and Mondri [3] and is a generalization
of many of the other open-loop NVoD schemes previously described.
2.2 Tailored Transmission Scheme
The base version of the tailored transmission scheme works as follows. A video
is partitioned into N equal-length segments. Each segment is transmitted periodically
and repeatedly on its own channel. A client who wants to receive
a video starts by listening to one, more, or all channels and records these
segments.
We shall need the following notation:
s i denote the time the client starts recording segment
denote the time the client has entirely received segment
denote the time the client starts viewing segment
r i denote the transmission rate of segment i [bits/sec];
D denote the segment size [bits];
b denote the video consumption rate [bits/sec].
To assure the continuous playout of the video we require that each segment
is fully received before its playout starts, i.e. v i  w i . Given a segment size
the transmission rate r i of segment i must
satisfy the following condition to assure a continuous playout of the video:
(v
If the client starts recording all segments at the same time, i.e. s
and Mondri have shown (Lemma 1 in [3]) that the transmission rate will be
minimal and is given as
r min
(w
Without loss of generality, we may assume that t
is the duration of a segment. Then, r min
and the
total server transmission bandwidth is
R min

Figure

1 illustrates the tailored transmission scheme for the case of minimal
transmission rates. The client starts receiving all segments at time t 0 . The
shaded areas for each segment contain exactly the content of that segment as
received by the client who started recording at time t 0 . A client is not expected
to arrive at the starting point of a segment; instead a client begins recording
at whatever point (s)he arrives at, and stores the data for later consumption.
Therefore, the startup latency of is the scheme corresponds to the segment
duration D=b.00000011111100011100000000111111110011001111000001111111111000011111111000001111111111
Segments
Time
Client joins
Fig. 1. An example of the tailored transmission scheme with minimal transmission
rates.
3 How to Support VCR Functions
Given the base scheme of the tailored transmission with its minimal transmission
rates, we will show how to adapt (increase) the segment transmission rates
to support VCR functions. To convey the main idea, we will limit ourselves
rst to the case where the only VCR function possible is FF. In fact, the FF is
the only VCR action that \accelerates" the consumption of the video, which
possibly can lead to a situation where the consumption of the video gets ahead
of the reception of the video. We present a solution that makes sure that any
FF command issued can be successfully executed. The other user interactions
such as SF, SB, FB or PAUSE can be accommodated by buering at the client
side. From now on, we therefore consider only two states: PLAY and FF.
We make the following two central assumptions:
The client has enough disk storage to buer the contents of a large portion
of the video;
The client has enough network access and disk I/O bandwidth to start
receiving the N segments at the same time.
The trend for terminal equipments appears to be that more and more storage
capacity is available. Actually, there already exist products that meet the
above assumptions. An example is the digital video recorder by TiVo [18] that
can store up to 60 hours of MPEG II video and, connected to a satellite feed,
can receive transmissions at high data-rates.
However, for the case where the assumption on storage does not hold, we also
know how to support VCR functions: the idea will remain the same, only the
individual segment transmission rates required will be higher. The scheme we
propose may be adapted to this situation. Note that the trade-o between the
storage capability of the client and segment transmission rates for the case of
NVoD has already been explored by Birk and Mondri [3].
3.1 Deterministic Support
Whenever a client issues a FF command, the video is viewed at a playout rate
than the normal rate, i.e. the consumption of the video occurs at
a rate equal to X F  b and each segment will be consumed after D
bXF units
of time instead of D=b units of time in case of PLAY. As a consequence, the
viewing times of all segments not yet viewed will be \advanced" in time. To
obtain a deterministic guarantee that every FF command issued during the
viewing of a video can be executed, we consider the worst case scenario where
the client views the whole video in FF.
i denote the time the client starts viewing segment i, given that (s)he
has viewed segments mode. We can compute the v FF
i as
If the client starts recording all segments at the same time, i.e. s
compute, similar to (2), the transmission rate r FF
i that allows unrestricted FF
interactions as
r FF
(v FF
XF  D
1 The playout and therefore VCR actions do not start before segment 1 has been
entirely received; we therefore have v FF
If we assume that t D=b, the expression simplies to
r FF
3.2 Probabilistic Support for FF
In the previous subsection, we have computed the minimal transmission rates
r FF
i such that all the FF interactions issued can be realized. We have considered
the worst case scenario where the client views the whole video in FF
mode. While a client might do so, we think that it is much more likely that
the viewing of a video will alternate between PLAY and FF modes (and possibly
other VCR actions). We will in the following use a model for the viewing
behavior where a user strictly alternates between PLAY and FF. We refer to
this behavior as S-FF (for Simple FF).
Our goal is to support FF interactions with high probability while transmitting
each segment at a rate lower than r FF
. To this purpose we dene the rates r I
as follows:
The server transmits the segments i Ng at a rate r I
where A is the rate increase factor, with 1  A  X F , and r min
i is
computed in (2);
The server transmits segment 1 at rate r I
still because the playout
does not start before segment 1 has been entirely received.
Analytical Model for the S-FF Model
In this section we will compute a closed-form lower-bound on the probability
that a segment is successfully consumed by the client. Segment i is successfully
consumed by the client if segment available to him/her before the
consumption of segment i has been completed; otherwise we will say that
the consumption of segment i has failed. A failure is resolved once the next
segment is entirely available to the client. It is worth pointing out that failures
may occur both in mode PLAY and in mode FF, as shown on Figure 2.
We will assume that the client alternates between both modes of consump-
tion. More precisely, we introduce two independent renewal sequences of rvs
fS P (n)g n and the fS FF (n)g n , where S P (n) and S FF (n) will represent the
duration of the n-th PLAY and FF periods, respectively.
F
F
Playout limit
in FF mode
in P mode
time
bits
Consumption curve
Fig. 2. Failures occurring in PLAY and FF modes.
For modeling purposes, and also because we believe this assumption corresponds
to a reasonable behavior of the client, we will assume that the remaining
duration of a PLAY or FF period when a failure occurs is resumed when
the next segment is available to the client. This corresponds, for instance, to
the situation where the client wants to reach a particular point in the video
or avoid a particular scene, regardless of the failures that (s)he may encounter
while viewing the video.
In order to ensure a probabilistic support for FF (cf. Section 3.2) recall that
segment i is transmitted at rate r I
Therefore,
the i-th segment will be entirely available to the client at time w
The continuous playout of segment i requires that at the viewing time v i , this
segment has been entirely received, that is v i  w i . Segment
will fail if this inequality does not hold. The continuous playout of the video
requires that all segments be on time, namely,
Recall that v since the client cannot start viewing the rst segment
before it has been entirely received.
The number L of segments on time is given by
where 1A stands for the indicator function of the event A, from which we
deduce the mean number of segments on time
Denote by R(t) the number of bits of the video which have been consumed by
the client in [v 1
Computing P(v i  w i ) in closed-form for all i is not an easy task. Indeed, it is
related to computing the distribution of the length of a busy period in a
uid
queue fed by a Markov-Modulated Rate Process. In the present paper, we will
content ourselves with the derivation of an elementary lower bound.
To derive this lower bound, we consider the semi-Markov accumulation process
which is constructed as follows: during a PLAY period Q(t)
continuously increases with the rate b and during a FF period it continuously
increases with the rate bX F . More precisely, for t > 0,
with T n :=
By convention T
By construction of Q(t) and R(t) it is obvious that (see Figure 3)
Observe that both processes fR(t); t  w 1 g and fQ(t); t  w 1 g would be
identical in the absence of failures. We see from (6) and the denition (5) that
which implies that
Hence, cf. (4),
For the transmission scheme we described in Section 3.2, the segment arrival
times are given by w but the analysis above actually holds
for any reception schedule of segments given by a sequence fw
Failure
SFF (2)
SP (2)
Fig. 3. Comparison of Q(t) and R(t).
In Section 5, we present results for determining P(Q(T ) < x), for any T
and x. These results are actually obtained for any semi-Markov accumulation
process with a nite state-space (see Section 5.2). When S P (n) and S FF (n)
are exponentially distributed random variables (rvs) with respective means
1= P and 1= FF , we can apply the formulas in Section 5.3. First, use (16)
with use the formulas for q ij (x) (the density
of the distribution of Q, conditionally on the start/end states) with
and . The probabilities P(Q(T are then obtained by numerical
integration.
5 Semi-Markov Accumulation Process
In this section, we develop a framework for evaluating the workload distribution
generated in a given time-interval by a semi-Markov accumulation process
with an arbitrary (but nite) state-space.
After dening the process (Section 5.1), we show that the Laplace transforms
of the sought distributions satisfy the linear system of equations (15). Finally,
we apply the formula to the case of a two-state continuous-time Markov process
(Section 5.3), where the Laplace transform can be inverted to obtain the
density of the distribution.
5.1 Denition
We rst construct formally the accumulation process from a semi-Markov
process. Kg be a nite state-space. Let
be a sequence of i.i.d. rvs, for each
fZ(n)g n be a homogeneous discrete-time Markov chain on the state-space
The semi-Markov process fX(t); t  0g is dened jointly with a sequence
of jump times as
with nonnegative rv.
The accumulation process Q(t) is such that while the process X(t) is in state i,
Q(t) accumulates at a constant rate r i . Formally, fQ(t); t  0g is constructed
as follows: set
This construction is illustrated in Figure 4. The upper part shows the evolution
of the discrete-time Markov chain Z(n), and of X(t). The lower part displays
Q(t) as a function of the jump times T n . The accumulation rates are such that
5.2 Distribution of Q(t)
Let Q i;r (T ) denote the quantity accumulated in [0; T ) given that
and T In other words, the process X starts in state i with a residual
time r in this state. Similarly, denote Q i;S i (T ) the same quantity, but
given that distributed according to the
total sojourn time distribution (i.e., as if a transition to state i had occurred
at time 0).
Depending on the problem to be solved, one may be interested in the distribution
of Q i;S i (T ) or that of Q
S i is the forward recurrence time of
. The latter corresponds to the case where the semi-Markov process fX(t)g
Fig. 4. Construction of the accumulation process
is stationary. The common procedure for computing these distributions is to
compute that of Q i;r (T ) for an arbitrary r, and then integrate with respect to
the proper distribution.
We are therefore interested in the distribution of Q i;r (T ), jointly with that
of X(T ), namely P(Q i;r (T )  We shall actually compute the
Laplace-Stieltjes Transform (LST)
The computation below may be seen as a generalization of the analysis developed
by Cox and Miller in [5, x9.3] for alternating renewal processes (i.e.
First, if r  T , then no jump occurs before time T , and since
In that case,
On the other hand, if r < T , then at least one jump occurs in the time-interval
conditioning on the state reached after the rst jump (i.e. Z(1))
then using the stationarity and independence of the underlying sequences, we
have
We now compute the Laplace transform of ^
T () with respect to T . With
the help of (10)-(11), we obtain
re
r
dT
dT
A relation involving only the rvs Q i;S i (T ) is obtained from (12) by integrating
both sides with respect to r, considered to be distributed as S i . Let S i (r)
denote the distribution function of S i and let S
be its LST.
Introduce also the notation
dT
Then, we have
dT
This is a system of linear equations from which the required Laplace transforms
can be computed. To see this better, dene the matrices
diag (S
diag
denotes the mm diagonal matrix with elements
Then, (14) rewrites as
K=L
The matrix I SP is invertible because the spectral radius of SP is less than
This follows by application of a standard
bound on the spectral radius ([11, Cor. 6.1.5]): (SP)
)j. This is less than one in the specied domain, from well
known properties of Laplace transforms.
Once the matrix K is computed, other initial conditions of the process fX(t);
may be investigated.
For instance, if the residual sojourn time in state i is r, then the distribution
is obtained using (12), that is
If the residual sojourn time in state i is given by e
the forward recurrence
time of S i (in other words, if fX(t); t  0g is stationary), then integrating
(12) gives, with obvious notation
f
dT
Remark: A simple extension of this derivation shows that the accumulation
process may be generalized by replacing the constant-rate process by any
stationary process with independent increments. The formulas above hold with
the term \r replaced by some  i () characteristic of the process (see [7,
Eq. (7.3') p. 419]). For instance, for the Poisson process with rate r,
process with drift r and variance  2 ,
5.3 Application to a Two-State Markov Accumulation Process
In this section, we address the case of a two-state, continuous-time Markov
process, with innitesimal generator
(T ) denote the quantity accumulated during the interval [0; T ) when
accumulation rates in states 1 and 2 are r 1 and r 2 , respectively. In distribution,
we have
Computing the distribution of Q r1 ;r 2 (T ) is therefore reduced to computing the
distribution of Q 1;0 (T ), which is the visit time in state 1 during the interval
apply formulas of Section 5.3.
We assume that the residual time in the initial state has the same distribution
as the total sojourn time. Observe that due to the memoryless property of the
exponential distribution, S i and e
have the same distribution. The relevant
matrices are:
Using (15), we obtain
The last step is to invert the Laplace transform K ij (; ) with respect to
and . From the denition (13), this will give the density of the distribution
of Q(T ).
The inversion can be performed using general rules and tables for Laplace
transforms (see e.g. [17]). Inverting with respect to  is straightforward, because
we have a rational function of degree 1 in . We obtain:
dq P(Q

For the inversion with respect to , we use in particular the following properties

a
I 1
aT
aT
a
I 1
aT
(i.e. inverse of the
Laplace transform g(s) at point t), I n () is the modied Bessel function of the
rst kind and order n (see e.g. [17, p. 7]) and - a (t) is the Dirac function at
point a.
for x  0. We nally nd, with
s
x
s
x
In order to obtain the distribution functions P(Q(T
the Laplace transforms K ij (; )= should be inverted. This leads to more
involved series which shall not be reproduced here.
6 Numerical Results
We have applied the bound in (7) to a video of length 2 hours = 7200 sec.
We have varied the segment size from 200 sec to 800 sec. The number N of
segments varies inversely from 36 to 9. The playout factor for FF is
This is a standard value for VCRs, also used in other papers. We consider two
dierent duration ratios  (that is: PLAY periods last 2 times,
resp. 5 times longer than FF periods). The parameters chosen are detailed in

Table

1. We have displayed in this table the average \natural" consumption
rate of the video, given by
FF

Table
Parameters of the numerical experiments.
1= P 1= FF A b N =b
In order to compare the performance of our scheme for videos of dierent
lengths, we have measured the probability of success:
The results should depend on how the natural rate b N compares to the rate
increase factor A. If b N =b < A, then the law of large numbers will force the
\natural" consumption curve Q(t) (and therefore R(t)) to lie below the playout
limit with large probability. Note that this eect may be long to appear if b N =b
is close to A. If b N =b > A, then the converse eect appears. In that case, it
also turns out that the actual curve R(t) records a large number of failures.
Another eect may kick in: the probability that a failure occurs within segment
may depend on i. First, the time between w 1 and w 2 (=D  (2=A 1)=b) is
smaller than the typical inter-arrival time between segments w
This may give a signicant advance of data, and with few (large) segments,
may result in a large success probability. On the other hand, when b N =b < A,
the rst segments tend to be vulnerable to
uctuations in the consumption
rate and have a smaller success probability. But if b N =b > A, the rst segments
are more likely to be played out without failures than later ones.
The results are reported in Figure 5. The curve for 1=
exhibits the poorest performance. This was expected, since b N =b > A
in this case. Note however that the accuracy of the bound is not good for small
Probability
of
success
Segment duration
Play 60, FF=30, A=1.9
Play 45, FF=9, A=1.4
Play 60, FF=30, A=1.8
Play 60, FF=30, A=1.7
Play 45, FF=9, A=1.3
Fig. 5. Lower bounds on the probability of success E [L]=N for segments of the whole
video.
values of the segment length (see Table 2), and that the probability of success
is actually larger than 80%.
The other curves exhibit a probability of success larger than 85% for 1=
(which is just slightly larger than b N =b), and larger
than 95% for the three other sets of parameters. The curves with
almost coincide. The experiments show that choosing a parameter
A only slightly larger than the expected consumption rate of the user, coupled
with su-ciently large segment sizes, achieves a very reasonable success
probability.
The accuracy of the bound (7) is not good in relative terms, as demonstrated
in

Table

2. In this table, the bound is compared with values obtained by
simulating a million replications of a playout of the entire video. The relative
accuracy improves when D increases; this is explained by the fact that the
law of large numbers has more eects when segments are longer.
The accuracy is however su-cient to assess the e-ciency of the rate increase
technique, and may be used to optimize the parameter A, in a compromise
between the probability of success and the bandwidth requirements. Such an
optimization is outside the scope of this paper.

Table
Comparison of the lower bound on the success probability (B) with simulations (S);
1= 9.
200 0.9602 0.9837 200 0.5226 0.8099
300 0.9794 0.9898 300 0.6132 0.8110
700 0.9989 0.9993 700 0.8716 0.9021
Conclusions
We have shown how by increasing the segment transmission rates for the tailored
transmission scheme one can provide either deterministic or probabilistic
support of user interactions. Since the FF action is the most \challenging" one
to support, we restricted our analysis to a viewing behavior where only PLAY
and FF are allowed. We rst derived deterministic guarantees for satisfying
all possible FF actions. Since the deterministic guarantees were based on the
pessimistic assumption that the user watches the whole video from start to
end in FF mode, we then dened a model for the viewing behavior (S-FF
model) that consists of the user alternating between the PLAY and the FF
modes.
For the S-FF model, we derived an analytic expression for a lower bound on
the success probability. The reception of the segments is modeled as a semi-Markov
accumulation process that allows the computation of the amount of
video data received. While supporting VCR functions (and in particular FF)
requires an increase in the segment transmission rates, our results indicate
that this increase remains \moderate". The analytical results obtained for the
S-FF are still pessimistic ones in the sense that a user who executes not only
PLAY and FF but also actions such as PAUSE of SF will reduce the rate
at which the video is consumed compared to the case of the S-FF model. In
future extensions of this research, we shall exploit the theoretical formalism
for accumulation processes that we have developed in this paper in order to
handle various user's behavior and other VCR functions.



--R

Providing unrestricted VCR functions in multicast video-on-demand servers
The role of multicast communication in the provision of scalable and interactive video-on-demand service
Tailored transmissions for e-cient near-video-on- demand service

The Theory of Stochastic Processes.
Channel allocation under batching and VCR control in video-on-demand systems
Stochastic Processes.
Providing interactive functions through active client bu

Supplying instantaneous video-on-demand services using controlled multicast
Matrix Analysis.

The split and merge protocol for interactive video on demand.

Multicast delivery for interactive video-on-demand service
Multicast with cache (Mcache): An adaptive zero-delay Video-on-Demand service
Schaum's Outline of Theory and Problems of Laplace Transforms.

Pyramid broadcasting for video on demand service.

--TR
Matrix analysis
Channel allocation under batching and VCR control in video-on-demand systems
The Split and Merge Protocol for Interactive Video-on-Demand
Providing Interactive Functions through Active Client-Buffer Management in Partitioned Video Multicast VoD Systems
An Efficient Implementation of Interactive Video-on-Demand
Supplying Instantaneous Video-on-Demand Services Using Controlled Multicast
Multicast Delivery for Interactive Video-On-Demand Service
Providing Unrestricted VCR Functions in Multicast Video-on-Demand Servers
interactivity;semi-Markov accumulation process;stochastic bounds;video on demand