Approximation Algorithms for Auto-Scaling Video Cloud

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


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

By

Mr. Zhangyu CHANG


Abstract:

The traffic of video-on-demand (VoD) and live streaming services fluctuates
significantly over a day. To cost-effectively serve user demand, content
providers (CPs) can deploy geo-dispersed auto-scaling servers to elastically
scale their resources with a pay-asyou- go pricing model. In this thesis, we
study some optimization problems for CPs to minimize deployment costs while
meeting quality-of-service constraints. We show that these problems are NP-hard
and propose approximation algorithms for each of them.

First, we consider a regional auto-scaling data center for VoD consisting of
multiple servers that may be activated or deactivated according to user
traffic. To minimize the number of active servers, we present AVARDO, an
approximation algorithm that jointly optimizes video allocation in servers,
active server selection at different traffic levels, and request dispatching to
one of the active servers.

To serve geo-distributed VoD users, we next consider a Netflix-like cloud
consisting of multiple geo-dispersed data centers placed close to user pools.
We present RAVO, which jointly optimizes video management (i.e., where to place
and retrieve videos) and resource allocation (i.e., how much link, storage, and
processing capacities are needed for local servers). For a large video pool, we
propose a clustering algorithm to substantially reduce computational complexity
with little compromise on performance.

Finally, we consider a multi-origin multi-channel cloud for live streaming.
This cloud pushes each video channel from its origin to all the auto-scaling
end servers demanding the channel, forming an overlay tree. We present COCOS
for overlay construction (i.e., which channels a server shall forward to the
others).

We prove the approximation ratios for AVARDO, RAVO, and COCOS. Extensive
trace-driven experiments under real-world settings validate their
near-optimality (less than 10% from the optimality). They outperform the
state-of-the-art schemes by wide margins, substantially cutting the optimality
gaps by multiple times.


Date:                   Thursday, 21 December 2023

Time:                   3:00pm - 5:00pm

Venue:                  Room 4504
                        Lifts 25/26

Chairman:               Prof. Tiezheng QIAN (MATH)

Committee Members:      Prof. Gary CHAN (Supervisor)
                        Prof. Dan XU
                        Prof. Qian ZHANG
                        Prof. Yansong YANG (ECE)
                        Prof. Jack LEE (CUHK)


**** ALL are Welcome ****