On the Stability of Distribution Topologies in Peer-to-Peer Live Streaming Systems

Peer-to-Peer Live-Streaming-Systeme sind ständigen Störungen ausgesetzt.Insbesondere ermöglichen unzuverlässige Teilnehmer Ausfälle und Angriffe, welche überraschend Peers aus dem System entfernen. Die Folgen solcher Vorfälle werden großteils von der Verteilungstopologie bestimmt, d.h. der Kommunikationsstruktur zwischen den Peers.In dieser Arbeit analysieren wir Optimierungsprobleme welche bei der Betrachtung von Stabilitätsbegriffen für solche Verteilungstopologien auftreten. Dabei werden sowohl Angriffe als auch unkoordinierte Ausfälle berücksichtigt.Zunächst untersuchen wir die Berechnungskomplexität und Approximierbarkeit des Problems resourcen-effiziente Angriffe zu bestimmen. Dies demonstriert Beschränkungen in den Planungsmöglichkeiten von Angreifern und zeigt inwieweit die Topologieparameter die Schwierigkeit solcher Angriffsrobleme beeinflussen. Anschließend studieren wir Topologieformationsprobleme. Dabei sind Topologieparameter vorgegeben und es muss eine passende Verteilungstopologie gefunden werden. Ziel ist es Topologien zu erzeugen, welche den durch Angriffe mit beliebigen Parametern erzeugbaren maximalen Schaden minimieren.Wir identifizieren notwendige und hinreichende Eigenschaften solcher Verteilungstopologien. Dies führt zu mathematisch fundierten Zielstellungen für das Topologie-Management von Peer-to-Peer Live-Streaming-Systemen.Wir zeigen zwei große Klassen effizient konstruierbarer Verteilungstopologien, welche den maximal möglichen, durch Angriffe verursachten Paketverlust minimieren. Zusätzlich beweisen wir, dass die Bestimmung dieser Eigenschaft für beliebige Topologien coNP-vollständig ist.Soll die maximale Anzahl von Peers minimiert werden, bei denen ein Angriff zu ungenügender Stream-Qualität führt, ändern sich die Anforderungen an Verteilungstopologien. Wir zeigen, dass dieses Topologieformationsproblem eng mit offenen Problemen aus Design- und Kodierungstheorie verwandt ist.Schließlich analysieren wir Verteilungstopologien die den durch unkoordinierte Ausfälle zu erwartetenden Paketverlust minimieren. Wir zeigen Eigenschaften und Existenzbedingungen. Außerdem bestimmen wir die Berechnungskomplexität des Auffindens solcher Topologien. Unsere Ergebnisse liefern Richtlinien für das Topologie-Management von Peer-to-Peer Live-Streaming-Systemen und zeigen auf, welche Stabilitätsziele effizient erreicht werden können.The stability of peer-to-peer live streaming systems is constantly challenged. Especially, the unreliability and vulnerability of their participants allows for failures and attacks suddenly disabling certain sets of peers. The consequences of such events are largely determined by the distribution topology, i.e., the pattern of communication between the peers.In this thesis, we analyze a broad range of optimization problems concerning the stability of distribution topologies. For this, we discuss notions of stability against both attacks and failures.At first, we investigate the computational complexity and approximability of finding resource-efficient attacks. This allows to point out limitations of an attacker's planning capabilities and demonstrates the influence of the chosen system parameters on the hardness of such attack problems.Then, we turn to study topology formation problems. Here, a set of topology parameters is given and the task consists in finding an eligible distribution topology. In particular, it has to minimize the maximum damage achievable by attacks with arbitrary attack parameters.We identify necessary and sufficient conditions on attack-stable distribution topologies. Thereby, we give mathematically sound guidelines for the topology management of peer-to-peer live streaming systems.We find large classes of efficiently-constructable topologies minimizing the system-wide packet loss under attacks. Additionally, we show that determining this feature for arbitrary topologies is coNP-complete.Considering topologies minimizing the maximum number of peers for which an attack leads to a heavy decrease in perceived streaming quality, the requirements change. Here, we show that the corresponding topology formation problem is closely related to long-standing open problems of Design and Coding Theory.Finally, we study topologies minimizing the expected packet loss due to uncoordinated peer failures. We investigate properties and existence conditions of such topologies. Furthermore, we determine the computational complexity of constructing them.Our results provide guidelines for the topology management of peer-to-peer live streaming systems and mathematically determine which goals can be achieved efficiently