Hálózat bezárása

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. június 10-én felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A Kloz-hálózat (néha Klos-hálózat ) a többlépcsős (más szóhasználattal - többszintű [1] ) kapcsolóhálózat egy típusa, amelyet először Charles Kloz írt le hivatalosan 1953 - ban [2] . Egy ilyen hálózat egy gyakorlati többlépcsős telefonkapcsoló rendszer elméleti változata.

Általános leírás

A Klose hálózat három kaszkádból (szintből áll): egy bemeneti kaszkádból, egy köztes (középső) kaszkádból és egy kimeneti kaszkádból. Mindegyik kaszkád számos keresztkapcsolóból áll - az ún. "crossbars", vagy más szóhasználattal kapcsolóelemek (CE) [3] [4] , amint az az alábbi ábrán látható.

Minden hívás (csatlakozási kérés) elér egy bejövő CI-t, amely után bármely elérhető középső szintű CI-n keresztül továbbítható a megfelelő kimenő CI-hez. Ebben az esetben a középső szintű CE elérhető egy új híváshoz, ha mind a bejövő CE-vel összekötő vonal, mind a kimenő CE-vel összekötő vonal szabad.

A Close hálózatok legfontosabb előnye, hogy sokkal kevesebb kapcsolási ponttal rendelkeznek, mint egy keresztváltó kapcsolóval. Gyakorlati értelemben a Klose hálózat nagyon előnyös volt az elektromechanikus telefonközpontokban való megvalósításhoz, de a VLSI megjelenésével értéke csökkent, bár elveit a digitális gyors csomagkapcsolókban is alkalmazták, például a NEC ATOM switchében [5] ] [6] .

A Klose hálózatot három n , m és r egész szám határozza meg . Az n szám megegyezik a bejövő fokozat mindegyik r CE-jéhez kapcsolódó vonalak számával. A bejövő fokozat mindegyik CE-je m kimenettel rendelkezik, és a középső fokozat is m CE-t tartalmaz. Így a bejövő fokozat CE dimenziója n x m lesz , azaz n bemenet és m kimenet. Pontosan egy kapcsolat van minden bejövő CI és minden középső szakasz CI között, és ugyanez igaz a középső szakasztól a kimenő szakaszig tartó kapcsolatokra is. A kimenő (harmadik) kaszkád r CE-t tartalmaz, amelyek mindegyikének mérete m x n .

Blokkolási valószínűségek

A Clos hálózat blokkolásának valószínűségét m és n relatív értéke határozza meg .

Szigorúan nem blokkoló Kloz-hálózatok ( m ≥ 2 n - 1) - Kloz eredeti, 1953 -as származéka

Ha m ≥ 2 n - 1, akkor a Clos hálózat szigorúan nem blokkoló abban az értelemben, hogy a bejövő SP szabad bemenete mindig csatlakoztatható a kimenő SP szabad kimenetéhez anélkül, hogy a meglévő kapcsolatokat át kellene kapcsolni. Ez a következtetés képezi Klose 1953 -as klasszikus tanulmányának alapját . Tegyük fel, hogy van egy üresjárati vonal a bejövő CI-n, amelyet egy adott kimenő CI üresjárati vonalához kell csatlakoztatni. A legrosszabb esetben a bejövő CI már n - 1 kapcsolatot kiszolgál, ugyanez elmondható a kimenő CI-ről is, vagyis hogy n - 1 kapcsolatot szolgál ki. Tételezzük fel, a legrosszabb esetben is, hogy ezek a kapcsolatok mindegyike más-más középszintű FE-n halad át. Ezért a legrosszabb esetben 2 n - 2 középszintű FE nem tud új kapcsolatot létesíteni. Így ahhoz, hogy a Clos hálózat szigorúan ne blokkoljon, még egy középső szintű FE-re van szükség, és ezek teljes számának 2 n - 1-nek kell lennie.

Clos hálózatok, amelyek nem blokkolnak újrakommutációk alatt ( m ≥ n )

Ha m ≥ n , akkor a Clos hálózatot "újrakommutációk alatt nem blokkolónak" nevezik. Ez azt jelenti, hogy a bemeneti CE szabad portja mindig csatlakoztatható a CE kimenet szabad portjához, de ehhez szükség lehet a meglévő kapcsolatok újrakapcsolására úgy, hogy azokat a központi (középső) többi CE-jén keresztül hozzuk létre. a Close hálózat kaszkádja [7] .

Ennek bizonyításához elegendő az m = n esetet figyelembe venni , amikor a Clos hálózat teljes mértékben érintett, vagyis r × n kapcsolat kiszolgált. A bizonyítás megmutatja, hogy az r × n bemeneti vonal bármely permutációja r × n kimeneti vonalra hogyan bontható fel kisebb permutációkra, amelyek mindegyike megvalósítható egy külön FE-vel a Clos hálózatban, ahol m = n .

A bizonyítás Hall tételét [8] használja , amelyet „házassági tételnek” neveznek, mert magyarázata a „fiúk” és „lányok” bevonásával történik. Így feltételezzük, hogy r fiú és r lány van. A tétel kimondja, hogy ha egy k fiúból álló részhalmazban (minden k esetén 0 ≤ k ≤ r ) minden fiú k vagy több lányt ismer, akkor minden fiú feleségül veheti azt a lányt, akit ismer. Nyilvánvaló, hogy ez elengedhetetlen feltétele a házasságkötésnek, és meglepő módon ez elég is.

A Klose hálózat kontextusában minden fiú bejövő FE, és minden lány kimenő FE. Azt mondják, hogy egy fiú ismer egy lányt, ha a bejövő és a kimenő CI ugyanazt a kapcsolatot szolgálja. Minden k fiúból álló halmaznak legalább k lányt kell ismernie, mert k bejövő FE k × n kapcsolatot szolgál ki, és legalább k kimenő FE-re van szükség a kiszolgálásukhoz. Innentől kezdve minden bejövő CI egy kimenő CI-vel lesz párosítva, amely ugyanazt az egy-egy kapcsolatot szolgálja ki. Ezeket az r kapcsolatokat egy középső szintű CI szolgálhatja ki. Ha most eltávolítjuk ezt a középszintű FE-t a Clos hálózatból, akkor m 1-gyel csökken, és kisebb Clos hálózatunk lesz. Ezután a folyamat ismétlődik, amíg m egyenlő nem lesz 1-gyel, és minden kapcsolatot a középső fokozat CE-je szolgál ki.

Blokkoló valószínűségek – Lee és Jacobeus közelítések

A valódi telefonkapcsoló rendszerek a megvalósításuk magas költsége miatt ritkán szigorúan nem blokkolóak, általában alacsony a blokkolási valószínűségük, ami a Lee vagy Jacobeus közelítésekkel számítható ki [9] , feltéve, hogy a meglévő kapcsolatokat nem kapcsolják át. Ebben az esetben a többi aktív csatlakozás potenciális száma minden bemeneti vagy kimeneti kapcsolóban u = n - 1 lesz.

A Lee-közelítés feltételezi, hogy a szakaszok közötti minden belső vonalat már elfoglalja egy p valószínűségű kapcsolat , és ez a vonal teljesen független a többi egyenestől. Ebben az esetben a blokkolás valószínűsége túlbecsült lesz, különösen kis r esetén . Annak a valószínűsége, hogy egy adott mellék foglalt, p = uq / m , ahol q egyenlő annak valószínűségével, hogy a bejövő vagy a kimenő vonal foglalt. Ezzel szemben annak a valószínűsége, hogy a vonal szabad, 1 - p . Annak a valószínűsége, hogy a bejövő FE-t a kimenő FE-vel a középső FE-n keresztül összekötő út szabad, egyenlő annak a valószínűségével, hogy mindkét vonal szabad, nevezetesen (1 - p ) 2 . Következésképpen az elérhetetlenség valószínűsége 1 - (1 - p ) 2 lesz . A blokkolás valószínűsége, vagy annak a valószínűsége, hogy nincsenek ilyen szabad utak, ekkor [1 - (1 - p ) 2 ] m .

A Jacobeus-közelítés pontosabb, és a származtatásának bemutatásához tegyük fel, hogy a közepes fokozatú CE-k már kiszolgálnak bizonyos számú hívást. Ez azt a tényt tükrözi, hogy csak a bejövő és kimenő CI-k „relatív” konfigurációja számít. Ugyanazon a bejövő CE - n keresztül a hálózatba i csatlakozások lépnek be, és ezek kiszolgálására ingyenes vonalakat kell kijelölni, és vannak j csatlakozások, amelyek ugyanazon a kimenő CE-n keresztül hagyják el a Clos hálózatot, és ezek kiszolgálására is szabad vonalakat kell használni. . Ezért 0 ≤ i ≤ u és 0 ≤ j ≤ u .

Legyen A egyenlő az m középszintű CE- hez kimenő j kapcsolat kapcsolási módszereinek számával. Legyen B egyenlő ezen kapcsolási módok számával, amelyet blokkolással fejezünk ki. Ez megegyezik azon esetek számával, amikor a középső szakasz fennmaradó m - j CE-je egyezik az i bejövő kapcsolatok m - j -ével, ami az ilyen kapcsolatok m - j -t tartalmazó részhalmazainak száma . Ekkor a blokkolási valószínűség a következő lesz:

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

Ha f i annak a valószínűsége, hogy i másik kapcsolatot már kiszolgál egy bejövő CI, és g j egyenlő annak a valószínűségével, hogy j másik kapcsolatot már kiszolgált egy kimenő CI, akkor a teljes blokkolási valószínűség:

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

Kiszámítható az f i és g j mennyiségek felhasználásával , amelyek mindegyikének binomiális eloszlása van . Az algebrai transzformációk után a blokkolási valószínűség a következőképpen fejezhető ki:

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

Zárja be a háromnál több kaszkádot tartalmazó hálózatokat

A Klose hálózat tetszőleges számú páratlan kaszkádból felépíthető. Az egyes központi szintű FE-k 3-kaszkádos Clos-hálózatra cserélésével egy 5-kaszkádos Clos-hálózatot kapunk. A folyamat megismétlésével Clos hálózatokat kaphat, amelyek 7, 9, 11 és így tovább kaszkádokból állnak.

Benes hálózat ( m = n =2)

Az ilyen típusú nem blokkoló hálózatokat rekommutációk során, ahol m = n = 2, általában "Benesh hálózatnak " nevezik , és még azokat a hálózatokat is, amelyeket korábban elemeztek és tárgyaltak. Egy ilyen hálózat be- és kimeneteinek száma N = r × n = 2 r . Az ilyen hálózatok kaszkádokkal rendelkeznek, amelyek mindegyike N /2 2×2 FE-ből áll. Az alábbiakban egy 8×8-as Beneš-hálózat látható (azaz ahol N = 8); 5 fokozata van , mindegyik N /2 = 4 2×2 FE-t tartalmaz, összesen 20 db 2×2 FE-t. A három központi kaszkád két kisebb Benes 4×4 hálózatból áll, míg a központi kaszkádban a 2×2 FE mindegyike 2×2 Benes hálózatnak tekinthető. Ez a példa az ilyen típusú hálózatok rekurzív összetevőjét mutatja be. $2log_{2}N-1$ $2log_{8}N-1=$ $Nlog_{2}NN/2=$

Irodalom

Podlazov V.S., Szokolov V.V. Általánosított Kloz-hálózatok // Automatizálás és telemechanika, szerk. Academizdattsentr "Science" RAS. - 2009. - 10. sz . - S. 158-171 . — ISSN 0005-2310 . (Orosz)

Jegyzetek

↑ V. P. Vidomenko, „Kloz Networks 40 Years Later”, 2. Konferencia „Információs hálózatok és rendszerek (KISS-93)”, 1993. november 18-20., Abstracts, State. Távközlési Egyetem (GUT) im. prof. M. A. Bonch-Bruevich , Szentpétervár, 1993, 42-44.
↑ Clos, Charles. A nem blokkoló kapcsolóhálózatok tanulmánya // Bell Labs Technical Journal : folyóirat. - 1953. - március ( 32. évf. , 2. sz.). - P. 406-424 . — ISSN 00058580 . Az eredetiből archiválva : 2012. március 14.
↑ Razhivin Igor. Távközlési magyarázó szótár "Digital Wireline Telecommunications for Open Systems": Digital Wireline telecommunications on Open Systems (OSI). (2003). — Ide tartozik többek között az ATM technológia. Letöltve: 2012. július 8. Az eredetiből archiválva : 2012. január 3.. (Orosz)
↑ A. N. Nazarov, I. A. Razzhivin, M. V. Szimonov. ATM: Műszaki megoldások a hálózatépítéshez. — Referenciakiadás. - M . : Hot Line - Telecom, 2001. - S. 376. - ISBN 5-93517-040-X .
↑ Kapcsoló tervezési alapelvek . Kunegin Szergej Vlagyimirovics. Letöltve: 2012. július 8. Az eredetiből archiválva : 2008. május 30. (Orosz)
↑ Output-buffer switch architektúra aszinkron átviteli módhoz, Suzuki, H.; Nagano, H.; Suzuki, T.; Takeuchi, T.; Iwasaki, S. ICC '89, BOSTONICC. konferencia rekordja. (angol) . IEEE Xplore, digitális könyvtár. Letöltve: 2012. július 8. Az eredetiből archiválva : 2012. október 7..
↑ Václav E. Beneš, "A hálózatok és a telefonforgalom összekapcsolásának matematikai elmélete", Akadémiai Kiadó , 1965.
↑ Philip Hall. A részhalmazok képviselőiről // 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.