Închideți rețeaua

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 10 iunie 2021; verificările necesită 4 modificări .

Rețeaua Kloz (uneori rețea Klos ) este un tip de rețea de comutare cu mai multe etape (în altă terminologie - multi-nivel [1] ) , descrisă pentru prima dată oficial de Charles Kloz în 1953 [2] . O astfel de rețea este o versiune teoretică a unui sistem practic de comutare telefonică în mai multe etape.

Descriere generală

Rețeaua Klose are trei cascade (niveluri): o cascadă de intrare, o cascadă intermediară (de mijloc) și o cascadă de ieșire. Fiecare cascadă constă dintr-un număr de comutatoare încrucișate - așa-numitele. „bare transversale” sau, în altă terminologie, elemente de comutare (CE) [3] [4] , după cum se arată în figura de mai jos.

Fiecare apel (cerere de conectare) atinge un CI de intrare, după care poate fi direcționat prin orice CI disponibil de nivel mediu către CI de ieșire corespunzător. În acest caz, CE de nivel mediu este disponibil pentru un nou apel dacă atât linia care îl conectează cu CE de intrare, cât și linia care îl conectează cu CE de ieșire sunt libere.

Avantajul cheie al rețelelor Close este că au un număr mult mai mic de puncte de comutare în comparație cu un comutator încrucișat. În sens practic, rețeaua Klose a fost foarte benefică pentru implementarea în centralele telefonice electromecanice, dar odată cu apariția VLSI, valoarea acesteia a scăzut, deși principiile sale au fost folosite și în comutatoarele digitale rapide de pachete, de exemplu, în comutatorul ATOM al NEC [5] ] [6] .

O rețea Klose este definită de trei numere întregi n , m și r . Numărul n este egal cu numărul de linii conectate la fiecare dintre r CE-urile etapei de intrare. Fiecare CE al etapei de intrare are m ieșiri, iar etapa de mijloc conține, de asemenea, m CE. Astfel, dimensiunea CE a etapei de intrare va fi n x m , adică n intrări și m ieșiri. Există exact o conexiune între fiecare etapă CI de intrare și fiecare CI treaptă de mijloc și același lucru este valabil și pentru conexiunile de la etapa de mijloc la etapa de ieșire. Cascada de ieșire (a treia) conține r CE, fiecare dintre ele având dimensiunea m x n .

Probabilități de blocare

Probabilitățile de blocare a rețelei Clos sunt determinate de valorile relative ale lui m și n .

Rețele Kloz strict neblocante ( m ≥ 2 n - 1) - Derivarea originală a lui Kloz din 1953

Dacă m ≥ 2 n - 1, atunci rețeaua Clos este strict neblocantă, în sensul că intrarea liberă a SP de intrare poate fi întotdeauna conectată la ieșirea liberă a SP de ieșire, fără a fi nevoie de a restabili conexiunile existente. Această concluzie formează baza lucrării clasice din 1953 a lui Klose . Să presupunem că există o linie inactivă pe un CI de intrare care trebuie să fie conectată la o linie inactivă pe un anumit CI de ieșire. În cel mai rău caz, CI de intrare deservește deja n - 1 conexiuni, același lucru se poate spune despre CI de ieșire, adică că deservește n - 1 conexiuni. Să presupunem, de asemenea, în cel mai rău caz, că fiecare dintre aceste conexiuni trece printr-un FE de nivel mediu diferit. Prin urmare, în cel mai rău caz, 2 n - 2 FE de nivel mediu nu sunt capabile să stabilească o nouă conexiune. Astfel, pentru ca rețeaua Clos să fie strict neblocantă, este necesară încă o FE de nivel mediu, iar numărul lor total ar trebui să fie 2 n - 1.

Rețele Clos care sunt neblocante sub recomutații ( m ≥ n )

Dacă m ≥ n , atunci rețeaua Clos se numește „neblocare sub recomutații”. Aceasta înseamnă că portul liber al CE de intrare poate fi întotdeauna conectat la portul liber al CE de ieșire, dar pentru aceasta, poate fi necesară re-comutarea conexiunilor existente prin stabilirea lor prin alte CE ale centralei (de mijloc) cascada rețelei Close [7] .

Pentru a demonstra acest punct, este suficient să luăm în considerare cazul cu m = n , când rețeaua Clos este complet implicată, adică r × n conexiuni sunt deservite. Dovada arată cum orice permutare a r × n linii de intrare pentru r × n linii de ieșire poate fi împărțită în permutări mai mici, fiecare dintre acestea putând fi implementată de un FE separat în rețeaua Clos, unde m = n .

Demonstrarea folosește teorema lui Hall [8] , numită „teorema căsătoriei”, datorită explicației sale cu implicarea „băieților” și „fetelor”. Astfel, se presupune că există r băieți și r fete. Teorema afirmă că dacă într-o submulțime de k băieți (pentru fiecare k , deci 0 ≤ k ≤ r ) fiecare băiat cunoaște k sau mai multe fete, atunci fiecare băiat se poate căsători cu fata pe care o cunoaște. Este clar că aceasta este o condiție necesară pentru ca o căsătorie să aibă loc și, în mod surprinzător, este suficient.

În contextul rețelei Klose, fiecare băiat este un FE care vine, iar fiecare fată este un FE care iese. Se spune că un băiat cunoaște o fată atunci când CI de intrare și de ieșire servesc aceeași conexiune. Fiecare set de k băieți trebuie să fie familiarizat cu cel puțin k fete, deoarece k FE de intrare deservesc k × n conexiuni și necesită cel puțin k FE de ieșire pentru a le deservi. De aici, fiecare CI de intrare va fi asociat cu un CI de ieșire care servește aceeași conexiune unu-la-unu. Aceste conexiuni r pot fi deservite de un CI de nivel mediu. Dacă acum eliminăm acest FE de nivel mediu din rețeaua Clos, atunci m scade cu 1 și avem o rețea Clos mai mică. Apoi procesul se repetă din nou până când m devine egal cu 1 și fiecare conexiune este deservită de CE-ul etapei de mijloc.

Probabilități de blocare - aproximări Lee și Jacobeus

Sistemele reale de comutare telefonică sunt rareori strict neblocante din cauza costului ridicat al implementării lor, ele au, de obicei, o probabilitate de blocare scăzută, care poate fi calculată folosind aproximațiile Lee sau Jacobeus [9] , cu condiția ca conexiunile existente să nu fie resmutate. În acest caz, numărul potențial al altor conexiuni active în fiecare comutator de intrare sau ieșire va fi u = n - 1.

Aproximația Lee presupune că fiecare linie internă dintre etape este deja ocupată de o conexiune cu probabilitatea p și că această linie este complet independentă de celelalte linii. În acest caz, probabilitatea de blocare va fi supraestimată, în special pentru r mic . Probabilitatea ca o anumită extensie să fie ocupată este p = uq / m , unde q este egală cu probabilitatea ca fie linia de intrare, fie linia de ieșire să fie ocupată. În schimb, probabilitatea ca linia să fie liberă este 1 - p . Probabilitatea ca calea care conectează FE de intrare cu FE de ieșire prin nivelul mijlociu FE să fie liberă este egală cu probabilitatea ca ambele linii să fie libere, și anume (1 - p ) 2 . În consecință, probabilitatea indisponibilității sale va fi 1 - (1 - p ) 2 . Probabilitatea blocării, sau probabilitatea ca astfel de căi libere să nu existe, este atunci [1 - (1 - p ) 2 ] m .

Aproximarea Jacobeus este mai precisă și, pentru a arăta cum este derivată, presupunem că CE-urile din stadiul mediu deservesc deja un anumit număr de apeluri. Acest lucru reflectă faptul că doar configurațiile „relative” ale CI-urilor de intrare și de ieșire contează. Există i conexiuni care intră în rețea prin același CE de intrare, iar liniile libere trebuie alocate pentru a le deservi și există j conexiuni care părăsesc rețeaua Clos prin același CE de ieșire, iar liniile libere trebuie de asemenea folosite pentru a le deservi. . Prin urmare, 0 ≤ i ≤ u , și 0 ≤ j ≤ u .

Fie A egal cu numărul de metode de comutare pentru j conexiuni care ies către m CE de nivel mediu. Fie B egal cu numărul acestor metode de comutare, care este exprimat în blocare. Acesta este egal cu numărul de cazuri în care restul m - j CE-uri ale etapei mijlocii se potrivesc cu m - j din i conexiuni de intrare, care este numărul de subseturi care conțin m - j din aceste conexiuni. Atunci probabilitatea de blocare va fi:

\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!)} }

Dacă f i este probabilitatea ca i alte conexiuni să fie deja deservite de un CI de intrare și g j este egală cu probabilitatea ca j alte conexiuni să fie deja deservite de un CI de ieșire, atunci probabilitatea totală de blocare este:

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

Poate fi calculat folosind mărimile f i și g j , fiecare dintre ele având o distribuție binomială . După transformări algebrice, probabilitatea de blocare poate fi exprimată astfel:

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

Închideți rețelele cu mai mult de trei cascade

Rețeaua Klose poate fi construită din orice număr de cascade impare. Prin înlocuirea fiecărui nivel central FE cu o rețea Clos cu 3 cascade, obținem o rețea Clos cu 5 cascade. Repetând acest proces, puteți obține rețele Clos, formate din cascade 7, 9, 11 și așa mai departe.

Rețeaua Benes ( m = n =2)

O rețea neblocante de acest tip sub recomutații, unde m = n = 2, este în general numită „rețea Benesh ” , și chiar acele rețele care au fost analizate și discutate înaintea lui. Numărul de intrări și ieșiri ale unei astfel de rețele este N = r × n = 2 r . Astfel de rețele au cascade, fiecare dintre acestea fiind formată din N /2 2×2 FE. Următoarele arată o rețea Beneš 8×8 (adică unde N = 8); are 5 trepte, fiecare conţinând N /2 = 4 2×2 FE, pentru un total de 20 2×2 FE. Cele trei cascade centrale constau din două rețele Benes 4×4 mai mici, în timp ce în cascada centrală fiecare dintre FE 2×2 poate fi considerată o rețea Benes 2×2. Acest exemplu arată componenta recursivă a rețelelor de acest tip. $2log_{2}N-1$ $2log_{8}N-1=$ $Nlog_{2}NN/2=$

Literatură

Podlazov V.S., Sokolov V.V. Rețele Kloz generalizate // Automatizare și telemecanică, ed. Academizdattsentr „Știință” RAS. - 2009. - Nr. 10 . - S. 158-171 . — ISSN 0005-2310 . (Rusă)

Note

↑ V. P. Vidomenko, „Kloz Networks 40 Years Later”, 2nd Conference „Information Networks and Systems (KISS-93)”, 18-20 noiembrie 1993, Rezumate, State. Universitatea de Telecomunicații (GUT) im. prof. M. A. Bonch-Bruevich , Sankt Petersburg, 1993, p. 42-44;
↑ Clos, Charles. Un studiu al rețelelor de comutare neblocante // Jurnalul tehnic Bell Labs : jurnal. - 1953. - Martie ( vol. 32 , nr. 2 ). - P. 406-424 . — ISSN 00058580 . Arhivat din original pe 14 martie 2012.
↑ Razhivin Igor. Dicționar explicativ de telecomunicații „Digital Wireline Telecommunications for Open Systems”: Telecomunicații digitale prin cablu pe sisteme deschise (OSI). (2003). — Acoperă, printre altele, tehnologia ATM. Preluat la 8 iulie 2012. Arhivat din original la 3 ianuarie 2012. (Rusă)
↑ A. N. Nazarov, I. A. Razzhivin, M. V. Simonov. ATM: Soluții tehnice pentru rețea. — Ediție de referință. - M . : Hot Line - Telecom, 2001. - S. 376. - ISBN 5-93517-040-X .
↑ Principii de proiectare a comutatorului . Kunegin Serghei Vladimirovici. Preluat la 8 iulie 2012. Arhivat din original la 30 mai 2008. (Rusă)
↑ Arhitectura comutatorului de ieșire-tampon pentru modul de transfer asincron, Suzuki, H.; Nagano, H.; Suzuki, T.; Takeuchi, T.; Iwasaki, S. ICC '89, BOSTNICC. înregistrarea conferinței. (engleză) . IEEE Xplore, Biblioteca digitală. Preluat la 8 iulie 2012. Arhivat din original la 7 octombrie 2012.
↑ Václav E. Beneš, „Teoria matematică a conectării rețelelor și a traficului telefonic”, Academic Press , 1965.
↑ Philip Hall. Despre reprezentanții submulților // 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.