Peer-to-Peer-Netzwerke: Algorithmen und Methoden

einfaches Beispiel. Wenn zum Beispiel vier Teile aus je vier Bits bestehen, z.B. xl = 0101, x2 = 0011, x3 = 1000, and x4 = 0000, dann kann man zusatzlich einen redundanten Fehlercode z = X1 + x2 + X3 + X4 = 1110 durch die XOR-Operation der einzelnen Bits berechnen. Dieser Fehler-Code wird nun zusatzlich verbreitet. Wenn zum Beispiel der zweite Teil verloren geht, so kann man durch Berechnung von x2 = z + xl + X3 + X4 den fehlenden Teil wieder rekonstruieren.
    Diese Technik wird in der Bitubertragungsschicht von Rechnernetzwerken als so genannte Vorwdrtsfehlerkorrektur (Forward Error Correction) verwendet. Dort ist das Hauptproblem, dass einzelne Bits durch Storungen verloren gehen konnten. Zuweilen treten these Storungen auch gehauft auf, als so genannte Bursts. Fur Kommunikation, die unter dieser Fehlerart zu leiden hat, sind die Kodierungen von Reed and Solomon besonders geeignet [108], welche eine begrenzte Menge von Bitfehlern kompensieren konnen. Die Situation in Bittorrent ist ahnlich. Nur gehen hier gleich ganze Blocke verloren.
Reed-Solomon-Kodierungen
    Betrachten wir eine Datei, die in n Blocke zerlegt wurde. Dann muss man bei einer Reed-Solomon-Kodierung im Voraus festlegen, wieviele Blocke davon maximal verloren gehen konnen. Sei diese Zahl k. Man kodiert nun staff n Blocke n + k Blocke, and n beliebige dieser n + k Blocke genfigen dann zur Rekonstruktion der Datei. Hierzu seien X = ( X 1 ,.. , xn)T die Originalblocke. Diese Blocke werden als Vektoren fiber einem Korper betrachtet, so dass man sie addieren and mit Variablen multiplizieren kann. Man kann sich ffir den Anfang vorstellen, dass es sich bier um einfache Zahlen handelt.
    Dann konstruiert man die kodierten Blocke Y = (y1 i ... , yn+k ), indem man die Matrixmultiplikation mit einer sorgfaltig gewahlten (n + k) x n Matrix durchfuhrt:

    Hierbei muss jede n x n Teilmatrix, die man durch Streichen von k beliebigen Zeilen von M erhalt, invertierbar sein. Sei M' eine Teilmatrix, die die korrespondierenden Zeilen des n-stelligen Teilcodes (yi,, ... yiJ mit it < i2 < ... < in erhalt. Dann gilt

    Ist nun M' invertiert, so kann man durch

    den Originalvektor rekonstruieren. Hierzu benotigt man dann nur einen n-stelligen Teilcode and die Indizes des entsprechenden Codes. Diese Kodierung wird (n + k, n) -Reed-Solomon-Code genannt. Wie bereits erwahnt, steht hier jeder Block ffir einen Vektor fiber einem endlichen Korper. Besonders geeignet ist zum Beispiel ein Vektor fiber den Galois-Korpern F[256] oder F[216], da diese den Wortlangen gangiger CPUs entsprechen. Die Addition wird durch die XOR-Operation dargestellt and die Multiplikation kann mit Hilfe einer Multiplikationstabelle geschehen.

    Fur die Matrix kann man zum Beispiel eine Vandermonde-Matrix wahlen, in der jede Zeile die Form (1, x, x'2, ... , xn) hat. Damit kann man fur einen endlichen Korper F[2b] and n + k < 2v den Reed-Solomon-Code erzeugen. Hierzu gibt es auch weitere Moglichkeiten (z.B. durch zufallige Wahl der Eintrage).
    Da der Verlust von k Blocken verkraftet werden kann, heiBen diese Codes auch Erasure Codes. Bedauerlicherweise ist der Berechnungsaufwand in Reed-SolomonCodes durch die Matrix-Multiplikation and die Invertierung der Matrix relativ hoch. Daher betrachtet man schneller berechenbare Erasure Codes, worunter jedoch die Redundanz der Codes leidet. In [ 109] wurde die Technik der Replikation von Daten mit Erasure Codes verglichen, wobei den Erasure Codes der Vorzug zu geben ist. Erasure Codes werden zum Beispiel in Dhash [39] and Oceanstore [110] eingesetzt.
12.6 Netzwerkkodierung
    Bei der Vorwartsfehlerkorrektur im vorigen Abschnitt musste im Vorhinein abgeschatzt werden, wie groB der auftretende Fehler ist. Mit der so genannten Netzwerkkodierung ist das nicht mehr notig. Sie wurde von Ahlswede, Cai, Li and Yeung eingefuhrt [111] and betrachtet die Informationsverteilung in einem Flussgraphen von den Quellen zu den Senken. In Abbildung 12.8 kann man die Ausgangspro- blemstellung sehen. Ziel ist die Verteilung der Bits x and y an die Senken. Jede Kante kann nur ein Bit weitergeben. Bei einer klassischen Information sverte Hung musste man sich auf der mittleren Kante fur x (Abb. 12.6) oder y (Abb. 12.7) entscheiden, worauthin entweder links die Information x oder rechts die Information y fehlt. Das Prinzip der Netzwerkkodierung beruht nun darauf, dass auf jeder Kante eine passende Kodierung der vorhandenen Informationen weitergegeben wird.
    In diesem Beispiel ubertragt man also die