Peer-to-Peer-Netzwerke: Algorithmen und Methoden

Summe aller Kosten auf den Kamen minimiert wird. Dieses Problem ist die diskrete Version des so genannten Steiner-Baum-Problems, welches im kontinuierlichen euklidischen Raum ArP-vollstandig ist. Fur die lokale Optimierung kennt man gute Losungen, bekannt durch das Seifenblasenexperiment [98]. Hierbei werden zwei parallele Glasplatten mit senkrecht verbindenden Staben in Seifenwasser getaucht. Beim Herausholen bildet sich ein Seifenfilm zwischen den Staben, der eine minimale Oberflache anstrebt (siehe Abbildung 12.1). Mit etwas Gluck bildet sich hierbei ein Steiner-Baum zwischen den Positionen der Stabe.

    Abb. 12.1. Das Seifenblasenexperiment.
    Die diskrete Variante ist, einen Baum in einem gegebenen ungerichteten Graphen zu finden, so dass die Summe der Distanzen des Baumes, der eine gegebene Menge von Knoten verbindet, minimiert wird. Wahrend fur das kontinuierliche Problem wenigstens effiziente Approximationsalgorithmen bekannt sind, ist das Problem im diskreten Fall schwieriger.
    In den Router-Knoten ohne Verzweigung werden die Nachrichten wie bei einer Unicast-Verbindung einfach weitergereicht. An den Verzweigungsknoten des Baumes werden die Nachrichten dupliziert and in die beiden Teilbaume durchgereicht. An den Blattern des Router-Baumes werden schlieBlich alle angemeldeten Hosts mit Kopien der Pakete versorgt. Fur die Etablierung eines solchen Multicast-Baumes gibt es verschiedene Protokolle.
    Das erste war das Distance-Vector-Multicast-Routing-Protocol (DVMRP), das jahrelang im so genannten MBONE, einem Multicast-fahigen Teilnetzwerk des Internets, eingesetzt wurde. Mittlerweile hat sich das PIM-SM (Protocol Independent Multicast - Sparse Mode) [99] weitestgehend durchgesetzt. Wahrend DVM- RP noch eigene Multicast-Routing-Tabellen verwendet hat, ist PIM-SM weitgehend protokollunabhangig. Es verwendet die Unicast-Routeninformation, um auch den Multicast-Verkehr zu befordern. Hierzu ist mindestens ein designierter Rendezvous- Punkt (RP) in jeder Domain notwendig. Dieser dient als Anlaufstation fur die lokale Organisation des Multicast-Baumes. Von der Quelle wird ein Kurzester-Wege-Baum zu den RPs der angemeldeten Hosts konstruiert. Ein Kurzester-Wege-Baum ist die Vereinigung aller kurzesten Wege von einem Knoten, hier der Quelle, zu einer Menge von Knoten, hier die RPs. In der Praxis kann es vorkommen, dass dieser Baum nicht aus kurzesten Wegen besteht, da die Informationen aus den ,normalen" Unicast- Routing-Tabellen verwendet werden.
    Da TCP fur Multicast nicht verwendet werden kann and UDP keine Sicherung gegen den Verlust von Paketen hat, konnen Multicast-Nachrichten nicht ohne wei teres bestatigt werden. Um einen zuverlassigen Multicast zu erreichen, gibt es zwei Losungen. Die erste arbeitet mit Vorwdrtsfehlerkorrektur (Forward Error Correction). Hierbei werden die Nachrichten redundant kodiert, so dass der Verlust einer bestimmten Menge von Paketen kompensiert werden kann. Auf der anderen Seite kann man die Bestatigungen in den Routern uberprufen and so in der Vermittlungsschicht die Nachrichten absichern (und neu versenden). In diesem Zusammenhang ist Ciscos PGM (Pragmatic General Multicast) [100] zu erwahnen.

    Die Adressmethode von Multicast kann auf der Mediumzugriffsebene (Medium Access Control - MAC) im lokalen Netzwerk zu Kollisionen fuhren. AuBerdem besteht durch Multicast die besondere Gefahrdung durch so genannte Denial-ofService-Angriffe, die man gesondert abwehren muss. Im Vergleich zu Unicast ist der Wartungs- and Konfigurationsaufwand wesentlich groBer, wahrend these Dienste Beim Endkunden kaum nachgefragt werden. Somit ist der kommerzielle Druck auf die Internet-Service-Provider nicht groB genug, um die zusatzlichen Kosten zu rechtfertigen.
    Es ist dartiber hinaus nicht klar, ob der Aufwand eines IP-Multicasts zum Vertrieb einer einzelnen Datei an viele andere Teilnehmer gerechtfertigt ist. Zum einen ist die Anzahl moglicher Interessenten oftmals sehr gering. Zudem kommen die Anfragen nicht zeitgleich. Wird eine Ubertragung dann initiiert and kommt spater ein neuer Interessent hinzu, so muss die Ubertragung wiederholt werden. Eine andere Frage ist, ob IP-Multicast sich ohne weiteres mit den Problemen, die DHCP, NAT and Firewalls bereiten, vereinbaren lasst.

    Abb. 12.2. Der IP-Multicast-Baum.

12.2 Scribe
    Da IP-Multicast in der Regel nicht zur VerfUgung steht, wurde nach gangbaren Al- ternativen gesucht. Eine hiervon nennt sich Scribe and wurde von Castro, Druschel and Kermarrec in [101]