Constrained Shortest Path First
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. Nebenbedingen können beispielsweise sein: die Bandbreite einer Verbindung („Bandbreitenbedingung“), Gesamtverzögerungszeit, maximal Anzahl besuchter Knoten oder Ein- und Ausschlussbedingung für Knoten.
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 and IS-IS identische sein oder von diesem völlig abweichen, abhängig von den Nebenbedingungen.
Beispiel mit Bandbreitenbedingung
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 and 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 (d-nb.info).