Неблокирующий переключатель минимального диапазона — это устройство, которое может соединять N входов с N выходами в любой комбинации. Наиболее распространенное применение коммутаторов этого типа – на телефонных станциях . Термин «неблокирующий» означает, что, если он исправен, он всегда может установить соединение. Термин «минимальный» означает, что он имеет наименьшее количество возможных компонентов и, следовательно, минимальный расход.
Исторически в телефонных коммутаторах соединения между абонентами осуществлялись с помощью больших и дорогих блоков электромеханических реле , переключателей Строугера . Основное математическое свойство переключателей Строугера заключается в том, что для каждого входа переключателя имеется ровно один выход. Большая часть математической теории переключающих схем пытается использовать это свойство для уменьшения общего количества переключателей, необходимых для подключения комбинации входов к комбинации выходов.
В 1940-х и 1950-х годах инженеры Bell Lab начали расширенную серию математических исследований методов уменьшения размера и стоимости « коммутируемой структуры », необходимой для реализации телефонной станции. Один из первых успешных математических анализов был выполнен Чарльзом Клосом ( французское произношение: [ʃaʁl klo] ), а коммутируемая структура, состоящая из меньших коммутаторов, называется сетью Clos . [1]
Ригельный переключатель обладает свойством подключать N входов к N выходам в любой взаимно-однозначной комбинации, поэтому он может подключить любого вызывающего абонента к любому незанятому получателю, и это свойство соответствует техническому термину «неблокируемый». Будучи неблокирующим, он всегда мог завершить вызов (незанятому получателю), что максимизировало бы доступность услуги.
Однако перекрестный переключатель делает это за счет использования N 2 (N в квадрате) простых однополюсных переключателей . Для больших N (а практические требования телефонного коммутатора считаются большими) такой рост оказался слишком дорогим. Кроме того, у больших перекладинных переключателей были физические проблемы. Мало того, что переключатель требовал слишком много места, металлические стержни, содержащие контакты переключателя, становились настолько длинными, что провисали и становились ненадежными. Инженеры также заметили, что в любой момент времени каждая планка ригельного переключателя осуществляла только одно соединение. Остальные контакты на двух планках не использовались. Казалось, это означало, что большая часть коммутационной ткани поперечного переключателя была потрачена впустую.
Очевидным способом имитации поперечного переключателя было найти способ собрать его из поперечных переключателей меньшего размера. Если перекладинный переключатель можно было бы имитировать с помощью некоторого расположения перекладин меньшего размера, то эти меньшие поперечины, в свою очередь, могли бы также имитироваться еще меньшими поперечинами. Коммутационная фабрика может стать очень эффективной и, возможно, даже создаваться из стандартизированных частей. Это называется сетью Clos .
Следующий подход заключался в том, чтобы разбить перекрестный переключатель на три слоя более мелких перекрестных переключателей. Будет «входной уровень», «средний уровень» и «выходной уровень». Коммутаторы меньшего размера менее массивны, более надежны и, как правило, проще в сборке и, следовательно, менее дороги.
Телефонной системе достаточно установить соединение один к одному. Интуитивно это означает, что количество входов и количество выходов всегда могут быть равны в каждом субпереключателе, но интуиция не доказывает, что это возможно, и не говорит нам, как это сделать. Предположим, мы хотим синтезировать ригельный переключатель 16 на 16. Конструкция может иметь 4 дополнительных переключателя на входной стороне, каждый с 4 входами, всего 16 входов. Кроме того, на стороне выхода мы также можем иметь 4 выходных переключателя, каждый с 4 выходами, всего 16 выходов. Желательно, чтобы в конструкции использовалось как можно меньше проводов, ведь провода стоят реальных денег. Наименьшее возможное количество проводов, которыми можно соединить два субпереключателя, — это один провод. Таким образом, каждый входной дополнительный переключатель будет иметь один провод к каждому среднему переключателю. Кроме того, каждый средний субпереключатель будет иметь один провод к каждому выходному субпереключателю.
Вопрос в том, сколько средних переключателей необходимо и, следовательно, сколько всего проводов должно соединить входной уровень со средним уровнем. Поскольку телефонные переключатели симметричны (вызывающие и вызываемые абоненты взаимозаменяемы), к выходному слою будет применена та же логика, а средние подпереключатели будут «квадратными», имеющими то же количество входов, что и выходов.
Количество средних подпереключателей зависит от алгоритма, используемого для выделения им соединения. Основной алгоритм управления трехуровневым коммутатором заключается в поиске среди средних подпереключателей среднего подпереключателя, имеющего неиспользуемые провода к нужным входным и выходным переключателям. Как только подключаемый средний дополнительный переключатель найден, подключение к правильным входам и выходам входных и выходных переключателей становится тривиальным.
Теоретически в примере необходимы только четыре центральных переключателя, каждый из которых имеет ровно одно соединение с каждым входным переключателем и одно соединение с каждым выходным переключателем. Это называется «минимальным переключателем», и управление им было Святым Граалем исследований Bell Labs.
Однако небольшая работа с карандашом и бумагой покажет, что такой минимальный переключатель легко получить в условиях, когда ни один средний переключатель не имеет соединения одновременно с необходимым входным переключателем и необходимым выходным переключателем. Чтобы частично заблокировать переключатель, достаточно четырех вызовов. Если входной переключатель наполовину заполнен, он подключается через два средних переключателя. Если выходной переключатель также наполовину заполнен соединениями от двух других средних переключателей, то не останется среднего переключателя, который мог бы обеспечить путь между этим входом и выходом.
По этой причине считалось, что для «просто подключаемого неблокирующего переключателя» 16x16 с четырьмя входными вспомогательными переключателями и четырьмя выходными переключателями требуется 7 средних переключателей; в худшем случае почти полный входной дополнительный переключатель будет использовать три средних переключателя, почти полный выходной дополнительный переключатель будет использовать три разных, а седьмой будет гарантированно свободен для выполнения последнего соединения. По этой причине иногда такое расположение переключателей называют «переключателем 2 n -1», где n — количество входных портов входных подпереключателей.
Пример намеренно небольшой, и в таком маленьком примере реорганизация не спасает многих переключателей. Перекладина 16×16 имеет 256 контактов, а переключатель минимального пролета 16×16 имеет 4×4×4×3 = 192 контакта.
По мере того, как цифры становятся больше, экономия увеличивается. Например, для обмена на 10 000 линий потребуется 100 миллионов контактов для реализации полной перекрестной панели. Но три слоя из 100 субпереключателей 100×100 будут использовать только 300 10 000 контактных субпереключателей, или 3 миллиона контактов.
Каждый из этих подпереключателей может, в свою очередь, состоять из перекладин 3×10 и 10×10, всего 3000 контактов, что составляет 900 000 для всей станции; это гораздо меньше, чем 100 миллионов.
Решающим открытием стал способ реорганизовать соединения средних переключателей в «торговые провода», чтобы можно было установить новое соединение.
Первый шаг — найти неиспользуемую ссылку от входного подпереключателя к подпереключателю среднего уровня (который мы назовем A) и неиспользуемую ссылку от подпереключателя среднего уровня (который мы назовем B) к желаемому выходному подпереключателю. Поскольку до прихода нового соединения входной и выходной подпереключатели имели хотя бы одно неиспользуемое соединение, оба этих неиспользуемых канала должны существовать.
Если A и B являются одним и тем же коммутатором среднего уровня, то соединение может быть установлено немедленно, как и в случае с коммутатором «2 n −1». Однако если A и B — разные подкоммутаторы среднего уровня, потребуется дополнительная работа. Алгоритм находит новое расположение соединений через средние переключатели A и B, которое включает в себя все существующие соединения, а также желаемое новое соединение.
Составьте список всех желаемых соединений, которые проходят через A или B. То есть все существующие соединения, которые необходимо сохранить, и новое соединение. Сам алгоритм заботится только о внутренних соединениях между входом и выходом переключателя, хотя практическая реализация также должна отслеживать правильные соединения входного и выходного переключателя.
В этом списке каждый входной вспомогательный переключатель может присутствовать не более чем в двух соединениях: одно с вспомогательным переключателем A и одно с вспомогательным переключателем B. Возможные варианты: ноль, один или два. Аналогично, каждый выходной дополнительный переключатель появляется не более чем в двух соединениях.
Каждое соединение связано не более чем с двумя другими с помощью общего входного или выходного переключателя, образуя одно звено в «цепочке» соединений.
Далее начните с нового соединения. Назначьте ему путь от входного субпереключателя через средний субпереключатель A до выходного субпереключателя. Если выходной дополнительный переключатель этого первого соединения имеет второе соединение, назначьте этому второму соединению путь от его входного дополнительного переключателя через дополнительный переключатель B. Если этот входной дополнительный переключатель имеет другое соединение, назначьте этому третьему соединению путь через дополнительный переключатель A. Продолжайте таким же образом вперед и назад. , чередуя средние переключатели A и B. В конечном итоге должно произойти одно из двух:
В первом случае вернитесь к входному подпереключателю нового соединения и проследите его цепочку назад, назначая соединения путям через средние подпереключатели B и A в той же чередующейся схеме.
При этом через каждый входной или выходной подпереключатель в цепи проходит не более двух соединений, и они назначаются разным средним переключателям. Таким образом, все необходимые ссылки доступны.
Могут быть дополнительные соединения через подпереключатели A и B, которые не являются частью цепи, включающей новое соединение; эти соединения можно оставить как есть.
После того, как новая схема подключения будет разработана в программном обеспечении, электронику переключателя можно фактически перепрограммировать, физически перемещая соединения. Электронные переключатели спроектированы так, что новую конфигурацию можно записать в электронику, не нарушая существующее соединение, а затем вступить в силу с помощью одного логического импульса. В результате соединение устанавливается мгновенно, с незаметным прерыванием разговора. В старых электромеханических переключателях иногда можно было услышать лязг «шума переключения».
Этот алгоритм представляет собой разновидность топологической сортировки и является сердцем алгоритма, управляющего переключателем минимального охвата.
Как только алгоритм был обнаружен, системные инженеры и менеджеры Bell начали его обсуждать. Через несколько лет инженеры Bell приступили к разработке электромеханических переключателей, которыми можно было бы управлять. В то время в компьютерах использовались трубки , и они были недостаточно надежны для управления телефонной системой (переключатели телефонной системы критически важны с точки зрения безопасности и рассчитаны на незапланированный отказ примерно раз в тридцать лет). Релейные компьютеры были слишком медленными для реализации алгоритма. Однако всю систему можно было спроектировать так, чтобы, когда компьютеры станут достаточно надежными, их можно было модернизировать в существующие системы коммутации.
Сделать отказоустойчивыми композитные коммутаторы несложно . Когда подпереключатель выходит из строя, вызывающие абоненты просто повторно набирают номер. Таким образом, при каждом новом подключении программное обеспечение пробует следующее свободное соединение в каждом субкоммутаторе, а не повторно использует последнее выпущенное соединение. Новое соединение с большей вероятностью сработает, поскольку в нем используется другая схема.
Следовательно, в занятом коммутаторе, когда на конкретной плате отсутствуют какие-либо соединения, она является отличным кандидатом для тестирования.
Для проверки или вывода из эксплуатации той или иной печатной платы существует известный алгоритм. Поскольку через дополнительный переключатель карты проходит меньше соединений, программное обеспечение направляет больше тестовых сигналов через дополнительный переключатель на измерительное устройство, а затем считывает результаты измерений. Это не прерывает старые вызовы, которые продолжают работать.
Если тест не пройден, программное обеспечение изолирует конкретную печатную плату, считывая информацию о неисправности с нескольких внешних переключателей. Затем он помечает свободные цепи в неисправной схеме как занятые. Когда вызовы, использующие неисправную схему, завершаются, эти линии также помечаются как занятые. Некоторое время спустя, когда через неисправную схему не проходят никакие вызовы, компьютер загорается на плате, требующей замены, и технический специалист может заменить плату. Вскоре после замены следующий тест завершается успешно, соединения отремонтированного субпереключателя помечаются как «не заняты», и коммутатор возвращается к полной работе.
Диагностика первых электронных переключателей Bell фактически загорала зеленый свет на каждой исправной печатной плате и красный свет на каждой вышедшей из строя печатной плате. Печатные схемы были разработаны таким образом, чтобы их можно было снимать и заменять, не выключая весь переключатель.
Конечным результатом стал Bell 1ESS . Этим управлял центральный процессор, называемый Central Control (CC), двойной компьютер с синхронизированной гарвардской архитектурой , использующий надежную диодно-транзисторную логику . В ЦП 1ESS два компьютера выполняли каждый шаг, проверяя друг друга. Если они не соглашались, они диагностировали себя, и правильно работающий компьютер принимался за работу переключателя, в то время как другой дисквалифицировал себя и требовал ремонта. По состоянию на 2012 год коммутатор 1ESS все еще использовался ограниченно и имел подтвержденную надежность менее одного внепланового часа отказа за каждые тридцать лет работы, что подтверждает его конструкцию.
Первоначально он был установлен на междугородных магистралях в крупных городах, наиболее загруженных частях каждой телефонной станции. В первый День матери, когда с ней работали крупные города, система Bell установила рекорд общей пропускной способности сети, как по количеству завершенных вызовов, так и по общему количеству вызовов в секунду на коммутатор. Это привело к рекордному общему доходу на одну магистраль.
Практическая реализация переключателя может быть создана из нечетного числа слоев более мелких подпереключателей. Концептуально каждый поперечный переключатель трехступенчатого переключателя можно дополнительно разложить на более мелкие перекрестные переключатели. Хотя каждый субпереключатель имеет ограниченные возможности мультиплексирования, работая вместе, они синтезируют эффект более крупного перекрестного переключателя N × N.
В современном цифровом телефонном коммутаторе применение двух различных подходов к мультиплексированию на чередующихся уровнях еще больше снижает стоимость коммутационной структуры:
Практичные цифровые телефонные коммутаторы минимизируют размер и стоимость электроники. Во-первых, обычно коммутатор «складывают», так что входные и выходные соединения с абонентской линией обрабатываются одной и той же логикой управления. Затем на внешнем уровне используется переключатель временного разделения. Внешний уровень реализован в интерфейсных картах абонентских линий (SLIC) в уличных ящиках местного присутствия. Под дистанционным управлением с центрального коммутатора карты подключаются к временным слотам по линии с временным мультиплексированием, ведущей к центральному коммутатору. В США мультиплексная линия кратна линии Т-1 . В Европе и многих других странах она кратна линии Е-1 .
Дефицитные ресурсы телефонного коммутатора — это соединения между уровнями подкоммутаторов. Эти соединения могут быть либо временными интервалами, либо проводными, в зависимости от типа мультиплексирования. Логика управления должна распределять эти связи, и основным методом является уже рассмотренный алгоритм. Субпереключатели логически организованы таким образом, что они синтезируют более крупные подпереключатели. Каждый субпереключатель и синтезированный субпереключатель управляются ( рекурсивно ) логикой, полученной на основе математики Клоса. Компьютерный код разбивает большие мультиплексоры на меньшие мультиплексоры.
Если рекурсию довести до предела, разбивая перекладину до минимально возможного числа переключающих элементов, полученное устройство иногда называют кроссоверным переключателем или баньяновым переключателем в зависимости от его топологии.
Коммутаторы обычно взаимодействуют с другими коммутаторами и оптоволоконными сетями через быстрые мультиплексированные линии передачи данных, такие как SONET .
Каждая линия коммутатора может периодически проверяться компьютером, отправляя через него тестовые данные. Если линия коммутатора выходит из строя, все линии коммутатора помечаются как используемые. Линии мультиплексора распределяются по принципу «первым пришел — первым вышел», так что новые соединения находят новые коммутационные элементы. Когда все соединения неисправного переключателя отключены, неисправного переключателя можно избежать и позже заменить.
По состоянию на 2018 год такие выключатели больше не производятся. На смену им приходят высокоскоростные маршрутизаторы Интернет-протокола .
