Article ID: | iaor201524343 |
Volume: | 21 |
Issue: | 4 |
Start Page Number: | 559 |
End Page Number: | 579 |
Publication Date: | Jul 2014 |
Journal: | International Transactions in Operational Research |
Authors: | Rodrguez-Bocca Pablo, Robledo Franco, Romero Pablo, Rostagnol Claudia |
Keywords: | combinatorial optimization |
We propose a deterministic fluid model to understand the trade‐offs in the design of peer‐assisted video‐on‐demand (VoD) services. There are three entities in this model: peers (or end users), seeders (altruistic users that own one or several complete video items), and cache servers that store and forward videos with a limited capacity. Peers join the network, download one or multiple concurrent video streams (possibly different video items), and abort the system when they wish. Peers are assumed to cooperate in a BitTorrent‐based fashion, governed by tit‐for‐tat and fair availability. The issue is to minimize the expected downloading times, choosing the set of video items that should be stored in each cache server. We first prove that the deterministic model is globally stable, and find closed expressions for the expected waiting times. Then, we introduce a combinatorial optimization problem (COP), whose nature is similar to the multiknapsack problem (where the items are videos, and knapsacks are related with the storage of cache servers). The problem turns out to be NP‐complete. Therefore, we heuristically address the problem following a GRASP (greedy randomized adaptive search procedure) methodology. Finally, we simulate the new caching methodology with real‐life traces taken from YouTube logs. The results suggest that the peer‐to‐peer philosophy is both stable and cost‐effective for on‐demand streaming purposes.