Content Delivery Networks. Ein Überblick

Zusammenfassung

Für die Betreiber großer Webportale ist es von entscheidender Bedeutung, dass ihre Inhal- te wie Bilder bzw. Videos schnell und zuverlässig an ihre Endnutzer ausgeliefert werden können. Zu diesem Zweck haben sich Content Delivery Netzworks, kurz CDNs, etabliert. Sie bestehen aus einer weltweiten, dezentralen Server-Infrastuktur, über die Webinhal- te an Endnutzer verteilt werden können. Im Folgenden wird zunächst erläutert, wie ein CDN prinzipiell funktioniert und für welche Probleme es einen Lösungsansatz darstellt. Anschließend werden die Techniken und Algorithmen beschrieben, die von CDNs ver- wendet werden, u. a. das Problem der Server-Platzierung sowie Methoden zur Replika- tion und Auslagerung der Inhalte. Zum Schluss wird eine Kombination von CDNs mit Peer-To-Peer-Netzen vorgestellt, wie auch ein Überblick über den Markt kommerzieller CDN-Anbieter gegeben.

1 Einleitung

Die schnelle und zuverlässige Auslieferung von Inhalten ist eines der grundlegenden Herausforderungen, denen sich Anbieter großer Webportale stellen müssen. Besitze ein solcher Anbieter beispielsweise nur eine einzige Serverfarm an einem bestimmten Standort, und biete eine populäre Webplattform bereit, die täglich von hunderttausenden Besuchern weltweit benutzt wird. Dabei stellt der Anbieter fest, dass zu den Zeiten, zu denen gehäuft Nutzer aus seiner Umgebung auf das Angebot zugreifen, der Zugriff für Nutzer aus anderen Gegenden merklich verlangsamt ist. Ebenso dauert die Auslieferung an Nutzer aus anderen Ländern bzw. Kontinenten ebenfalls spürbar länger. Ursache davon sind die Ausbreitungs- und Latenzzeiten, die mit zunehmender Entfernung ansteigen, sowie die Tatsache, dass eine hohe Zugriffszahl zu einer hohen Auslastung der Netzwerkinfrastuktur führt.

Diese Probleme lassen sich durch die Verwendung eines sogenannten Content Delivery Net- works (dt. Netzwerk zur Auslieferung von Inhalten; kurz CDN ) umgehen. Es handelt sich hierbei um eine Infrastruktur weltweit verteilter, sogenannter Surrogat-Server (Stellvertreter- Server), die jeweils Kopien der Inhalte des Ursprungs-Servers (in obigen Beispiel derjenige am Standort des Anbieters) bereitstellen. Die Kommunikation unter Verwendung eines CDNs fin- det nicht direkt zwischen den Clients der Nutzer und den Ursprungs-Servern des Anbieters, sondern zwischen den Clients und den Surrogat-Servern respektive den Surrogat-Servern und den Ursprungsservern statt. Durch Platzierung der Surrogat-Server an sinnvoll gewählten, weltweit verteilten Standorten wird jedem Nutzer ein schneller Zugriff auf die Inhalte ermög- licht sowie die Möglichkeit einer hohen Netzwerkauslastung verringert. In Anlehnung an den Artikel von Pallis et al. [PaVa06] wird im Folgenden die Funktionsweise sowie die grund- legenden Herausforderungen, die sich durch den Betrieb eines Content Delivery Networks ergeben, erläutert. Ferner werden aktuelle Forschungen und Entwicklungen im CDN-Bereich vorgestellt.

2 Abrufen von Inhalten mittels HTTP

Die Unterschiede, die sich aus der Verwendung eines CDNs ergeben, sollen anhand des fol- genden Beispiels erläutert werden. Stellen wir uns dafür folgendes Szenario vor, wie es im klassischen Fall, d.h. ohne Verwendung eines CDNs, ablaufen würde: Ein Client möchte eine Webressource, in diesem Fall eine HTML-Datei, von einem Server www.example.com abrufen. Dafür führt der Client zunächst einen DNS-Request aus, um an die IP-Adresse des Servers zu gelangen. Anschließend wird eine HTTP-Anfrage an diese IP-Adresse initiiert, und der Server beantwortet diese durch Versenden der HTML-Datei als eine Folge von IP-Paketen. Aufgrund der physikalischen Beschränkung derÜbertragungsgeschwindigkeit und ineffizienter Routing- bzw. Kommunikationsmechanismen [NySS10] führt eine zunehmende Entfernung zwischen Client und Server zu einer merklichen Erhöhung der Paketumlaufzeiten¹ um ein Vielfaches sowie einer deutlichen Verringerung der Datenraten auf ein Bruchteil des ursprünglichen Wer- tes. Somit kann eine HTTP-Anfrage unter Umständen mehrere Sekunden andauern, was ein eine unerwünschte und zu vermeidende Situation darstellt. Folglich stellt geografische Nähe zwischen Server und Client ein entscheidendes Kriterium für die schnelle und zuverlässige Auslieferung von Webinhalten dar. Darüber hinaus kann es bei einer großen Anzahl an Zu- griffen auf diesen Server zu einer hohen Auslastung der Verbindung und des Servers selbst kommen, beispielsweise wenn viele Nutzer von weltweit verteilten Standorten auf diesen Ser- ver zugreifen möchten. Die hohe Auslastung des Servers führt ferner dazu, dass ihm weniger Ressourcen zur Bearbeitung von HTTP-Anfragen bereitstehen, und diese dann jeweils länger andauern oder überhaupt nicht beantwortet werden können.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Prinzip-Schema eines Content Delivery Networks, Eigene Darstellung.

Das Content Delivery Network umgeht diese Probleme, indem es den angebotenen Dienst de- zentralisiert. Die HTTP-Anfrage aus dem obigen Beispiel würde lediglich an einen Surrogat- Server geleitet werden, der sich in der Nähe des Standortes des Clients befindet. Zur Be- stimmung, an welchen Surrogat-Server eine Anfrage geleitet werden soll, verwenden CDNs hauptsächlich zwei verschiedene Techniken, namentlich das DNS-Forwarding sowie die URL- Rewrite-Methode [KrWZ01]. Beim DNS-Forwarding betreibt das CDN selbst autoritative² DNS-Server, sodass Domain-Namen standortabhängig auf unterschiedliche IP-Adressen, und zwar die der Surrogat-Server, aufgelöst werden. Der DNS-Server kann dabei je nach Auslas- tung etc. des CDNs zu unterschiedlichen Surrogat-Servern umleiten (sog. Load-Balancing). Durch einen niedrigen Time-To-Live-Eintrag (TTL) im DNS-Response-Header wird hier- bei verhindert, dass der Client das DNS-Mapping zu lange zwischengespeichert und er- möglicht somit dem CDN, schnell aufÄnderungen der Netzwerklast o.ä. zu reagieren. Bei der URL-Rewrite-Methode dagegen ist das Umschreiben von URLs nach bestimmten Mus- tern, um Anfragen auf Surrogat-Server umzuleiten. Es wird hauptsächlich für eingebettete Inhalte wie Bilder und Videos verwendet, wohingegen das DNS-Forwarding hauptsächlich bei den HTML-Seiten selbst Verwendung findet. Beispielhaft würde die URL eines PNG- Bildes www.example.com/images/picture.png auf eine URL des Surrogat-Servers, die die ursprüngliche URL als Parameter enthält, umgeschrieben werden, z. B. cdn.surrogate.net /www.example.com/images/picture.png . Durch Verwendung dieser beiden Techniken ist es möglich, dass Inhalte einer einzelnen HTML-Seite von unterschiedlichen Surrogat-Servern stammen; der Ablauf ist dem Nutzer jedoch völlig verborgen und das Load-Balancing er- möglicht kurze Latenzzeiten beim Abruf der jeweiligen Ressourcen. Zu beachten ist, dass der Einsatz eines CDNs keinesfalls auf reine Webanwendungen beschränkt ist.

3 Das Webserver Replica Placement Problem

Für den Betrieb eines CDNs ist es wichtig, die Surrogate-Server derart auf dem Globus zu plat- zieren, dass der Nutzen des CDNs maximiert und die dabei entstehenden Kosten minimiert werden. Dieses Problem wird als Webserver Replica Placement Problem bezeichnet und lässt sich wie folgt algorithmisch formulieren [QiPV01]: Das CDN wird als zusammenhängender Graph modelliert, dessen Knotenmenge aus den m möglichen Standorten für eine bestimmte Anzahl n an Surrogat-Servern (wobei n < m) sowie den Clients, die auf das CDN zugrei- fen sollen, besteht. Die Kanten dieses Graphen repräsentieren die (möglichen) Verbindungen zwischen den einzelnen Standorten bzw. Rechnern, und die Kantengewichte entsprechen, je nach betrachtetem Fall, verschiedenen realen Interpretationen wie z.B. der Latenzzeit oder der Hop-Anzahl. Nun gilt es die m Server derart zu platzieren, dass die Kosten für Anfragen bei Verwendung dieser Platzierung minimal werden. Die Kosten cij für eine solche Anfrage von einem Knoten i zu einem anderen Knoten j sind dabei definiert als deren Distanz im Graphen.

Die Entwicklung entsprechender effizienter Algorithmen für dieses NP-harte Problem [QiPV01] war und ist Teil der aktuellen Forschung an CDNs. Im Folgenden werden zunächst zwei Algorithmen vorgestellt, die auch im Übersichtsartikel von Pallis et al. erwähnt [PaVa06], sowie von Qui et al. in [QiPV01] beschrieben werden. In Abschnitt 3.3 wird anschließend Weiterentwicklung [SzPS05] eines dieser Algorithmen vorgestellt.

3.1 Der greedy-basierte Algorithmus

Der greedy-basierte Algorithmus stellt eine eher einfache Methode dar, Platzierungen für Surrogat-Server zu finden. Eine solche Platzierung ist dann (annähernd) optimal, wenn die Kosten, die durch Zugriffe aller Clients auf die Surrogat-Server entstehen, minimal werden. Ferner nimmt der hier vorgestellte Algorithmus zur Vereinfachung an, dass ein Client jeweils nur auf einen einzigen Surrogat-Server zugreift, d.h. dass Anfragen eines Clients immer an den gleichen Surrogate-Server gerichtet sind.

Der Algorithmus läuft wie nun folgt ab, indem er m Iterationen ausführt: In der ersten Iteration werden für jeden der m potentiellen Standorte die gesamten Anfrage-Kosten∑ ckl für Anfragen zwischen jedem der Clients k und dem aktuell betrachteten Serverstandort l berechnet, und derjenige Serverstandort gewählt, für den sich die geringsten Kosten∑ ckl = min ergeben.

In jeder weiteren Iteration wird nun angenommen, dass die bereits ausgewählten Server fest platziert sind und Anfragen daher auch über diese geleitet werden können. Ansonsten findet die Berechnung analog zur ersten Iteration statt. Dies wird solange wiederholt, bis alle n Server platziert worden sind.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2: Ausführung des greedy-basierten Algorithmus mit n = 2 und m = 3. Eigene Darstellung.

Da dieser Algorithmus m-mal jeden Pfad zwischen den n potentiellen Serverstandorten be- trachtet, hat er eine asymptotische Laufzeit von O(n² m). Qiu et. al. [QiPV01] vergleichen diesen Algorithmus mit einem sog. super-optimalen Algorithmus, d. h. einem Algorithmus, der stets beste, aber nicht in jedem Fall zulässige (bezüglich der Randbedingungen) Lösun- gen generiert. Sie verwenden diesen als Maß für die Leistungsfähigkeit des greedy-basierten Algorithmus und führen dafür einen sog. relativen Performanzfaktor ein, dessen Wert der Quotient der Kosten einer Lösung eines approximierenden Algorithmus (wie dem greedy- basiereten Algorithmus) und der Kosten einer Lösung des super-optimalen Algorithmus für eine bestimmte Eingabe ist. Dieser Performanzfaktor ist daher umso näher an 1 ist, je besser die vom approximierenden Algorithmus gelieferte Lösung an die des super-optimalen Algo- rithmus heranreicht. Der greedy-basierete Algorithmus erreicht dabei einen Wert von 1.1 - 1.5, was auf relativ gute Lösungen hinweist. Im Worst-Case dagegen erreicht dieser lediglich einen derartigen Wert von 4.

3.2 Der Hot-Spot-Algorithmus

Der sog. Hot-Spot-Algorithmus verfolgt einen abweichenden Ansatz, indem er versucht, die Surrogat-Server in der Nähe derjenigen Clients zu platzieren, die die größte Auslastung produ- zieren. Dazu wird für jeden der n potentiellen Standorte der dort entstehende Traffic berechnet und anschließend diese Liste anhand der berechneten Werte absteigend sortiert. Schließlich werden diejenigen Standorte ausgewählt, die die m höchsten Auslastungswerte aufweisen. Zur Berechnung des Traffics, der an einem Standort generiert wird, betrachtet der Algorithmus eine fest definierte Nachbarschaft mit Radius r, d.h. der minimalen Entfernung zwischen die- sem Standort und einem anderen Knoten bzw. Client. Das Traffic-Aufkommen ist hierbei durch die Kantengewichte angegeben.

Als Laufzeit weist dieser Algorithmus zwar nur O(n² + min(n · log n, nm)) auf, hat laut Qui et. al. jedoch einen relativen Performanzwert von ca. 1,6 - 2 im Mittel. Aufgrund des abwei- chenden Ansatzes im Vergleich zum Greedy-Algorithmus und des besseren Laufzeitverhaltens stellt der Hot-Spot dennoch ein vielversprechendes Verfahren zur Bestimmung der Platzierung von Surrogat-Servern dar.

3.3 Der Hot-Zone-Algorithmus

Als Verbesserung des eben beschriebenen Hot-Spot-Algorithmus sowohl bezüglich der Quali- tät der Lösungen als auch der Laufzeit stellen Szymaniak et. al. in [SzPS05] den sog. Hot-Zone- Algorithmus vor. Der Hot-Zone ist Latenz-basiert, d.h. er betrachtet die Latenzzeiten zwischen den Knoten als Kostenangaben. Diese nutzt er, um das Netzwerk in Regionen einzuteilen, die aus Knoten bestehen, die untereinander eine relativ geringe Latenz aufweisen. Anschließend werden in denjenigen Regionen mit der höchsten Traffic-Auslastung Surrogat-Server plat- ziert, ähnlich wie beim Hot-Spot-Algorithmus. Da die Regionen aber deutlich kleiner als das Gesamtnetzwerk sind, wird der Aufwand für das Platzieren enorm reduziert.

Die Laufzeit dieses Algorithmus beträgt hierbei nur noch O(n · max(log n, m)). Durch Weg- fallen des quadratischen Faktors n² stellt der Hot-Zone-Algorithmus eine deutliche Verbes- serung bezüglich der Laufzeit zu den oben vorgestellten Algorithmen dar, da die Anzahl n an potentiellen Standorten typischerweise sehr groß ist. Ferner stellen Szymaniak et. al. fest, dass Hot-Zone Lösungen ähnlicher Qualität wie die des Greedy-Ansatzes liefert. Somit stellt HotSpot einen geeigneten Algorithmus dar, um Surrogate-Server in CDNs zu platzieren.

3.4 Weitere Forschung zum Webserver Replica Placement Problem

Die in den vorigen Abschnitten vorgestellten Algorithmen sind sogenannte statische Verfah- ren, d.h. es ist nicht ohne Weiteres möglich, eine Platzierung effizient zu ändern. Dynamische Placement-Algorithmen wie unter anderem von Presti et. al in [PrBP05] vorgestellt sollen es dagegen ermöglichen, Platzierungen auch bei sich ändernden Umständen neu zu berechnen, z. B. wenn sich das Traffic-Aufkommen an einem Knoten signifikant erhöht hat und ein weite- rer Surrogat-Server platziert werden sol. Weitere, erst kürzlich vorgestellte Arbeiten wie u.a. [RoMa13] zeigen ferner, dass die Forschung an dynamischen Algorithmen weiterhin aktuell ist.

[...]

¹ Die Paketumlaufzeit (engl. Round Trip Time (RTT)) ist die Summe der Laufzeit eines Pakets und der Laufzeit des Antwortpakets bzw. Quittung und ist neben der Latzenzzeit ein wichtiges Kriterium zur Bestimmung der Leistung von Netzwerken.

² Autoritative DNS-Server sind diejenigen DNS-Server, die für einen bestimmten Bereich (DNS-Zone) zuständig sind.