Anwendungen wie verteilte Datenbanken und Shared Whiteboards benötigen ständig oder zu definierten Zeitpunkten eine konsistente Sicht auf ein System. Um dies zu erreichen, verwenden sie geeignete Protokolle zum Austausch von Nachrichten. Die Funktionalität zur Kommunikation kann entweder in die Anwendung selber integriert sein oder durch einen dedizierten Kommunikationsdienst erbracht werden. Dieser Kommunikationsdienst realisiert einen geordneten Multicast - also eine 1:N-Kommunikationsbeziehung, in der alle Empfänger versendete Nachrichten eines Senders in der gleichen Reihenfolge erhalten - oder sogar einen geordneten Multipeer-Dienst - also eine M:N-Kommunikationsbeziehung, in der alle Empfänger versendete Nachrichten mehrerer Sender in der gleichen Reihenfolge erhalten.
In diesem Bericht untersuche ich zwei unterschiedliche Lösungsansätze, die eine zuverlässige und skalierbare Multicast-Kommunikation garantieren. Im Falle einer sender-initiierter Lösung liegt die Verantwortung dafür beim Sender, welcher die Zustandsinformationen von allen Empfängern in zuständiger Multicast-Gruppe verwaltet. Dies ist möglich mittels positiver Bestätigungen (ACK's) von Empfängern bei jedem Paketempfang. Zusammen mit der Untersuchung der Zeitinformation am Sender kann eventueller Paketverlust entdeckt und ein fehlendes Paket wiedergesendet werden. Der zweite Ansatz - empfänger-initiiert - verschiebt die Überprüfung der Transportzuverlässigkeit an den Empfänger. Diese fordern die Paketsendewiederholung mit negativen Empfangsbestätigungen (NAK's). In One-Many Applikationen, mit einem Sender und mehreren Empfängern, leisten empfänger-initiierte Protokolle bessere Leistungen als sender-initiierte. Weitere Verbesserungen können mit Anwendung von zufällig langen Verzögerungen der NAK Paket-Sendung an der Empfängerseite erreicht werden. Bei den Applikationen, wo alle Stationen als Sender und gleichzeitig als Empfänger auftreten (Many-Many), wird der Durchsatz mittels point-to-point Retournieren von NAK's gegenüber dem sender-initiiertem Gegenstück fast verdoppelt. Multicasting von NAK's verbessert den Durchsatz nur unwesentlich. Diese Methode führt zu besseren Ergebnissen im One-Many Fall.
Ich werde drei generische Protokolle studieren, eines ist sender-initiiert und die anderen empfänger-initiiert. Fokussiert werden die fundamentale Unterschiede zwischen Verwendung von ACK's und NAK's und weiters die Gegenüberstellung von point-to-point Kanälen für NAK's und Multicasting von NAK's. Da sich in der Technologie die Verarbeitunsgeschwindigkeiten langsamer als die Kommunikationsbandbreiten verbessert, werden in dieser Analyse die Datenverarbeitungsmechanismen an einzelnen Knoten von diesem Protokoll untersucht. Zum Schluß wird noch die Skalierbarkeit der Protokolle behandeln, d. h. wie die wachsende Anzahl von Stationen die Leistung und den Durchsatz beeinflußt.
In diesem Kapitel beschreibe ich die oben vorgestellte Lösungsansätze für zuverlässige Datenübertragung in Multicast Applikationen. Analysiert werden die wichtigsten Charakteristiken von generischen ACK- und NAK-basierten Protokollen im allgemeinen.
Bei sender-initierten Protokollen retourniert der Empfänger nach jedem Paketempfang ein ACK Paket. Der Sender führt eine ACK-Liste für alle Empfänger, von denen er ACK-Pakete empfängt, die nach jedem ACK-Empfang aktualisiert wird. Mit jeder Paketsendung startet der Sender einen Timer mit bestimmter Ablaufszeit. Wenn vor der Ablaufszeit nicht alle (von allen Empfängern) ACK-Pakete ankommen, sendet der Sender noch einmal und startet den Timer neu. Weiter sollten die sender-initiierten Protokolle noch folgende Charakteristiken erfüllen:
Nur die Pakete werden wiedergesendet, die bei der Übertragung entweder beschädigt waren oder als verloren erkannt wurden.
Ein Paket wird immer an alle Empfänger in der Multicastgruppe gesendet und der Timer neu gestartet, auch bei der Wiedersendung.
Immer wenn der Empfänger ein Paket korrekt empfängt, sendet er ein ACK-Paket über eine point-to-point Verbindung zum Sender.
Sobald ein Timer abläuft, wird das korrespondierende Paket immer an alle Empfänger in der Multicastgruppe wiedergesendet.
Dieses Protokoll werde ich weiter als (A) bezeichnen.
Bei diesem Protokoll liegt die Verantwortung für eine zuverlässige Datenübertragung beim Empfänger. Der Sender verschickt Pakete bis er ein NAK-Paket vom Empfänger empfängt. Sobald dieses geschieht, wiederholt der Sender die Übertragung des verlorenes Paket an alle Empfänger. Wenn ein Empfänger entscheidet, daß er ein verschicktes Paket nicht empfangen hat, sendet er ein NAK zum Sender. Um zu gewährleisten, daß das NAK Paket nicht verloren geht, verwendet der Empfänger einen Timer, in ähnlicher Weise wie der Sender beim (A). Ein verlorenes Paket wird erkannt, wenn der Empfänger ein Paket mit einer größeren Sequence-Nummern empfängt als erwartet, oder nach einem Timeout bei der Wiedersendung. Im Falle, daß der Sender keine Pakete zum Senden hat (muß er warten bis die Pakete produziert werden), sendet er seine Zustandsinformation, z.B. die Sequence-Nummer vom zuletztgesendeten Paket. Man kann zwei Varianten von receiver-initiierten Protokollen unterscheiden:
(N1) Protokoll:
Der Sender sendet alle Pakete im Multicast-Verfahren.
Sobald ein Empfänger ein verlorenes Paket erkennt, sendet er NAK über point-to-point Verbindung zum Sender und startet einen Timer.
Wenn der Timer abläuft, ohne das korrespondierende Paket zu empfangen, wird ein Paketverlust erkannt.
(N2) Protokoll:
Der Sender sendet alle Pakete und eine Zustandsinformation im Multicast-Verfahren.
Sobald der Empfänger einen Paketverlust erkennt, wartet er eine zufällig-lange Dauer, dann sendet er einen Multicast-NAK an den Sender und alle anderen Empfänger und startet den Timer.
Empfängt ein Empfänger während der Wartezeit (Verzögerung) ein NAK-Paket vom anderen Empfänger, startet er einen Timer und verhält sich als ob er ein NAK gesendet hätte.
Das Ablaufen dieses Timers ohne vorherigen Empfang des korrespondierenden Pakets bedeutet seinen Verlust.
Da das zuerst generierte NAK-Paket noch vor weiteren NAK-Generierungen zu anderen Empfängern gelangt, wird fast immer gewährleistet, daß während einer Paketübertragung höchstens ein NAK zum Sender retourniert wird.
Angenommen es gibt R + 1 Teilnehmer, die eine zuverlässige Datenübertragung benötigen. In folgenden werden zwei Arten von Applikationen behandelt:
One-Many Applikation - ein Sender sendet kontinuierlich Pakete an den Empfänger R, z.B. Telelektüre oder Telekonferenz, wo nur ein Teilnehmer als Sender auftritt.
Many-Many Applikation - mehrere oder alle Teilnehmer treten als Sender auf, d. h. die Wahrscheinlichkeit, daß ein Teilnehmer ein zufällig gewähltes Paket sendet, ist 1/(R + 1). (z.B. verteilte interaktive Simulationen, DIS).
In der Durchsatzanalyse wird in beiden Fällen angenommen, daß alle Paketverluste gegenseitig unabhängig sind und daß die Wahrscheinlichkeit eines Paketverlustes unabhängig vom Empfänger ist. Weiters wird angenommen, das ACK- und NAK-Pakete nie verloren gehen.
Das Ziel der Analyse ist die Bearbeitungszeit am Sender und am Empfänger, die notwendig zur erfolgreichen Paketübertragung vom Sender zu allen Empfängern ist, zu berechnen. Diese Bearbeitungszeit beinhaltet die Zeit die benötigt wird für Paket-Sendung/Empfang, weiter die eventuelle Wiedersendungszeiten, Timeouts und ACK/NAK-Pakete-Sendung. Der Reziprokwert dieser Bearbeitungszeit ist dann die maximale Rate, mit der der Sender und Empfänger neue Pakete bearbeiten. Für ein bestimmtes Protokoll ((A), (N1), (N2)) und eine bestimmte Applikationsstruktur (One-Many, Many-Many), kann mit Hilfe dieser Rate der maximale Protokoll-Durchsatz bestimmt werden.
(A) Protokoll:
Die Analyse erfolgt in folgenden Schritten:
a) mittlere Bearbeitungsdauer am Sender - E[XA]:
Das ist jene Zeit, die der Sender zum Senden von einem Multicast-Paket zu allen Empfängern benötigt. Die Messung startet wenn der Sender das Paket vom übergeordneten Protokoll erhält. Danach wird das Paket vorbereitet, gesendet, der Timer gestartet und die ACK-Pakete von Empfängern bearbeitet. Außerdem muß bei jedem Timerüberlauf das Paket wiedergesendet und der Timer neu gesetzt werden. Somit setzt sich XA aus der Summe der Paketsende- und Timeoutbearbeitungsdauer am Sender (mit einzelnen Empfängern im Multicast korrespondierende Werte) und der Summe von nachträglicher Bearbeitungsdauer von retournierten ACK's zusammen.
b) mittlere Bearbeitungsdauer am Empfänger - E[YA]:
Das ist mittlere Zeit, die für die Bearbeitung von zufällig gewähltem Paket am Empfänger benötigt wird. Diese Zeit setzt sich aus Bearbeitung des empfangenen Pakets und Generierung und Sendung des ACK-Pakets zusammen.
c) Bearbeitungsrate am Sender und max. Bearbeitungsrate am Empfänger - ASA und ARA:
Diese Werte werden als 1/E[XA] bzw. 1/E[YA] berechnet.
d) Protokolldurchstaz:
d1) One-Many Applikationen AoA
Der Protokolldurchsatz wird in diesem Fall als Minimum aus der Paket-Bearbeitungsdauer am Sender ASA und am Receiver ARA berechnet.
AoA = min
d2) Many-Many Applikationen AmA
In diesem Fall ist die mittlere Bearbeitungsdauer E[XA]/(R+1) + RE[YA]/(R+1), daher ist der Durchsatz:
AmA = (R+1)/(E[XA] + RE[YA])
(N1) Protokoll:
a) mittlere Bearbeitungsdauer am Sender - E[XN1]:
Hier wird XN1 aus der Summe von einzelnen Paketsendedauern am Sender und der Summe von nachträglicher Bearbeitungsdauer von retournierten NAK's zusammengesetzt.
b) mittlere Bearbeitungsdauer am Empfänger - E[YN1]:
E[YN1] ist abhängig von der Zeit die benötigt ist für den Paketempfang und von der Zeit die benötigt ist für die Vorbereitung und die Sendung von NAK's. Dazu kommt noch die Zeit, die für die Handlung nach dem Timerablauf notwendig ist.
(N2) Protokoll:
Das (N2)-Protokoll unterscheidet sich vom (N1) in zwei Punkten. Zuerst werden die NAK's als Multicast-Pakete an die restlichen Empfänger und an den Sender gesendet. Wenn ein Empfänger ein NAK korrespondierend mit einem noch nicht erhaltenem Paket vor der eigenen NAK-Sendung erhält, braucht er das NAK-Paket nicht senden. Die zufällig lange Verzögerung vor der NAK-Sendung gewährleistet, daß im Falle eines Paketverlustes meistens nur ein NAK-Paket von allen Empfänger in der Multicastgruppe generiert wird. Der Erfolg dieses Protokolls hängt von der Netzwerktopologie und von der zufälligen Zeitspanne ab.
c) Bearbeitungsrate am Sender und am Empfänger - ASN und ARN:
wie im Punkt c) beim (A)-Protokoll
d) Protokolldurchstaz:
d1) One-Many Applikationen AoN
AoN1 = min
AoN2 = min
d2) Many-Many Applikationen AmN
AmN1 = (R+1)/(E[XN1] + RE[YN1])
AmN2 = (R+1)/(E[XN2] + RE[YN2])
In diesem Abschnitt werden relative Leistungen von den Protokollen (A), (N1) und (N2) behandelt. Die eingeführten Werte wurden am DEC-Station 5000/200 unter ULTRIX 4.2a Betriebsystem gemessen. Zuerst werden die Paket-Sende- und Empfangsraten bei einzelnen Protokollen verglichen.
Die Messungen haben gezeigt, daß der Sender einen Flaschenhalls beim (A) Protokoll darstellt, sowohl bei der Messung mit Paketverlustwahrscheinlichkeit p = 0.25 als auch bei p = 0.05. Mit der wachsenden Anzahl der Empfänger verschlechtert sich die Senderate. Dieses wird durch die wachsende Anzahl der ACK-Antworten verursacht. Die Empfangsrate ist höher als die Senderate, aber sie verschlechtert sich auch mit der Anzahl der Empfänger. Die gemessenen Werte bei (N1) und (N2)-Protokollen zeigen, daß die Senderaten besser als bei (A) sind, wobei bei (N2) sind die Sende- und Empfangsraten viel mehr ausgeglichen wie bei (A) und (N1). Das heißt, daß die Zeitverluste bei der Datenübertragung mit (N2) gleichmäßig am Sender und am Empfänger verteilt sind.
a) One-Many Applikationen
Bei One-Many Applikationen wird der Datendurchsatz vom Sender determiniert , also
Ao = AS für (A), (N1) und (N2).
(N1) vs. (A)
Aus der Sicht des Durchsatzes (mit wachsender Anzahl der Empfängern - R) erzielt (N1) bessere Ergebnisse als (A) bei jeder Paketverlustwahrscheinlichkeit. Der Unterschied in relativen Leistungen ist höher mit kleinen Verlustwahrscheinlichkeiten; dies passiert, weil das sender-initiierte Schema eine Menge von unnötigen ACK's produziert, die den Sender belasten. Die relative Leistung von (N1) wird gegenüber von (A) logarithmisch mit wachsendem R erhöht.
(N2) vs. (N1)
Mit wachsendem R erhöht das Multicasting von NAK's bei (N2) den Durchsatz, speziell bei hohen Verlustwahrscheinlichkeiten.
b) Many-Many Applikationen
(N1) vs. (A)
Die Leistung von empfänger-initiiertem (N1) ist bei Many-Many Applikationen zwar fast doppelt so hoch wie beim (A), jedoch ist der Unterschied nicht so groß, wie bei One-Many Anwendungen. Die Ursache dafür ist, daß auf jeder Station die empfänger-seitige Paketverarbeitung durchgeführt wird. Somit haben die sender-spezifischen Ereignisse fast keinen Einfluß auf die gemessenen Werte. Auch die relative Bearbeitungsrate zwischen (N1) und (A) liegt unter 50%.
(N2) vs. (N1)
Mit Ersetzung der point-to-point Übertragung von NAK's (N1) durch Multicasting von NAK's (N2) wird der Durchsatz reduziert. Dies passiert, weil die Multicast-Übertragung von NAK's die Komplexität der Verarbeitung an Empfängern erhöht, und diese beeinflußt wesentlich die Leistung bei Many-Many Anwendungen.
(N2) vs. (A)
Trotz der Verschlechterung der Leistung durch das Einsetzen des (N2) statt (N1) ist diese immer noch leicht höher als der gemessene Wert bei (A).
In diesem Bericht wurde das Problem der zuverlässigen Datenübertragung in größeren Netzwerken (mit Tausenden Teilnehmer in der Multicastgruppe) untersucht. Vorgestellt wurden drei generische Protokolle, ein sender-initiierter (A) und zwei empfänger-initiierte (N1), (N2). Fokussiert wurde an die Bearbeitung der Daten an einzelnen Knoten, nicht an die Netzwerkbandbreite, wie bei vielen anderen Analysen.
Die Analyse hat gezeigt, daß das (N2)-Protokoll für One-Many Szenarien gut geeignet ist, wobei (N1) bessere Ergebnisse bei Many-Many Anwendungen erzielt werden. Das heißt, daß die relative Leistung der zuverlässigen Protokolle auch davon abhängig ist, welche Funktion (Senden od. Empfangen) die einzelnen Multicast-Teilnehmer repräsentieren.
Diese Untersuchung kann noch um weitere Aspekte erweitert werden. Es wurde angenommen, daß die Verluste an einzelnen Empfängern voneinander unabhängig waren. Weitere Themen sind die Zeitverluste (Verzögerungen) der einzelnen Protokolle und die zahlreichen Optimierungen, die man anwenden kann.
Don Towsley, Jim Kurose, Sridhar Pingali - "A Comparison of Sender-Initiated and Receiver-Initiated Reliable Multicast Protocols", IEEE Journal on Selected Areas in Communications, Vol. 15, No. 3, April 1997, Page 398
Stefan Dresler - "Protokolle für eine geordnete Auslieferung in Multicast-Gruppen", April 1997, MARB
Anan Oswal - "IB - Reliable Multicast Transport protocol", http://www.isi.edu/
