Multicast Routing-Algorithms

In diesem Abschnitt werden Multicast-Routing-Algorithmen für Delay Tolerant Networks (DTNs) beschrieben.

General Operations

1.Message Buffering

Nachrichten bleiben im Knotenbuffer gespeichert, bis sie

• aufgrund von Bufferoverflow gelöscht werden müssen oder
• gemäß dem Semantic-Model verfallen und auch gelöscht werden müssen.

Also gibt man neuen Nachrichten die Gelegenheit zugestellt zu werden.

2.Forwarding State

Jede Nachricht m ist mit zwei Listen verknüpft.

• Die NEXT-HOP-Liste Ln(m) erfasst die Knoten, zu denen die Nachricht gesendet werden soll.
• Die SENT-Liste Ls(m) enthält die Knoten, die diese Nachricht schon erhalten haben.

Ln(m) wird nach dem Eintreffen der Nachricht initialisiert und wird aktualisiert , wenn sich die Gruppenzugehörigkeit ändert.

3.Message Forwarding

Angenommen, dass ein Kontakt zwischen den Knoten A und B ansteht. Knoten befördern Nachrichten wie folgt:

Für jede Nachricht m, die im Knoten A gespeichert ist, wird A versuchen sie dem Knoten B genau dann zu übertragen, wenn der

Knoten B

1.in der NEXT-HOP-Liste Ln(m) der Nachricht m

und gleichzeitig

2.nicht in ihrer SENT-Liste Ls(m)

liegt. Nach der Übertragung wird der Knoten B in die SENT-Liste Ls(m) der Nachricht m hinzugefügt, um somit abzusichern, dass er in einem späteren Zeitpunkt keine Kopien derselben Nachricht erhält.

Specific Operations

1.Static Tree-Based Routing (STBR)

• Beim STBR wird im DTN-Graph ein kürzester-Pfad-Baum, von der Quelle zu den beabsichtigten Nachrichtempfängern, erstellt. Die Nachricht wird dem Baum entlang befördert. Diese Route ist statisch und infolgedessen, wenn eine Nachricht den Kontakt mit einem Knoten aus Ln(m) verpasst, muss sie auf die nächste Gelegenheit warten, was wiederum die Nachrichtzustellung erheblich verzögert.
• Die Benutzung von statischen Routen erlaubt den Knoten nicht, lokale Information auszunutzen, um Nachrichten besseren Pfaden entlang zu befördern.

2.Dynamic Tree-Based Routing (DTBR)

• DTBR behandelt die erwähnten Problemen von STBR, indem es expizite Adressierungsmethoden anwendet. D.h. Nachrichten enthalten im message-header die Endpoint-IDs der Empfänger, und die Gruppen-IDs.

-->Auf diese Weise können Knoten die Next-Hops einer Nachricht, aufgrund von verfügbarer Queuing-, und Kontakt-Information, dynamisch berechnen.

3.Group-Based Routing (GBR)

• In GBR erstellen Knoten eine Forwarding Group für jede Nachricht, indem sie einen Baum, wie in STBR, berechnen und als Forwarding Group die Knoten des Baumes, einschießlich den Empfängern der Nachricht, setzen.
• Nachrichten werden in die Forwarding Group mittels Flooding befördert.

4.Broadcast-Based Routing (BBR)

• In BBR enthält die NEXT-HOP-Liste Ln(m) der Nachricht m immer alle Knoten des Netzwerkes. So werden Nachrichten durch das ganze Netzwerk verstreut.

5.Unicast-Based Routing (UBR)

• In UBR , wenn eine Multicast Nachricht bei einem Knoten A (Quelle) generiert wird, sendet dieser Knote eine Unicast-Nachricht, in der die originale Multicast Nachricht eingekapselt ist, zu jedem berechneten Empfänger.
• Die Quelle speichert die Multicast-Nachricht und sendet neue Unicast-Nachrichten, wenn sie über neue beabsichtigte Empfänger informiert wird.
• Unicast-Nachrichten werden vom Knotenspeicher gelöscht, nachdem sie zu einem NEXT-HOP übertragen wurden.

---

Main Page --> S2006-IPI