Cesko.wiki Constrained Shortest Path First
Author
Albert FloresConstrained 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
Příklad sítě; čísla na hranách jsou omezení šíř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. +more 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.
