PAR9

Question 1

Úplná permutace

Answer 1

Každý uzel vyšle a přijme právě 1 paket.

Question 2

Neúplná permutace

Answer 2

Každý uzel vyšle nebo přijme nejvýše 1 paket.

Question 3

Náhodná permutace

Answer 3

Každý procesor si volí náhodně 1 cíl → 1 uzel se může stát cílem pro více než 1 paket.

Question 4

On-line směrování

Answer 4

Permutace není globálně známá; každý procesor zná pouze svůj paket.

Question 5

Off-line směrování

Answer 5

Permutace je známá dopředu; protože se provádí jedna a tatáž opakovaně → vyplatí se předpočítat si časově anebo paměťově optimální směrování.

Question 6

Zhušťovací (packing) neúplná permutace

Answer 6

Směřování paketů z libovolné podmnožiny vstupů M do prvních m=|M|výstupních uzlů tak, že relativní pořadí paketů se nezmění. Relativní pořadí paketů můžeme vypočítat pomocí PPS. Opakem zhušťování je zřeďování.

Question 7

Monotónní permutace

Answer 7

Monotónní permutace je každá permutace, kde nedochází ke změně pořadí paketů mezi vstupy a výstupy. Libovolná monotónní permutace je složením zhušťovací a zřeďovací permutace.