Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Summe, d.h. das XOR, auf der mittleren Kante. Aus x und x + y kann man nun x und y rekonstruieren (und analog aus y und x + y ebenfalls x und y), siehe Abbildung 12.8.
    Es wurde bereits in [111] bewiesen, dass dies im Allgemeinen durch eine zufallige Kodierung gelost werden kann. In [ 112] wurde diese Idee aufgegriffen and auf Peer-to-Peer-Netzwerke angewendet.
    Hierzu sieht man jeden Block bi als einen Eintrag des Vektors (b1, . . . , bm), der das game Dokument darstellt. Anstatt einzelne Blocke zu veroffentlichen, wird jetzt eine Linearkombination

    dieser Vektoreintrage samt der Faktoren versendet. Die Faktoren werden zufallig gewahlt. Wenn nun der Empfanger m Blocke c a , . . . , c,n erhalten hat, so sei A = (ai j )i, j c [m] die zugehorige Variablenmatrix aus den einzelnen Faktoren der Blocke. Dann gilt

    Abb. 12.6. Ubertragt man auf der mittleren Kante nur x, so fehlt links das Bit y.
    Abb. 12.7. Ubertragt man auf der mittleren Kante nur y, so fehlt rechts das Bit x.
    Abb. 12.8. Mit Hilfe der Netzwerkkodierung kann die Information A and B an den Senken des Netzwerks ankommen.

    Ist nun die Matrix A umkehrbar, so erhalt man die ursprungliche Datei durch Berechnung von

    Die Blocke werden hier wieder als Vektoren Ober einem Galois-Korper dargestellt. Damit ergeben sich die folgenden Aufgaben der Peers:
    • Peers mit vollstandiger Information (Quellen):
    Auf Anfrage eines anderen Peers wird eine Linearkombination Uber den ursprunglichen Peers wie eben beschrieben and der Variablenvektor zusammen mit dem Datenblock weitergegeben.
    • Peers mit unvollstandiger Information:
    Erhalt ein solcher Peer eine Anfrage, dann berechnet er eine Linearkombination Ober den bereits erhaltenen Codes cl, ... ct, wobei zum Code ci die Variablen ai = ai,l,... , ai,, gehoren, d.h.

    Nun wahlt der Peer die Zufallszahlen r1, ... r,,,, and iibermittelt an den anfragenden Peer den Vektor

    Dann uberpruft der anfragende Peer, ob dieser Vektor linear unabhangig ist von den bereits vorhandenen Variablenvektoren. Ist das der Fall, dann teilt er es dem Partner mit and dieser dbermittelt dann den Vektor:

    Der Vorteil der Netzwerkkodierung gegenuber der Vorwarts-Fehlerkorrektur ist, class die Peers keine Entscheidung treffen mussen, wie die Daten weiterzugeben sind. Sie erstellen eine Mischung aus alien Codes, die sie bisher erhalten haben.
12.7 Zusammenfassung
    Die Netzwerkkodierung lost das Coupon-Collector-Problem bestmoglich. Ein gewisser Nachteil ergibt sich aus der Ubertragung der Variablenvektoren, die zu einer Aufblahung des Datenvolumens fuhren. Beispielsweise sind fur die Ubertragung einer 4 GByte-Datei in Teilen von je einem MByte Vektoren der GroBe 4.096 notwendig. Das ist ein Datenanteil von vier Promille. Wahlt man kleinere Vektoren, so erhoht sich der Aufwand entsprechend. Ein weiteres Problem ist auch die Invertierung der Matrix. Bei 4096 Eintragen ist eine Matrix mit 16 Mio. Eintragen zu in- vertieren. Das bedingt einen erheblichen Berechnungsaufwand. Daher schneidet auf dem Papier die Netzwerkkodierung zwar besser ab, wenn leistungsstarke Rechner mit schlechter Bandbreite verbunden sind. In der Praxis hat sich die Netzwerkkodierung noch nicht durchgesetzt, da der Ansatz von Bittorrent mit erheblich geringerem Berechnungsaufwand die Verteilung sicherstellen kann. Zwar schneidet Bittorrent in den Vergleichen von [112] wesentlich schlechter ab, these Sind jedoch nicht unum- stritten.

13

Peer-to-Peer-Netzwerke in der Praxis
    In case of major discrepancy, it's always reality that's got it wrong.
    Douglas Adams
    Peer-to-Peer-Netzwerke sind seit ihrem ersten Auftreten ein Massenphanomen and werden in der Offentlichkeit gleichgesetzt mit illegalem File-Sharing. In diesem Kapitel werden populare Peer-to-Peer-Netzwerke betrachtet. Die Popularitat ist hierbei schwer einzuschatzen. Denn die meisten Daten werden ohne Erlaubnis der Rechte-Inhaber verteilt, and these gehen in letzter Zeit vermehrt dagegen vor. Auch versuchen zuweilen Netzwerkadministratoren and Internet-Service-Provider, die Teilnahme an Peer-to-Peer-Netzwerken zu unterbinden. Da das zumeist Uber die Identifikation von Ports geschieht, segeln die Peers nun oft unter wechselnden oder falschen Ports, d.h., die Netzwerke sind nicht mehr uber eine einfache Port-Analyse identifizierbar, wie es IP eigentlich vorsieht. Also muss der Verkehr selbst analysiert werden, um den Anteil der Peer-to-Peer-Netzwerke zu bestimmen. Auf die Selbst- auskunft der Teilnehmer ist wenig Verlass.