Zavřít síť

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. června 2021; kontroly vyžadují 4 úpravy .

Kloz network (někdy Klos network ) je typ vícestupňové (jiné terminologie - vícevrstvá [1] ) přepínací sítě , kterou poprvé formálně popsal Charles Kloz v roce 1953 [2] . Taková síť je teoretickou verzí praktického vícestupňového telefonního spojovacího systému.

Obecný popis

Síť Klose má tři kaskády (vrstvy): vstupní kaskádu, střední (střední) kaskádu a výstupní kaskádu. Každá kaskáda se skládá z řady křížových spínačů – tzv. "příčníky", nebo v jiné terminologii spínací prvky (CE) [3] [4] , jak je znázorněno na obrázku níže.

Každé volání (žádost o spojení) zasáhne příchozí CI, načež může být směrováno přes jakoukoli dostupnou střední vrstvu CI na odpovídající odchozí CI. V tomto případě je střední vrstva CE k dispozici pro nové volání, pokud je volná jak linka spojující ji s příchozím CE, tak linka spojující ji s odchozím CE.

Klíčovou výhodou blízkých sítí je, že mají mnohem menší počet spínacích bodů ve srovnání s kříženým přepínačem. V praktickém smyslu byla síť Klose velmi přínosná pro implementaci v elektromechanických telefonních ústřednách, ale s příchodem VLSI její hodnota klesla, i když její principy byly využity i v digitálních rychlých paketových přepínačích, například v přepínači ATOM společnosti NEC [5 ] [6] .

Kloseova síť je definována třemi celými čísly n , ma r . Počet n se rovná počtu linek připojených ke každému z r CE příchozího stupně. Každý CE vstupního stupně má m výstupů a střední stupeň také obsahuje m CE. Rozměr CE vstupního stupně tedy bude n x m , tj. n vstupů a m výstupů. Mezi každým příchozím stupněm CI a každým středním stupněm CI je přesně jedno spojení a totéž platí pro spojení ze středního stupně do odchozího stupně. Odchozí (třetí) kaskáda obsahuje r CE, z nichž každý má rozměr m x n .

Pravděpodobnosti blokování

Pravděpodobnosti zablokování sítě Clos jsou určeny relativními hodnotami ma n .

Přísně neblokující Klozovy sítě ( m ≥ 2 n - 1) - Klozova původní derivace z roku 1953

Pokud m ≥ 2 n - 1, pak je síť Clos striktně neblokující v tom smyslu, že volný vstup příchozího SP lze vždy propojit s volným výstupem odchozího SP bez nutnosti přepojování stávajících spojení. Tento závěr tvoří základ Kloseovy klasické práce z roku 1953 . Předpokládejme, že na příchozím CI je nečinná linka, která musí být připojena k nečinné lince na konkrétním odchozím CI. V nejhorším případě již příchozí CI obsluhuje n - 1 spojení, totéž lze říci o odchozím CI, tedy že obsluhuje n - 1 spojení. Předpokládejme, také pro nejhorší případ, že každé z těchto spojení prochází jiným středním FE. Proto v nejhorším případě není 2 n - 2 FE střední vrstvy schopno navázat nové spojení. Aby tedy byla síť Clos striktně neblokující, je potřeba ještě jeden FE střední vrstvy a jejich celkový počet by měl být 2 n - 1.

Uzavírací sítě, které jsou neblokující v rámci rekomutace ( m ≥ n )

Je-li m ≥ n , pak se síť Clos nazývá „neblokující při rekomutacích“. To znamená, že volný port vstupu CE lze vždy propojit s volným portem výstupního CE, ale k tomu může být nutné přepnout stávající spojení vytvořením přes jiné CE centrálního (středního) kaskáda Close network [7] .

K prokázání tohoto bodu postačí uvažovat případ s m = n , kdy je síť Clos plně zapojena, to znamená, že je obsluhováno r × n spojení. Důkaz ukazuje, jak lze jakoukoliv permutaci r × n vstupních linek pro r × n výstupních linek rozložit na menší permutace, z nichž každá může být implementována samostatným FE v síti Clos, kde m = n .

Důkaz využívá Hallův teorém [8] , nazývaný „manželský teorém“, kvůli jeho vysvětlení se zapojením „chlapců“ a „dívek“. Předpokládá se tedy, že je r chlapců a r dívek. Věta říká, že pokud v podmnožině k chlapců (pro každé k , tedy 0 ≤ k ≤ r ) každý chlapec zná k nebo více dívek, pak si každý chlapec může vzít dívku, kterou zná. Je jasné, že je to nutná podmínka k uzavření manželství a kupodivu to stačí.

V kontextu sítě Klose je každý chlapec příchozí FE a každá dívka je odcházející FE. Říká se, že chlapec zná dívku, když příchozí a odchozí KI obsluhují stejné spojení. Každá sada k chlapců musí znát alespoň k dívek, protože k příchozích FE obsluhuje k × n spojení a vyžaduje alespoň k odchozích FE, aby je obsluhovaly. Odtud bude každá příchozí CI spárována s odchozí CI, která obsluhuje stejné připojení typu one-to-one. Tato r připojení mohou být obsluhována jednou střední vrstvou CI. Pokud nyní odstraníme tento FE střední úrovně ze sítě Clos, pak se m sníží o 1 a máme menší síť Clos. Poté se proces znovu opakuje, dokud se m nerovná 1 a každé spojení je obsluhováno CE středního stupně.

Pravděpodobnosti blokování - Leeova a Jacobeova aproximace

Reálné telefonní přepínací systémy jsou zřídkakdy striktně neblokující kvůli vysokým nákladům na jejich implementaci, obvykle mají nízkou pravděpodobnost blokování, kterou lze vypočítat pomocí Leeovy nebo Jacobeovy aproximace [9] , za předpokladu, že nedojde k přepnutí stávajících spojení. V tomto případě bude potenciální počet dalších aktivních spojení v každém vstupním nebo výstupním spínači u = n - 1.

Leeova aproximace předpokládá, že každá vnitřní přímka mezi stupni je již obsazena spojením s pravděpodobností p a že tato přímka je zcela nezávislá na ostatních liniích. V tomto případě bude pravděpodobnost zablokování nadhodnocena, zejména pro malé r . Pravděpodobnost, že je daná pobočka obsazena, je p = uq / m , kde q se rovná pravděpodobnosti, že je buď příchozí nebo odchozí linka obsazena. Naopak pravděpodobnost, že je čára volná, je 1 - p . Pravděpodobnost, že cesta spojující příchozí FE s odchozí FE přes střední vrstvu FE je volná, je rovna pravděpodobnosti, že jsou obě linky volné, konkrétně (1 - p ) 2 . V důsledku toho bude pravděpodobnost jeho nedostupnosti 1 - (1 - p ) 2 . Pravděpodobnost zablokování neboli pravděpodobnost, že takové volné cesty neexistují, je pak [1 - (1 - p ) 2 ] m .

Jacobeusova aproximace je přesnější a abychom ukázali, jak je odvozena, předpokládejme, že střední fáze CE již obsluhují určitý počet volání. To odráží skutečnost, že záleží pouze na „relativních“ konfiguracích příchozích a odchozích CI. Existuje i spojení vstupujících do sítě přes stejný příchozí CE a pro jejich obsluhu musí být přiděleny volné linky a existuje j spojení opouštějících síť Clos přes stejný odchozí CE a k jejich obsluze musí být také použity volné linky. . Proto 0 ≤ i ≤ u a 0 ≤ j ≤ u .

Nechť A se rovná počtu způsobů přepínání pro j spojení odcházejících do m CE střední vrstvy. Nechť B se rovná počtu těchto způsobů přepínání, který je vyjádřen v blokování. To se rovná počtu případů, ve kterých zbývajících m - j CE středního stupně odpovídá m - j z i příchozích spojení, což je počet podmnožin obsahujících m - j těchto spojení. Pak bude pravděpodobnost blokování:

\beta _{ij}={\frac {B}{A}}={\frac {\left({\begin{array}{c}i\\mj\end{array}}\right) }{\left({\begin{array}{c}m\\j\end{array}}\right)}}={\frac {i!j!}{(i+jm)!m!)} }

Pokud f i je pravděpodobnost, že i další spojení jsou již obsluhována příchozím CI, a g j se rovná pravděpodobnosti, že j dalších spojení jsou již obsluhována odchozím CI, pak je celková pravděpodobnost blokování:

{\displaystyle P_{B}=\sum _{i=0}^{u}\sum _{j=0}^{u}f_{i}g_{j}\beta _{ij))

Lze jej vypočítat pomocí veličin f i a g j , z nichž každá má binomické rozdělení . Po algebraických transformacích lze pravděpodobnost blokování vyjádřit jako:

P_{B}={\frac {(u!)^{2}(2-q)^{2u-m}q^{m}}{m!(2u-m)!}}

Uzavřete sítě s více než třemi kaskádami

Síť Klose může být postavena z libovolného počtu lichých kaskád. Nahrazením každé centrální vrstvy FE 3-kaskádovou sítí Clos získáme 5-kaskádovou síť Clos. Opakováním tohoto procesu můžete získat sítě Clos skládající se ze 7, 9, 11 atd. kaskád.

Benešova síť ( m = n =2)

Neblokující síť tohoto typu za rekomutací, kde m = n = 2, se obecně nazývá „Beneshova síť “ a dokonce i ty sítě, které byly analyzovány a diskutovány před ním. Počet vstupů a výstupů takové sítě je N = r × n = 2 r . Takové sítě mají kaskády, z nichž každá se skládá z N /2 2×2 FE. Následující ukazuje Benešovu síť 8×8 (tj. kde N = 8); má 5 stupňů, z nichž každý obsahuje N /2 = 4 2×2 FE, celkem tedy 20 2×2 FE. Tři centrální kaskády se skládají ze dvou menších sítí Benes 4×4, zatímco v centrální kaskádě lze každou z 2×2 FE považovat za síť 2×2 Benes. Tento příklad ukazuje rekurzivní složku sítí tohoto typu. $2log_{2}N-1$ $2log_{8}N-1=$ $Nlog_{2}NN/2=$

Literatura

Podlazov V.S., Sokolov V.V. Generalized Kloz networks // Automatizace a telemechanika, ed. Academizdattsentr "Science" RAS. - 2009. - č. 10 . - S. 158-171 . — ISSN 0005-2310 . (Ruština)

Poznámky

↑ V. P. Vidomenko, „Kloz Networks 40 Years Later“, 2. konference „Information Networks and Systems (KISS-93)“, 18.-20. listopadu 1993, Abstracts, State. Univerzita telekomunikací (GUT) im. prof. M. A. Bonch-Bruevich , St. Petersburg, 1993, str. 42-44;
↑ Clos, Charles. Studie neblokujících přepínacích sítí // Bell Labs Technical Journal : deník. - 1953. - březen ( roč. 32 , č. 2 ). - str. 406-424 . — ISSN 00058580 . Archivováno z originálu 14. března 2012.
↑ Razhivin Igor. Telekomunikační výkladový slovník "Digital Wireline Telecommunications for Open Systems": Digital Wireline telekomunikace na otevřených systémech (OSI). (2003). — Zahrnuje mimo jiné technologii ATM. Získáno 8. července 2012. Archivováno z originálu 3. ledna 2012. (Ruština)
↑ A. N. Nazarov, I. A. Razzhivin, M. V. Simonov. ATM: Technická řešení pro síťové propojení. — Referenční vydání. - M . : Hot Line - Telecom, 2001. - S. 376. - ISBN 5-93517-040-X .
↑ Principy návrhu přepínačů . Kunegin Sergej Vladimirovič. Získáno 8. července 2012. Archivováno z originálu 30. května 2008. (Ruština)
↑ Architektura přepínače výstupní vyrovnávací paměti pro asynchronní přenosový režim, Suzuki, H.; Nagano, H.; Suzuki, T.; Takeuchi, T.; Iwasaki, S. ICC '89, BOSTONICC. záznam konference. (anglicky) . IEEE Xplore, digitální knihovna. Získáno 8. července 2012. Archivováno z originálu dne 7. října 2012.
↑ Václav E. Beneš, "Matematická teorie propojování sítí a telefonního provozu", Academic Press , 1965.
↑ Philip Hall. O zástupcích podmnožin // Journal of the London Mathematical Society. - 1935. - T. 10 . - S. 26-30 . - doi : 10.1112/jlms/s1-10.37.26 .
↑ Hui, JY: "Switching and Traffic Theory for Integrated Broadband Networks", Kluwer Academic Publishers, 1990.