Constrained Shortest Path First

Technology
12 hours ago
8
4
2
Avatar
Author
Albert Flores

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

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.

5 min read
Share this post:
Like it 8

Leave a Comment

Please, enter your name.
Please, provide a valid email address.
Please, enter your comment.
Enjoy this post? Join Cesko.wiki
Don’t forget to share it
Top