4222785
| Question | Answer |
| Typy a podtypy komunikací | Jeden-jednomu – jedna komunikující dvojice – více komunikací typu jeden-jednomu – permutační směrování Jeden-mnoha – vysílání ve skupině (multicast) – vysílání jeden-všem (one-to-all broadcast, OAB) – rozesílání jeden-všem (one-to-asll scatter) Všichni-všem –vysílání všichni-všem (all-to-all broadcast) – rozesílání všichni všem (all-to-all-scatter) |
| Čím se dá popsat komunikace v propojovacích sítích? | – topologie (jak je to propojený) – směrovací algoritmus (určení trasy) – řízení toku (mechanismy pro přidělování sdílených prostředků sítě zprávám/paketům) = jak řešit sdílení linky |
| Typy kanálů ve směrovačích | Vnější kanály (#souběžně použitelných portů): – 1-portový (1vstup./1výst) – všeportový (dochází k permutaci/křížení mezi V/V) – výstupně všeportový (rozkopíruje vstup) Vnitřní kanály (ejekční/injekční) – kom. s počítačem – 1-portový – k-portový – všeportový |
| Typy směrovačů podle front | Bufferování na V/V – na vstupu i výstupu – na vstupu – na výstupu |
| Typy směrovačů podle směrovosti | – jednosměrné (simplexní, jen jedním směrem) – poloduplexní (buď tam nebo zpátky) - plně duplexní (jde posílat zároveň tam i zpět) |
| Jednotky komunikace | – zprávy: na úrovni programu, různá délka – paket: část zprávy pevné délky, samostatně směrovatelný, skládá se z hlavičkového flitu a datového flitu – flit: (float digit) konstatní velikost, není samost. směrovatelný – fit: (physical digit) nejmenší jedn. na fyz. úrovni, kt. je přenesena v 1 cyklu |
| Směrovací algoritmus | – směrovací relace R, která vrací množinu možných výstupních kanálů (tras) aka kudy můžu jít – výběrová funkce – vybírá tu nejvíc stylish cestu |
| Typy směrovacích algoritmů | – směrovací rozhodování = kdy a jak se dělá směrování – adaptivita = jsem schopen reagovat na změny – minimálnost = garance nejkratších cest – implementace směrovacích algoritmů |
| Typy směrovacího rozhodování | – distriubuované (inkrementální) = mám předchozí adresu a určuju jen příští adresu – zdrojové (all-at-once) směrování = od začátku nalinkuje cestu staticky (cesta je v hlavičce) ---křižovatkové (street-sign) = pokud v hlavičce není nic pro mě, pokračuje paket ve stejném směru jako přišel (nutno mít topologii, kde lze definovat přímý směr), výrazně kratší hlavička – hybridní (vícefázové) směrování = zdrojový uzel předpočítá mezilehlé uzly, ale ne všechny, distribuovaně se rozhoduje o detailech |
| Typy směrovacích alg. podle adaptivity | – deterministická – datově necitlivé = nedeterministická, necitlivé ke stavu sítě, náhodně/cyklicky – adaptivní = funkce, kt. má info o stavu sítě v okolí a na základě toho se rozhoduje, kam směruje, odhad/heuristika |
| Typy směrovacích alg. podle minimality | – minimální alg. (lačné/přímé...): náchylné k deadlocku, málo citlivé ke stavu sítě – neminimální alg.: mohou být adapt i necitlivé, netrpí zablokováním, ale paket se může poflakovat donekonečna (livelock), protože se může oddálit od cíle |
| Typy směrovacích alg. podle implementace | – konečný automat (HW automat, nejrychlejší) – směrovací tabulky: předpočítané tabulky N položek. statické/dynamické, velké paměťové nároky |
| Metrika časové složitosti komunikačních operací | – šířka kanálu w = velikost fitu – rychlost kanálu q = nejvyšší rychlost – přenosu po 1 fyz. vodiči – zpoždění kanálu \(t_m=1/q\) zpoždění mezi sousedními směrovací na 1 fit – startovní zpoždění \(t_s\) – směrovací zpoždění \(t_r\) = než se rozhodne, kam se posílá – přepínací rozhodnutí \(t_w\) = uvnitř směrovače přepnutí vstupů na výstupy – základní síťové zpoždění = čas od vstupu hlavičky do zdroj. směr. do výst. konce paketu z cíl. směr. – základní komun. zpoždění = zákl síť. zpož.+start. zpož. – celkové síťové zpoždění = zákl síť. zpož.+ zpož. způs. jinými komun. |
| Předpoklady modelu časové komunikační složitosti | \(\mu \) = velikost paketu (v [B]). \(\delta\) = délka přenosové trasy. Platí \(t_s\gg t_m\approx t_w\approx t_r\). Doba přenosu \(\mu \)-bytového paketu mezi 2 sousedními směrovači je \(\mu t_m\) (v [s]). Předpoklad: Směrovače mají vstupní i výstupní fronty. |
| Přepínání kanálů Circuit Switching CS | 1) zkonstruování fyzického obvodu – pošle se sonda, kt. má za úkol vybudovat cestu, rezervuje fyz. linky, po dosažení je odeslán potvrzovací flit 2) Přenos zprávy: trasa = rezervovaný HW obvod, plná přenosová rychlost, sonda se ukládá v každém směr, trasa funguje jako 1 vodič, neomezená délka zprávy – výhodné pro dlouhé a nečasté zprávy – uvolnění obvodu, např. posl. dat bity, cíl. uzlem |
| Základní komunikační zpoždění pro CS | Přenos zprávy délky \(\mu \) na vzdálenost \(\delta\) trvá čas \[ t_{\rm CS}(\mu,\delta)=t_s+\delta(t_r+(p+1)(t_w+t_m))+\mu t_m. \] Sonda potřebuje čas \(\delta(t_r+p(t_w+t_m))\), aby se dostala do cíle. Potvrzení putuje zpět čas \(\delta(t_w+t_m)\). Přenos dat trvá čas \(\mu t_m\). |
| Přepínání ulož-pošli-dál Store-and-Forward SF | – rozdělení do paketů pev. délky, pakety rozděleny na flity – směrovače mají buffer fronty pro celé pakety – každý paket je individuáln směrován ze zdroje do cíle – 1 krok, hop, zkopírování celého paketu z výstupní fronty do vstupní fronty – směrovací rozhodnutí probíhá až po té, co byl celá paket uložen ve vstupní frontě – výhodné pro krátké a časté zprávy |
| Základní komunikační zpoždění pro SF | Přenos paketu délky \(\mu\) na vzdálenost \(\delta\) trvá \[ t_{\rm SF}(\mu,\delta)=t_s+\delta(t_r+(t_w+t_m)\mu ). \] Každý směrovač musí nejprve učinit směrovací rozhodnutí a pak teprve celý paket přeskočí do dalšího směrovače, což trvá \(t_r+ (t_w+t_m)\mu \), a tento postup se opakuje \(\delta\) krát. Komunikační zpoždění je tedy úměrné součinu velikosti paketu a délky trasy. \(\implies\) požadavek na minimální směrování a malý průměr sítě. |
| Průřezové přepínání Virtual Cut-Through VCT | vesměs stejné jako SF, jen se směrovací rozhodnutí dělá v momentě, kdy je ve frontě první hlavička => prořízne do dalších směrovačů a postupuje dál, táhne za sebou zbytek – nedělá se pro něj už směrovací rozhodování a linka je blokovaná, dokud nedojde zbytek do cíle – pokud hlavička nemůže pokračovat, následující flity se postupně dotahují a kanály, které dosud obsazovaly, se postupně uvolňují ~ lokomotiva s vagony na gumičkách (c) Hardy |
| Základní komunikační zpoždění pro VCT | Paket délky \(\mu\) je přenesen na vzdálenost \(\delta\) v čase \[ t_{\rm VCT}(\mu,\delta)=t_s+\delta(t_r+t_w+t_m)+\mu \max(t_w,t_m). \] \(\delta(t_r+t_w+t_m)\): zpoždění hlavičky při provádění směr. rozhodnutí, přepínaní a přesunech mezi směr. \(\max(t_w,t_m)\): Rychlost přenosu řetězce flitů, jakmile hlavička dosáhne cíle, předpokládáme-li, že směrovače mají jak vstup. tak výst. fronty. – V případě pouze vstup. front nebo pouze výst. front by bylo \(t_w+t_m\) místo \(\max(t_w,t_m)\) |
| Červí přepínání Wormhole WH | Stejné jako VCT akorát, že směrovače nemají dostatečnou velikost front na uložení celého paketu, ale jen toho prvního flitu (mezi vagónky máme tyče :/) – když hlavička nemůže pokračovat, celá trasa zamrzne – náchylné k zablokování |
| Základní komunikační zpoždění pro WH | Totéž jako u VCT \[ t_{\rm WH}(\mu,\delta)=t_s+\delta(t_r+t_w+t_m)+\mu \max(t_w,t_m). \] |
| Zjednodušené výrazy pro komunikační zpoždění | Typické paralelní architektury: \(t_s\gg t_m\) \(t_m\approx t_w\approx t_r\) Zjednodušené výrazy: \( t_{\rm SF}(\mu,\delta)= t_s+\delta(t_r+(t_w+t_m)\mu ) \doteq t_s+\delta\mu t_m \) \(\implies\) SF je citlivé na vzdálenost. \( t_{\rm CS}(\mu,\delta) \doteq t_{\rm VCT}(\mu,\delta)=t_{\rm WH}(\mu,\delta)\doteq t_s+\delta t_d+\mu t_m,\) kde \(t_d=t_r+t_w+t_m\) \(\implies\) CS, VCT a WH jsou necitlivé na vzdálenost Pro velká \(\mu\) (řádově stovky flitů) je \(\mu t_m\gg \delta t_d\) ve většině paralelních strojů. |
| Řešení problému zablokování | – detekce a zotavení (problémové) – prevence: malé využití prostředků => CS – vyhnutí se zablokování: postupné přidělování prostředků tak, aby globálně nemohlo k zabl. dojít |
| Vyhnutí se zablokování – graf kanálových závislostí | – máme deterministickou fci R na grafu G, která jednoznačně přiřadí ze vstupního kanálu a uzlu jeho cílový uzel – vyrobíme graf kanálových závislostí (větší než původní) a pokud je acyklický, tak jsme vyhráli, pokud není – zkoušíme odstraňovat hrany, tak aby byla zachována silná souvislost (orient. graf) a zmizly všechny kružnice, pokud to jde, vyhráli jsme – omezili jsme možnosti směrovací fce R – př. XY směrování |
| Vyhnutí se zablokování – nepravidelné sítě: algoritmy typu Nahoru*/Dolu* | 1) zkonstruuj kostru do šířky s kořenem r 2) vezmi každou hranu a a) různá hloubka uzlů – orientuj směrem ke kořenu b) stejná hloubka – očísluj všechny uzly jedinečným ID a orientuj k uzlu s menším ID legální trasy směrování sestávají z: 0 nebo více hran ve směru orient. G' – následovaných 0 nebo víc v opačném směru orien. G' – obecně vede na delší cesty |
| Zablokování v toroidech | Nutná podpora HW na vytvoření virtuálního kanálu – jeden uzel obsluhuje nezávisle na sobě až 2 komunikace – zdvojení kružnice a rozdělení na spirálu, která má začátek a konec - acykl., směrovací funkce určuje pohyb po spirále |
Want to create your own Flashcards for free with GoConqr? Learn more.