Peer-to-Peer-Netzwerke: Algorithmen und Methoden

1.

    Beweis. Jeder Binarbaum kann durch sukzessives Anhangen von zwei Blattern an einen Knoten konstruiert werden. Der einfachste Baum besteht aus einem Blatt, hier gilt b = 1 and k = 0. Dies ist der Induktionsanfang. Wenn wir als Induktionsvoraus- setzung annehmen, dass die Aussage fur b Blatter korrekt ist, dann erhoht sich durch Anhangen von zwei Blattern die Anzahl der Blatter effektiv um eins (daja ein bereits vorhandenes Blatt zum internen Knoten wird) and die Anzahl der internen Knoten erhoht sich auch um eins. Daraus folgt das Lemma. ❑
    Dieses Problem lasst sich durch Erhohung des Grades nicht verringern. Dann nimmt die Anzahl der internen Knoten ab, wie das folgende Lemma zeigt.
    Lemma 12.2. In jedem Baum mit Grad d gilt fur die Anzahl der Blatter b and die Anzahl der internen Knoten k: (d - 1)k + 1 = b.
    Beweis. Der Beweis ist vollig analog zum Beweis von Lemma 12.1. Jeder Baum mit Grad d kann durch sukzessives Anhangen von d Blattern an einem Knoten konstruiert werden. Der einfachste Baum besteht aus einem Blatt, hier gilt b = 1 and k = 0. Dies ist der Induktionsanfang. Angenommen, die Gleichung stimmt fur b Blatter hangen wir jetzt d Blatter an, so erhoht sich die Anzahl der Blatter effektiv um d - 1 (da ja ein Blatt zum internen Knoten wird), and die Anzahl der internen Knoten erhoht sich um eins. Daraus folgt das Lemma. ❑
    Man sieht also, dass sich der Aufwand der benachteiligten Knoten erhoht. Da Peer-to-Peer-Netzwerke auf Freiwilligkeit beruhen, ist davon auszugehen, dass sich solche Peers dieser Aufgabe durch Abmelden entziehen konnen (in der Hoffnung durch Neuanmelden zum Blatt im Baum zu werden).
    Split-Stream lost dieses Problem durch die Kombination folgender Techniken: Zuerst wird jede Datei in Blocke (Stripes) zerlegt. AuBerdem ist von jedem Peer seine eingehende and ausgehende Bandbreite bekannt. Fur jeden dieser Blocke wird jetzt ein eigener Baum konstruiert. So ubernimmt ein Peer fur gewisse Blocke die Funktion eines internen Knotens, d.h. eines Verteilers, and fur andere Blocke nur die Funktion des Blattes, d.h. eines Empfangers, siehe Abbildung 12.5. Hierbei wird beachtet, dass die Eingangs- and Ausgangsbandbreiten jedes Peers berucksichtigt werden. Es wird Scribe fur jeden einzelnen Stripe verwendet. Dazu wird fur jeden Stripe eine Stripe-ID angelegt. AuBerdem gibt es lokale Optimierungsmechanismen, die eine Uberschreitung der Eingangs- and Ausgangsbandbreite wieder korrigieren.
    Splitstream lost die Ungleichbehandlung der Peers. Jedoch entsteht durch die explizite Verteilung jedes Blocks ein erheblicher Organisationsaufwand.
12.4 Bittorrent
    Brarn Cohen ist der Erfinder von Bittorrent [107]. Bittorrent ist ein sehr erfolgrei- ches Peer-to-Peer-Netzwerk, das in den letzten Jahren mehr als die Halfte des Inter- netverkehrs verursacht hat. Der Erfolg des Netzwerks beruht in seiner Effektivitat zur Verwendung des Uploads von Peers, die die Datei noch nicht vollstandig her- unter geladen haben. Andererseits besitzt Bittorrent keine Mechanismen zur Suche von Dateien. Die Beteiligten eines Teilnetzwerks konzentrieren sich auf den Download einer Datei. Dieser wird organisiert durch einen so genannten Tracker-Host, der die Verbindungen der interessierten Peers vermittelt. Bittorrent verwendet implizit Multicast-Baume fur die Verteilung der Daten, ahnlich wie Splitstream. Die Beschreibung von Bittorrent ist aber Peer-orientiert and nicht datenorientert. Anders formuliert, es wird nicht fur jeden Teil der Datei explizit ein Baum konstruiert. Vielmehr wird fur jeden Peer angegeben, welche Teile er als nachstes ladt oder wei- tergibt.

    Die Ziele von Bittorrent lassen sich wie folgt zusammenfassen:
    Abb. 12.5. Funktionsweise von Splitstream.
    • Moglichst effizienter Download einer Datei unter Zuhilfenahme der Upload- Fahigkeit der Peers.
    • Faires Verhaltnis zwischen Upload and Download eines Peers. In der Praxis wird der Upload der Engpass. Das wird zum Beispiel durch die asymmetrische Proto- kollgestaltung von ISDN oder durch die asymmetrische Bitubertragungsschicht von DSL verursacht.
    • Fairness zwischen den Peers. Kein Peer soil nur Daten herunterladen konnen, wahrend andere Peers Daten hochladen.
    • Verwendung verschiedener Quellen. Dies schlieBt sowohl Peers ein, die die Datei vollstandig geladen haben, als auch Peers, die erst einige Teile der Datei geladen haben.

    Technisch wird das in Bittorrent folgendermaBen realisiert: Die Verbindungsauf- nahme erfolgt durch einen