Entwurf von Overlay-Multicast-Netzwerken für Streaming

In diesem Papier präsentieren wir einen polynomialen Zeit-Approximationsalgorithmus zum Entwurf eines Multicast-Overlay-Netzwerks. Der Algorithmus findet eine Lösung, die die Kapazitäts- und Zuverlässigkeitsanforderungen innerhalb eines konstanten Faktors zur optimalen Lösung erfüllt und die Kosten innerhalb eines logarithmischen Faktors. Die Klasse von Netzwerken, auf die unser Algorithmus anwendbar ist, schließt das von Akamai Technologies verwendete Netzwerk ein, um Live-Medienstreams über das Internet zu liefern. Insbesondere analysieren wir Netzwerke, die aus drei Stufen von Knoten bestehen. Die Knoten in der ersten Stufe sind die Quellen, an denen die Live-Streams ihren Ursprung haben. Eine Quelle leitet jeden ihrer Streams an einen oder mehrere Knoten in der zweiten Stufe weiter, die als Reflektoren bezeichnet werden. Ein Reflektor kann einen eingehenden Stream in mehrere identische ausgehende Streams aufteilen, die dann an Knoten in der dritten und letzten Stufe gesendet werden, die als Senken bezeichnet werden. Während die Pakete in einem Stream von einer Stufe zur nächsten reisen, können einige von ihnen verloren gehen. Die Aufgabe einer Senke besteht darin, die Pakete von mehreren Instanzen desselben Streams (durch Umordnen der Pakete und Verwerfen von Duplikaten) zu kombinieren, um eine einzelne Instanz des Streams mit minimalem Verlust zu bilden. Wir nehmen an, dass die Verlustquote zwischen jedem Paar von Knoten im Netzwerk bekannt ist und dass Verluste zwischen verschiedenen Paaren unabhängig sind, diskutieren jedoch Erweiterungen, in denen einige Verluste korreliert sein können.