Неблокирующий переключатель минимального диапазона - Nonblocking minimal spanning switch

Заменитель 16х16 поперечный переключатель из 12 перекладин 4х4.

А неблокирующий переключатель минимального охвата это устройство, которое может подключать N входов к N выходам в любой комбинации. Наиболее часто переключатели этого типа используются в обмен телефонами. Термин «неблокирующий» означает, что если он исправен, он всегда может установить соединение. Термин «минимальный» означает, что он имеет минимально возможное количество компонентов и, следовательно, минимальные затраты.

Исторически сложилось так, что в телефонных коммутаторах соединения между вызывающими абонентами выполнялись с помощью больших дорогих блоков электромеханических реле, Переключатели Strowger. Основное математическое свойство переключателей Строуджера состоит в том, что на каждый вход переключателя приходится ровно один выход. Большая часть математических теория коммутационных цепей пытается использовать это свойство для уменьшения общего количества переключателей, необходимых для соединения комбинации входов с комбинацией выходов.

В 1940-х и 1950-х годах инженеры Bell Laboratories начал расширенную серию математических исследований методов уменьшения размера и затрат "коммутируемая ткань «необходимо было реализовать телефонную станцию. Один из первых успешных математических анализов был проведен Чарльзом Клосом (Французское произношение:[aʁl klo]), а коммутируемая матрица, состоящая из коммутаторов меньшего размера, называется Сеть Clos.^[1]

Предпосылки: переключение топологий

Переключатель перекладины

В поперечный переключатель имеет свойство подключать N входов к N выходам в любом один к одному комбинация, поэтому он может подключить любого вызывающего абонента к любому незанятому получателю, свойство, получившее технический термин «неблокирующий». Будучи неблокирующим, он всегда мог завершить вызов (незанятому получателю), что увеличило бы доступность услуги.

Однако поперечный переключатель делает это за счет использования N² (N в квадрате) простой Переключатели SPST. Для большого N (а практические требования к телефонному коммутатору считаются большими) такой рост был слишком дорогим. Кроме того, у больших переключателей на перекладине были физические проблемы. Для переключателя требовалось не только слишком много места, но и металлические стержни, содержащие контакты переключателя, становились настолько длинными, что прогибались и становились ненадежными. Инженеры также заметили, что в любое время каждая планка перекрестного переключателя выполняла только одно соединение. Остальные контакты на двух планках не использовались. Это, по-видимому, означало, что большая часть коммутационной ткани поперечного переключателя была потрачена впустую.

Очевидным способом имитации перекрестного переключателя было найти способ построить его из меньших переключающих перекладин. Если поперечный переключатель может быть эмулирован некоторым расположением поперечных переключателей меньшего размера, то эти меньшие поперечные переключатели также могут быть эмулированы еще меньшими поперечными переключателями. Коммутационная матрица может стать очень эффективной и, возможно, даже быть создана из стандартизованных частей. Это называется Сеть Clos.

Полностью подключенные трехуровневые переключатели

Следующий подход заключался в том, чтобы разделить перекладину на три слоя более мелких перекладин. Будет «входной уровень», «средний уровень» и «выходной уровень». Коммутаторы меньшего размера менее массивны, более надежны и, как правило, проще в сборке и, следовательно, менее дороги.

Телефонная система должна устанавливать соединение только один на один. Интуитивно кажется, что это означает, что количество входов и выходов всегда может быть равным в каждом субпереключателе, но интуиция не доказывает, что это возможно, и не говорит нам, как это сделать. Предположим, мы хотим синтезировать переключающий переключатель 16 на 16. Конструкция может иметь 4 субпереключателя на входной стороне, каждый с 4 входами, всего 16 входов. Кроме того, на стороне выхода у нас также может быть 4 субпереключателя выхода, каждый с 4 выходами, всего 16 выходов. Желательно, чтобы в конструкции использовалось как можно меньше проводов, потому что провода стоят реальных денег. Наименьшее возможное количество проводов, которые могут соединить два субвитча, - это один провод. Таким образом, каждый входной субпереключатель будет иметь один провод к каждому среднему субпереключателю. Кроме того, у каждого промежуточного переключателя будет один провод к каждому выходному переключателю.

Вопрос в том, сколько промежуточных переключателей необходимо и, следовательно, сколько всего проводов должно соединить входной уровень со средним уровнем. Поскольку телефонные коммутаторы симметричны (вызывающие и вызываемые абоненты взаимозаменяемы), та же логика будет применяться к уровню вывода, а средние субкоммутаторы будут «квадратными», имея такое же количество входов, что и выходы.

Количество средних субкоммутаторов зависит от алгоритма, используемого для выделения им соединения. Базовый алгоритм управления трехуровневым переключателем заключается в поиске промежуточных переключателей среднего переключателя, у которого есть неиспользуемые провода к необходимым переключателям входа и выхода. Как только подключаемый средний субпереключатель найден, подключение к правильным входам и выходам в переключателях входа и выхода становится тривиальным.

Теоретически в этом примере необходимы только четыре центральных переключателя, каждый с ровно одним подключением к каждому входному переключателю и по одному подключению к каждому выходному переключателю. Это называется «переключателем минимального охвата», и управление им было святым Граалем исследований Bell Labs.

Однако небольшая работа с карандашом и бумагой покажет, что такой минимальный переключатель легко получить в условиях, в которых ни один средний переключатель не подключен одновременно к необходимому входному переключателю и нужному выходному переключателю. Чтобы частично заблокировать коммутатор, достаточно четырех вызовов. Если входной переключатель наполовину заполнен, он подключается через два средних переключателя. Если выходной переключатель также наполовину заполнен соединениями от двух других средних переключателей, то не остается среднего переключателя, который мог бы обеспечить путь между этим входом и выходом.

По этой причине считалось, что для «односвязного неблокирующего переключателя» 16x16 с четырьмя входными субпереключателями и четырьмя выходными переключателями потребуется 7 средних переключателей; в худшем случае почти полный входной субпереключатель будет использовать три средних переключателя, почти полный выходной субпереключатель будет использовать три разных, а седьмой гарантированно будет свободен для последнего подключения. По этой причине иногда такое расположение переключателей называют "2п−1 switch », где п - количество входных портов входных субпереключателей.

Пример намеренно небольшой, и в таком маленьком примере реорганизация не спасает много переключателей. Перемычка 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п−1 "случай переключения. Однако, если A и B другой переключатели среднего уровня, требуется больше работы. Алгоритм находит новое расположение соединений через промежуточные переключатели A и B, которое включает все существующие соединения, плюс желаемое новое соединение.

Составьте список всех желаемых подключений, которые проходят через A или B. То есть все существующие подключения, которые необходимо поддерживать. и новое соединение. Собственно алгоритм заботится только о внутренних соединениях от входа к переключателю выхода, хотя практическая реализация также должна отслеживать правильные подключения переключателя входа и выхода.

В этом списке каждый входной субпереключатель может присутствовать не более чем в двух соединениях: одно с субпереключателем A и одно с субкоммутатором B. Возможные варианты: ноль, один или два. Аналогично, каждый выходной субпереключатель появляется максимум в двух соединениях.

Каждое соединение связано не более чем с двумя другими посредством общего входного или выходного переключателя, образуя одно звено в «цепочке» соединений.

Затем начните с нового подключения. Назначьте ему путь от входного субпереключателя через средний субпереключатель A к выходному субпереключателю. Если выходной субпереключатель этого первого соединения имеет второе соединение, назначьте этому второму соединению путь от входного субпереключателя до субпереключателя B. Если этот входной субпереключатель имеет другое соединение, назначьте этому третьему соединению путь через субпереключатель A. Продолжайте взад и вперед таким же образом. , чередуя промежуточные переключатели A и B. В конце концов должно произойти одно из двух:

цепочка заканчивается субкоммутатором только с одним соединением, или
цепь возвращается к первоначально выбранному соединению.

В первом случае вернитесь к входному субпереключателю нового соединения и проследите его цепочку в обратном направлении, назначая соединения путям через средние субкоммутаторы B и A в том же порядке чередования.

Когда это сделано, каждый входной или выходной субпереключатель в цепочке имеет не более двух соединений, проходящих через него, и они назначаются различным средним переключателям. Таким образом, все необходимые ссылки доступны.

Могут быть дополнительные соединения через субпереключатели A и B, которые не являются частью цепочки, включая новое соединение; эти соединения можно оставить как есть.

После того, как в программном обеспечении будет разработан новый шаблон подключения, электроника переключателя может быть фактически перепрограммирована, физически перемещая соединения. Электронные переключатели спроектированы таким образом, что новую конфигурацию можно записать в электронику, не нарушая существующее соединение, а затем вступить в силу с помощью одного логического импульса. В результате соединение перемещается мгновенно, с незаметным прерыванием разговора. В более старых электромеханических переключателях иногда слышался лязг «коммутирующий шум».

Этот алгоритм представляет собой форму топологическая сортировка, и является сердцем алгоритма, который управляет переключателем минимального охвата.

Практические реализации переключателей

Как только алгоритм был открыт, системные инженеры и менеджеры Bell начали его обсуждение. Спустя несколько лет инженеры Bell приступили к разработке электромеханических переключателей, которыми можно было управлять. В то время компьютеры использовали трубы и не были достаточно надежными для управления телефонной системой (переключатели телефонной системы критически важны для безопасности, и они рассчитаны на то, чтобы иметь незапланированный выход из строя примерно раз в тридцать лет). Реле компьютеры на базе были слишком медленными, чтобы реализовать алгоритм. Однако вся система могла быть спроектирована так, чтобы, когда компьютеры были достаточно надежными, их можно было модернизировать для существующих систем коммутации.

Сделать композитные переключатели несложно отказоустойчивой. При выходе из строя вспомогательного коммутатора вызывающие абоненты просто повторно набирают номер. Таким образом, при каждом новом подключении программа пробует следующее свободное подключение в каждом субкоммутаторе, а не повторно использует последнее выпущенное соединение. Новое соединение, скорее всего, будет работать, потому что оно использует другую схему.

Следовательно, в загруженном коммутаторе, когда на конкретной плате отсутствуют какие-либо соединения, это отличный кандидат для тестирования.

Для проверки или вывода из эксплуатации конкретной печатной платы существует хорошо известный алгоритм. Поскольку через субпереключатель карты проходит меньше соединений, программное обеспечение направляет больше тестовых сигналов через субпереключатель на измерительное устройство, а затем считывает результаты измерения. Это не прерывает старые вызовы, которые продолжают работать.

Если тест не удается, программное обеспечение изолирует конкретную печатную плату, считывая неисправность с нескольких внешних переключателей. Затем он отмечает свободные цепи неисправной схемы как занятые. Когда вызовы с использованием неисправной схемы завершаются, эти каналы также помечаются как занятые. Некоторое время спустя, когда через неисправную схему не проходит ни один вызов, компьютер загорается на печатной плате, которую необходимо заменить, и технический специалист может заменить печатную плату. Вскоре после замены следующая проверка завершается успешно, соединения с отремонтированным субкоммутатором помечаются как «не заняты», и коммутатор возвращается в режим полной работы.

Диагностика ранних электронных переключателей Bell фактически загоралась зеленым светом на каждой исправной печатной плате и загоралась красным светом на каждой вышедшей из строя печатной плате. Печатные схемы были спроектированы таким образом, чтобы их можно было снимать и заменять, не выключая весь переключатель.

Конечным результатом стал колокол. 1ESS. Это управлялось центральным процессором, называемым Central Control (CC), ступенька, Гарвардская архитектура двойной компьютер с использованием надежных диодно-транзисторная логика. В ЦП 1ESS два компьютера выполняли каждый шаг, проверяя друг друга. Когда они не соглашались, они ставили себе диагноз, и правильно работающий компьютер брался за переключение, в то время как другой дисквалифицировал себя и требовал ремонта. Коммутатор 1ESS по-прежнему использовался ограниченно по состоянию на 2012 год и имел подтвержденную надежность менее одного часа внепланового отказа за каждые тридцать лет эксплуатации, что подтверждает его конструкцию.

Первоначально она была установлена на магистральных линиях дальней связи в крупных городах, наиболее часто используемых частях каждой телефонной станции. В первый День матери, когда с ее помощью работали крупные города, система Bell установила рекорд по общей пропускной способности сети, как по выполненным вызовам, так и по общему количеству вызовов в секунду на коммутатор. Это привело к рекордной общей выручке на ствол.

Цифровые переключатели

Практическая реализация переключателя может быть создана из странный количество слоев меньших субпереключателей. Концептуально каждый поперечный переключатель трехступенчатого переключателя может быть далее разбит на более мелкие поперечные переключатели. Хотя каждый субпереключатель имеет ограниченную возможность мультиплексирования, работая вместе, они синтезируют эффект большего N×N поперечный переключатель.

В современном цифровом телефонном коммутаторе применение двух различных подходов к мультиплексору на чередующихся уровнях дополнительно снижает стоимость коммутационной матрицы:

разделение пространства мультиплексоры что-то вроде поперечные переключатели уже описано, или какое-то расположение переключатели кроссовера или баньян переключатели. Любой отдельный выход можно выбрать из любого входа. В цифровых переключателях это обычно И ворота. 8000 раз в секунду соединение перепрограммируется для подключения определенных проводов на время Временной интервал. Преимущество дизайна: В системах с пространственным разделением количество соединений с пространственным разделением делится на количество временных интервалов в системе мультиплексирования с разделением по времени. Это значительно снижает размер и стоимость коммутационной матрицы. Это также увеличивает надежность, потому что существует гораздо меньше физических соединений, которые могут выйти из строя.
мультиплексоры с временным разделением у каждого есть память, которая читается в фиксированном порядке и записывается в программируемом порядке (или наоборот). Этот тип переключателя переставляет временные интервалы в мультиплексированный сигнал с временным разделением который поступает в мультиплексоры с пространственным разделением на соседних уровнях. Преимущество дизайна: Переключатели с временным разделением имеют только один входной и выходной провод. Поскольку у них гораздо меньше электрических соединений, которые могут выйти из строя, они намного более надежны, чем переключатели с пространственным разделением, и поэтому являются предпочтительными переключателями для внешних (входных и выходных) уровней современных телефонных коммутаторов.

Практичные цифровые телефонные коммутаторы минимизируют размер и стоимость электроники. Во-первых, обычно коммутатор «складывается», так что и входные, и выходные соединения с абонентской линией обрабатываются одной и той же логикой управления. Затем во внешнем слое используется переключатель с временным разделением. Внешний уровень реализован в интерфейсных платах абонентской линии (SLIC) в уличных блоках местного присутствия. При дистанционном управлении с центрального коммутатора карты подключаются к временным слотам в линии с временным мультиплексированием к центральному коммутатору. В США мультиплексированная линия является кратной Линия Т-1. В Европе и многих других странах это кратное E-1 линия.

Скудные ресурсы в телефонный коммутатор - это соединения между слоями субпереключателей. Эти соединения могут быть либо временными интервалами, либо проводами, в зависимости от типа мультиплексирования. В логика управления должен выделить эти соединения, и основным методом является уже обсужденный алгоритм. Субпереключатели логически расположены так, что они синтезируют субпереключатели большего размера. Каждый субпереключатель и синтезированный субпереключатель контролируются (рекурсивно ) по логике, полученной из математики Клоса. Компьютерный код разбивает большие мультиплексоры на меньшие мультиплексоры.

Если рекурсия доведена до предела, разбивая перекладину до минимально возможного количества переключающих элементов, получившееся устройство иногда называют переключатель кроссовера или баньян переключатель в зависимости от его топологии.

Коммутаторы обычно взаимодействуют с другими коммутаторами и оптоволоконными сетями через быстрые мультиплексированные линии передачи данных, такие как СОНЕТ.

Каждая линия коммутатора может периодически проверяться компьютером, отправляя через него тестовые данные. Если линия переключателя выходит из строя, все линии переключателя помечаются как используемые. Линии мультиплексора распределяются по принципу «первым пришел - первым обслужен», чтобы новые соединения находили новые элементы переключения. Когда все соединения отключены от неисправного переключателя, неисправный переключатель можно избежать, а позже заменить.

По состоянию на 2018 год такие переключатели больше не производятся. Их заменяют высокоскоростные протокол Интернета роутеры.

Пример изменения маршрута коммутатора

Сигналы A, B, C, D маршрутизируются, но сигнал E блокируется, если только сигнал, например D, показанный фиолетовым цветом, не перенаправляется

После перенаправления D, выделенного фиолетовым, сигнал E может быть маршрутизирован, и все дополнительные сигналы плюс E подключены.