Peer-to-Peer-Netzwerke: Algorithmen und Methoden

arbeiten and derzeit kaum ausgenutzt werden. Im Gegensatz zu Kupferkabeln kann man hier technologisch aufrusten, ohne das Medium (das Kabel) austauschen zu mussen. Nur durch Ersetzen der beiden Endstellen kann man die Datenkapazitat vervielfachen. Es kann also davon ausgegangen werden, dass das Internet mit dem Peer-to-Peer-Netzwerk-Verkehr mitwachsen wird and der Einfluss von Peer-to-Peer-Netzwerken noch zunehmen wird.

A

Mathematische Grundlagen
A.1 Algebra
    Ein algebraischer Korper ist ein kommutativer unitarer Ring, in dem jedes von Null verschiedene Element multiplikativ invertierbar ist, d.h., es mussen folgende Eigenschaften gelten:
    1. Addition
    Fur die Addition mussen die folgenden Gesetze gelten:
    a) Assoziativitat: a + (b + c) = (a + b) + c
    b) Kommutativitat: a + b = b + a
    c) Neutrales Element: Es gibt die Null, also 0 + a = a
    d) Additives Inverses: Fur jedes a gibt es ein Inverses -a mit a + (-a) = 0
    2. Multiplikation
    a) Assoziativitat: a • (b • c) = (a • b) • c
    b) Kommutativitat: a • b = b • a
    c) Neutrales Element: Es gibt die Eins, also 1 • a = a
    d) Zu jedem Element a, das nicht Null ist, gibt es multiplikativ Inverses a-1 mita•a-1=1
    3. Es gilt das Distributivgesetz: a - (b + c) = a - b + a - c
    Aus der Schule kennt man die Korper der rationalen Zahlen, reellen Zahlen and komplexen Zahlen. Hier werden auch endliche Korper verwendet: die so genannten Galois-Korper (mit 2k Elementen) and Restklassenringen uber den Zahlen Zp = {0, 1, . . . , p - 1}, in denen die Addition and Multiplikation beziiglich Rest p betrachtet wird.
    Die Galois-Korper werden nicht Ober Restklassenringe definiert. Vielmehr betrachtet man hierzu ein Polynom vom Grad k - 1 als Zahl

    die durch die Bitfolge a = al, ... , ak definiert wird. Die Variablen xi werden niemals eingesetzt oder umgeformt. Sie bleiben als algebraische Rechensymbole stehen. Die Addition zweier Zahlen im Galois-Korper ergibt sich nun durch

    Die Multiplikation ergibt sich durch

    wobei q(x) ein irreduzibles Polynom ist, das keine Faktorzerlegung in Polynome a(x), b(x) mit mindestens Grad Eins hat. Ein irreduzibles Polynom vom Grad 2 ist zum Beispiel: q(x) = x2 +x+ 1.
    Bei der Polynommultiplikation werden jeweils die Variablen x mitmultipliziert:

    Die Polynomdivision wird analog durchgefuhrt.
Logarithmen, Kombinatorik and Wachstumsklassen
    Wir bezeichnen mit In n = loge n den naturlichen Logarithmus zur Basis e zz~ 2.718281828.... Ferner bezeichnet log n = loge n den Logarithmus zur Basis 2. Mit logk n wird (log n)k abgekurzt.
    Fur die Eulersche Zahl e gilt:

    and insbesondere fur alle n E N:

    Um das asymptotische Wachstum von Funktionen zu vergleichen, wird die so genannte 0-Notation verwendet. Fur Funktionen f, g : R+ R+ wird definiert:

    Der Term f (n) = O(g(n)) besagt nun, dass die Funktion f (n) bis auf einen konstanten Faktor hochstens so schnell wachst wie g(n). Dieser Term ist equivalent zu g(n) = ,Q(f (n)). Wenn f (n) and g(n) in derselben Wachstumsklasse liegen, dann sind sie his auf einen Faktor in einer konstanten Schwankungsbreite gleich: g(n) = (9 (f (n))•
    Um Aussagen treffen zu konnen, dass eine Funktion echt starker wachst als eine andere Funktion, wird nun f (n) = w(g(n)) verwendet, was das Gegenteil von f (n) = O(g(n)) beschreibt. Fur echt schwacher wird f (n) = o(g(n)) verwendet, was das Gegenteil von f (n) = P(g(n)) beschreibt.
A.2 Graphtheorie
    Das wichtigste mathematische Konzept far Rechnernetzwerke ist der Graph. Ein Graph G = (V, E) besteht aus einer Knotenmenge V and einer Kantenmenge E. Man unterscheidet folgende Typen von Graphen:
    • Der ungerichtete Graph hat als Kantenmenge zweielementige Mengen von Knoten. Der Grad eines Knoten im Graphen ist die Anzahl der Kanten in der Kantenmenge E, die diesen Knoten gemeinsam haben. Der Grad eines Graphen ist der maximale Grad eines Knotens.
    In Abbildung A.1 ist der Graph mit der Kantenmenge {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}} dargestellt.
    Abb. A.I. Ein ungerichteter Graph.
    Er kann zum Beispiel verwendet werden, um Netzwerke mit bidirektionalen Verbindungen wie etwa TCP-Verbindungen zu beschreiben.
    • Der gerichtete Graph hat als Kantenmenge Paare (Tupel) von zwei verschiedenen Knoten, wie zurn Beispiel (u, v). Zuweilen werden auch Selbstkanten erlaubt. Durch die Reihenfolge wird die Richtung angezeigt. Der erste Knoten zeigt auf den zweiten. Man unterscheidet in gerichteten Graphen Eingrad and Ausgrad. Der Ausgrad ist die Anzahl