Неблокирующий минимальный переключатель связующего является устройством , которое можно подключить N входов N выходов в любой комбинации. Наиболее часто коммутаторы этого типа используются в телефонных станциях . Термин «неблокирующий» означает, что если он исправен, он всегда может установить соединение. Термин «минимальный» означает, что он имеет наименьшее количество возможных компонентов и, следовательно, минимальные затраты.
Исторически сложилось так, что в телефонных коммутаторах соединения между вызывающими абонентами осуществлялись с помощью больших дорогих блоков электромеханических реле , коммутаторов Строуджера . Основное математическое свойство переключателей Строуджера состоит в том, что на каждый вход переключателя приходится ровно один выход. Большая часть математической теории коммутационных схем пытается использовать это свойство для уменьшения общего количества переключателей, необходимых для соединения комбинации входов с комбинацией выходов.
В 1940-х и 1950-х годах инженеры Bell Laboratories начали расширенную серию математических исследований методов уменьшения размера и стоимости « коммутируемой ткани », необходимой для реализации телефонной станции. Одним из первых, успешный математический анализ был проведен Чарльзом Клоса ( французское произношение: [ʃaʁl кло] ), и переключился ткани построены из более мелких коммутаторов называется сеть Клоса . [1]
Предпосылки: переключение топологий
Переключатель перекладины
Переключатель перекладины имеет свойство быть возможностью подключения N входов к выходам N в любой один-к-одному комбинации, так что он может соединить любой вызывающий абонент любого не занятой приемник, свойство данного технический термина «неблокирующий». Будучи неблокирующим, он всегда может завершить вызов (незанятому получателю), что максимально повысит доступность услуги.
Однако поперечный переключатель делает это за счет использования N 2 (N в квадрате) простых переключателей SPST . Для большого N (а практические требования к телефонному коммутатору считаются большими) такой рост был слишком дорогим. Кроме того, у больших переключателей на перекладине были физические проблемы. Для переключателя требовалось не только слишком много места, но и металлические стержни, содержащие контакты переключателя, становились настолько длинными, что прогибались и становились ненадежными. Инженеры также заметили, что в любой момент каждая полоса перекрестного переключателя выполняла только одно соединение. Остальные контакты на двух планках не использовались. Это, по-видимому, означало, что большая часть коммутационной ткани поперечного переключателя была потрачена впустую.
Очевидный способ имитации перекрестного переключателя состоял в том, чтобы найти способ построить его из меньших перекрестных переключателей. Если поперечный переключатель может быть эмулирован некоторым расположением поперечных переключателей меньшего размера, то эти меньшие поперечные переключатели также могут, в свою очередь, эмулироваться еще меньшими поперечными переключателями. Коммутационная матрица может стать очень эффективной и, возможно, даже быть создана из стандартизованных частей. Это называется сетью Клоса .
Полностью подключенные трехуровневые переключатели
Следующий подход заключался в том, чтобы разделить перекладину на три слоя более мелких перекладин. Будет «входной уровень», «средний уровень» и «выходной уровень». Коммутаторы меньшего размера менее массивны, более надежны и, как правило, проще в сборке и, следовательно, менее дороги.
Телефонная система должна устанавливать соединение только один на один. Интуитивно кажется, что это означает, что количество входов и выходов всегда может быть одинаковым в каждом субпереключателе, но интуиция не доказывает, что это возможно, и не говорит нам, как это сделать. Предположим, мы хотим синтезировать перекрестный переключатель 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 . Это управляется процессором под названием Центральный блок управления (CC), с замковым шагом , Harvard архитектуры двойного компьютера с помощью надежной логики диодной транзистора . В ЦП 1ESS два компьютера выполняли каждый шаг, проверяя друг друга. Когда они не соглашались, они диагностировали себя, и правильно работающий компьютер брался за переключение, в то время как другой дисквалифицировал себя и требовал ремонта. Коммутатор 1ESS по-прежнему использовался ограниченно по состоянию на 2012 год и имел подтвержденную надежность менее одного часа внепланового отказа за каждые тридцать лет эксплуатации, что подтверждает его конструкцию.
Первоначально он был установлен на магистральных линиях дальней связи в крупных городах, наиболее часто используемых частях каждой телефонной станции. В первый День матери, когда с ее помощью работали крупные города, система Bell установила рекорд по общей пропускной способности сети, как по выполненным вызовам, так и по общему количеству вызовов в секунду на коммутатор. Это привело к рекордной общей выручке на ствол.
Цифровые переключатели
Практическая реализация переключателя может быть создана из нечетного количества слоев меньших суб-переключателей. Концептуально каждый поперечный переключатель трехступенчатого переключателя может быть далее разбит на более мелкие поперечные переключатели. Хотя каждый субпереключатель имеет ограниченную возможность мультиплексирования, работая вместе, они синтезируют эффект большего переключателя N × N.
В современном цифровом телефонном коммутаторе применение двух различных подходов к мультиплексору на чередующихся уровнях дополнительно снижает стоимость коммутационной матрицы:
- Мультиплексоры с пространственным разделением - это что-то вроде уже описанных перекрестных переключателей , некоторых перекрестных переключателей или переключателей баньяна . Любой отдельный выход можно выбрать из любого входа. В цифровых коммутаторах, это, как правило , расположение и ворота . 8000 раз в секунду соединение перепрограммируется для подключения определенных проводов на время временного интервала . Преимущество конструкции: в системах с пространственным разделением количество соединений с пространственным разделением делится на количество временных интервалов в системе с временным разделением каналов. Это значительно снижает размер и стоимость коммутационной матрицы. Это также увеличивает надежность, потому что существует гораздо меньше физических соединений, которые могут выйти из строя.
- Каждый мультиплексор с временным разделением имеет память, которая считывается в фиксированном порядке и записывается в программируемом порядке (или наоборот ). Этот тип коммутатора переставляет временные интервалы в мультиплексированном сигнале с временным разделением, который поступает в мультиплексоры с пространственным разделением на его соседних уровнях. Преимущество конструкции: переключатели с временным разделением имеют только один входной и выходной провод. Поскольку у них гораздо меньше электрических соединений, которые могут выйти из строя, они намного более надежны, чем переключатели с пространственным разделением, и поэтому являются предпочтительными переключателями для внешних (входных и выходных) уровней современных телефонных коммутаторов.
Практичные цифровые телефонные коммутаторы минимизируют размер и стоимость электроники. Во-первых, коммутатор обычно «складывают», так что и входные, и выходные соединения с абонентской линией обрабатываются одной и той же логикой управления. Затем во внешнем слое используется переключатель с временным разделением. Внешний уровень реализован в интерфейсных картах абонентской линии (SLIC) в уличных блоках местного присутствия. При дистанционном управлении с центрального коммутатора карты подключаются к временным слотам в линии с временным мультиплексированием к центральному коммутатору. В США мультиплексированная линия является кратной линии T-1 . В Европе и многих других странах он кратен линии E-1 .
Дефицитные ресурсы в телефонном коммутаторе - это соединения между уровнями субкоммутаторов. Эти соединения могут быть либо временными интервалами, либо проводами, в зависимости от типа мультиплексирования. Логика управления должна выделять эти соединения, а основной метод является алгоритмом уже обсуждался. Субпереключатели логически устроены так, что они синтезируют субпереключатели большего размера. Каждый субпереключатель и синтезированный субпереключатель контролируются ( рекурсивно ) логикой, полученной из математики Клоса. Компьютерный код разбивает мультиплексоры большего размера на мультиплексоры меньшего размера.
Если рекурсия доведена до предела, разбивая перекладину до минимально возможного количества переключающих элементов, полученное устройство иногда называют перекрестным переключателем или баньяновым переключателем в зависимости от его топологии.
Коммутаторы обычно взаимодействуют с другими коммутаторами и оптоволоконными сетями через быстрые мультиплексированные линии передачи данных, такие как SONET .
Каждая линия коммутатора может периодически проверяться компьютером, отправляя через него тестовые данные. Если линия переключателя выходит из строя, все линии переключателя помечаются как используемые. Линии мультиплексора распределяются по принципу «первым пришел - первым обслужен», чтобы новые соединения находили новые элементы переключения. Когда все соединения отключены от неисправного переключателя, неисправный переключатель можно избежать, а позже заменить.
По состоянию на 2018 год такие переключатели больше не производятся. Их заменяют высокоскоростные маршрутизаторы с интернет-протоколом .
Пример перенаправления коммутатора
Смотрите также
Рекомендации
- Перейти ↑ Clos, Charles (март 1953). «Исследование неблокирующих коммутационных сетей» (PDF) . Технический журнал Bell System . 32 (2): 406–424. DOI : 10.1002 / j.1538-7305.1953.tb01433.x . ISSN 0005-8580 . Проверено 22 марта 2011 года . CS1 maint: обескураженный параметр ( ссылка )