Ein Vergleich von sender-initiierten und empfÀnger

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, dass er ein verschicktes Paket nicht empfangen hat, sendet er ein NAK zum Sender. Um zu gewĂ€hrleisten, dass 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, dass der Sender keine Pakete zum Senden hat (muss 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, dass 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, dass 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, dass alle Paketverluste gegenseitig unabhÀngig sind und dass 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[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 muss bei jedem TimerĂŒberlauf das Paket wiedergesendet und der Timer neu gesetzt werden. Somit setzt sich XAaus 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 - ASAund 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 ASAund am Receiver ARA berechnet.

AoA= min{ASA, ARA}

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])

4. Durchsatzanalyse von empfÀnger - initiierten Protokollen


(N1) Protokoll:

a) mittlere Bearbeitungsdauer am Sender - E[XN1]:

Hier wird XN1aus 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, dass 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 - ASNund ARN:

wie im Punkt c) beim (A) - Protokoll

d) Protokolldurchstaz:

d1) One - Many Applikationen AoN

AoN1= min{ASN1, ARN1}
AoN2= min{ASN2, ARN2}


d2) Many - Many Applikationen AmN

AmN1= (R+1)/(E[XN1] + RE[YN1])
AmN2= (R+1)/(E[XN2] + RE[YN2])

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, dass 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, dass 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, dass die Zeitverluste bei der DatenĂŒbertragung mit (N2) gleichmĂ€ĂŸig am Sender und am EmpfĂ€nger verteilt sind.

    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.
    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, dass 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, dass das (N2) - Protokoll fĂŒr One - Many Szenarien gut geeignet ist, wobei (N1) bessere Ergebnisse bei Many - Many Anwendungen erzielt werden. Das heißt, dass 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, dass 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.

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

2341 Worte in "deutsch"  als "hilfreich"  bewertet