Luk netværk

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. juni 2021; checks kræver 4 redigeringer .

Kloz-netværk (nogle gange Klos-netværk ) er en type flertrins (i anden terminologi - flerlags [1] ) koblingsnetværk , først formelt beskrevet af Charles Kloz i 1953 [2] . Et sådant netværk er en teoretisk version af et praktisk flertrins telefonomstillingssystem.

Generel beskrivelse

Klose-netværket har tre kaskader (tier): en inputkaskade, en mellemkaskade (midt) og en outputkaskade. Hver kaskade består af et antal krydskontakter - de såkaldte. "tværstænger", eller, med anden terminologi, koblingselementer (CE) [3] [4] , som vist i figuren nedenfor.

Hvert opkald (forbindelsesanmodning) rammer et indgående CI, hvorefter det kan dirigeres gennem ethvert tilgængeligt mellemtrins CI til det tilsvarende udgående CI. I dette tilfælde er mellemtrins CE tilgængelig for et nyt opkald, hvis både linjen, der forbinder det med det indgående CE, og linjen, der forbinder det med det udgående CE, er ledigt.

Den vigtigste fordel ved tætte netværk er, at de har et meget mindre antal switching points sammenlignet med en crossover switch. I praktisk forstand var Klose-netværket meget gavnligt til implementering i elektromekaniske telefoncentraler, men med fremkomsten af VLSI faldt dets værdi, selvom dets principper også blev brugt i digitale hurtige pakkeomskiftere, for eksempel i NEC's ATOM-switch [5 ] [6] .

Et Klose-netværk er defineret af tre heltal n , m og r . Antallet n er lig med antallet af linjer forbundet til hver af r CE'erne i det indkommende trin. Hvert CE i det indkommende trin har m udgange, og mellemtrinet indeholder også m CE'er. Dimensionen af CE for det indkommende trin vil således være n x m , det vil sige n inputs og m outputs. Der er nøjagtig én forbindelse mellem hvert indkommende trin CI og hvert mellemtrin CI, og det samme gælder for forbindelser fra mellemtrinnet til det udgående trin. Den udgående (tredje) kaskade indeholder r CE'er, som hver har dimensionen m x n .

Blokeringssandsynligheder

Sandsynligheden for at blokere Clos-netværket bestemmes af de relative værdier af m og n .

Strengt ikke-blokerende Kloz-netværk ( m ≥ 2 n - 1) - Kloz' originale 1953 -afledning

Hvis m ≥ 2 n - 1, så er Clos-netværket strengt ikke-blokerende i den forstand, at den indgående SP's frie input altid kan forbindes til den udgående SP's frie udgang uden behov for at omskifte eksisterende forbindelser. Denne konklusion danner grundlaget for Kloses klassiske papir fra 1953 . Antag, at der er en ledig linje på en indgående CI, der skal forbindes til en ledig linje på en bestemt udgående CI. I værste fald betjener den indgående CI allerede n - 1 forbindelser, det samme kan siges om den udgående CI, det vil sige, at den betjener n - 1 forbindelser. Antag, også for det værste tilfælde, at hver af disse forbindelser passerer gennem en anden mellemlags FE. Derfor er 2 n - 2 mellemlags FE'er i værste fald ikke i stand til at etablere en ny forbindelse. For at Clos-netværket skal være strengt ikke-blokerende, kræves der yderligere en mellemtrins FE, og deres samlede antal skal være 2 n - 1.

Luk netværk, der er ikke-blokerende under rekommuteringer ( m ≥ n )

Hvis m ≥ n , så kaldes Clos-netværket "ikke-blokerende under omkommuteringer". Det betyder, at den frie port på input-CE'en altid kan forbindes til den frie port på output-CE'en, men for dette kan det være nødvendigt at omskifte de eksisterende forbindelser ved at etablere dem gennem andre CE'er i centralen (midten) kaskade af det nære netværk [7] .

For at bevise dette punkt er det tilstrækkeligt at overveje tilfældet med m = n , når Clos-netværket er fuldt involveret, det vil sige, at r × n forbindelser betjenes. Beviset viser, hvordan enhver permutation af r × n input-linjer for r × n output-linjer kan opdeles i mindre permutationer, som hver kan implementeres af en separat FE i Clos-netværket, hvor m = n .

Beviset bruger Halls teorem [8] , kaldet "ægteskabsteoremet", på grund af dets forklaring med involvering af "drenge" og "piger". Det antages således, at der er r drenge og r piger. Sætningen siger, at hvis hver dreng i en delmængde af k drenge (for hver k , altså 0 ≤ k ≤ r ) kender k eller flere piger, så kan hver dreng gifte sig med den pige, han kender. Det er klart, at dette er en nødvendig betingelse for, at et ægteskab kan finde sted, og overraskende nok er det nok.

I forbindelse med Klose-netværket er hver dreng en indkommende FE, og hver pige er en udgående FE. En dreng siges at kende en pige, når de indgående og udgående CI'er tjener den samme forbindelse. Hvert sæt af k drenge skal være bekendt med mindst k piger, fordi k indgående FE'er betjener k × n forbindelser og kræver mindst k udgående FE'er for at servicere dem. Herfra vil hver indkommende CI blive parret med en udgående CI, der betjener den samme en-til-en forbindelse. Disse r- forbindelser kan betjenes af et mellemtrins CI. Hvis vi nu fjerner denne mellemniveau FE fra Clos netværket, så falder m med 1, og vi har et mindre Clos netværk. Derefter gentages processen igen, indtil m bliver lig med 1, og hver forbindelse betjenes af CE på mellemtrinnet.

Blokeringssandsynligheder - Lee og Jacobeus tilnærmelser

Rigtige telefonomstillingssystemer er sjældent strengt ikke-blokerende på grund af de høje omkostninger ved deres implementering, de har normalt en lav blokeringssandsynlighed, som kan beregnes ved hjælp af Lee- eller Jacobeus -approksimationerne [9] , forudsat at eksisterende forbindelser ikke omkobles. I dette tilfælde vil det potentielle antal andre aktive forbindelser i hver indgangs- eller udgangskontakt være u = n - 1.

Lee-approksimationen antager, at hver indre linje mellem stadier allerede er optaget af en forbindelse med sandsynlighed p , og at denne linje er fuldstændig uafhængig af de andre linjer. I dette tilfælde vil sandsynligheden for blokering blive overvurderet, især for små r . Sandsynligheden for, at et givet lokalnummer er optaget, er p = uq / m , hvor q er lig med sandsynligheden for, at enten den indgående eller udgående linje er optaget. Omvendt er sandsynligheden for, at linjen er fri, 1 - p . Sandsynligheden for, at stien, der forbinder den indgående FE med den udgående FE gennem det midterste lag FE, er fri, er lig med sandsynligheden for, at begge linjer er frie, nemlig (1 - p ) 2 . Som følge heraf vil sandsynligheden for, at den ikke er tilgængelig, være 1 - (1 - p ) 2 . Sandsynligheden for blokering, eller sandsynligheden for, at der ikke er sådanne frie stier, er da [1 - (1 - p ) 2 ] m .

Jacobeus-tilnærmelsen er mere nøjagtig, og for at vise, hvordan den er udledt, antag, at mellemtrins-CE'erne allerede betjener et vist antal opkald. Dette afspejler det faktum, at kun de "relative" konfigurationer af indgående og udgående CI'er har betydning. Der er i -forbindelser, der kommer ind i netværket gennem den samme indgående CE, og der skal allokeres frie linjer til at betjene dem, og der er j -forbindelser, der forlader Clos-netværket gennem samme udgående CE, og frie linjer skal også bruges til at betjene dem. . Derfor er 0 ≤ i ≤ u , og 0 ≤ j ≤ u .

Lad A være lig med antallet af koblingsmetoder for j forbindelser, der udgår til m mellemtrins CE'er. Lad B være lig med antallet af disse koblingsmetoder, hvilket udtrykkes i blokering. Dette er lig med antallet af tilfælde, hvor de resterende m - j CE'er i mellemtrinnet matcher m - j af i indgående forbindelser, hvilket er antallet af delmængder, der indeholder m - j af disse forbindelser. Så vil blokeringssandsynligheden være:

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

Hvis f i er sandsynligheden for, at i andre forbindelser allerede betjenes af et indkommende CI, og g j er lig med sandsynligheden for, at j andre forbindelser allerede betjenes af et udgående CI, så er den samlede blokeringssandsynlighed:

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

Det kan beregnes ved hjælp af størrelserne f i og g j , som hver har en binomialfordeling . Efter algebraiske transformationer kan blokeringssandsynligheden udtrykkes som:

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

Luk netværk med mere end tre kaskader

Klose-netværket kan bygges ud fra et vilkårligt antal ulige kaskader. Ved at erstatte hver central tier FE med et 3-kaskade Clos-netværk opnår vi et 5-kaskade Clos-netværk. Ved at gentage denne proces kan du få Clos-netværk, bestående af 7, 9, 11 og så videre kaskader.

Benes netværk ( m = n =2)

Et ikke-blokerende netværk af denne type under rekommuteringer, hvor m = n = 2, kaldes generelt et "Benesh-netværk " , og endda de netværk, der blev analyseret og diskuteret før ham. Antallet af input og output af et sådant netværk er N = r × n = 2 r . Sådanne netværk har kaskader, som hver består af N /2 2×2 FE'er. Det følgende viser et 8×8 Beneš-netværk (dvs. hvor N = 8); den har 5 trin, der hver indeholder N /2 = 4 2×2 FE'er, i alt 20 2×2 FE'er. De tre centrale kaskader består af to mindre Benes 4×4 netværk, mens hver af 2×2 FE’erne i den centrale kaskade kan betragtes som et 2×2 Benes netværk. Dette eksempel viser den rekursive komponent i netværk af denne type. $2log_{2}N-1$ $2log_{8}N-1=$ $Nlog_{2}NN/2=$

Litteratur

Podlazov V.S., Sokolov V.V. Generaliserede Kloz-netværk // Automation og telemekanik, red. Academizdattsentr "Science" RAS. - 2009. - Nr. 10 . - S. 158-171 . — ISSN 0005-2310 . (Russisk)

Noter

↑ V. P. Vidomenko, "Kloz Networks 40 Years Later", 2. konference "Information Networks and Systems (KISS-93)", November 18-20, 1993, Abstracts, State. University of Telecommunications (GUT) im. prof. M. A. Bonch-Bruevich , St. Petersburg, 1993, s. 42-44;
↑ Clos, Charles. En undersøgelse af ikke-blokerende koblingsnetværk // Bell Labs Technical Journal : journal. - 1953. - Marts ( bind 32 , nr. 2 ). - S. 406-424 . — ISSN 00058580 . Arkiveret fra originalen den 14. marts 2012.
↑ Razhivin Igor. Telekommunikations forklarende ordbog "Digital Wireline Telecommunications for Open Systems": Digital Wireline telekommunikation på åbne systemer (OSI). (2003). — Dækker blandt andet ATM-teknologi. Hentet 8. juli 2012. Arkiveret fra originalen 3. januar 2012. (Russisk)
↑ A. N. Nazarov, I. A. Razzhivin, M. V. Simonov. ATM: Tekniske løsninger til netværk. — Referenceudgave. - M . : Hot Line - Telecom, 2001. - S. 376. - ISBN 5-93517-040-X .
↑ Switch Design Principper . Kunegin Sergey Vladimirovich. Hentet 8. juli 2012. Arkiveret fra originalen 30. maj 2008. (Russisk)
↑ Output-buffer switch-arkitektur til asynkron overførselstilstand, Suzuki, H.; Nagano, H.; Suzuki, T.; Takeuchi, T.; Iwasaki, S. ICC '89, BOSTONICC. konferencerekord. (engelsk) . IEEE Xplore, Digital Library. Hentet 8. juli 2012. Arkiveret fra originalen 7. oktober 2012.
↑ Václav E. Beneš, "Mathematical Theory of Connecting Networks and Telephone Traffic", Academic Press , 1965.
↑ Philip Hall. Om repræsentanter for undergrupper // 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.