Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy 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 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 algoritmu Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo 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 8(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ší. u Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy 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ů. Délka cesty v ohodnoceném grafu je rovna součtu ohodnocení hran na této cestě. 9 Vzdálenost vrcholů je opět rovna délce nejkratší cesty. 9 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 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. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Směrování obecně 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 ] -EHIHiHIte X • 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ě Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy ooooooooo Příklad reálné sítě 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ěrování o úkolem směrování je: • vyhledávat optimální směrovací trasy • kriteriem optimality je metrika • dopravit datový paket určenému adresátovi o 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 9 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 na lezení/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ěrováče (dle cílové adresy) • vyžaduje přístup ke směrovací tabulce Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Cena komunikace Určení ceny (ohodnocení) linky - metrika: 9 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í) o cena linky = reálná cena (platba) za využití linky • staticky přiřazeno administrátorem • 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) - Bell man-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 o na základe obsahu přijatých updatů si pak doplňují nové informace a inkrementují své distance vektor číslo 9 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á nej kratší 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 Dijkstrův algoritmus • „Klasický" algoritmus hledání nejkratší cesty. 9 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. Uvod Směrování v síti Distribuované směrování Kvalita služby O0OOOOOOOOOOOOOOOOOOOOOOOOO Cesty mezi všemi vrcholy ooooooooo Dijkstrův algoritmus - popis • Počáteční vrchol označíme s. 9 Pro každý vrchol v grafu je udržována hodnota d [v] - délka nejkratší 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. 9 Po skončení výpočtu je nejkratší cesta posloupnost vrcholů s, p [. . . p [v] . . . ] , ... p [p [v] ] , p [v] , v. Uvod Směrování v síti Distribuované směrování Kvalita služby OO0OOOOOOOOOOOOOOOOOOOOOOOO Cesty mezi všemi vrcholy 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. o 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. o Relaxuj všechny hrany (ív, v): • Pokud d [v] > d[u] -\-w(u, v), uprav d [v]. • w(u, v) značíme ohodnocení (weight) hrany (ív, v). Úvod 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 □ s 1 ► 1 OnO Uvod Směrování v síti Distribuované směrování Kvalita služby OOOO0OOOOOOOOOOOOOOOOOOOOOO Cesty mezi všemi vrcholy ooooooooo Dijkstrův algoritmus - příklad Obrázek: Vrcholy množiny Q jsou vyznačeny modře. Napravo od grafu znázorněn stav prioritní fronty. Úvod 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). o 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 (9((a? + 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 Uvod Směrování v síti Distribuované směrování Kvalita služby oooooo«oooooooooooooooooooo Cesty mezi všemi vrcholy 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. Nejpoužívanější link-state protokoly jsou OSPF a IS-IS. Oba používají Dijkstrův algoritmus. Uvod Směrování v síti Distribuované směrování Kvalita služby OOOOOOO0OOOOOOOOOOOOOOOOOOO Cesty mezi všemi vrcholy ooooooooo Link State I. Směrovací tabulka 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 Uvod Směrování v síti Distribuované směrování Kvalita služby OOOOOOOO0OOOOOOOOOOOOOOOOOO Cesty mezi všemi vrcholy ooooooooo Link State II 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 nejkratší 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) Uvod Směrování v síti Distribuované směrování Kvalita služby OOOOOOOOO0OOOOOOOOOOOOOOOOO Cesty mezi všemi vrcholy ooooooooo Link State III. - protokol OSPF • Open Shortest Path First • nejpouží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 šířky pásma daného rozhraní • cost = 100000000/bandwidth (bw v bps) • možno ručně měnit • rozšírení: • autentizace zpráv • směrovací oblasti - další úroveň hierarchie • load-balancing - více cest se stejnou cenou Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOO0OOOOOOOOOOOOOOOO ooooooooo Bellman-Ford algoritmus o 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 OOOOOOOOOOO0OOOOOOOOOOOOOOO Cesty mezi všemi vrcholy 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íti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy oooooooooooo«oooooooooooooo ooooooooo Bellman-Ford - příklad 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. □ Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOO0OOOOOOOOOOOOO ooooooooo Bell m an-Ford - aplikace • Bell man-Ford algoritmus je používán v druhé třídě směrovacích protokolů - distance-vector. o 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ů. 9 Každý aktivní prvek periodicky rozesílá tyto sobě známé vzdálenosti k ostatním. 9 Obdrží-li aktivní prvek tabulku vzdáleností, provede relaxaci hran, případně aktualizuje svoji směrovací tabulku a rozešle svým sousedům. o 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. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOO0OOOOOOOOOOOO ooooooooo Distance Vector I. Net A Net D Network Interface 1 Network Interface 1 Network Interface 1 A EO B SO C SO B SO C S1 D EO C SO ■ A SO ■ B SO D SO 1 D S1 1 A SO 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íť • 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 Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOO0OOOOOOOOOOO ooooooooo Distance Vector II 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 o Inicializace: • sousedé: známá cena • Distance Vector = < c/7, 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 Úvod 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 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 Down 10.2.0.0 50 1 10.1.0.0 SO 2 I y I -v y-v ■ y -i y y i y i ■ o pomalá konvergence zapríčiní vznik nesprávných udaju 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 OOOOOOOOOOOOOOOOO0OOOOOOOOO ooooooooo Distance Vector III. Ilustrace problému pomalé konvergence 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 Tabla 10.2.0.0 SO 0 10.3.0.0 S1 0 10.4.0.0 1 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 9 směrovač C usoudí, že nejlepší cesta do sítě 10.4.0.0 je přes směrovač B Úvod 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.o| 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 Ô 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ě Úvod 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.01 EČT ~Q 10.2.0.0 SO 0 10.3.0.0 SO 1 10.4.0.0 SO 2 Routing Table 10.2.0.01 SČT ~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 SČT ~Q 10.4.0.0 SO 2 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) Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOO0OOOOOO ooooooooo Distance Vector III. Ilustrace problému pomalé konvergence 10.1.0.0 Packet for Network 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 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 Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOOO0OOOOO ooooooooo Distance Vector III. Ilustrace problému pomalé konvergence 10.1.0.0 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 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 OOOOOOOOOOOOOOOOOOOOOO0OOOO Cesty mezi všemi vrcholy ooooooooo Distance Vector IV. - protokol RIP I. • hlavní představitel DV směrování o 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ě □ [fP ► 4 !Š ► 4 > Úvod Směrování v síti Distribuované směrování Kvalita služby OOOOOOOOOOOOOOOOOOOOOOO0OOO Cesty mezi všemi vrcholy ooooooooo Distance Vector IV. - protokol RIP II. RIP message from C Net2 4 Net3 8 Net6 4 Net8 3 Net9 5 Old routing table Netl 7 A Net2 2 C Net6 8 F Net8 4 E Net9 4 F RIP message from C after increment Net2 5 Net3 9 Net6 5 Net8 4 Net9 6 New routing table Updating algorithm Netl 7 A Net2 5 C Net3 9 C Net6 5 C Net8 4 E Net9 4 F Netl: No news, do not change Net2: Same next hop, 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 tabulek. = Směrování v síti Distribuované směrování Kvalita služby OOOOOOOOOOOOOOOOOOOOOOOO0OO Cesty mezi všemi vrcholy ooooooooo Distance Vector - protokol RIP III. 14 1 - 55 1 - 14 1 - 23 1 - 78 1 08 1 - 23 1 - 55 1 - 66 1 - Obrázek: RIP - příklad: iniciální stav tabulek. □ rS1 Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOOOOOOO0O ooooooooo Distance Vector IV. - protokol RIP IV. 08 2 E 14 1 — 23 1 — 55 2 B 66 3 E 78 1 — 92 2 A Net: 23 Net: 14 Net: 78 08 3 A 14 1 — 23 2 A 55 1 — 66 2 C 78 2 A 92 3 A B 08 3 A 14 2 A 23 2 A 55 3 A F 66 4 A 78 1 -- 92 1 -- Net: 55 C 08 2 D 14 2 B 23 3 D 55 1 -- 66 1 -- 78 3 B 92 4 B Net: 92 Net: 66 D 08 1 -- J-í Net: 08 J-l 08 1 — 14 2 A 14 3 E 23 1 -- 23 2 E 55 3 A 55 2 C 66 2 D 66 1 — 78 2 A 78 3 E 92 3 A 92 4 E Obrázek: RIP - příklad: finální stav tabulek. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy ooooooooooooooooooooooooooo ooooooooo Kvalita služby základní parametry síťových toků: • spolehlivost (reliability) - požadavek plné spolehlivosti vs. tolerance definované ztrátovosti o zpoždění (latency delay) 9 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ší cesty • Příklad grafu s vyznačenými šířkami pásma (ohodnocení hran) 9 cesta šírka(l-2-3-5 ) = 10 • cesta šírka (1-4-2-3-5) = 10 • cesta šířka(1-4-3-5) = 15 • cesta šírka(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ší cesty • úprava optimalizační funkce - zavedení záporné šírky pásma • optimalizační funkce cesty je minimální šírka cest 9 ú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 OOOOOOOOOOOOOOOOOOOOOOOO0OO ooooooooo A* algoritmus • 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. o 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* algoritmus • 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. o Č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 . f i .muni . cz/public/ITI/IJJ^ - i Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy oooooooooooooooooooooooooo* 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. Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy •oooooooo Floyd-Warshallův algoritmus o Vypočítává nejkratší 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). 9 Paměťová složitost algoritmu je 0(n2). Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy 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. Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOOOOOOOOO OO0OOOOOO Floyd-Warshallův algoritmus - pseudokód 9 V matici d na pozici d [i] [j] je uložena vypočtená vzdálenost vrcholů ij. 9 Vstupem je graf v podobě matice sousednosti, kde jednotlivé prvky značí ohodnocení hrany nebo oc 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]) Úvod Směrování v síti Distribuované směrování Kvalita služby Cesty mezi všemi vrcholy OOOOOOOOOOOOOOOOOOOOOOOOOOO 000*00000 Floyd-Warshallův algoritmus - příklad Obrázek: Vrcholy, kterými mohou vést cesty, jsou vyznačeny Matice udává nejkratší nalezené vzdálenosti mezi dvojicemi vrcholů. i 2 018 18 o 4 ? 12 5 ? 7 3 4 ? 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 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 1 2 3 4 5 1 0 16 411 7 2 16 0 12 5 7 3 4 12 o 7 3 4 11 5 7 o 2 5 7 7 3 2 0 1 2 3 4 5 1 0 14 4 9 7 2 14 0 10 5 7 3 4 10 o 5 3 4 9 5 5 0 2 5 7 7 3 2 0 □ Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy OOOO0OOOO 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. 9 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í nej kratší 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 OOOOO0OOO 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 | 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] . Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy OOOOOO0OO 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]= oc 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. Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy ooooooo«o Cvičeni O Na grafu níže vypočítejte nej kratší 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). Uvod Směrování v síti Distribuované směrování Kvalita služby ooooooooooooooooooooooooooo Cesty mezi všemi vrcholy 00000000« Cvičeni 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, v, w G V(G) : 5(u, w) < 5(u, v) + 5(v, w) Q Nechť vstupem Bellman-Fordova algoritmu je graf, v němž každá nej kratší cesta obsahuje nejvýše k hran. Navrhněte úpravu algoritmu umožňující ukončit výpočet po k + 1 iteracích.