Approximation Algorithms for Auto-Scaling Video Cloud

PhD Thesis Proposal Defence


Title: "Approximation Algorithms for Auto-Scaling Video Cloud"

by

Mr. Zhangyu CHANG


Abstract:

Video traffic of video-on-demand (VoD) or live streaming services has been 
observed to vary significantly within short timescale. In order to 
cost-effectively manage such traffic volume and dynamics, the content 
provider (CP) may deploy a set of geo-dispersed auto-scaling servers whose 
resources are scaled elastically according to user demands and charged in 
a pay-as-you-go manner. In this thesis, we first overview auto-scaling 
cloud and cloud computing to support video service, and then propose and 
study approximation algorithms to optimize auto-scaling cloud-based 
network for VoD and live streaming services.

We first consider a regional auto-scaling cloud-based VoD data center 
consisting of multiple servers where each server may be activated or 
deactivated according to the traffic. We present AVARDO, an approximation 
algorithm to maximize the user capacity of the active servers by jointly 
optimizing video block allocation in the servers, server selection at 
different traffic levels, and request dispatching to a server.

We then consider optimizing a geo-distributed Netflix-like VoD cloud where 
servers are placed close to user pools. We propose an approximation 
algorithm called RAVO to minimize the deployment cost by jointly 
optimizing video management (in terms of video placement and retrieval at 
servers) and resource allocation (in terms of link, storage, and 
processing capacities), subject to a certain user delay constraint on 
video access. For large video pool, we propose a clustering algorithm to 
substantially reduce the run-time complexity with little compromise on 
performance.

We finally consider optimizing a multi-origin multi-channel live streaming 
cloud that pushes each channel stream from an origin as an overlay tree 
covering only the auto-scaling end servers with local demand for the 
channel. We propose a bi-criteria approximation algorithm called COCOS to 
minimize both the deployment cost and Origin-to-End (O2E) delays, which 
can be equivalently posed as minimizing the deployment cost while meeting 
a certain maximum O2E delay constraint.

Our extensive trace-driven experiments under real-world settings validate 
that AVARDO, RAVO and COCOS are all near-optimal and outperform their 
state-of-the-art comparison schemes by a wide margin.


Date:			Monday, 15 August 2022

Time:                  	5:00pm - 7:00pm

Zoom Meeting: 
https://hkust.zoom.us/j/99469626519?pwd=Yk5HWVUxT3VnK1pkSndzUFlLMXVidz09

Committee Members:	Prof. Gary Chan (Supervisor)
 			Dr. Brahim Bensaou (Chairperson)
 			Prof. Kai Chen
 			Dr. Wei Wang


**** ALL are Welcome ****