Random redundant storage for video on demand

In een zogenaamd ‘video-on-demand’-systeem kunnen klanten op ieder moment een film naar keuze opstarten. De films liggen opgeslagen in een centrale ‘server’, en worden bij aanvraag over een extern netwerk naar de klant gestuurd. De server voorziet een groot aantal klanten tegelijk van hun eigen, continue stroom van video data. In een video server onderscheiden we drie delen: een verzameling harde schijven (disks) waarop de video data opgeslagen ligt, een geheugen van waaruit de data het externe netwerk ingestuurd wordt, en een intern netwerk dat de disks verbindt met het geheugen. Als een klant een film opstart krijgt hij een deel van de het geheugen als persoonlijke buffer toegewezen. Vanuit deze buffer wordt de video naar de klant gestuurd. De films worden opgesplitst in blokken van constante grootte en deze blokken worden op de disks opgeslagen. We nemen aan dat de server in periodes werkt, en wel als volgt. Aan het begin van een periode wordt gekeken welke buffers ruimte hebben voor een volgend blok en de corresponderende blokken worden aangevraagd bij de disks. Ieder aangevraagd blok wordt toegewezen aan een disk, opgehaald, en verstuurd naar de corresponderende buffer. De volgende periode begint als alle disks klaar zijn met het ophalen van de aan hen toegekende blokken. In de server hebben we een algoritme nodig dat beschrijft hoe de data blokken worden opgeslagen op de disks en een algoritme dat de aangevraagde blokken toewijst aan de disks, waarbij de combinatie van beide algoritmen ervoor moet zorgen dat de disks effici¨ent gebruikt worden. In dit proefschrift analyseren we de werking van aselecte, redundante opslagstrategi ¨een. Van elk blok video data worden ´e´en of meer kopi¨een opgeslagen op aselect gekozen disks. Voor de aangevraagde blokken die op meer dan ´e´en disk opgeslagen liggen, moet een keuze gemaakt worden welke disks te gebruiken voor ieder blok. Dit resulteert in het volgende zogenaamde ‘retrieval’ probleem dat in iedere periode opgelost dient te worden. Gegeven is een verzameling blokken en voor ieder blok is gegeven op welke disks het opgeslagen ligt. Ken nu de blokken toe aan de disks zodanig dat de periodelengte geminimaliseerd wordt. De verwachte periodelengte geeft aan hoe effici¨ent de disks in de server gebruikt worden en is dus een maat voor de prestatie van een opslagstrategie metbijbehorend retrieval-algoritme. We beschouwen twee retrieval-problemen, die verschillen in de definitie van periodelengte. In het blok-gebaseerde retrieval-probleem (BRP) minimaliseren we het maximaal aantal blokken dat aan een van de disks is toegewezen, en in het tijdgebaseerde retrieval-probleem (TRP) minimaliseren we de daadwerkelijke eindtijd van de disk die het laatst klaar is. TRP is gebaseerd op een gedetailleerder model dan BRP. In TRP nemen we de daadwerkelijke leestijden van de blokken mee in de beslissing van toewijzing en staan we toe dat een blok gedeeltelijk van meer dan ´e´en disk opgehaald wordt. Het voordeel van het meenemen van de leestijden in het model is dat we bij het toekennen van de aangevraagde blokken aan de disks gebruik kunnen maken van de eigenschap dat magnetische schijven een hogere leessnelheid realiseren bij het lezen aan de buitenkant van de disk dan aan de binnenkant. De vrijheid om een blok in delen van meerdere disks te lezen heeft als voordeel dat het beter mogelijk is de hoeveelheid werk gelijkmatig te verdelen over de disks. Een nadeel is dat het totaal aantal verplaatsingen van de leeskoppen van de disks toeneemt. We analyseren beide retrieval-problemen met technieken uit de combinatorische optimalisering. We laten zien dat de retrieval-problemen een speciale klasse van multiprocessor planningsproblemen vormen. We modelleren BRP als een geheeltallig lineair programmeringsprobleem en laten zien dat we het probleem kunnen oplossen met behulp van een speciale ‘maximum flow’ graaf. Dit betekent dat BRP oplosbaar is in polynomiale tijd. We modelleren TRP als gemengd geheeltallig lineair programmeringsprobleem en bewijzen dat het probleem NPlastig is in de sterke zin. We beschrijven twee benaderings-algoritmen voor TRP, gebaseerd op LP-relaxatie, en een heuristiek gebaseerd op ‘list scheduling’. Met een probabilistische analyse van BRP laten we zien dat gerandomiseerde redundante opslagstrategi¨een goed presteren, in de zin dat de kans op een . Met simulaties kwantificeren we de verbetering van TRP ten opzichte van BRP. De resultaten geven aan dat TRP het mogelijk maakt de disks effici¨enter te gebruiken, met name door gebruik te maken van de eigenschap dat disks sneller kunnen lezen aan de buitenkant dan aan de binnenkant. Aan de hand van een aantal toepassingen laten we zien hoe de toegenomen disk-effici¨entie gebruikt kan worden om, bijvoorbeeld, het aantal klanten toe te laten nemen. Dit proefschrift laat zien dat aselecte redundante opslagstrategi¨een een goede keuze zijn voor video-opslag in video-on-demand-systemen. De modellen en algoritmen zijn toepasbaar op een groot scala aan toepassingen en leiden tot zeer effici¨ent disk gebruik.