|
Student: Frederic Thouin, Ph.D. Student
Supervisor: Prof. Mark Coates
Description: As the number of available titles and usage of
video-on-demand services is expected to grow dramatically in the next
years, many providers are planning the deployment of large-scale
video-on-demand (VoD) systems. These systems
require significant resources (bandwidth and storage) to store the videos,
distribute them to caches, and deliver them to clients. An important and
complicated task part of the network planning phase is resource allocation.
It consists of determining the location and number of resources to deploy
such that user demand is satisfied, cost is minimized, and any quality of
experience (QoE) constraints (delay, packet loss,
frame loss, or packet jitter) are respected. This operation is important
because it is often very difficult (or even impossible) to substantially
alter the chosen solution after the deployment. The main challenge is to
build sufficiently accurate models for all of the factors involved: the
available infrastructure, the network topology, the peak/average usage of
the system, the popularity of each title, and bandwidth and storage
requirements.
In the case of a distributed
video-on-demand network deployment, the resources to consider are the
equipment required at the origin and proxy video servers and for the actual
transport between each location. We assume an existing topology with a high
bandwidth capacity and focus on the equipment required at each location to
store and stream the content. A video server consists of storage devices to
cache the desired content and streaming devices to deliver the videos to
the users. The VoD equipment allocation problem
consists of determining the number of streaming and storage devices at each
location in the topology such that the demand is satisfied and the
deployment cost is minimized. A natural extension of the problem
thus involves identifying the best type of equipment to install at each
location when many models are available and there is flexibility for
variation from site to site. Therefore, we address the
problem of determining not only the number, but also the model of the VoD servers at each potential replica location.
The VoD equipment allocation problem:
We consider a metropolitan area network
with one origin server and N potential replica locations. Each cluster of clients has worst-case demand
Mi (peak usage demand) and is assigned to a potential replica
location with hit ratio hi. The hit ratio represents an estimate
of the fraction of the demand Mi served at the replica, the
other portion is served directly by the origin server.
We address the VoD equipment allocation problem of determining not only the number, but
also the model of the VoD servers at each
potential replica location. To solve this problem, we require the
specification of a set of available VoD server
models W = {wj : j = 1,...,W} where wj is a VoD server
with streaming capacity Fj Gbps, storage capacity Gj
TB and unit cost Bj k$. We define the
sets N={ni : i
= 1,...,N} and V = {vo, vi  W : i = 1,..., N} where ni
is the number and vi is the model of the servers installed at
location i. The optimization problem is expressed
as follows:
where  is the total cost of the network for a fixed set  . We impose
the following constraints:
The first constraint states that the
storage capacity at the origin must be large enough to host the entire
initial library. The second and third constraints ensure that the streaming
capacity at each location and the origin is large enough to serve the
fraction of the demand routed to this site. The fourth constraint in imposes
that the total network streaming capacity is larger than the total demand
from all locations. The fifth and last one states that the storage capacity
at each location should be large enough to ensure the estimated hit ratio.
Fig. 1: Video-on-Demand equipment allocation problem. Logical connectivity between origin, N=5 replica servers and clients. Each replica represents a potential location to install VoD equipment in the network. Clients' requests (shown as movie stream arrows) are served by replicas when possible (if content is available) or by origin. Key shows the specifications (streaming and storage capacity and price) of W=3 different VoD server models. We show the number and type of VoD servers installed at each potential location. The optimal solution can include locations with no equipment (empty square).
|
Return to AAPN Projects