Távközlő hálózatok - Blokkolásmentes kapcsolás számítása

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

A lényeg az, hogy ha 3 fokozatú kapcsolásban gondolkozunk, és az első fokozatban n-bemenetű és k-kimenetű (röviden nxk) kapcsolókat használunk, valamint a teljes kapcsoló-struktúrának N bemenete (és N kimenete van), akkor:

• egyrészt az első fokozatban N/n kapcsolóelem kell
• másrészt mivel az első fokozatban N/n kapcsolóelem van, ezért a második fokozat kapcsolóelemei N/n bemenetűek lesznek, hiszen az első fokozat i-dik kapcsolóelemének j-dik lábát a második fokozat j-dik kapcsolóelemének i-dik lábára kötjük
• innen az is következik, hogy a második fokozatban k db kapcsolóelemünk van
• továbbá a három fokozatú struktúra miatt az is világos, hogy innentől az egész szimmetrikus, tehát a második fokozatban minden kapcsolóelemnek ugyanannyi kimenete van, mint bemenete, továbbá a harmadik fokozatban szintén N/n kapcsolóelemünk van, amelyek kxn-esek (k bemenet, n kimenet)

Ugye itt a példában N=64, n=16, innen N/n=4, amit még meg is adtak. Amit keresünk, az a k. Ehhez csak annyit kell tudni, hogy három fokozatú struktúra esetén a blokkolásmentes kapcsoláshoz k=2n-1 nek kell lennie legalább (többnek ugye meg nincs értelme).

Hogy miért? A blokkolásmentes kapcsoláshoz három fokozatú struktúra esetén az kell, hogy mindig találjunk a 2. fokozatban egy olyan kapcsolóelemet, amelyiknek egy meghatározott (i,j) bemenet-kimenet párja szabad (ahol egyébként i a hívó, j pedig a hívott fél kapcsolóelemének sorszáma az 1. és a 3. fokozatban). Ilyenkor ugyanis az első fokozatban az i. kapcsolóelem egyszerűen átkapcsolja a megfelelő bemenetét az i-dik kimenetére, innen a keresett 2. fokozatbeli kapcsolóelem átkapcsolja a j-dik kimenetére, ahol a 3. fokozatban már a hívott fél kapcsolóelemén van a hívás, innen már csak egy egyszerű kapcsolás és kész.

Na de a lényeg: Mennyi legyen a k (vagyis a 2. fokozat kapcsolóelemeinek a száma), hogy mindig legyen egy olyan, amelyiknek az (i,j) bemenet-kimenet párja szabad? Ugye (n-1) kapcsoló i-dik bemenetét foglalhatja a többi 1. fokozatbeli kapcsoló (vagyis mindegyik azt az egyet leszámítva ugye, ahonnan most próbálunk kapcsolatot létesíteni), hasonlóan (n-1) kapcsolóelem j-dik kimenete lehet foglalt a 3-dik szakaszbeli többi kapcsolóelem miatt. Legrosszabb esetben ezek mind különböznek, de a (2n-1)-dik már biztos jó lesz. Ezért kell ennyi.

Vagyis itt k = 2*16-1 = 31.

Innen a kérdéseket már könnyű megválaszolni:

• K: Mi kell középre?
• V: 31db 4x4-es kapcsolóelem.

• K: Hány kapcsolópont van?
• V:
  • 1. fokozatban: 4*(16*31)
  • 2. fokozatban: 31*(4*4)
  • 3. fokozatban: ugyanannyi, mint az 1-ben.
  • Szumma: 1984 + 496 + 1984 = 4464

• K: Hány lenne amúgy?
• V: Gondolom itt arra gondol, hogy ha csak egy 64*64-es kapcsolótáblát használunk. Nos ekkor természetesen 64*64
  • 64 * 64 = 4096

4464 > 4096, akkor miért is használjuk ezt?

Igazából nem túl valóságos számokat használ a példa. Talán a könnyebb számolás kedvéért. De ha mondjuk kipróbálod N=8192 n=64 és a hozzá tartozó k=2n-1=127 számokkal, akkor valószínűleg sokkal kisebb számot fogsz kapni a 8192*8192-nél.

• 1.fokozat: 128*(64*127) = 1040384
• 2.fokozat: 127*(64*64) = 520192
• 3.fokozat: 128*(127*64) = 1040384
  • Összesen: 2600960

• Ellenben: 8192 * 8192 = 67108864

(Lala levlistás levelei alapján.)

A th slideok átnézése és némi végiggondolás után arra jutottam,hogy az N=8192 n=64 esethez leírt megoldás nem jó, mert a középső fokozathoz k*((N/n) *(N/n)), azaz 127*(128*128) darab kapcsoló szükséges, mivel az első fokozatban 128 db 127-es kimenet van, amelyek a 127 darab középső kapcsoló darabonkénti 128 bemenetéhez kell, hogy kapcsolódjanak, így lesz szimmetrikus a dolog, és ugyanígy a középső 127 darabonkénti 128 kimenete a 3. kapcsolófokozat 128 darab, 127 bemenetűjéhez kapcsolódik, ezért a kapcsolók száma:

 1.fokozat: 128*(64*127) =  1040384

 2.fokozat: 127*(128*128) = 2080768

 3.fokozat: 128*(127*64) =  1040384

 Összesen:						4161536	

Ha tévednék, akkor nyugodtan javítsatok ki. (neocry - 2006.12.05.)

-- palacsint - 2006.05.24.