[Back]

J. Walla:
"Exakte und heuristische Optimierungsmethoden zur Lösung von Video Server Load Re-Balancing";
Supervisor: G. Raidl, M. Ruthmair; Institut für Computergraphik und Algorithmen, 2009.

A Video-on-Demand (VoD) system usually consists of a large number of independent video servers. In order to serve a maximal number of concurrent requests with a given
number of servers the overall network load should be equally balanced among the available servers. A load balancing procedure for a VoD system relies on the prediction of the expected maximal number of parallel accesses to each video le. Based on this estimation a required number of replicas per video le and their placement on the available servers as well as an assignment of the predicted requests to these replicas should be determined.
This assignment should ensure a fair load for each server during the period of highest user interest, taking into account its share of the overall upload capacity of the VoD system.
This master's thesis gives a formalisation of the VoD load balancing problem in terms of
a combinatorial optimization problem, called Video-Server Load Re-Balancing (VSLRB).
In contrast to many works in literature this formulation incorporates minimisation of the
reorganisation costs which arise from the transformation of the current replica assignment
into the newly obtained one. An equivalent formulation in terms of a mixed integer linear
program (MIP) is given as an exact approach to solving this problem. Furthermore this
thesis describes a heuristic approach in the form of an application of Variable Neighbourhood Search (VNS) to VSLRB. This VNS features a neighbourhood structure based on cyclic exchanges of requests and a neighbourhood structure based on the MIP approach.
Tests where conducted on ten test instances of varying size. Results show that in each case the described approach is able to identify solutions with practically negligible deviations of server loads from pre-calculated target server loads.

Ein Video-on-Demand (VoD) System besteht h äu fig aus einer gro ßen Anzahl unabh ängiger
Video-Server. Um mit einer gegebenen Anzahl an Video-Servern eine m öglichst groß e
Anzahl gleichzeitiger Zugriff e bedienen zu k onnen, soll ein Ausgleich der Netzwerklast
zwischen den vorhandenen Servern erzielt werden. Das Lastverteilungsproblem in einem
VoD-System besteht darin, ausgehend von einer Sch ätzung der pro Video-Clip maximal
gleichzeitig zu erwartenden Zugriff e eine Anzahl von Replikaten jedes Video-Clips und
deren Platzierung auf den vorhandenen Servern zu ermitteln. Gleichzeitig erfolgt eine Zuordnung der gesch ätzten Zugri ffe zu diesen Replikaten, sodass f ur jeden Server des Systems entsprechend seiner Übertragungskapazit ät eine gerechte Auslastung w ährend der Phase h öchster Nachfrage erreicht wird. Diese Diplomarbeit beschreibt eine Formulierung dieses Lastverteilungsproblems als kombinatorisches Optimierungsproblem, genannt Video- Server Load Re-Balancing (VSLRB). Es ber ücksichtigt im Gegensatz zu vielen Arbeiten aus der Literatur auch die Minimierung des Reorganisationsaufwands zur Herstellung der neu ermittelten Replikatszuordnung aus der bereits bestehenden. Zur exakten L ösung dieses Problems wird eine Formulierung als gemischt-ganzzahliges lineares Programm (MIP) entwickelt. Um auch L ösungen f ur gr öß ere Instanzen dieses Problems ermitteln zu können, wird weiters eine Anwendung der Metaheuristik Variable Neighbourhood Search (VNS) beschrieben. Diese verwendet unter anderem eine Nachbarschaftsstruktur basierend auf zyklischen Vertauschungen (Cyclic Exchange Neighbourhood) und eine Nachbarschaftsstruktur, die unter Verwendung des MIP-Ansatzes durchsucht wird. Tests mit insgesamt zehn Testinstanzen von unterschiedlicher Gr öß e zeigen, dass das beschriebene Verfahren in der Lage ist, in jedem dieser F älle L ösungen mit praktisch zu vernachl ässigenden Abweichungen der Serverlasten von zuvor berechneten zu erzielenden Lasten zu ermitteln.

http://publik.tuwien.ac.at/files/PubDat_178582.pdf