Neblokirajući minimalni obuhvatni prekidač

Zamena za 16x16 unakrsni komutator, napravljena od 12 4x4 unakrsna komutatora.

Neblokirajući minimalni obuhvatni prekidač je uređaj koji može da poveže N ulaza sa N izlaza u bilo kojoj kombinaciji. Najpoznatija upotreba prekidača ovog tipa je u telefonskoj centrali. Izraz „neblokirajući“ znači da ako nije oštećen, uvek može da ostvaruje konekciju. Izraz „minimalni“ znači da ima najmanji mogući broj komponenata, a zbog toga i minimalne troškove.

Istorijski, u telefonskim centralama, veze između onih koji telefoniraju su bile uređene sa velikim, skupim bankama elektromehaničkih releja, ''Strowger prekidača''. Osnovno matematičko svojstvo Strowger prekidača je da za svaki ulaz u prekidač, postoji tačno jedan izlaz. Mnoge matematičke teorije o prekidačkim kolima nastoje da iskoriste ovu osobinu kako bi smanjile ukupan broj prekidača potrebnih da se poveže jedna kombinacija ulaza sa jednom kombinacijom izlaza.

1940-ih i 1950-ih, inženjeri u Belovim laoboratorijama su započeli proširenu seriju matematičkih istraživanja, u okviru metoda za smanjivanje veličine i potrošnje ''svič fabrike'', potrebne za implementaciju telefonske centrale. Jednu raniju, uspešnu matematičku analizu, izveo je Charles Clos i svič fabrika, konstruisana od manjih prekidača, nazvana je ''clos mreža''.

Pozadina: prekidačke topologije

Unakrsni komutator

Unakrsni komutator je u stanju da poveže N ulaza sa N izlaza u bilo kojoj jedan-na-jedan kombinaciji, tako da može da poveže bilo kog pozivaoca sa bilo kojim slobodnim prijemnikom i to svojstvo je tehnički nazvano „neblokirajuće“. Ako je neblokirajući, to znači da bi uvek mogao da uspostavi poziv (slobodnom prijemniku), što bi maksimizovalo dostupnost servisa.

Kako god, unakrsni komutator ovo radi trošeći N² jednostavnih prekidača. Za veliko N (a praktične potrebe telefonske centrale se smatraju velikim), ovaj rast je bio previše skup. Dalje, unakrsni komutator je imao fizičkih problema. Ne samo što je zahtevao previše prostora, već bi i metalni provodnici koji sadrže prekidače postali tako dugački da bi popustili i postali nepouzdani. Inženjeri su takođe primetili da je u bilo kom trenutku, svaki provodnik sa unakrsnim prekidačem uspostavljao samo jednu konekciju. Ostali kontakti na dva provodnika su bili neiskorišćeni. Ovo je nagoveštavalo da će većina provodnika svič fabrike ostajati neiskorišćena.

Očigledan način da se simulira unakrsni komutator, bio je da se pronađe neko rešenje, tako da se on izgradi od manjih unakrsnih komutatora. Ako bi on mogao da se oponaša nekim oblikom grupisanja manjih unakrsnih komutatora, onda bi ovi manji, takođe mogli da se simuliraju još manjim. Svič fabrika bi mogla da postane veoma efikasna i verovatno napravljena od standardizovanih delova. Ovo se naziva clos mreža.

Potpuno povezani troslojni prekidači

Naredni pristup bio je razbijanje unakrsnog komutatora na tri sloja manjih unakrsnih komutatora. Tu je postojao „ulazni sloj“, „srednji sloj“ i „izlazni sloj“. Manji prekidači su manje težine, pouzdaniji i genereralno lakši za pravljenje, a samim tim i jeftiniji.

Telefonski sistem jedino treba da napravi jedan-na-jedan konekciju. Intuitivno, na osnovu ovoga se čini da bi broj ulaza i broj izlaza uvek mogao da bude jednak u svakom potprekidaču, ali intuicija ne dokazuje ovo, niti nam govori kako to da postignemo. Pretpostavimo da želimo da sintetizujemo 16 po 16 unakrsnih komutatora. Ovaj dizajn bi mogao da ima 4 potprekidača na ulaznoj strani, svaki sa 4 ulaza, za ukupno 16 ulaza. Dalje, na izlaznoj strani, mogli bismo takođe da imamo 4 izlazna potprekidača, svaki sa 4 izlaza, za ukupno 16 izlaza. Poželjno je da dizajn koristi što manje žica, jer su one prilično skupe. Dakle, najmanji mogući broj žica koje mogu da povežu dva potprekidača u jednu žicu. Ovako, svaki ulazni potprekidač će imati jednu žicu ka svakom srednjem potprekidaču. Takođe, svaki srednji potprekidač će imati jednu žicu ka svakom izlaznom potprekidaču.

Pitanje je koliko srednjih potprekidača je potrebno i otuda, koliko ukupno žica bi trebalo da povezuje ulazni sloj sa izlaznim. Pošto su telefonski prekidači simetrični (pozivaoci i prijemnici su zamenjivi), ista logika se primenjuje i na izlazni sloj i srednji potprekidači će biti „kvadratni“, imaće isti broj ulaza i izlaza.

Broj srednjih potprekidača zavisi od algoritma korišćenog za alociranje veze ka njima. Osnovni algoritam za upravljanje troslojnim prekidačem je traženje srednjeg potprekidača koji ima neiskorišćene žice za potrebne ulazne i izlazne prekidače. Jednom kada se pronađe srednji prekidač sposoban za konekciju, povezivanje sa pravim ulazima i izlazima, u ulaznim i izlaznim prekidačima je trivijalno.

Teoretski, u primeru, potrebana su samo četiri centralna prekidača, svaki sa tačno jednom vezom sa svakim ulaznim prekidačem i sa jednom vezom sa svakim izlaznim prekidačem. Ovo se naziva „minimalni obuhvatni prekidač“ i rukovođenje ovim, bio je sveti gral istrage Belovih laboratorija.

Kako god, uz malo posla sa olovkom i papirom pokazaće se da je lako dobiti ovakav minimalni prekidač, u stanju u kom nijedan srednji prekidač nema vezu sa oba potrebna ulazna i izlazna prekidača. U stvari, ako postoji jedan poziv po ulaznom prekidaču i to rezultuje jednim pozivom po izlaznom prekidaču, onda prvih šesnaest poziva ovog hipotetičkog prekidača, zapravo blokira čak do petnaest dodatnih poziva kojima bi bile potrebne slične veze.

Iz ovog razloga, za „jednostavi povezani neblokirajući prekidač“, 16x16 prekidač, sa četiri ulazna potprekidača i četiri izlazna prekidača, smatralo se da zahteva 7 srednjih prekidača. Zbog toga, nekada se ovaj raspored naziva „2n-1 prekidač“, gde je n broj ulaznih potprekidača.

Primer je namerno mali i u tako malom primeru, reorganizacija ne čuva mnogo prekidača. 16x16 unakrsni ima 256 kontakata, dok 16x16 minimalni obuhvatni prekidač ima 4x4x4x3 = 192 kontakta. Stvarna telefonska centrala ima stotine hiljada ulaza i desetine miliona prekidačkih kontakata.

Upravljanje minimalnim obuhvatnim prekidačem

Presudno otkriće bio je novi način reorganizacije veza u srednjim prekidačima da „razmenjuju žice“, tako da bi nova konekcija mogla biti završena.

Prvi korak u neblokirajućem minimalnom obuhvatnom prekidačkom algoritmu, samo je naivna ranija shema (iznad): traži potprekidač srednjeg sloja koji ima potrebne ulazne i izlazne veze. Ako je pronađen potprekidač srednjeg sloja, koji povezuje oba potrebna ulazna i izlazna potprekidača, onda je alocirana i konekcija prolazi.

Međutim, pošto je broj srednjih potprekidača manji u minimalnom obuhvatnom prekidaču nego u „2n-1“ prekidaču, nekada je potraga neuspešna. Ako potprekidač sa potrebnim parom konekcija ne može biti pronađen, par potprekidača mora biti pronađen. Jedan potprekidač mora imati vezu sa odgovrajućim ulaznim prekidačem; drugi mora imati vezu sa odgovrajućim izlaznim potprekidačem. Ovi potprekidači moraju da postoje, jer za svaki ulaz u minimalni obuhvatni prekidač, postoji žica iz ulaznog potprekidača ka srednjem prekidaču. Pošto je ceo prekidač za telefonski sistem, takođe je i simetričan, tako da postoji i slobodna žica od jednog od prekidača srednjeg sloja ka odgovarajućem izlaznom potprekidaču.

Sada, konceptualno, algoritam mora da reorganizuje konekcije u ova dva srednja potprekidača (nazovimo ih A i B). Ideja je da se zadrže sve postojeće veze koje već prolaze kroz A i B, kako bi se izbeglo prekidanje poziva, a opet okupile ili u A ili u B dve žice koje vode ka odgovarajućim ulaznim i izlaznim potprekidačima.

U standardnom objašnjenju crtanjem, A i B se predstavljaju kao veze koje u stvari leže jedna na drugoj. Ulazi od A moraju da leže na odgovarajućim ulazim od B. Izlazi iz A moraju, takođe, da leže na odgovarajućim izlazima iz B.

Veze koje prolaze kroz A i B su smeštene u listu, koja takođe uključuje željene nove konekcije.

Prvo, svaka konekcija koja ima samo jedan ulaz ili samo jedan izlaz, crta se iznad A i B. Kod crtanju olovkom i papirom, onaj koji crta zapravo pomera olovku duž nacrtane veze.

Polazeći od nekog ulaza ili izlaza, crtač crta vezu ka izlazu, zatim crta drugu vezu od izlaza ka ulazu i tako dalje, sve dok ima veza.

Svaki put kada se crta od ulaza ka izlazu, konekcija se alocira ka potprekidaču A. Kada se crta u drugom smeru, konekcija se alocira ka B.

Kada više nema konekcija sa samo jednim ulazom ili samo jednim izlazom, sve što je ostalo su ciklični grafovi, odnosno „petlje“ konekcija. Ponovo, crta se svaki graf u potpunosti, dodeljuju se veze potprekidačima i uklanja svaka veza iz liste konekcija.

Manje beleženja se vodi ako se svi grafovi bez petlji (aciklični grafovi) crtaju i uklanjaju pre petlji (cikličnih grafova). Na taj način, ne mora se nikada proveravati nijedan ulaz ili izlaz više od dva puta i nema potrebe za čuvanjem liste sa ulazima i izlazima koji su ispitani.

Nije bitno da li A i B dobijaju određen smer crtanja, zato što imaju isti broj veza: jednu žicu ka svakom ulaznom i izlaznom potprekidaču.

Nakon što su veze alocirane u nizove u softveru, elektronika prekidača može zapravo biti reprogramirana, fizički pomerajući veze. Elektronski prekidači su dizajnirani sa namerom da novi podaci mogu svi biti zapisani u elektronici, a zatim proizvesti efekat sa jednim logičkim pulsom. Rezultat je da se konekcije pomeraju momentalno, sa neprimetnim prekidima u konverzaciji. U starijim elektromehaničkim prekidačima, mogao se povremeno čuti šum „prebacivanja“.

Algoritam je forma topološkog sortiranja i srž algoritma koji kontroliše minimalni obuhvatni prekidač.

Praktične implementacije prekidača

Čim je algoritam otkriven, Belovi sistemski inženjeri i menadžeri su započeli da diskutuju o njemu. Posle nekoliko godina, Belovi inženjeri započeli su dizajniranje elektromehaničkih prekidača koje bi algoritam mogao da kontroliše. U to vreme, računari su koristili vakuumske cevi i nisu bili dovoljno pouzdani da kontrolišu telefonski sistem (prekidači telefonskog sistema su kritični po pitanju sigurnosti i dizajnirani su tako da imaju neplanirano otkazivanje, otprilike jednom u trideset godina). Kompjuteri bazirani na relejima su bili prespori da implementiraju algoritam. Kako god, ceo sistem je mogao biti dizajniran tako da kada računari budu dovoljno pouzdani, mogu biti modifikovani za postojeći sistem prekidača.

Najzad, lock-step dualni računari su razvijeni korišćenjem tranzistora. U ovom sistemu, dva računara izvode svaki korak, proveravajući jedan drugog. Kada se ne bi složili, izvršili bi dijagnozu međusobno i računar koji je ispravno radio, preuzeo bi operaciju nad prekidačem, a drugi bi diskvalifikovao samog sebe i zatražio popravku.

Nije teško napraviti skup prekidača koji tolerišu greške. Kada se potprekidač pokvari, pozivalac jednostavno zove ponovo. Tako, sa svakom novom konekcijom, softver pokušava narednu slobodnu konekciju u svakom potprekidaču, radije nego da ponovo koristi poslednju oslobođenu. Verovatnije je da će nova veza raditi, jer koristi drugo kolo. Kako manje konekcija prolazi kroz potprekidač, softver usmerava više test signala kroz potprekidač ka uređaju za merenje i onda čita rezultate. Ovo ne prekida ranije pozive koji nastavljaju da rade. Ako test ne uspe, softver izoluje konkretno kolo, čitajući o otkazivanju iz nekoliko spoljašnjih prekidača. Zatim obeležava slobodna kola, u kolu koje otkazuje, kao zauzeta. Kako se pozivi koji koriste otkazano kolo završe, ova kola se takođe označavaju kao zauzeta. Malo kasnije, kada nijedan poziv ne prolazi kroz oštećeno kolo, kompjuter pali svetlo na ploči kola koje treba da bude zamenjeno i tehničari mogu da obave zamenu. Sledeći test uspeva, veze ka popravljenim potprekidačima su označene kao slobodne i prekidač se vraća punoj operaciji.

Dijagnoza na Belovim ranijim elektronskim prekidačima, zapravo bi upalila zeleno svetlo na svakoj dobro odštampanoj kolnoj ploči, a crveno svetlo na svakoj neuspelo odštampanoj kolnoj ploči. Odštampana kola su bila dizajnirana tako da mogu biti uklonjena i zamenjena bez isključivanje celog prekidača.

Konačni rezultat je bio Belov ''1ESS prekidač''. U početku je bio instaliran na udaljenim vodovima u velikim gradovima, na najtežim korišćenim delovima svake telefonske centrale. Na prvi Dan majki na koji su operisali s tim, Belov sistem je postavio rekord za ukupni mrežni kapacitet, oba u završenim pozivima i ukupan broj poziva u sekundi po prekidaču, što je rezultovalo rekordom za ukupni profit po vodu.

Moderni prekidači

Praktična implementacija prekidača može biti napravljena od neparnog broja slojeva manjih potprekidača. Konceptualno, unakrsni komutatori troslojnog prekidača mogu biti dalje rastavljeni na manje unakrsne komutatore. Mada svaki potprekidač ima ograničenu sposobnost multipleksovanja, kada rade zajedno, stvaraju efekat većeg NxN unakrsnog prekidača.

U modernom telefonskom kablu, korišćenje dva različita pristupa multipleksovanja drugim slojevima dalje smanjuje cenu svič fabrike:

1. prostorni multiplekseri su nešto kao već opisani unakrsni komutator ili neko njihovo grupisanje. Bilo koji pojedinačni izlaz može biti odabran iz bilo kog ulaza. U digitalnim prekidačima, ovo je obično jedno grupisanje I kola. 8000 puta u sekundi, veza se reprogramira da poveže određene žice za vreme jednog vremenskog odsečka. Prednost dizajna: u sistemu prostornog deljenja, broj konekcija se deli brojem vremenskih odsečaka u sistemu sa multipleksovanjem deljenjem vremena. Ovo značajno smanjuje veličinu i troškove svič fabrike. Takođe povećava pouzdanost, jer postoji daleko manje fizičkih konekcija koje bi mogle da padnu.
2. kod prekidača sa deljenjem vremena, svaki ima memoriju koja se u čita u fiksnom redosledu i piše se u programabilnom redosledu. Ovaj tip prekidača permutuje vremenske odsečke u signal koji se multipleksuje deljenjem vremena, koji ide ka prostornim multiplekserima u susednim slojevima. Prednost dizajna: prekidači sa vremenskim multiplekserima imaju samo jednu ulaznu i izlaznu žicu. Pošto imaju daleko manje električnih veza koje bi mogle da padnu, oni su daleko pouzdaniji od prostornih multipleksera i zbog toga se češće koriste za spoljašnje (ulazne i izlazne) slojeve modernih telefonskih centrala.

Nedostajući resursi u telefonskoj centrali su veze između slojeva potprekidača. Kontrolna logika mora da alocira ove veze, a osnovni metod je opisani algoritam. Potprekidači su logički raspoređeni tako da sintetizuju veće potprekidače. Svaki potprekidač, kao i sintetizovani potprekidač, kontroliše (rekurzivno) gore pomenuti algoritam.

Vidi još

• Unakrsni komutator
• Svič fabrika
• Clos mreža