Stäng nätverk

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 juni 2021; kontroller kräver 4 redigeringar .

Kloz nätverk (ibland Klos nätverk ) är en typ av flerstegs (i annan terminologi - flernivå [1] ) kopplingsnätverk , som först formellt beskrevs av Charles Kloz 1953 [ 2] . Ett sådant nätverk är en teoretisk version av ett praktiskt flerstegs telefonväxelsystem.

Allmän beskrivning

Klose-nätverket har tre kaskader (nivåer): en ingångskaskad, en mellankaskad (mitten) och en utgångskaskad. Varje kaskad består av ett antal korsbrytare - den sk. "crossbars", eller, med annan terminologi, switching elements (CE) [3] [4] , som visas i figuren nedan.

Varje samtal (anslutningsbegäran) träffar ett inkommande CI, varefter det kan dirigeras genom vilken tillgänglig mellannivå CI som helst till motsvarande utgående CI. I det här fallet är mellannivån CE tillgänglig för ett nytt samtal om både linjen som förbinder den med den inkommande CE:n och linjen som förbinder den med den utgående CE:n är ledig.

Den största fördelen med nära nätverk är att de har ett mycket mindre antal kopplingspunkter jämfört med en crossover-switch. I praktisk mening var Klose-nätverket mycket fördelaktigt för implementering i elektromekaniska telefonväxlar, men med tillkomsten av VLSI minskade dess värde, även om dess principer också användes i digitala snabba paketväxlar, till exempel i NEC:s ATOM-växel [5 ] [6] .

Ett Klose-nätverk definieras av tre heltal n , m och r . Antalet n är lika med antalet linjer anslutna till var och en av r CE:erna för det inkommande steget. Varje CE i det inkommande steget har m utgångar, och mellansteget innehåller också m CE. Sålunda kommer dimensionen på CE för det inkommande steget att vara n x m , det vill säga n ingångar och m utgångar. Det finns exakt en koppling mellan varje inkommande steg CI och varje mellansteg CI, och detsamma gäller för anslutningar från mellansteget till det utgående steget. Den utgående (tredje) kaskaden innehåller r CE, som var och en har dimensionen m x n .

Blockeringssannolikheter

Sannolikheterna för att blockera Clos-nätverket bestäms av de relativa värdena för m och n .

Strikt icke-blockerande Kloz-nätverk ( m ≥ 2 n - 1) - Kloz ursprungliga 1953 -härledning

Om m ≥ 2 n - 1, så är Clos-nätverket strikt icke-blockerande i den meningen att den inkommande SP:ns fria ingång alltid kan anslutas till den utgående SP:ns fria utgång utan att behöva byta om befintliga anslutningar. Denna slutsats utgör grunden för Kloses klassiska uppsats från 1953 . Anta att det finns en ledig linje på en inkommande CI som måste anslutas till en ledig linje på en viss utgående CI. I värsta fall betjänar den inkommande CI redan n - 1 anslutningar, detsamma kan sägas om den utgående CI, det vill säga att den betjänar n - 1 anslutningar. Antag, också i värsta fall, att var och en av dessa anslutningar passerar genom en annan mellanskikts-FE. Därför, i värsta fall, kan 2 n - 2 FE:er på mitten inte upprätta en ny anslutning. Således, för att Clos-nätverket ska vara strikt icke-blockerande, krävs ytterligare en mellannivå FE, och deras totala antal bör vara 2 n - 1.

Stänga nätverk som är icke-blockerande under omkommutering ( m ≥ n )

Om m ≥ n kallas Clos-nätverket "icke-blockerande under omkommutationer". Detta innebär att den fria porten på ingångs-CE alltid kan anslutas till den fria porten på utgång-CE, men för detta kan det vara nödvändigt att byta om de befintliga anslutningarna genom att etablera dem genom andra CE:er i centralen (mitten) kaskad av det nära nätverket [7] .

För att bevisa denna punkt räcker det att betrakta fallet med m = n , när Clos-nätverket är fullt involverat, det vill säga r × n anslutningar betjänas. Beviset visar hur eventuell permutation av r × n ingångslinjer för r × n utgångslinjer kan brytas ner i mindre permutationer, som var och en kan implementeras av en separat FE i Clos-nätverket, där m = n .

Beviset använder Halls teorem [8] , kallad "äktenskapsteorem", på grund av dess förklaring med inblandning av "pojkar" och "flickor". Det antas alltså att det finns r pojkar och r tjejer. Teoremet säger att om i en delmängd av k pojkar (för varje k , alltså 0 ≤ k ≤ r ) känner varje pojke k eller fler flickor, då kan varje pojke gifta sig med den flicka han känner. Det är tydligt att detta är en nödvändig förutsättning för att ett äktenskap ska kunna äga rum, och överraskande nog räcker det.

I samband med Klose-nätverket är varje pojke en inkommande FE, och varje tjej är en utgående FE. En pojke sägs känna en flicka när de inkommande och utgående CI:erna har samma anknytning. Varje uppsättning av k pojkar måste vara bekanta med minst k flickor, eftersom k inkommande FEs betjänar k × n anslutningar och kräver minst k utgående FEs för att betjäna dem. Härifrån kommer varje inkommande CI att paras med en utgående CI som betjänar samma en-till-en-anslutning. Dessa r- anslutningar kan betjänas av en mellannivå CI. Om vi nu tar bort denna mellannivå FE från Clos-nätverket, så minskar m med 1, och vi har ett mindre Clos-nätverk. Därefter upprepas processen igen tills m blir lika med 1, och varje anslutning betjänas av CE för mellansteget.

Blockeringssannolikheter - Lee och Jacobeus approximationer

Verkliga telefonväxlingssystem är sällan strikt icke-blockerande på grund av den höga kostnaden för deras implementering, de har vanligtvis en låg blockeringssannolikhet, vilket kan beräknas med hjälp av Lee eller Jacobeus approximationer [9] , förutsatt att befintliga anslutningar inte växlas om. I detta fall kommer det potentiella antalet andra aktiva anslutningar i varje ingångs- eller utgångsomkopplare att vara u = n - 1.

Lee-approximationen antar att varje inre linje mellan stegen redan är upptagen av en koppling med sannolikhet p , och att denna linje är helt oberoende av de andra linjerna. I det här fallet kommer sannolikheten för blockering att överskattas, särskilt för små r . Sannolikheten att en given anknytning är upptagen är p = uq / m , där q är lika med sannolikheten att antingen den inkommande eller utgående linjen är upptagen. Omvänt är sannolikheten att linjen är fri 1 - p . Sannolikheten att vägen som förbinder den inkommande FE med den utgående FE genom mittskiktet FE är fri är lika med sannolikheten att båda linjerna är fria, nämligen (1 - p ) 2 . Följaktligen kommer sannolikheten för dess otillgänglighet att vara 1 - (1 - p ) 2 . Sannolikheten för blockering, eller sannolikheten att det inte finns några sådana fria vägar, är då [1 - (1 - p ) 2 ] m .

Jacobeus-approximationen är mer exakt, och för att visa hur den härleds, anta att CE:erna i medelstadiet redan betjänar ett visst antal samtal. Detta återspeglar det faktum att endast de "relativa" konfigurationerna av inkommande och utgående CI har betydelse. Det finns i -anslutningar som går in i nätverket via samma inkommande CE, och fria linjer måste tilldelas för att betjäna dem, och det finns j -anslutningar som lämnar Clos-nätverket via samma utgående CE, och fria linjer måste också användas för att betjäna dem. . Därför är 0 ≤ i ≤ u och 0 ≤ j ≤ u .

Låt A vara lika med antalet kopplingsmetoder för j anslutningar som utgår till m mellanskikts CE:er. Låt B vara lika med antalet av dessa kopplingsmetoder, vilket uttrycks i blockering. Detta är lika med antalet fall i vilka de återstående m - j CE:erna i mellansteget matchar m - j av i inkommande anslutningar, vilket är antalet delmängder som innehåller m - j av dessa anslutningar. Då blir sannolikheten för blockering:

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

Om f i är sannolikheten att i andra anslutningar redan betjänas av en inkommande CI, och g j är lika med sannolikheten att j andra anslutningar redan betjänas av en utgående CI, då är den totala blockeringssannolikheten:

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

Den kan beräknas med hjälp av storheterna fi och g j , som var och en har en binomialfördelning . Efter algebraiska transformationer kan blockeringssannolikheten uttryckas som:

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

Stäng nätverk med mer än tre kaskader

Klose-nätverket kan byggas från valfritt antal udda kaskader. Genom att ersätta varje central tier FE med ett 3-kaskad Clos-nätverk får vi ett 5-kaskad Clos-nätverk. Genom att upprepa denna process kan du få Clos-nätverk, bestående av 7, 9, 11 och så vidare kaskader.

Benes nätverk ( m = n =2)

Ett icke-blockerande nätverk av den här typen under omkommutationer, där m = n = 2, kallas i allmänhet ett "Benesh-nätverk " , och även de nätverk som analyserades och diskuterades före honom. Antalet ingångar och utgångar för ett sådant nätverk är N = r × n = 2 r . Sådana nätverk har kaskader, som var och en består av N /2 2×2 FEs. Följande visar ett 8×8 Beneš-nätverk (dvs där N = 8); den har 5 steg, som var och en innehåller N /2 = 4 2×2 FEs, för totalt 20 2×2 FEs. De tre centrala kaskaderna består av två mindre Benes 4×4-nätverk, medan i den centrala kaskaden kan var och en av 2×2 FE:erna betraktas som ett 2×2 Benes-nätverk. Detta exempel visar den rekursiva komponenten i nätverk av denna typ. $2log_{2}N-1$ $2log_{8}N-1=$ $Nlog_{2}NN/2=$

Litteratur

Podlazov V.S., Sokolov V.V. Generaliserade Kloz-nätverk // Automation och telemekanik, red. Academizdattsentr "Science" RAS. - 2009. - Nr 10 . - S. 158-171 . — ISSN 0005-2310 . (ryska)

Anteckningar

↑ V. P. Vidomenko, "Kloz Networks 40 Years Later", 2:a konferensen "Information Networks and Systems (KISS-93)", 18-20 november 1993, Abstracts, State. University of Telecommunications (GUT) im. prof. M. A. Bonch-Bruevich , St. Petersburg, 1993, sid. 42-44;
↑ Clos, Charles. En studie av icke-blockerande växlingsnätverk // Bell Labs Technical Journal : journal. - 1953. - Mars ( vol. 32 , nr 2 ). - s. 406-424 . — ISSN 00058580 . Arkiverad från originalet den 14 mars 2012.
↑ Razhivin Igor. Telekommunikations förklarande ordbok "Digital Wireline Telecommunications for Open Systems": Digital Wireline telecommunications on Open Systems (OSI). (2003). — Täcker bland annat ATM-teknik. Hämtad 8 juli 2012. Arkiverad från originalet 3 januari 2012. (ryska)
↑ A. N. Nazarov, I. A. Razzhivin, M. V. Simonov. ATM: Tekniska lösningar för nätverk. — Referensupplaga. - M . : Hot Line - Telecom, 2001. - S. 376. - ISBN 5-93517-040-X .
↑ Switch Design Principer . Kunegin Sergey Vladimirovich. Hämtad 8 juli 2012. Arkiverad från originalet 30 maj 2008. (ryska)
↑ Output-buffert switch-arkitektur för asynkront överföringsläge, Suzuki, H.; Nagano, H.; Suzuki, T.; Takeuchi, T.; Iwasaki, S. ICC '89, BOSTONICC. konferensrekord. (engelska) . IEEE Xplore, Digital Library. Hämtad 8 juli 2012. Arkiverad från originalet 7 oktober 2012.
↑ Václav E. Beneš, "Mathematical Theory of Connecting Networks and Telephone Traffic", Academic Press , 1965.
↑ Philip Hall. Om representanter för delmängder // 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.