The Design and Implementation of Video Servers in Video-on-Demand Systems

Abstract

Joseph Kee-Ying Ng and Shuhua Xiong1. Introduction.

With the advent of technologies in multimedia computing and high-speed network, the demand for multimedia communication is increasing. Users demand not only talking to each other, but also seeing and sending texts to each other. Compared with text and voice, video images include massive nature information which is difficult to be explained by speech and word alone. Since the volume of digitized video data is very large, video data need to be compressed before transmission and storage. JPEG, MPEG-1, MPEG-2, MPEG-4, MPEG-7, H.261 and H.263 are some of the most popular compression standards for images and videos–[24].

It is obvious that multimedia communication will be widely used in fields such as distance learning, telemedicine, remote monitor and control, home shopping, and entertainment. Among these applications, Video-on-demand (VoD) is a hot topic and will become increasingly popular. At present, the video stored in VoD system server is commonly compressed according to the MPEG-1, or MPEG-2 standards.

2. Single-Server and Multi-Server Design.

In the earlier literatures about VoD systems designs, the common type of architecture is the single-server model. The video server can range from a standard PC for small-scale system to a massively parallel supercomputer with thousands of processors for large-scale system. However, a single server VoD system has some limitations [12, 17]. One of them is the I/O capacity. In the proposed single-server VoD systems, there are three ways to try to overcome this limitation. They are replication, partitioning the video files and bathing stream respectively. However they can not achieve efficient improvement in performance. The second limitation is no fault tolerance in the server level. In other words, once the server fails, the whole system collapses.

With the advent of multimedia techniques and the increase in demand in video quality and services, the I/O limitations and the single point of failure are becoming the major obstacles in the design of the video server. Furthermore, with the tendency of substituting expensive and high computation machines with cheaper personal computers, VoD system design is in favor of a multi-server design. Therefore, it is necessary to develop multi-server VoD systems. Such systems are designed to improve the scalability and performance over a single-server design. Although there are technological advances in CPU design, network bandwidth, and storage capacity. Unfortunately, there is still a bottleneck that plagues the realization of such a system [9]—the speed of data transfer from the secondary data storage to main memory. CPU speeds and storage capacity are increasing at the rate of nearly 45–50% each year, but the mechanical overheads in magnetic disks are improving at the rate of only 7% each year. Since multimedia information systems are inherently I/O intensive, it is critical to reduce the negative effects of this bottleneck. In some of the more recent VoD systems, disk-array is the most popular policy to address the I/O bottleneck.

3. Major Problems in Video Server Design.

The major problems in the design of a multi-server VoD system are as follows:

• Overcoming the hotspot of popular videos: There are popular videos, like the Titanic. On the other hand, there are also videos that will become popular over time. At any time, users probably like to access the popular videos. If the architecture of the VoD system and the deployment of video data are not suitable, then it is likely that the servers or the disks, which are responsible for the popular videos, are too busy to handle their tasks while the others are idle. This is known as the hot spot of popular videos. Obviously, a good VoD system should eliminate it.
• Keeping the load balance: All the servers in a multi-server VoD system should share the same load. The case where some servers are overloaded while others are under utilized should be avoided.
• Supporting fault tolerance. In a multi-server VoD system, some servers may fail over time due to hardware or software failures. In order to maintain the guaranteed service for all the clients, tasks assigned to the failed servers should be shared by the other active servers without severely affecting the playback of any other clients.
• Providing full VCR-like functionality: In a true VoD system, the user has complete control over the session presentation. The user has full-function VCR (virtual VCR) capabilities, which include fast forward and reverse play, freezing, and random positioning, etc.
• Providing different levels of QoS: In a flexible VoD system, different clients may demand to play any video at any playback rate according to their application requirements, actual network workload, or configuration environment.
• Minimizing the storage capacity: A reasonable VoD system has a large collection of videos. In principle, we hope to store as many videos as possible but minimizing the storage capacity. Since the capacity of storage devices is increasing while the price is decreasing, this problem is no longer an essential or critical one.
• Easy to maintain and change: After a VoD prototype is built, the videos will probably be upgraded over time and servers probably need maintenance and leave the system. When servers join or leave, scalability is a problem for the VoD system. Furthermore, it is necessary to remove old videos and add in new ones. So, a flexible system should be easily changed without severely interrupting its regular service.

4. Existing Methods and their Advantages and Disadvantages.4.1 Space Striping and Time Striping.

No existing VoD system can effectively handle all of the above problems at the same time. Almost every one has its advantages and also has its drawbacks. Either for a single-server VoD system with multiple disks, or a multi-server VoD system with multiple disks, the most popular design is based on the striping strategy. Striping strategy is based on a standardized scheme for multiple-disk database design, known as Redundancy Array Independent Disks (RAID) [21]. The RAID scheme consists of six levels, Level 0 through Level 5, and each level has its characteristic in the placements of data and redundancy algorithms. According to the ways of dividing striping units, striping strategy can be divided into two categories: space striping and time striping.

Fig. 4.1. Time striping across video servers.

Fig. 4.2. Space striping across video servers.

Figure 4.1 and 4.2 generalize the two striping approaches. By time striping, a video file is stripped or divided in terms of time among several video servers. The granularity can be as small as one frome-time. Figure 4.1 shows the placement of the frames from a video file when the granularity of a strip is one frame-time. On the other hand, by space striping, the video file is divided into segments of fixed length—fixed amount of storage space. Assuming a granularity of 8 Kbyte, Figure 4.2 shows the storage arrangement for the same video file by space striping. One typical example for using space striping is the Tiger Video Fileserver [3]. In the Tiger system, files are broken up into blocks of equal size that is typically in the range of 64 Kbytes to 1 Mbytes per block. Every file is striped across every disk and every cub. Thus it can provide absolute load balancing and a constant bit rate (CBR) transmission and some limited fault tolerance by employing the mirroring strategy. The Tiger system also developed a multiple bit rate server [2] to support limited pre-defined multiple bit rates transmission. Here, the block sizes are proportional to the corresponding bit rates in such system. However, for a certain video file, once the block size is given, the bit rate is determined and unchangeable. Thus with both types of Tiger Video Fileservers, different client can not demand the QoS at any arbitrary levels, and VCR-like functions can not be supported. For the Tiger system, the capability of fault tolerance is very limited, it is the tradeoff in the choice of decluster factor between reserving bandwidth for failed mode operation and the degree of fault tolerance. Furthermore the Tiger system ignores the features in MPEG standard where video stream is compressed into a variable-bit-rate (VBR) stream with a constant frame rate. There are also other VoD systems with space striping [9] and most of them suffer from the similar drawbacks as in the Tiger Video Fileserver.

On the other hand, there are also many VoD systems that use time striping strategy. The features of MPEG usually are taken into consideration in the time striping VoD system. The principle of time striping is similar to that of space striping. Their difference is that time striping is using time unit to stripe the video, such that every unit has equal time interval. The time interval of a unit is typically in the range from one frame to several frames. In theory, employing subframe [1] can achieve better storage balance and load balance, however it can not support VCR-like function and has low throughput due to the rotation and seek time of the disk. Therefore, most of the VoD systems that employ time striping strategy allocate the video file into blocks of one frame or several frames. If the block size is equal to one frame, the system can support some VCR-like functions but resuls in an unbalance load because of the differences in size among the I-, P-, and B-frames. So in many VoD systems that aim at providing VCR-like functions, a unit is usually defined as an independently decodable data block. For example, Taecj-Geun Kwon et al. [11] proposed disk placement for arbitrary-rate playback, in which the time striping unit at least includes a Group of Picture (GoP) pattern. Thus, with the MPEG-1 or MPEG-2 compression standard, VoD systems that use time striping strategy provide a variable bit rate (VBR) transmission at a constant frame rate and can achieve VCR-like functions.

A common disadvantage of striping is that changing the system configuration such as the adding or removing of servers or disks requires changing the allocation of all the video data. That is to say, most striping systems have difficulties in maintaining or changing the video files. In practice, it is likely that there are often new videos or new servers to be added into the system. VoD system without the striping policy can enjoy the flexibility when a server join or leave the system in run-time. Like the distributed video system proposed by Kuo and et al. [8] it provides fault tolerance and easy joining algorithm at the cost of communication overhead and extra storage.

4.2 VCR-like Functions.

According to the interactivity, Little and Venkatesh from Boston University have classified interactive video services into the following different categories [14, 17]:

• Broadcast (No-VoD) services which is similar to broadcast TV, for this service the user has absolutely no control over the session.
• Pay-per-view (PPV) services in which the user signs up and pays for specific video programme. This service is similar to the existing Cable Pay-Per-View services.
• Quasi Video-on-Demand (Q-VoD) services, where users are grouped based on their common viewing interest or preferences. Users subscribing this service can perform at the simplest level of temporal control activities by switching among different groups.
• Near video-on-demand (N-VoD) services in which functions like forward and reverse are simulated by transitions in discrete time intervals (on the order of 5 minutes). This capability can be provided by multiple channels with the same video programme skewed in time.
• True Video-on-Demand (T-VoD) services, this is by far the most difficult to implement. The user has complete control over the video session presentation. as well as full-function VCR (virtual VCR) capabilities, including forward and reverse play, freeze, and random positioning[13].

A simple approach to provide VCR-like functions is to store a Fast Forward (FF) replica for each video object in the system and starts displaying the replica instead of the normal speed video object. Replica occupies extra storage capacity, so most VoD systems don't use this method. On the contrary, they employ the skipping scheme. For a common VoD system with common disk-array data placement, sometimes it can provide some limited QoS guarantees, however, the load will be unbalanced. For example, in the VoD system with a Round-robin (RR) scheduler, video segments are stored in disk-array in turn. Although the RR policy is simple to implement, it is not suitable for arbitrary-rate playback because accesses are clustered on some specific disks at a particular speed.

In the more recent literatures, several schemes have been proposed to support arbitrary-rate playback and keep the load balance. One of them is the segment sampling method (SSM) proposed by Chen et al. [5]. In order to achieve the segments sampled to be distributed as uniform as possible, this scheme shifts to the right segments to be read for FF at some specific rate to avoid retrieving at the hotspot disks, in which segments are stored basically in an RR manner. Moreover Chen et al. also presented another scheme known as the segment placement method (SPM), in which the placement of data segment is different from that in RR. The SPM scheme judiciously allocates segments across disks to minimize the variation of the number of segments skipped, so that the segment can be uniformly sampled in FF at some pre-determined speed. Based on RR, SSM, and SPM, Taeck-Geun Kwon et al.[11] presented another theory, in which the optimal load balance at any FF rate is achieved by setting N (the number of disks) to a prime number. This method is called prime round-robin (PRR). In addition, Sincoskie [19] has proposed a design based on interleaving the video frames. This scheme provides very limited remote-control functionality and is non-scalable. Alok Srivastava et al. [20] have also proposed another scheme which interleaved the storage. This proposed scheme can provide the complete functionality of a remote control and minimize the starting delay and the buffer requirement at the user end. However, there is a fatal drawback in Alok Srivastava's desgn. That is, their use of three different kind of disks in their implementation: normal disks for normal playback, fast-forwarding disks for FF playback and rewinding disks for RF playback.

In general, the concept of arbitrary-rate in these papers only refers to arbitrary multiples of normal playback speed, it is mainly used to provide VCR-like functions. It does not refer to true arbitrary-rate that means any client can demand to play any video at any rate, such as 10, 11, 20, 25, 30 fps and so on. Furthermore, almost all of these methods do not consider the features in MPEG compression, thus they will have difficulty to be used widely. In addition, most of them did not emphasize on the support of fault tolerance and care less about changing the system dynamically.

4.3 Fault Tolerance.

Multiple servers and disks in a VoD system significantly improve storage capacity and I/O bandwidth. However, the use of multiple devices increases the probability of failure. In a VoD system using striping strategy, without fault tolerance, a failure would result in a disruption of service to all users. Therefore, a good VoD system should provide a high degree of fault-tolerance.

In theory, fault tolerance is usually in conflict with storage capacity and reserving bandwidth for recovering. If a VoD system has to minimize the storage by getting rid of data redundancy, it would not be fault tolerant, such as RAID Level 0. In fact, any fault tolerant capability is achieved at the cost of data redundancy. One of the more popular techniques to provide fault tolerance is the replica of data. For example, in RAID level 1 (mirrored scheme), redundancy is achieved by the simple expedient of duplicating all the data. Every disk in the array has a mirror disk that contains the same data. In the related literatures, there are four replica declustering techniques [6, 7], namely, mirrored declustering, chained declustering, interleaved declustering and rotational mirrored declustering, respectively. In mirrored declustering, the disks are organized into many identical disk arrays, and fault tolerance is then achieved by storing replicated data in these disk arrays. However, it is not suitable for sequential access application, such as VoD, where failure of a single disk will result in the whole striped array out of use since the video stream requires access to each disk in cyclical order repeatedly. The chained declustering method proposed by Golubhik L. et al. [7] can achieve better fault tolerance and load balancing after failure than the mirrored declustering method, because of employing judicious assignment of backup copy. The Tiger system, on the other hand, uses interleave declustering method to provide fault tolerance. This method is based on mirrored scheme and has some improvements. It declusters its mirrored data. That is, a block of data having its primary copy on disk i has its secondary copy spread out over disks i through i+d, whered is known as the decluster factor. The bigger the d, the smaller the reserving bandwidth for recovery, because d increases the number of machines over which the work of a failed cub or disk is spread. However, a larger decluster factor would decrease the efficiency of the I/O. Moreover the continuous d cubs are permitted failure at the same time. Thus d must be the tradeoff among these elements. Therefore, the Tiger system only can provide limited fault tolerance.

Ming-syan Chen et al. [6] proposed a replica placement method, which is called rotational mirrored declustering (RMD). RMD is similar to conventional mirrored scheme in that replicas are stored in different disk arrays. However it is different from the latter in that the replica placements in different disk arrays under RMD are properly rotated. Thus it performs some merits compared to conventional methods in the terms of load balancing and fault tolerance capability.

There are also other methods to achieve fault tolerance. One of them is to introduce parity units. The implementation is described in RAID Level 3, 4 and 5 [21]. RAID level 3 uses bit-interleaved parity whereas Level 4 and 5 use block-level parity. The difference between them is that Level 5 distributes the parity across all disks. When a server or a disk fails, the lost unit stored in the failed one can be recovered from the parity unit together with the remaining units. In RAID Level 2, an error-correcting code is calculated across the corresponding bits on each data disk, and the bits of code are stored in the corresponding bit positions on multiple parity disks. A typical one is using the Hamming code. Of course there are also other coding methods that can play this role. For example, in [1, 23], erasure-correction codes and forward error correction (FEC) are used to support fault tolerance.

5. A Design with Arbitrary-rate Playback and QoS Guarantee.

As mentioned before, we find out that almost all of the existing VoD systems can not provide different levels of QoS without degrading the total performance of VoD system. In practice, there are many users who own computer with low computing power and only have a local link with limited bandwidth. Thus different clients may probably request to play a video at different levels of QoS. Furthermore, as MPEG-1 and MPEG-2 are two of the compression standards for VoD systems, many existing systems and design prototypes have not made full use of the features in the MPEG compression standard. On the contrary, some of them may assume conditions that is in conflict with the compression standards.

Up to this very moment, there has not been a VoD system that can resolve all the fore-mentioned problems. According to the above observations, we have proposed a multi-server VoD system model to incorporate the MPEG compression standards in providing a better QoS guarantee in video playback sessions. In that model, we introduce a mapping data method to support different levels of QoS playback and guarantee true arbitrary-rate playback as smooth as possible without violating MPEG compression and decompression standards. Through some pre-processing for the video streams, we know whether a frame should be sent or not at a given frame rate and pre-save this information as a mapping data. If the frame should be sent, then the mapping data is set to 1. Otherwise it is set to 0. With the mapping data of every video file, any client can demand any video at any rate. When a client demand to play a particular video at a specific rate, the server will first find out the corresponding mapping data file. If the corresponding mapping data for a particular frame is 1, then the frame is retrieved from the secondary storage and is sent to the client. Otherwise the frame is skipped. Thus in our VoD system model, by employing this mapping data method and suitable schedules, true arbitrary-rate playback can be achieved. That is, any client can demand to play any video at any playback rate at any time. In addition, the degree of fault tolerance in our multi-server design is very high. This feature is embodied in two facets: one is that the model can tolerate failure of one or more slave servers. The other is that when there are failed slave servers, all the on-line servers will pick up the tasks of the failed servers and maintain the video services. Thus, the reserving bandwidth or reserving capability for fault tolerance is relatively small. Furthermore, it not only overcomes the hotspot problem from popular videos, it also keeps the system's load balanced. In summary, our VoD system model can provide different levels of QoS and can achieve the video playback of the video as smooth as possible. For details of our video server design, please refer to our technical reports [10].

6. Concluding Remarks.

With the advances in technologies in multimedia computing and the development in high-speed networks, Video on Demand systems are emerging to be one of the popular entity in the community. Current systems and design prototypes rely on techniques like striping and disk arrays to tackle the problems of I/O bandwidth, load balancing, and fault tolerance. On the other hand, as the MPEG video compression schemes are becoming the standards for video storage, VoD systems in the future should incorporate the MPEG features in their designs. With all the hard work from the researchers in the fields of multimedia computing, distributed systems, and communications, hopefully some time in the near future, we can have a perfect VoD system that can serve the community over the public network.

References

[1] C. Bernhardt and E. Biersack, The server Array: A Scalable Video Server Architecture, High-Speed networks for Multimedia Applications, 1996.

[2] W. J. Bolosky, R. P. Fitzgerald and J. R. Douceur, Distributed Schedule Management in the Tiger Video Fileserver.

[3] W. J. Bolosky, J. S. Barrera et al., The Tiger Video Fileserver, Proceedings of the sixth international workshop on Network and Operating System Support for Digital Audio and Video, IEEE Computer Society Press, Los Alamitos, California, 1996.

[4] E. Chang and A. Zakhor, Cost Analysis for VBR Video Servers, IEEE Multimedia, No. 3, Vol. 4, pp. 56–64, 1996.

[5] M. S. Chen, D. Kandlur, and P. Yu, Support for Fully Interactive Playback in Disk-Array-Based Video Server, Proc. ACM Multimedia, pp. 391–398, 1994.

[6] M. S. Chen, H. I. Hsiao, C. S. Li, P. S. Yu, Using Rotational Mirrored Declustering for Replica placement in a Disk-Array-Based Video server, Multimedia Systems, pp. 371-379, 1997.

[7] L. Golubchik, J. C. S. Lui, and R. R. Muntz, Chained Declustering balancing and robustness to Skew and failure, Proceedings of 2nd International workshop On Research Issues in data Engineer Transaction and Query Processing, Temple, AZ, pp. 89-95.

[8] G. H. Huang, S. K. Ni, and T. W. Kuo, The Design and Implementation of the CPU Power Regulator for Multimedia Operating Systems, Proceedings of the IEEE 17th Real-Time Systems Symposium, Work-in-Progress session, 1996.

[9] D. Jadav, A. Choudhary and P. B. Berra, An Evaluation of Design trade-off in a High-performance, Media-on-Demand Server, Multimedia Systems, pp. 53–68, 1997.

[10] J. Ng, and S. Xiong, A Multiple Server Design for a Video on Demand System, Technical Report (JNG11-98), Department of Computer Science, Hong Kong Baptist University, November 1998. http://www.comp.hkbu.edu.hk/~jng/Tech-Rpt/index.html

[11] T. Kwon, Y. Choi and S. Lee, Disk placement for arbitrary-rate playback in an interactive video server, Multimedia Systems, pp. 271–281, 1997.

[12] J. Y. B. Lee, Parallel Video Servers: a Tutorial, IEEE Multimedia, Vol. 5, No. 2, pp. 20–28, 1998.

[13] W. Liao and V. K. Li, The Split and Merge Protocol for Interactive Video-on-Demand, IEEE Multimedia, Vol. 4, No. 4, pp. 51–62, 1997.

[14] T. Little, and D. Venkatesh, Prospects for interactive video-on-demand, IEEE Multimedia, Vol. 1, No. 3, pp. 14–24, 1994.

[15] C. U. Orji, P. O. Bobbie, K. C. Nwosu, Spatio-temporal Effects of Multimedia Objects Storage and Delivery for Video-on-Demand Systems, Multimedia Systems, pp. 39–52, 1997.

[16] D. Patterson, G. Gibson, and R. Katz, A Case for Redundant Arrays of Inexpensive Disks (RAID), ACM SIGMOD, pp. 109–116, 1988.

[17] J. Peltoniemi, Video-on-Demand Overview, http://www.cs.tut.fi/tlt/stuff/vod/VoDOverview/vod1.html

[18] S. Sengodan and V. O. K. Li, A Shared Buffer Architecture for Interactive VoD Servers, IEEE Multimedia, 1997.

[19] W. D. Sinsoskie, System Architecture for a Large Scale Video-on-Demand Service, Computer Networks and ISDN Systems, Vol. 22, pp. 155–162.

[20] A. Srivastava, A. Kumar and A. Singru, Design and Analysis of a Video-on-Demand Server, Multimedia Systems, pp. 238-254, 1997.

[21] W. Stallings, Operating Systems: Internals and Design Principles, 3^rd Edition, Prentice Hall, pp. 471–479, 1998.

[22] J. L. Wolf, P. S.Yu and H. Shachnai, Disk Load Balancing for Video-on-Demand systems, Multimedia Systems, pp. 358–370, 1997.

[23] P. C. Wong and Y. B. Lee, Redundant Array of Inexpensive servers (RAIS) for On-Demand Multimedia Services, Proc. ICC 97, IEEE Computer Society Press, Los Alamitos, Calif., pp. 787–792, 1997.

[24] C. H. Wu and J. D. Irwin, Emerging Multimedia Computer Communication Technologies, Prentice Hall PTR, 1998.

Edited by: Domenico Talia and Hong Shen

Received: August 23rd, 1998

Accepted: October 3rd, 1998