Constraint Based Routing

Constrained Shortest Path First (CSPF) ist eine Erweiterung für Kürzester Pfad Algorithmen. Der von CSPF berechnete kürzeste Pfad erfüllt zusätzliche Nebenbedingungen. Dies bedeutet, dass der Kürzeste Pfad Algorithmus berechnet wird, nachdem die Kanten entfernt wurden, welche die Nebenbedingung nicht erfüllen. Nebenbedingungen können beispielsweise die Bandbreite einer Verbindung („Bandbreitenbedingung“), die Gesamtverzögerungszeit, die maximale Anzahl besuchter Knoten oder die Ein- und Ausschlussbedingung für Knoten sein.

CSPF wird in verschieden Graphentheorie- und Netzwerkanwendungen, wie MPLS und Traffic Engineering, benutzt. Routing Algorithmen, die CSPF nutzen, werden auch Constraint-Based Routing (CBR) genannt.

Der durch CSPF berechnete Pfad kann mit dem Ergebnis von OSPF und IS-IS identische sein oder von diesem völlig abweichen, abhängig von den Nebenbedingungen.

Beispiel mit Bandbreitenbedingung

Netzwerk für das Beispiel

Zu berechnen ist der Pfad von Knoten A zu Knoten C der die Bandbreitenbedingung x erfüllt. Die Kosten seien für jede benutzte Verbindung immer gleich 1.

Falls x = 50 liefert CSPF A → B → C.

Falls x = 55 liefert CSPF A → D → E → C.

Falls x = 90 liefert CSPF A → D → E → F → C.

Im obigen Fall liefern OSPF und IS-IS jedoch immer A → B → C.

Obwohl bei dieser Topologie die Kosten der unterschiedlichen Pfade verschieden sind, liefert CSPF den entsprechenden Pfad.

Seien nun weiter die Verbindungskosten je 1, bis auf A → Bund B → C mit Verbindungskosten 4:

Falls x = 50 liefert CSPF A → D → E → C.

Quellen

• Mark Ziegelmann: Constrained Shortest Paths and Related Problems. Constrained Network Optimization. VDM Verlag Dr. Müller 2007, ISBN 978-3-8364-4633-4