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.