Constrained Shortest Path First

Constrained Shortest Path First (CSPF) je rozšíření algoritmů pro hledání nejkratší cesty. Cesta vypočítaná pomocí CSPF je nejkratší cesta splňující určitá omezení. Jednoduše to znamená, že algoritmus hledání nejkratší cesty po vypuštění spojů, které nesplňují určitou sadu omezení. Omezením může být např. minimální požadovaná šířka pásma spoje (zaručená šířka pásma), koncové zpoždění, maximální počet použitých hopů, zahrnutí nebo vypuštění určitých uzlů. CSPF se používá v MPLS Traffic Engineering. Směrování pomocí CSPF se nazývá Constraint Based Routing (CBR).

Cesta vypočítaná pomocí CSPF může být stejná jako cesta vypočítaná pomocí OSPF a IS-IS, ale může být i jiná podle množiny omezení, která mají být splněna.

Příklad s omezením šířky pásma

Uvažujme síť vpravo, v které má být spočítána cesta z routeru A na router C splňující omezení na šířka pásma, a kde cena každého spoje je rovna počtu hopů (tj. 1).

Je-li x 50 jednotek, pak CSPF najde cestu A → B → C.

Je-li x 55 jednotek, pak CSPF najde cestu A → D → E → C.

Je-li x 90 jednotek, pak CSPF najde cestu A → D → E → F → C.

Ve všech těchto případech OSPF a IS-IS najde cestu A → B → C.

Jestliže však ceny spojů v této síti jsou různé, CSPF může najít různé cesty. Předpokládejme například, že oproti předchozímu příkladu je cena cest A → B a B → C 4. Portom:

Je-li x 50 jednotek, pak CSPF najde cestu A → D → E → C.

Je-li x 55 jednotek, pak CSPF najde cestu A → D → E → C.

Je-li x 90 jednotek, pak CSPF najde cestu A → D → E → F → C.

Reference

• ZIEGELMANN, Mark. Constrained Shortest Path and Related Problems. Constrained Network Optimization. [s.l.]: VDM Verlag Dr. Müller, 2007. Dostupné online. ISBN 978-3-8364-4633-4.