Wie versprochen, eine kleine Zusammenfassung des Papiers “Maintaining High Bandwidth under Dynamic Network Conditions”, das ich gestern kurz verlinkt hatte. Thema des Artikels ist das Verteilen von Daten in einem Peer-to-Peer Netzwerk, zum Beispiel um ISOs oder Patches zu verteilen, oder Multimediadaten zu verteilen, ohne einen hohen Load auf den “primären” Datenverteiler einbüssen zu müssen. Die Daten, die verteilt werden, sind meistens nur von einer einzigen Quelle erhältlich, werden aber von vielen Leuten gleichzeitig und schnell gezogen (in dem Artikel, und scheinbar auch woanders, wird dieser Effekt “flash-crowd effect” genannt).
Seit geraumer Zeit gibt es jetzt zum Beispiel BitTorrent, in dem Artikel wird untersucht, wie man ein solches Verfahren verbessern kann. Das Interessante ist aber, dass bei dem Versuch diese Verteilungsverfahren zu optimieren, verschiedene Alternativen vorgeschlagen und dokumentiert werden. Man kriegt also einen Einblick, wie solche Peer-to-Peer Protokolle zu designen sind, je nachdem, welchen Schwerpunkt man haben will. Eine wichtige Entscheidung ist z.B., ob man ein faires Netzwerk haben will, wo praktisch jeder Knoten gleich runterlädt und hochlädt, oder ein schnelles Netzwerk (bei dem also ein Knoten so schnell zu den Daten kommt, die er haben will). Die untersuchten Entscheidungen in dem Artikel sind:
- Ob Knoten (bzw. Peers) in dem P2P-Netz die Daten gesendet bekommen (PUSH-Modell), oder diese Daten anfragen (PULL-Modell)
- Welcher Algorithmus eingesetzt wird, um neue Knoten zu finden, die gute “Transfer”-Charakteristiken haben (Bandbreite, Latenz)
- Welche Daten angefordert werden sollen, je nachdem wie die Netzwerksituation ist
- Welche Daten anderen Peers zu senden sind
- Welche Verfahren eingesetzt werden, um die Daten umzukodieren (z.B. Fehlerkorrektur, oder gar keine Kodierung)
Push oder Pull?
Push ist natürlich die Methode, die einfacher zu realisieren ist. Bei Streaming-anwendungen sollten z.B. alle empfangenden Knoten dieselben Daten mit derselben Geschwindigkeit bekommen. Allerdings wird es gleich komplizierter, wenn Daten von mehreren Sendern gleichzeitig empfangen werden. In dem Fall müssen die Empfänger den Sendern mitteilen, welche Daten sie schon empfangen, damit nicht doppelte Pakete verschickt werden (alles klar?). Bei Pull können die Empfänger genauer kontrollieren, was sie empfangen wollen und von wem. Allerdings wird dadurch die Latenz der Kommunikation erhöht, und es kann unter Umständen auch zu einer nicht zu ignorierenden Erhöhung der ausgetauschten Datenmenge kommen. Hier gibt es also keinen klaren Gewinner, und in dem implementierten Ansatz der Autoren werden auch beide Verfahren gleichzeitig verwendet.
Nachbarnsuche (Peering-Strategie)
Ein extrem wichtiger Punkt (vielleicht der wichtigste) ist, wie ein Knoten seine Nachbarn findet, wie es sie auswählt, und wie er neue Nachbarn hinzuzieht, wenn Knoten ausfallen oder sich ihre Verbindung verschlechtert. Im Idealfall weiss jeder Knoten über alle anderen Knoten bescheid, und kennt auch ihre Parameter in Sachen Bandbreite, usw… Das ist natürlich kaum möglich, denn der Overhead, diese ganze Daten im Netzwerk zu verteilen wäre viel zu hoch (das ist auch so eins der Probleme der herkömmlichen Multicast-Routing Algorithmen). Eine andere Möglichkeit wäre, das ein zentraler Knoten diese Information festhält, und ich glaube (aber ich weiss nicht wirklich genau wie Bittorrent funktionniert), dass in Bittorrent diese Rolle von dem Tracker übernommen wird. Ist dieser Tracker nun weg oder schlecht erreichbar, bricht das Ganze zusammen. Nicht zu übersehen ist auch die Bandbreite, die der Tracker dann zur Verfügung stellen muss, um diese Daten managen zu können. Ein weitere “triviale” Möglichkeit wäre einfach, dass jeder Knoten eine feste Liste von Nachbarn ermittelt, und diese dann nicht mehr ändert. Wenn diese Knoten aufhören oder nicht mehr erreichbar sind, oder diese Anfangsliste einfach schlecht ist, hat der Knoten verloren. Ein sinnvoller Ansatz ist also eine Peeringstrategie, wo der Knoten nicht über ein globales Wissen verfügen muss (das gesamte Netzwerk kennen), und auch nicht mit vielen Nachbarknoten kommunizieren muss, aber trotzdem relativ schnell gute Nachbarn finden kann.
Ich weiss nicht, wie die das im Artikel lösen (noch nicht komplett durchgelesen), aber ein sinnvoller Ansatz wäre denke ich eine Art “randomisierte” Aggregierung von Nachbarsdaten durch die Knoten selber. Also Knoten A kommuniziert mit 10 Knoten, welche selber 10 Knoten als Nachbarn haben, A kann mit diesen 10 Knoten die kompletten Nachbarsdaten austauschen (also mit Tiefe 1), irgendwie die 5 Besten + 5 Zufällige zusammenbasteln, und an weitere Knoten schicken (oder an den Tracker, der deswegen nicht alle Daten von allen Peers kennen muss). Kommt ein neuer Knoten in das Netz, kriegt er eine zufällige, aggregierte Menge von Nachbarn, und kann sich so durchhangeln. Gehen ein paar Knoten hops, können ihre Nachbarn beim Tracker wieder “randomisierte”, im Durchschnitt gute Nachbarn bekommen. Hauptsache, im Durchschnitt klappt es gut, und relativ schnell kann man die Nachbarnauswahl verfeinern, indem man neue Nachbarn hinzunimmt, und die schlechtesten rauswirft.
So, das ist auch genug für heute, denn langsam wird es spät. Mehr in den nächsten Tagen.