Multicast Routing-Algorithms

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 werden die Nachrichten einem Baum in dem DTN-Graph entlang befördert, wobei die Wurzel die Quelle der Nachricht ist und alle Empfänger erreicht.
• 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.
• Nachrichten werden nur bei Knoten dupliziert, die mehr als einen ausgehenden Pfad haben.

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, um die Wahrscheinlichkeit der Zustellung zu steigern.

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.

Fazit

• GBR und BBR erreichen die besten Delivery-ratios. Beide Algorithmen benutzen eine Art von Flooding für die Beförderung der Nachrichten.

-->Beförderung der Nachrichten über mehreren Pfaden ist ein vielversprechender Ansatz für Multicasting in DTNs.

• UBR ist sehr langsam in DTNs.

--> Multicast routing, realisiert durch mehrfache Unicast Nachrichten, ist sehr ineffizient in DTNs.

---

Main Page --> S2006-IPI