A video-on-demand method, client and server

0001The present invention relates to a video-on-demand system and a method of broadcasting any of audio programs video programs, audio-visual programs and the like, for use in a video-on-demand system.

0002Traditional video-on-demand (VOD) systems provide users with the flexibility of choosing both the movie that they wish to see as well as the time that they wish to see it. Such a system is modelled using a client-server architecture in which the client consists of a set of users, while the video server contains a number of disks on which the videos are stored. Whenever a request for a video is made by a client, its blocks are fetched from the disks by a centralised VOD server, and transferred to the client isochronously.

0003In the event that the video is not present on the disks, it is typically to be fetched from tertiary storage. Thus, for each individual request by a client, an I/O stream needs to be scheduled. Each scheduling of an I/O stream typically requires a considerable amount of the network bandwidth. As a result, as the number of clients increases, the bandwidth may turn out to be a serious constraint. One solution to this problem includes the sharing of bandwidth among users. This type of solution is referred to as the User Centred Approach.

0004As the number of clients increases, an alternative approach for video on demand systems is that of periodic broadcasting.

0005In the broadcasting approach, bandwidth is dedicated to individual video objects rather than users. We assume that there are N movies (say, the N hot movies of the current year) which are broadcast periodically. Thus, in this case, the bandwidth is shared among the N different movies. As a result, the bandwidth utilisation of this technique is independent of the number of clients. This approach is a Data Centred approach because the bandwidth is divided among the individual video objects.

0006In the conventional broadcasting method, the access time for each of the N movies is determined by the frequency of broadcasting. The access time (also referred to as the latency or client wait time) for the movie is simply equal to the time required to access the first segment. Thus the access time of a movie decreases linearly with the bandwidth. An alternative approach to reduce the bandwidth requirement is the "Pyramid" scheme. In this technique, each video is divided into multiple segments and the initial segments are shorter and are transmitted more frequently. The Pyramid scheme is discussed in the paper, "Metropolitan Area Video On Demand Service using Pyramid Broadcasting", by S. Vishwanathan and T. Imelinki, SPIE Vol. 2417, pp. 66-77 (Feb. 1995). We shall subsequently refer to this scheme as the VI scheme.

0007Under the VI method, the access time for a movie is found to improve exponentially with the bandwidth. However, the VI method requires considerable amount of buffer requirements at the client end, which do not significantly change with the bandwidth. The VI method typically requires at each client a storage size which is substantially more than 50% of the length of the movie. In this range of storage sizes it may become necessary to use disks in order to do the buffering. Further, as the transmission rates may be significantly high, the client may need large disk bandwidth to write onto the disk as quickly as it is receiving the movie.

0008According to the first aspect of the present invention there is provided a method of broadcasting any of audio programs video programs, audio-visual programs and the like, for use in a system wherein the programs are broadcast to receiving stations, the method comprising the steps of: <ul id="ul0001" list-style="none" compact="compact"><li>repetitively broadcasting to the receiving stations a given portion of a particular program; and,</li><li>repetitively broadcasting to the receiving stations, less frequently than the given portion, a subsequent portion of the particular program; and</li><li>wherein data blocks of at least one of the given portion and the subsequent portion are broadcast in varying permutations from one repetition to a next repetition.</li></ul>

0009According to the second aspect of the present invention, there is provided a method of broadcasting any of audio programs video programs, audio-visual programs and the like, for use in a system of a type wherein the programs are broadcast to receiving stations, the method comprising the steps of: <ul id="ul0002" list-style="none" compact="compact"><li>repetitively broadcasting to the receiving stations, a given portion of a particular program; and,</li><li>repetitively broadcasting to the receiving stations, less frequently that the given portion, subsequent portions of the particular program;</li><li>wherein each portion is of a length which is proportional to a sum of the lengths of all preceding portions.</li></ul>

0010According to the third aspect of the present invention, there is provided a method of receiving any of audio programs video programs, audio-visual programs and the like, the method comprising the steps of: <ul id="ul0003" list-style="none" compact="compact"><li>(a) receiving a transmission comprising repetitive broadcasts of various portions of a particular program wherein data blocks of at least one of the portions are not organised in natural presentation order;</li><li>(b) determining a natural order of the data blocks;</li><li>(c) identifying a next data block required for a natural order presentation of the program to a viewer;</li><li>(d) latching onto the next data block in the natural order from a repetitive broadcast of the portion and skipping other data blocks in the broadcast; and,</li><li>(e) repeating steps (c) and (d) for subsequent repetitive broadcasts of the portion until each data block has been latched in the natural order.</li></ul>

0011According to the fourth aspect of the present invention, there is provided a method of broadcasting multimedia programs for use in a system wherein the programs are broadcast to receiving stations, the method comprising repetitively broadcasting to the receiving stations a plurality of portions of a multimedia program, each portion being broadcast less frequently than those portions of the multimedia program which are temporality previous in viewing order each of the portions comprising a plurality of data blocks which vary in permutation between one broadcast of the portion and a subsequent broadcast of the portion and wherein each portion is of a longer viewing length than those portions of the multimedia program which are temporality previous in viewing order.

0012According to the fifth aspect of the present invention, there is provided a client station for receiving broadcasted multimedia programs for use in a system wherein the multimedia programs are transmitted as a plurality of repetitively broadcast segments and wherein each of the segments includes a number of blocks which can vary in permutation from broadcast to broadcast, the station comprising: <ul id="ul0004" list-style="none" compact="compact"><li>a receiver having a channel selector and a block selector;</li><li>the channel selector including means for identifying channels on which a particular program is being broadcast and means for receiving blocks from the channels;</li><li>the block selector, coupled to the channel selector, the block selector including means for determining a natural viewing order of the blocks within each broadcast of a segment;</li><li>a buffer memory, coupled to the block selector, for storing from each broadcast of a segment, a next data block in the natural order; and,</li><li>a decoder, connected to receive the data blocks stored in the buffer memory.</li></ul>

0013The receiver selects blocks to be skipped (in a pyramid type broadcast) based on information indicative of the permutation selected by the server. The receiver determines the number of blocks to skip before buffering the next block for the video being viewed.

0014According to the sixth aspect of the present invention, there is provided a multimedia server, comprising: <ul id="ul0005" list-style="none" compact="compact"><li>a plurality of disks having data blocks of a multimedia presentation stored thereon;</li><li>a block selector for formatting the multimedia presentation into a plurality of segments, each of the segments including a temporally distinct portion of the multimedia presentation; and,</li><li>broadcast means for repetitively broadcasting to the receiving stations a plurality of portions of a multimedia program, each portion being broadcast less frequently than those portions of the multimedia program which are temporally previous in viewing order each of the portions comprising a plurality of data blocks which vary in permutation between one broadcast of the portion and a subsequent broadcast of the portion and wherein each portion is of a longer viewing length those portions of the multimedia program which are temporality previous in viewing order.</li></ul>

0015The multimedia (video) server divides the channel bandwidth among the videos to be broadcasted. Each video is divided into non-overlapping segments and each segment is further divided into blocks where a block is the basic unit of transmission. As in the VI scheme, the sizes and frequencies of transmission for the different segments of a video vary. However, instead of transmitting the blocks in each segment in sequential order, these blocks are transmitted in permutations.

0016A method/system embodying the invention has the advantage that it reduces the client storage requirement in systems using a pyramid type scheme. Further, a method/system embodying the invention has the advantage that it reduces the rate that data needs to be written to the client storage for buffering in systems using a pyramid type scheme.

0017The invention will now be described, by way of example, with reference to the accompanying drawings, in which: <ul id="ul0006" list-style="none" compact="compact"><li>FIG. 1 illustrates segment division;</li><li>FIG. 2 illustrates the block transmission order in accordance with an embodiment of the present invention;</li><li>FIG. 3 is a block diagram of a video (multimedia) server system according to an embodiment of the present invention;</li><li>FIG. 4 is a flow chart of the block selector in the server of FIG. 3; and</li><li>FIG. 5 is a flow chart of the channel/block selector in the client stations of FIG. 3;</li><li>FIG. 6 is a block diagram of a client station according to an embodiment of the present invention.</li></ul>

0018FIG. 3 is a block diagram of a video server system according to an embodiment of the present invention. The system includes a video server 100, wherein videos (such as movies) are stored in disks 102 in the form of a plurality of blocks 104 which can be striped across the disks. The video server 100 includes a processor (cpu) 106 which performs under control of program code (programs) stored in a main memory 108. The video server 100 also includes a memory buffer 110 for temporarily storing retrieved video blocks 104 and a network interface 112 for coupling the video server 100 to a communication network 114. The network interface 112 divides the communication network 114 into a number (R) of TDM channels onto which video data is be broadcast.

0019In accordance with an embodiment of the present invention, one of the programs which controls the operation of the video server 100 is a Fibonacci Segment Scheduler 116. The Fibonacci Segment Scheduler 116 includes a block selector 118 whose functions include selection of video blocks to retrieve from the from disks 102 and the selection of a network channel for transmission. The block selector 118 works in conjunction with various convention control processes 120 to retrieve the selected blocks from the disks and to cause the selected blocks to be broadcast to client stations 122 by way of the communication network 114. As will be described in more detail later, the video blocks are periodically transmitted (broadcast) on the network 114 in various size segments along with permutation information 124. The video server 100 also broadcasts movie ID information 126 which identifies (to the client stations) which movie is being broadcast on which set of channels.

0020Each of the client stations 122 includes a channel/block selector 128 (which can be embodied using microprocessor executable program code) which selects appropriate channels and video blocks transmitted thereon for decoding and viewing by the client. The selected video blocks are provided to a buffer 130 where they are temporarily stored and then provided to a decoder 132 in proper temporal playout order.

0021The video server 100 can be embodied using any processor of sufficient performance for the number of video streams to be supported. For example, a small capacity video server could be embodied using a RISC System/6000 TM system while a larger capacity server could be embodied using an ES/9000 TM system (both available from International Business Machines Corporation of Armonk, New York). The disks 102 can be, for example, a conventional RAID-5 disk array. The communication network 114 can be, for example, a fibre optic network or a conventional bidirectional cable network. The client stations 122 can be embodied as a set-top box including the memory buffer 130. The decoder 132 should be such that it conforms to the format of the video blocks (as read from the buffer 130). Typically, this will be an decoder complying with the MPEG-1 or MPEG-2 compression standards.

0022Each movie is partitioned into segments S₁, S₂, ... S_R of geometrically increasing sizes such that S_i= αS_i-1. The geometric parameter α is larger than 1. Alternatively, this partitioning employs a general Fibonacci sequence in which the segment sizes can be related as follows:<maths id="math0001" num=""><img file="EP0768768A2_D0001.tif" /></maths>

0023The network 120 is divided into R channels. Each of the segments of size S_i is transmitted only on channel i.

0024Figure 1 illustrates the segment division in the conventional VI scheme. This figure illustrates the case for 2 movies. (This can be generalised to any number of movies.) Each of the movies is divided into 4 segments, such that the (i+1)th segment is twice as large as the ith segment. Thus, as shown in the figure, movie 1 is divided into the 4 segments A1, B1, C1, and D1, while the movie 2 is divided into the 4 segments A2, B2, C2, and D2.

0025On the first channel, only the segments of the smallest size are transmitted. Thus, on the first channel, only the segments A1 and A2 are transmitted. On the second channel, the next largest segments B1 and B2 are transmitted, the next largest segments C1 and C2 are transmitted on the third, and the largest segments D1 and D2 are transmitted on the fourth.

0026In order to start to receive transmission of (say) movie 1, the client latches on to the first segment (A1) of the movie. The transmission rate on each channel is larger than the consumption rate. Consequently, as a particular segment (A1) is being transmitted, video data builds up (is buffered) at the client end. After the transmission of A1 has been completed, this buffered data is used to continue the uninterrupted transmission at the user end, while the client tries to latch on into the next segment B1. This process continues for each successive segment until the whole movie has been accessed. The transmission and reception parameters are chosen in such a way that the transmission can be carried on continuously without any interruption.

0027In the present embodiment, each segment is divided into multiple blocks. However, in contrast to the VI scheme, the blocks are not transmitted in their natural sequence. Instead, the order of the blocks is permuted in such a way that the storage requirements are reduced substantially.

0028An example of the general order in which the blocks are transmitted in the VI scheme versus the present scheme is illustrated in the Figure 2. Figure 2 shows the first channel of Figure 1 in which the segments A1 and A2 are transmitted. The segment A1 is divided into 6 blocks: a, b, c, d, e, f. The segment A2 is divided into the 6 blocks labelled p, q, r, s, t, u. The top half of Figure 2 illustrates the order in which the blocks are transmitted in the VI scheme. The lower half of Figure 2 illustrates the order in which the blocks are transmitted in the present scheme which is a permutation based scheme.

0029In the present scheme, the video server staggers and interleaves multiple copies of a segment. Each copy is referred to as a transmission group. In the example of the present scheme provided in Figure 2, every 6^th block is consecutive and it forms a group. In general, every Gth block is consecutive, and the parameter G is chosen in a way which is described later.

0030In Figure 2, three transmission groups are shown. The first group is (a, b, c, d, e, f) where the blocks are circled. The second group is (e, f, a, b, c, d), where the blocks are interleaved with the first one and located one position to the right. The third group is (c, d, e, f, a, b), where the blocks are interleaved with the first one and located two positions to the right. The staggering distance of the second group from the first group is 2 counting cyclically backward where that of the third group is 4 counting cyclically backward. The methods to determine the number of groups to be staggered and the staggering distance are provided later.

0031Note that in Figure 2 all the blocks corresponding to one particular group are circled. All of these blocks are received at the client end in accordance with the principles of the present invention. Thus, from the client point of view, it has to receive every Gth block corresponding to a particular group. As discussed with respect to Fig. 2, a group is formed by every 6^th block in the diagram. Thus, there are 6 groups in all, i.e. 3 groups for each video. Further, every pair of consecutive groups of a segment are (cyclically) distant from one another by two blocks. In general every Gth block is consecutive, and the client latches onto the time division from which to tap these blocks.

0032It can be seen from Fig. 2 that the latency time in both of the VI scheme and the present scheme is the same, when S_i = αS_i-1. However, the present scheme also considers a general Fibonacci sequence in which the segment sizes can be related as follows:<maths id="math0002" num=""><img file="EP0768768A2_D0002.tif" /></maths>

0033This reduces the latency and further decreases buffer requirement.

0034The above described scheme staggers the various segments in such a way that the transmission rate is greatly reduced. This reduced transmission rate helps in reducing the storage requirements at the client substantially. The larger the number of groups staggered and interleaved in the transmission of each segment the greater the reduction of storage requirement at the client. At the same time, this staggering is limited by the fact that too much of it may not satisfy the isochronous requirement at the client end. Thus, the various segments should be staggered by the maximum amount without violating the client consumption requirement for continuous showing.

0035Within a segment, the distance between consecutive blocks in a group should be less than the play time of a block. Furthermore, there is an additional requirement between the consecutive segments of a movie. When the ith segment is not begun to be received before the end of the consumption of the (i-1)th segment, it is called a hiccup. While pursuing staggering to reduce storage requirement, one needs to at the same time avoid creating a hiccup. It is noted that the last segment may be staggered only under the constraint of the client consumption rate, because there is no danger of a hiccup in that case.

0036Assume that the network bandwidth is B, the consumption rate is c, and the number of movies to be shown is N. The length of the movie is assumed to be L. Let p be the number of groups staggered or interleaved in the transmission of each segment and p_last be that for the last segment.

0037In the preferred embodiment, <ul id="ul0007" list-style="none" compact="compact"><li>1. Choose α to be a small integer. In practice, setting α=2 turns out to be a good choice.</li><li>2. Choose R to be the largest integer value which is less than or equal to 8, which satisfies the following relationship:<maths id="math0003" num=""><math display="block"><mrow><mtext mathvariant="italic">R</mtext><mtext> ≤ </mtext><mfrac><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">N</mtext><mtext>(α+1)</mtext><mtext mathvariant="italic">c</mtext></mrow></mfrac></mrow></math><img file="EP0768768A2_D0003.tif" /></maths> The value 8 is arbitrary because in practice when α is 2, and R is 8, the user latency is so small, that any further improvement is superfluous. Thus, we choose:<maths id="math0004" num=""><img file="EP0768768A2_D0004.tif" /></maths></li><li>3. Divide the movie into generalised fibonacci segments, S₁, S₂, ... S_R, satisfying the following two relationships:<maths id="math0005" num=""><img file="EP0768768A2_D0005.tif" /></maths> and<maths id="math0006" num=""><img file="EP0768768A2_D0006.tif" /></maths></li><li>4. Choose p to equal to the largest integer which satisfies:<maths id="math0007" num=""><math display="block"><mrow><mtext mathvariant="italic">p</mtext><mtext>_</mtext><mfrac><mrow><mtext mathvariant="italic">B</mtext></mrow><mrow><mtext mathvariant="italic">NRc</mtext></mrow></mfrac><mtext>-α+</mtext><mtext mathvariant="italic">1</mtext></mrow></math><img file="EP0768768A2_D0007.tif" /></maths> Consequently, we choose:<maths id="math0008" num=""><img file="EP0768768A2_D0008.tif" /></maths></li><li>5. Choose:<maths id="math0009" num=""><img file="EP0768768A2_D0009.tif" /></maths></li><li>6. Divide each segment S_i into pL_i blocks for each i∈ 1 ... (R-1). Thus each segment S_i is divided into a multiple of p blocks. The value L_i is chosen as large as possible for each segment S_i. Further, the last block S_R is divided into p_last · L_R blocks.</li></ul>

0038Note that L_i (respectively, L_R) is the staggering distance among the p (respectively, p_last) transmission groups of each segment (respectively, the last segment). Furthermore, for each movie, the distance between consecutive blocks of a segment (G) is equal to p except for the last segment where the distance is p_last. Hence, for N movies sharing the channels, the distance is Np for each segment, except the last segment where the distance is Np_last.

0039The basic order of transmission of the blocks for the different channels and movies is as follows: <ul id="ul0008" list-style="none" compact="compact"><li>for q=1 to N (movie number)</li><li>for i=1 to R (channel number)</li><li>transmit the next block in sequence for channel i and movie q next I next q</li></ul>

0040We assume that the transmission is divided into R channels and consider the transmission on the ith channel for a particular movie q.

0041FIG. 4 presents a flow chart of the server block selector 118 of FIG. 3 according to an embodiment of the present invention. The flowchart shows the sequence in which blocks are transmitted at the client end for a particular channel i and movie q. It should be understood, however, that the sequence of transmission is actually interspersed using time division multiplexing. Channel R employs a slightly different transmission algorithm from other channels.

0042In step 201, the indexing variables for transmission blocks are initialised, where j is set to 1 and n is set to zero.

0043In step 205 the value of the channel number (i) is checked. If i is less than R (the last channel), block nL_i + j is selected for the next transmission in step 210. n is then incremented by 1 in step 215.

0044In step 220, it is determined if n is less than p (the number of groups per segment other than the last segment). If n is less than p, step 210 is executed again for the next transmission. Otherwise, the channel number j is set to (j+1) mod p in step 225.

0045If, in step 205, it is determined that i is set to the last channel number R, block nL_R + j is selected for the next transmission in step 240. Then, n is then incremented by 1 in step 245. In step 250, if n is less than p_last (the number of groups in the last segment), step 240 is executed again for the next transmission. Otherwise j is set to (j+1) mod p_last in step 255.

0046FIG. 5 shows a flow chart of the client station channel/block selector 128 according to an embodiment of the present invention. Assume that the client wants to receive video q. In step 300, the indexing variable i on the next segment to receive is set to 1.

0047In step 305 the receiver latches onto any block of the ith segment of video q which comes in first on channel i. Then, in step 310, the channel/block selector checks whether the buffer 130 is full. If yes, the next pL_i blocks of video q in transmission is skipped. Otherwise, in step 320, the channel/ block selector 128 receives the next block of segment S_i of video q which first arrives on channel i and stores in the buffer 130.

0048In step 325, the channel/block selector checks whether all blocks of segment S_i have been received. If so, in step 330, it is determined whether i is equal to R. If all blocks have not been received, the channel/block selector returns to step 305.

0049If, in step 330, it is determined that i is not equal to R, in step 335 i is incremented by 1 and then the channel/block selector returns to step 305. If, however, it is determined that i is equal to R, the entire video has been received and the channel/block selector exits in step 340.

0050Note that in the client receiving algorithm, the number of blocks to be skipped by the client before receiving the next consecutive block is almost a constant, but not quite. Every once in a while, the next block to be received is spaced one block ahead of the distance between the previous two blocks in the same group. This can be done either by incorporating header information at the front of the blocks which describes which movie a block belongs to, or it can be done by simply skipping a block after receiving every L_i blocks from the segment S_i.

0051The present invention is also applicable if frequency division multiplexing is used. At the broadcasting server, again each video is divided into multiple segments and each segment is divided into blocks. Each channel is divided into p subchannels and the staggered groups for each segment is now mapped onto the subchannels. The blocks in each segment are transmitted concurrently on the multiple subchannels with different phase shifts corresponding to the staggering distance. The methods to determine p and the staggering distance is the same as before. At the client end, the appropriate subchannel is selected based on the phase shift requirement to receive the next block in order to minimise the storage requirement.

0052FIG. 6 is a block diagram of a client station 130 according to an embodiment of the present invention. The client station includes a network interface 602 which provides the electrical and communications interface to the network 114. Information from the network is routed to the appropriate client station components by the network interface 602.

0053The Permutation Information 124, Movie ID 126 as well as other conventional timing information is directed along a first path. The Permutation Information 124 and Movie ID are stored in a memory 604 while the timing information is provided to a control processor 606. The control processor 606 operates under program control in accordance with the flowchart of FIG. 5.

0054The video blocks are directed along a second path to a TDM demultiplexor 608. The TDM demultiplexor uses the channel data portion of the Movie ID (the data which indicates which channels a movie and its particular segments is being carried on) as a select input. The control processor loads a register 610 (which provides the TDM demultiplexor's select input) with the appropriate channel data for receiving a desired segment.

0055The selected segment is provided from the output to the TDM Demultiplexor to the input of a Block demultiplexor 612. The select input of the Block demultiplexor is provided by a second register 614 which the control processor loads with the appropriate block selection data as determined in accordance with the flowchart of FIG. 5.

0056The selected block is provided to a buffer memory 130 in which it is temporarily stored and then provided to a decoder 132. The decoder 132 decodes the buffered blocks in temporal order and, in turn, provides a video output to a user display device.

0057Those of ordinary skill in the art will understand that various timing signals, which will not be described in detail here, are provided to each of the components of the client station to ensure its proper operation.