Handling Updates and Crashes in VoD Systems.
Though there have been several recent efforts to develop disk based video servers, these approaches have all ignored the topic of updates and disk server crashes. In this paper, we present a priority based model for building video servers that handle two classes of events: user events that could include enter, play, pause, rewind, fast-forward, exit, as well assystem events such as insert, delete, server-down,server-up that correspond to uploading new movie blocks onto the disk(s), eliminating existing blocks from the disk(s), and/or experiencing a disk server crash. We will present algorithms to handle such events. Our algorithms are provably correct, and computable in polynomial time. Furthermore, we guarantee that under certain reasonable conditions, continuing clients experience jitter free presentations. We further justify the efficiency of our techniques with a prototype implementation and experimental results.
Introduction
Over the last few years, there has been a tremendous drop in digitization costs, accompanied by a
concomitant drop in prices of secondary and tertiary storage facilities, and advances in sophisticated
compression technology. These three advances, amongst others, have caused a great increase in the
quality and quantity of research into the design of video servers [2, 4, 11, 6, 10, 16].
Most models of video servers to date assume the following parameters:
1. Movies are stored, in part, or in their entirety, on one or more disks.
2. The video-on-demand VoD system is responsible for handling "events" that occur. Client events
that have been studied include:
ffl the enter of a new client into the system, requesting a movie,
ffl the exit of an existing client from the system.
ffl the activities of continuing clients (e.g. play, fast forward, rewind, pause).
"Handling" an event refers to the process by which the VoD server assigns jobs to different disk
servers, so as to optimize some performance criterion. A variety of algorithms to "handle" the
above events have been studied by researchers.
Authors' Address: Department of Computer Science, University of Maryland, College Park, MD 20742.
All the above events are "user" events, in the sense that they are invoked or caused by the activities
of a user of the VoD system. However, in reality, there is another class of events that must be accounted
for, which we call system events, which includes events such as server-down (specifying that a certain
disk server has crashed), server-up (specifying that a disk server that had previously crashed is "up"
again), insert (specifying that the system manager wishes to include some new movies (or blocks of
movies) on a disk), and delete (specifying that the system manager wishes to delete some movies
from a server's disk array). Most work to date on server crashes has focused on the important topic
of recovery of data on the crashed disk, but has not really looked into how to satisfy clients in the
VoD system who were promised service based, in part, on the expectation that the crashed disk would
satisfy some requests. The main focus of this paper is to develop VoD server algorithms that can
handle not just user events, but can also handle system events.
The problem of updates in video servers is crucial for several applications where video data is being
gathered at regular intervals and being placed on the VoD system. For example, a movie-on-demand
vendor may, at regular intervals, include new movies in the repertoire of movies offered to potential
customers. These movies need to be placed on the disk array that the vendor may be using, leading
to an insert operation. Similarly, in news-on-demand systems, new news videos and audio reports
may become available on a continuing basis, and these need to be made available to editors of news
programs for creating their current and up to date news shows. In many similar systems today, this
is done by taking the system "down", accomplishing the update, and then bringing the system back
"up" again. The obvious undesirable aspect of this way of handling updates is that service must be
denied to customers who wish to access the server when it is down, thus leading to lost revenues for
the VoD vendor. The algorithms proposed in this paper treat updates as (collections of) events, and
schedule them to occur concurrently with user-events in a manner that ensures that:
1. existing customers see no deterioration (under some reasonable restrictions) in the quality of
service, and
2. the update gets incorporated in a timely fashion. In particular, our algorithms will flexibly adapt
to the load on the disks, so as to incorporate as much of the update as possible when resources
are available, and to reduce the update rate when resources have been previously committed.
3. the system is not "taken down" in order to accomplish the update.
Unlike the issue of updates, disk crashes have certainly been studied extensively over the years [2,
12]. However, consider the problem of a VoD server that has made certain commitments to customers.
When a crash occurs, the VoD server must try to ensure that any client being serviced by the disk
that crashed be "switched" to another disk that can service that client's needs. Furthermore, the VoD
server must ensure that the fact disk d has crashed be taken into account when processing new events.
In the same vein, when a disk server that had previously crashed comes back "up", this means that
new system resources are available, thus enabling the VoD server to take appropriate actions (e.g.
admit waiting clients, re-distribute the load on servers to achieve good load balance, etc. We show
how our framework for handling updates can handle such crashes as well (under certain limitations of
course).
In particular, we propose an algorithm called the VSUC ("Video Server with Updates and Crashes")
algorithm, that handles events (including user events, as well as update events and crashes) and has
several nice properties. In particular:
Disk Array
Server
Disk Array
Server n
Disk Array
Client 1 Client 2 Client m-1 Client m
High Speed Network
ROUTER

Figure

1: System structure.
ffl VSUC guarantees that under certain conditions, it ensures continuous, jitter free service for
clients, once they have been admitted. (We will make the conditions precise in Theorem 4.1).
ffl VSUC also guarantees (again under certain conditions), that no client is denied service for
arbitrarily long (cf. Theorem 4.2).
ffl VSUC reacts to client events, as well as system events in polynomial time.
System Architecture
Throughout this paper, we will use the term video block (or just block) to denote a video segment.
We will assume that the size of a block is arbitrary, but fixed. In other words, one VoD application
may choose a block to be of size frames, while another may consider it to be of size 60 frames. As
our video data is stored on disk, this means that the start of each video block is located on a single
page of any disk that contains the block.
As data is laid out on a collection of disks, we will assume that this collection of disks is partitioned
into disjoint subsets DC 1
We will furthermore assume that all disks in DC i are homogeneous
(i.e. have identical characteristics) and a single disk server DS i regulates access to the disk drives
in DC i . It is entirely possible that DC i contains only one disk, but it could contain more. Note
that there is no requirement that two disk collections DC need to have the same characteristics
and hence, disks in DC i may have vastly different characteristics than those in DC j - this is what
accomplishes heterogeneity.
The design of disk servers is now well known [2, 4, 11, 6, 10, 16]. In its simplest form, a disk server
is a piece of software that, given a physical disk address, retrieves the object located at that address.
In our case, disk servers DS i mediate access to a collection DC i of disks, which means that given a
disk-id and a physical disk address, the server retrieves the block located at the given disk address
on the specified disk. Figure 1 shows the structure of the system as described informally above.
In our architecture, the video server is responsible for the following tasks:
1. When an event (user event or system event) occurs, the video server must determine how to
handle the event. This is accompanied by creating a schedule to accomplish the event, and
deciding what instructions must be sent to the disk server(s) involved to successfully handle the
event. For example, for a user event play, such instructions could include: Fetch (for client
cl id) the block starting on page p of disk d. Note that the disk server does not necessarily need
to know the client's identity, cl id.
2. In addition, the video server may need to "switch" clients from one disk server to another. For
example, client cl id 1 may be being served by disk server DS 1 . If a new client cl id 20 requests a
movie (or block) that is only available through disk server DS 1
and if disk server DS 1
is already
functioning at peak capacity, then it may be possible to "switch" client cl id 1
to another disk
server (say DS 2
has the resources needed to satisfy client cl id 1
3. Third, the video server may "split" a job into smaller, manageable jobs, and distribute these
smaller jobs to different servers, which leads to better system utilization.
4. Fourth, whenever events such as disk server crashes occur, the VoD server must re-assign the
existing clients to other servers (when possible) and schedule system generated recovery events
so as to minimize the damage caused by the crash.
2.1 System Parameters
In any VoD system, the participating entities may be divided into the following components:
1. Servers: these are the disk servers that retrieve specified blocks from the relevant disks;
2. Clients: these are the processes that are making/issuing requests to the servers; and
3. Data: this includes the movie blocks laid out on the disks.
In order to successfully model a VoD system, and develop provably correct and efficient algorithms
for this purpose, we must model each of the above parameters, as well as the interactions between the
above components.

Tables

2,3, and 4 show the notations we use to denote the relevant parameters of servers, clients, and
movies, respectively.
Throughout this paper, we assume that there is a set
of movies that
we wish to store on disk. Each movie M i has bnum(M i ) "blocks". A block denotes the level of
granularity at which we wish to store and reason about the media-data. For example, a block may be
a single-frame (finest granularity) or a consecutive sequence of (100 frames). The application developer
is free to select the size of a block in any way s/he wishes, but once such a block size is selected, s/he is
committed to using the selected block size for the application. In other words, they are free to choose
their block size as they wish, but once they make the choice, they must stick to it.
Symbol Meaning
buf(i; s) The total buffer space associated with the disk server i at state s.
s) The total cycle time for read operation by the server i at state s.
s) The total disk bandwidth associated with the disk server i at state s.
s) The time-slice allocated to client j at state s by server i.
(i) The set of servers handling request by client i at state s.
s) The set of servers that contain block b of movie M i according to placement
mapping - at state s.
server client(i; s) The set of all clients that have been assigned a non-zero time-allocation
by disk server i at state s.
server status(i; s) The status flag for server i. It is true when the server is working, false
otherwise.
s) The time required for the disk server i to switch from one client's job
to another client's job at state s.
s) The buffer space needed at the server i to match the consumption rate
of client j at state s.
priority(e; s) The priority of the event e at state s.

Figure

2: Server Parameters
Symbol Meaning
s) The consumption rate of client i at state s.
s) The set of data blocks that server i is providing to client j at state s.
inuse(i; s) This set consists of 3-tuples, (j; M k ; b), it specifies that the server i is
providing block b of movie M k , to client j at state s.
active client(s) The set of all clients that are active at state s
client(m; s) The set of all clients that are watching movie m at state s
rew win(i; s) The size of rewind window for client i at state s. This means the client
can not rewind the movie more than that many blocks.
s) The size of fast forward window for client i at state s. This means the
client can not fast forward the movie more than that many blocks.
play win(i; s) The time limit for client i to access the system at state s.
pause win(i; s) The time limit for client i to pause at state s.

Figure

3: Client Parameters
Symbol Meaning
The number of blocks for a movie M i .

Figure

4: Movie Parameters
3 State Transition Model
In this paper, we will develop a state transition model that has the following properties:
ffl A state is any feasible configuration of the system, and includes information such as: which
disk server(s) are serving a client, and what service they are providing to the client, and what
resources are committed by the server to the client to accomplish the service provided.
ffl The state of the system may change with time, and is triggered by events. Events include:
Client events such as enter, exit, fast-forward, pause, rewind, play, as well as
- Server events such as server-down, server-up where a server goes "down" or comes back
"up", and
Manager events such as insert, delete. Note that manager events could either be initiated
by a human VoD system manager, or by a tertiary storage device that is staging data
onto disk (though we will not go into this possibility in detail in this paper).
3.1 What is a State ?
A system state s consists of the following components:
1. A set active client(s) of active clients at state s.
2. The current cyctime(i; s) of each server in the system.
3. The consumption rates of the active clients (cons(i; s)) in state s.
4. The time, timealloc(i; j; s), within cyctime(i; s) that has been allocated by server i to client j
in state s.
5. The locations (-(m; b; s)) of each movie block, i.e. the set of all servers on which block b of
movie m is located in state s.
6. The set of data blocks (data(i; j; s)) being provided by server i to client j in state s.
7. A client mapping - s which specifies, for each client C, a set of servers, - s (C), specifying which
servers are serving client C.
8. A set down servers(s) consisting of a set of servers that are down in state s.
9. A set insert list(s) consisting of a set of 3-tuples of the form (i; m; b) where m is a movie, b
is a block, and i is the server where this block will be inserted. (This set is used to model a set
of insertion updates that are "yet to be handled.")
10. A set delete list(s) consisting of a set of 3-tuples of the form (i; m; b) where m is a movie, b
is a block, and i is the server where this block will be deleted. (This set is used to model a set
of deletion updates that are "yet to be handled.") 3
A system state s must satisfy certain simple constraints that we list below.
1. For each server i that is not down, the sum of the time-allocations assigned to the clients being
served by that server must be less than the cycle time of the server. This is captured by the
2. If a server is processing a request for some data, then that data must be available in the server.
This is captured by the expression:
3. The sum of consumption rates of the clients being served by a given disk server must not exceed
the total disk bandwidth of the server. This is captured by the expression:
4. For each server i that is down, there is no active client. This is captured by the expression:
The above constraints specify the basic constraints that tie together, the resources of the VoD disk
server system, and the requirements of the clients.
3.2 Prioritized Events
Informally speaking, an event is something that (potentially) causes the VoD system to make a transition
from its current state to a "next" (or new) state. The study of the performance of disk servers for
multimedia applications varies substantially, depending upon the space of events that are considered
in the model. In our framework, the space of events that are allowed falls into two categories:
ffl Client events: enter,exit,pause,play,fast-forward,rewind;
ffl System events: server-up, server-down, insert, delete.
Each event has an associated integer called the priority of the event, and a set of attributes. For
example, the event server-up has an attribute specifying which server is up. Thus, server-up(2,s)
specifies that the event "server 2 is up" has occurred at state s. Likewise, the event insert has three
attributes - a server id, movie id, and a block number - specifying the server to which the event is
assigned, the movie identifier and the movie block identifier. For example, the event insert(2,m1,b1)
specifies that block b1 of movie m1 is being inserted into server 2.
The priority of an event is chosen either by the importance of the event or by the inherent attributes
of the event. For example, handling client event like play inherently implies delivering continuous
data stream to the client. If the data stream is interrupted due to any reason, then the client may
experience degradation in the quality of service. This degradation has to be avoided by choosing
appropriate priority for play event. As an example of system event, we can consider delete event.
In the case where enough disk space is not available to download hot movies, the system should be
able to make space by deleting data blocks as soon as possible. To expedite data deletion, the event
should be assigned high priority.
Before specifying how events are handled, we describe some concepts underlying our approach.
3.3 Modeling Usage Constraints
In any VoD system, the system administrator may wish to enforce some "usage" constraints. In this
paper, we do not try to force constraints upon the system. However, we do make available to the
system administrator, the ability to articulate and enforce certain types of constraints that s/he feels
are desirable for his system.
ffl Pause time constraint: A pause time constraint associates, with each client c, an upper
bound, pause win(c; s), on the amount of time for which the customer can "pause" the movie
s/he is watching. For example, suppose pause win (John Smith, s)=25. This means that as far
as the system is concerned, John Smith's pause time cannot exceed time units at state s. If
the pause window expires, then the resources allocated to him by the VoD system will be "taken
back" to satisfy other users' requests.
In general, when a customer "pauses", the server(s) satisfying the customer's request continues
to "hold" the resources which were assigned by the system. Clearly, holding such resources for
an indefinite period is not wise. The pause window specifies, for each customer, an upper bound
on the period of time for which the customer can pause the movie.
ffl Fast-forward/Rewind window constraint: In addition to pause window constraint discussed
above, each client c is associated with fast-forward and rewind window constraint which
specifies an upper bound on the number of data blocks that the client can fast-forward or rewind,
respectively. The fast-forward and rewind windows associated with client c at state s is specified
by ff win(c; s) and rew win(c; s).
ffl Play time constraint: Finally, sometimes, it might be desirable to put a restriction on the
time that a client can be serviced by the server for a request. This constraint can help to prevent
valuable resources from being taken for a arbitrary long time by irresponsible usage. Also, by
establishing the maximum time that a client can access the system for a request, every request
will eventually be satisfied by the server.
The total play time constraint for a client i is specified by play win(i; s). For example, play win
(John Smith, s)=180 says that John Smith has at most 180 time units to finish viewing the
current movie.
To client c1
read
delete m1:b1 c1 cannot rewind
m5: [b21-b40]
m4: [b01-b30]
m3: [b41-b50]
m2: [b31-b60]
m5: [b21-b40]
m4: [b01-b30]
m3: [b41-b50]
m2: [b31-b60]

Figure

5: Deletion of a block
3.4 Update Boundaries
Suppose s is a system state (at some arbitrary point in time) and j is a client being served by a server
i. The state s contains a data tuple specifying what data is being provided to the client by that server.
For example, consider the situation described in the example of Section 3.1. In that example, in the
state shown, server 1 is presenting blocks b2 and b3 of movie m1 to client c 1
Now, suppose the system administrator wishes to delete block b1 of movie m1 on server 1. Figure 5
shows this situation. While the system manager has the ability to make the request at any time, the
precise time at which the request is actually scheduled (i.e. the precise time at which deletion of the
block is scheduled) must take into account, the existing clients watching that movie w.r.t. the server in
question. In this case, the question that needs to be addressed is: What happens if the client c 1
wishes
to rewind to b1? If the deletion is incorporated immediately upon receipt of the deletion request, then
the rewind request of the client will be denied - a situation that may or may not be desirable. Thus,
at any given point in time, each client has an associated rewind boundary associated with each server,
specifying "how far back" that server can support a rewind request issued by the client. The rewind
boundary may change with time. Rewind boundary, and its dual concept, fast-forward boundary, are
defined below.
Definition 3.1 (Rewind Boundary) The rewind boundary of a movie m w.r.t. server i in state s
is defined as follows:
Rewind Boundary(m,s)
If the above set over which the min is performed is empty, that is, movie client(m,s) is empty,
then Rewind example, let us return to the movie m2 at server 2 and the state s in
1. client c 5
is reading block b4 of movie m2;
2. client c 6
is reading block b3 of movie m2;
block being read by c5
block being read by c6
rewind boundary
rewind window for c5
rewind window for c6
this block can be updated
(= min of the two above boundaries )

Figure

Rewind boundary computation
3. no other client is reading movie m2 (exactly what they are doing is not pertinent for this
example).
If the rewind window for client c5 is 2, and that of client c 6
is 1, then the rewind boundary associated
with server 2, movie m2 and state s is given by
2:
Let us try to see why this is the case, and what this statement means. (Figure 6 illustrates this
reasoning).
ffl Two clients, viz. c 5
, are reading (parts of) movie m2 from disk server 2. If we try to update
the copy of movie m2 residing on disk server 2, the only clients who can be affected (in the
current state) are therefore clients c 5
and c 6
Client c 5
is currently reading block b4 and his rewind window is of length 2, which means he can
only go "back" 2 blocks in the movie by executing a rewind command. Effectively, this means
that he cannot access any blocks before block b2.
ffl Likewise. client c 6
is currently reading block b3 and his rewind window is of length 1, which
means he can only go "back" 1 block in the movie by executing a rewind command. Effectively,
this means that he cannot access any blocks before block b2.
ffl As the minimum of these two blocks is b2, this means that neither client has read access to block
b1 in this state.
ffl Thus, if we wish to update block 1 which lies "below" this rewind boundary, then this is "safe."
An analogous situation occurs w.r.t. fast forward boundaries which are defined as stated below.
c3's ff_window
c2's ff_window
c4's ff_window
c1's ff_window
current reading block13

Figure

7: Fast forward boundary computation
Definition 3.2 (Fast Forward Boundary) The fast forward boundary of a movie m in state s is
defined as follows:
FF Boundary(m,s)
If the above set over which the max is performed is empty, that is, movie client(m,s) is empty,
then FF example, consider the single disk server in Figure 7. This disk server, i, contains several
movies, but only one of these, viz. movie m4 is shown in the figure. Blocks 1-5,7-20 of this movie are
available on the disk server i. Suppose that in state s, we have four clients watching this particular
movie (other clients may be watching other movies) and that the blocks these clients are watching
and the fast forward windows of these clients are as given below:
Client Block being watched ff win
Then, the fast forward boundary is given by:
FF
This means that only blocks 13-20 of the movie may be updated at this point of time.
The primary use of rewind boundaries and fast forward boundaries is to ensure that when an update
request is made by the system manager, that the users viewing the application have the flexibility to
rewind or fast forward, within the limits of their fast forward/rewind boundaries. Notice that it is not
always possible to guarantee this. For example, in figure 7, if client c 1
wishes to fast forward to block
6, there is no way to satisfy this request without switching him to another disk server, because the
disk server in figure 7 does not have block 6.
With these definitions in mind, we are now ready to define how to handle events.
Handling Events
In this section, we provide detailed algorithms for handling events. We will first provide an abstract,
declarative specification of what constitutes an appropriate way of handling events. Then, we will
provide algorithms to successfully handle events.
4.1 Optimal Event Handling: Specification and Semantics
Suppose s is a valid state of the system, and e is an event that occurs. In this section, we will first
specify what it means for a state s 0 to handle the event e occurring in state s. This will be done
without specifying how to find such a state s 0 . We will later provide algorithms to handle such events.
Definition 4.1 (Event Handling) State s 0 is said to handle event e in state s iff one of the following
conditions is true:
1. New clients: [e =New client c enters with a request for movie m:]
2. Old clients: [e =Old client c exits the system]
3. Continuing clients:
(a) (e =Continuing client c watches, in "normal viewing" mode, block b of movie m)
(b) (e =Continuing client c pauses)
(c) (e =Continuing client c fast forwards from block b to block b
(d) (e =Continuing client c rewinds from block b to block
4. Server status event:
(a) (e =disk server i crashes)
(b) (e =disk server i comes back "up")
rewind windowforward window
rewind ff
boundary

Figure

8: Example of deferred updates
5. Update event status:
(a) movie m from server i)
delete list(s 0 ))).
The handling of update events requires some intuition. Let us suppose, that we have a movie containing
100 blocks which is stored, in its entirety, on one disk server, and we have 2 clients c 1
who are
watching the movie, via this server. Let us say that
is watching block 45, and c 2
is watching block
50, and each of them is consuming 1 block per time unit (just to keep things simple). Let us further
say that the system manager now wishes to update the entire movie, replacing old blocks by new
ones (which may be viewed as a simultaneous insert and delete). Additionally, both clients c
have
rewind windows and fast forward windows of 5 blocks each. Figure 8 shows this situation.
ffl At this stage, the rewind and fast forward boundaries for this movie are 40 and 55, respectively.
ffl This means that blocks may be safely updated right away (assuming
that enough bandwidth is available).
ffl The blocks b such that 40 - b - 55 can only be updated later, i.e. the updating of these blocks
must be deferred.
ffl For example, after one time unit, block 40 can be updated. After 2 time units, block 41 can be
updated, and so on.
The skeptical reader will immediately wonder whether this definition allows us to postpone update
events for an arbitrarily long time. The answer is that as stated above, update events could get
deferred for ever. To avoid this situation, and to also assign different priorities to different clients, we
now introduce the notion of priority. Associated with each event (client initiated or system initiated,
or deferred) is a priority. The higher the priority, the more important the event. In particular, if e is
an update event, and e is deferred, then for each time unit that e is updated, we must "increment"
e's priority by a factor ffi e . Thus, different events can have different associated ``prioritization steps''
which may be selected by the system manager, based on the importance of the event as determined
by him/her. What this means is that the priority of an update events "gradually rises" till it can be
deferred no longer. We discuss this scheme in detail below, and also show how the same idea applies
to priorities on other (non-deferred) events.
4.2 Priority Scheme for events
Whenever an event occurs, that event is assigned an initial priority, either by the system, or by the
system administrator. The system maintains a list of default priority assignments. In the event of a
different priority assignment being made by the system administrator, then the latter overrides the
former.
Integers are used to represent "initial" priority assignments, though as we shall see, "non-initial"
priority assignments may be real-valued. The precise integers used for initial priority assignment are
not really important. What is more important is the relative priority ordering.
Initial Priority Assignments: Figure 9 shows the initial priority assignments. The
rationale for these assignments is discussed below.
1. System events have the highest priority. The reason for this is that a server crash, or a server
coming "back up" are events that are hard to control. It is not possible, for instance, to defer or
delay a crash. If it occurs, the system must transition to a new state that "handles" the crash
as best as possible.
2. Next, existing clients already being served by the system must have the highest priority. The
reason for this is that the VoD system has made a commitment to serve these clients well, and
it must try to honor these commitments. However, each existing client may "spawn" different
events, including exit, pause, play, fast forward, and rewind. Each of these events has a
different priority.
(a) The highest priority is assigned to events that exit. Processing an exit event early is
desirable in general, because this can be done very fast, and furthermore, this frees up
resources that may be used to satisfy other clients (continuing clients, as well as potential
new clients).
(b) The next highest priority in this class is assigned to pause events because: first these
events request no new resources (and hence, they can be satisfied immediately) and second,
because of the pause window, these events may lead to future exit events that do in fact
(c) The next highest priority in this class is assigned to play events. The reason for this is
that in most cases, play events are relatively easy to satisfy as they merely require that the
next block of the movie be fetched, and in most cases, the next block will be on the disk(s)
that are already serving the client.
(d) The last two events in this category, with equal priority, are rewind and fast forward.
These events may require substantial "switching" of clients (i.e. a client may be switched
from its current server to another, because when blocks are skipped, the current server no
longer has blocks that are several "jumps" ahead of the block currently being scanned.
3. New clients who just entered the system or has been waiting for service have the lowest priority
among user events. The reason for this is that once the video server started to serve a client,
that service should be continued with minimal disruption. But, in the case of new clients, it
is reasonable to expect some delay before the service starts. However, this shouldn't cause
new clients to wait infinitely. In this paper, this situation is handled by increasing the priority
incrementally.
Event Type Event Priority
System Server down 9
System Server up 9
Client (old) Exit 7
Client (continuing) Pause 6
Client (continuing) Play 5
Client (continuing) Fast - Forward 4
Client (continuing) Rewind 4
Client (enter) Enter 3
Manager Delete 2-7
Manager Insert 1

Figure

9: Initial assigned priorities for different events
4. Of the system events, the delete event has the highest priority. The reason for this is that
delete events can be accomplished by a very simple operation - just remove the pointers to the
appropriate blocks. In contrast, insert events require greater resources (e.g. disk bandwidth is
needed to write onto the disk).
Priority Steps: Suppose an update request is received for block b of movie m in server i. Further-
more, suppose rwb and fwb denote, respectively, the rewind boundary, and the fast forward boundary
associated with the current state. It is not difficult to see that we must have rwb - ffb. The update
cannot be carried out immediately if rwb - b - ffb. As a consequence, we might need to defer the
update. However, as mentioned above, deferring the update might cause the event to be indefinitely
delayed.
One possible way to avoid this is to assign higher priority to update events than client events, so
that they can be handled first. The problem here is that this might cause the continuous streams to
experience interruption. To handle update events eventually as well as to minimize their effect on continuous
streams, we define priority-step. The priority step ffi u is specified by the system administrator
for the update request u. ffi u is a non-negative real number, and its interpretation is as follows:
is the current state (in which the update u occurs with the priority p shown in

Figure

9 (p must be either 1 or 2).
are states that occur, consecutively after s 0
, all of which defer update u.
ffl Then the priority p i of the update event u in state s i is (p
Thus, for example, suppose u is a deletion request, and the system manager assigns a step of 0:2
to u. Then, after 6 state changes (i.e. in state s 6
), the priority of this update will be 3:2, which would
exceed the priority of a new event (which is occurring in that state. What this means is that if a
new client enters the system in state s 6
, and requests a movie, then the server in question would be
asked to consider the higher priority update request u, as opposed to serving the customer.
By making the step size small, the system manager can allow a greater period of time to elapse
before making the update have higher priority over new clients. For example, had the system manager
set ffi u in the above example to 0:002, then 501 state changes would have to occur, before update u's
priority exceeded that of a new client.
Furthermore, the system manager does not have to specify the same priority step for each update.
Different updates can have different associated priorities, as would be expected in most real life systems.
We are now ready to give an algorithm that manipulates the priorities, such as those shown in

Figure

9, and the above priority steps, to handle events that occur at any given point in time.
Video Server with Updates and Crashes (VSUC) Algorithm
main HandleEvents ( NewEvents, OldEvents )
f
set of events that can't be scheduled in this cycle */
set of client events that have been scheduled successfully */
While ( !timeout and EvtList
get the first event in EvtList ;
switch
f
case
case
case play, rewind, fast-forward : handleContEvents ( evt )
case pause : handlePauseEvents ( evt )
case
case enter : handleEnterEvents ( evt )
case insert: handleInsertEvents ( evt )
case delete: handleDeleteEvents ( evt )
increase priority of each event in EvtList by
merge events from EvtList and WaitList ;
return
procedure HandleServerDownEvents ( evt )
for each data block b i in crashed server do
update placement mapping so that b i
is not visible ;
for each event e i
in crashed server do
insert e i
into EvtList preserving the sorted order ;
procedure HandleServerUpEvents ( evt )
f
for each data block b i
in recovered server do
update placement mapping so that b i
is visible ;
procedure HandleExitEvents ( evt )
f
release resources and data structures allocated for evt ;
procedure HandleContEvents ( evt )
f
set of blocks necessary for servicing evt ;
/* depending on event type, the way blocks are read from disks can be */
/* different. For example, in play event, certain number of continuous */
blocks should be read, but in rewind(ff) event, some intermediate blocks */
/* can be skipped to match the speed */
if ( servers that have been assigned to evt contain all blocks in Blocks )
f
update the data component of evt ;
insert evt into DoneList ;
return
set of servers that contain all blocks in Blocks ;
placement mapping error */
f
/* make evt considered after block insertions */
decrease evt's priority by
insert evt into EvtList preserving the sorted order ;
return
set of servers in DServers satisfying resource constraints ;
f
if ( evt's priority has been decreased previously )
f
Finished
while ( Svlist 6= ; and !Finished ) do
f
select one server randomly from Svlist ;
event e is served by s and there exists s 0 (6=s) that satisfies e
while ( Switchables 6= ; and !Finished ) do
f
select one event randomly from Switchables ;
if ( evt can be served using the resources that will be released from e 0 )
f
release resources from e 0 and update resource allocation of s ;
allocate resources to evt and update resource allocation of s ;
allocate resources to e 0 and update resource allocation of s
put evt into DoneList ;
Finished
f
/* make evt scheduled prior to other clients in next cycle; */
increase evt's priority by ffi 0
evt
insert evt into WaitList ;
else
f
/* make evt considered after scheduling other normal continuing clients */
decrease evt's priority by ffi ''
evt
insert evt into EvtList preserving the sorted order ;
else
f
for each server s i
in RServers do
f
for the specified criteria ;
f
allocate resources to evt from
update resource allocation of
insert evt into DoneList ;
procedure HandlePauseEvents ( evt )
f
yield disk bandwidth to update events for next cycle ;
keep the other status unchanged ;
procedure HandleEnterEvents ( evt )
f
/* enter event can be handled in a way similar to handling continuous events. */
/* The difference is that in the case of enter events, resources have not */
/* been assigned previously. Therefore, checking if already assigned server */
/* can handle the event is not necessary for enter events. */
procedure HandleInsertEvents ( evt )
f
s evt
server that data block is inserted into ; /* specified in evt */
the size of data that is inserted into s evt
data size that server s evt
can handle using available resources ;
f
allocate resources to evt ;
update resource allocation of s evt
by Dsize ;
update placement mapping information of s evt
else
f
Dsize can't be inserted in its entirety */
allocate resources to evt ;
update resource allocation of s evt by Msize ;
reduce evt's data size by Msize ;
increase evt's priority by
insert it into WaitList ;
procedure HandleDeleteEvents ( evt )
f
number that is deleted ;
calculate the rewind and fast forward boundary of the movie ;
rewind boundary or b evt ? ff boundary )
delete b evt
and update placement mapping information ;
else
f
/* evt is deferred to next cycle */
increase evt's priority by ffi evt
insert it into WaitList ;
It is easy to prove that the VSUC algorithm described above has a number of nice properties, as
stated in the theorems below. An informal description of these properties is as follows:
ffl Under certain reasonable conditions, clients who have already been admitted to the system experience
no jitter, independently of what other events occur. This result applies when (1) if the
placement mapping is "full" (i.e. either the entire movie is available through a server, or none
of it is), and (2) when the client watches a movie entirely in "normal" viewing mode, and (3) no
server outages occur.
ffl Every event eventually gets handled as long as servers that go "down" eventually come back "up."
ffl The VSUC algorithm runs in polynomial time, i.e. if the current state is s and if ev is the set
of events that occur, then a new state s 0 (together perhaps with deferred events) is computed in
polynomial time.
Theorem 4.1 (Continuity of Commitments) Suppose s is the current state of the system, and
C i is a continuing client in state s who is watching movie m in "normal" mode. Furthermore, suppose
1. movie m is contained in its entirety in each server sv 2 - s (i) and
2. no server in - s (i) goes "down" at this time and
3. for all updates u (before client C i entered the system,) that were deferred when client C i enters,
pr
where pr u is the priority of the update u when client C i enters the system,
ffi u is the priority step associated with the update, and ffi C i
is the priority step associated with C i .
4. for all updates u (before client C i entered the system,) that enter the system after client C i
enters, newpr
where newpr u is the priority of the update u when it enters
the system.
Then client C i 's movie request event will be satisfied by the VSUC algorithm.
Proof Sketch. In the VSUC algorithm, the only event that diminishes the system's resources and
that has a higher priority than a continuing client is a server down event or a deferred update event.
However, by the assumption in the statement of the theorem, no servers serving client C i go down,
and hence, the highest priority events are either deferred updates or continuing clients.
Suppose a server sv is serving client C i 's request (in part or in full). If no deferred events occur,
then the same server can continue servicing client C i 's request for ``next'' blocks. However, if deferred
events occur, then there are two possibilities:
1. Suppose the deferred update u was requested before client C i entered the system. As pr u - 5
and as ffi
, it follows that throughout the normal playing of the movie, client C i 's priority
is higher than that of the update u. Thus, server sv continues to serve client C i without allowing
deferred events to obtain priority over the client C i .
2. On the other hand, if the deferred update was requested after client C i entered the system, then
client C is guaranteed to obtain priority over the update because newpr
Hence, client C i can continue to be served by server sv. 2
The above theorem has important implications for admission control, both of new clients and of
new updates.
ffl Client Admission: To guarantee continuity of service, a new client C i should be admitted to
the system only if for all deferred updates u that need to be handled when client C i enters the
system, we must know that pr u - 5 and ffi
ffl Update Admission: To guarantee continuity of service to existing clients, a new update u
should be admitted to the system only if newpr
Theorem 4.2 (All update events get handled eventually) Suppose s is the current state of the
system and ev is any update event that requires a set SV of servers. Further suppose that for all times
t ? now and all servers in SV , if there exists a time t 0 ? t at which one or more servers in SV go
down, then there exists a time t ? ? t 0 at which all servers in SV come back up. Then: for any update
event ev that occurs now, there exists a time t ev - now such that ev gets handled at time t ev .
Proof Sketch. If update event ev does not get handled now, then, as in each execution of
the VSUC algorithm, event ev's priority strictly increases till it exceeds 7, at which point t 0 in time,
it will be handled unless one or more servers that are needed to service event ev are down. By the
restriction in the statement of the theorem, there exists a time t ? ? t 0 at which all servers in SV are
"up" simultaneously. We are guaranteed that this event will be handled latest at time t ? . 2
Theorem 4.3 Suppose ev(t) is a set of events that occur at time t. The time taken for the the VSUC
algorithm to terminate is polynomial in the sum of the number of events in ev(t) and the number of
deferred events.
Proof. It follows immediately that each function call in the main algorithm runs in time polynomial
w.r.t. the above sum. 2
5 Experiments
5.1 Crash Handling vs Survival rate
Simulation experiments of the suggested VoD architecture were carried out. As we mentioned above,
the video server consists of multiple disk servers with possibly different relative performance character-
istics. The performance characteristics of disk servers are defined from 1(the lowest) to 4(the highest).
Three disk server configurations considered in the experiments are homogeneous servers with highest
performance characteristics, homogeneous servers with lowest performance characteristics, and
heterogeneous servers with different performance characteristics [3].
In the following experiments, we examined the resilence of the video server against disk server
crashes under different disk server configurations, i.e., how well the video server performs when crashes
occur. The number of disk server crashes and crash time were generated randomly. We assumed that
the crash recovery time is uniform. After the recovery time, the disk server would be available again
for use. To compare the resilience of the video server, we repeated same experiment with different
frequency of the server crashes, measuring average number of continuing clients after crashes.

Figure

shows the effect of handling server crashes on the number of continuing clients. Regardless
of server configuration, the system could support more streams with crash handling than without
crash handling. However, depending upon the performance characteristics of the servers involved, the
number of continuing clients that could be supported varied. The most notable improvement was
shown in the case of the homogeneous server with highest performance characteristics.
As the frequency of disk crashes increases, the system will experience much more difficulty scheduling
clients because resources and video data at the crashed servers are not available during crash
recovery.
Crash Handling
Handling
Effect of Server Crashes on Average Number of Continuing Client
Probability of Server Crash
Average
Number
of
Continuing
Client
Heterogenous
Homogenous-low
Homogenous-high

Figure

10: Effect of the disk server crashes.2040608010012040 70 100 130 160 190 220 250 280 310 340 370 400 430 460 490 520 550 580
Survival
percentage
Period of server crashes
"Homogeneous-high"
"Homogeneous-low"
"Hetergeneous"

Figure

11: Effect of server crash rate on survival rate.
1 Number of Video Clips 800
minutes video 400
minutes video 200
minutes video 100
2 Size of Video Segment 10-80 minutes
3 Size of Block 0.2 seconds' compressed video data
4 Number of Requests 800-2000
Request Pattern Based on actual data referenced in [5]
6 Number of Disk Servers
7 Types of Disk Servers Buffer / Disk bandwidth
Group 3 32MB / 16MB
Group 4 16MB / 8MB
8 Buffer size Avg. 50 MB per server
9 Disk Bandwidth Avg. 20 MB combined per server

Table

1: Parameters used in simulation
To measure how many clients can continue even after server crashes, we define survival rate as the
ratio of clients who can continue to be served to the total number of clients in the system when crash
occurs. Figure 11 shows that homogeneous disk servers showed a stable survival rate with respect to
disk crashes. However, heterogeneous disk servers showed a noticeable variation in the survival rate.
In the next experiment, we used different disk server configurations and examined the effect of
crashes on disk servers with different performance characteristics. The request pattern for the video
data is same as above. Table 1 shows several parameters related to the experiment.
For the experiment, we used four different types of disk servers. Servers with the highest performance
characteristics belong to group 1 and servers with the lowest belong to group 4. Under normal
operation, servers with higher performance characteristics store more video segments and support
more concurrent streams than those with lower performance characteristics. Therefore, the effects of
disk crashes will vary depending on the performance characteristics of the server that crashes.

Figure

12.a to 12.d show how many clients on the crashed server continue to be served even
after disk crashes (under varying system load). For the comparison, we showed both the number of
continuing clients with crash handling and without crash handling. Here, "after no crash handling"
means that the streams on the crashed server(s) will be discontinued unconditionally.
In these figures, the difference between the top line and the bottom line is the number of clients
on the crashed disk. On the average, our crash handling VoD server algorithm can satisfy about half
the clients affected by the crash by rescheduling their streams to other available servers.
number of clients before server crash
number of clients after crash handling
number of clients after no crash handling
Continuing Clients Before/After Server Crash in Group1
Clients in the system
Number
of
continuing
clients
number of clients before server crash
number of clients with crash handling
number of clients after no crash handling
Continuing Clients Before/After Server Crash in Group2
Clients in the system
Number
of
continuing
clients
(a) Continuing clients in Group 1 (b) Continuing clients in Group 2
number of clients before server crash
number of clients after crash handling
number of clients after no crash handling
Continuing Clients Before/After Server Crash in Group3
Clients in the system
Number
of
continuing
clients
number of clients before server crash
number of clients after crash handling
number of clients after no crash handling
Number Of Continuing Clients Before/After Server Crash in Group4
Clients in the system
Number
of
continuing
clients
(c) Continuing clients in Group 3 (d) Continuing clients in Group 4

Figure

12: continuing clients after server crash
5.2 Performance vs Segmentation
In this experiment, we examined the performance of the video server for different segmentations -
here a segment refers to a continuous sequence of video blocks. We assumed that video objects are
divided into several segments of equal size. These segments are placed in the disk servers in a way
that adjacent segments should be placed in the different disk servers (otherwise multiple segments are
merged into one large segment on a single server). Video segments were placed on the servers in a
manner proportional to the size of the disk storage available, i.e., the probability that a video segment
is placed on a disk having capacity 5 GB is 5 times the probability that same segment is placed on a 1
GB disk. Under this segment placement scheme, any two disk servers with adjacent segments should
be synchronized for the seamless display of video stream. That is, as soon as a segment is consumed
from the first server, the next segment should be delivered from the second server without delay. If
the second server cannot deliver next segment in time, then clients may experience deterioration in
quality of service. We will show later that this situation can be relaxed if we increase buffer space for
each stream.
number of segments: 1
number of segments: 2
number of segments: 4
number of segments: 8
800 1000 1200 1400 1600 1800 2000 2200200600100014001800Normal Continuing Clients Without Any Glitch
Clients in the system
Number
of
clients
who
experienced
no
glitch number of segments: 1
number of segments: 2
number of segments: 4
number of segments: 8
1000 1200 1400 1600 1800 2000 220010305070Average Interrupt Time Experienced by Clients
Clients in the system
length
in
cycles
(a) Number of continuing clients (b) Average blocked time
number of segments: 1
number of segments: 2
number of segments: 4
number of segments: 8
800 1000 1200 1400 1600 1800 2000 22002060100140180Average Initial Response Time
Clients in the system
Response
time
in
cycles
number of segments: 1
number of segments: 2
number of segments: 4
number of segments: 8
800 1000 1200 1400 1600 1800 2000 2200300500700900Number Of Updates Executed
Clients in the system
Number
of
updates
executed
(c) Average initial waiting time (d) Number of updates executed

Figure

13: experiment results

Figure

13.a shows how many streams will experience intermediate stream delay due to server
switches for retrieval of adjacent segments. When video objects are stored in their entirety, then there
is no need for server switches for the ongoing streams. But, as the number of segments in a movie is
increased, the number of clients experiencing intermediate delays due to server switch increases.
In

Figure

13.b, we examined average intermediate stream delay experienced by the clients. It
shows that once video objects are segmented, the average stream delay decreases as the number of
segments increases. This is due to the fact that with smaller segments, clients stay at the server for
a shorter time than larger segments. With shorter stays at the servers, resource availability of disk
servers become flexible and therefore server switching can be done more easily and frequently.
From figure 13.a and 13.b, we might conclude that storing video objects in its entirety on one disk
server is the best scheme. But two other criteria show that this scheme has some disadvantages as
well.

Figure

13.c shows the server response time specifying how long each client has waited till the first
frame of the video object was displayed. Under a moderate to a large number of clients in the system,
the system response time increases sharply as the number of segments decreases. Also, the number of
updates done during the simulation increases as the number of segments increases. Figure 13.d shows
how many update requests have been done during the simulation.
Furthermore, as mentioned earlier, intermediate stream delays due to server switches can be compensated
to a certain degree if we increase buffer space for streams. From figure 13.b, average stream
delay is less than cycles when the total number of clients is 1800. Therefore, as we increase the
buffer space for streams, the number of clients experiencing actual intermediate display delay will be
reduced.
6 Conclusions
Though there has been extensive work on handling disk crashes most such work has occurred in the
area of recovery of data on the crashed disk. Likewise, though there has been extensive work on
developing systems support for handling VCR-like functions in video servers, this work has ignored
two possibilities:
1. That during the operation of such a video server, updates might occur. The problem of handling
such updates has not been adequately addressed in the literature.
2. Similarly, during the operation of such a video server, one or more servers might crash and/or
otherwise become inaccessible. This means that any clients currently being served by those
servers must be satisfied in some other way. To date, there has been no formal theoretical work
on extending VoD servers to handle this possibility.
The primary aim of this paper is to provide a formal model of VoD systems that is capable of
handling such events, as well as to provide the VSUC algorithm that can neatly handle the variations
in resource availability that may arise as a consequence of such events. In particular, the VSUC
algorithm has many nice properties that, to our knowledge, have been proposed for the first time.
ffl First, the VSUC algorithm guarantees that under certain reasonable conditions, users to whom
the VoD server has already made commitments, will experience no disruption or jitter in service
as long as they watch the movie in "normal" mode.
ffl Second, the VSUC algorithm guarantees (again under certain reasonable restrictions) that no
request made by a continuing client will be denied service "forever", i.e. it will eventually be
handled.
ffl Third, the VSUC algorithm reacts to both user events and system events, in polynomial time.

Acknowledgements

This work was supported by the Army Research Office under Grants DAAH-04-95-10174 and DAAH-
04-96-10297, by ARPA/Rome Labs contract F30602-93-C-0241 (ARPA Order Nr. A716), by Army
Research Laboratory under Cooperative Agreement DAAL01-96-2-0002 Federated Laboratory ATIRP
Consortium and by an NSF Young Investigator award IRI-93-57756. We are grateful to Dr. B.
Prabhakaran for a careful reading of the manuscript and for making many useful comments and
critiques.



--R

Staggered Striping in Multimedia Information Sys- tems
Fault Tolerant Design of Multimedia Servers
An Event-Based Model for Continuous Media Data on Heterogeneous Disk Servers
Support for Fully Interactive Playout in a Disk- Array-Based Video Server
"A Generalized Interval Caching Policy for Mixed Interactive and Long Video Workloads"
Toward Workload Characterization of Video Server and Digital Library Application
A Distributed Hierarchical Storage manager for a Video-on- Demand System
On Multimedia Repositories

Issues in the Design of a Storage Server for Video-On-Demand

A Case for Redundant Arrays of Inexpensive Disks
An Introduction to Disk Drive Modeling
Disk Striping
A Distributed
Design and Performance Tradeoffs in Clustered Video Servers.
Designing and On-Demand Multimedia Service
Optimizing the Placement of Multimedia Objects on Disk Arrays
Scheduling Algorithms for Modern Disk Drives
--TR
constraints;priority and optimal handling;video server;updates;disk crashes