PAR6

Question 1

zprava

Answer 1

jednotka komunikace z hlediska programu; promenna delka

Question 2

paket

Answer 2

jednotka komunikace se smerovaci informaci pevne delky – sklada se z flitu

Question 3

flit

Answer 3

jednotka komunikace na linkove vrstve

Question 4

fit

Answer 4

nejmensi jednotka komunikace na fyzicke urovni

Question 5

Deterministicka smerovaci funkce

Answer 5

Deterministicka smerovaci funkce R na grafu G: pro každý vstupni uzel u z V(G); pro každý jeho vstupni kanal c1 a pro každý cilovy uzel d; smerovaci funkce R urci vystupni kanal c2 = R(u;c1;d)

Question 6

Graf kanalovych zavislosti Z = Z(G;R)

Answer 6

1)uzly V(Z) = kanaly Ci site G; 2) lezi E(Z) prave tehdy; když R muze v G smerovat paket z kanalu C1 na kanal C2

Question 7

Legalni orientovane trasy

Answer 7

Uvazujme souvisly graf G a jeho korektni digraf G’. Pak legalni orientovane trasy pro smerovaci fci R’ Nahoru/Dolu v G’ jsou pouze takove; které se sestavaji 1)z 0 nebo vice hran ve smeru orientace G’ 2)nasledovanych 0 nebo vice v opacnem smeru orientace G’

Question 8

Striktne klesajici poradi

Answer 8

R’d = smerovaci fce; která pouziva virtualni decr kanaly v striktne klesajicim poradi a virtualni incr kanaly v stritkne rostoucim poradi

Question 9

architektura smerovace

Answer 9

vnitřní vstupní (injekční) a výstupní (ejekční) kanály - na sběrnici; vnější vstupní a výstupní kanály

Question 10

prepinac smerovace

Answer 10

přepínač propojuje vstupní kanály na výstupní

Question 11

smerovaci alg (z ceho se sklada)

Answer 11

a)smerovaci relace R; která vraci mnozinu moznych vystupnich kanalu (tras) b)vyberove funkce p; která z teto mnoziny vybira 1 polozku

Question 12

smerovaci rozhodnuti

Answer 12

distribuované (inkrementální) směrování - směrovače počítají z cílových adres v hlavičkách;;zdrojové - zdrojový uzel určí úplnou trasu; směrovač jen čte a zkracuje řetěz tranzitních adres;;- křižovatkové pro mřížky/toroidy - hlavička = směrovka + adresa jejího uzlu;;hybridní (vícefázové) - zdroj předpočítá mezilehlé uzly; přesné mezitrasy dělají směrovače;;

Question 13

adaptivita

Answer 13

žádná; pseudo; plná;;deterministické směr. alg. - pořád ta samá trasa pro danou dvojici zdroje a cile;;datově necitlivé - výběrová fce necitlivá ke stavu sítě; výběr volných kanálů náhodně/cyklicky;;adaptivní - snaha vybrat nejméně zahlcený směr (+ bez poruch);; - používá info o stavu kanálů (délky front; historie atp.);;používá se distribuované adaptivní směrování;;

Question 14

Minimalita – minimalni

Answer 14

po nejkr. trase;;každé směrovací rozhodnutí přivádí paket blíže k cíli;;hrozí deadlock;;např. deterministické; datově necitlivé;;

Question 15

Minimalita – neminimalni

Answer 15

obcházecí;;paket může být poslán dále od cíle;;hrozí livelock;;např. plně adaptivní;;

Question 16

Deadlock = staticke zablikovani

Answer 16

cyklus závislostí na prostředcích (řetěz požadavků);;efekt sněhové koule: deadlock se šíří čím je větší; kdykoli agent (-paket) potřebuje prostředek (-kanál) z tohoto cyklu; je automaticky zablokován také;;

Question 17

reseni deadlocku

Answer 17

• detekce a zotavení: teprve až se to po** tak se něco dělá; síť je potřeba zotavit;;- prevence: konzervativní přidělování všech prostředků najednou; jejich malé využití; např. v CS;;- vyhnutí se zablokování: postupné přidělování; vždy po každém přidělení musí být deadlock vyloučen;;

Question 18

Korektni graf:

Answer 18

Souvisly graf je korektni; pokud lze uvalenim orientace na jeho hrany zkonstruovat graf G’ ktery ma pouze 1 koren a je acyklicky (neexistuji orientovane kruznice)