当前位置:首页 >> >>

On the design of a low-cost video-on-demand storage system


On the Design of a Low-Cost Video-on-Demand Storage System
Banu Ozden Rajeev Rastogi Avi Silberschatz AT&T Bell Laboratories 600 Mountain Avenue Murray Hill NJ 07974-0636
Abstract

fozden, rastogi, avig@research.att.com

Recent advances in storage technology, coupled with the dramatic increase in the bandwidth of networks, make it now possible to provide \video on demand" service to viewers. A video on demand server is a computer system that stores videos in compressed digital form and provides support for di erent portions of compressed video data to be accessed and transmitted concurrently. In this paper, we present a low-cost storage architecture for a video on demand server that relies principally on disks. The high bandwidths of disks in conjunction with a clever strategy for striping videos on them is utilized in order to enable simultaneous access and transmission of di erent portions of a video, separated by xed time intervals. We also present a wide range of schemes for implementing VCR-like functions including fast-forward, rewind and pause. Finally, we extend our schemes to the case when videos have di erent rate requirements.

1

1 Introduction
The video on demand (VOD) concept has become exceedingly popular with telecommunications, computer and cable companies. Viewers that subscribe to a VOD service have access to a much wider feature set in comparison to the broadcast based cable and TV networks. For example, a viewer can start watching a video, from among a particular set of videos, at any time the viewer wishes to do so. When watching a video, a viewer can apply VCR operations like pause, resume, fastforward and rewind to the video. Thus, VOD services di er substantially from today's broadcast cable services in which, at any given time, all the viewers see the same portion of a video and viewers of videos have no control over its transmission. Also, unlike today's video stores, VOD services o er convenience (since viewers do not have to leave their homes) and typically result in lower response times. Until recently, low network bandwidths and video storage technologies made o ering VOD services to viewers a di cult task. However, today, networks built using optic bers have bandwidths of several gigabits per second. Furthermore, not only is it now possible to store video data in digital form, but it is also possible to obtain high compression ratios. For example, display of video at 30 frames/sec that is compressed using the MPEG-1 Gal91] compression algorithm requires a bandwidth of merely 1.5 Mbps. Thus, it is possible now to concurrently transmit independent video streams to thousands of viewers. Even though the problem of transmitting video data is considerably simpli ed due to the availability of high bandwidth networks, the design and implementation of VOD storage servers that are responsible for the storage and retrieval of di erent portions of videos simultaneously remains a non-trivial problem. A storage architecture for a VOD server must address the following issues: low-cost, continuous retrieval of videos, ability to support VCR operations, and servicing multiple viewers concurrently. In general, a VOD server will contain a cache to temporarily store the currently viewed videos. The currently viewed videos will be loaded onto the cache from a library which stores videos permanently (e.g., a jukebox of tapes). The cache can be designed with random access memory (RAM) as a at architecture. However, this approach will increase the cost of the VOD server substantially due to the high cost of RAM and the high storage requirements of videos. For example, an MPEG-1 compressed 100 minute video with an average bandwidth of 1.5 Mbps requires approximately 1.125 GB of storage. Assuming the cost of RAM is $50:00 per MB, the cost of a 2

RAM-based cache to store 100 videos will exceed $5:5 million. In this paper, we propose a storage hierarchy to design a low-cost cache for a VOD server. The hierarchy consists of disks which store the currently viewed videos, and a small amount of RAM bu ers which store only portions of the videos. Due to the low cost of disks (approximately 30 cents per MB), the cost of a VOD server based on our architecture is substantially less than the one in which the entire video is loaded into RAM. However, unlike a RAM-based architecture, access times to random locations on disks are relatively high. Therefore, clever storage allocation schemes must be devised to continuously retrieve di erent portions of a video for a large number of users and at the same time to minimize the bu ering requirements. For the same reasons, the implementation of VCR operations like fast-forward, rewind, pause and resume is a di cult task. We present a \phase-constrained" storage allocation scheme which enables a large number of di erent parts of a video to be viewed simultaneously, and a variety of schemes for implementing the VCR operations. The schemes illustrate the trade-o between the size of the RAM bu ers required and the quality of the VCR-type service, in particular, abruptness in display perceived by viewers during fast-forward/rewind operations as well as the response time for switching back to normal display mode from pause, fast forward and rewind modes. The lower costs of schemes that provide limited functionality for fast-forward, rewind and pause make them attractive for a wide range of environments. The remainder of the paper is organized as follows. In Section 2, we present an overview of the system architecture that provides VOD services. We present our scheme for storing videos on disks in Section 3. In Section 4, we describe how VCR operations can be implemented in our architecture. Schemes for implementing ne granularity fast-forward and rewind are presented in Section 5. In Section 6, we present bu ering schemes that provide the same functionality as if videos were stored in RAM, but do not require entire videos to be stored in RAM. We extend our scheme to handle multiple videos with varying rate requirements and multiple disks in Section 7. A comparison of our work with related work in the area can be found in Section 8. Concluding remarks are o ered in Section 9.

2 Overall System Architecture
In this section, we present an overview of the system architecture for supporting VOD services. The main system component, the VOD server, is a computer with one or more processors, and a 3

Movie Library

MOD Server

RAM Buffer

Network

Decoder Display

Decoder Display

Figure 1: System architecture for VOD servers. cache to hold a set of currently viewed videos in compressed form. The cache is updated from a library of videos at the same site or from a library or a cache at another site. The cache that stores the currently viewed videos can be designed as a at architecture consisting only of RAM. Due to the high cost of RAM, however, this approach makes the cost of a VOD server prohibitively expensive. Therefore, we propose a two-level cache architecture consisting primarily of secondary storage devices and a limited amount of RAM. The second level of the cache consists of disks, which store the currently viewed videos, while the rst level consists of the RAM bu er to temporarily hold portions of videos currently being displayed. Due to the lower cost of disks, our approach yields cheaper VOD services. Figure 1 illustrates the overall architecture for VOD servers. The compressed data for video Vi is transmitted at a rate of ri over a high bandwidth network individually to every viewer that requests the video. The number of viewers serviced by a single VOD server would vary depending on the geographical location. However, we expect this number to be between 5,000 and 10,000. Every viewer has a decoder, which consumes the compressed data for video Vi from a local bu er at a rate of about ri and outputs frames to a display at the playback rate (which is typically 30 frames/sec). Viewers can issue commands to control the display of a video that is stored in the VOD server. These commands include begin, fast-forward, rewind, pause and resume. The commands are transmitted to the VOD server, which maintains information relating to the status of every viewer (e.g., 4

the last command executed by the viewer, the position in the video of the last bit transmitted to the viewer). While a video is being displayed, viewers can apply any of the above commands to control the display of the video. We refer to the transmission of a video starting at a given time as a phase. Two phases may correspond to the same or di erent videos. To simplify our discussion, we will initially present our results assuming that only one video with rate rd is being handled by the VOD server. In addition, we assume that the server has a single disk with bandwidth rt . In Section 7, we show how our results can be generalized to multiple videos with varying rates and multiple disks. The maximum number of concurrent phases that can be supported by retrieving video data from the disk, denoted by p, is given by:

r p = b r t c:
d

(1)

The reason for this is that each phase requires video data to be retrieved from disk at a rate rd . Even if the server can support the maximum number of phases, this number is not, in general, su cient to provide each viewer with an independent phase, since the number of viewers will typically be larger than the maximum number of phases. The challenge is to devise clever storage algorithms and bu ering techniques to assign viewers to the right phases at the right times in order to provide on-demand video service with VCR functionalities. Since the server can support a limited number of concurrent phases that are shared between several viewers, it follows that in order to provide low average response times when viewers request a video, and to provide good implementations of VCR operations, the following two properties should be preserved: 1. The VOD server must support the maximum number of phases. 2. The phases must be uniformly distributed across the entire video. Thus, in a VOD server that preserves the above two properties, if the length of the video is l l seconds, then the di erence between any two concurrent phases is p . Our goal is to devise storage allocation schemes that support the maximum number of concurl rent phases, each of which is p apart. Furthermore, in order to keep the cost of the system low, the storage allocation scheme must not require large amounts of video data to be bu ered in RAM.

5

3 The Basic Storage Architecture
In this section, we propose a storage architecture that enables a VOD server to support the maximum number of concurrent phases with xed phase di erences, and requires only a small amount of bu er space to be maintained per phase. Before presenting our scheme, we rst show that adopting the naive approach of storing the video data contiguously on disk requires large amounts of video data to be bu ered in RAM, which implies that we need to develop better allocation schemes. For every phase, the video data from disk is retrieved into a RAM bu er of size b bits at a rate rd . In order to ensure that data for the p phases can be continually retrieved from disk at a rate rd , in the time that the b bits from p bu ers are consumed at a rate rd , the b bits of the video following the b bits consumed must be retrieved into the bu ers. Since each retrieval involves positioning the disk head at the desired location and then transferring the b bits from the disk to the bu er, we have the following equation. ( rb + tlat ) p rb t d where tlat is the disk latency. Hence, the size b of the bu er per phase can be calculated as lat r b t( rt ?dr rt : (2) d) p Thus, the bu er size per phase increases both with latency of the disk and the number of concurrent phases. In the following example, we compute for a commercially available disk the sizes of portions of videos that need to be bu ered in order to support the maximum number of concurrent phases.

a transfer rate of 80 Mbps and a disk latency of 15 milliseconds. Suppose that MPEG-1 is used, which implies that rd is 1.5 Mbps. Thus, the maximum number of concurrent phases that can be supported at a rate of 1.5 Mbps using the device is b 180 c = 53 = p. Using Equation 2, we compute :5 the bu er size requirements b to support 53 concurrent phases to be b 190 Mb. Since we require 53 di erent bu ers, the total storage requirements are 53 190 10 Gb, which is larger than the size of a 111 minute video. 2

Example 1: Consider a commercially available disk costing $3000 with a capacity of 9 GB,

3.1 Phase-Constrained Allocation
In order to keep the amount of bu er per phase low, we propose a new storage allocation scheme for a video on disk, which we call the phase-constrained allocation scheme. The phase-constrained al6

For the disk in Example 1, and a 100 minute video, tc = 6000 = 113:21 seconds. We refer to tc as 53 the smallest phase di erence since the rst bit in any two adjacent rows are tc seconds apart in the video. Since video data in each row is retrieved in portions of size d, a row can be further viewed as consisting of n portions of size d, where n = tc drd Thus, a video can be represented as a (p n) matrix of portions as shown in Figure 2. Each portion in the matrix can be uniquely identi ed by the row and column to which it belongs. Suppose we now store the video matrix on disk sequentially in column-major form. Thus, as shown in Figure 3, Column 1 is stored rst, followed by Column 2, and nally Column n. We show that by sequentially reading from disk, the video data in the p rows can be retrieved concurrently. Furthermore, the video data in each row can be retrieved at a rate rd . Retrieving an entire column takes prtd units of time. This is because columns are stored and retrieved sequentially one after another. From Equation 1, it follows that: p d d; (3) rt rd Therefore, in the time required to consume d bits of the video at a rate rd , an entire column can be retrieved from disk. As a result, while a portion in each row is being consumed at a rate rd , the next portion in each of the rows can be retrieved.
1

location scheme lays out video data on disk in an interleaved fashion such that retrieving the video data sequentially from disk enables portions at xed intervals in the video to be retrieved concurrently. Thus, the phase-constrained scheme eliminates seeks to random locations, and thereby enables the concurrent retrieval of the maximum number of phases p, while maintaining the bu er size per phase as a constant independent of the number of phases and disk latencies. Note however, that the time di erence between any two adjacent phases is xed. Let l be the length of a video in seconds. Thus, the storage occupied by the video is l rd bits. Suppose video data is read from disks in portions of size d. We shall assume that l rd is a multiple of p d:1 Our goal is to be able to support p concurrent phases of the video. In order to do this, we chop the video into p contiguous partitions. Thus, the video data can be visualized as a (p 1) vector, the concatenation of whose rows is the video itself and each row contains tc rd bits of video data, where l tc = p :

The length of the video can be modi ed by appending advertisements, etc. to the end of the video.

7

1 1 2 3

2

3

n

... ... ... . . .

p

...
d

Figure 2: The video viewed as a matrix.
1st column (1,1) (2,1) (p,1) (1,2) 2nd column (2,2) (p,2) (1,n) nth column (2,n) (p,n)

...
d

...

...

...

Figure 3: Placement of n columns of video matrix. If we assume that once the nth column has been retrieved, the disk head can be repositioned to the start of the device almost instantaneously, then we can show that p concurrent phases can be supported, the phase di erence between any two phases being a multiple of tc . The reason for this is that the time to retrieve data for the n columns sequentially from disk is n rpt d which is less than or equal to n dd = tc (due to Equation 3). As a result, every tc seconds the disk head can be r repositioned to the start. Thus, a new phase can be initiated every tc seconds. Furthermore, for every other concurrent phase, the last portion retrieved just before the disk head is repositioned, belongs to Column n. Since we assume that repositioning time is negligible, Column 1 can be retrieved immediately after Column n. Thus, since the portion following portion (i; n) in Column n, is portion (i + 1; 1) in Column 1, data for concurrent phases can be retrieved from disk at a rate rd. In Section 3.3, we present schemes that take into account repositioning time when retrieving data for p concurrent phases.

3.2 Bu ering
We now compute the bu ering requirements for our storage scheme. With every row of the video matrix, we associate a video bu er, into which consecutive portions in the row are retrieved. Each of the video bu ers is implemented as a circular bu er; that is, while writing into the bu er, if the 8

end is reached, then further bits are written at the beginning of the video bu er (similarly, while reading, if the end is reached, then subsequent bits are read from the beginning of the bu er). With the above circular storage scheme, every tnc seconds, consecutive columns of video data are retrieved from disk into video bu ers. The size of each bu er is 2d, one half of which is used to read in a portion of the video from disk, while d bits of the video are transmitted to viewers from the other half. Also, the number of video bu ers is p to store the p di erent portions of the video contained in a single column { the rst portion in a column is read into the rst video bu er, the second portion into the second video bu er and so on. Thus, in the scheme, initially, the p portions of the video in the rst column are read into the rst d bits of each of the corresponding video bu ers. Following this, the next p portions in the second column are read into the latter d bits of each of the corresponding video bu ers. Concurrently, the rst d bits from each of the video bu ers can be transmitted to viewers. Once the portions from the second column have been retrieved, the portions from the third column are retrieved into the rst d bits of the video bu ers and so on. Since consecutive portions of a video are retrieved every tnc seconds, consecutive portions of the video are retrieved into the bu er at a rate of rd : Thus, in the rst video bu er, the rst n portions of the video (from the rst row) are output at a rate of rd , while in the second, the next n portions (from the second row) are output and so on. Thus, data for p concurrent phases of the video can be retrieved by sequentially accessing the contents of consecutive video bu ers.

3.3 Repositioning
The storage technique we have presented thus far enables data to be retrieved continuously at a rate of rd under the assumption that once the nth column of the video is retrieved from disk, the disk head can be repositioned at the start almost instantaneously. However, in reality, this assumption does not hold. Below, we present techniques for retrieving data for p concurrent phases of the video if we were to relax this assumption. The basic problem is to retrieve data from the device at a rate of rd in light of the fact that no data can be transferred while the head is being repositioned at the start. A simple solution to this problem is to maintain another disk which stores the video exactly as stored by the rst disk and which takes over the function of the disk whose head is being repositioned. An alternate scheme that does not require the entire video to be duplicated on both disks can be employed if the minimum phase di erence tc is at least twice the repositioning time. The video data matrix is divided into two submatrices so that one submatrix contains the rst d n e columns 2 9

and the other submatrix, the remaining b n c columns of the original matrix, and each submatrix 2 is stored in column-major form on two disks with bandwidth rt : The rst submatrix is retrieved from the rst disk, and then the second submatrix is read from the other disk while the rst disk is repositioned. When the end of the data on the second disk is reached, the data is read from the rst disk and the second disk is repositioned. If the time it takes to reposition the disk to the start is low, in comparison to the time taken to read the entire video, as is the case for disks, then almost at any given instant one of the disks would be idle. To remedy this de ciency, in the following, we present a scheme that is more suitable for disks. In the scheme, we eliminate the additional disk by storing, for some m, the last m portions of the column-major form representation of the video in RAM so that after the rst lrd ? md portions have been retrieved from the disk into the video bu ers, repositioning of the head to the start is initiated. Furthermore, while the device is being repositioned, the last m portions of the video are retrieved into the video bu ers from RAM instead of the device. Once the head is repositioned and the last m portions have been retrieved into the video bu ers, the columns are once again loaded into the video bu ers from disk beginning with the rst column as described earlier in the section. For the above scheme to retrieve data for phases of the video continuously at a rate of rd ; we need the time to reposition the head to be less than or equal to the time to consume m portions of the video at a rate of rd ; that is,

m d t lat rd where tlat is the maximum disk latency. Thus, the total RAM required is md + 2dp. The cost of retrieving data for p concurrent phases of the video into the video bu ers using the disk in Example 1 and our storage allocation scheme can be computed as follows. Since the unit of retrieval from disks is a sector, whose size is typically 512 bytes, we can choose the portion size d to be any multiple of 512 bytes. We choose d to be 4096 bytes, a common page size in operating systems. Since the maximum number of concurrent phases for the disk is 53, the RAM required for the video bu ers is 4096 53 2 = 434 KB: Since the cost of the disk is $3000, if we use the additional disk to make up for repositioning time, the total storage cost for the system per video would be approximately $6021. On the other hand, if we use the latter scheme that uses RAM, due to the low value of tlat , the cost of RAM is negligible. Thus, the storage cost of the system per video would be $3021 as opposed to $62; 500 if the entire video were stored in RAM.
10

4 Implementation of VCR Operations
We now turn our attention to how VCR operations can be implemented in our basic architecture. We assume that videos are digitized and compressed using the widely used MPEG-1 video compression algorithm Gal91]. However, our scheme for the implementation of VCR operations is general and can be used even if di erent compression algorithms, transfer and playback rates are employed. The MPEG-1 video compression algorithm requires compressed video data to be retrieved at a rate of about rd = 1:5 Mbps in order to support the display of moving pictures at a rate of 30 frames per second. MPEG-1 compressed video is a sequence of Intraframe (I), Predicted (P) and Bidirectional (B) frames. I-frames are stand-alone frames and can be decoded independently of other frames. P-frames are coded with reference to the previous frame and thus can be decoded only if the previous frame is available, while a B-frame requires the closest I/P-frame preceding and following the B-frame for decoding. I-frames consume the most bandwidth, while B-frames consume the least (the ratio of the bandwidths consumed by the frames is 5:3:1). We refer to a sequence of frames beginning with an I-frame and ending with a P-frame as an independent sequence of frames. Thus, since an independent sequence of frames contains references for every B-frame in it, it can be decoded by an MPEG-1 decoder. The organization of frames in MPEG-1 is quite exible, the frequency of I-frames being a parameter to the MPEG-1 encoder. We shall assume that in MPEG-1 compressed videos stored on the VOD server, there are 2k +1 BBP frames between any two consecutive I-frames, where k is a positive integer (see Figure 4). In addition to I, B and P frames, there is a special instance of a P-frame, which is a constant frame and which we refer to as a Repeat (R) frame, with the following property: when an MPEG-1 decoder receives an R-frame immediately after it receives a P-frame or an R-frame, it outputs the same frame as the previous one output by it. Since the consumption rate of the MPEG-1 decoder may not be uniform (it could exceed or fall below 1.5 Mbps), a process at the viewer site continuously monitors the decoder bu er, discarding BBP frames immediately preceding an I-frame if the bu er over ows and inserting additional Rframes between P and I-frames in case the bu er under ows2. We now describe how the control operations begin, pause, fast-forward, rewind and resume for a video are executed with our basic storage architecture. As we described earlier, contiguous portions
2 We do not expect deletion and insertion of a few additional frames to seriously e ect the quality of the video 1 since each frame is displayed for only 30 th of a second.

11

...
I BBP BBP BBP I

Figure 4: A possible sequence of MPEG-1 frames. of the video are retrieved into p video bu ers at a rate rd . The rst n portions are retrieved into the rst video bu er, the next n into the second video bu er, and so on.

begin: The transmission of compressed video data to the viewer starts once the rst video

bu er contains the rst frame of the video. Portions of size d are transmitted to the user at a rate rd from the video bu er (wrapping around if necessary). After the i nth portion is transmitted, transmission of video data is resumed from the i + 1th video bu er. We refer to the video bu er that outputs the video data currently being transmitted to the viewer as the current video bu er. Since in the worst case, n d bits may need to be transmitted before the rst video bu er contains the rst frame of the video, the delay involved in the transmission of a video when a viewer issues a begin command, in the worst case, is the minimum phase di erence tc .

pause: Once a P-frame immediately preceding an I-frame is transmitted, subsequent frames
transmitted to the viewer are R-frames.

fast-forward: Beginning with the current video bu er, the following steps are executed.
1. Continue transmitting compressed video data normally until a P-frame is transmitted from the current video bu er and the next video bu er contains an I-frame. 2. Transmit video data beginning with the I-frame in the next video bu er. 3. Go to Step 1. Thus, during fast-forward, independent sequences of frames are transmitted, the number of bits skipped between any two successive sequences being approximately n d.

rewind: This operation is implemented in a similar fashion to the fast-forward operation

except that instead of jumping ahead to the following video bu er, jumps during transmission are made to the preceding video bu er. Thus, beginning with the current video bu er, the following steps are executed. 12

1. Continue transmitting compressed video data normally until a P-frame is transmitted from the current video bu er and the previous video bu er contains an I-frame. 2. Transmit video data beginning with the I-frame in the previous video bu er. 3. Go to Step 1.

resume: In case the previously issued command was either fast forward or rewind, bits are

continued to be transmitted normally from the current video bu er. If, however, the previous command was pause, then once the current video bu er contains the I-frame following the last P-frame transmitted, normal transmission of video data from the video bu er is resumed beginning with the I-frame. Thus, in the worst case, similar to the case of the begin operation, a viewer may experience a delay of tc seconds before transmission can be resumed after a pause operation.

Furthermore, the basic architecture enables the viewer to jump to any location in the video in tc seconds. During fast-forward and rewind, since independent sequences of frames are transmitted, the MPEG-1 decoder has no problems decoding transmitted data. Also, when switching from one video bu er to another, one of the video bu ers must contain an I-frame, while the other must contain a P-frame. However, this is not really a problem, since due to the high frequency of Pframes in the compressed video, it is very likely that every time a video bu er contains an I-frame, adjacent video bu ers would contain P-frames. Finally, in the extreme case, 30tc frames may be skipped for every IBBP sequence transmitted. Thus, fast-forward and rewind could give the e ect that the frames are displayed at approximately 7:5tc times their normal rate. We shall refer to the number of frames skipped during fast-forward and rewind as their granularity. For the disk in Example 1, tc for a 100 minute video is approximately 113 seconds. Thus, the worst case delay is 113 seconds when beginning or resuming the display of a video. Furthermore, the number of frames skipped when fast-forwarding and rewinding is 3390 (113 seconds of the video). By reducing the minimum phase di erence tc , we could provide better quality VOD service to viewers. We now show how multiple disks can be employed to reduce tc . Returning to Example 1, suppose that instead of using a single disk, we were to use an array of 5 disks. In this case, the bandwidth of the disk array increases ve-fold from 80 Mbps to 400 Mbps. The number of phases, p, increases from 53 to b 400 c = 266, and, therefore, the minimum phase di erence tc reduces from 1:5 6000 113 seconds to 266 or approximately 22 seconds. In this system, the worst case delay is 22 seconds and the number of frames skipped is 660 (22 seconds of the video). The storage cost of the system 13

would increase ve-fold, from $3021 to $15105; which is still less than the cost of storing the entire video in RAM (i.e., $62500). Although the basic service may be su cient for many viewers, there may be viewers who are willing to pay more for higher quality VOD service. Ideally, during fast-forward and rewind, we would like the 2k BBP frames between consecutive IBBP frames to be skipped (typically, the value of k ranges between 2 and 5). In the following sections, we individually address the following two issues. 1. Reduction of the granularity of fast-forward and rewind. 2. Elimination of the delay in resuming normal display after a pause operation.

5 Improving Granularity of Fast-Forward and Rewind
The granularity of fast-forward and rewind operations presented in Section 4 is dependent on the phase di erence tc. There are two possible approaches to reducing the number of bits skipped between two successive independent sequences of frames during fast-forward and rewind. We elaborate on both approaches in the following subsections.

5.1 Storing a Fast-Forward Version of the Video
A separate version of the video that is used to perform fast-forward and rewind operations is stored. Since we assume that there are 2k BBP sequences between any two consecutive IBBP sequences in the video, the fast-forward (FF) version is obtained from the compressed MPEG-1 video by omitting the 2k BBP sequences in between two consecutive IBBP sequences. Thus, the FF-version of the video contains only consecutive IBBP sequences of frames and thus, transmitting it to viewers at a rate of rd would result in an e ect that is similar to one of playing the video in fast-forward 1 mode3. The storage required for the FF-version of the video can be shown to be k+1 times the storage required for the video. Since the bandwidth requirements for I, P and B are in the ratio 5:3:1, assuming that a B-frame consumes a unit of storage, it follows that P and I frames consume 3 and 5 units of storage, respectively. Thus, since there are 2k + 1 consecutive BBP frame sequences between any two consecutive I-frames, and each BBP sequence consumes 5 units of storage, it can be shown that for every 10 + 10k units of the video (I frame followed by 2k + 1 BBP frames), the
Note that since only IBBP sequences are transmitted, it is possible that the rate at which the decoder consumes bits would increase beyond d However, the process at the viewer site can insert R-frames to ensure that the bu er never under ows.
3
r :

14

FF-version of it contains only 10 frames (I frame followed by a BBP frame sequence). Thus, it 1 follows that the FF-version of the video consumes k+1 times the storage consumed by the video.

5.1.1 Storing the Fast-Forward Version in RAM
One simple option is to store the entire FF-version of the video in RAM. This is more cost-e ective than the RAM-based architecture in which the entire video is stored in RAM since the FF-version of 1 the video occupies only k+1 times the storage occupied by the video. The operations fast-forward, rewind, and resume require the transmission of bits to switch between the video bu ers and the FF-version of the video. The various operations are implemented as follows (pause and resumption from pause mode is implemented as described in the previous section).

fast-forward: Frames are continued to be transmitted from the current video bu er until

a P-frame is transmitted. Once a P-frame is transmitted, the rst I-frame that follows the P-frame in the video is located in the FF-version of the video. Frames are continued to be transmitted at a rate of rd from the FF-version beginning with the I-frame.

is transmitted. Once a P-frame is transmitted, the rst I-frame that precedes the P-frame in the video is located in the FF-version of the video. The following steps are executed. 1. Transmit frames from the FF-version of the video beginning with the I-frame until a P-frame is transmitted. 2. Once the P-frame is transmitted, locate the I-frame in the FF-version that belongs to the IBBP sequence that immediately precedes the IBBP sequence just transmitted. 3. Go to Step 1.

rewind: In this case, frames are transmitted from the current video bu er until a P-frame

resume: Resumption of normal display from fast-forward and rewind is handled in a similar

fashion to resumption from pause. Once a P-frame is transmitted from the FF-version, until one of the video bu ers contains the rst I-frame in the video following the P-frame, Rframes are transmitted to the viewer. Normal transmission is resumed from the video bu er beginning with the I-frame.

15

5.1.2 Storing the Fast-Forward Version on Disk
An alternative to storing the FF-version of the video in RAM is to store it on disk using the phase-constrained allocation scheme described in Section 3 as we did for the video itself. Thus, in addition to video bu ers in which consecutive portions of a video are retrieved, an additional set of bu ers into which consecutive portions of the FF-version of the video are retrieved is maintained. We refer to these as FF-bu ers. The minimum phase di erence for the stored FF-version of the 1 video is tff ; which is approximately k+1 times smaller than the minimum phase di erence tc for the video. The number of portions, nff of size d in a row of the FF-version is tffd rd . (thus, there are 5 BBP sequences between any two consecutive I frames). The video consumes 1.125 GB of storage, while its FF-version requires 1:125 = 375 MB of storage space. Also, if the 3 FF-version of the video were to be stored on the disk described in Example 1 using the phaseconstrained scheme, then tff would be approximately 113 = 37 seconds. 2 3 There are three possible ways in which the fast-forward operation can be implemented. The simplest way of implementing the fast forward operation is to rst determine the FF-bu er containing frames closest to and following the frame being currently transmitted from the current video bu er. After a P-frame is transmitted from the current video bu er, frames are transmitted from the FF-bu er beginning with an I-frame. The number of bits between portions contained concurrently in any two consecutive FF-bu ers is nff d bits in the FF-version of the video. Thus, in the worst case, switching from a video bu er to a FF-bu er could result in approximately n d bits (tc seconds) of the video being skipped. However, once transmission is switched from the video bu er to the FF-bu er, 2k BBP sequences are skipped between any two consecutive IBBP sequences. A second approach is to continue transmitting from the current video bu er until a P-frame immediately preceding an I-frame is transmitted and then simply transmit R-frames until an FFbu er contains the I-frame that follows the P-frame in the video. In the worst case, this could result in the viewer's display being frozen for about tff seconds since the required I-frame may have just been transmitted from the FF-bu er and waiting for it to be retrieved into the FF-bu er again may result in a delay of tff seconds. It would be desirable if we could avoid freezing the viewer's display as well as skipping n d bits 16

Example 2: Consider a 100 minute video compressed using MPEG-1 and for which k = 2

of the video when switching from the video bu er to an FF-bu er. A third solution that achieves both is to simply continue transmitting frames normally from the video bu er until one of the FF-bu ers contains the rst I-frame in the video that follows the last P-frame transmitted. At this time, transmission of subsequent frames is carried out from the FF-bu ers beginning with the I-frame. In this case, however, in the worst case, the delay involved in switching from the video bu er to the FF-bu er could be greater than tff seconds since the rst I-frame following the last transmitted P-frame may have just been transmitted out of the FF-bu er. The I-frame is retrieved into the FF-bu er again after tff seconds. However, in that time, few more frames may have been transmitted to the viewer from the video bu er. As a result, in the worst case, before transmission of bits from the FF-bu er can begin, it may need to output nff d bits plus the number of bits of the FF-version of the video output by the viewer bu er before transmission switches to the FF-bu er. Thus, in order to compute the delay, td , involved in switching from the video bu er to the FF-bu er, in the worst case, we use the following equation.
d nff d + (rd+t1) rd td k In the above equation, rd td on the right hand side of the equation is the number of bits output from the FF-bu er in time td . The rst term on the left hand side is the number of bits that the FF-bu er must output before it outputs the same bit twice, and the second term is the number of additional bits it needs to output in order to catch up with the viewer bu er (the viewer bu er rd outputs rd td bits of video in time td or tkd+1 bits of the FF-version of the video since the FF-version 1 of the video is k+1 times the size of the video). Thus, in the worst case, the delay is

nff d (k + 1) : k rd For the video in Example 2, td is approximately 56:5 seconds. Thus, unlike the case in which the FF-version of the video is loaded into RAM in which a smooth transition to the fast-forward mode is possible without delay, in the disk based solution, the transition to fast-forward mode is either abrupt or could, in the worst case, result in a delay of at least tff seconds. The problem with storing an FF-version of the video on a disk is that the implementation of the rewind command is not possible using the FF-bu ers. The reason for this is that successive IBBP sequences of frames are retrieved into the FF-bu ers, while for rewind, once an IBBP sequence of frames is transmitted, the previous IBBP sequence of frames needs to be transmitted. Thus, for the purpose of supporting rewind, we store a di erent version of the video, which we refer to td
17

as the REW-version of the video, on the disk. The REW-version, like the FF-version, contains only IBBP sequences of frames except that the order of appearance of the IBBP sequences in the FF-version and the REW-version are reversed. Also, a separate set of bu ers is maintained into which consecutive portions of the REW-version of the video are retrieved, which we refer to as REW-bu ers. The minimum phase di erence for the REW-version of the video is also tff seconds. The alternatives described for the implementation of fast forward can also be used to implement rewind by switching to the REW-bu er instead of the FF-bu er. In addition, in the rst alternative, the REW-bu er containing frames closest to and preceding the frame being currently transmitted from the current video bu er is determined. In the second and third alternatives, instead of transmitting the rst I-frame in the video that follows the last P-frame transmitted from the FFbu er, the rst I-frame in the video that precedes the P-frame is transmitted from the REW-bu er. The number of bits skipped by the rst alternative and the worst case delay in the second alternative are as described for fast-forward. However, for the third alternative, the worst case time delay, td , can be shown to be d ( td nffk + 2)k + 1) : ( rd The reason for this is that, initially, there must exist a REW-bu er that, before outputting a maximum of nff d bits of the REW-version of the video, will output the I-frame required for switching transmission from the video bu er to the REW-bu er. However, since frames are continually transmitted to the viewer from the video bu er, in the worst case, only the di erence between nff d 1 and k+1 times the number of bits transmitted from the video bu er in time td are output from the t rd REW-bu er in time td (the viewer bu er outputs rd td bits of video in time td or kd+1 bits of the 1 REW-version of the video since the REW-version of the video is k+1 times the size of the video).
d nff d ? (rd+t1) rd td k For the video in Example 2, td is approximately 28 seconds. Thus, the worst-case switching time for REW is about half of that for FF. The resume operation is implemented similar to the case in which the entire FF-version was stored in RAM and may require the display to be frozen for tc seconds.

5.2 Bu er Based Solution
The schemes for implementing ne granularity fast-forward and rewind described in the previous subsection either require the entire FF-version of the video to be stored in RAM or resulted in 18

(1,1) (2,1) (3,1) (1,2) (2,2) (3,2) . . . Movie

... ... . . . ...

... ...

(p,1) (p,2) . . .

Column 1 Column 2 current movie buffer Movie Buffers

... . . . . . . ... (p,n) Column n

. . . (1,n) (2,n) (3,n) ...

Viewer Buffer k+1 Current Viewer Buffer k+1 (k+2) Viewer Buffer

Figure 5: Viewer Bu ers for Fast-forward and Rewind an abruptness or delay in switching to fast-forward/rewind mode. In this subsection, we present a scheme for supporting ne-granularity fast-forward and rewind that does not require the entire FF-version of the video to be stored (in RAM or on disk) and results in a smooth transition to fast-forward and rewind mode. The scheme is especially suitable in case a few number of viewers are watching the video. Informally, the basic idea underlying the scheme is that, at all times, if we were to bu er n d bits following, and n d bits of the FF-version of the video preceding the current bit being transmitted, then it is possible to support both ne-granularity fast forward and rewind without any delays. It is necessary to bu er bits since video bu ers output the video at a rate of rd ; and during fastforward/rewind, the FF-version of the video, and not the video itself needs to be transmitted at rd: The reason that it su ces to bu er n d bits of FF-version of the video following the current bit being transmitted is that when a viewer issues the fast-forward command, in the time that the bu ered n d bits of the FF-version of the video are transmitted, n d bits are output by each video bu er. Thus, the n d + 1th bit of FF-version of the video would be output by a video bu er and by bu ering it, its availability for transmission once n d bits are transmitted can be ensured. Using a similar argument, it can be shown that bu ering n d bits preceding the current bit being transmitted su ces to support continuous rewind. Note that bu ering x < n d bits of the FF-version of the video preceding or following the current bit being transmitted, could result in hiccups due to the unavailability of bits during fast-forward/rewind. The reason for this is that 19

once x bits of FF-version of the video have been transmitted, the x + 1th bit may not be available since x < n d and thus, none of the video bu ers may have output it while the x bits were being transmitted. In order to bu er the required bits of the FF-version of the video, 2k+4 viewer bu ers are maintained per viewer watching the video (see Figure 5). A viewer bu er is used to store the FF-version of the video output by a video bu er and has a size nd?jIBBP j + jIBBP j which is the k+1 maximum number of bits of FF-version, that a video bu er can output (jIBBP j is the storage required for an IBBP sequence). The bu ers are arranged in a circular fashion and each bu er is a circular bu er. One viewer bu er stores the FF-version of the video output from the current video bu er. k + 1 viewer bu ers following the bu er are used to store n d bits of the FF-version of the video output from the k + 1 video bu ers following the current video bu er, while k + 1 viewer bu ers preceding the bu er are used to store n d bits of the FF-version of the video output from the k + 1 video bu ers preceding the current video bu er. The remaining viewer bu er is used to load the FF-version of the video in case the viewer issues a fast-forward or rewind command. With every viewer bu er are associated variables start buf and end buf. start buf stores the o set from the start of the bu er of the bit in the viewer bu er with the lowest position in the video. Variable end buf stores the o set from the start of the bu er, of the last bit contained in the bu er. An additional variable cur buf is used to store the current viewer bu er. During normal display and during pause, cur buf is the viewer bu er containing the FF-version of the video output by the current video bu er, and during fast forward and rewind mode, cur buf is the viewer bu er from which bits are transmitted. The FF-version of a video is loaded into a viewer bu er from a single video bu er. Consecutive bits output from the video bu er and belonging to only IBBP sequences are simply copied into the viewer bu er beginning from the start of the bu er. When a bit whose position in the video is the smallest among all the bits (belonging to IBBP sequences and) output by the video bu er is copied into the viewer bu er, start buf for the bu er is set equal to the o set of the bit from the beginning of the viewer bu er. Bits are continued to be copied into the viewer bu er until it contains all the bits output by the video bu er that belong to IBBP sequences. end buf for the bu er is set to the o set of the last bit from the start of the bu er. During fast-forward and rewind, the FF-version of the video is transmitted from the viewer bu ers at a rate of rd : While transmitting data from a viewer bu er, if end buf is reached and start buf for the bu er is 0, then subsequent bits are transmitted beginning with start buf in the 20

next viewer bu er. If, on the other hand, start buf for the bu er is not 0, then subsequent bits are retrieved from the start of the bu er. Once one or more bits have been retrieved from a bu er, if the next bit to be retrieved from the bu er is at o set start buf from the beginning of the bu er, then subsequent bits are retrieved from start buf in the next bu er. Traversing the viewer bu ers in the reverse direction (during rewind) is carried out as follows. If the beginning of the bu er is reached and start buf is not 0, then subsequent bits are traversed beginning with end buf. On the other hand, if the o set of the current bit from the start of the bu er is start buf, then subsequent bits are accessed from the previous viewer bu er, beginning with
end buf, if start buf for the bu er is 0, and start buf-1, otherwise.

The various operations are implemented as follows.

begin: 2k + 4 viewer bu ers are allocated for the viewer and cur buf is set to one of them

(that is arbitrarily chosen). cur buf and the k viewer bu ers following it are loaded with the FF-version of the video from the rst k + 1 video bu ers. Once the k + 1 viewer bu ers are loaded, and the rst video bu er contains the rst frame of the video, video data is transmitted to the viewer from the rst video bu er and concurrently the k + 1th viewer bu er following cur buf is loaded from the k + 2nd video bu er. During normal transmission of bits to the viewer, when transmission switches from the current video bu er to the next, cur buf is set to the next viewer bu er and the k +1th viewer bu er following cur buf is begun to be loaded from the k + 1th video bu er following the current video bu er. Furthermore, during normal display, loading of viewer bu ers is restricted to only cur buf, the k + 1 viewer bu ers following cur buf and the k +1 viewer bu ers preceding cur buf. The maximum latency to start viewing the video is less than 2 tc: video bu er, loading of the k +2nd viewer bu er following cur buf is initiated from the k +2nd video bu er following the current video bu er. Concurrently, the I-frame following the Pframe is located in cur buf and subsequent bits are transmitted from cur buf beginning with the I-frame. During fast-forward, every time transmission of bits switches from a viewer bu er to the next bu er (cur buf is set to the next bu er), the following steps are performed. 21

fast-forward: Once a P-frame immediately preceding an I-frame is transmitted from the

1. The loading of the k + 2nd viewer bu er preceding cur buf from the k + 2nd video bu er preceding the current video bu er is terminated. 2. The k + 2nd viewer bu er following cur buf is loaded from the k + 2nd video bu er following the current video bu er. loading of the k +2nd viewer bu er preceding cur buf is initiated from the k +2nd video bu er preceding the current video bu er. Concurrently, the I-frame belonging to the sequence is located in cur buf and sequences of IBBP frames are transmitted at a rate of rd in the reverse order of their occurrence in the viewer bu ers. During rewind, once every bit from a viewer bu er has been transmitted and transmission switches to the previous viewer bu er (cur buf is set to the previous bu er), the following steps are performed. 1. The loading of the k + 2nd viewer bu er following cur buf from the k + 2nd video bu er following the current video bu er is terminated. 2. The k + 2nd viewer bu er preceding cur buf is loaded from the k + 2nd video bu er preceding the current video bu er.

rewind: Once a P-frame belonging to an IBBP sequence is transmitted from the video bu er,

pause: In this case, bits are transmitted normally from the video bu ers until a P-frame

preceding an I-frame is transmitted. Once the P-frame is transmitted, subsequent frames transmitted to the viewer are R-frames (loading of viewer bu ers is continued as before the transmission of R-frames). frame following the last P-frame transmitted, transmission of video data to viewers is resumed at a rate of rd : Also, all viewer bu ers that were being loaded during the pause operation, are continued to be loaded. In case the previous command was rewind or fast-forward, bits are transmitted from the viewer bu ers until a P-frame is transmitted. Once the P-frame is transmitted, until a video bu er contains the I-frame following the P-frame, subsequent frames transmitted to the viewer are R-frames. During the transmission of R-frames, loading of viewer bu ers is restricted to the k + 1 bu ers following and the k + 1 bu ers preceding cur buf. Once a video bu er contains the I-frame, normal transmission is resumed from the video bu er beginning with the I-frame. 22

resume: In case the previous command was a pause, once the video bu er contains the I-

We now show that with the above scheme, during fast-forward and rewind, data to be transmitted is always available in the viewer bu er. The primary reason for this is that during normal transmission of bits to the viewer, every time transmission switches to the next video bu er, loading from the k + 1th video bu er following the next video bu er is begun. Thus, in case the viewer issues the fast-forward command, FF-version bits from the next video bu er and k video bu ers following it need to be transmitted before FF-version bits from the k + 1th video bu er will be needed. Thus, since the number of FF-version bits in k + 1 video bu ers is (k+1) nd = n d, in the k+1 time that n d FF-version bits are transmitted from the k + 1 viewer bu ers, all the FF-version bits from the k + 1th video bu er are loaded into the appropriate viewer bu er. Similarly, since once transmission from viewer bu ers is begun, every time transmission switches to the next viewer bu er, loading of the k + 2nd viewer bu er following the next viewer bu er is begun. Thus, during fast-forward, data to be transmitted is always available in the viewer bu ers. Also, since k +1 viewer bu ers are used to store the FF-version bits from the k +1 video bu ers preceeding the current video bu er, in case the viewer issues the rewind command, in the time taken to transmit the n d FF-version bits contained in the k + 1 preceeding bu ers, the k + 2nd preceeding viewer bu er can be completely loaded from the appropriate video bu er. Thus, during rewind, data to be transmitted is always available in the viewer bu ers. We now compute the additional bu er requirements per viewer incurred by the scheme for the video in Example 2. Recall that k = 2, tc 113 seconds and n d = tc rd = 170 Mb. Thus, the total bu er requirements for the 2k + 4 viewer bu ers are approximately 456 Mb which is the storage required for about 5 minutes of the video.

6 Reducing Response Time
The schemes presented for pause in sections 4 and 5, and those for ne-granularity fast-forward and rewind in the previous section all require a video bu er to contain the rst I-frame in the video following the last P-frame transmitted before normal transmission of bits to the viewer can be resumed. In the worst case, this could result in a delay of tc seconds which, to some viewers, may be unacceptable. In the following subsections, we rst present a scheme that can be used in conjunction with all the schemes presented in sections 4 and 5 in order to eliminate the delay associated with only the pause operation. We then present a scheme that eliminates the delay associated with all of the operations - pause, fast-forward and rewind, and that also provides smooth ne granularity fast-forward and rewind operations. The schemes are built on the scheme 23

presented in Section 4 that ensures video bu ers output continuous portions of the video at a rate of rd : Both schemes can be used to provide, at an additional cost, enhanced VOD services to few viewers since they require RAM bu ers to be allocated on a per viewer basis.

6.1 Pause
For the pause operation, our scheme requires a circular viewer bu er to be maintained per user. The idea is to store in the viewer bu er, bits following the last bit transmitted before pause so that subsequent bits can be transmitted from the viewer bu er (instead of the video bu er) without delay when the viewer issues the resume command. If immediate resumption of normal transmission of bits from pause mode is to be supported, then the size of the viewer bu er required must be at least n d. The reason for this is that if the size of the bu er is x, where x < n d, then if the viewer issues a pause command, only x bits following the last bit transmitted can be bu ered. Thus, if the viewer were to issue the resume command when the x + 1st bit was output by the video bu er, it would not be possible to bu er the x + 1st bit. Thus, it would not be possible to transmit the x + 1st bit to the viewer, since x < n d and the bit needs to be transmitted after x bits have been transmitted, but is not output in the video bu er again until n d bits have been transmitted. On the other hand, if the size of the viewer bu er is n d, then when the viewer resumes after a pause, some video bu er must output bits contained in the bu er and it can be used to replenish the bits consumed from the viewer bu er. We now describe how the viewer bu er can be used to implement pause and resume. With every viewer bu er are associated variables start buf, num bits and next pos. start buf stores the o set from the start of the viewer bu er, of the next bit to be transmitted to the viewer. Also, num bits stores the number of untransmitted bits contained in the bu er, while next pos stores the position in the video of the next bit to be retrieved into the viewer bu er. Furthermore, at any time, x bits output by a video bu er are retrieved into the viewer bu er at o set ((start buf + num bits) mod nd) if the following two conditions hold. 1. x nd ? num bits. 2. The position in the video of the rst among the x consecutive bits is next pos.
num bits and next pos are incremented by x. Also, x bits are transmitted from the viewer bu er beginning with start buf, if x num bits. num bits is decremented by x and start buf is set to ((start buf + x) mod nd).

24

frames transmitted to the viewer are R-frames. In addition, if bits were being transmitted from a video bu er, then start buf and num bits are both set to 0 and next pos is set to the position in the video of the next I-frame to be transmitted.

pause: Once a P-frame that is immediately followed by an I-frame is transmitted, subsequent

resume: Bits are transmitted to viewers from the viewer bu er beginning with start buf.
The above described scheme for pause and resume can be used in conjunction with the schemes for fast-forward and rewind described in the previous two sections. In the schemes, implementations of fast-forward and rewind stay the same except that in case bits were being transmitted from the viewer bu er when the commands were issued, transmission of bits switches from the viewer bu er to a video bu er (in Section 4), RAM, an FF or a REW bu er (in Section 5.1), or a viewer bu er storing FF-version of the video (Section 5.2). Furthermore, while bits are being transmitted from the viewer bu er, in the scheme presented in Section 5.2, cur buf is the viewer bu er containing the FF-version of the video from the video bu er that output the bits being transmitted. The scheme ensures that after a pause, transmission can be resumed without delay from the viewer bu er. The reason for this is that bits following the last bit transmitted (transmission of bits is suspended due to the pause), are retrieved into the viewer bu er from the video bu er. In case transmission is resumed before the viewer bu er lls up, then bits will be transmitted from the viewer bu er and concurrently bits will be retrieved into the viewer bu er from the video bu ers. In the case that transmission from the viewer bu er is resumed after it is full, some video bu er outputs the bit following the last bit in the viewer bu er before the n d bits in the viewer bu er can be transmitted. Bits are then retrieved into the viewer bu er from that video bu er concurrently with the transmission of bits from the viewer bu er. The scheme requires a bu er of size n d per viewer and thus, for the video in Example 2, the additional bu er space required would be 170 Mb.

6.2 Fast-Forward and Rewind
In this subsection, we propose a comprehensive scheme that in addition to eliminating the response time for pause, fast forward and rewind, also provides ne granularity fast-forward and rewind. The scheme requires (k + 1)n d bits of the video preceding as well as following the current bit being transmitted to be bu ered in order to support continuous fast-forward and rewind. The basic idea is similar to that presented in Section 5.2. In the time that FF-version of video contained in the bu ered (k + 1)n d bits can be transmitted, during fast-forward/rewind, the (k + 1)nd + 1th 25

bit is output by a video bu er (since typically, (k + 1)n d bits of the video contain n d bits of the FF-version of the video, n d bits are output by a video bu er). Unlike the scheme presented in Section 5.2, the scheme we present in this section eliminates the delay involved in resuming normal transmission after a fast-forward/rewind operation. It does this by bu ering all bits of the video instead of only the FF-version bits of the video. Our scheme requires 2k + 4 circular viewer bu ers, each of size n d and arranged in a circular fashion, to be maintained per viewer. Bits are always transmitted to viewers from viewer bu ers, and a viewer bu er is used to store bits output by a video bu er. k +1 bu ers each are used to store the (k +1)n d bits following as well as preceding the current bit being transmitted. One bu er stores the bits output by the current video bu er, while another is used to store bits following/preceding the bu ered (k + 1)n d bits in case the viewer issues a fast-forward/rewind command. With every viewer bu er is associated a variable start buf that stores the o set, from the start of the bu er, of the bit in the bu er with the lowest position in the video. Bits are loaded into a viewer bu er from a single video bu er. Loading of bits from a video bu er into a viewer bu er can be initiated at any time and is carried out by copying bits output by the video bu er into consecutive bits in the viewer bu er beginning from the start of the viewer bu er. When the bit whose position in the video is the lowest among all the bits that are output from the video bu er is copied into the viewer bu er, start buf for the viewer bu er is set to the o set of the bit in the viewer bu er. The loading of a viewer bu er from a video bu er is terminated once the end of the viewer bu er is reached. During normal display, fast-forward and rewind, bits are transmitted to viewers from one of the viewer bu ers. Variable cur buf stores the current viewer bu er from which bits are being transmitted. While traversing/transmitting from cur buf, if one or more bits have been transmitted from the viewer bu er and the next bit to be transmitted/accessed is at o set start buf, then subsequent bits are transmitted from start buf in the next viewer bu er and cur buf is set to it. When traversing bits in the reverse direction from the viewer bu er, if the o set of the last bit accessed is start buf, then subsequent bits are accessed beginning from the end of the preceding viewer bu er if start buf for it is 0, else bits are accessed beginning with start buf-1. The various operations are implemented as described below.

begin: 2k + 4 circular viewer bu ers are allocated for the viewer, and cur buf is set to one of
26

them. cur buf and k viewer bu ers following it are loaded from the rst k + 1 video bu ers,

respectively. Once the k + 1 viewer bu ers are loaded, and the rst video bu er contains the rst frame, transmission of video data is initiated from cur buf beginning with start buf. Concurrently, the k + 1th viewer bu er following cur buf is loaded from the k + 2nd video bu er. During normal display, when transmission switches from a viewer bu er to another, loading of the k + 1th viewer bu er following cur buf is initiated from the k + 1th video bu er following the current video bu er. Also, during normal display, loading of viewer bu ers from video bu ers is restricted to cur buf, the k + 1 bu ers following cur buf and the k + 1 bu ers preceding cur buf.

fast-forward: Normal transmission of bits from the viewer bu ers is continued until a P-

frame immediately preceding an I-frame is transmitted. Once the P-frame is transmitted, the loading of the k + 2nd viewer bu er following cur buf is initiated from the k + 2nd video bu er following the current video bu er. Concurrently, beginning with the I-frame, consecutive IBBP frames are transmitted from the viewer bu ers at a rate of rd : Finally, every time the transmission of bits switches from one viewer bu er to the next, 1. The loading of the k + 2nd viewer bu er preceding cur buf from the k + 2nd video bu er preceding the current video bu er is terminated. 2. The loading of the k + 2nd viewer bu er following cur buf from the k + 2nd video bu er following the current video bu er is initiated.

rewind: Normal transmission of bits from the viewer bu er is continued until a P-frame
belonging to an IBBP sequence is transmitted. Once the P-frame is transmitted, the loading of the k +2nd viewer bu er preceding cur buf is initiated from the k +2nd video bu er preceding the current video bu er. Concurrently, beginning with the IBBP sequence, preceding IBBP sequences are transmitted from the viewer bu ers in the reverse order of their occurrence in the video. Finally, every time the transmission of IBBP sequences from a viewer bu er is completed and transmission of bits shifts to a previous viewer bu er,

1. The loading of the k + 2nd viewer bu er following cur buf from the k + 2nd video bu er following the current video bu er is terminated. 2. The loading of the k + 2nd viewer bu er preceding cur buf from the k + 2nd video bu er preceding the current video bu er is initiated. 27

pause: The transmission of data from viewer bu ers is continued until a P-frame immediately preceding an I-frame is transmitted. Once the P-frame is transmitted, R-frames are transmitted to the viewer and transmission of bits from viewer bu ers is stopped. Loading of data during pause is continued only in the k + 1 viewer bu ers following and the k + 1 viewer bu ers preceding cur buf.

resume: If the last command was a pause, then transmission of R-frames is stopped and
normal transmission of bits to the viewer is resumed with the I-frame following the last Pframe transmitted from the viewer bu er. On the other hand, if the last command was a fast-forward or rewind, then normal transmission of bits from viewer bu ers is resumed.

For the video and disk in Example 2, since k = 2 and n d = 170 Mb, the total bu er requirements are (2k + 4)n d or 1.36 Gb which is almost the storage required by 15 minutes of the movie. The bu er requirements can be reduced by employing multiple disks. For example, if we employed an array with ve disks, then tc reduces to 22 seconds and thus, nd = tc rd = 33 Mb. As a result, the total bu er requirements become 264 Mb which is the storage required by about 3 minutes of the video.

7 Multiple Videos and Disks
In this section, we show how the phase-constrained allocation scheme can be extended to store multiple videos with di erent rate requirements. Also, we show how we can use multiple disks in order to support a larger number of concurrent phases. VCR operations for the schemes presented in this section are not described, and can be implemented as described in previous sections.

7.1 Multiple Videos
Generalizing the phase-constrained scheme to store multiple videos with identical rate requirements rd is fairly trivial. The various videos are concatenated to form a single \super video". The super video is then stored using the phase-constrained scheme. Thus, at any given time, data for p phases is retrieved; the phases could be for di erent videos in the super video. Furthermore, if the length l of the super video is l seconds, then for every video, a phase is begun every p seconds. In a number of cases, videos may be compressed using di erent compression algorithms and may thus have di erent transfer requirements. For example, videos compressed using the MPEG-1 standard require a transfer rate of about 1.5 Mbps. On the other hand, for videos compressed using 28

MPEG-2, the transfer rate varies between 3 Mbps and 12 Mbps. In case videos have di erent rates, the maximum number of concurrent phases that can be supported at any given time depends on the transfer rates of videos being retrieved. Furthermore, for the videos, interleaving xed size portions of size d on disk as is done in Section 3.1 does not work. The reason for this is that in the time to retrieve subsequent portions of size d for concurrent phases, phases with higher transfer rates may starve while those with lower transfer rates may have surplus bits, thus resulting in higher bu er requirements. In this section, we show how the phase-constrained allocation scheme can be extended to handle videos with varying rates. Let t be an arbitrarily small amount such that t ri is a multiple of the unit of retrieval from disk. The disk is viewed as a sequence of blocks of size t rt . Let the videos be V1 , V2 , : : :, Vm with rates r1 ; : : : ; rm , r1 r2 rm , and lengths l1 ; : : : ; lm seconds, respectively. For every video Vi , consecutive portions of size t ri are assigned to consecutive disk blocks. An upper bound on the number of disk blocks q required to store the videos is computed as follows. Let rmax = maxfr1 ; : : : ; rm g. The number of portions that can be stored in a block is t rt at least b t rmax c. Thus, since video Vi contains at most d lti e portions, the total number of blocks required, q, can be at most
m X qmax = d( b r1t c d lti e)e (4) rmax i=1 The algorithm for assigning portions of videos to blocks, referred to as the PVB algorithm, is as follows. Variables i, j and k are used to keep track of the portions, videos and blocks respectively. Initially, i = 1; j = 1 and k = 1. Also, q = qmax .

1. For video Vj , assign the ith portion of size t rj to block k. 2. (a) If k = q, then k = 1. Else, k = k + 1. (b) If i is the last portion of video Vj , then set j = j + 1, i = 1. Else, set i = i + 1. (c) If j > m, exit. Else, go to Step 1. Thus, beginning with block 1 on the disk and portion 1 of video V1 , consecutive portions of Vj of size t rj are stored in consecutive blocks. After a portion is stored in block q, the next portion is stored in block 1. Also, after the last portion of a video Vj is stored in a block, the rst portion of video Vj +1 is stored in the next block. The algorithm terminates once the last portion of video Vm is stored. 29

Note that since q = qmax , the number of portions assigned to a block by the above algorithm is rt at most b rmax c. As a result, the sum of all the portions assigned to a block does not exceed its size t rt . It can be shown that by sequentially reading the q blocks from disk, data for video Vi can be retrieved at a rate ri . The reason for this is that the time to retrieve an entire block from disk is t (since the size of the block is t rt ). Also, the time to consume a portion of size t ri at rate ri is t. Thus, in the time that it takes to consume a portion of size t ri , the next block containing the next portion can be retrieved from disk. rt The portions contained in every block are retrieved into b rmax c circular bu ers, each of size 2 t rmax ; the rst portion is retrieved into the rst bu er, the second portion into the second bu er, and so on. Repositioning the disk head after the q blocks are read is handled as described in Section 3.3 by storing an appropriate number of blocks at the end in RAM. Note that the value of qmax in Equation 4 is based on the pessimistic assumption that the rt number of portions per block is b rmax c. However, in reality, since certain videos may have lower rt transfer rates than rmax , it may be possible to store more than b rmax c portions per block, and thus reduce the number of blocks required to store the videos. Thus, by assigning to q a value smaller than qmax in the PVB algorithm, it would be possible to support a larger number of phases concurrently and begin phases of a video more frequently (since the time to retrieve q blocks from disk is q t, a phase of a video is begun every q t seconds). The number of bu ers of size 2 t rmax required is the maximum number of portions assigned to a block by the PVB algorithm. In the following, we use binary search to e ciently compute qacc, a more accurate value (than qmax) for q in the PVB algorithm. The scheme uses two variables { Qmin and Qmax . Qmax is Pm initially set to qmax , while Qmin is set to b i=1r(tli ri ) c, which is a lower bound on the number of t blocks required to store the videos (li ri is the length in bits of video Vi ). Thus, qacc , the minimum number of blocks required to store the videos lies between Qmin and Qmax . In the following, we use binary search in order to generate possible values for qacc between Qmin and Qmax , and for each of the generated values of qacc, check if the videos can be stored in qacc blocks using the PVB algorithm. 1. If Qmax Qmin , then set qacc to Qmax and exit. 2. Assign portions of videos to blocks using the PVB algorithm with q = b Qmin +Qmax c instead 2 of qmax . 30

3. If for every block, the sum of portions assigned to it does not exceed its size t rt , then set Qmax equal to b Qmin +Qmax c. Else, set Qmin equal to b Qmin +Qmax c + 1. Go to Step 1. 2 2 In the above procedure, if it is determined that the videos cannot be stored in b Qmin +Qmax c 2 Qmin +Qmax c + 1, else Q Qmin +Qmax c. Thus, always, q , blocks, then Qmin is set to b max is set to b acc 2 2 the minimum number of blocks required to store the videos lies between Qmin and Qmax . Since if Qmin 6= Qmax , then b Qmin +Qmax c < Qmax and b Qmin +Qmax c + 1 > Qmin , during each iteration 2 2 of the procedure, Qmax ? Qmin decreases and nally, when Qmax = Qmin , Qmax is the minimum number of blocks required to store the videos.

7.2 Multiple Disks
VOD servers that provide support for hundreds of videos need to rely on several disks to store the videos. Multiple disks may also be used to provide support for a large number of phases concurrently using schemes presented in this section. Let the videos to be stored be V1 ; : : : ; Vm , and let there be n disks, each with a transfer rate of rt . The simplest scheme is to treat the multiple disks as a single logical disk whose transfer rate is n rt , the sum of the transfer rates of all the disks. To do so, each block is striped across the n disks and retrieved in parallel by the n disks. qacc can be computed as described earlier using block size t n rt (instead of t rt ) and for each video Vi , portions can then be assigned to the q blocks of size t n rt using the PVB algorithm with q = qacc. A drawback with the above approach is that in case a single disk were to fail, data for none of the blocks can be retrieved since every block is striped across the n disks GBLWP94]. Also, the number of portions assigned to each of the q blocks is uniform, which could result in storage space in disk blocks being wasted. The nal scheme we present alleviates both of the above problems by q storing portions of videos using the PVB algorithm in n blocks of size t rt on each disk (q can be set to d qacc e n, where qacc is computed as described earlier assuming a block size of t rt ). Beginning n with portion 1 of video V1 and block 1 on disk 1, consecutive portions of videos are assigned to the q n consecutive blocks on disk 1 using the PVB algorithm. If assigning a portion to a block on disk i causes the sum of the portions in the block to exceed t rt , then the portion is assigned to block 1 on disk i + 1, and successive portions are allocated to successive blocks on disk i + 1 using the PVB algorithm. If i = n, then it is not possible to store the videos in the q blocks. The number of portions assigned to blocks on a single disk is uniform; however, blocks on di erent disks can contain di erent numbers of portions. As a result, fewer than d qacc e n blocks n 31

may su ce to store the videos. An accurate value for q (which is also a multiple of n) can be computed using binary search as follows. Initially, Qmax is set to the smallest integer that is greater than or equal to qmax and that is a multiple of n. Similarly, Qmin is set to the largest integer that Pm is less than or equal to b i=1r(tli ri ) c, and that is a multiple of n. Note that the minimum value of t q required to store the videos lies between Qmin and Qmax . The following steps are repeated in order to determine the minimum value. 1. If Qmax Qmin , then return Qmax .
Q 2. Set q equal to b Qmin2+n max c n.

3. If the videos can be stored in the q blocks using the above scheme, then set Qmax to q. Else, set Qmin to q + n. Go to Step 1. In the above procedure, the values of Qmin and Qmax are updated in a manner such that the minimum value of q required to store the videos lies between Qmin and Qmax , and Qmin and Qmax are always multiples of n. Furthermore, if Qmin 6= Qmax , then Qmin b Qmin2+nQmax c n < Qmax , and so with every iteration Qmax ? Qmin decreases, and nally, when Qmax = Qmin , Qmax is the minimum value of q required to store the videos.

8 Related Work
A number of storage schemes for continuous retrieval of video and audio data have been proposed in the literature AOG92, RV91, RV93, GC92, YSB+ 89, GR93, GS93, BGMJ94, TPBG93, RW94, VGG94, CKY93, LS93, ORS95, ORSM95, CL93, DVV94]. However, in every one of the proposed schemes, except for DVV94], video data is separately retrieved for each request and is not shared among requests as is done by out schemes. In addition, every one of the schemes incurs disk latency overhead when servicing requests. The phase-constrained scheme, on the other hand, eliminates the disk latency overhead and thus, utilizes the disk bandwidth e ectively while keeping bu er requirements low. Finally, we are not aware of work on the implementation of VCR operations that is as detailed as the schemes we have presented in this paper. In DVV94], the notion of instants that are similar to phases and created dynamically is introduced. However, the issue of retrieving data for the instants from disks is not addressed by the authors. Among the other proposed schemes, AOG92, RV91, GC92, RW94, VGG94, CKY93, CL93, LS93, ORS95] address the problem of satisfying multiple concurrent requests for the retrieval 32

of multimedia objects residing on a disk. These schemes are similar in spirit to the contiguous allocation scheme that we presented in Section 3.1.1. In each of the schemes, concurrent requests are serviced in rounds retrieving successive portions of multimedia objects and performing multiple seeks in each round. Thus, the schemes are unsuitable for handling large number of requests concurrently. In fact, admission control tests based on computed bu er requirements for multiple requests are employed in order to determine the feasibility of additional requests with available resources. However, unlike our scheme, which is speci cally tailored for VOD environments, the schemes in AOG92, RV91, GC92, RW94, VGG94, CKY93, CL93, LS93, ORS95] can be used to concurrently retrieve arbitrary multimedia objects residing on disk. In addition, schemes proposed in RW94, CKY93, ORS95] order requests in order to reduce seek latency, while in VGG94], the authors propose a greedy disk scheduling algorithm for servicing requests that simultaneously minimizes (but does not eliminate) both seek time and rotational latency. The schemes in ORS95] eliminate the impact of rotational latency, but still incur seek latency. In order to reduce bu er requirements, an audio record is stored on optical disk as a sequence of data blocks separated by gaps in YSB+ 89]. Furthermore, in order to save disk space, the authors derive conditions for merging di erent audio records. In RV93], similar to YSB+ 89], the authors de ne an interleaved storage organization for multimedia data that permits the merging of time-dependent multimedia objects for e cient disk space utilization. However, they adopt a weaker condition for merging di erent media strands, a consequence of which is an increase in the read-ahead and bu ering requirements. In GR93], the authors use parallelism in order to support the display of high resolution video data that have high bandwidth requirements. In order to make up for the low I/O bandwidths of current disk technology, a multimedia object is declustered across several disk drives, and the aggregate bandwidth of multiple disks is utilized. In order to minimize the percentage of disk bandwidth that is wasted, in BGMJ94], the authors propose a technique referred to as staggered striping that permits two consecutive subobjects of a multimedia object to overlap on disk.

9 Concluding Remarks
We have proposed a low cost architecture for a video on demand (VOD) server. In our architecture, the currently viewed videos are stored on inexpensive disks. We proposed a novel storage allocation scheme that enables multiple di erent portions of a video to be concurrently retrieved from disk. We also extended the scheme to store videos with varying rates on multiple disks. Since the scheme 33

eliminates random disk head seeks, it requires only small portions of the video currently being viewed to be bu ered in RAM. We showed how VCR operations could be implemented in our basic architecture. We also showed how the quality of VOD services could be improved by allocating additional RAM bu ers per viewer. Thus, basic VOD services can be provided to all viewers at low cost by the basic architecture, and superior quality services can be provided on a per viewer basis at an extra cost by allocating additional bu ers.

Acknowledgments: We would like to thank Kim Mathews and Eric Petajan for discussions that
helped us understand details about MPEG-1.

References
AOG92] D. P. Anderson, Y. Osawa, and R. Govindan. A le system for continuous media. ACM Transactions on Computer Systems, 10(4):311{337, November 1992. BGMJ94] S. Berson, S. Ghandeharizadeh, R. Muntz, and X. Ju. Staggered striping in multimedia information systems. In Proceedings of ACM-SIGMOD 1994 International Conference on Management of Data, Minneapolis, Minnesota, pages 79{90, May 1994. CKY93] M. S. Chen, D. D. Kandlur, and P. S. Yu. Optimization of the grouped sweeping scheduling (gss) with heterogeneous multimedia streams. In Proceedings of ACM Multimedia, Anaheim, CA, pages 235{242, August 1993. CL93] H. J. Chen and T. D. C. Little. Physical storage organizations for time-dependent data. In Foundations of Data Organization and Algorithms, Chicago, Illinois, pages 19{34. SpringerVerlag, October 1993. DVV94] D. Deloddere, W. Verbiest, and H. Verhille. Interactive video on demand. IEEE Communications Magazine, 32(5):82{90, May 1994. Gal91] D. Gall. MPEG: A video compression standard for multimedia applications. Communications of the ACM, 34(4):46{58, April 1991. GBLWP94] G. R. Ganger, R. Y. Hou B. L. Worthington, and Y. N. Patt. Disk arrays: High-performance, high-reliability storage subsystems. Computer, 27(3):30{36, March 1994. GC92] J. Gemmell and S. Christodoulakis. Principles of delay-sensitive multimedia data storage and retrieval. ACM Transactions on Information Systems, 10(1):51{90, January 1992. GR93] S. Ghandeharizadeh and L. Ramos. Continuous retrieval of multimedia data using parallelism. IEEE Transactions on Knowledge and Data Engineering, 5(4):658{669, August 1993. GS93] S. Ghandeharizadeh and C. Shahabi. Management of physical replicas in parallel multimedia information systems. In Foundations of Data Organization and Algorithms, Chicago, Illinois, pages 51{68. Springer-Verlag, October 1993. LS93] P. Lougher and D. Shepherd. The design of a storage server for continuous media. The Computer Journal, 36(1):32{42, 1993. ORS95] B. Ozden, R. Rastogi, and A. Silberschatz. A framework for the storage and retrieval of continuous media data. In Proceedings of the IEEE International Conference on Multimedia Computing and Systems, Washington D.C., May 1995.

34

ORSM95] B. Ozden, R. Rastogi, A. Silberschatz, and C. Martin. Demand paging for movie-on-demand servers. In Proceedings of the IEEE International Conference on Multimedia Computing and Systems, Washington D.C., May 1995. RV91] P. V. Rangan and H. M. Vin. Designing le systems for digital video and audio. In Proceedings of the Thirteenth Symposium on Operating System Principles, New York, pages 81{94, October 1991. RV93] P. V. Rangan and H. M. Vin. E cient storage techniques for digital continuous multimedia. IEEE Transactions on Knowledge and Data Engineering, 5(4):564{573, August 1993. RW94] A. L. N. Reddy and J. C. Wyllie. I/O issues in a multimedia system. Computer, 27(3):69{74, March 1994. TPBG93] F. A. Tobagi, J. Pang, R. Baird, and M. Gang. Streaming RAID: A disk storage system for video and audio les. In Proceedings of ACM Multimedia, Anaheim, CA, pages 393{400, August 1993. VGG94] H. Vin, A. Goyal, and P. Goyal. An observation-based admission control algorithm for multimedia servers. In Proceedings of the IEEE International Conference on Multimedia Computing and Systems, Boston, MA, pages 234{243, May 1994. YSB+ 89] C. Yu, W. Sun, D. Bitton, Q. Yang, R. Bruno, and J. Tullis. E cient placement of audio data on optical disks for real-time applications. Communications of the ACM, 32(7):862{871, July 1989.

35


赞助商链接
相关文章:
...demand for good quality water around the world
With increasing demand for good quality water ...has shown a great potential as a low-cost, ...The storage of rainwater for daily activities and...
Marketing Strategy of Fast Fashion Brand A Case Ana...
consumers’ demand within days and apply the information to product design. ...efficiency and low cost and this mix are widely regarded as a pioneering ...
2011英语六级阅读理解模拟
Thus , in the American economic system it is the demand of individual ...agreements with Asian partners as a low-cost route to developing new ...
英语论文-中国在世界经济中的优势与劣势
fast growing market demand; 3) low cost and high quality of human ... because the emphasis of formal finance system is still designed to service...
kotler_chapter10
are more certain about costs than about demand. ...A) good-value pricing B) add-on pricing C) ... If Canon Camera Company follows a low-price, ...
大学英语四级模拟卷二
3. A. Emigration of top students, poor infrastructure, and low demand. B...D. To develop an intelligent system of road signals. Section B Conversation...
International Financial Accounting and Reporting—easyJet and...
1 1 Introduction After discovering the demand for low cost carriers (LCC),...focus-on-being-the-lowest-cost-producer-96465 (Accessed: 16th November 2013...
Marketing Assignment 2- The Easy Jet Case Service
II.2 Recommendations for the Waiting Line System and Stabilising the Demand ...3) Cooperate with other low-cost airline companies like Ryanair to co-...
MT+Tutorial+W3+Ex2+-+Defining+Factors+ANSWERS
These low average costs make it less attractive ...s near monopoly in operating systems, coupled ...video-on-demand services, online video rental ...
蓝海策略优劣
Flexible computer-aided design and manufacturing ...? Create competitive advantages Lowering cost: it ...P101, demand and value innovation: reach beyond ...
更多相关标签: