COMPUTER NETWORKS RESEARCH LAB

TSP Lab

Department of Electrical and Computer Engineering, McGill University

  NAVIGATION

Home
People
Photos
 

  RESEARCH

Projects
Publications
 

  LINKS

AAPN
MITACS
McGill TSP
McGill ECE
 

  LOCAL ACCESS
Local Info
 
 

Project Descriptions Return to AAPN Projects

Video-on-Demand Server Selection and Placement
 

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).