Scalable Distributed Video-on-Demand: Theoretical Bounds and Practical Algorithms

Laurent Viennot; Yacine Boufkhad; Fabien Mathieu; Fabien De Montgolfier; Diego Perino

inria-00270406, version 2

Scalable Distributed Video-on-Demand: Theoretical Bounds and Practical Algorithms

Laurent Viennot () ¹, Yacine Boufkhad () ^1, 2, Fabien Mathieu () ^1, 3, Fabien De Montgolfier () ^1, 2, Diego Perino ()^a^, 1, 3

N° RR-6496 (2008)

Résumé : We analyze a distributed system where n nodes called boxes store a large set of videos and collaborate to serve simultaneously n videos or less. We explore under which conditions such a system can be scalable while serving any sequence of demands. We model this problem through a combination of two algorithms: a video allocation algorithm and a connection scheduling algorithm. The latter plays against an adversary that incrementally proposes video requests.

a – France Telecom R&D - Orange Labs
1 : GANG (INRIA Rocquencourt)
CNRS : UMR7089 – INRIA – Université Paris VII - Paris Diderot
2 : Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA)
CNRS : UMR7089 – Université Paris VII - Paris Diderot
3 : France Télécom Recherche & Développement (FT R&D)
France Télécom

inria-00270406, version 2
http://hal.inria.fr/inria-00270406
oai:hal.inria.fr:inria-00270406
Contributeur : Rapport De Recherche Inria <>
Soumis le : Mardi 8 Avril 2008, 08:59:00
Dernière modification le : Mardi 8 Avril 2008, 09:16:44

Voir la fiche détaillée

Documents associés

PS :

PDF :

arXiv : 0804.0743

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Rapports</head>
<biblStruct type="report" xml:id="inria-00270406"><monogr>
<author><persName><forename>Laurent</forename><surname>Viennot</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">GANG</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7089</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Paris VII - Paris Diderot</orgName>
</affiliation>
</author>
<author><persName><forename>Yacine</forename><surname>Boufkhad</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">GANG</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7089</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Paris VII - Paris Diderot</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIAFA</orgName>
<orgName type="team">Laboratoire d'informatique Algorithmique : Fondements et Applications</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7089</orgName>
<orgName type="institution">Université Paris VII - Paris Diderot</orgName>
</affiliation>
</author>
<author><persName><forename>Fabien</forename><surname>Mathieu</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">GANG</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7089</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Paris VII - Paris Diderot</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">FT R&D</orgName>
<orgName type="team">France Télécom Recherche & Développement</orgName>
<country>FR</country>
<orgName type="institution">France Télécom</orgName>
</affiliation>
</author>
<author><persName><forename>Fabien</forename><surname>De Montgolfier</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">GANG</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7089</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Paris VII - Paris Diderot</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIAFA</orgName>
<orgName type="team">Laboratoire d'informatique Algorithmique : Fondements et Applications</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7089</orgName>
<orgName type="institution">Université Paris VII - Paris Diderot</orgName>
</affiliation>
</author>
<author><persName><forename>Diego</forename><surname>Perino</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Rocquencourt</orgName>
<orgName type="team">GANG</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR7089</orgName>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université Paris VII - Paris Diderot</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">FT R&D</orgName>
<orgName type="team">France Télécom Recherche & Développement</orgName>
<country>FR</country>
<orgName type="institution">France Télécom</orgName>
</affiliation>
</author>
<title type="main" level="m">Scalable Distributed Video-on-Demand: Theoretical Bounds and Practical Algorithms</title><title type="main" level="m">Scalable Distributed Video-on-Demand: Theoretical Bounds and Practical Algorithms</title><imprint><biblScope type="publicationDate">2008-00-00</biblScope><biblScope type="pp">19</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00270406</idno><idno type="HALFile">http://hal.inria.fr/inria-00270406/PDF/RR-6496.pdf</idno></biblStruct>
</listBibl>
</listBibl>