Browse Prior Art Database

MMPacking: Load and Storage Balancing Algorithm for Distributed Multimedia Servers

IP.com Disclosure Number: IPCOM000117591D
Original Publication Date: 1996-Apr-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 143K

Publishing Venue

IBM

Related People

Bouloutas, A: AUTHOR [+3]

Abstract

Disclosed is a method to balance traffic (load) in a distributed server environment where video streams are distributed among a number of stations. Since different video streams are requested by clients with different rates, video stream replication is used to balance the traffic patterns of the stations; thus, the requests and I/O usage of the stations is balanced, since replication allows requests for the same video stream to be routed to different stations. This method achieves load balancing with a small degree of replication (at most N-1 replicas of video streams are created in a system with N servers).

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 38% of the total text.

MMPacking:  Load and Storage Balancing Algorithm for Distributed
Multimedia Servers

      Disclosed is a method to balance traffic (load) in a
distributed server environment where video streams are distributed
among a number of stations.  Since different video streams are
requested by clients with different rates, video stream replication
is used to balance the traffic patterns of the stations; thus, the
requests and I/O usage of the stations is balanced, since replication
allows requests for the same video stream to be routed to different
stations.  This method achieves load balancing with a small degree of
replication (at most N-1 replicas of video streams are created in a
system with N servers).

      Consider an environment as shown in the Figure, where a
distributed video server is employed to deliver video services to
clients.  The server is composed of N stations, WS(0), ..., WS(N-1),
storing a total of M different video streams, VS(0), VS(M-1), and is
connected to a total of C clients through a network as shown in the
Figure.  Clients generate requests for video streams to the server.
Video streams are requested with different probabilities:  video
stream VS sub i is requested with probability P sub i.

      Since the probabilities of video stream requests may be
different, the stations storing them may experience different traffic
patterns resulting in unbalanced traffic or I/O usage.  An important
problem is to distribute the video streams among the servers so that
all servers share an equal load, while imposing similar storage
requirements to the server stations.

      This method achieves load and storage balancing in the
distributed server by replicating a small number of video streams in
the server, and by employing a weighted scheduling algorithm to
achieve load balancing.  This results to the probability of a video
request being the same for all stations in the distributed server.
Furthermore, the number of video streams stored in each station of
the server is approximately equal to the number of streams stored in
any other station; more precisely, the difference of number of video
streams between any two stations is less or equal to two.

The problem is solved with two basic operations:
  1.  placement of video streams in server stations and replication
of
       a small subset of video streams;
  2.  weighted scheduling of client requests for the replicated video
       streams.

      Select a small number of video streams for replication in the
following fashion.  Sort the video streams in ascending order using
their corresponding probabilities, P sub i, as the key.  Denote this
ordering of the video streams as: VS sub 0, VS sub 1 , ..., VS sub
(M-1); the corresponding probabilities of request are:  P sub 0 , P
sub 1, ..., P sub (M-1) respectively.  Then, assuming an ordering of
the workstations, WS(0), ..., WS(N-1), we place the video streams in
a round robin fashion to a...