Exakte und heuristische Optimierungsmethoden zur Lösung von Video Server Load Re-Balancing

Abstract

Ein Video-on-Demand (VoD) System besteht häufig aus einer großen Anzahl unabhängiger Video-Server. Um mit einer gegebenen Anzahl an Video-Servern eine möglichst große Anzahl gleichzeitiger Zugriffe bedienen zu können, 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 Zugriffe eine Anzahl von Replikaten jedes Video-Clips und deren Platzierung auf den vorhandenen Servern zu ermitteln. Gleichzeitig erfolgt eine Zuordnung der geschätzten Zugriffe zu diesen Replikaten, sodass für 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ür 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.<br />

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 file.<br />Based on this estimation a required number of replicas per video file 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.<br />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.