Optimally Scheduling Video-on-Demand to Minimize Delay When Server and Receiver Bandwidth May Differ William Evans Abstract We establish tight bounds on the intrinsic cost (either minimizing delay d for fixed server and receiver bandwidths, or minimizing server bandwidth for fixed delay and receiver bandwidth) of broadcasting a movie of length m over a channel of bandwidth S in such a way that a receiver (with bandwidth R), starting at an arbitrary time t, can download the movie so that it can begin playback after a delay of at most d time units. Our bounds are realized by a simple abstract protocol that partitions the movie into a fixed number of segments, partitions the server bandwidth into an equivalent number of equal bandwidth subchannels, and broadcasts each segment repeatedly on its own subchannel. This protocol can be implemented as a concrete discrete protocol in which movie information is packaged into discrete fixed length packets using only a modest overhead (measured in terms of increased delay or server bandwidth). Our primary contribution is a lower bound on the required delay that applies in a very general model of communication. This lower bound matches the behaviour of our abstract protocol in the limit as the number of segments approaches infinity. We are also able to relate its behaviour to arbitrary protocols that have a fixed number of segments. 1 Intro duction David Kirkpatrick 1); no matter when a person tunes in, they know the movie will start within m minutes. If the television has memory and can record from the channel into the memory while simultaneously displaying from the memory, we can do better. Of course, if we knew what movie a person would request, we could store the entire movie in the television memory and there would be no delay in showing the movie. We assume that this is not possible and, in fact, that the television memory is empty when the person selects a movie (i.e. tunes to a channel). How small of a delay could we hope to achieve? In this paper, we obtain asymptotically tight upper and lower bounds on the delay achievable in this model. In particular, both bounds approach 1 -1 + j S/R =0 (j R-S )j S -j R e j! Suppose we broadcast a movie using bandwidth S (measured in units of movie bandwidth). A person may tune their television, which can receive any R/S fraction of the bandwidth, to this channel at any time in order to watch the movie. We would like to minimize the delay between when they tune to the channel and when they can start watching the movie. Let m be the length of the movie (in minutes). We can certainly guarantee a delay of at most m minutes simply by repeatedly broadcasting the movie back-to-back (as long as S and R are at least research was supp orted in part by the Natural Sciences and Engineering Research Council of Canada. Department of Computer Science, University of British Columbia, Vancouver B.C. Canada, V6T 1Z4. Email: {will, kirk}@cs.ubc.ca This of the total movie, as we increase the number of segments into which we divide the movie. In Section 3, we define our model of broadcast protocols. In Section 4, we outline our results. In Section 5, we describe a broadcast protocol that achieves the optimal delay in the limit as the number of segments into which it partitions the movie increases. In Sections 6 and 7, we show that this protocol is optimal by demonstrating a lower bound on the delay of any protocol within our model. In Section 8, we discuss the impact on our protocol of insisting on a fixed, smallest unit of transmission. We start by outlining some related work. 2 Related work Many video-on-demand protocols have been designed for repeatedly broadcasting a movie so that a receiver may receive and watch the movie by listening to the broadcast. Staggered broadcast is perhaps the simplest example of such a protocol. It repeatedly transmits a copy of the movie on each of c channels (each with bandwidth equal to the movie bandwidth). By starting the movie at equally spaced time intervals across the channels, a receiver need wait at most 1/c of the movie to start watching it. More complicated protocols require the receiver to Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688 1041 store what it reads from the broadcast into memory and then to play what it stores immediately or at a later time, perhaps while simultaneously reading additional broadcast data into memory. The family of pyramid protocols [8] partition a movie into some number of unequal size, contiguous segments and then transmit these segments on channels or sub-channels of equal bandwidth. On the other hand, the family of harmonic protocols [6] partition a movie into equal size segments and transmit them on unequal bandwidth channels: the ith segment receiving bandwidth 1/i. Early protocols in both families were designed like the staggered protocol so that a receiver could begin watching the movie immediately on receiving the first segment. In other words, a receiver could wait until the start of the first segment to begin watching and buffering the broadcast. Paris, Carter, and Long [7] ^ recognized that the receiver's wait could be decreased if the receiver buffered data from the moment they started receiving the broadcast. Their polyharmonic protocol (part of the harmonic family) forced every receiver to wait the same amount of time, regardless of arrival time. If the number of segments increases, the receiver's wait approaches a 1/(eS - 1) fraction of the movie, where S is the bandwidth of both the receiver and server. Hu, Nikolaidis, and van Beek's greedy equal bandwidth protocol [4] is a pyramid family protocol that also requires a forced delay. It achieves the same asymptotic performance as the polyharmonic protocol. All of these protocols assume that the receiver and server have the same bandwidth. However, in 1998 Gao, Kurose, and Towsley [3] proposed a formal framework for studying broadcast protocols that permit limited receiver bandwidth. They described the greedy diskconserving protocol for limited receiver bandwidth and illustrated its performance. They also proved that any broadcasting scheme with server bandwidth S will cause a client to wait at least 1/(eS - 1) fraction of the movie, for some arrival time. Hu [5] also claims this lower bound on client delay, but only for what he calls optimal ly-structured broadcasting protocols (which are similar to our early delivery stripped schedules). Engebretsen and Sudan [2] obtain the same 1/(eS - 1) lower bound by relating broadcast protocols to priority encoded transmission schemes of a particular type, for which they prove a lower bound. Bar-Noy, Ladner, and Tamir [1] also prove this lower bound, generalized to M movies as 1/(eS/M - 1). None of the lower bounds depend on receiver bandwidth. 3 Mo del We start by formalizing our notion of a broadcast protocol. A transmission function (t, x) is the instantaneous bandwidth allocated to movie instant x [0, m] at absolute time t [0, ), where m is the length of the movie. A reception function (t, , x) is the instantaneous bandwidth received of movie instant x at absolute time t + by a receiver that arrives at time t. A transmission/reception function pair (, ) defines a continuous t/r protocol. Such a protocol is consistent if (t, , x) (t + , x) for all t [0, ), [0, ), and x [0, m]; has sender bandwidth at most S if m (t, x)dx S 0 for all t [0, ); has receiver bandwidth at most R if m (t, , x)dx R 0 for all t [0, ) and [0, ); and achieves a length m video transfer with delay at most d if 0a a (t, d + a , x)dx - (t, d + a, x)dx a - a 0 for all t [0, ), a [0, m], and a [0, m]. It should be clear that every discrete movie t/r protocol can be expressed as a transmission/reception function pair. An advantage of considering protocols in this generality is that it allows us to prove the equivalence of any protocol with a natural regularized form of it. (Note this regular form is implicitly assumed in Hu's lower bound proof [5] even though it is not proved.) A transmission function (t, x) is regular if (t, x) = (t , x) for all t, t [0, ). Regularity states that the amount of bandwidth used to transmit a movie instant x is constant over time. Similarly, a reception function (t, , x) is regular if (t, , x) = (t , , x) for all t, t [0, ). Theorem 3.1. If (, ) achieves a length m video transfer with delay d using server bandwidth S and receiver bandwidth R, then there exists a regular transmission/reception function pair ( , ) with the same property. The proof is given in Appendix A and consists of regularizing (averaging) (, ) to obtain ( , ). 1042 3.1 Stripp ed proto cols Stripped protocols subdivide unit bandwidth channels into a fixed number of equal bandwidth subchannels (strips). The movie is partitioned into as many segments as there are strips, and each strip is dedicated to the transmission of information from one and only one segment (in an unconstrained fashion). Thus stripped protocols have a kind of discrete regularity ­ the bandwidth devoted to a single segment is constant over all time instants. A continuous t/r protocol (, ) with sender bandwidth S and movie length m is k -stripped if there exist xi for 0 i k S , where 0 = x0 x1 · · · xkS = m, (called movie partition points) such that xi xi-1 (, ) achieves late delivery with delay d if xi (t, d + xi , x)dx xi - xi-1 for all 1 i k S. Again, late delivery ensures only that the right quantity of bits are in hand by the time the segment finishes playing. 4 Results 1. There is a simple stripped protocol (Section 5) that fits the early delivery model and achieves optimal movie length among all such protocols with the same fragmentation factor (Section 6). 2. This same protocol approaches the optimal movie length among all protocols in the late delivery model as k goes to infinity (Section 7). The rate of convergence is O(1/k ). 3. It follows from 2. that our simple stripped protocol approximates the optimal movie length for any regular continuous t/r protocol (and hence, by Theorem 3.1, any even non-regular continuous t/r protocol.) 4. Our simple stripped protocol can be realized by a fully discrete protocol (using packets of a fixed size), but this causes a modest increase in the delay (Section 8). 5 An optimal early delivery stripp ed schedule Our results are the following: (t, x)dx 1/k for all t [0, ) and 1 i k S. xi-1 Stripped protocols are interesting because (i) many real discrete protocols are stripped protocols, and (ii) in the limit as the number of strips approaches infinity, stripped protocols become arbitrary regular continuous t/r protocols. 3.2 Early and late delivery We consider two models for stripped protocols. In each case we denote by k the fragmentation factor and assume that the total broadcast bandwidth can be subdivided into subchannels of bandwidth 1/k , each of which is dedicated to the broadcast of one movie segment. The models differ in their requirement for segment delivery. In the early delivery stripped model we insist that the information sufficient to play the entire segment is in hand before playback of the segment begins. In the late delivery stripped model we insist only that information sufficient to play the entire segment is in hand before playback of the segment completes. (In fact, our models are even weaker and hence more inclusive, requiring only that the quantity of bits received be sufficient for playback.) (, ) achieves early delivery with delay d if xi (t, d + xi-1 , x)dx xi - xi-1 for all 1 i k S. xi-1 Note that a protocol may meet the specifications of early delivery without actually achieving full video transfer ­ early delivery ensures only that we have received enough bits of each segment (with duplicates counted multiply), not necessarily the correct bits. We divide the server's bandwidth into strips of bandwidth 1/k for some integer k . Each strip is devoted to transmitting, repeatedly, a single, distinct, contiguous piece of the movie called a segment. The server transmits a segment on each strip in such a way that the receiver will obtain the entire segment if it reads from the strip starting at any point for time k where is the duration of the segment (measured in bandwidth units). A simple way to achieve this goal is for the server to transmit the segment, repeatedly, on the strip. At time 0, the receiver starts reading the k R strips that carry the first k R segments of the movie. Let d be the time when the receiver has the entire first segment of the movie. At this point, the receiver stops reading the first strip (carrying the first segment) and uses that bandwidth to read from strip k R + 1 (carrying segment k R + 1). The receiver follows this strategy for the duration of the movie: after receiving segment i, the receiver stops reading strip i and uses the nowavailable bandwidth to read from strip k R + i. The 1043 total number of strips available to carry the movie is k S . Thus receiving stops at the end of segment k S . In order to be able to show the movie without interruption starting at time d, the first segment of the movie must be in hand at time t0 = d. Since the protocol is stripped, playback of the first segment completes at time t1 = d + d/k , at which point we must have the second segment in hand. In general, for i 0, the completion time ti+1 of segment i + 1 is the completion time of segment i plus the duration of segment i + 1. Thus, ti+1 = ti + i+1 where t0 = d. d 0 The duration of the first segment, 1 , is tk = k . The duration of segment i + 1 is the amount of time the receiver spends reading from strip i + 1 divided by k . For the first k R strips, the receiver spends time ti reading strip i + 1. However, the receiver only reads strip k R + i + 1 (for i 0) after it has stopped reading strip i + 1. So the time spent reading strip k R + i + 1 is tkR+i - ti . Defining ti = 0 for i < 0, we obtain the following relation for i 0: ti - ti-kR i+1 = . k Combining this with the previous recurrence yields: if i < 0 0 d if i = 0 (5.1) ti = t -ti ti-1 + i-1 k-kR-1 if i > 0. Figure 1: The x-axis measures time while the y -axis represents server bandwidth that has been divided into many equal bandwidth strips. The black rectangles (one per strip) illustrate the times at which a receiver with bandwidth R = 2 will read each of the strips. The gray rectangles represent the transmitted movie segments. Server bandwidth is S = 6 and k = 7. Note that the sequence ti - d, for i = 0 . . . k S , are the movie partition points of the schedule. Figure 1 shows at what times the receiver reads from each strip in a movie transmission schedule when S = 6, R = 2, and k = 7. Viewing this figure, the reader may mistakenly conclude that segment duration is monotonically increasing. Figure 2, which eases the comparison of segment lengths, should confound this belief. This is an odd property for a supposedly optimal schedule: some later parts of the movie are transmitted more frequently than earlier parts. It follows from our results in Section 6 that an optimal schedule, for certain R and S , must have this surprising property. Before proving optimality, we calculate the delay that is guaranteed by the above scheme. As a first step, we restate the recurrence equation (5.1) in a slightly more general form and then present some of its basic Figure 2: The same segments as in Figure 1 but leftjustified to show their non-monotonicity. properties and a general solution. 0 d ti = ti-1 + if i < 0 if i = 0 if i > 0. (5.2) ti-1 -ti-a-1 k 1044 Lemma 5.1. If the sequence {ti } satisfies the recurrence 5.2 then 1 i 1 (i) ti = d + k , for 0 i a i 1 (ii) ti = d + k j-1-a tj , for i 0, and =i i , 1 1 i j a+1 i j -j a (iii) ti = d + k =0 (-) j 1 . for i 0, where = 1 a+1 k(1+ k ) Proof. The equation (i) follows 1mmediately from the i , 1 fact that t0 = d and ti = ti-1 + k for 1 i a. Equation (ii) follows from 5.2 by induction on i. Equation (i) provides the basis for an inductive proof of the equation (iii). For the inductive step, assume that it is true for all integer values i from 0 to n a. 1 t tn - tn-a 1 tn-a tn+1 = tn + = + n- k k k = -1 + 1 k + k d1 1 k collecting powers of , + n n+1 1 1 - ma 1 + (-)m tn+1 = d + m-1 k n +n m-1 j - ja - ja j (-) j j-1 =1 =d 1 1 + k n+1 n+1 j +1 a (-) =0 j n + 1 - ja j . Here we usn the = dntional fa( t that when n + 1 = e ad i c +1-ma -m they both equal 1). m(a + 1), m-1a m Theorem 5.1. The schedule described in this section achieves a delay of 1 -1 + j S/R =0 (j R-S )j S -j R e j! + 1 k n j +1 an (-)j n =0 n - ja j of the total movie, in the limit as k goes to infinity. Proof. The final segment finishes playing at time tkS , where ti is defined by recurrence equation (5.1). Thus the total movie time is tkS - d. If we can split a movie into an arbitrary number of segments, then we are interested in this value as k goes to infinity. Applying lemma 5.1(iii) with a = k R and i = k S , we get S/R d 1 n-a j +1 ( n-a a =0 (-)j - (j + 1)a j by ind. hypothesis) -1 n n+1 j +1 an 1 - ja j (-) =d + j k =0 n+1 j -a a =1 (5.3) 6 k lim tkS = d (-) j n Suppose that (, ) is a k -stripped protocol with server When n + 1 is not an integer multiple of a + 1, say bandwidth S and receiver bandwidth R that achieves n + 1 = m(a + 1) + r, where 1 r < a + 1, then early delivery with delay d. Let 0 = r0 , r1 , . . . , rkS = m -a +1 n m = n+1 = a+1 = n+1 + 1. In this case, be the movie partition points. a a Since (, ) is k -stripped, it follows that at time collecting powers of , d + ri the receiver has received at most (d + ri )/k units 1 n+1 1 of segment i + 1 for i 0. Since all of the movie interval tn+1 = d + [ri , ri+1 ] must be received by time d + ri , it follows that k n +n jm (6.4) ri+1 - ri (d + ri )/k - ja - ja · 1 + (-)j j j -1 =1 for i 0. =d 1 1 + k n+1 j +1 n+1 a (-) n-a 0 j - (j + 1)a j j =0 (j R - S )j S -j R e . j! Bounds on movie length under early delivery =0 n + 1 - ja j j . Lemma 6.1. rj + d d(1 + 1/k )j for j 0. Here we use the fact that n-j a = n+1-j a . j -1 Proof. When j = 0 the result follows from the fact j When n + 1 = m(a + 1) for some integer m, then that r0 = 0. From (6.4) and induction, we have -a +1 n m = n+1 = a+1 +1 = n+1 +1. In this case, again rj +1 (1 + 1/k )rj + d/k d(1 + 1/k )j +1 - d. a a = 1 and n-j a + 1045 Since (, ) has receiver bandwidth R, at time d+ri the receiver has received at most R(d + ri ) movie units. By the definition of early delivery, the entire movie interval [0, ri+1 ] must be in hand at time d + ri . Thus the information received by time d + ri that could be used for segments following the (i + 1)st segment is at most R(d + ri ) - ri+1 movie units. During time interval [d + ri , d + rj -1 ] only (rj -1 - ri )/k units of segment j are broadcast (since (, ) is k -stripped). Since the total size of segment j is rj - rj -1 and the segment must be received by time rj -1 , the part of segment j that must be received before d + ri is at least (rj - rj -1 ) - rj -1 - ri k where a - b max{a - b, 0}. Since this holds for all j > i + 1, we have, ( j rj -1 - ri rj - rj -1 ) - R(d + ri ) - ri+1 . k >i+1 For i 1, summing over j such that i+1 < j i+k R+1 and replacing - by -, this implies i+kR+1 ( j rj -1 - ri rj - rj -1 ) - R(d + ri ) - ri+1 . k =i+2 Simplifying the telescoping sum yields, ri+kR+1 - ri+1 - or equivalently (6.5) for i 1. Theorem 6.1. rj + d t j for j 0. Proof. Lemmas 5.1(i) and 6.1 establish the base cases (0 j k R). Since ti+kR = d + 1 k i+j R-1 k =i i+kR 1j rj + Rri R(d + ri ) - ri+1 k =i+1 7 Bounds on movie length under late delivery In the preceding section, we showed that the delay achieved by our k -stripped protocol is exactly the delay achieved by the best possible early delivery, k -stripped protocol. The early delivery model requires the entire ith segment to have been received by the time the (i - 1)th segment finishes playing. More general protocols, that still could play the movie without interruption, may receive part of the ith segment during the process of playing the ith segment. To include these more general protocols, we consider a model that only requires the ith segment to have been received by the time the ith segment finishes playing. This is the late delivery model and in this section we compare it to our k -stripped protocol. It is convenient to compare our k -stripped protocol to any late model (k + 1)-stripped protocol. Let (, ) be a (k + 1)-stripped protocol with server bandwidth S and receiver bandwidth R that achieves late delivery with delay d. Let 0 = s0 , s1 , . . . , s(k+1)S = m be its movie partition points. At time d + si+1 , the receiver has at most (d + si+1 )/(k + 1) units of segment i + 1. The late model insists that all of segment i + 1 (i.e. movie interval [si , si+1 ]) must be received by time d + si+1 . Thus, for i0 (7.6) si+1 - si (d + si+1 )/(k + 1), or equivalently, (7.7) si+1 - si (d + si )/k . ri+kR+1 Rd + 1 k ji+kR rj =i+1 It follows immediately from Lemma 6.1 and the correspondence between equations (6.4) and (7.7) that (7.8) si + d d(1 + 1/k )i , tj holds (by Lemma 5.1(ii), using the recurrence (5.1)) the result follows by induction on j (using (6.5)). This establishes that, for fixed delay d, the movie length, tkS - d, realized by our optimal schedule is at least as long as that achieved by any protocol in the early delivery, k -stripped model. for i 0. Since (, ) has receiver bandwidth R, at time d+si the receiver has at most R(d + si ) movie units. By the definition of late delivery, the entire movie interval [0, si ] must be in hand at time d + si . Thus, the information received by time d + si that could be used for segments following the ith segment is at most R(d - si ) - si movie units. During time interval [d + si , d + sj ] only (sj - si )/(k + 1) units of segment j are broadcast (since (, ) is (k + 1)-stripped). Since the total size of segment j is sj - sj -1 and the segment must be received by time sj , the part of segment j that must be received before d + si is at least (sj - sj -1 ) - sj - s i . k+1 1046 Since this holds for all j > i, we have, ( j sj - s i R(d + si ) - si . sj - sj -1 ) - k+1 >i For i 0, summing over j such that i < j i + (k + 1)R and replacing - by -, this implies i+(k+1)R ( j sj - s i sj - sj -1 ) - R(d + si ) - si . k+1 =i+1 Simplifying the telescoping sum yields, si+(k+1)R - si - i+(k+1)R j 1 sj + R s i R d + R s i - s i k + 1 =i+1 or (by collecting terms and scaling by (k + 1)/k ) (7.9) si+(k+1)R Rd(k + 1)/k + 1 k i+(k+1)R-1 j sj =i+1 for i 1. Let {ui } be the sequence defined by: if i < 0 0 d(k + 1)/k if i = 0 (7.10) ui = u -ui ui-1 + i-1 k-(k+1)R if i > 0. Since the recurrence (7.10) is a special case of our generic recurrence (5.2), it follows from Lemma 5.1(iii) that 1 i+1 1 ui = d + k ji (7.11) i (k+1)R - j ((k + 1)R - 1) j · (-) j =0 for i 0, where = 1 . 1 (k+1)R k(1+ k ) By direct analogy with Theorem 6.1 we have: Theorem 7.1. sj + d uj -1 for j 1. 8 Discretizing transmission One ob jection to the preceding continuous models is that they require the movie to be split into many small, arbitrary sized pieces as k increases. This may not be possible or desirable since we can't split a digital movie into pieces smaller than a single bit and the communication protocol may require packets to contain some integral number of bits. Another ob jection is our "parallel strips" view of the channel. One might argue that a channel transmits a sequence of bits or packets, and that we must convert from our parallel strips view to a serialized packet view. There is an obvious approach to this conversion: simply read and transmit a constant amount (a packet) from each strip in round-robin order (also known as time-division multiplexing ). However, we may have movie segments that are not divisible into an integral number of constant size packets. If we follow the obvious approach, we may create a packet that spans the start/end boundary of a strip's segment. The number of packets we need to obtain the segment from this strip is then one more than it should be and our serialized stripped schedule may fail to deliver the segment in time. To remedy this problem, we use our existing algorithm to obtain a stripped schedule for a channel with less than the actual available bandwidth. We then fatten each strip by a constant factor, enough to permit the transmission of each segment in one fewer packet. Let S be the server's bandwidth and R the receiver's bandwidth. We pretend that the server can send and we can receive only an fraction of the regular bandwidth for some < 1. We divide the server channel into k S strips, each with bandwidth /k . Using our optimal algorithm (Theorem 5.1), we create a schedule with delay d = m(k/) (R, S ) for a movie of length m where (k) (R, S ) = -1 + 1 + 1 k 1 kS k+ j kRS 1 =0 (-)j k S -j k R . j Let b be the length of the movie that can be played p This means that the movie length, s(k+1)S , of any using one packet's worth of information.d To read the /k ackets protocol in the late, (k + 1)-stripped model with fixed first segment (of length d/k ) we need b delay d is upper bounded by u(k+1)S -1 - d. It remains and they must be received by time d when transmitted to see how u(k+1)S -1 - d compares to the movie length, on the fattened strip (of bandwidth 1/k ). Thus, must tkS - d, of our optimal schedule. be small enough so that It is straight-forward to verify that both u(k+1)S -1 d b /k 1 and tkS converge to the same limit (equation (5.3)) d . b k as k goes to infinity; u(k+1)S -1 from above and tkS from below. The rate at which they converge is upper b bounded by their difference, which (by inspection of the This is satisfied for = 1 - d/k . Notice that for absolute values of the differences of their corresponding to be positive, b must be less than d/k , reflecting the need for the packet size to be smaller than the number terms) is seen to decrease asymptotically as O(1/k ). 1047 of bits needed to transmit the first segment. Since the first segment is smaller than any other segment, this choice of insures that the required number of packets to carry segment i arrive on the fattened strip before segment i arrived on the original strip, for all i. The cost of this packetization is an increase in delay. With server bandwidth S and receiver bandwidth R, we would expect our delay to be m(k) (R, S ). Our delay is m(k/) (R, S ). For example, if R = S , this is larger by a factor of b (1 + 1/k )kS - 1 e d/k S . (1 + /k )kS - 1 [6] L. Juhn and L. Tseng. Harmonic broadcasting for video-on-demand service. IEEE Trans. on Broadcasting, 43(3):268­271, September 1997. [7] J.-F. Paris, S. W. Carter, and D. D. E. Long. A low ^ bandwidth broadcasting protocol for video on demand. In Proceedings of the 7th International Conference on Computer Communications and Networks, pages 690­ 697, October 1998. [8] S. Viswanathan and T. Imielinski. Metropolitan area video-on-demand service using pyramid broadcasting. Multimedia Systems, 4(4):197­208, 1996. A App endix One should bear in mind that the length b of the movie that can be shown using one packet's worth of information is typically much smaller than the delay length d, so even for a rather large fragmentatation b factor k , d/k is small. 9 Conclusion Proof. [of Theorem 3.1] Let (t, x) = lim and (t, , x) = lim T 1 T T 1 T 0 T (t, x)dt 0 T (t, , x)dt. We consider broadcast protocols for video on demand when server bandwidth S and receiver bandwidth R may differ. We describe a simple stripped protocol in the early model (where each segment is received entirely before being played) that achieves optimal movie length for a fixed delay among all such protocols with the same fragmentation factor. 10 Acknowledgements We would like to thank Richard Ladner for introducing us to some of the problems in this area. References [1] A. Bar-Noy, R. E. Ladner, and Tami Tamir. Scheduling techniques for media-on-demand. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 791­800, January 2003. [2] L. Engebretsen and M. Sudan. Harmonic broadcasting is optimal. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 431­432, January 2002. [3] L. Gao, J. Kurose, and D. Towsley. Efficient schemes for broadcasting popular videos. In Proc. IEEE Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), July 1998. [4] A. Hu, I. Nikolaidis, and P. van Beek. On the design of efficient video-on-demand broadcast schemes. In Proc. Symp. on Modeling, Analysis and Simulation of Computer and Telecommunications Systems (MASCOTS), pages 262­269, 1999. [5] Ailan Hu. Video-on-demand broadcasting protocols: a comprehensive study. In Proc. IEEE INFOCOM, pages 508­517, April 2001. We note that ( , ) is consistent (t, , x) = lim 1 T T T T T (t, , x)dt (t + , x)dt (t, x)dt 0 lim 1 T T 0 1 T T = (t, x); = lim 0 has receiver bandwidth at most R m m T 1 ( t, , x)dx = lim (t, , x)dtdx 0 0 T T 0 Tm 1 = lim (t, , x)dxdt T T 0 0 T 1 lim Rdt T T 0 = R; and has sender bandwidth at most S m T m 1 (t, x)dx = (t, x)dtdx lim 0 0 T T 0 Tm 1 = lim (t, x)dxdt T T 0 0 T 1 S dt lim T T 0 = S. 1048 Now suppose ( , ) does not achieve a length m video transfer with delay d. Then there exists a time t and a movie interval [a, a ] such that a t, d + a x)dx - 0 ( , 0 a (t, d + a, x)dx < a - a. But 0 a (t, d + a , x)dx a T (t, d + a , x)dtdx (t, d + a , x)dxdt a (t, d + a, x)dx + a 1 = lim T T 0 T 1 = lim T T 0 T 1 lim T T 0 - 0 0 a 0 - a d t Ta 1 =a a + lim (t, d + a, x)dxdt T T 0 0 T a 1 (t, d + a, x)dtdx =a -a+ lim 0 T T 0 a =a -a+ (t, d + a, x)dx 0 This contradiction proves that ( , ) does in fact achieve a length m video transfer with delay d. 1049