The dyadic stream merging algorithm.
We study the stream merging problem for media-on-demand servers. Clients requesting media from the server arrive by a Poisson process, and delivery to the clients starts immediately. Clients are prepared to receive up to two streams at any time, one or both being fed into a buffer cache. We present an on-line algorithm, the dyadic stream merging algorithm, whose recursive structure allows us to derive a tight asymptotic bound on stream merging performance. In particular, let  be the Poisson request arrival rate, and let L be the fixed media length. Then the long-time ratio of the expected total stream length under the dyadic algorithm to that under an algorithm with no merging is asymptotically equal to 3/log(L)2L;. Furthermore, we establish the near-optimality of the dyadic algorithm by comparisons with experimental results obtained for an optimal algorithm constructed as a dynamic program. The dyadic algorithm and the best on-line algorithm of those recently proposed differ by less than a percent in their comparison with an off-line optimal algorithm. Finally, the worst-case performance of our algorithm is shown to be no worse than that of earlier algorithms. Thus, the dyadic algorithm appears to be the first near optimal algorithm that admits a rigorous average-case analysis.
INTRODUCTION
At a sequence of random times, clients request content streaming from a
given media server, e.g., videos from a video-on-demand server, with delivery
for each client to begin immediately. To reduce the potentially heavy
tra-c burden created by these media streams, it is clearly desirable to
combine streams of the same content; this can be implemented in practice
by using multicast protocols (e.g., see [28]). With a multicast protocol
This work is supported by the NSF Grant No. 0092113.
Journal of Algorithms, 2002, to appear.
CILOVI
in place, a stream sent to a client can be received by all other clients at
a minimal possible usage of network resources. To see how this can be
done and still preserve immediate-start delivery, we need the following as-
sumptions: clients can receive two streams in parallel and each has a cache
for buering stream content. Although multimedia streaming embraces
video, audio, and data streaming, we will stay with video terminology for
simplicity.
The basic idea of stream merging can be explained on the following
example. Consider a situation in which (i) client C 1 arrives at t 1 and
requests a video of duration L and (ii) client C 0 is currently playing the
same video from a stream S 0 that began at time t 0 < t 1 . Client C 1 missed
the rst  := t 1 t 0 time units of the video from S 0 and that part of the
video needs to be sent to C 1 by the server in stream S 1 . However, C 1 can
make use of stream S 0 by buering its content for later playback. In that
way the stream S 1 can be terminated after  time units. This process is
called stream merging; in the present case, S 1 was discontinued after being
"merged" at time with the earlier starting
Note that the total streaming time has been reduced from 2L; with no
merging, to a minimum achievable value of streaming
time is a simple and eective measure of bandwidth consumption that we
will retain throughout the paper.
merging becomes much more involved as we increase the number
of streams that are candidates for merging, because then the number of
ways in which merging can be done also increases. For example, consider
the case of three clients C 0 , C 1 , and C 2 arriving at times t 0 <
and initiating streams S 0 , S 1 , and S 2 for a video of duration L. Let
be the interarrival times. Figure 1 illustrates an example in which
the t i 's are given by 0, 3 and 4, and Consider the ways in which
we can merge the streams for all three clients. For the given setup, the two
possible merging patterns are shown in Fig. 1. In Fig. 1(a), S 1 and S 2 are
merged independently with S 0 as described earlier: C 1 caches S 0 during
during at the end of the
respective intervals S 1 and S 2 are merged with
The second possibility is rst to merge S 2 with S 1 and then S 1 with S 0 .
This scenario is illustrated in Fig. 1 (b). Figure 2 breaks down Fig. 1 (b)
into the individual schedules for C 1 and C 2 . Client C 1 plays S 1 and caches
during its buer which is only
fed by S 0 during the last L 2 1 time units of the video. Client C 2 caches
and plays from S 2 during at which point S 2 is discontinued,
and play proceeds from C 2 's buer. Client C 2 continues to cache S 1 ; but in
addition, it caches the remainder of S 0 (in a suitably chosen region of the
cache where the two buering operations can not overlap). This continues
2 at which point S 1 is shut down and S 0 becomes the only
(a) (b)
FIG. 1. Stream merging examples. The position of the video runs diagonally. The
x-axis represents time. By following the zig-zag lines one obtains which part of the video
is being played from which stream. The dashed lines show where the play of the video
changes from one stream to another.
schedule C schedule
FIG. 2. Individual schedules for the clients C 1
and C 2
in Fig. 1 (b).
active stream while it is supplying the last L units of
the video to the buer of C 2 . In this process, C 2 has played the rst  2
time units of the video directly from S 2 , the next  time units from
a cached segment of S 1 and the last L  time units from a cached
segment of S 0 .
At any given time, a vertical line in Fig. 2 crosses each of the streams
currently being received. Accordingly, in the schedules for C 1 and C 2 the
bold lines incident to the vertical lines at time t indicate that the buer
content at time t consists of the corresponding segments of S 0 and S 1 .
CILOVI
Note that, although the streaming at C 1 is the same as in the rst merging
example, does not terminate at time no longer needed
by the media server must still send S 1 to C 2 until C 2 can switch to
which occurs at in order to
facilitate the requirements of C 2 . Without such an extension C 2 would not
be in a position to receive all parts of the movie. Note also that the cost
(sum of stream durations) of the second merging pattern is 16 as compared
to the cost 17 of the rst pattern. In general, the best merge pattern for an
arrival at time t depends not only on arrival times before t; but also on the
arrival times after t. As it will become clear in the next section, for this
example the solution, that our dyadic tree algorithm yields, corresponds to

Figure

(b).
The technique of stream merging originated with Eager, Vernon, and Zahorjan
[11, 12] as a model of the pyramid broadcasting scheme introduced
by Viswanathan and Imielinski [36,37]. This paradigm provides the multi-cast
basis for sharing streams and is built upon the assumption that clients
can receive more bandwidth than they need for play-out. The skyscraper
broadcasting scheme [15,22,31] is another example of these new techniques.
A number of related techniques go under the names of batching [1, 9, 10],
patching [6, 16, 21], tapping [7, 8], and piggy-backing [2, 18, 19, 29] and the
general problem has several parameters and useful performance metrics.
Other parameters include delay guarantees, receiving bandwidth, server
bandwidth, and buer size [5, 13{15, 17, 20, 23{27, 30{35]. The maximum
number of streams is another metric that is of greater interest in certain
circumstances. In this setting, the algorithm of this paper has the properties

It is on-line, i.e., the media server does not know arrival times in advance

It gives a zero-delay guarantee, i.e., all video requests are satised
immediately.
It restricts the number of streams being received by a client at any one
time to at most two { the receive-two model.
The buer size can accommodate up to half of the video.
The last two assumptions are justied in the papers by Bar-Noy and Ladner
[3, 4], which supply the primary motivation for the work here. In
particular, most of the improvement of merging streams is already present
in the receive-two model. The L=2 buer size limit comes about because
our algorithm does not attempt merging with an existing stream that is
already at least half over. As Bar-Noy and Ladner argue, this convenience
does not lead to increased average cost even for only moderately large arrival
rates. For further discussion of the literature on stream merging, we
refer the reader to the mini-survey of [3].
Many excellent numerical/experimental studies have appeared in the
stream-merging literature, but the absence of mathematical foundations
has stood out, at least until the work in [3, 4], which focuses on compet-
itive, or worst-case, analysis. Here, we give what appears to be the rst
rigorous average-case analysis of a near-optimal algorithm.
The paper is organized as follows. In Section 2 we present the dyadic
tree algorithm and state our main results. Section 3 contains numerical
experiments that verify the algorithm's performance and conclusions. The
proofs of the main results can be found in Section 4.
2. ALGORITHM AND RESULTS
The problem of stream merging can be posed as a problem on trees
(see [3, 4]). A merge tree is a representation of a stream merging diagram,
such as those shown in Figure 1. Each stream of the merging diagram
corresponds to a node in the associated merge tree. Thus, the number of
nodes in the merge tree is equal to the number of requests placed with the
server, i.e., the number of clients. If stream S j is merged directly to an
earlier starting stream S i ; then the node associated with S j is a child of
the node associated with S i . It is convenient to label the nodes with the
arrival times of the corresponding streams.
A root stream is merged with no other stream, i.e., it is the root in a
merge tree. The length of the root stream is always the full length of the
video, L. The start rule below provides a simple way to determine which
streams are roots, i.e. it denes a sequence of merge trees. Let t
the stream starting times.
Start rule: Node t 0 is a root. If t i is a root, then t
L=2g is a root.
In other words, the start rule says that a node will be in a given tree
only if the root stream of that tree started less the L=2 time units ago. As
noted earlier, this constraint simplies the algorithmics; there is a sacrice
in e-ciency, but only when tra-c is low. For example, suppose we have a
root stream starting at time t 0 and an arrival at time t 1 with
made a descendant of t 0 ; then no other node arriving
after can be merged with t 1 without extending its length to L.
Hence, some gain is achieved only if there are no arrivals in the interval
However, this is an unlikely scenario under high tra-c
load.
When the arrivals are Poisson, the sequence of merge trees becomes a
renewal process. This fact allows us to focus our analysis on a single merge
tree rooted at t 0 . Let ft n g 1
n=0 be a sample path of a Poisson process with
rate  on the non-negative reals, and assume for convenience that t
6 COFFMAN, JELENKOVI
CILOVI
I
I
I 14
I 2
I 5FIG. 3. Dyadic partition of the interval.
The total length of all streams in a merge tree is dened as
l n 1ft n < L=2g; (1)
where l n denotes the length of the stream initiated by the arrival at time
the indicator function 1fAg is equal to 1 if A is true and 0 otherwise.
By denition l L. The quantity T will measure the eectiveness of
stream merging algorithms.
Our new stream merging algorithm is implicit in the following algorithm
for constructing merge trees from a given root.
The Dyadic Tree Algorithm: The input is a sequence of n > 0 arrival
times and the output is a tree of n nodes. The
arrival at time 0 determines the root. To nd the children of the root, rst
divide the interval [0; L=2) into dyadic subintervals I
with lengths shown in Figure 3. If I i contains at
least one arrival time, then t (i) denotes the earliest such time; otherwise,
Each t (i) > 0 is made a child of the root. Then for each t (i) > 0;
the algorithm is applied recursively to the interval [t (i) to determine
the subtree rooted at t (i) .
It is not di-cult to verify that this can be formulated as an on-line
algorithm, as we show at the end of this section. In particular, the decision
as to where a node t i should be attached to an existing tree is unaected by
arrivals after time t i . The following theorem gives our rst result, a uniform
bound on total stream length. We postpone the proof until Section 4.
Throughout the paper we use log to denote log 2 .
Theorem 2.1. The total cost of the dyadic tree algorithm satises4 L log(L)4 L  ET (L;
Furthermore, it can be shown that the upper bound of the preceding
theorem is asymptotically tight for large values of L. A detailed proof of
the next theorem is given in Section 4.
Theorem 2.2. The total cost of the dyadic tree algorithm satises
lim
Observe that, by Theorem 2.2, the long-time ratio of the expected total
stream length under the dyadic algorithm to that under an algorithm with
no merging is asymptotically equal to 3 log(L)=(2L).
Here we point out that, by Lemma 1 of [3], the length l of the non-root
stream initiated at time t > 0 is given by
where t p is its parent and t l is the last stream that merges with it. If t is
a leaf then t l = t, i.e.,
In order to consider the worst-case performance we examine a slightly
dierent model. This modication is necessary owing to the fact that in
the original model the number of requests in [0; L=2) is unbounded, so that
the worst case performance is meaningless. Let time be slotted and let the
video have a length of 2n time slots. We assume that in each of the slots at
most one stream can be initiated. According to the start rule a merge tree
is being built on n slots. The total stream length achieves its maximum
when a stream is initiated in every time slot. In [4] it is proved that the
worst-case performance of the optimal algorithm is (n log n).
Let T (2n) denote the total stream length for the worst-case merge tree
built on n slots, 1. It is easy to show by induction that T (n)
is monotonic in n; hence, one can assume that n is a power of 2. Next,
consider two merge trees built on n=2 slots each, i.e.,
1. The key fact is that in these two cases only the lengths of
streams initiated in the 0th and n=2-th slot dier. This follows from the fact
that the length of the stream initiated at t depends only on t and starting
times of the parent stream and the last stream that merges with it (see (2)).
In the rst case the lengths of streams initiated at are
2n and 3n=2, respectively. In the second case the lengths are equal to
n. Thus, the dierence is 3n=2 and one obtains T
The solution to this recurrence has the form T n). Thus, the
dyadic algorithm is within a constant factor of optimal in the worst-case. A
more detailed numeric comparison of the dyadic algorithm and the optimal
algorithm is made in the next section.
We conclude this section with a straightforward on-line implementation
of the algorithm.
8 COFFMAN, JELENKOVI
CILOVI
On-line Dyadic Stream Merging: Let S be a stack with push and pop
operations dened for triples of numbers (t a Each triple corresponds
to a stream: t a is the time at which the stream was initiated, t r is the time
after which newly arrived streams will not be allowed to merge with it and
t e is the time when the stream terminates.
push the root triple (0; L=2; L) onto S. At time t < L=2 of
a new request:
1. pop the triples (t a t; at this point let
be the top of the stack,
2. for all but the root triple in S increase the last component by 2t
is the arrival time of the parent of
3. add the new stream to the stack by performing push (t; t
a g; the stream
started at t is the child of the stream started at ^ t a .
This procedure uniquely and explicitly denes the merge tree as well as the
stream termination times.
3. NUMERICAL RESULTS AND CONCLUSIONS
This section provides a numerical validation of the asymptotic approxi-
mation
The rst example investigates the dependency of the total cost on the
length of the stream for xed values of the arrival rate . The parameter
values are set within the regions that are plausible for real-life systems. In
particular, we set plot the ratio ET=T 0 in

Figure

4, where ET is obtained by simulating 10,000 trees for each set of
values. Points marked with "o", "+" and "x" correspond to  1 equal to
5, 20, and 60 sec, respectively. Note that for the
merge tree consists of only 11 nodes on average.
In the second example we x L and look at ET (; L) as a function of the
rst argument. The simulation results of ET=T 0 are plotted in Figure 5. As
in the previous case we simulated 10,000 trees for each point. Values of L
are set to 120, 60, and 30 min and denoted respectively by the symbols "o",
"+", and "x". Using approximation T 0 with the appropriate multiplicative
factor yields excellent engineering estimates for all reasonable values of L
and .
Finally, we compare the performance of the dyadic tree algorithm to the
performance of the optimal o-line algorithm. The cost of the latter can be
2.5 30.10.30.50.70.9Length of the stream, hours
FIG. 4. ET=T 0 as a function of the stream length for three values of the arrival
rate. Expected interarrival times are 5 sec ("o"), 20 sec ("+") and 60 sec ("x").
FIG. 5. ET=T 0 as a function of the arrival rate for three values of the stream
length. The stream length is set to 120 min ("o"),
("x").
determined by a dynamic program (see [2]). Let T opt (i; j) be the optimal
cost of the merge tree for streams initiated at 0  t i <    < t j < L=2. The
optimal merge tree satises the preorder traversal property [4] and, hence,
1kn
CILOVI
Increase
in
cost,
FIG. 6. Performance of the algorithm in comparison with the optimal o-line
algorithm. The length of the stream is equal to 2 hours.
with T opt (i; L. The last term represents the gain from a merge of
optimal trees rooted at t 0 and t k . We used the fact that the length of the
stream t is given by (2).
For numerical comparison, let the length of the video be 2 hours and let
the value of the expected interarrival time vary from 5 sec to 60 sec in steps
of 5 sec. For every pair (; L) we simulated 1,000 trees and based on that
computed the average cost for two algorithms. The increase in expected
cost when using the dyadic tree algorithm instead of the optimal o-line
algorithm is rather small as shown in Figure 6. For all parameter values
the increase did not exceed 8%.
In summary, we have been able to prove the tight asymptotic average-case
behavior 3
4 L log(L) for the dyadic stream merging algorithm, and
to show in addition that its average-case and worst-case performance are
comparable to those of the best on-line algorithms known to date.
4. PROOFS
We start by introducing a recursive procedure for labeling the arrival
times in [0; L=2). For the purposes of the proof these labels replace the t i
labels. The procedure can be thought of as a function EL : T 7! ! that
maps a set T of arrival times to the space of indices !. Each index !
consists of a number of digits equal to the depth of the node in the merge
tree that corresponds to the given arrival. In general,
2:::, and the parent of the node labeled ! is a
FIG. 7. An illustration of the labeling algorithm. In this example there are seven
points that need to be labeled. On the rst call of the procedure three points are assigned
labels (1,2 and 4). The recursive algorithm is applied until all points are labeled.
node labeled with the prex . The algorithm labels the
arrivals as follows. The interval [0; L=2) is divided into dyadic intervals in
increasing order from the root as shown in Figure 3. If a point t is the rst
point in the subinterval I i then its label is i. Label the rest of the points
in [t; 2 i L) recursively by using the parent's label as a prex for childrens'
labels. An example of how the points are labeled is shown in Figure 7.
4.1. Proof of Theorem 2.1
Lower bound: By applying the above labeling procedure, it is not hard to
verify that (1) becomes
l n 1ft n <
l
where l !1 :::! n is the length of the stream starting at the point labeled
. If for a particular realization of the Poisson process there is no
point with label
Next, we estimate the expected values of l !1 :::! n . Let ; fn g 1
n=1 be a set
of i.i.d. exponential random variables with mean  1 , and consider rst
the streams that are children of the root, i.e., the streams whose indices
consist of a single digit. Given that, for a particular realization of the
Poisson process, there exists a stream with label ! 1 , its length must be at
least 2 !1 L=2 according to (2). Therefore,
l !1  L=2
L=2
CILOVI
taking into account the memoryless property
of the Poisson process, we conclude that
L=2
A node with label of form a child of the node with label ! 1 . Considering
the preceding inequality, the recursive nature of the merging algorithm
and the size of the problem in which node ! 1 is the root one obtains
L=2
L=2
The recursive structure of the merging algorithm shows that for a stream
with an arbitrary index

with the understanding that the sum in the above expression is equal to
zero if
and, hence, the expected value of an individual stream length is further
lower bounded by
L=2
Now observe that the number of indices with a digit sum equal to k is
since the above sum is equal to the number of ways one can partition a set
of cardinality k. Rearrange the sum in (3), use the bound (4) and apply (5)
to nd
L +X
L=2
L +X
L=2
where the last step follows from Jensen's inequality. Finally, simple manipulations
of the preceding bound yield
blog L
Llog(L) L
from which we conclude that the lower bound holds.
Upper bound: Consider the streams that are children of the root. For such
streams we have by (2)
l !1  3 L=2
The inequality is tight when there is an arrival right after time 2 !1 L=2
and an arrival just before time 2 !1 L. Next we examine the streams that
can be reached from the root in exactly two steps. An upper bound on
their length is
l !1!2  3
whereupon the memoryless property of the Poisson process gives
14 COFFMAN, JELENKOVI
CILOVI
Note that (6) and (7) are of the same form. In the rst inequality the size
of the problem is L=2 while in the second the size is (2 !1 L=2 infft n
. Since the merging algorithm is recursive, for
streams that have depth n  2 in the merge tree one can conclude that

3E
L=2
Recall (5) in order to verify that the number of indices with the digit sum
k and last digit i is equal to 2 k
The length of the root stream is always L so (3), (6), (8) and (9) yield
L=2
A simple computation shows that E (1
therefore, by changing the order of summation and setting
one obtains
Finally, straightforward but tedious calculations show
which in conjunction with bound (10) and the monotonicity of the function
log(L)je
This concludes the proof.
4.2. Proof of Theorem 2.2
The upper bound is a direct consequence of Theorem 2.1. Below we
provide the proof of the lower bound. Let P   P (;
the probability of having at least one Poisson arrival in an interval
of length . By conditioning on an arrival in both (2
and one obtains from (2)
3L=2
Extending the above reasoning to the streams with two-digit labels yields
a lower bound on their expected lengths
3L=2
In the above inequality we conditioned on the position of the stream
its parent and the last stream that will merge to it. Due to the recursive
structure of the algorithm, for a stream with an arbitrary label
the lower bound has the following form

3L=2
CILOVI
Next, the preceding inequality, (1) and (5) result in
3L=2
6
3L
Lblog(L)c 6L:
Finally, setting log log(L) and using log e > 1 yield
lim
log(L)
and, therefore,
blog(L)c
log(L)log log(L)
log(L)
as L !1:
This concludes our proof.

ACKNOWLEDGMENT

The authors would like to thank the anonymous reviewer for helpful comments.



--R

On optimal batching policies for video- on-demand storage servers
On optimal piggyback merging policies for video-on-demand systems
Competitive on-line stream merging algorithms for media-on-demand


Optimizing patching performance.
Improving video-on-demand server e-ciency through stream tapping
Improving bandwidth e-ciency of video-on-demand servers
A periodic broadcasting approach to video-on-demand service
Dynamic batching policies for an on-demand video server
Minimizing bandwidth requirements for on-demand data delivery
Optimal and e-cient mergind schedules for video-on-demand servers
Optimized regional caching for on-demand data delivery
Dynamic skyscraper broadcasts for video-on-demand

Supplying instantaneous video-on-demand services using controlled multicast

Reducing I/O demand in video-on- demand storage servers
Adaptive piggybacking: A novel technique for data sharing in video-on-demand storage servers
Exploiting client bandwidth for more e-cient video broadcast
Patching: a multicast technique for true video- on-demand services
Skyscraper broadcasting: A new broadcasting scheme for metropolitan video-on-demand systems
Fast broadcasting for hot video access.
Harmonic broadcasting for video-on-demand service
Staircase data broadcasting and receiving scheme for hot video service.
Enhancing harmonic data broadcasting and receiving scheme fo popular video service.
Fast data broadcasting and receiving scheme for popular video service.
Computer Networking: A Top-Down Approach Featuring the Internet
Merging video streams in a multimedia storage server: complexity and heuristics.





Data broadcasting and seamless channel transition for highly-demanded videos
Pyramid broadcasting for video-on-demand ser- vice
Metropolitan area for video-on-demand service using pyramid broadcasting
--TR
Reducing I/O demand in video-on-demand storage servers
Dynamic batching policies for an on-demand video server
Adaptive piggybacking
On optimal piggyback merging policies for video-on-demand systems
Metropolitan area video-on-demand service using pyramid broadcasting
Skyscraper broadcasting
Merging video streams in a multimedia storage server
<italic>Patching</italic>
Improving bandwidth efficiency of video-on-demand servers
Zero-delay broadcasting protocols for video-on-demand
Optimal and efficient merging schedules for video-on-demand servers
Catching and selective catching
An efficient bandwidth-sharing technique for true video on demand systems
Competitive on-line stream merging algorithms for media-on-demand
Computer Networking
Dynamic Skyscraper Broadcasts for Video-on-Demand
Fast broadcasting for hot video access
Supplying Instantaneous Video-on-Demand Services Using Controlled Multicast
A Low Bandwidth Broadcasting Protocol for Video on Demand
Exploiting Client Bandwidth for More Efficient Video Broadcast
On Optimal Batching Policies for Video-on-Demand Storage Servers
Video-on-Demand Server Efficiency through Stream Tapping

--CTR
Marcus Rocha , Marcelo Maia , talo Cunha , Jussara Almeida , Srgio Campos, Scalable media streaming to interactive users, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore
Marcelo Maia , Marcus Rocha , talo Cunha , Jussara Almeida , Srgio Campos, Network bandwidth requirements for optimized streaming media transmission to interactive users, Proceedings of the 12th Brazilian symposium on Multimedia and the web, November 19-22, 2006, Natal, Rio Grande do Norte, Brazil
Wun-Tat Chan , Tak-Wah Lam , Hing-Fung Ting , Prudence W. H. Wong, On-line stream merging in a general setting, Theoretical Computer Science, v.296 n.1, p.27-46, 4 March
Amotz Bar-Noy , Richard E. Ladner, Competitive on-line stream merging algorithms for media-on-demand, Journal of Algorithms, v.48 n.1, p.59-90, August
Raj Kumar Rajendran , Dan Rubenstein, Optimizing the quality of scalable video streams on P2P networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.15, p.2641-2658, October 2006
video-on-demand;average-case analysis;stream merging