Неблокирующие коммутационные сети: от перекрестных коммутаторов к сетям Кло

Введение

Неблокирующий минимальный коммутатор – это устройство, способное соединять N входов с N выходами в любой комбинации. Наиболее известное применение таких коммутаторов – в телефонных станциях. Термин "неблокирующий" означает, что при отсутствии дефектов он всегда может установить соединение. Термин "минимальный" означает, что он содержит наименьшее возможное количество компонентов, а следовательно, и минимальные затраты. Исторически, в телефонных коммутаторах соединения между абонентами осуществлялись с помощью больших и дорогих блоков электромеханических реле – коммутаторов Строугера. Основное математическое свойство коммутаторов Строугера заключается в том, что для каждого входа коммутатора существует ровно один выход. Значительная часть математической теории коммутационных схем направлена на использование этого свойства для сокращения общего числа коммутаторов, необходимых для соединения комбинации входов с комбинацией выходов. В 1940-х и 1950-х годах инженеры Bell Labs начали серию углубленных математических исследований, посвященных методам уменьшения размера и стоимости "коммутационного поля", необходимого для реализации телефонной станции. Один из первых успешных математических анализов был проведен Чарльзом Клосом (ʃaʁl klo), а коммутационное поле, построенное из меньших коммутаторов, называется сетью Клоса.

Переключатель

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

Скрыватели с трехслойным соединением

Следующим подходом было разделить перекрестную коммутационную матрицу на три уровня меньших перекрестных коммутационных матриц. Будут "входной уровень", "средний уровень" и "выходной уровень". Меньшие коммутационные матрицы менее громоздки, более надежны и, как правило, проще в изготовлении, а следовательно, и дешевле. Телефонная система должна устанавливать соединение "один к одному". Интуитивно это кажется, что количество входов и выходов всегда может быть одинаковым в каждой подматрице, но интуиция не доказывает, что это возможно, и не указывает, как это сделать. Предположим, мы хотим создать перекрестную коммутационную матрицу 16x16. Проект может включать 4 подматрицы на входной стороне, каждая с 4 входами, что в сумме дает 16 входов. Кроме того, на выходной стороне мы также можем использовать 4 выходные подматрицы, каждая с 4 выходами, что в сумме дает 16 выходов. Желательно, чтобы конструкция использовала как можно меньше проводов, поскольку провода стоят денег. Минимальное количество проводов, которые могут соединить две подматрицы, – это один провод. Таким образом, каждая входная подматрица будет иметь один провод к каждой средней подматрице. Кроме того, каждая средняя подматрица будет иметь один провод к каждой выходной подматрице. Вопрос в том, сколько средних подматриц необходимо и, следовательно, сколько проводов в общей сложности должно соединять входной уровень со средним уровнем. Поскольку телефонные коммутаторы симметричны (звонящий и вызываемый абонент взаимозаменяемы), та же логика применима к выходному уровню, а средние подматрицы будут "квадратными", имея одинаковое количество входов и выходов. Количество средних подматриц зависит от алгоритма, используемого для распределения соединений между ними. Основной алгоритм управления трехслойной коммутационной матрицей заключается в поиске средней подматрицы, которая имеет неиспользованные провода к необходимым входным и выходным коммутационным матрицам. Как только подходящая средняя подматрица найдена, подключение к правильным входам и выходам во входных и выходных коммутационных матрицах становится тривиальным. Теоретически, в данном примере достаточно всего четырех центральных коммутационных матриц, каждая с ровно одним соединением с каждой входной коммутационной матрицей и одним соединением с каждой выходной коммутационной матрицей. Это называется "минимальной коммутационной матрицей", и управление ею было главной целью исследований Bell Labs. Однако небольшая работа с карандашом и бумагой покажет, что легко привести такую минимальную коммутационную матрицу в состояние, когда ни одна средняя подматрица не имеет соединения как с необходимой входной, так и с необходимой выходной коммутационной матрицей. Для частичной блокировки коммутационной матрицы достаточно всего четырех вызовов. Если входная коммутационная матрица наполовину заполнена, она имеет соединения через две средние коммутационные матрицы. Если выходная коммутационная матрица также наполовину заполнена соединениями из двух других средних коммутационных матриц, то не остается ни одной средней коммутационной матрицы, которая могла бы обеспечить путь между этим входом и выходом. По этой причине считалось, что для "просто связанной неблокирующей коммутационной матрицы" 16x16 с четырьмя входными и четырьмя выходными подматрицами требуется 7 средних коммутационных матриц; в худшем случае почти заполненная входная подматрица будет использовать три средние коммутационные матрицы, почти заполненная выходная подматрица будет использовать три другие, а седьмая гарантированно будет свободна для последнего соединения. По этой причине иногда такое расположение коммутационной матрицы называют "2n-1 коммутационной матрицей", где n – количество входных портов входных подматриц. Пример намеренно мал, и в таком небольшом примере реорганизация не позволяет существенно сэкономить коммутационные матрицы. Перекрестная коммутационная матрица 16x16 имеет 256 контактов, в то время как минимальная коммутационная матрица 16x16 имеет 4x4x4x3 = 192 контакта. По мере увеличения чисел экономия возрастает. Например, для телефонной станции на 10 000 линий потребуется 100 миллионов контактов для реализации полной перекрестной коммутационной матрицы. Но три уровня из 100 подматриц 100x100 потребуют всего 300 подматриц с 10 000 контактов или 3 миллиона контактов. Эти подматрицы, в свою очередь, могут быть изготовлены из 3x10 перекрестных коммутационных матриц 10x10, в общей сложности 3000 контактов, что составляет 900 000 для всей станции; это гораздо меньше, чем 100 миллионов.

The next approach was to break apart the crossbar switch into three layers of smaller crossbar switches. There would be an "input layer", a "middle layer" and an "output layer." The smaller switches are less massive, more reliable, and generally easier to build, and therefore less expensive. A telephone system only has to make a one to one connection. Intuitively this seems to mean that the number of inputs and the number of outputs can always be equal in each subswitch, but intuition does not prove this can be done nor does it tell us how to do so. Suppose we want to synthesize a 16 by 16 crossbar switch. The design could have 4 subswitches on the input side, each with 4 inputs, for 16 total inputs. Further, on the output side, we could also have 4 output subswitches, each with 4 outputs, for a total of 16 outputs. It is desirable that the design use as few wires as possible, because wires cost real money. The least possible number of wires that can connect two subswitches is a single wire. So, each input subswitch will have a single wire to each middle subswitch. Also, each middle subswitch will have a single wire to each output subswitch. The question is how many middle subswitches are needed, and therefore how many total wires should connect the input layer to the middle layer. Since telephone switches are symmetric (callers and callees are interchangeable), the same logic will apply to the output layer, and the middle subswitches will be "square", having the same number of inputs as outputs. The number of middle subswitches depends on the algorithm used to allocate connection to them. The basic algorithm for managing a three layer switch is to search the middle subswitches for a middle subswitch that has unused wires to the needed input and output switches. Once a connectible middle subswitch is found, connecting to the correct inputs and outputs in the input and output switches is trivial. Theoretically, in the example, only four central switches are needed, each with exactly one connection to each input switch and one connection to each output switch. This is called a "minimal spanning switch," and managing it was the holy grail of the Bell Labs' investigations. However, a bit of work with a pencil and paper will show that it is easy to get such a minimal switch into conditions in which no single middle switch has a connection to both the needed input switch and the needed output switch. It only takes four calls to partially block the switch. If an input switch is half full, it has connections via two middle switches. If an output switch is also half full with connections from the other two middle switches, then there is no remaining middle switch which can provide a path between that input and output. For this reason, a "simply connected nonblocking switch" 16x16 switch with four input subswitches and four output switches was thought to require 7 middle switches; in the worst case an almost full input subswitch would use three middle switches, an almost full output subswitch would use three different ones, and the seventh would be guaranteed to be free to make the last connection. For this reason, sometimes this switch arrangement is called a "2n−1 switch", where n is the number of input ports of the input subswitches. The example is intentionally small, and in such a small example, the reorganization does not save many switches. A 16×16 crossbar has 256 contacts, while a 16×16 minimal spanning switch has 4×4×4×3 = 192 contacts. As the numbers get larger, the savings increase. For example, a 10,000 line exchange would need 100 million contacts to implement a full crossbar. But three layers of 100 100×100 subswitches would use only 300 10,000 contact subswitches, or 3 million contacts. Those subswitches could in turn each be made of 3×10 10×10 crossbars, a total of 3000 contacts, making 900,000 for the whole exchange; that is a far smaller number than 100 million.

Практические реализации коммутаторов

Как только алгоритм был обнаружен, инженеры и менеджеры Bell System начали его обсуждать. Через несколько лет инженеры Bell приступили к разработке электромеханических коммутаторов, которыми можно было управлять с его помощью. В то время компьютеры использовали вакуумные лампы и были недостаточно надежны для управления телефонной системой (коммутаторы телефонной системы критически важны для безопасности, и они рассчитаны на незапланированный отказ примерно раз в тридцать лет). Компьютеры на реле были слишком медленными для реализации алгоритма. Однако вся система могла быть спроектирована таким образом, чтобы при достижении необходимой надежности компьютеры могли быть установлены на существующие коммутационные системы. Создать отказоустойчивые композитные коммутаторы несложно. При отказе подкоммутатора вызывающие абоненты просто перезванивают. Таким образом, при каждом новом соединении программное обеспечение пытается использовать следующее свободное соединение в каждом подкоммутаторе, а не повторно использовать только что освободившееся. Новое соединение с большей вероятностью будет успешным, поскольку использует другую схему. Следовательно, в загруженном коммутаторе, если на конкретной PCB нет активных соединений, она является отличным кандидатом для тестирования. Существует известный алгоритм для тестирования или изъятия из эксплуатации конкретной печатной платы. По мере уменьшения количества соединений, проходящих через подкоммутатор платы, программное обеспечение направляет больше тестовых сигналов через этот подкоммутатор на измерительное устройство и считывает результаты измерений. Это не прерывает текущие вызовы, которые продолжают работать. В случае неудачи теста программное обеспечение определяет точную неисправную плату, считывая информацию об отказе с нескольких внешних коммутаторов. Затем оно помечает свободные цепи в неисправной схеме как занятые. По мере завершения вызовов, использующих неисправные схемы, эти цепи также помечаются как занятые. Через некоторое время, когда через неисправные схемы не проходит ни одного вызова, компьютер загорает индикатор на плате, требующей замены, и техник может ее заменить. Вскоре после замены следующий тест проходит успешно, соединения с восстановленным подкоммутатором помечаются как "свободные", и коммутатор возвращается к нормальной работе. Диагностика ранних электронных коммутаторов Bell фактически зажигала зеленый индикатор на каждой исправной печатной плате и красный индикатор на каждой неисправной. Печатные схемы были разработаны таким образом, чтобы их можно было извлекать и заменять, не отключая весь коммутатор. В конечном итоге был создан Bell 1ESS. Управлением осуществлялся процессор, известный как Центральный контроллер (CC) – двойной компьютер с архитектурой Гарварда, работающий в такт и использующий надежную диодно-транзисторную логику. В процессоре 1ESS два компьютера выполняли каждый шаг, взаимно контролируя друг друга. В случае расхождения они проводили самодиагностику, и правильно работающий компьютер брал на себя управление коммутатором, в то время как другой отключался и запрашивал ремонт. В 2012 году коммутатор 1ESS все еще использовался в ограниченном масштабе и демонстрировал подтвержденную надежность менее одного часа незапланированного простоя за тридцать лет эксплуатации, что подтверждало правильность его конструкции. Первоначально он был установлен на магистральных линиях связи в крупных городах – наиболее загруженных участках каждой телефонной станции. В первый День матери, когда крупные города использовали этот коммутатор, система Bell установила рекорд общей пропускной способности сети как по количеству завершенных вызовов, так и по количеству вызовов в секунду на коммутатор. Это привело к рекордному доходу на один канал связи.

As soon as the algorithm was discovered, Bell system engineers and managers began discussing it. After several years, Bell engineers began designing electromechanical switches that could be controlled by it. At the time, computers used tubes and were not reliable enough to control a phone system (phone system switches are safety critical, and they are designed to have an unplanned failure about once per thirty years). Relay based computers were too slow to implement the algorithm. However, the entire system could be designed so that when computers were reliable enough, they could be retrofitted to existing switching systems. It's not difficult to make composite switches fault tolerant. When a subswitch fails, the callers simply redial. So, on each new connection, the software tries the next free connection in each subswitch rather than reusing the most recently released one. The new connection is more likely to work because it uses different circuitry. Therefore, in a busy switch, when a particular PCB lacks any connections, it is an excellent candidate for testing. To test or remove a particular printed circuit card from service, there is a well known algorithm. As fewer connections pass through the card's subswitch, the software routes more test signals through the subswitch to a measurement device, and then reads the measurement. This does not interrupt old calls, which remain working. If a test fails, the software isolates the exact circuit board by reading the failure from several external switches. It then marks the free circuits in the failing circuitry as busy. As calls using the faulty circuitry are ended, those circuits are also marked busy. Some time later, when no calls pass through the faulty circuitry, the computer lights a light on the circuit board that needs replacement, and a technician can replace the circuit board. Shortly after replacement, the next test succeeds, the connections to the repaired subswitch are marked "not busy," and the switch returns to full operation. The diagnostics on Bell's early electronic switches would actually light a green light on each good printed circuit board, and light a red light on each failed printed circuit board. The printed circuits were designed so that they could be removed and replaced without turning off the whole switch. The eventual result was the Bell 1ESS. This was controlled by a CPU called the Central Control (CC), a lock step, Harvard architecture dual computer using reliable diode–transistor logic. In the 1ESS CPU, two computers performed each step, checking each other. When they disagreed, they would diagnose themselves, and the correctly running computer would take up switch operation while the other would disqualify itself and request repair. The 1ESS switch was still in limited use as of 2012, and had a verified reliability of less than one unscheduled hour of failure in each thirty years of operation, validating its design. Initially it was installed on long distance trunks in major cities, the most heavily used parts of each telephone exchange. On the first Mother's Day that major cities operated with it, the Bell system set a record for total network capacity, both in calls completed, and total calls per second per switch. This resulted in a record for total revenue per trunk.