Sulje verkko

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 10. kesäkuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Kloz-verkko (joskus Klos-verkko ) on eräänlainen monivaiheinen (toisessa terminologiassa - monitasoinen [1] ) kytkentäverkko , jonka Charles Kloz kuvasi ensimmäisen kerran virallisesti vuonna 1953 [2] . Tällainen verkko on teoreettinen versio käytännöllisestä monivaiheisesta puhelinkytkentäjärjestelmästä.

Yleinen kuvaus

Klose-verkossa on kolme kaskadia (tasoa): tulokaskadi, väli (keski) kaskadi ja lähtökaskadi. Jokainen kaskadi koostuu useista ristikytkimistä - ns. "crossbars" tai muussa terminologiassa kytkentäelementit (CE) [3] [4] , kuten alla olevassa kuvassa näkyy.

Jokainen puhelu (yhteyspyyntö) osuu saapuvaan CI:hen, jonka jälkeen se voidaan reitittää minkä tahansa käytettävissä olevan keskitason CI:n kautta vastaavaan lähtevään CI:hen. Tässä tapauksessa keskitason CE on käytettävissä uudelle puhelulle, jos sekä sen tulevaan CE:hen yhdistävä linja että sen lähtevään CE:hen yhdistävä linja ovat vapaat.

Close-verkkojen tärkein etu on, että niissä on paljon pienempi määrä kytkentäpisteitä verrattuna crossover-kytkimeen. Käytännössä Klose-verkko oli erittäin hyödyllinen toteutuksessa sähkömekaanisissa puhelinkeskuksissa, mutta VLSI:n myötä sen arvo laski, vaikka sen periaatteita käytettiin myös digitaalisissa nopeissa pakettikytkimissä, esimerkiksi NEC:n ATOM-kytkimessä [5 ] [6] .

Klose-verkko määritellään kolmella kokonaisluvulla n , m ja r . Luku n on yhtä suuri kuin tulovaiheen kuhunkin r CE:hen kytkettyjen linjojen lukumäärä . Jokaisella tulevan portaan CE:llä on m lähtöä ja keskiasteella on myös m CE:tä. Siten sisääntulevan portaan CE:n mitta on n x m , eli n tuloa ja m lähtöä. Jokaisen tulevan vaiheen CI ja kunkin keskiasteen CI välillä on täsmälleen yksi yhteys, ja sama pätee yhteyksiin keskivaiheesta lähtevään vaiheeseen. Lähtevä (kolmas) kaskadi sisältää r CE:tä, joiden jokaisen mitat ovat m x n .

Estotodennäköisyydet

Clos-verkon estämisen todennäköisyydet määräytyvät m :n ja n :n suhteellisilla arvoilla .

Täysin estävät Kloz-verkot ( m ≥ 2 n - 1) - Klozin alkuperäinen 1953 johdannainen

Jos m ≥ 2 n - 1, niin Clos-verkko on ehdottomasti estoton siinä mielessä, että saapuvan SP:n vapaa tulo voidaan aina kytkeä lähtevän SP:n vapaaseen lähtöön ilman tarvetta vaihtaa olemassa olevia yhteyksiä. Tämä johtopäätös muodostaa Klosen klassisen vuoden 1953 paperin perustan . Oletetaan, että saapuvassa CI:ssä on tyhjä linja, joka on kytkettävä tietyn lähtevän CI:n vapaaseen linjaan. Pahimmassa tapauksessa saapuva CI palvelee jo n - 1 yhteyttä, sama voidaan sanoa lähtevästä CI:stä, eli se palvelee n - 1 yhteyttä. Oletetaan myös pahimmassa tapauksessa, että jokainen näistä yhteyksistä kulkee eri keskitason FE:n läpi. Siksi 2 n - 2 keskitason FE:tä ei pahimmassa tapauksessa pysty muodostamaan uutta yhteyttä. Siten, jotta Clos-verkko olisi ehdottomasti ei-estoinen, tarvitaan vielä yksi keskitason FE, ja niiden kokonaismäärän tulisi olla 2 n - 1.

Suljetut verkot, jotka eivät estä uudelleenkommutaatioita ( m ≥ n )

Jos m ≥ n , niin Clos-verkkoa kutsutaan "ei-estäväksi uudelleenkommutaatioiden alla". Tämä tarkoittaa, että CE-tulon vapaa portti voidaan aina kytkeä ulostulon CE vapaaseen porttiin, mutta tätä varten voi olla tarpeen vaihtaa olemassa olevat yhteydet uudelleen muodostamalla ne keskusyksikön (keski) muiden CE:iden kautta. Close-verkon kaskadi [7] .

Tämän todistamiseksi riittää, kun tarkastellaan tapausta m = n , kun Clos-verkko on täysin mukana, eli r × n yhteyttä palvellaan. Todistus osoittaa, kuinka mikä tahansa r × n -tulolinjan permutaatio r × n lähtölinjalle voidaan jakaa pienemmiksi permutaatioiksi, joista jokainen voidaan toteuttaa erillisellä FE:llä Clos-verkossa, missä m = n .

Todistuksessa käytetään Hallin teoreemaa [8] , jota kutsutaan "avioliittolauseeksi", koska se selittyy "poikien" ja "tyttöjen" kanssa. Näin ollen oletetaan, että on r poikaa ja r tyttöä. Lause sanoo, että jos k pojan osajoukossa (jokaiselle k :lle eli 0 ≤ k ≤ r ) jokainen poika tuntee k tai useampia tyttöjä, niin jokainen poika voi mennä naimisiin tuntemansa tytön kanssa. On selvää, että tämä on välttämätön edellytys avioliiton solmimiselle, ja yllättävää kyllä, tämä riittää.

Klose-verkoston yhteydessä jokainen poika on saapuva FE ja jokainen tyttö lähtevä FE. Pojan sanotaan tuntevan tytön, kun saapuva ja lähtevä CI palvelee samaa yhteyttä. Jokaisen k pojan joukon on tunnettava vähintään k tyttöä, koska k saapuvaa FE:tä palvelee k × n yhteyttä ja vaatii vähintään k lähtevää FE:tä palvellakseen niitä. Tästä eteenpäin jokainen saapuva CI yhdistetään lähtevän CI:n kanssa, joka palvelee samaa kahdenkeskistä yhteyttä. Näitä r -yhteyksiä voi palvella yksi keskitason CI. Jos nyt poistamme tämän keskitason FE:n Clos-verkosta, niin m pienenee yhdellä ja meillä on pienempi Clos-verkko. Sitten prosessia toistetaan uudelleen, kunnes m on yhtä suuri kuin 1, ja jokaista yhteyttä palvelee keskiasteen CE.

Estotodennäköisyydet - Leen ja Jacobeuksen approksimaatiot

Todelliset puhelinkytkentäjärjestelmät ovat harvoin tiukasti ei-estoisia niiden toteuttamisen korkeiden kustannusten vuoksi, niillä on yleensä pieni eston todennäköisyys, joka voidaan laskea käyttämällä Lee- tai Jacobeus- likiarvoja [9] edellyttäen, että olemassa olevia yhteyksiä ei kytketä uudelleen. Tässä tapauksessa muiden aktiivisten kytkentöjen mahdollinen lukumäärä kussakin tulo- tai lähtökytkimessä on u = n - 1.

Lee-approksimaatio olettaa, että jokainen portaiden välinen sisäinen suora on jo varattu yhteyden todennäköisyydellä p ja että tämä suora on täysin riippumaton muista viivoista. Tässä tapauksessa tukkeutumisen todennäköisyys on yliarvioitu, varsinkin pienille r :ille . Todennäköisyys, että tietty alaliittymä on varattu, on p = uq / m , missä q on yhtä suuri kuin todennäköisyys, että joko saapuva tai lähtevä linja on varattu. Päinvastoin, todennäköisyys, että viiva on vapaa, on 1 - p . Todennäköisyys, että saapuvan FE:n ja lähtevän FE:n keskitason FE kautta yhdistävä polku on vapaa, on yhtä suuri kuin todennäköisyys, että molemmat linjat ovat vapaita, nimittäin (1 - p ) 2 . Näin ollen sen epäkäytettävyyden todennäköisyys on 1 - (1 - p ) 2 . Eston todennäköisyys tai todennäköisyys, ettei tällaisia vapaita polkuja ole, on tällöin [1 - (1 - p ) 2 ] m .

Jacobeuksen approksimaatio on tarkempi, ja näyttääksesi, kuinka se johdetaan, oletetaan, että keskitason CE:t palvelevat jo tiettyä määrää puheluita. Tämä kuvastaa sitä tosiasiaa, että vain saapuvien ja lähtevien CI:iden "suhteellisilla" kokoonpanoilla on merkitystä. Saman saapuvan CE:n kautta verkkoon tulee i yhteyksiä, joita palvelemaan on varattava vapaita yhteyksiä ja saman lähtevän CE:n kautta Clos-verkosta lähteviä yhteyksiä on j , ja niiden palvelemiseen on myös käytettävä vapaita linjoja. . Siksi 0 ≤ i ≤ u ja 0 ≤ j ≤ u .

Olkoon A yhtä suuri kuin m keskitason CE :hen lähtevän j yhteyden kytkentämenetelmien lukumäärä. Olkoon B yhtä suuri kuin näiden kytkentämenetelmien lukumäärä, joka ilmaistaan estona. Tämä on yhtä suuri kuin niiden tapausten lukumäärä, joissa keskivaiheen jäljellä olevat m - j CE:t vastaavat i saapuvan yhteyden m - j : ää, mikä on näiden yhteyksien m - j sisältävien osajoukkojen lukumäärä . Tällöin eston todennäköisyys on:

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

Jos f i on todennäköisyys, että saapuva CI palvelee jo i muuta yhteyttä, ja g j on yhtä suuri kuin todennäköisyys, että lähtevä CI palvelee jo j muuta yhteyttä, koko eston todennäköisyys on:

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

Se voidaan laskea käyttämällä suureita f i ja g j , joilla kullakin on binomijakauma . Algebrallisten muunnosten jälkeen eston todennäköisyys voidaan ilmaista seuraavasti:

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

Sulje verkot yli kolmella kaskadilla

Klose-verkko voidaan rakentaa mistä tahansa määrästä parittomat kaskadit. Korvaamalla jokainen keskustaso FE 3-kaskadilla Clos-verkolla saadaan 5-kaskadi Clos-verkko. Toistamalla tämän prosessin saat Clos-verkot, jotka koostuvat 7, 9, 11 ja niin edelleen kaskadeista.

Benesin verkko ( m = n =2)

Tämän tyyppistä estämätöntä verkkoa uudelleenkommutaatioissa, joissa m = n = 2, kutsutaan yleensä "Benesh-verkoksi " ja jopa niitä verkkoja, joita analysoitiin ja keskusteltiin ennen häntä. Tällaisen verkon tulojen ja lähtöjen lukumäärä on N = r × n = 2 r . Tällaisissa verkoissa on kaskadeja, joista jokainen koostuu N /2 2 × 2 FE:stä. Seuraavassa on 8 × 8 Benešin verkko (eli missä N = 8); siinä on 5 vaihetta, joista jokainen sisältää N /2 = 4 2 × 2 FE:tä, yhteensä 20 2 × 2 FE:tä. Kolme keskuskaskadia koostuvat kahdesta pienemmästä Benes 4 × 4 -verkosta, kun taas keskuskaskadissa kutakin 2 × 2 FE:tä voidaan pitää 2 × 2 Benes -verkkona. Tämä esimerkki näyttää tämäntyyppisten verkkojen rekursiivisen komponentin. $2log_{2}N-1$ $2log_{8}N-1=$ $Nlog_{2}NN/2=$

Kirjallisuus

Podlazov V.S., Sokolov V.V. Yleiset Kloz-verkot // Automaatio ja telemekaniikka, toim. Academizdattsentr "Science" RAS. - 2009. - Nro 10 . - S. 158-171 . — ISSN 0005-2310 . (Venäjän kieli)

Muistiinpanot

↑ V. P. Vidomenko, “Kloz Networks 40 Years Later”, 2. konferenssi “Information Networks and Systems (KISS-93)”, 18.-20.11.1993, Abstracts, State. Telekommunikaatioyliopisto (GUT) im. prof. M. A. Bonch-Bruevich , Pietari, 1993, s. 42-44;
↑ Clos, Charles. Tutkimus estämättömistä kytkentäverkoista // Bell Labs Technical Journal : päiväkirja. - 1953. - maaliskuu ( osa 32 , nro 2 ) . - s. 406-424 . — ISSN 00058580 . Arkistoitu alkuperäisestä 14. maaliskuuta 2012.
↑ Razhivin Igor. Tietoliikenteen selittävä sanakirja "Digital Wireline Telecommunications for Open Systems": Digital Wireline telecommunications on Open Systems (OSI). (2003). — Kattaa muun muassa ATM-tekniikan. Haettu 8. heinäkuuta 2012. Arkistoitu alkuperäisestä 3. tammikuuta 2012. (Venäjän kieli)
↑ A. N. Nazarov, I. A. Razzhivin, M. V. Simonov. ATM: Tekniset ratkaisut verkottumiseen. — Viitepainos. - M . : Hot Line - Telecom, 2001. - S. 376. - ISBN 5-93517-040-X .
↑ Kytkimien suunnitteluperiaatteet . Kunegin Sergei Vladimirovich. Haettu 8. heinäkuuta 2012. Arkistoitu alkuperäisestä 30. toukokuuta 2008. (Venäjän kieli)
↑ Lähtö-puskurikytkimen arkkitehtuuri asynkroniseen siirtotilaan, Suzuki, H.; Nagano, H.; Suzuki, T.; Takeuchi, T.; Iwasaki, S. ICC '89, BOSTONICC. konferenssin ennätys. (englanniksi) . IEEE Xplore, digitaalinen kirjasto. Haettu 8. heinäkuuta 2012. Arkistoitu alkuperäisestä 7. lokakuuta 2012.
↑ Václav E. Beneš, "Verkkojen ja puhelinliikenteen yhdistämisen matemaattinen teoria", Academic Press , 1965.
↑ Philip Hall. Osajoukkojen edustajista // 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.