Multi-Path Routing
# 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 (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.

* 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.
* Es werden die Verbindungsengpässe der ersten Schicht (siehe unten) gesucht und deren Last auf das gefundene Minimum gesetzt.
* 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.
* 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.
* 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.

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