Неблокирајући минимални обухватни прекидач

Неблокирајући минимални обухватни прекидач је уређај који може да повеже Н улаза са Н излаза у било којој комбинацији. Најпознатија употреба прекидача овог типа је у телефонској централи. Израз „неблокирајући“ значи да ако није оштећен, увек може да остварује конекцију. Израз „минимални“ значи да има најмањи могући број компонената, а због тога и минималне трошкове.

Замена за 16x16 унакрсни комутатор, направљена од 12 4x4 унакрсна комутатора.

Историјски, у телефонским централама, везе између оних који телефонирају су биле уређене са великим, скупим банкама електромеханичких релеја, ''Строwгер прекидача''. Основно математичко својство Строwгер прекидача је да за сваки улаз у прекидач, постоји тачно један излаз. Многе математичке теорије о прекидачким колима настоје да искористе ову особину како би смањиле укупан број прекидача потребних да се повеже једна комбинација улаза са једном комбинацијом излаза.

1940-их и 1950-их, инжењери у Беловим лаобораторијама су започели проширену серију математичких истраживања, у оквиру метода за смањивање величине и потрошње ''свич фабрике'', потребне за имплементацију телефонске централе. Једну ранију, успешну математичку анализу, извео је Цхарлес Цлос и свич фабрика, конструисана од мањих прекидача, названа је ''цлос мрежа''.

Позадина: прекидачке топологије

Унакрсни комутатор

Унакрсни комутатор је у стању да повеже Н улаза са Н излаза у било којој један-на-један комбинацији, тако да може да повеже било ког позиваоца са било којим слободним пријемником и то својство је технички названо „неблокирајуће“. Ако је неблокирајући, то значи да би увек могао да успостави позив (слободном пријемнику), што би максимизовало доступност сервиса.

Како год, унакрсни комутатор ово ради трошећи Н² једноставних прекидача. За велико Н (а практичне потребе телефонске централе се сматрају великим), овај раст је био превише скуп. Даље, унакрсни комутатор је имао физичких проблема. Не само што је захтевао превише простора, већ би и метални проводници који садрже прекидаче постали тако дугачки да би попустили и постали непоуздани. Инжењери су такође приметили да је у било ком тренутку, сваки проводник са унакрсним прекидачем успостављао само једну конекцију. Остали контакти на два проводника су били неискоришћени. Ово је наговештавало да ће већина проводника свич фабрике остајати неискоришћена.

Очигледан начин да се симулира унакрсни комутатор, био је да се пронађе неко решење, тако да се он изгради од мањих унакрсних комутатора. Ако би он могао да се опонаша неким обликом груписања мањих унакрсних комутатора, онда би ови мањи, такође могли да се симулирају још мањим. Свич фабрика би могла да постане веома ефикасна и вероватно направљена од стандардизованих делова. Ово се назива цлос мрежа.

Потпуно повезани трослојни прекидачи

Наредни приступ био је разбијање унакрсног комутатора на три слоја мањих унакрсних комутатора. Ту је постојао „улазни слој“, „средњи слој“ и „излазни слој“. Мањи прекидачи су мање тежине, поузданији и генерерално лакши за прављење, а самим тим и јефтинији.

Телефонски систем једино треба да направи један-на-један конекцију. Интуитивно, на основу овога се чини да би број улаза и број излаза увек могао да буде једнак у сваком потпрекидачу, али интуиција не доказује ово, нити нам говори како то да постигнемо. Претпоставимо да желимо да синтетизујемо 16 по 16 унакрсних комутатора. Овај дизајн би могао да има 4 потпрекидача на улазној страни, сваки са 4 улаза, за укупно 16 улаза. Даље, на излазној страни, могли бисмо такође да имамо 4 излазна потпрекидача, сваки са 4 излаза, за укупно 16 излаза. Пожељно је да дизајн користи што мање жица, јер су оне прилично скупе. Дакле, најмањи могући број жица које могу да повежу два потпрекидача у једну жицу. Овако, сваки улазни потпрекидач ће имати једну жицу ка сваком средњем потпрекидачу. Такође, сваки средњи потпрекидач ће имати једну жицу ка сваком излазном потпрекидачу.

Питање је колико средњих потпрекидача је потребно и отуда, колико укупно жица би требало да повезује улазни слој са излазним. Пошто су телефонски прекидачи симетрични (позиваоци и пријемници су замењиви), иста логика се примењује и на излазни слој и средњи потпрекидачи ће бити „квадратни“, имаће исти број улаза и излаза.

Број средњих потпрекидача зависи од алгоритма коришћеног за алоцирање везе ка њима. Основни алгоритам за управљање трослојним прекидачем је тражење средњег потпрекидача који има неискоришћене жице за потребне улазне и излазне прекидаче. Једном када се пронађе средњи прекидач способан за конекцију, повезивање са правим улазима и излазима, у улазним и излазним прекидачима је тривијално.

Теоретски, у примеру, потребана су само четири централна прекидача, сваки са тачно једном везом са сваким улазним прекидачем и са једном везом са сваким излазним прекидачем. Ово се назива „минимални обухватни прекидач“ и руковођење овим, био је свети грал истраге Белових лабораторија.

Како год, уз мало посла са оловком и папиром показаће се да је лако добити овакав минимални прекидач, у стању у ком ниједан средњи прекидач нема везу са оба потребна улазна и излазна прекидача. У ствари, ако постоји један позив по улазном прекидачу и то резултује једним позивом по излазном прекидачу, онда првих шеснаест позива овог хипотетичког прекидача, заправо блокира чак до петнаест додатних позива којима би биле потребне сличне везе.

Из овог разлога, за „једностави повезани неблокирајући прекидач“, 16x16 прекидач, са четири улазна потпрекидача и четири излазна прекидача, сматрало се да захтева 7 средњих прекидача. Због тога, некада се овај распоред назива „2н-1 прекидач“, где је н број улазних потпрекидача.

Пример је намерно мали и у тако малом примеру, реорганизација не чува много прекидача. 16x16 унакрсни има 256 контаката, док 16x16 минимални обухватни прекидач има 4x4x4x3 = 192 контакта. Стварна телефонска централа има стотине хиљада улаза и десетине милиона прекидачких контаката.

Управљање минималним обухватним прекидачем

Пресудно откриће био је нови начин реорганизације веза у средњим прекидачима да „размењују жице“, тако да би нова конекција могла бити завршена.

Први корак у неблокирајућем минималном обухватном прекидачком алгоритму, само је наивна ранија схема (изнад): тражи потпрекидач средњег слоја који има потребне улазне и излазне везе. Ако је пронађен потпрекидач средњег слоја, који повезује оба потребна улазна и излазна потпрекидача, онда је алоцирана и конекција пролази.

Међутим, пошто је број средњих потпрекидача мањи у минималном обухватном прекидачу него у „2н-1“ прекидачу, некада је потрага неуспешна. Ако потпрекидач са потребним паром конекција не може бити пронађен, пар потпрекидача мора бити пронађен. Један потпрекидач мора имати везу са одговрајућим улазним прекидачем; други мора имати везу са одговрајућим излазним потпрекидачем. Ови потпрекидачи морају да постоје, јер за сваки улаз у минимални обухватни прекидач, постоји жица из улазног потпрекидача ка средњем прекидачу. Пошто је цео прекидач за телефонски систем, такође је и симетричан, тако да постоји и слободна жица од једног од прекидача средњег слоја ка одговарајућем излазном потпрекидачу.

Сада, концептуално, алгоритам мора да реорганизује конекције у ова два средња потпрекидача (назовимо их А и Б). Идеја је да се задрже све постојеће везе које већ пролазе кроз А и Б, како би се избегло прекидање позива, а опет окупиле или у А или у Б две жице које воде ка одговарајућим улазним и излазним потпрекидачима.

У стандардном објашњењу цртањем, А и Б се представљају као везе које у ствари леже једна на другој. Улази од А морају да леже на одговарајућим улазим од Б. Излази из А морају, такође, да леже на одговарајућим излазима из Б.

Везе које пролазе кроз А и Б су смештене у листу, која такође укључује жељене нове конекције.

Прво, свака конекција која има само један улаз или само један излаз, црта се изнад А и Б. Код цртању оловком и папиром, онај који црта заправо помера оловку дуж нацртане везе.

Полазећи од неког улаза или излаза, цртач црта везу ка излазу, затим црта другу везу од излаза ка улазу и тако даље, све док има веза.

Сваки пут када се црта од улаза ка излазу, конекција се алоцира ка потпрекидачу А. Када се црта у другом смеру, конекција се алоцира ка Б.

Када више нема конекција са само једним улазом или само једним излазом, све што је остало су циклични графови, односно „петље“ конекција. Поново, црта се сваки граф у потпуности, додељују се везе потпрекидачима и уклања свака веза из листе конекција.

Мање бележења се води ако се сви графови без петљи (ациклични графови) цртају и уклањају пре петљи (цикличних графова). На тај начин, не мора се никада проверавати ниједан улаз или излаз више од два пута и нема потребе за чувањем листе са улазима и излазима који су испитани.

Није битно да ли А и Б добијају одређен смер цртања, зато што имају исти број веза: једну жицу ка сваком улазном и излазном потпрекидачу.

Након што су везе алоциране у низове у софтверу, електроника прекидача може заправо бити репрограмирана, физички померајући везе. Електронски прекидачи су дизајнирани са намером да нови подаци могу сви бити записани у електроници, а затим произвести ефекат са једним логичким пулсом. Резултат је да се конекције померају моментално, са неприметним прекидима у конверзацији. У старијим електромеханичким прекидачима, могао се повремено чути шум „пребацивања“.

Алгоритам је форма тополошког сортирања и срж алгоритма који контролише минимални обухватни прекидач.

Практичне имплементације прекидача

Чим је алгоритам откривен, Белови системски инжењери и менаџери су започели да дискутују о њему. После неколико година, Белови инжењери започели су дизајнирање електромеханичких прекидача које би алгоритам могао да контролише. У то време, рачунари су користили вакуумске цеви и нису били довољно поуздани да контролишу телефонски систем (прекидачи телефонског система су критични по питању сигурности и дизајнирани су тако да имају непланирано отказивање, отприлике једном у тридесет година). Компјутери базирани на релејима су били преспори да имплементирају алгоритам. Како год, цео систем је могао бити дизајниран тако да када рачунари буду довољно поуздани, могу бити модификовани за постојећи систем прекидача.

Најзад, лоцк-степ дуални рачунари су развијени коришћењем транзистора. У овом систему, два рачунара изводе сваки корак, проверавајући један другог. Када се не би сложили, извршили би дијагнозу међусобно и рачунар који је исправно радио, преузео би операцију над прекидачем, а други би дисквалификовао самог себе и затражио поправку.

Није тешко направити скуп прекидача који толеришу грешке. Када се потпрекидач поквари, позивалац једноставно зове поново. Тако, са сваком новом конекцијом, софтвер покушава наредну слободну конекцију у сваком потпрекидачу, радије него да поново користи последњу ослобођену. Вероватније је да ће нова веза радити, јер користи друго коло. Како мање конекција пролази кроз потпрекидач, софтвер усмерава више тест сигнала кроз потпрекидач ка уређају за мерење и онда чита резултате. Ово не прекида раније позиве који настављају да раде. Ако тест не успе, софтвер изолује конкретно коло, читајући о отказивању из неколико спољашњих прекидача. Затим обележава слободна кола, у колу које отказује, као заузета. Како се позиви који користе отказано коло заврше, ова кола се такође означавају као заузета. Мало касније, када ниједан позив не пролази кроз оштећено коло, компјутер пали светло на плочи кола које треба да буде замењено и техничари могу да обаве замену. Следећи тест успева, везе ка поправљеним потпрекидачима су означене као слободне и прекидач се враћа пуној операцији.

Дијагноза на Беловим ранијим електронским прекидачима, заправо би упалила зелено светло на свакој добро одштампаној колној плочи, а црвено светло на свакој неуспело одштампаној колној плочи. Одштампана кола су била дизајнирана тако да могу бити уклоњена и замењена без искључивање целог прекидача.

Коначни резултат је био Белов ''1ЕСС прекидач''. У почетку је био инсталиран на удаљеним водовима у великим градовима, на најтежим коришћеним деловима сваке телефонске централе. На први Дан мајки на који су оперисали с тим, Белов систем је поставио рекорд за укупни мрежни капацитет, оба у завршеним позивима и укупан број позива у секунди по прекидачу, што је резултовало рекордом за укупни профит по воду.

Модерни прекидачи

Практична имплементација прекидача може бити направљена од непарног броја слојева мањих потпрекидача. Концептуално, унакрсни комутатори трослојног прекидача могу бити даље растављени на мање унакрсне комутаторе. Мада сваки потпрекидач има ограничену способност мултиплексовања, када раде заједно, стварају ефекат већег НxН унакрсног прекидача.

У модерном телефонском каблу, коришћење два различита приступа мултиплексовања другим слојевима даље смањује цену свич фабрике:

1. просторни мултиплексери су нешто као већ описани унакрсни комутатор или неко њихово груписање. Било који појединачни излаз може бити одабран из било ког улаза. У дигиталним прекидачима, ово је обично једно груписање I кола. 8000 пута у секунди, веза се репрограмира да повеже одређене жице за време једног временског одсечка. Предност дизајна: у систему просторног дељења, број конекција се дели бројем временских одсечака у систему са мултиплексовањем дељењем времена. Ово значајно смањује величину и трошкове свич фабрике. Такође повећава поузданост, јер постоји далеко мање физичких конекција које би могле да падну.
2. код прекидача са дељењем времена, сваки има меморију која се у чита у фиксном редоследу и пише се у програмабилном редоследу. Овај тип прекидача пермутује временске одсечке у сигнал који се мултиплексује дељењем времена, који иде ка просторним мултиплексерима у суседним слојевима. Предност дизајна: прекидачи са временским мултиплексерима имају само једну улазну и излазну жицу. Пошто имају далеко мање електричних веза које би могле да падну, они су далеко поузданији од просторних мултиплексера и због тога се чешће користе за спољашње (улазне и излазне) слојеве модерних телефонских централа.

Недостајући ресурси у телефонској централи су везе између слојева потпрекидача. Контролна логика мора да алоцира ове везе, а основни метод је описани алгоритам. Потпрекидачи су логички распоређени тако да синтетизују веће потпрекидаче. Сваки потпрекидач, као и синтетизовани потпрекидач, контролише (рекурзивно) горе поменути алгоритам.

Види још

• Унакрсни комутатор
• Свич фабрика
• Цлос мрежа