32 - Základní architektury přepínačů, algoritmy pro plánování, řešení blokování, vícestupňové přepínací sítě Flashcards
Obecná architektura přepínače
Základní části přepínače:
- Vstupní rozhraní (fabric input interface) - propojuje vstupní modul a přepínací logiku, rozděluje pakety na buňky pevné délky pro přepínání a posílá data na přepínací logiku podle plánovače
- Vstupní buffer (fabric input buffers) - ukládá příchozí data pokud je nelze poslat do přepínací logiky
- Přepínací logika (switch fabric, též backplane) - síťová topologie, kde uzly sítě jsou spojeny každý s každým pomocí jednoho či více přepínacích obvodů
- Plánovač (scheduler) - plánuje přepínání dat ze vstupu na výstup
- Výstupní rozhraní (fabric output interface)
- Výstupní buffer (fabric output buffers)
Požadavky na přepínače a problémy přepínání
Požadavky na přepínače
- Maximální přenos dat přepínací logikou
- Paralelní přenosy mezi různými rozhraními
- Spravedlivé přidělování šířky pásma
- Zachování pořadí paketů
Problémy
- vnitřní blokování
- soutěžení o porty
- blokování fronty (HOL - head of line)
- přenos multicastu
Metriky pro měření činnosti přepínače
Propustnost - přenesená data za jednotku času (bps / pps)
latence - “zpoždění” - doba přenosu paketu ze vstupního na výstupní rozhraní (s)
počet dostupných cest - počet možných cest v přepínací logice které propojují každou dvojici vstupních a výstupních portů
Architektury přepínačů ->
Přepínače se sdílenou propojovací deskou (shared backplane) ->
Přepínače se sdílenou sběrnicí (shared bus)
- Sdílené přenosové médium – řídící a datové linky
- Bus protocol – řídí přenos po sběrnici
- Potřebná propustnost sběrnice R x N - Vhodné pro zařízení s propustností kolem 1 Gb/s
Šířka sběrnice w = (R x N)/r
- R – rychlost na portu
- N – počet portů
- r – taktovací frekvence sběrnice
- Nativní implementace přenosů broadcast/multicast
- Pouze jeden port může v daný okamžik komunikovat
- S počtem portů rose šířka sběrnice
16 portů, rychlost 100 Mb/s, frekvence 40 MHz
propustnost RxN = 16x100 -> 1,6 Gb/s
šířka sběrnice 100x16/40 -> 40 bitů
Architektury přepínačů ->
Přepínače s přepínanou propojovací deskou (shared backplane), scheduler
- Paralelní přenos paketů
- Buňky pevné délky
- Přenos buněk ve fixních časových intervalech (time slots)
- Potřeba plánování přepínání - plánovač (scheduler) ->
- Detekce buněk na vstupu > Plánování přenosu -> Přenos buněk
Scheduler
- řeší problém párování portů, vnitřní blokování a virtuální fronty
- algoritmy pro přidělování - lístků, PIM, iSLIP (round-robin)
Jednostupňové - přepínače se sdílenou pamětí / křížový přepínač
Vícestupňové - Closova síť, Benešova síť, síť Torus
Architektury přepínačů ->
Přepínače s přepínanou propojovací deskou (shared backplane) ->
Jednostupňové přepínání ->
přepínač se sdílenou pamětí
- Centrální paměť mezi vstupy a výstupy
Pakety uloženy po příchodu do sdílené paměti
Paměť (pevná X proměnná velikost) rozdělena do front příslušejících k výstupům
Rychlost při přístupu do paměti (Šířka pásma paměti)
- BW = 2 x N x R (simultánní čtení a zápis)
Doba zápisu/ čtení buňky t = C / (2xNxR), - C – velikost buňky paměti - R – rychlost na portu - N – počet portů
Architektury přepínačů ->
Přepínače s přepínanou propojovací deskou (shared backplane) ->
Jednostupňové přepínání ->
Křížový přepínač (crossbar)
- N^2 propojení (crosspoints) - dvoustavové chování: on/off (např. tranzistory)
- Interně neblokující -> možnost paralelních přenosů (Více propojení aktivních v daném časovém slotu)
- lze přepojit všechny vstupy a výstupy
- Nativní podpora multicastu
- Možnost kolizí - více vstupů požaduje jeden výstup
Centrální plánovač
- řídí propojení (crosspoints) pomocí řídící linky
- nastavuje konfiguraci přepínače podle požadavků na vstupu
Nevýhody
- Rozšiřitelnost – kvadratická složitost O(N2)
- Obtížné garantovat kvalitu služby QoS - souběžné požadavky z více vstupů na jeden výstup
Chybí redundance (pouze jedna cesta mezi vstupem a výstupem)
Plánovací algoritmy a blokování
Největší párování (maximum matching) - Párování, které obsahuje největší možný počet hran (každý s každým - Globálně optimální, největší propustnost)
Maximální párování (maximal matching) - Párování, ke kterému nelze přiřadit další hranu, aniž bychom zvýšili stupeň některého z uzlů na 2 - Lokální maximum
Problém plánování je biparitní graf, uzly jsou množina vstupních X výstupních portů, hrany množina propojení
Plánovací algoritmy a blokování - Algoritmus přidělování lístků
- Žádost o lístek (Request) - Vstupní port P pošle po řídící sběrnici požadavek na výstupní port Q
- Přidělení pořadí (Grant) - Port Q vrátí P lístek TQX s přiděleným pořadovým číslem X.
- Propojení a přenos (Connect & Transfer)
- Výstupní port Q umístí na řídící sběrnici aktuální číslo TQX – broadcast.
- Q nastaví příslušný propojovací tranzistor do stavu zapnuto.
- Vstupní port P zapíše data na datovou sběrnici.
Výhody:
- Umožňuje asynchronní zpracování
- Přenos rámců variabilní velikosti
Nevýhody:
- Blokování na začátku fronty (HOL) – menší propustnost (první buňka v pořadí blokuje, blokované buňky čekají i když je cílový port dostupný)
- Nezávislé přidělování lístků – problém s multicastem
Plánovací algoritmy a blokování - Algoritmus PIM (Parallel Iterative Matching)
- Podobné jako přidělování lístků
- využívá virtuální fronty (VOQ)
- Virtuální výstupní fronty VOQ (virtual output queues) – řešení HOL
- Rozdělení vstupní fronty na portu do více front (Pro každý výstupní port)
- celkově potřeujeme N^2 front
- hledá největší párování pomocí NÁHODNÉHO VÝBĚRU výběru
Žádost o port - Vstupní port P posílá žádosti na všechny žádané porty
Udělení portu - Výstupní port Q přidělí port - V případě více žádostí o přístup, NÁHODNĚ vybere jednu.
Přijetí a přenos - Vstupní port P zpracuje došlé udělení portů - V případě povolení více přenosů, NÁHODNĚ vybere jeden
1 iterace - Propustnost cca 63%
možné vylepšení pomocí více iterací (např. dvě iterace cca 75% propustnost)
Nalezení největšího párování (nejhůře N iterací - všechny vstupy na jeden výstup, nejlépe 1 iterace (každý vstup na jiný výstup), orůměr logN
Plánovací algoritmy a blokování - Algoritmus iSLIP
- využívá virtuální fronty (VOQ)
- deterministická obsluha (vs náhodná u PIMú, propustnost 75%
- Při soupeření o port používá rotující ukazatele
- Po každé iteraci se inkrementují ukazatele
Ii – ukazatel na vstupním portu i
Oj – ukazatel na výstupním portu j
- Žádost - každý port zašle žádost na každý výstupní port
- Přidělení - pokud výstupní port Y dostane více žádostí, vybere tu, která má číslo portu ≥ Oj - pokud je jich více, vybere se ta s nejmenší hodnotou
- Přijetí - pokud vstupní port X obdrží více povolení, vybere ten port, který je ≥ Ii - pokud je jich více, vybere se ta s nejmenší hodnotou
Architektury přepínačů ->
Přepínače s přepínanou propojovací deskou (shared backplane) ->
Vícestupňové přepínání (Rozšiřitelné architektury pro velké množství portů) - porovnání s jednostupňovým
Jednostupňové
- např křížový přepínač, problém s kvadratickým nárůstem portů,
- HOL blokování
- vyžaduje algoritmy pro hledání maximálního párování
- je možné zvětšit počet portů anož by se nafouklo přepínací pole?
Vícestupňové
- vstup -> více přepínacích obvodů -> výstup
- bez HOL
- algoritmy pro hledání interního bezkonfliktního propojení
Architektury přepínačů ->
Přepínače s přepínanou propojovací deskou (shared backplane) ->
Vícestupňové přepínání (Rozšiřitelné architektury pro velké množství portů)->
Přepínací síť Clos (m,n,r)
(m,n,r)
m - různých cest mezi vstupním a výstupním portem (počet přepínačů uvnitř té přepínací sítě)
n - vstupů v jedné jednotce
r - počet vstupních přepínačů (v tom co jsi uvedl 2) a taky typ přepínače uvnitř té přepínačí sítě (tedy v tom co jsi uvedl to je 2x2)
Např. Clos(7,4,2)
- > 7 různých cest mezi porty = 7 prostředních přepínačú typu 2x2
- > 4 vstupy v jednom vstupním a výstupním přepínači (4x7 & 7x4)
- > 2 vstupní přepínače
Closův teorém: pokud platí m >= 2n - 1 pak lze přidat nové propojení vstupu a výstupu bez přeskládání - síť je tak neblokující
- přepínač o 256 portech vyžaduje síť (31, 16, 16) -> drahé - modifikované řešení - m >= n - není již neblokující, ale levnější (je neblokující PO PŘESKLÁDÁNÍ - využívá se barvení hran)
Třístupňová přepínací síť - využívá křížové přepínače
- První stupeň – rozdělí n-vstupů na menší skupiny
- Prostřední stupeň – propojí každý vstupní a výstupní přepínač.
- > m-různých cest mezi daným vstupním a výstupním portem
Architektury přepínačů ->
Přepínače s přepínanou propojovací deskou (shared backplane) ->
Vícestupňové přepínání (Rozšiřitelné architektury pro velké množství portů)->
Přepínací síť Beneš, BNn
- Modifikovaná síť Clos(2,2,1) s přeskládáním
- Hierarchicky rekurzivní konstrukce!!
- Počet vstupů: N=2^n
- Blok N/2-vstupních přepínačů 2x2
- Prostřední část rekurzivních bloků BN(n-1)
- Blok N/2-výstupních přepínačů 2x2
- Počet bloků (stupňů): 2 log2 N – 1
Beneš BN3 -> N = 2^3 = 8 vstupů (4 přepínače na vstupu a výstupu), 5 stupňů (sloupců)
Architektury přepínačů ->
Přepínače s přepínanou propojovací deskou (shared backplane) ->
Vícestupňové přepínání (Rozšiřitelné architektury pro velké množství portů)->
Přepínací síť Torus
Decentralizované přímé přepínání
- Každý uzel slouží jako vstup, výstup i přepínací uzel (přímá síť)
- n-dimenzionální síť uzlů ki s adresou (a1,a2, …, an)
- Každý uzel ki připojen dvěma cestami v každé dimenzi
existuje víc cest mezi uzly - síť torus 8 x 8 x 8: 90 cest přes 6 uzlů
