Constrained Shortest Path First

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


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Constrained Shortest Path First — (CSPF) is an extension of shortest path algorithms. The path computed using CSPF is a shortest path fulfilling a set of constraints. It simply means that it runs shortest path algorithm after pruning those links that violate a given set of… …   Wikipedia

  • 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… …   Deutsch Wikipedia

  • Multiprotocol Label Switching — MPLS redirects here. For other uses, see Mpls. MPLS Layer Multiprotocol Label Switching (MPLS) is a mechanism in high performance telecommunications networks that directs data from one network node to the next based on short path labels rather… …   Wikipedia

  • Routing protocol — A routing protocol is a protocol that specifies how routers communicate with each other to disseminate information that allows them to select routes between any two nodes on a network. Typically, each router has a prior knowledge only of its… …   Wikipedia

  • CBR — Die Abkürzung CBR steht für: C B R – ehemaliges Kürzel der Messe für Caravan, Wassersport, Tourismus und Freizeit in München, heute f.re.e California Bearing Ratio – im Straßenbau ein Prüfverfahren zur Ermittlung der Festigkeit von Boden, siehe… …   Deutsch Wikipedia

  • CSPF — steht für: Central States Pension Fund, einen US amerikanischen Pensionsfonds Constrained Shortest Path First, einen Kürzesten Pfad Algorithmus Diese Seite ist eine Begriffsklärung zur Unterscheidung mehrerer mit demselben Wort …   Deutsch Wikipedia

  • Wireless mesh network — Animation showing self healing wireless mesh (Click to enlarge) …   Wikipedia

  • Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… …   Wikipedia

  • List of NP-complete problems — Here are some of the more commonly known problems that are NP complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP complete problems). Most of the problems in this list are taken… …   Wikipedia

  • Liste de problèmes NP-complets — Ceci est une liste des problèmes NP complets les plus connus en théorie de la complexité des algorithmes, exprimés sous la forme d un problème de décision. Puisqu on connaît plus de 3000 problèmes NP complets, cette liste n est pas exhaustive. La …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”