Open AccessDynamic Request Routing for Online Video-on-Demand Service: A Markov Decision Process Approach
Author(s) -
Jianxiong Wan,
Limin Liu,
Jianwei Guo
Publication year - 2014
Publication title -
mathematical problems in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.262
H-Index - 62
eISSN - 1026-7077
pISSN - 1024-123X
DOI - 10.1155/2014/920829
Subject(s) - markov decision process , computer science , mathematical optimization , state space , partially observable markov decision process , routing (electronic design automation) , heuristic , queueing theory , curse of dimensionality , greedy algorithm , markov process , server , markov chain , distributed computing , markov model , computer network , algorithm , mathematics , artificial intelligence , machine learning , statistics
We investigate the request routing problem in the CDN-based Video-on-Demand system. We model the system as a controlled queueing system including a dispatcher and several edge servers. The system is formulated as a Markov decision process (MDP). Since the MDP formulation suffers from the so-called “the curse of dimensionality” problem, we then develop a greedy heuristic algorithm, which is simple and can be implemented online, to approximately solve the MDP model. However, we do not know how far it deviates from the optimal solution. To address this problem, we further aggregate the state space of the original MDP model and use the bounded-parameter MDP (BMDP) to reformulate the system. This allows us to obtain a suboptimal solution with a known performance bound. The effectiveness of two approaches is evaluated in a simulation study
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom