Interactive Video On Demand System
Video On Demand has become increasingly popular. Giant television providers in the United States have committed to provide VOD services in the near future. Interactive Video On Demand (IVOD) is an extension of VOD in which additional functionalities such as Fast Forward, Fast Rewind, and Pause are implemented. These functionalities pose new requirements and challenges on the system implementation. An IVOD system has three components: Client's "set-top box", network, and servers with archives. The clients' set-top boxes are their interfaces to the IVOD system. It has a network interface, a decoder, buffers, and synchronization hardware. Clients input their commands using remote controls. Network of an IVOD system must be a high speed network. Currently available technologies that are suitable for transferring IVOD data include SONET, ATM, ADSL, and HFC. Servers with archives are places where user commands are processed and where movies are stored. Issues such as admission control, servicing policies, and the storage subsystem structure must be considered when designing the IVOD system. In addition to the technical issues described above, non-technical issues such as standards, property rights, and cost must also be considered.
|List of Figures||iv|
|List of Tables||iv|
|4||Quality of Service||7|
|6.1||Network Requirements of the IVOD System||9|
|6.2||Existing Network Technologies||10|
|7.3.2||Movie Storage Data Distribution||16|
|7.3.3||Data Block Placement||17|
|7.4||User Traffic Characterization||19|
|8||Ways of Handling Interactive Functions||20|
|Figure 1||A Centralized Interactive Video On Demand System||2|
|Figure 2||A Centralized IOVD System with Local Buffers||3|
|Figure 3||A Distributed Interactive Video On Demand System||3|
|Figure 4||Communications Between Clients and Servers||4|
|Figure 5||A User's Set-Top Box||5|
|Figure 6||An IVOD Storage Hierarchy||6|
|Figure 7||The Overall Interactive Video On Demand System Architecture||6|
|Figure 8||A Network Model for IVOD Systems||10|
|Figure 9||An ADSL Local Distribution Network||11|
|Figure 10||A Hybrid Fiber Coax Local Distribution Network||12|
|Figure 11||A Typical Structure of an IVOD Server||13|
|Figure 12||Data Flow Graph of an IVOD Server||13|
|Table 1||Interactive TV Trials in the United States||22|
|Table 2||Interactive TV Trials Outside the US||23|
With the explosion of Internet, people have endless hype, opinions, forecasts, and
beliefs about it . Interactive Television, they feel, is the vision to their beliefs:
people will soon be able to purchase products, view movies, play video games, browse
Internet, participate video-conferences without leaving their houses . Of all the new
things that people can do with television, video-on-demands is highly supported by
Hollywood since it can lead to new markets and can bring them unpredictable profits.
People have been passive participants in receiving what TV service providers offer
since television was introduced. Interactive Video On Demand (IVOD), unlike traditional
television delivery, provides users with flexibility in choosing the kinds of information
they like to receive . An IVOD system is capable of serving a large number of end users
to concurrently access large number of repositories of stored data, often movies .
IVOD is basically an extension of Video On Demand (VOD). In addition to the freedom of
choosing movies, users can interact with movies and decide the viewing schedule . In
other words, IVOD system supports VCR-like functions, such as fast forward, rewind, pause.
The enormous communication bandwidth and disk bandwidth required, and the Quality of
Service (QoS) demanded necessitate a careful design of the system in order to maximize the
number of concurrent users while minimizing the cost.
An IVOD system comprises of 3 major components: the "set-top box" at the client's site, the distribution network, and the server. There are many design issues to consider in building each of these components. In this paper, we first discuss several different alternatives for the system structure -- the placement of video servers. We then provide a general description on each of the system components. In Section 3 and Section 4, some interactive functions and the QoS expected from an IVOD system are presented. The next three sections discuss each of the system components in details: The hardware requirements for the "set-top box" at clients' sites are outlined in Section 5. Network requirements and existing potential network technologies for implementing an IVOD system are studied in Section 6. Section 7 presents various issues to consider in building an IVOD server, including admission control to guarantee QoS, servicing policies employed to serve viewers, and user traffic characterization to improve system's performance. Design issues to consider in building the storage subsystem in an IVOD server are also discussed. They include the structure of the storage subsystem, the movies' distributions in the subsystem, the placement schemes of data blocks on storage devices in the subsystem, and the disk scheduling algorithms used to retrieve data blocks for viewers. Several proposed ways of supporting interactive functions are outlined in Section 8. Lastly, Section 9 lists some of the existing VOD trials.
As with other networked systems, IVOD can be designed as centralized multimedia systems or distributed multimedia systems. A centralized IVOD system places processing servers and media archives in a single site as a central node. Requests from clients are processed at the central node, and videos demanded are delivered through the network to the client sites. Figure 1 illustrates a centralized system architecture. Centralized IVOD systems are simple to manage, but they usually suffer from poor scalability, long network delay, and low throughput. The performance of centralized IVOD systems can be improved if local servers are added. These local servers have video buffers, but no media archives. Popular movies can be stored in local video buffers so that they can be delivered to clients more quickly. Videos that are not buffered at local sites can be delivered to clients from the central archive when they are requested. A distributed IVOD system has local processing servers and media archives. Clients' requests are handled by local servers (Figure 3). If the movie requested is not in the local archive, the local server can request the movie from remote servers located across the network.
Figure 1. A Centralized Interactive Video On Demand System
Figure 2. A Centralized IVOD System with Local Buffers
Figure 3. A Distributed Interactive Video On Demand System
A distributed IVOD system can be viewed as many small regional IVOD systems connected
together. The distributed IVOD system spreads users' requests to many sites, thereby
moving the processing servers and media archives closer to the clients. Local servers
reduce network delay and congestion as experienced by central servers, but distributed
systems are more difficult to manage. The choice of the system structure depends on the
available storage, communication systems, costs, application demands, and other factors.
However, the desired QoS of IVOD systems (described in Section 4) makes the
distributed structure more preferable.
Each IVOD connection requires a bi-directional communication between the client and the
local server. Each server has a number of video selections available for users. The server
processes the client's requests and tries to respond to the clients' demands as soon as
possible. An IVOD system should be able to handle hundreds or even thousands of clients
with different preferences simultaneously . The quality of each service should remain
in specific bounds throughout the entire session. An IVOD service usually starts from a
client requesting information from a server; the server responds via the network to the
The system architecture of an Interactive Video On Demand system basically consists of
three major parts: a client, a network, and a server. Each part can be subdivided further
into components and interfaces. Figure 4 depicts the communications between clients and
Figure 4. Communications Between Clients and Servers
A client subscribing to an Interactive Video On Demand service has a display device
(usually TV) and some audio devices (e.g. speakers) to present the movie requested. He/She
interacts with the system via an input device such as a remote control, a mouse, or a
keyboard. A controller is needed at the client site to take the client's commands and to
send the signal to the server through its network interface. The controller also stores
video signals it receives from the server into its buffers, decodes the compressed
signals, and sends the decoded signals to the display at the appropriate time. The
controller is assembled in a box, known as the "set-top box." Figure 5 depicts
the components at the client site.
Figure 5. A User's Set-Top Box
An IVOD service requires real-time display of the video purchased by the client. A typical video stream consists of frames of pictures, sounds corresponding to those frames, and captioned text. The large quantity of information needed to be transmitted to the client continuously with minimal delay poses high performance requirements on the network. An IVOD network should be a high speed network with reasonable error rate as retransmission is unacceptable. Since video information is delay sensitive, the delay variation (jitter) should be kept to a minimum.
A server of an IVOD system processes commands from users. It accepts or rejects the
clients' requests based on the current state of the system and the network load (refer
to Section 7.1). It also performs scheduling on the retrieval of data for all active
clients. A multimedia archive is connected to the server. The archive contains a
collection of videos available to the users. Depending on the system requirements and the
budget available, a range of storage devices can be used: cache (RAM) is the most
expensive but has the lowest access time. Disk-arrays provide fault-tolerance at a
reasonable price and access rate (10 msec). Optical discs have a capacity of 650 MB with
access time 100 msec. Digital Versatile Disc (DVD) is state of the art. Each disc can
stores 4.7 gigabytes of information. The content of movies stored on DVD discs can be
easily configured to suit viewers' preferences with the help of authoring tools. Tape
drives are on the lower price range, but with longer access time. A typical IVOD storage
system uses a combination of storage devices to optimize the tradeoff between cost and
efficiency. Figure 6 depicts a general IVOD storage hierarchy.
Figure 6. An IVOD Storage Hierarchy
Combining all the components above, an IVOD system is constructed. The overall system architecture of an IVOD system is shown in Figure 7.
Figure 7. The Overall Interactive Video On Demand System Architecture
Other interactive features include the ability to avoid or select advertisements, to investigate additional details about news events (through hypermedia, for example), and to browse, select, and purchase goods . Seven main interactive functions: Fast Forward, Fast Reverse, Jump, Play, Stop, Pause, and Slow Down will be discussed in this paper.
Quality of Service (QoS) can be used in many different aspects. For instance, QoS in
networks may include guarantees on the throughput, network delays, delay jitter, error
rate, etc. QoS in this paper refers to the required standards of IVOD services expected by
users. They include:
Fast setup time: Initial service delay (connection setup time) should be within
a few minutes.
Independence of Quality of Service to different customers: Quality of service
provided to the current customers should not be degraded due to the joining of new
customers to the service.
Continuity of media streams: There should be no or little jitter in presentation
Prompt response to interactive functions: The loading of extra data from the
server due to interactive functions, e.g. fast forward, should be invisible to the
customer in the ideal case. It should appear as if the client is operating his/her own
Transparency of the involvement of multiple media streams: Multiple media
streams must be synchronized. For instance, if a video object is to be combined with an
audio object at the client's site, this should be done in such a way that
lip-synchronization is achieved.
All of the above QoS require cooperation of all three components in the IVOD system: server, network, as well as the "set-top box".
To support interactive services, considerable functionalities must be built into the
set-top box. Four important components for set-top box are Network Interface, Buffer,
Decoder and Synchronization Hardware.
The network interface allows the client to receive data from server. Moreover, it
provides a mechanism to translate user commands received by the sensor to appropriate
signals for transmissions on network.
In order to save storage space, disk bandwidth, and network bandwidth, movies are
usually encoded before they are stored. Thus, a decoder at the client's site is needed to
decode the arrived media streams before presenting them to the viewer.
Due to delay jitters in the network, the arrival time of a video stream cannot be
determined exactly. In order to guarantee starvation-free (continuous) playback, the
server must ensure a media unit is available at the client prior to its earliest predicted
playback time. By taking into account the maximum network delay (max), the
server can transmit a media unit at least max prior to the unit's earliest
predicted playback time. However, if the actual network delay experienced by the media
unit is less than max, the media unit will arrive at the client earlier than
its scheduled playback time, and will have to be buffered . For details on the
computations of the maximum buffering that is needed at the client's site, refer to .
If the buffer size is large enough and the Jump size is relatively small, Jump Forward
or Jump Backward may not require data delivery from the server. In other words, the data
required are already in the client's buffer. The response to the jumps will be faster as
compared to those requiring data from the server. Buffering also makes the response to
Fast Forward and Fast Rewind faster if the initial data required is in the buffer.
As mentioned above, decoding is required at the client's site. Buffering of data that
may be required for future display allows data to be decoded while the current data is
being displayed. Less powerful decoding hardware or decoding algorithm can be used since
real-time decoding is avoided. Thus, the cost of the "set-top box" can be
A movie consists of both video and audio streams. They must be synchronized before
being presented. Synchronization is required at the client site to support scalable video
. In scalable video, a video stream is decomposed to a base stream and one or more
additional streams. The additional streams are to be combined with the base stream to
produce higher quality video. Each of those streams is stored as individual media files on
the server. Depending on the quality demanded and the bandwidth available to the client,
the presentation may require zero or more of the additional streams . Therefore,
different media streams must be synchronized before presenting to the customers.
Lastly, the user interface should be simple and easy to use. Preferably, the same remote control can be used for both the IVOD system and the video cassette recorder. In addition, the cost of set-top box must fall within reasonable limits (under a few hundred dollars) for the technology to succeed. Open and interoperable systems that let users subscribe to several different services are preferred .
Unlike traditional computer communications that are bursty and short-lived, the deliveries of videos involve sending enormous amount of data to customer homes continuously for a long-period of time (the length of the movie presentation). Videos are usually encoded using MPEG-1 or MPEG-2 standards. Since MPEG encoding standards exploit the intra-dependancy between frames, the resulting encoded video streams are usually of variable bit rates. These characteristics of videos lead to new criteria and challenges on the network.
High Speed Network. High speed networks are definitely needed for IVOD systems. For
example, videos compressed using MPEG standards require a bandwidth between 1.5 and 6
Mbps. A system supporting 100 users requires a bandwidth close to 600 Mbps. Ordinary 10
Mbps Ethernet or 28.8 kpbs telephone lines cannot support such video transfers.
Connection-Oriented Transfer. IVOD services are real-time multimedia application
services. In other words, the time at which packets arrive at the destination is strictly
bounded. Any packets arrived later than their expected time are useless and discarded.
Moreover, retransmissions are not possible . Consequently, connection-oriented services,
which reduce the rate of dropped and late packets, are desired.
Latency and Jitter. The delay between a video stream being sent from the server
and it being received by the client needs to be minimized. Variations in delay (jitter)
must be kept within rigorous bounds to preserve the quality of the presentation .
In order to provide IVOD services, the network needs to deliver guaranteed services to delay-sensitive variable-bit-rate video traffic. The delay sensitive characteristic of video services requires the network to support some resource reservation schemes for each video stream.
As mentioned above, a typical video stream requires an average bandwidth of 1.5Mbps.
A typical IVOD network can be divided into two levels: backbone and local distribution networks. The backbone connects servers and routers/access nodes together, while the local distribution network links a client site to its nearby router/access node. Each local distribution network link needs a bandwidth of at least 1.5 Mbps - the bandwidth of a single IVOD video stream. The bandwidth of the backbone is usually on the order of hundreds megabits per second, depending on the number of simultaneous connections the IVOD network has to support. Figure 8 illustrates a network model for IVOD systems.
Figure 8. A Network Model for IVOD Systems
IVOD services require high-speed and low-jitter networks to support hundreds or even
thousands of simultaneous connections. The required bandwidth of the backbone is on the
order of hundreds megabits per seconds. Two attractive solutions are SONET and ATM.
SONET. SONET is a synchronous fiber optic network. The entire bandwidth of a
fiber optic link is devoted to a single channel. Nodes connecting the channel transmit
data at different time slots. A basic SONET channel (STS-1) has a bandwidth of 51.84 Mbps.
SONET can also multiplex multiple digital channels together  to support more viewers.
For example, three STS-1 channels are multiplexed to form a STS-3 channel with 155.52 Mbps
bandwidth. SONET is suitable for delivering IVOD streams because bandwidth is guaranteed
and jitter is zero.
ATM. ATM is the acronym for Asynchronous Transfer Mode. It is asynchronous
because it allows data arriving at irregular intervals . ATM is suitable for
transferring IVOD data because it is a connection-oriented packet switching network. ATM
transmits data at a rate from 1.544 Mbps to 622 Mbps, over copper and fiber media.
Note that a backbone with ATM running over SONET can also be adopted.
A local distribution link requires a bandwidth of 1.5 Mbps. Many signaling schemes can
deliver video data at such a data rate over existing communication links . Two such
schemes are described below.
Asymmetrical Digital Subscriber Loop (ADSL). ADSL is a signaling scheme used on copper-wire networks (e.g. telephone networks). It can deliver data at high speed with few signal distortions over existing copper wires. ADSL consists of a pair of ADSL units. One is installed in the client site; the other is attached at the central phone office. ADSL uses advanced integrated circuit designs, complex digital signal processing techniques, and software-based algorithms to compensate distortions in copper wires . ADSL can provide a subscriber with a down-link of 1.536 Mbps wide-band signal, an up-link of 16 Kbps, and a basic-rate ISDN channel/the analog 4 kHz telephone channel on existing twisted copper wire . These characteristics satisfy the bi-directional communication and bandwidth requirements posted by IVOD services. If the client site is within 5.5 kilometers of the access node, no additional equipments are necessary to ensure strength of the received signal. ADSL is achievable because it divides the signal on a range of carrier frequencies, dynamically adjusting to achieve the most efficient channel allocation . Extensions of ADSL include HDSL, SDSL, S-HDSL, and VDSL. HDSL has a data rate of 6 Mbps, and it can support MPEG-2 video streams up to about 2 km . An ADSL local distribution network is shown in figure 9.
Figure 9. An ADSL Local Distribution Network 
Hybrid Fiber Coax (HFC). HFC is currently being installed by cable TV companies. It migrates the all-coaxial cable design to a network with fiber and coaxial cable. Variations on HFC exist and have been implemented. They include fiber-to-feeder, fiber-to-the-hub, fiber-to-the-zone, fiber-to-the-curb, and fiber-to-the-tap. Fiber-to-the-feeder and fiber-to-the-hub are networks with fiber trunks, coaxial distribution links and subscriber drops. The others are networks consist of fiber trunks and distribution links, but coaxial subscriber drops . The migration to HFC involves a replacement of the current 300-450 MHz coaxial cables by new 750 MHz coax cables . Each channel is subdivided in 125 6-MHz subchannels. Bi-directional communications are implemented using splitband systems. In North America, the frequency band between 5-54 MHz is used as up-link. The remaining bandwidth is guard band and down-link. Since clients share the same physical medium, collisions occur when they try to access the medium at the same time. The problem of sharing the transmission medium limits the number of clients attached to a coax tree structure . The network architecture of HFC is depicted in Figure 10.
Figure 10. A Hybrid Fiber Coax Local Distribution Network 
IVOD services are feasible on HFC because the frequency band of the coaxial cables is splitted so that an up-link is available for sending clients' requests to servers. Currently, Rogers Cables Canada is upgrading its existing cable system to HFC, hoping they will soon be able to deliver Internet access services, if not Video On Demand services.
Server is the heart of the IVOD system. It provides high quality services to users by
using strategies that minimize cost. Server has a storage subsystem where movies are
stored. Many researchers have explored ways to optimize the server capacity and have
discussed issues concerning building a multimedia server in general. This section will
discuss admission control, servicing policies, the storage subsystem, and traffic
characterization, which are issues related to optimizing server performances. Figure 11
and Figure 12 depict the general structure and details of an IVOD server:
Figure 11. A Typical Structure of an IVOD server 
Figure 12. Data Flow Graph of an IVOD Server 
Any incoming clients who want to use the IVOD service will have to request for and set
up a connection with one of the servers. If the required movie or parts of the required
movie are not stored in the current server, transfers of data between servers are needed.
Hence, admission control for the remote server is also required.
In order to guarantee new clients have continuous playback of the video and to ensure
the QoS contracted to existing connections are not jeopardized, the server must have
enough resources such as storage subsystem read bandwidth, memory buffers, processing
bandwidth, and network bandwidth before admitting a new connection request . Before
establishing a connection, a set of QoS parameters sent by the client will be checked by
the server. If requested QoS can not be achieved, negotiations can be made between the
client and the server, or the connection will be denied. An alternative is that the server
does not commit the resources requested by the client until the connection is up for some
threshold of time, usually a few minutes . This reduces the probability of committing
resources to connections that just last for a few minutes or even a few seconds.
An admission control algorithm must have some knowledge about the capability of the
storage subsystem, e.g. the minimum number of blocks that the server can read in a time
slot. A time slot is the interval between serving a video stream divided by the number of
active streams in the server. Neufield, Makaroff, and Hutchinson 
suggested that the minimum number of blocks that a server can read in a time slot, called minRead,
is the only storage subsystem information required for the admission control algorithm.
According to them, minRead can be determined by running a calibration program that
uniformly spaces data blocks across the disk to maximize seek times (assuming a SCAN
algorithm is used). The estimation of minRead should be as accurate as possible
because conservative estimations of minRead degrade server performances. A simple
admission control algorithm can be described as follows: sum the block schedules for all
active streams together with that of the requested stream. If the sum is greater than minRead
in any time slot, the connection will be denied. An improvement can be made to this simple
scheme by allowing the server to read ahead when the server is idle.
The server must also ensure enough network resources are available before accepting a
new connection. Unfortunately, variable bit rate video streams create difficulties in
determining the amount of resources needed. If the network reserves resources according to
the average video stream rate, delay or packet loss may occur when the servers are sending
at their peak rates. If the network reserves resources according to the peak video stream
rate, the network may be under-utilized most of the time . Traffic policing is
performed on admitted connections to ensure the connections have not over-used any network
In addition to checking the storage system and network bandwidth, the server also ensures the availability of memory buffers and processing bandwidth. The server, based on the required QoS, determines the amount of buffer space and the processing bandwidth needed by the requested stream.
Servicing policies determine the design and the implementation of various IVOD
components. The server capacity, which is the number of simultaneous viewers that can be
supported by the server, depends on the strategies used in allocating video streams to
viewers. Obviously, from the service providers' point of view, server capacity should be
as large as possible. The simplest way of allocating streams to viewers is to dedicate a
single stream to each viewer. However, this scheme is expensive and inefficient since the
server capacity is bounded by the maximum number of streams that can be handled by the
server. If the network in the IVOD system supports multicast, e.g. ATM, sharing of video
streams among several viewers is possible. Sharing of video streams can significantly
increase the number of simultaneous viewers and can save network bandwidth . Three
service policies have been proposed in :
On-Demand Single Cast (ODSC). ODSC is the simplest of the three schemes. In this
service policy, each client has a dedicated video stream that is assigned to the viewer
when its connection is granted. Since the client has complete control over his/her own
video stream, the implementation of the interactive functions mentioned in Section 3
becomes easy. The drawback of this scheme is that the server capacity is limited. The
waiting for services to become available can be unexpectedly long if client requests come
at times when the server is fully utilized .
Phase Multicast (PMC) or Batching. To use this policy, the data network must
support multicasting. Each video stream is shared by viewers of a multicast group.
Video streams are started at fixed intervals or phases. Connections that are
admitted in between startings of streams are grouped and served by the next video stream
. The video streams' starting intervals can be fixed by the service provider, or they
can be determined by the server dynamically. Without any doubts, the longer the time
interval between consecutive streams, the lesser the service costs and the greater the
number of viewers can be supported by each stream. However, long setup time delay may
cause clients' dissatisfaction. Thus, a tradeoff exists between cost and quality of
A serious drawback of this scheme is the difficulty in implementing interactive
functions. Since the video streams are now shared by others, the delivery of each video
stream cannot deviate from its scheduled time. A discussion on how to support interactive
functions under PMC is out of the scope of this paper.
On Demand Multicast (ODMC). ODMC is a hybrid of PMC and ODSC. During light load,
the server uses ODSC to serve viewers. It switches to PMC during heavy load. Thus, ODMC
addresses problems of PMC and ODSC, which include the inability of ODSC to cope with
overload situations and the underutilization of the server during light load when PMC is
Simulations had been run on the above three service policies under the condition that no interactions are allowed. Thus, the system simulated was really a VOD rather than an IVOD. It was found that the ODMC scheme is suitable for server that is utilized lightly by providing fast setup time. At very high levels of utilization, the PMC service policy should be used. The ODSC service model should only be used when support of extensive random access, which is what IVOD needed, is required. For details on the simulation and the performance results, refer to .
Server subsystem is where compressed movies are stored. The compressed video and corresponding compressed audio streams for a movie can be stored in the same server or in different ones. The storage subsystem is also the place where most of the optimizations are done to improve the performance of the IVOD system. It is an important factor in determining the server's cost. So far, the standard used in an IVOD system that has been agreed on is the use of MPEG-2 for video encoding .
Even with MPEG-2 compression, a movie will occupy approximately 4GB . If the fixed
magnetic disks are used as the sole storage medium in IVOD systems, the cost of archiving
thousands of movies is on the order of millions. Therefore, large tertiary storage devices
such as tape, optical jukeboxes, or the new technology Digital Versatile Disc (DVD)
jukeboxes should also be used .
Tertiary devices are highly cost effective because they provide large storage
capacities at low cost. However, their random access time is slow, and their throughput is
low. Consequently, servers should be organized as a hierarchy that combines the
cost-effectiveness of tertiary storage and high performance of fixed magnetic disks .
Refer to Figure 6 for a server storage hierarchy.
A hierarchical storage model can be described as follows: Popular movies are stored in RAM, less popular ones on the hard disks and the least popular ones on tertiary storage. This hierarchical approach reduces operating costs while offering a wide selection of movies to its users .
Several approaches are possible for managing the storage hierarchy. One approach is to
store the beginning segments of the multimedia files in magnetic disks. This approach
reduces in start-up latency and provides smooth transitions in the playback . It
improves the system performance if viewers make another selection within the first minutes
of the movie [15, 5].
An alternative is to calculate movies' popularity on a daily basis. Based on their popularity, movies are rearranged or replicated as necessary during off-peak hours. Consequently, movies are available for viewing during peak hours based on anticipated demand .
The way in which data blocks of media files are placed on disk can significantly affect
the data retrieval scheme and the system performance since the time required for
retrieving data depends totally on the location of data blocks. The data retrieval scheme
can in turn affect how interactive functions, such as Fast Forward (FF) and Fast Backward
(FB) searches, are supported. One possible approach of implementing FF and FB is to read
more data blocks for that particular client in a round. However, extra disk bandwidth
requires more storage devices to serve the same number of clients, thereby increasing the
cost of the storage subsystem. Cheng, Wen, Lee, Wang, and Oyang  suggested that if the
data blocks are placed by a placement scheme that effectively utilize disk bandwidth
during normal playback, one can design a data retrieval scheme which requires no extra
bandwidth to support interactive functions. However, an extra buffer of size several file
blocks is needed when a stream is in the FF or FB search modes.
Two general strategies used in data block placement schemes are load-matching and
Load-matching. Placement of more frequently accessed data blocks in
"best" (outer) tracks while those that are accessed occasionally are placed in
inner tracks. This strategy exploits the track dependent transfer rate that can have a
ratio of 1:1.8 from inner to outer tracks .
Load-balancing. Placement of data in a way such that constant streaming capacity
is provided independent of viewers' choices and location of data.
Both of the above strategies try to maximize the server's capacity, which is the number
of simultaneous viewers supported. Details on implementation of load-matching and
load-balancing and description on interdisk and intradisk load-balancing can be found in
 and .
Two main schemes of data block placement are disk farm and disk array (RAID). Each disk
holds several entire movies in disk farm; whereas in RAID, each movie is scattered over
multiple drives, e.g. block 0 on drive 0, block 1 on drive 1, and so on so forth. This
organization is called striping. RAID is preferred to disk farm because it offers better
Load matching is a possible approach under this scheme: Popular movies are stored in
outer tracks while less popular ones are stored in inner tracks. However, popularity of
movies may change several times in a day. Thus, the capacity of the server will decrease
when such changes happen. One can dynamically rearrange the movies on disks but this can
be expensive [7, 15]. Under this scheme, the number of concurrent access to a single
multimedia file is limited by the throughput of the disk. However, this scheme is easy to
RAID (Redundant Array of Inexpensive Disks)
Unlike storing data in a single disk, both load-balancing and load-matching can be
achieved in RAID by "striping" all movies onto all disks [7, 15]. Under this
scheme, data is "striped" across an array of disks. The coarser the striping,
the larger the buffer required. Figure 13 describes the structure of a RAID.
Figure 13. RAID 
Striping allows parallel accesses of data from the same physical sectors of all disks in the array. Hence, logical sectors and physical sectors have identical access time. The effective throughput can be increased by a factor that is equaled to the number of disks in the array. The increased transfer rate makes RAID a good structure for the storage subsystem since high bandwidth is required in supporting IVOD . RAID can have several parity disks to provide fault tolerance. Those extra disks contain block-by-block EXCLUSIVE OR of the other disks to allow data recovery for the faulty disks. The number of drives' failures that can be survived is determined by the number of parity disks added. This scheme, however, is ill-suited to interactive functions such as FF and FB since many of the blocks read in parallel will be discarded .
Real-time constraints makes traditional disk scheduling algorithm, such as first come first serve, short seek time first, and scan, inappropriate for IVOD. Here are two suggested scheduling algorithms :
The best known algorithm for real-time scheduling of tasks with deadlines is the earliest
deadline first algorithm (EDF). The media block with the earliest deadline is fetched
first. The disadvantage of this algorithm is excessive seeks and poor utilization of the
server's resource .
A variant of EDF is a combination of SCAN and EDF that is called the Scan-EDF
scheduling algorithm . Scan-EDF, like EDF, services blocks with the earliest deadline
first. However, when several blocks have the same deadline, those blocks are served using
the SCAN algorithm (the disk head moves back and forth across the disk and fetch requested
blocks as it passes them). Clearly, the effectiveness of SCAN-EDF depends entirely on the
number of requests that have the same deadline .
Under round-based algorithms, a server serves all streams in units of round. During
each round, the server retrieves a certain number of blocks for each stream. Since MPEG-2
results in variable-bit-rate compressed streams, the number of blocks that must be
retrieved for each client in each round will vary according to the compression ratio
achieved for each block .
To ensure continuous playback of media streams, the server must retrieve a sufficient
number of blocks for each client in each round to prevent starvation for the round's
duration. Thus, the server has to know the maximum duration of a round as round length
depends on the number of blocks retrieved for each stream. A simple scheme that retrieves
the same number of blocks for each stream (generally referred to as a round robin
algorithm ) is inefficient since the maximum playback rate among all streams will
dictate the number of blocks to read. This results in streams with smaller playback rates
retrieving more data blocks than needed in each round. This may overflow some clients'
buffer as well as decrease the capacity of the server. Consequently, more clients can be
accommodated by reducing the number of data blocks retrieved per service round for streams
with lower playback rate .
One proposed approach to minimize the round length is to make the number of blocks retrieved for each stream in each round proportional to its playback rate . This scheme is called Quality Proportional Multi-subscriber Servicing (QMPS) algorithm. This algorithm is provably optimal in . For more information on QMPS, please refer to .
Even though customers access the IVOD system randomly, having a priori knowledge about the users' access pattern can lead to a more efficient design of the storage scheme and a more efficient utilization of the storage and network bandwidth . For instance, if traffic characteristic indicates that a movie is popular in a particular site, the system can replicate the movie to increase availability. Similarly, knowing the typical user access pattern can be beneficial in designing schemes for resource managements, such as popularity tables updates, data redistributions, and system reconfigurations. Preferably, these resource managements should be done during off-peak hours .
Several ways are proposed on the handling of interactive functions. Most of the
researches are done on implementing FF and FB. Several proposed methods are outlined
Chen, Kandlur, and Yu  proposed that FF and FB can be supported using MPEG frame
skipping. Their approach composes of a storage method, a segment placement scheme, and a
playout method with a segment sampling scheme or a segment placement scheme as
alternatives for selecting segments.
Usage of D-frames provided by MPEG-1 [7, 19]
MPEG-1 D-frames contain only the block averages that can be used for browsing. Thus,
only D-frames are presented to the client after decoding when the client is in FF or FB
modes. This method is attractive since no additional processing is required as the
D-frames are always generated by MPEG-1. However, the resulting outputs have poor
resolutions. Unfortunately, D-frames are not available in MPEG-2.
Block categorizing 
Unlike the previous two schemes, in which the client is responsible for supporting the interactive functions, FF and FB are supported by the server in block categorizing. This scheme works as follows: Each block is marked as being relevant or irrelevant to FF/FB. Both types of blocks are retrieved during normal playback while only those marked relevant are retrieved and transmitted in FF/FB modes. This scheme can be achieved by scalable compression, which combines one or more additional streams with the base stream to produce higher quality [12, 19]. However, scalable compression poses additional overhead on splitting the blocks and recombining them before presenting. This scheme requires extra bandwidth if differential compression is used since most frames are relevant to FF/FB.
Table 1 and 2 list some of the VOD trials existed in the United States and in other parts of the world . In 1995, VOD services had started to appear in the market. However, the responses were poor. Things started to changes in the middle of 1996. Major operators such as Americast, Tele-Communciations Inc, Rogers Cablesystems Ltd. have committed to buying million set-top boxes . A typical set-top box costs about three hundred US dollars. Table 1 and 2 show that many companies have just started to offering VOD services. Price ranges from US $7.50 to US $20.00 per month plus movie charges. Network technologies used in the trials are mostly HFC and ADSL because they require fewer modifications of existing cable and telephone networks. However, when HDTV at 20 Mbps is highly demanded, networks with ATM and Satellite may even be used in local distributions. Analysts estimated that more than US$ 1 billion were spent in 1994 on VOD infrastructure worldwide and nearly US$ 3 billions for 1995 .
Table 1. Interactive TV Trials in the United States
|Interactive TV Trials in the United States|
|Bell Atlantic (FutureVision)||Dover Toms River NJ||Philips, FutureVision, TeleTV||nCUBE, FTTC||NVOD, PPV, transaction||Switch DigVid||2/96-Rollout||0/38,000 (passed)||Varies|
|Bell Atlantic (Stargazer)||Fairfax Vir||Stellar One||nCUBE,||VOD, Inter.||ADSL||3/95 12/96||1,000/1,000||$7.50/mo|
|Bell South (Inter. Serv)||Atlanta GA||Sci/Atlanta||H/P||VOD, NVOD transaction||Fiber/Coax||2/96-mid/97||0/12,000 (passed)||NA|
|Cox Cable (Canceled)||Omaha NB||Zenith||N/A||VOD, NVOD transaction||Hybrid F/Coax||6/94- 12/95||0/2,000||$20+ movie|
|Pacific BellHFC in SD, SJose, Org Cty||California||Sci/Atlanta||N/A||NVOD, VOD, cable||Hybrid F/Coax||96-1997||200/1 million passed(1997-?)||N/A|
|SNET (Canceled)||Hartford CN||Sci/Atlanta||H/P||NVOD, PPV||Hybrid F/Coax||4/94- Mid 96||350/150,000 passed||$20/mo +movies|
|Sprint (VDT Trial)||Wake Forest, NC||N/A||N/A||VOD, Sega, Info||N/A||10/95- Fall 97||650/1,000||N/A|
Table 2. Interactive TV Trials Outside the US
|Interactive TV Trials Outside the US
Primary Source: Electronic Engineering Times, Nov 27,1995
|Cambridge Cable||UK||Fiber/Coax||Online Media||1994||250|
|Deutsche Telekom||Germany||ADSL/ATM/HFC Satellite||Alcatel Nokia IBM HP||1996||1,500,000|
|French Telecom||France||ADSL, Fiber to home||Phillips, SEMA||1996||1-2,000|
|Canel+||France||Satellite||Sony Pioneer Sagem Phillips Thompson||1996||N/A|
|Svenska Kabel TV||Sweden||Fiber/Coax||Digital, Vela Research||1995||500|
|Telecom Italia||Italy||ADSL||B.Atlantic, OS-9/David||1995||1,000|
|Telecom Australia||Australia||ADSL||CLI, OS-9/David||1996||2,500|
|Hong Kong Telecom||Hong Kong||Fiber to building, ATM||NEC, OS-9/David||1996||65,000|
|Israel Telecom||Two city trial||ADSL||Celerity Server, David Settop||1996||N/A|
|Korean Telecom||Korea||ADSL||Celerity Server Samsung/David Settop||1995||100|
|Nakano City TV||Japan||HFC/ATM||Fujitsu, OS-9/David||1995||300|
|Singapore Telecom||Singapore||ADSL, ATM||N/A||1995||300|
In this paper, we give an introduction to the overall system architecture of an IVOD
system. Issues to be considered in designing and building each of the components are
discussed in turn. Lastly, some existing trials are presented.
Developing this new information delivery infrastructure requires considerable planning
and effort . In addition to meeting technology requirements, such as network and disk
bandwidth, making IVOD service a reality also involves considerations of other factors.
They include the cost of building the system, international standard agreement, and
service providers' security. The economics of providing IVOD service cannot be ignored. A
large video server can easily cost more than a mainframe, certainly 10 million dollars.
Consider a regional IVOD service with 100,000 subscribers, each of which rent a 300-dollar
"set-top box". If the networking equipments cost 10 million dollars and have a
4-year depreciation period, the service has to generate 10 dollars per home per month.
Charging 2 dollars per movie and 3 dollars rental for "set-top box" requires
every subscriber buying 2 movies per month to break even . Certainly, all the cost
figures mentioned above vary with time, but it is clear that a mass market is needed for
the technology to be viable . Unfortunately, few of the existing trials have more than
2000 subscribers. For the development of a mass market, agreement on international
standards must be reached. Establishing standards for "set-top box", video-file
server, and standards that allow competition among service providers are important for
such systems to grow . Currently, MPEG-2 is the only standard being agreed on for video
encoding . Mechanisms to protect intellectual property rights must also be established
so that service providers are able to maintain control of their data and thus are able to
stay in business. One mechanism to avoid movie duplication is to limit storage buffer
space in the "set-top box" .
In fact, the technologies required to make IVOD a reality already exist. If an IVOD system can be built with a reasonable cost, international standards can be developed, and mechanisms for protecting the interests of service providers can be established, we can easily see the appearances of large-scale IVOD services in the near future.
Send E-mail to
TSN@The-Saudi.Net with questions or
comments about The Saudi Network.