Ú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 ^S1^ 4!^ > ^)t^O O Úvod Q Směrování v síti Q Distribuované směrování • Link-state algoritmy • Distance vector algoritmy Q Kvalita služby • A* algoritmus Q 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 Nejkratší cesty - vzdá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. • 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ší. 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. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Nej kratší cesty a cykly 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ů • datagramy (fragmenty) putují sítí nezávisle A • 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ě • ú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 • smerovaní • 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 Určení ceny (ohodnocení) linky - metrika: • všechny linky mají stejnou cenu (např. 1) • minimalizace ceny — minimalizace počtu skoků • nejjednodušší, nejčastěji využívané • cena linky = převrácená hodnota kapacity (1/prenosová .kapacita) • 10Mb linka má lOOx vyšší cenu než 1Gb linka • cena linky = zpoždění linky • 250ms satelitní spojení má lOx vyšší cenu než 25ms pozemní linka • 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í) • cena linky = reálná cena (platba) za využití linky • staticky přiřazeno administrátorem • atd. 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" Si S • „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. • 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. • 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 S. • Relaxuj všechny hrany (u, v): • Pokud d[v] > d[u] +w(u,v), uprav d[v]. • w(u, v) značíme ohodnocení (weight) hrany (u, v). 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 ^S1^ 4!^ > ^)t^O Obrázek: Vrcholy množiny Q jsou vyznačeny modře. Napravo od grafu je znázorněn stav prioritní fronty. U vod Směrování v síti Distribuované směrování Kvalita služby OOOOOÄOOOOOOOOOOOOOOOOOOOOO Cesty mezi všemi vrcholy ooooooooo Dijkstrův algoritmus - časová složitost Označme n — \ V\, m — \E\. 9 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 Si 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. SPF strom 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) • 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 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 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. Si :e • 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. R1 <^^> R2 R3 Network I Interface Network Interface Network I Interface • směrovač si udržuje všechny známé routy v tabulce ve formě uspořádaných trojic (A/, G, D), kde: • 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 • 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 Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy oooooooooooooooo«oooooooooo ooooooooo Distance Vector III. 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 Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooo«ooooooooo ooooooooo Distance Vector III. Ilustrace problému pomalé konvergence Routincj 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 Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOÄOOOOOOOO 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ě Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooo«ooooooo 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) Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOOÄOOOOOO ooooooooo Distance Vector III. Ilustrace problému pomalé konvergence 10.1.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 4 Routing Table 10,2.0.0 SO 0 10.3.0.0 S1 0 10.4.0.0 S1 3 10.1.0.0 SO 1 Routing Table 10.3.0.0 SO 0 10.4.0.0 SO 2 10.2.0.0 SO 1 10.1.0.0 SO 2 • Důsledek: vznik směrovací smyčky • paket pro síť 10.4.0.0 skáče mezi routery B a C Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooo«ooooo ooooooooo Distance Vector III. Ilustrace problému pomalé konvergence 10.1.0.0 EO 10.2.0.0 "Z_ s° SO 10.3.0.0 -Z_ 81 SO 10.4.0.0 E0 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 E0 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í) • hlavní představitel DV smerovaní • 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 • časový limit 180s (detekce chyb spojení) • použití: • 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 OOOOOOOOOOOOOOOOOOOOOOO0OOO 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 tabulgk. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy 0000000000000000000000000*0 ooooooooo Distance Vector IV. - protokol RIP IV. Obrázek: RIP - příklad: finální stav tabulek. ^S1^ 4!^ > ^)o^O Si • 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) • Příklad grafu s vyznačenými šířkami pásma (ohodnocení hran) • cesta šířka(l-2-3-5 ) = 10 • 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 • úprava optimalizační funkce - zavedení záporné šírky pásma • optimalizační funkce cesty je minimální šířka cest • úprava známých algoritmu na hledání minimální cesty • Dijkstra • Bellman Ford Si • 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. • 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.avi 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 I Vlož do fronty cestu p + (x, y) Vrať zprávu o neexistenci cesty. Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOOOOOOOOO «00000000 Floyd-Warshallův algoritmus • Vypočítává 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 o«ooooooo 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]) ^S1^ 4!^ > ^)t^O Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOOOOOOOOO 000*00000 "" ' ;oritmus - příklad 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 O ? 5 ? 3 4 ? O 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 O 7 3 4 12 5 7 O 2 5 ? ? 3 2 O 1 2 3 4 5 1 0 18 412 ? 2 18 0 22 5 ? 3 4 22 O 7 3 4 12 5 7 O 2 5 ? ? 3 2 O 1 2 3 4 5 1 0 18 411 7 2 18 0 22 5 25 3 4 22 O 7 3 4 11 5 7 O 2 5 7 25 3 2 O 12 3 4 1 0 16 411 2 16 0 12 5 3 412 O 7 4 11 5 7 O 5 7 7 3 2 12 3 1 0 14 4 2 14 0 10 3 410 O 4 9 5 5 5 7 7 3 Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo oooo»oooo Distribuovaný Floyd-Warshall 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ů. Úvod Směrování v síti Distribuované směrování Kvalita s ooooooooooooooooooooooooooo lužby Cesty mezi všemi vrcholy 00000*000 Distribuovaný Floyd-Warshall - pseudoki 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: 1 1 d[v] = w(u,v); p[v] = v; I Jinak: 1 1 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]. □ Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo oooooo»oo Distribuovaný Floyd-Warshall • 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. Q 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). ^S1^ 4!^ > ^)t^O Si O 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, i/, w G V(G) : S(u, w) < S(u, v) + S(v, w) Q 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.