Multicast

Multicasting oder Multiple Broadcasting (von englisch : multicast ) ermöglicht das gleichzeitige Versenden von Informationen an mehrere Teilnehmer eines Netzwerks von einem Punkt oder Knoten aus . Anders als beim Broadcasting werden die Empfänger jedoch zuvor vom Sender ausgewählt . Das bedeutet, dass das Senden eingeschränkt ist und nicht alle Benutzer in einem Netzwerk die Daten erhalten ​.

Vor dem Senden der Informationen müssen eine Reihe von Parametern festgelegt werden. Um es zu empfangen, ist es notwendig, eine sogenannte "Multicast-Gruppe" einzurichten. Dieser Multicast-Gruppe ist eine Internet -Adresse zugeordnet , auf diese Weise sendet der Absender der Multicast -Nachricht diese an eine oder mehrere Gruppen und später erreicht die Nachricht die Prozesse, die an dieser Gruppe abonniert sind, wobei ein Prozess abonniert werden kann zu mehreren zur Zeit Die aktuelle Version des Internetprotokolls (IP), bekannt als IPv4 , reserviert Typ-D-Adressen für Multicasting. IP-Adressen sind 32 Bit lang , und Typ-D-Adressen sind solche, bei denen die 4 höchstwertigen Bits „1110“ ( 224.0.0.0a 239.255.255.255) sind.

Multicasting im Internet

Routing
Einzelsendung ( Unicast )
Einige Sendungen ( Anycast )
Breite Verbreitung ( Rundfunk )
Mehrfachübertragung ( Multicast )
Geocasting ( Geocast )

Einige Beispiele für Multicasting im Internet sind:

• IEEE 802.1aq – Shortest Path Bridging (SPB)
• IP-Multicast
• Internet-Relay-Chat (IRC)
• NNTP
• PSYK
• Peercasting mit Punkt-zu-Punkt -Verbindungen ( Peer-to-Peer ).

Wie es funktioniert

Die oben erwähnte Gruppenadressierung ist eine der Schlüsseleigenschaften von IP-Multicast, da sie grundlegend für das Funktionieren dieses Kommunikationskonzepts ist. Zusätzlich besteht die Möglichkeit, eine statische Adresse zu vergeben, in der beispielsweise eine Verbindung zu einem Multicast-Server konfiguriert werden kann, damit dieser den entsprechenden Dienst anbietet.

Zuverlässigkeit

Bormann ​ definiert den Begriff der Zuverlässigkeit aus Sicht des Senders und Empfängers der Nachricht. Aus Sicht des Zweiten gilt das Protokoll als zuverlässig, wenn es feststellen kann, wann es fehlschlägt. Andererseits gilt es aus Sicht des Senders als zuverlässig, wenn sichergestellt ist (mit hinreichender Wahrscheinlichkeit), dass alle Nachrichten innerhalb eines Zeitlimits bei allen nicht ausgefallenen Empfängern ankommen. Das heißt, der Zuverlässigkeitsbegriff steht in weitem Zusammenhang mit Fehlererkennungs- und Wiederherstellungsmechanismen.

Hinsichtlich des Konzepts der Zuverlässigkeit bei Multicast kann die folgende Definition gegeben werden: Der Begriff Zuverlässigkeit bei Multicast entspricht der endgültigen Lieferung aller Daten an alle Mitglieder der Gruppe, ohne dass eine bestimmte Lieferreihenfolge eingehalten wird. ]

Zwei Arten von Multicast werden je nach verwendetem Fehlerbehebungsverfahren unterschieden: Sender-initiiert oder Empfänger-initiiert. ]

Einfaches Multicast

Beim einfachen Multicast betrachten wir die Kommunikation als zuverlässig Eins-zu-Eins. Bei dieser Art von Multicast schlagen wir ein Protokoll vor, bei dem ein vom Sender initiiertes Fehlerwiederherstellungsverfahren verwendet wird , d. h. eines, bei dem der Absender für die Fehlerwiederherstellung verantwortlich ist und darin besteht, dass jeder Empfänger eine Empfangsbestätigung (ACK) an den sendet Absender, wenn eine Nachricht von ihm eintrifft.

Dieses Verfahren ist in Umgebungen problematisch, in denen es mehrere Multicast -Gruppen gibt, da eine große Anzahl von ACKs den Sender erreichen, was eine sogenannte ACK-Implosion verursacht, bei der der Sender gesättigt ist.

Bei dieser Art von Multicast wird die Nachricht mindestens einmal zugestellt, sodass Duplizierungsprobleme auftreten können. Darüber hinaus sagen wir, dass es eins-zu-eins zuverlässig ist, da es nicht dem Konzept der Übereinstimmung oder Unteilbarkeit entspricht: Wenn ein Prozess eine Nachricht empfängt, dann empfängt sie die gesamte Gruppe; oder alle oder keine.

Grundlegende Multicast-Struktur.

Zuverlässiges Multicast

Multicast wird häufig für Multimediaverkehr verwendet, sodass gelegentlicher Paketverlust kein Problem darstellt. Hinzu kommt, dass IP-Multicast sehr zuverlässig ist und mit den im Basic-Multicast erwähnten Problemen häufig IP-Multicast über UDP verwendet wird .

Bei diesem Typ wird das zweite oben erwähnte Fehlerwiederherstellungsverfahren verwendet, das empfängerinitiierte Verfahren, bei dem der Empfänger für die Fehlerwiederherstellung verantwortlich ist. Das heißt, Empfangsbestätigungen (ACK) werden nicht separat gesendet, sondern der Absender sendet sie als Anhang an andere Nachrichten, die an die Gruppe gesendet werden, um den Empfang früherer Nachrichten zu bestätigen, was als Huckepack bezeichnet wird (der Absender sendet beispielsweise eine Nachricht X an einen Prozess p und bestätigt durch ein angehängtes ACK, dass er zuvor eine Nachricht von p korrekt erhalten hat ). Darüber hinaus senden Empfänger separate negative Bestätigungen (NACK), wenn ein Nachrichtenverlust erkannt wird.

Auch bei diesem Verfahren kann es zu einer Implosion kommen, jedoch von NACK. Um dies zu vermeiden, wenn eine bestimmte Anzahl von Empfängern die aktuelle Nachricht nicht, aber die nächste erhalten, starten sie ein zufälliges Timeout und das NACK wird nur einmal von dem Empfänger an den Sender gesendet, dessen zufälliges Timeout zuerst abläuft. Dies minimiert doppelte NACKs. Diese Arten von Mechanismen sind als RINA ( Receiver-Initiated with NACK Avoidance) bekannt. ]

Beim zuverlässigen Multicast liefert ein Sendeprozess höchstens einmal eine Nachricht, und das Konzept der Übereinstimmung ist erfüllt.

So funktioniert zuverlässiges Multicast

Wir schlagen ein Beispiel mit einer Gruppe vor, die aus 3 Prozessen { p, q, r } besteht.

Multicast-Versand.

Bisherige Überlegungen:

• Jeder Prozess p hält eine Folgenummer für jede Gruppe, zu der er gehört.$S_{g}^{p}$
• Jeder Prozess verwaltet einen Vektor aus n Elementen (wobei n die Anzahl der Prozesse in der Gruppe ist), wobei jedes Element der Anzahl der von einem bestimmten Prozess empfangenen Nachrichten entspricht (z. B. ist im Prozess q die Anzahl der von p empfangenen Nachrichten ).$R_{p}$

Hinsichtlich des Sendens der Multicast-Nachricht sendet der Sendeprozess diese Nachricht an die Gruppe, wobei die entsprechende Sequenznummer und die erforderlichen Empfangsbestätigungen angehängt werden. Außerdem wird die Sequenznummer erhöht ( = + 1), wenn die Nachricht von den empfangenden Prozessen zugestellt wird. $S_{g}^{p}$$S_{g}^{p}$

Andererseits wird hinsichtlich des Empfangs zur Erläuterung des Konzepts die folgende Situation betrachtet: Empfang in q einer Nachricht von p an die Gruppe g, mit einer Sequenznummer und angehängten Bestätigungen < q, >. Wir haben drei Szenarien: $Jawohl$$R$

Multicast-Empfang.

• Wenn = + 1: Der Prozess q F-liefert die Nachricht und erhöht sich (Anzahl der von p empfangenen Nachrichten ).$Jawohl$$R_{g}^{p}$$R_{g}^{p}$

• Ja : Die Nachricht ist ein Duplikat (sie wurde bereits zuvor empfangen) und wird daher verworfen.$Jawohl$ $≤$ $R_{g}^{p}$

• Si + 1 o : Prozess q sendet eine negative Bestätigung (NACK) an p , die anzeigt, dass er eine oder mehrere Nachrichten verloren hat.$Jawohl$ $>$ $R_{g}^{p}$$R$ $>$ $R_{g}^{p}$

Wie im Bild rechts zu sehen ist, wird die aktuelle Nachricht von q und r zugestellt, obwohl vorherige Nachrichten eintreffen müssen, d. h. die Nachrichten kommen in einer anderen Reihenfolge für die verschiedenen Prozesse an. Dieses Problem wird durch die Verwendung eines anderen Typs von Multicast behoben, der als geordnetes Multicast bezeichnet wird.

Für den Fall, dass es der sendende Prozess ist, der Nachrichten verloren hat, wird er von dem entsprechenden Prozess mit einem NACK benachrichtigt.

Geordnetes Multicast

Der zuverlässige Multicast-Algorithmus über IP-Multicast garantiert nicht, dass Nachrichten immer in der gleichen Reihenfolge ankommen, und dies kann ein Problem für Anwendungen sein, die eine Reihenfolge erfordern.

Die gebräuchlichsten Sortierarten sind die Gesamtsortierung, die kausale Sortierung und die FIFO- Sortierung .

Typen sortieren

• FIFO-Ordnung: Wenn ein Prozess eine Nachricht m ₁ und dann eine Nachricht m ₂ rundsendet, müssen diese in der Reihenfolge zugestellt werden, in der sie vom Sender gesendet wurden, dh m 1 wird immer _vor m ₂ zugestellt .

• Kausale Reihenfolge: Wenn das Rundsenden einer Nachricht m ₁ kausal vor dem Rundsenden einer Nachricht m ₂ erfolgt, dann liefert ein korrekter Prozess m ₁ vor m ₂ .

• Gesamtreihenfolge: Wenn zwei korrekte Prozesse P _i und P _j zwei Nachrichten m ₁ und m ₂ liefern , dann liefert P _{i m 1} vor m ₂ genau dann, wenn P _{j m 1} vor m ₂ liefert .

Implementierung der FIFO-Sortierung

Ein Multicast mit FIFO-Ordnung hat zwei Operationen: OF-Multicast und OF-Delivery.

Die folgenden Variablen werden im Prozess P verwendet:

• S _g ^p Zähler der Nachrichten, die der Prozess p an die Gruppe g gesendet hat
• R _g ^q Sequenznummer der letzten von Prozess q empfangenen Nachricht p, die an Gruppe g gesendet wurde

Wenn die OF-Multicast-Operation von p für die Gruppe g durchgeführt wird

• Hängen Sie S _g ^p in die Nachricht ein
• B-Multicast der Nachricht an Gruppe g
• Erhöhe S _g ^p um 1 -> S _g ^p = S _g ^p + 1

Wenn p eine Nachricht von q erhält:

• Wenn S = R _g ^q +1 → wird geprüft, ob es sich um die erwartete Nachricht handelt, und p verwendet die OF-Übermittlungseinstellung R _g ^q = S

• Wenn S > R _g ^q +1 → Aufbewahrung der Nachricht, bis die Zwischennachrichten zugestellt wurden und S = R _g ^q +1 erfüllt ist ]

Implementierung der kausalen Sortierung

Dieser Algorithmus berücksichtigt die Beziehung "vorher passiert" und die kausalen Ordnungsoperationen werden verwendet: OC-Multicast und OC-Lieferung, jeder Prozess p _i hat seinen eigenen Vektor von Zeitstempeln.

Kausal geordnetes Multicast

Variablen im Prozess p

V _p ^g Vektor mit der Anzahl der von jedem Prozess empfangenen Nachrichten

Um eine OC-Multicast-Nachricht an die Gruppe g zu senden, fügt der Prozess 1 zu seinem Eintrag im Zeitstempelvektor hinzu und sendet die B-Multicast-Nachricht zusammen mit ihrem Zeitstempel an g.

Wenn ein Prozess pi B-eine Nachricht p _j liefert , muss er sie vor der OC-Lieferung in die Haltewarteschlange stellen: Er muss zuerst sicherstellen, dass er alle Nachrichten geliefert hat, die zuvor passiert sind, dies wird auf folgende Weise überprüft:

• P _j wartet, bis es jede von p _{j gesendete Nachricht zugestellt hat}

• P _i wartet auf die Nachricht, die p _j geliefert hat, bis zu dem Zeitpunkt, zu dem es die Nachricht gesendet hat.

Vollständige Sortierimplementierung

Der grundlegende Weg zum Implementieren einer vollständigen Ordnung besteht darin, Nachrichten, die per Multicast gesendet werden, vollständig geordnete Identifikatoren so zuzuweisen, dass jeder Prozess die gleiche Ordnung basierend auf diesen Identifikatoren durchführt.

Es gibt zwei Methoden, um Nachrichten Identifikatoren zuzuweisen:

• Sequenzer

Der als Sequenzer gewählte Prozess ist für das Ordnen der Nachrichten zuständig.

Wenn ein Prozess eine OT-Multicast-Nachricht m senden möchte, wird sie an den Sequenzer gesendet.

Der Sequencer weist den von B zugestellten Nachrichten inkrementell und fortlaufend eine Sequenznummer zu und sendet sie an alle Prozesse in der Gruppe.

Der Sequenzer gibt die Zahlenfolge per B-Multicast an die Nachrichtengruppe g mit der Bestellung bekannt.

Eine Nachricht wird auf unbestimmte Zeit in der Warteschlange gehalten, bis die OT-Zustellung gemäß der entsprechenden Sequenznummer durchgeführt werden kann.

ISIS Total Ordered Multicast

• Vollständige Umsetzung nach Vereinbarung (ISIS)

Es wurde ursprünglich für die ISIS-Tools entwickelt (die Firma, die dieses Tool vermarktet hat, existiert nicht mehr, aber ISIS wurde an der New Yorker Börse gehandelt und wird immer noch im französischen Flugsicherungssystem oder dem amerikanischen Kriegsschiff AEGIS [1] verwendet . Derzeit ist ISIS hat sich zu einer neuen Version entwickelt, die sich mehr auf die Replikation konzentriert und VSync [2] genannt wird ). Bei n Prozessen sind die Variablen für Prozess q :

A _g ^{q : höchste} vereinbarte Folgenummer für Gruppe g des Prozesses q

P _g ^{q : Größte} vorgeschlagene Sequenznummer für die Gruppe g des Prozesses q

Implementierung

Mehrere Nachrichten gleichzeitig an mehrere Prozesse senden

Vereinbarung zwischen Nachrichten in einem Multicast

Endgültiges Senden im geordneten Multicast

Bei der Umsetzung dieser Vereinbarung haben wir drei Teile (mit n Prozessen):

1. Der Prozess p erstellt eine Nachricht ( m ) und sendet sie per Multicast, das heißt: p führt B-Multicast<m,i> an g durch (i eindeutige Kennung von m)
2. Jeder Prozess q antwortet auf p mit einem Vorschlag P _g ^q = max( A _g ^q , P _g ^q )+1
   1. Der Nachricht m wird vorläufig die Sequenznummer Pgq zugewiesen
   2. Es wird gemäß dieser vorläufigen Nr. in die Aufbewahrungswarteschlange gestellt und geordnet
3. Der Prozess p entscheidet unter allen empfangenen Vorschlägen über die endgültige Sequenznummer und sendet sie erneut an alle Prozesse, das heißt: p sammelt alle vorgeschlagenen Sequenznummern und wählt die größte ( a ) als Übereinstimmung aus, wodurch B-Multicast < a durchgeführt wird. i> a g (wobei "a" die vereinbarte Reihenfolge ist)
   1. Jeder Prozess setzt A _g ^q = max( A _g ^q , a) und weist es der Nachricht i zu
   2. Ordnen Sie die Warteschlange neu an, wenn sie sich von der vorgeschlagenen unterscheidet
   3. Wenn die Nachricht an der Spitze der Warteschlange nicht zugestimmt hat, wird sie zugestellt

Praxisbeispiel

1. Wir haben 4 Prozesse, von denen P1 und P4 eine Nachricht erstellen und den Multicast durchführen.
2. Sobald die Nachricht gesendet wurde, erhalten sie die Ankunftsvorschläge für jeden Prozess (der Wert des ersten, der ankommt, ist geringer als der des letzten, der ankommt). Wir sammeln sie in zwei Gruppen und unterscheiden sie nach dem Prozess, der die Nachricht gesendet hat.
3. Sobald die Sequenznummer ausgewählt ist, wird sie an alle Prozesse gesendet, die Mailbox neu geordnet und die Nachricht gesendet.
   1. Wenn die Vereinbarung, die bei einem Prozess ankommt, einen Wert hat, der größer ist als die in der Mailbox gespeicherten, warten wir, bis die anderen Vereinbarungen die Mailbox erreichen, und senden die Nachricht von der niedrigsten zur höchsten Sequenznummer.
   2. Wenn die Vereinbarung, die einen Prozess erreicht, einen niedrigeren Wert hat als die in der Mailbox gespeicherten, können wir diese Nachricht direkt senden, ohne warten zu müssen.

In welchem ​​Szenario ist es sinnvoll

● Wenn Sie nach optimierter Netzwerkleistung suchen.

● Wenn Unterstützung für verteilte Anwendungen erwünscht ist.

● Falls Sie Ressourcen sparen möchten.

● Wenn Sie ein einfaches Wachstum in der Größenordnung finden möchten.

Bibliographie

• Rodrigo Santamaria. Hinweise Verteilte Systeme Universität von Salamanca. | Thema 5 – Koordinierung und Vereinbarung ]

Externe Links

• Verteilte Systeme - Koordination und Vereinbarung
• Alberto Lafuente, Mikel Larrea. UPV- EHU Mitteilung an Gruppen