Flooding-Algorithmus

Flooding-Algorithmus
Flooding Algorithmus

Flooding (deutsch: fluten) bzw. Flutalgorithmus ist der einfachste Algorithmus zur Informationsverteilung in einem Verteilten System. Voraussetzung ist einzig eine zusammenhängende Topologie. In einem Netz von anfangs nicht informierten Knoten senden ein oder mehrere Initiatorknoten eine Nachricht an alle ihre Nachbarn. Ein Knoten, der die Nachricht erhält und bisher noch nicht informiert wurde, sendet die Nachricht ebenfalls an alle seine Nachbarn, nicht aber zurück an den Absender. Nach einer Weile sind alle Knoten informiert. Da informierte Knoten keine weiteren Nachrichten aussenden, terminiert der Algorithmus.

Inhaltsverzeichnis

Pseudocode

Anmerkung: Alle Knoten sind zu Beginn nicht informiert.

Initiator

 informiert := true;
 sende <nachricht> an alle Nachbarn



Ein Knoten K empfängt <nachricht> von einem Nachbarn N

  wenn K nicht informiert ist, dann
      informiert := true;
      sende <nachricht> an alle Nachbarn außer N

Nachrichtenkomplexität

Seien e die Anzahl der Kanten und k die Anzahl der Knoten. Jeder Knoten muss seine Nachricht an jeden Nachbarn schicken. Also gehen über jede Kante 2 Nachrichten (2e). Allerdings schicken alle, außer dem Initiator, an den Nachbarn, von dem sie die Nachricht erhalten haben (Source), keine Nachricht zurück (-k). Eine Ausnahme ist der Initiator, der die Nachricht an alle Knoten im Netzwerk schickt (+1). Es werden also bei einem Initiator 2e-k+1 Nachrichten versendet.

Beispiel:

In einem Netzwerk mit 5 Knoten (A,B,C,D,E) gibt es 10 Kanten.

  • A hat 4 Kanten mit B,C,D und E.
  • B hat 3 (ungezählte) Kanten mit C,D,E und zu der bereits gezählten Kante A.
  • C hat 2 (ungezählte) Kanten zu D,E und zu bereits gezählten Kanten A,B.
  • D hat 1 (ungezählte) Kante zu E und 3 zu bereits gezählten Kanten A,B,C.

Das ergibt 10 Kanten.

Gleichung: 2e-k+1 = 2*10-5+1= 16 Nachrichten würden verschickt werden.

Verbesserungen

Flooding mit Bestätigung

Flooding Algorithmus mit Bestätigungen

Ein Problem des normalen Floodings ist, dass der Initiator nicht erkennt, dass alle Knoten seine Nachricht erhalten haben. Eine Lösung für dieses Problem ist das Flooding mit Bestätigung.

Dabei sendet ein Prozess eine Bestätigung ab, wenn er von allen Nachbarn bzw. Kindknoten, an die er eine Nachricht versendet hat, eine Bestätigung bekommen hat. Ebenfalls sendet ein Knoten eine Bestätigung ab, wenn er eine Nachricht bekommen hat, diese aber nicht weitersenden kann, weil er keine Nachbarn mehr hat. Der Initiator weiß, dass alle eine Nachricht erhalten haben, wenn er von allen seinen Nachbarn Bestätigungen erhalten hat.


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Flooding (Informatik) — Flooding (engl. überfluten) bezeichnet das Überschwemmen eines Netzwerkes mit Paketen. Dies kann gewollt sein, wie im Fall von OSPF, das mit Hilfe dieser Technik Informationen an alle angeschlossenen Rechner übermittelt, oder Usenet, in dem die… …   Deutsch Wikipedia

  • Flooder — Flooding (engl. überfluten) bezeichnet das Überschwemmen eines Netzwerkes mit Paketen. Dies kann gewollt sein, wie im Fall von OSPF, das mit Hilfe dieser Technik Informationen an alle angeschlossenen Rechner übermittelt, oder Usenet, in dem die… …   Deutsch Wikipedia

  • Vernetztes System — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • Verteilte Systeme — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • Verteiltes System — Ein Verteiltes System ist nach der Definition von Andrew Tanenbaum ein Zusammenschluss unabhängiger Computer, der sich für den Benutzer als ein einzelnes System präsentiert. Peter Löhr definiert es etwas grundlegender als „eine Menge… …   Deutsch Wikipedia

  • Broadcasting — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Dieser Artikel befasst sich mit Broadcast in einem Computernetzwerk …   Deutsch Wikipedia

  • Broadcat — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Dieser Artikel befasst sich mit Broadcast in einem Computernetzwerk …   Deutsch Wikipedia

  • Rundruf — Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf mit, ihn zu verbessern, und entferne anschließend diese Markierung. Dieser Artikel befasst sich mit Broadcast in einem Computernetzwerk …   Deutsch Wikipedia

  • Broadcast — Kommunikationsformen / Routing Schemata Unicast Broadcast Anycast …   Deutsch Wikipedia

  • Bitcoin — Das Hauptfenster unter Ubuntu Linux …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”