BHWS_skripta

2.1.9 Algoritmus Shortest Path First 

Optimální  cesta  bude  určena  zpracováním  údajů  z  přijatých  LSA  zpráv  pomocí 

algoritmu  Shortest  Path  First  (SPF).  Cesta  může  být  optimalizována  na  základě  různých 
parametrů jako např. podle šířky pásma, podle zpoždění  či  podle úrovně zabezpečení,  které 
jsou zohledňovány přidělenou metrikou. Častou formou realizace algoritmu SPF je Dijsktrův 
algoritmus, který hledá nejkratší cesty od referenčního uzlu ke všem dalším uzlům sítě. Podle 
sledovaných kritérií jsou jednotlivým cestám přiřazeny váhové koeficienty. Od referenčního 
uzlu je každý uzel označen návěštím odpovídajícím součtu vah vybrané cesty od referenčního 

Hardware počítačových sítí 

15 

uzlu.  Ve  výchozím  stavu  má  každé  návěští  hodnotu  ∞.  V prvním  kroku  jsou  vyhodnoceny 
linky referenčního uzlu. V dalším kroku jsou pak ověřeny linky sousedního uzlu, ke kterému 
vede  linka  od  referenčního  uzlu  s nejmenší  metrikou.  Pomocí  iterace  jsou  pak  postupně 
vybrány cesty s nejmenší celkovou metrikou k cílovým uzlům. 

Před zahájením iterace se předpokládá, že směrovač provádějící hledání nejkratších cest 

už  přijal  LSA  zprávy  od  svých  sousedů,  a  tak  má  ucelený  pohled  o  topologii  sítě,  tj.  zná 
všechny směrovače a všechny metriky. Každý iterační krok se skládá ze dvou operací:  

  aktualizace metriky uzlů sousedících s naposledy vybraným uzlem, 
  výběr uzlu, který má nejkratší metriku (označen hvězdičkou v Tab. 2.1).  

V uvedeném  příkladu  na  Obr.  2.9  byl  vybrán  uzel  C  jako  referenční  a  proto  jeho