imported>Phzh: Form, typo

2025-09-18T07:41:51Z

Form, typo

Neue Seite

'''Constrained Shortest Path First''' (CSPF) ist eine Erweiterung für [[Algorithmus|Algorithmen]] zur Bestimmung [[kürzester Pfad]]e. Der von CSPF berechnete kürzeste Pfad erfüllt zusätzliche [[Nebenbedingung]]en. Dies bedeutet, dass der Kürzeste-Pfad-Algorithmus berechnet wird, nachdem die [[Kante (Graphentheorie)|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 verschiedenen Graphentheorie- und Netzwerkanwendungen, wie [[Multiprotocol Label Switching|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 [[Open Shortest Path First|OSPF]] und [[IS-IS]] identisch sein oder von diesem völlig abweichen, abhängig von den Nebenbedingungen.

== Beispiel mit Bandbreitenbedingung ==

[[Datei:Constrained Shortest Path First.svg|300px|mini|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 → B und B → C mit Verbindungskosten 4:

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

== Quellen ==
* {{Literatur
|Autor=Mark Ziegelmann
|Titel=Constrained Shortest Paths and Related Problems. Constrained Network Optimization
|Verlag=VDM Verlag Dr. Müller
|Datum=2007
|ISBN=978-3-8364-4633-4
|Sprache=en}}

[[Kategorie:Graphsuchalgorithmus]]
[[Kategorie:Optimierungsalgorithmus]]
[[Kategorie:Routing]]

Constrained Shortest Path First - Versionsgeschichte

imported>Phzh: Form, typo