Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo PB165 - Grafy a sítě Směrování - hledání nejkratších cest Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Obsah přednášky Úvod Směrování v síti Distribuované směrování • Link-state algoritmy • Distance vector algoritmy Kvalita služby • A* algoritmus Cesty mezi všemi vrcholy • Floyd-Warshallův algoritmus • Distribuovaný Floyd-Warshallův algoritmus U vod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy ooooooooo álenost v grafu Pro připomenutí: • Délka cesty v neohodnoceném grafu je rovna počtu hran na této cestě. • Vzdálenost 5(u, v) vrcholů u, v v grafu je délka nejkratší cesty z u do v. 9 Vzdálenost mezi dvěma vrcholy nemusí být v případě orientovaného grafu symetrická. Obrázek: Nejkratší čety z u do v a naopak se liší. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Vzdálenost v ohodnoceném grafu V reálných aplikacích hledání nejkratších cest jsou hrany grafu obvykle nějakým způsobem ohodnoceny - např. vzdálenosti mezi městy silniční sítě, latence síťových spojů. Definice Délka cesty v ohodnoceném grafu je rovna součtu ohodnocení hran na této cestě. • Vzdálenost vrcholů je opět rovna délce nejkratší cesty. • Aby měl pojem vzdálenosti význam, v grafu nemůže existovat cyklus záporné délky. Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy ooooooooo Věta Pokud v grafu neexistuje cyklus záporné nebo nulové délky, je nejkratší sled v grafu (nejkratší) cestou. Důkaz. Nechť je součástí sledu s cyklus c. Tento cyklus má zřejmě kladnou délku. Potom existuje sled, který je „podsledem" s a cyklus c je z něj „vystřižen". Jelikož c má kladnou délku, je tento sled kratší než sled c obsahující. Takto lze pokračovat a sled zkracovat, dokud obsahuje nějaké cykly. Výsledný sled, který neobsahuje žádný cyklus, je cestou. □ Obrázek: Nejkratší sled je vyznačen červeně. Delší sledy vedou i po modrých a zelených hranách a tvoří cykly. Internet na L3 - datagramový přístup k přepínání paketů data vyšších vrstev umísťována do datagramů (fragmenty) putují sítí nezávisle A -tu*- -g>- 2 IL T Ě N X G3 1 "s*" jC směrování (Routing) = proces nalezení cesty mezi dvěma komunikujícími uzly cesta musí splňovat určité omezující podmínky ovlivňující faktory: statické: topologie sítě dynamické: zátěž sítě Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy ooooooooo Obrázek: Logická topologie IP/MPLS vrstvy sítě CESNET2. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Směr ování • úkolem směrování je: • vyhledávat optimální směrovací trasy • kriteriem optimality je metrika • dopravit datový paket určenému adresátovi • zpravidla se nezabývá celou cestou paketu • směrovač řeší jen jeden krok - komu paket předat jako dalšímu • někomu „blíže" cíli • tzv. hop-by-hop • ten pak rozhoduje, co s paketem udělat dál Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Směrování (Routing) vs. zasílání (Forwarding) • směrování • společná činnost směrovačů (globální) • proces nalezení/vytváření a údržby směrovacích tabulek • zasílání • lokální proces - každý směrovač samostatně • představuje proces průchodu paketů směrovačem • zaslání paketu na vybrané rozhraní směrovače (dle cílové adresy) • vyžaduje přístup ke směrovací tabulce Směrování v síti Distribuované smerovaní Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo ;omunikace Určení ceny (ohodnocení) linky - metrika: 0 všechny linky mají stejnou cenu (např. 1) • minimalizace ceny — minimalizace počtu skoků • nejjednodušší, nejčastěji využívané 0 cena linky = převrácená hodnota kapacity (1/prenosová-kapacita) o 10Mb linka má lOOx vyšší cenu než 1Gb linka o cena linky = zpoždění linky • 250ms satelitní spojení má lOx vyšší cenu než 25ms pozemní linka o cena linky = využití linky • linka s 90% využitím má lOx vyšší cenu než linka s 9% využitím • může způsobit oscilace (nezbytné tlumení) o cena linky = reálná cena (platba) za využití linky • staticky přiřazeno administrátorem <3 atd. Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy ooooooooo Distribuované směrování - základní přístupy Třídy distribuovaných směrovacích protokolů (dle charakteru směrovací informace): • Distance Vector (DV) - Bellman-Fordův algoritmus • sousední směrovače si v pravidelných intervalech či při topologické změně (např. výpadek zařízení) vyměňují kompletní kopie svých směrovacích tabulek • na základe obsahu přijatých updatů si pak doplňují nové informace a inkrementují své distance vektor číslo • metrika udávající počet hopů k dané síti • čili „všechny informace jen svým sousedům" • Link State (LS) • jednotlivé směrovače si zasílají pouze informace o stavu linek, na něž jsou bezprostředně připojeny • udržují si tak kompletní informace o topologii dané sítě -zařízení jsou si vědoma všech ostatních zařízení na síti • pak se počítá nejkratší cesta • čili „informace o svých sousedech všem" Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy •oooooooooooooooooooooooooo ooooooooo » „Klasický" algoritmus hledání nej kratší cesty. • Najde nejkratší cesty z jednoho vrcholu do všech ostatních. • Musí proto projít všechny vrcholy. • Pracuje pro orientovaný i neorientovaný graf. • Vyjma nezáporných cyklů vyžaduje nezáporné ohodnocení všech hran. • Lineární paměťová složitost. • Časová složitost záleží na použité datové struktuře. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy o»ooooooooooooooooooooooooo ooooooooo Dijkstrův algoritmus - popis • Počáteční vrchol označíme s. • Pro každý vrchol v grafu je udržována hodnota d [v] - délka nej kratší nalezené cesty z s do v. • Na počátku d[s]= 0 pro počáteční vrchol a d[v]= oo pro ostatní vrcholy. • Po skončení výpočtu obsahuje d [v] délku nejkratší cesty v grafu, pokud taková existuje, nebo oo v opačném případě. • Dále v proměnné p [v] ukládáme předchůdce vrcholu v na doposud nalezené nejkratší cestě z u. • Před výpočtem nastavíme hodnotu p [v] jako nedefinovanou pro všechny vrcholy. • Po skončení výpočtu je nejkratší cesta posloupnost vrcholů s, p [. . . p [v] . . . ] , ... p [p [v] ] , p [v] , v. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy oo»oooooooooooooooooooooooo ooooooooo Dijkstrův algoritmus - popis • Všechny vrcholy jsou rozděleny do dvou vzájemně disjunktních množin: S obsahuje všechny vrcholy, pro něž je v d [v] uložena definitivní nejkratší cesta z s do v v grafu. • Q obsahuje všechny ostatní vrcholy. • Vrcholy množiny Q jsou ukládány v prioritní frontě. • Nejvyšší prioritu má vrchol u s nejnižší hodnotou d[u] - nelze do něj již nalézt kratší cestu než která je aktuální. • V každé iteraci jsou provedeny následující kroky: • Odstraň vrchol u z počátku fronty. • Přesuň vrchol u z množiny Q do 5. • Relaxuj všechny hrany (u, v): o Pokud d[v] > d[u] +w(u, v), uprav d[v]. • w(u, v) značíme ohodnocení (weight) hrany (u, v). Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooo»ooooooooooooooooooooooo ooooooooo Dijkstrův algoritmus - pseudokód Vycházíme z počátečního vrcholu s, nek. značíme oo. Vlož všechny vrcholy do Q. d[s] = 0; p[s] = nedef; Pro všechny vrcholy v grafu vyjma počátečního: I d[u] = nek. I p[u] = nedef. Dokud není Q prázdná: I Odstraň z Q vrchol u s nejvyšší prioritou I Pro všechny hrany (u, v) proved5 : I | Pokud d[v] > d[u] + w(u,v) I I I d [v] = d[u] + w(u,v) I I I p [v] = u Úvod Směrování v s Distribuované směrování Kvalita služby oooo»oooooooooooooooooooooo Cesty mezi všemi OOOOOOOOO vrcholy Dijks trův algo ritmus - příklad Obrázek: Vrcholy množiny Q jsou vyznačeny modře. Napravo od grafu je znázorněn stav prioritní fronty. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooo»ooooooooooooooooooooo ooooooooo Dijkstrův algoritmus - časová složitost Označme n — \ V\, m — \E\. • Inicializace je provedena v lineárním čase vzhledem k počtu vrcholů. • Každou hranou prochází algoritmus vždy právě jednou nebo dvakrát (v případě neorientovaného grafu). • Hlavní cyklus je proveden vždy nkrát. • Je tudíž provedeno vždy právě n výběrů z prioritní fronty. • Složitost výběru z fronty zálež! na její implementaci: • Pole, seznam vrcholů - výběr lze provést v lineárním čase, složitost celého algoritmu je tedy 0(n2) + m. • Binární halda - výběr je proveden v čase 0(log(n)). Při každé relaxaci hrany může dojít k aktualizaci haldy (0(log(n)), celková složitost je tak rovna 0((n+ m)log(n)). • Fibonacciho halda - složitost výběru stejná jako v případě binární haldy, složitost úpravy haldy při relaxaci je ovšem konstantní - výsledná složtiost algoritmu 0(m + nlog(n)). http://en.wikipedia.org/wiki/Fibonacci_heap Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOO0OOOOOOOOOOOOOOOOOOOO ooooooooo Dijkstrův algoritmus - využití Dijkstrův algoritmus je používán v link-state směrovacích protokolech. Ty pracují na principu zasílání sousedních „vrcholů" aktivními síťovými prvky, které se směrování zúčastní. • Každý aktivní prvek periodicky rozesílá seznam sousedních vrcholů. • Ten je propagován skrze síť ke všem aktivním prvkům. • Každý aktivní prvek nezávisle na ostatnívh vypočítá strom nejkratších cest do všech ostatních aktivních prvků. • Riziko vzniků smyček v routovacích tabulkách. Nej používanější link-state protokoly jsou OSPF a IS-IS. Oba používají Dijkstrův algoritmus. Distribuované směrování ooooooosoo směrovače si zasílají pouze informaci o stavu linek, na něž jsou bezprostředně připojeny získají tím kompletní mapu sítě pak si počítají nejkratší cesty (např. s využitím Dijkstrova algoritmu) I při každé změně stavu linek směrovače testují pouze dosažitelnost svých bezprostředních sousedů výhoda: zaručená a rychlá konvergence, vhodné i pro rozsáhlé sítě nevýhoda: složitější algoritmus =>• větší nároky na CPU a paměť směrovače Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOO0OOOOOOOOOOOOOOOOOO ooooooooo Algoritmus • Předpoklad: • každý směrovač zná pouze cestu a cenu ke svým sousedům • Cíl: • v každém směrovací směrovací tabulka pro každý cíl • Idea: • šíří se topologie, cesty si počítají směrovače samy • fáze 1: šíření topologie (broadcast) • fáze 2: výpočet nej kratší cesty - (Dijkstra) • směrovače si udržují databázi stavů linek a periodicky posílají LS pakety svým sousedům • obsah LS paketu: identifikátor uzlu, cena spojů k sousedům, pořadové číslo, doba platnosti • každý směrovač přeposílá LS pakety dále (kromě toho, od nějž informaci dostal) Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooo«ooooooooooooooooo ooooooooo Link State III. - protokol OSPF • Open Shortest Path First • nej používanější LS protokol současnosti • metrika: cena (cost) • číslo (v rozsahu 1 až 65535) přiřazené ke každému rozhraní směrovače • čím menší číslo, tím má cesta lepší metriku (bude tedy preferována) • standardně je ke každému rozhraní přiřazena cena automaticky odvozená z šírky pásma daného rozhraní • cost = 100000000/bandwidth (bw v bps) • možno ručně měnit • rozšíření: o autentizace zpráv • směrovací oblasti - další úroveň hierarchie • load-balancing - více cest se stejnou cenou Uvod Směrování v síti Distribuované směrování Kvalita služby OOOOOOOOOO0OOOOOOOOOOOOOOOO Cesty mezi všemi vrcholy ooooooooo Bellman-Ford algoritmus • Stejně jako Dijkstrův algoritmus vypočítá vzdálenosti všech vrcholů grafu z jednoho zdroje. • Základní strukturou podobný Dijkstrovu algoritmu. • Graf smí obsahovat i záporně ohodnocené hrany. • Cykly s celkovým záporným ohodnocením jsou algoritmem detekovány. • Namísto výběru hrany k relaxaci v každé iteraci relaxuje všechny hrany. • Vyšší časová složitost než Dijkstrův algoritmus - O(mn). Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooo»ooooooooooooooo ooooooooo Bellman-Ford - pseudokód Proměnné d [v] a p [v] mají stejný význam jako u Dijkstrova algoritmu. Počet vrcholů grafu označme n. d[s] = 0; p[s] = undef; Pro všechny vrcholy v grafu vyjma počátečního: I d[u] = nek. I p[u] = nedef. Opakuj n-krát: I Pro všechny hrany (u,v): I | Pokud d[v] > d[u] + w(u,v) I I I d [v] = d[u] + w(u,v) I I I p [v] = u Pro všechny hrany (u,v) opakuj: I Pokud d [v] > d[u] + w(u,v): I | Chyba: graf obsahuje cyklus neg. váhy Úvod Směrování v sít Distribuované směrování Kvalita služby oooooooooooo»oooooooooooooo Cesty mezi všem ooooooooo vrcholy D „11 „ ._ . - příklad Dellrr nan-hord - Obrázek: Relaxované hrany v každém kroku jsou vyznačeny modře. Napravo od grafu je vypsána délka nejkratších cest do vrcholů. V poslední (nezobrazené) iteraci již nedojde k žádným změnám. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooo»ooooooooooooo ooooooooo Bellman-Ford - aplikace • Bellman-Ford algoritmus je používán v druhé třídě směrovacích protokolů - distance-vector. • Namísto struktury celého grafu jsou mezi aktivními prvky přenášeny jim známé vzdálenosti do ostatních aktivních prvků. • Každý aktivní prvek periodicky rozesílá tyto sobě známé vzdálenosti k ostatním. • Obdrží-li aktivní prvek tabulku vzdáleností, provede relaxaci hran, případně aktualizuje svoji směrovací tabulku a rozešle svým sousedům. • Distance-vector protokoly mají nižší výpočetní složitost než link-state protokoly. • Nejznámějšími distance-vector protokoly jsou RIP, BGP, EGP. Distribuované smerovaní oooo»ooooooooo směrovač si udržuje všechny známé routy v tabulce ve formě uspořádaných trojic (/V, G, D), kde: 1 N ... cílová sít G . .. adresa následujícího směrovače D .. . vzdálenost do cílové síťě (metrika) tabulky se upravují tak, aby se směrovalo nejkratší cestou problémy: pomalá konvergence, příliš mnoho režijních dat Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooo»ooooooooooo ooooooooo Algoritmus • Předpoklad: • každý směrovač zná pouze cestu a cenu ke svým sousedům • Cíl: • v každém směrovací směrovací tabulka pro každý cíl • Idea: • řekni sousedům svou představu směrovací tabulky • Inicializace: • sousedé: známá cena • Distance Vector = < cil, cena > • ostatní: nekonečno • resp. hodnota definovaná jako nekonečno (pro RIP např. 16) • Aktualizace: • pokud je cesta v získaném DV zvětšená o cenu cesty k danému sousedovi lepší než stávající uložená, aktualizuj tabulku Uvod Směrování v síti Distribuované směrování Kvalita služby oooooooooooooooo»oooooooooo Cesty mezi všemi vrcholy ooooooooo Ilustrace problému pomalé konvergence 10.1.0.0 E0 SO 10.2.0.0 "Z_ 10.3.0.0 —z_ 10.4.0.0 Routing Table 10.1.0.0 E0 0 10.2.0.0 so 0 10.3.0.0 SO 1 10.4.0.0 SO 2 Routing Table 10.2.0.0 SO 0 10.3.0.0 S1 0 10.4.0.0 S1 1 10.1.0.0 SO 1 Routing Table 10.3.0.0 SO 0 10.4.0.0 EO Down 10.2.0.0 SO 1 10.1.0.0 SO 2 pomalá konvergence zapříčiní vznik nesprávných údajů ve směrovacích tabulkách Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooo#ooooooooo ooooooooo Ilustrace problému pomalé konvergence Routing Table 10.1.0.0 EO 0 10.2.0.0 SO 0 10.3.0.0 SO 1 10.4.0.0 SO 2 Routing Table 10.2.0.01 SO I 0 10.3.0.0 S1 0 10.4.0.0 S1 1 10.1.0.0 SO 1 Routing Table 10.3.0.01 SO 0 10.4.0.0 SO 2 10.2.0.0 SO 1 10.1.0.0 SO 2 • směrovač C usoudí, že nej lepší cesta do sítě 10.4.0.0 je přes směrovač B Uvod Směrování v síti Distribuované směrování Kvalita služby oooooooooooooooooo»oooooooo Cesty mezi všemi vrcholy ooooooooo Distance Vector III. Ilustrace problému pomalé konvergence Routing Table 10.1.0,0| EO | 0 10.2.0.0 SO 0 10.3.0.0 SO 1 10.4.0.0 SO 2 Routing Table 10.2.0.01 SO | 0 10.3.0.0 S1 o 10.4.0.0 S1 1 10.1.0.0 SO 1 Routing Table 10.3.0.01 SO 0 10.4.0.0 SO 2 10.2.0.0 SO 1 10.1.0.0 SO 2 • směrovač A opraví svojí směrovací tabulku - chybně Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooo»ooooooo Cesty mezi všemi vrcholy ooooooooo Distance Vector III. Ilustrace problému pomalé konvergence Routing Table 10.1.0.0 E0 | 0 10.2.0.0 SO D 10.3.0.0 SO 1 10.4.0.0 SO 2 Routing Table 10.2.0.01 SO | 0 10.3.0.0 S1 o 10.4.0.0 S1 1 10.1.0.0 SO 1 Routing Table 10.3.0.01 SO | 0 10.4.0.0 SO Z 10.2.0.0 SO 1 10.1.0.0 SO 2 • metrika pro síť 10.4.0.0 roste do nekonečna (v rámci RIP do 16) Distribuované smerovaní ooooooooooo»oo 110.1.0.0 E0 10.2.0.0 "Z_ s° so 10.3.0.0 -Z_ 81 SO 10.4.0.01 EO Routing Table 10.1.0.0 EO 0 10.2.0.0 SO 0 10.3.0.0 SO 1 10.4.0.0 SO 2 Routing Table 10.2.0.0 SO 0 10.3.0.0 S1 0 10.4.0.0 S1 1 10.1.0.0 so 1 Routing Table 10.3.0.0 SO 0 10.4.0.0 EO 0 10.2.0.0 SO 1 10.1.0.0 SO 2 Řešení: dělení horizontu směrovač nesděluje cestu zpět uzlu, od kterého se o ní dozvěděl problém zůstává ve složitějších topologiích (navržena řada rozšíření) Uvod Směrování v síti Distribuované směrování Kvalita služby oooooooooooooooooooooo»oooo Cesty mezi všemi vrcholy ooooooooo Distance Vector IV. - protokol RIP I. • hlavní představitel DV směrování • RIPvl (RFC 1058) • RIPv2 (RFC 1723) - přidává např. autentizaci směrovacích informací • sítě identifikovány s využitím mechanismu CIDR • jako metrika se využívá počet hopů • přenos paketu mezi 2 sousedními směrovací má délku 1 • nekonečno — 16 • => nelze použít pro sítě s minimálním počtem hopů mezi libovolnými dvěma směrovací > 15 • směrovače zasílají informaci každých 30 sekund » triggered update při změně stavu hrany o časový limit 180s (detekce chyb spojení) • použití: o vhodné pro malé sítě a stabilní linky • není příliš vhodný pro redundantní sítě Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooo»ooo ooooooooo Distance Vector IV. - protokol RIP II. RIP message from C Net2 4 Net3 H Net6 A Net8 3 Net9 5 Old routing table Netl 7 A Net2 2 C Net6 8 ť Net8 4 Ľ Net9 4 ľ RIP message from C after increment Net2 5 Net3 9 Net6 5 Net8 4 Net9 6 Updating algorithm New routing table Netl 7 A Net2 5 C Net3 9 C Net6 5 C Net8 4 Ľ Net9 4 F Netl: No news, do not change Net2: Same next hap, replace Net3: A new router, add Net6: Different next hop, new hop count smaller, replace Net8: Different next hop, new hop count the same, do not change Net9: Different next hop, new hop count larger, do not change Obrázek: RIP - příklad aktualizace tabule^. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy oooooooooooooooooooooooo»oo ooooooooo Distance Vector - protokol RIP III. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooo»o ooooooooo Distance Vector IV. - protokol RIP IV. Obrázek: RIP - příklad: finální stav tabulek. ■0 0.0 Úvod Směrovár lí v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo • základní parametry síťových toků: • spolehlivost (reliability) - požadavek plné spolehlivosti vs. tolerance definované ztrátovosti • zpoždění (latency, delay) • rozptyl zpoždění (jitter) • přenosová kapacita (bandwidth) Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Směrování - hledání nejširší cest » Příklad grafu s vyznačenými šířkami pásma (ohodnocení hran) • cesta šířka(l-2-3-5 ) = 10 a cesta šířka(l-4-2-3-5) = 10 • cesta šířka(l-4-3-5) = 15 • cesta šířka(l-4-5) = 20 • cesta šířka cesty je minimum šířek hran • optimalizační funkce cesty je maximální šířka cest Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Směrování - hledání nejširší cest • úprava optimalizační funkce - zavedení záporné šířky pásma • optimalizační funkce cesty je minimální šířka cest • úprava známých algoritmů na hledání minimální cesty • Dijkstra • Bellman Ford Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy oooooooooooooooooooooooo»oo ooooooooo A* a Igoritmus • Upravený Dijkstrův algoritmus. • Používá se zejména k nalezení cesty do jednoho vrcholu -např. navigace. • Krom délky nejkratší cesty do každého vrcholu bere při vyhledávání v úvahu i heuristický odhad jeho vzdálenosti od cíle. • Každé cestě je přiřazen heuristický odhad délky jako součet ohodnocení jejích hran a heuristické ohodnocení koncového vrcholu. • Do prioritní fronty nejsou ukládány vrcholy grafu, ale cesty. • Nejvyšší prioritu má cesta s nejnižším heuristickým ohodnocením. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooo»o ooooooooo A* a Igoritmus • Pro každý vrchol je uloženo, je-li již „uzavřen" či nikoliv, tzn., byl-li již navštíven, prozkoumán odebráním z fronty některé cesty v tomto vrcholu končící. Dijkstrův algoritmus lze použít také k nalezení čety do jednoho vrcholu grafu. Obvykle ale projde mnoho neperspektivních vrcholů - např. při vyhledávání trasy v mapě jde i opačným směrem stejně daleko, jak správným. A* tyto vrchly eliminuje pomocí heuristiky, je-li vhodně zvolena. • Časová složitost záleží na kvalitě zvolené heuristiky - nejhůře může být exponenciální, nejlépe polynomiální, a to vůči délce optimální cesty. • Paměťová složitost může být v nej horším případě také exponenciální - existuje několik zlepšujících variant algoritmu. Více informací v přednášce doc. Hliněného: http://video.fi.muni.cz/public/ITI/ITI2.ayi U vod Směrování v síti Distribuované směrování Kvalita služby oooooooooooooooooooooooooo* Cesty mezi všemi vrcholy ooooooooo A* algoritmus - pseudokód Označme počáteční vrchol s, koncový c. Označ všechny vrcholy jako neuzavřené. Inicializuj prioritní frontu Q vrcholem (cestou) s. Dokud Q není prázdná: I Odstraň cestu p z Q. I Nechť x je koncový vrchol p. I Pokud x je uzavřený: I | pokračuj další iterací. I Pokud x = c: I | Vrať cestu p jako výsledek. I Uzavři x. I Pro všechny hrany (x, y): I | Vlož do fronty cestu p + (x, y) Vrať zprávu o neexistenci cesty. ■0 0.0 • Vypočítavá nej kratší vzdálenost mezi všemi dvojicemi vrcholů v grafu. • Graf může obsahovat záporně ohodnocené hrany, cykly s celkovým záporným ohodnocením vedou k chybnému řešení. • Mezi každými dvěma dvojicemi vrcholů postupně vylepšuje nejkratší známou vzdálenost. • V každém kroku algoritmu je definována množina vrcholů, kterými je možno nejkratší cesty vést. • Každou iterací je do této množiny přidán jeden vrchol. • V každé z n iterací jsou aktualizovány cesty mezi všemi n2 dvojicemi vrcholů. Časová složitost algoritmu je tedy 0(n3). • Paměťová složitost algoritmu je 0(n2). Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOOOOOOOOO O0OOOOOOO Floyd-Warshallův algoritmus - bližší popis • Nechť jsou vrcholy grafu očíslovány 1... n. • Nejprve algoritmus uvažuje pouze hrany grafu. Následně prohledává cesty procházející pouze vrcholem 1. Poté cesty procházející pouze vrcholy 1, 2, atd. • Mezi každými dvěma vrcholy u, v je v k + 1. iteraci algoritmu známa cesta využívající vrcholů 1... k. • Pro nejkratší cestu mezi těmito vrcholy využívající vrcholů 1... k + 1 jsou dvě možnosti: • Vede opět pouze po vrcholech 1... k. • Vede po vrcholech 1... k z u do vrcholu k + 1 a z něj poté dov. • Na konci výpočtu jsou známy nejkratší čety využívající všech vrcholůů grafu. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo oo»oooooo Floyd-Warshallův algoritmus - pseudokód • V matici d na pozici d [i] [j] je uložena vypočtená vzdálenost vrcholů /',_/'. • Vstupem je graf v podobě matice sousednosti, kde jednotlivé prvky značí ohodnocení hrany nebo oo Pro všechna k od 1 do n: I Pro všechna i od 1 do n: I | Pro všechna j od 1 do n: I | | d [i] [j] = minimum (d [i] [j] , d [i] [k] + d [k] [ j]) Obrázek: Vrcholy, kterými mohou vést cesty, jsou vyznačeny. Matice udává nejkratší nalezené vzdálenosti mezi dvojicemi vrcholů. 1 2 3 4 5 1 018 4 12 ? 2 18 0 ? 5 ? 3 4 ? 0 7 3 4 12 5 7 0 2 5 ? ? 3 2 0 1 2 3 4 5 1 0 18 412 ? 2 18 0 22 5 ? 3 4 22 0 7 3 4 12 5 7 0 2 5 ? ? 3 2 0 1 2 3 4 5 1 0 18 412 ? 2 18 0 22 5 ? 3 4 22 0 7 3 4 12 5 7 0 2 5 ? ? 3 2 0 1 2 3 4 5 1 0 18 411 7 2 18 0 22 5 25 3 4 22 0 7 3 4 11 5 7 0 2 5 7 25 3 2 0 12 3 4 1 0 16 411 2 16 0 12 5 3 412 0 7 4 11 5 7 0 5 7 7 3 2 12 3 1 0 14 4 2 14 0 10 3 410 0 4 9 5 5 5 7 7 3 Výhodou Floyd-Warshallova algoritmu je jeho snadná aplikace v distribuovaném prostředí - mezi autonomními jednotkami, které si mohou informace předávat jen pomocí zasílání zpráv po síti. • Každý vrchol grafu vypočítává nej kratší cesty do všech ostatních vrcholů grafu. • Na začátku zná každý vrchol jen cestu do svých sousedů. • Stejně jako v sekvenční variantě algoritmu, každá iterace algoritmu přidává jeden vrchol, kterým mohou procházet hledané nej kratší cesty. • Přidaný vrchol v každé iteraci rozešle svoji tabulku vzdáleností ostatním vrcholům grafu. • Ostatní vrcholy pomocí své a přijaté tabulky aktualizují nejkratší cesty do všech vrcholů. Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy ooooo»ooo Distribuovaný Floyd-Warshall - pseudokód Algoritmus je spuštěn ve vrcholu u. d[u] = 0; p[u] = nedef. Pro všechny ostatní vrcholy v: I Je-li v sousední vrchol: I I d[v] = w(u,v); p[v] = v; I Jinak: I I d[v] = nekon.; p[v] = nedef; Dokud nebyly vybrány všechny vrcholy: I Vyber doposud nevybraný vrchol v. I Pokud u = v: I | Rozešli ostatním vrcholům pole d. I Jinak: I | Přijmi od vrcholu v jeho pole dv. I Pro všechny vrcholy w: I | d[w] = minimum (d [w] , d[v]+dv[w]), uprav p[v]. • Pro správnost algoritmu je nutné, aby všechny výpočetní uzly (vrcholy grafu) vybraly vždy stejný vrchol, který poté rozesílá svoji tabulku vzdáleností. • Algoritmus je neefektivní z hlediska množství zasílaných dat. Pokud v některém vrcholu platí d[v]= oo pro právě vybraný vrchol v, jeho cesty se nijak neupraví a nemusí mu tedy být zasílána tabulka vzdáleností tohoto vrcholu. • Před rozesláním tabulky vzdáleností se mohou vrcholy vzájemně informovat, které mají obdržet tuto tabulku s výrazně nižšími nároky na přenesená data <í= Touegův algoritmus. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooo»o Cvičení O Na grafu níže vypočítejte nejkratší cesty použitím Dijkstrova, Bellman-Fordova a Floyd-Warshallova algoritmu. V případě prvních dvou použijte různé počáteční vrcholy. O Navrhněte způsob implementace nastíněného vylepšení distribuovaného Floyd-Warshallova algoritmu. Uvažujte, že výpočetní uzly mohou zasílat zprávy jen po hranách grafu (broadcasting je implementován přeposíláním zpráv mezi uzly). Si Q Proč nepracuje Dijkstrův algoritmus korektně na grafech obsahujících záporně ohodnocené hrany? K jakým výsledkům může dojít, je-li na takovém grafu spuštěn? O Dokažte tvrzení, označované také jako trojúhelníková nerovnost v grafech: Vu, v, w G V(G) : S(u, w) < S(u, v) + S(v, w) O Nechť vstupem Bellman-Fordova algoritmu je graf, v němž každá nejkratší cesta obsahuje nejvýše k hran. Navrhněte úpravu algoritmu umožňující ukončit výpočet po k + 1 iteracích.