Multi-Path Routing

Multi-Path Routing oder Multipath Routing (engl. Mehrwegevermittlung) ist eine Vermittlungstechnologie unter Verwendung mehrerer alternativer Pfade durch ein Netzwerk, was eine Reihe von Vorteilen, wie Fehlertoleranz, erhöhte Bandbreite oder verbesserte Sicherheit bietet. Die berechneten Mehrfachpfade können sich überlappen, oder ohne Verbindung sein.

Mehrwegevermittlung in kabellosen Netzwerken

Um die Leistung oder Fehlertoleranz zu verbessern:

CMR (Concurrent Multi-Path Routing) wird oft als die gleichzeitige Verwaltung und Nutzung mehrerer verfügbarer Pfade für die Übermittlung von Datenströmen ausgehend von einer oder mehreren Anwendungen verstanden. In dieser Form wird jedem Datenstrom ein getrennter Pfad zugewiesen, sofern dies die Anzahl der verfügbaren Pfade zulässt. Wenn es mehr Datenströme als verfügbare Pfade gibt, teilen sich einige Datenströme Pfade. Dies resultiert in einer besseren Ausnutzung der verfügbaren Bandbreite durch die Schaffung mehrerer aktiver Übertragungswarteschlangen. Des Weiteren bietet dies ein höheres Maß an Fehlertoleranz. Sollte ein Pfad ausfallen, wird nur der Datenverkehr über diesen Pfad beeinträchtigt, die anderen Pfade bedienen ihre Datenströme weiterhin. Außerdem ist im Idealfall ein alternativer Pfad sofort verfügbar über den der unterbrochene Datenstrom fortgesetzt oder wiederaufgenommen werden kann.

Diese Methode bietet eine bessere Übertragungsleistung und Fehlertoleranz durch das Bereitstellen von:

• Gleichzeitiger, paralleler Übertragung über mehrere Träger.
• Lastverteilung über verfügbarere Geräte.
• Vermeidung von Pfaderkundung, wenn ein unterbrochener Datenstrom neu zugewiesen wird.

Nachteile dieser Methode sind:

• Einige Anwendungen können langsamer beim Aussenden von Daten an die Transportschicht sein, die zugewiesenen Pfade werden daher nicht genügend ausgelastet.
• Der Wechsel zu einem alternativen Pfad kann zu einer Unterbrechung führen, während die Verbindung wiederhergestellt wird.

Echtes CMR

Eine leistungsfähigere Form von CMR (echtes CMR) geht über das bloße Darstellen von Pfaden, an die sich Anwendungen binden können, hinaus. Echtes CMR fasst alle verfügbaren Pfade zu einem einzigen, virtuellen Pfad zusammen. Alle Anwendungen übergeben ihre Pakete an diesen virtuellen Pfad, der auf der Netzwerkschicht aufgeteilt ist. Die Pakete werden dann über die tatsächlichen Pfade nach einer speziellen Methode, z. B. Ringverteilung oder gewichtetem Einreihen, übermittelt. Sollte eine Verbindung oder ein Vermittlungsknoten ausfallen und daher einen oder mehrere Pfade unbenutzbar machen, werden nachfolgende Pakete nicht über diese Pfade geleitet. Der Datenstrom wird ununterbrochen und für die Anwendung transparent fortgesetzt. Diese Methode bietet gegenüber der vorigen erhebliche Leistungsvorteile:

• Durch das ständige Übergeben von Paketen an alle Pfade werden diese weit besser ausgenutzt.
• Egal wie viele Knoten (und daher Pfade) ausfallen, so lange wie mindestens ein Pfad besteht, ist der virtuelle Pfad noch verfügbar und alle Sitzungen bleiben verbunden. Das bedeutet, dass kein Datenstrom wieder neugestartet werden muss und es keine Verbindungswiederherstellungsverzögerung gibt.

Es wird darauf hingewiesen, dass echtes CMR auf Grund seiner Beschaffenheit zur Zustellung der Pakete außerhalb der Reihenfolge (englisch Out of order delivery OOOD) führen kann, was auf Standard-TCP erheblich beeinträchtigend wirkt. Standard-TCP hat sich jedoch als völlig ungeeignet für den Einsatz in anspruchsvollen drahtlosen Umgebungen erwiesen und muss in jedem Fall durch ein Element, wie ein TCP-Gateway, das diesen Anforderungen gewachsen ist, ergänzt werden. Ein solches Gateway-Werkzeug ist SCPS-TP, das mit seiner Fähigkeit zur selektiven Negativbestätigung (SNACK) das OOOD-Problem erfolgreich behandelt.

Ein weiterer wichtiger Vorteil von echtem CMR, der dringend bei kabellosen Netzwerkverbindungen benötigt wird, ist die Unterstützung für erweiterte Sicherheit. Kurz gesagt, um einen Datenaustausch kompromittieren zu können, müssen viele der Routen kompromittiert werden, über die dieser geleitet wird. Weitere Informatione dazu finden sich im Abschnitt Einzelnachweise unter "Die Netzwerksicherheit verbessern".

Kapillare Vermittlung

In der Netzwerkplanung und Graphentheorie ist die kapillare Vermittlung für ein bestimmtes Netzwerk eine Multipfadlösung zwischen einem Paar von Quell- und Zielknoten. Anders als die Vermittlung anhand des kürzesten Pfades oder des maximalen Flusses existiert für die kapillare Vermittlung nur eine Lösung.

Kapillare Vermittlung kann durch einen iterativen linearen Programmierprozess (LP) erreicht werden, der den Fluss eines Einzelpfades in den eines kapillaren Pfads umwandelt.

1. Zuerst wird der Maximalwert der Last aller Vermittlungsknotenverbindungen minimiert
   • Dies geschieht durch Absenkung der oberen Grenze des Lastwertes und Anwendung auf alle Verbindungen.
   • Die Gesamtmasse des Flusses wird gleichmäßig auf die möglichen parallelen Routen aufgeteilt.
2. Es werden die Verbindungsengpässe der ersten Schicht (siehe unten) gesucht und deren Last auf das gefundene Minimum gesetzt.
3. Daraufhin wird in ähnlicher Weise die Maximallast der verbliebenen Verbindungen abgesenkt, aber nun ohne die Verbindungsengpässe der ersten Ebene.
   • Diese zweite Iteration verfeinert die Pfaddiversität.
4. Nun werden die Verbindungsengpässe der zweiten Ebene gesucht
   • Wieder wird die maximale Last aller verbliebenen Verbindungen minimiert, aber nun auch ohne die Engpässe der zweiten Ebene.
5. Dieser Prozess wird wiederholt, bis der gesamte Verbindungsfußabdruck innerhalb der Engpässe der Schichten liegt.

Auf jeder Funktionsebene werden, nach dem Minimieren der maximalen Last der Verbindung, Engpässe über eine Ermittlungsschleife identifiziert.

1. Bei jeder Iteration der Schleife wird die Last des Datendurchsatzes über alle Verbindungen, die unter Maximallast stehen und potentielle Engpässe darstellen, minimiert.
2. Verbindungen, die nicht fähig sind, ihren Durchsatz im Maximum zu halten, werden von der Kandidatenpfadliste entfernt.
3. Die Engpassermittlungsprozess stoppt, wenn keine Verbindungen mehr entfernt werden können, denn der beste Pfad ist nun bekannt.

Siehe auch

• IEEE 802.1aq
• Equal-cost multi-path routing
• Multipath TCP

Einzelnachweise

• S.-J. Lee, M. Gerla: Split Multipath Routing with Maximally Disjoint Paths in Ad Hoc Networks. In: Proc. ICC 2001. Band 10, Juni 2001, S. 3201–3205, doi:10.1109/ICC.2001.937262. 
• A. Nasipuri, R. Castaneda, S. R. Das: Performance of Multipath Routing for On-Demand Protocols in Mobile Ad Hoc Networks. In: Mobile Networks and Applications. Band 6, August 2001, S. 339–349, doi:10.1023/A:1011426611520. 
• M. K. Marina, S. R. Das: On-Demand Multi Path Distance Vector Routing in Ad Hoc Networks. In: Proc. ICNP 2001. September 2001, S. 14–23, doi:10.1109/ICNP.2001.992756. 
• A. Tsirigos, Z. J. Haas: Multipath Routing in the Presence of Frequent Topological Changes. In: IEEE Communications Magazine. Band 39, Nr. 11, November 2001, S. 132–138, doi:10.1109/35.965371. 
• H. Lim, K. Xu, M. Gerla: TCP Performance over Multipath Routing in Mobile Ad Hoc Networks. In: Proc. ICC 2003. Band 2, Mai 2003, S. 1064–1068, doi:10.1109/ICC.2003.1204520. 
• A. Tsirigos, Z. J. Haas: Analysis of Multipath Routing—Part I: The Effect on the Packet Delivery Ratio. In: IEEE Trans. Wireless Communications. Band 3, Nr. 1, Januar 2004, S. 138–146, doi:10.1109/TWC.2003.821207. 
• S. Card, F. Tims: Concurrent Multipath Routing & Transport in a Mobile Wireless Gateway. In: MILCOM 2004, www.critical.com. Monterey, Kalifornien, USA 2004. 
• N. Kammenhuber: Traffic-Adaptive Routing. S. Chapter 6.2 "Related Work" (tum.de [PDF]). 

Die Netzwerksicherheit verbessern:

• W. Lou, Y. Fang: A Multipath Routing Approach for Secure Data Delivery. In: Proc. MILCOM 2001. Band 2, Oktober 2001, S. 1467–1473, doi:10.1109/MILCOM.2001.986098. 
• C. K.-L. Lee, X.-H. Lin, Y.-K. Kwok: A Multipath Ad Hoc Routing Approach to Combat Wireless Link Insecurity. In: Proc. ICC 2003. Band 1, Mai 2003, S. 448–452, doi:10.1109/ICC.2003.1204217. 
• S. Bouam and J. Ben-Othman: Data Security in Ad Hoc Networks Using Multipath Routing. In: Proc. PIMRC 2003. Band 2, September 2003, S. 1331–1335, doi:10.1109/PIMRC.2003.1260329. 
• P. Papadimitratos, Z. J. Haas: Secure Data Transmission in Mobile Ad Hoc Networks. In: Proc. ACM WiSe 2003. September 2003, S. 41–50, doi:10.1145/941311.941318. 
• Zhi Li, Yu-Kwong Kwok: A New Multipath Routing Approach to Enhancing TCP Security in Ad Hoc Wireless Networks. In: Proc. ICPP Workshops. Juni 2005, S. 372–379, doi:10.1109/ICPPW.2005.11. 

Weblinks

• Prof. Dijiang Huang's multipath routing bibliography: [1]