Peer-to-Peer-Netzwerke: Algorithmen und Methoden

zu stellen, empfiehlt es sich, die Last auf das so genannte Knie einzustellen. Beim Knie steigt die Antwortzeit erstmals an, wahrend der Datendurchsatz schon nahe der Netzwerkkapazitat ist. Eine gute Stauvermeidungsstrategie (Congestion Avoidance) versucht, die Datenlast des Netzwerks bei diesem Knie zu halten. Neben dem Datendurchsatz ist es aber auch wichtig, dass die Datenraten aller Teilnehmer gleich sind, also fair gewahlt werden.
    Abb. 2.14. Netzwerkverhalten in Abhangigkeit der Datenlast.
    Fur ein einfaches Netzwerkmodell kann man das gutartige Verhalten von TCP sogar nachweisen. Hierzu nehmen wir an, dass n Nutzer teilnehmen and B die verfugbare Bandbreite ist. Das System wird in Runden modelliert. Zu Beginn (d.h. in Runde 0) hat Teilnehmer i E {1, ... , n} Datenrate xz(0) E [0, B]. In jeder weiteren Runde t kann der Teilnehmer seine Datenrate auf xi(t) E [0, B] setzen. In Runde t + 1 steht ihm, neben seiner alten Datenrate, nur die Information zur Verfugung, ob in der Runde t die Summe der Datenraten das Ziel K E [0, B] Uberschritten hat, d.h. ob
    xi (t) < K

    wobei K fur die Datenlast an der oben beschriebenen Knieposition steht. Wir bezeichnen mit dem Pradikat y(t) = 0, dass diese Ungleichung in Runde t erfullt wird and mit y(t) = 1 das Gegenteil.
    Jeder Teilnehmer bestimmt nun in Runde t + 1 aufgrund von y(t) and seiner alien Datenratenwahl xi (t) die Datenrate der nachsten Runde. Diese Entscheidung beschreiben wir durch eine Funktion f : [0, B] x {0, 1} -* [0, B], wobei fur alle i E {1, ... , n} gilt

    Das bedeutet insbesondere, dass alle Teilnehmer sich an dieselbe Datenratenanpas- sungsstrategie f halten. Damit wenden alle Teilnehmer in Runde t + 1 entweder die Funktion
    fo(x) = f (x, 0) oder fi(x) = f (x, 1)
    an, and es ergibt sich die Grundanforderung an fo and fl:

    Hierbei ist nicht unmittelbar klar, ob diese Eigenschaft fur alle Spieler gelten muss. Wir mochten daher der Wahl der Funktionen fo and ft eine Funktionenklasse zugrunde legen and diese gemaB einiger Schlusselkriterien untersuchen.
    In diesem Abschnitt beschranken wir uns fur die Wahl der Funktionen fo and fl auf line are Funktionen:

    Folgende Spezialfalle sind besonders interessant. Wir werden sie daher gesondert betrachten:
    1. Multiplicative Increase/Multiplicative Decrease (MIMD)
    fo(x) = bix and ft (x) = bDx ,
    wobei bI > 1 and bD < 1.
    2. Additive Increase/Additive Decrease (AIAD)
    fo(x)=al+x and fl(x)=aD+x,
    wobei aI > 0 and aD < 0.
    3. Additive Increase/Multiplicative Decrease (AIMD)
    fo (x) = al + x and fi (x) = bDx ,
    wobei aI > 0 and bD < 1.

    Die Schlusselkriterien sind Effizienz and Fairness. Die Datenraten verschiedener Teilnehmer sind absolut fair, wenn xi (t) = xj (t) fur alle i, j gilt. Die Effizienz wird durch die Nahe der Gesamtlast

    an der Knielast K gemessen. Ist X (t) > K, verlangert sich die Antwortzeit, and ist sogar X (t) > B, gehen Datenpakete verloren and mussen erneut versendet werden. Ist dagegen X (t) < K, entstehen Opportunitatskosten dadurch, dass die Netzwerkkapazitat nicht ausgenutzt wird.
    Fur zwei Teilnehmer kann man dieses System sehr gut grafisch untersuchen. In Abbildung 2.15 werden die Datenrate xi des ersten Teilnehmers and die Datenrate x2 eines zweiten Teilnehmers als Punkt (x1i x2) dargestellt. Die Effizienzlinie bezeichnet alle Punkte, die die Netzwerklast X im optimalen Bereich K halten, d.h. X1 + x2 = K. Punkte unter dieser Linie stehen fur Netzwerkzustande, die das Netzwerk zu wenig belasten, Punkte daruber fur eine Uberlastung des Netzwerks. Mit der Fairnesslinie werden alle Punkte mit x1 = x2 dargestellt. Je nachdem, ob man uber oder unter dieser Linie steht, erhalt x2 oder xi eine hohere Datenrate.
    Fur Datenraten (x1i x2) bezeichnen Datenraten (x1 + c, x2 - c) Netzwerkzustande gleicher Effizienz, da X = x1 + x2 konstant bleibt. Multipliziert man dagegen die Datenraten mit einem Faktor c > 0, so erhalt sich die Fairness, wie man hier sieht:

    In Abbildung 2.16 sind die Punkte gleicher Effizienz and gleicher Fairness wie (Xi, x2) dargestellt.
    Mit Hilfe dieses Diagramms kann man nun leicht die Schwachen der AIAD- und MIMD-Strategie beschreiben. Wahlt man die AIAD-Strategie (Additive Increase/Additive Decrease), so bewegen sich die Datenraten auf einer Linie (x1 + y, x2 + y). Hiermit ist es zwar moglich, sich der Effizienzlinie his auf einen additiven Term von max{al, -aD} (entspricht der Oszillationsamplitude) anzunahern, es ist aber nicht moglich die Fairness zu verbessern (Abbildung