Constrained Shortest Path First

Constrained Shortest Path First

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 constraints. A constraint could be minimum bandwidth required per link (also known as bandwidth guaranteed constraint), end-to-end delay, maximum number of links traversed, include/exclude nodes. CSPF is widely used in MPLS Traffic Engineering[citation needed]. The routing using CSPF is known as Constraint Based Routing (CBR).

The path computed using CSPF could be exactly same as that of computed from OSPF and IS-IS, or it could be completely different depending on the set of constraints to be met.

Example with bandwidth constraint

An Example network

Consider the network to the right, where a route has to be computed from router-A to the router-C satisfying bandwidth constrained of x- units, and link cost for each link is based on hop-count (i.e., 1).

If x = 50 units then CSPF will give path A → B → C.

If x = 55 units then CSPF will give path A → D → E → C.

If x = 90 units then CSPF will give path A → D → E → F → C.

In all of these cases OSPF and IS-IS will result in path A → B → C.

However, if the link costs in this topology are different, CSPF may accordingly determine a different path. For example, suppose that as before, hop count is used as link cost for all links but A → B and B → C, for which the cost is 4. In this case:

If x = 50 units then CSPF will give path A → B → C.

If x = 55 units then CSPF will give path A → D → E → C.

If x = 90 units then CSPF will give path A → D → E → F → C.

References


Wikimedia Foundation. 2010.

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

Look at other dictionaries:

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