Constrained Shortest Path First

Constrained Shortest Path First (CSPF) ist eine Erweiterung für Algorithmen zur Bestimmung kürzester Pfade. 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 identisch 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