Referat Ein Vergleich von sender-initiierten und empfänger-initiierten zuverlässigen Multicast- Protokollen

Ein Vergleich von sender-initiierten und empfänger-initiierten zuverlässigen Multicast- Protokollen

1 Motivation

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.

2. Protokolle und das Systemmodell

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.

Sender initiierte Protokolle

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.

Receiver-initiierte Protokolle

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.

Applikations , Netzwerk- und Fehlermodelle

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.

3. Durchsatzanalyse von sender-initiierten Protokollen

(A) Protokoll:

Die Analyse erfolgt in folgenden Schritten:

a) mittlere Bearbeitungsdauer am Sender - E[X^A

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 X^A 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[Y^A

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 - A_S^A und A_R^A

Diese Werte werden als 1/E[X^A] bzw. 1 E[Y^A] berechnet.

d) Protokolldurchstaz:

d1) One-Many Applikationen A_o^A

Der Protokolldurchsatz wird in diesem Fall als Minimum aus der Paket- Bearbeitungsdauer am Sender A_S^A und am Receiver A_R^A berechnet.

A_o^A = min

d2) Many-Many Applikationen A_m^A

In diesem Fall ist die mittlere Bearbeitungsdauer E[X^A]/(R+1) + RE[Y^A]/(R+1), daher ist der Durchsatz:

A_m^A = (R+1)/(E[X^A] + RE[Y^A

4. Durchsatzanalyse von empfänger-initiierten Protokollen

(N1) Protokoll:

a) mittlere Bearbeitungsdauer am Sender - E[X^N

Hier wird X^N 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[Y^N

E[Y^N ] 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 - A_S^N und A_R^N

wie im Punkt c) beim (A)-Protokoll

d) Protokolldurchstaz:

d1) One-Many Applikationen A_o^N

A_o^N = min A_o^N = min

d2) Many-Many Applikationen A_m^N

A_m^N = (R+1)/(E[X^N ] + RE[Y^N ]) A_m^N = (R+1)/(E[X^N ] + RE[Y^N

5. Gemessene Ergebnisse

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

A_o = A_S  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).

6. Zusammenfassung

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.

. Literatur

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", https://www.isi.edu/