В области телекоммуникаций сеть Clos — это своего рода многоступенчатая коммутационная сеть, которая представляет собой теоретическую идеализацию практических многоступенчатых коммутационных систем. Она была изобретена Эдсоном Эрвином [1] в 1938 году и впервые формализована американским [2] инженером Чарльзом Клосом [3] в 1952 году.
Добавляя этапы, сеть Clos уменьшает количество точек пересечения, необходимых для составления большого коммутатора пересечения . Топология сети Clos (схема ниже) параметризуется тремя целыми числами n , m и r : n представляет собой количество источников, которые поступают на каждый из r коммутаторов пересечения входного этапа; каждый коммутатор пересечения входного этапа имеет m выходов; и имеется m коммутаторов пересечения среднего этапа.
Коммутация каналов организует выделенный коммуникационный путь для соединения между конечными точками на время соединения. Это жертвует общей доступной полосой пропускания, если выделенные соединения используются неэффективно, но делает соединение и полосу пропускания более предсказуемыми и вводит накладные расходы на управление только при инициировании соединений, а не при обработке каждого пакета, как в современных сетях с коммутацией пакетов .
Когда сеть Clos была впервые разработана, количество точек пересечения было хорошим приближением общей стоимости коммутационной системы. Хотя это было важно для электромеханических кросс-баров, это стало менее актуальным с появлением VLSI , где межсоединения могли быть реализованы либо непосредственно в кремнии, либо в относительно небольшом кластере плат. С появлением сложных центров обработки данных с огромными структурами межсоединений, каждая из которых основана на оптоволоконных соединениях, сети Clos вновь обрели важность. [4] Подтип сети Clos, сеть Бенеша, также нашел недавнее применение в машинном обучении . [5]
Сети Clos имеют три этапа: входной этап, средний этап и выходной этап. Каждый этап состоит из ряда коммутаторов пересечения (см. схему ниже), часто называемых просто коммутаторами пересечения . Сеть реализует r-way perfect shuffle между этапами. Каждый вызов, входящий в коммутатор пересечения входящего трафика, может быть направлен через любой из доступных коммутаторов пересечения среднего этапа на соответствующий коммутатор пересечения исходящего трафика. Коммутатор пересечения среднего этапа доступен для конкретного нового вызова, если как соединение, соединяющее коммутатор входящего трафика с коммутатором среднего этапа, так и соединение, соединяющее коммутатор среднего этапа с коммутатором исходящего трафика, свободны.
Сети Clos определяются тремя целыми числами n , m и r . n представляет собой количество источников, которые поступают на каждый из r коммутаторов пересечения входной ступени. Каждый коммутатор пересечения входной ступени имеет m выходов, и имеется m коммутаторов пересечения средней ступени. Между каждым коммутатором пересечения входной ступени и каждым коммутатором средней ступени имеется ровно одно соединение. Имеется r коммутаторов пересечения выходной ступени, каждый из которых имеет m входов и n выходов. Каждый коммутатор средней ступени соединен ровно один раз с каждым коммутатором пересечения выходной ступени. Таким образом, на входной ступени имеется r коммутаторов, каждый из которых имеет n входов и m выходов. На средней ступени имеется m коммутаторов, каждый из которых имеет r входов и r выходов. На выходной ступени имеется r коммутаторов, каждый из которых имеет m входов и n выходов.
Относительные значения m и n определяют блокирующие характеристики сети Клоса.
Если m ≥ 2 n −1, сеть Clos является неблокируемой в строгом смысле , что означает, что неиспользуемый вход на входном коммутаторе всегда может быть подключен к неиспользуемому выходу на выходном коммутаторе без необходимости переупорядочивать существующие вызовы . Это результат, который лег в основу классической статьи Clos 1953 года. Предположим, что на входе входного коммутатора есть свободный терминал, и он должен быть подключен к свободному терминалу на определенном выходном коммутаторе. В худшем случае на входном коммутаторе активны n −1 других вызовов, а на выходном коммутаторе активны n −1 других вызовов. Предположим, также в худшем случае, что каждый из этих вызовов проходит через другой коммутатор средней ступени. Следовательно, в худшем случае 2 n −2 коммутаторов средней ступени не могут передать новый вызов. Поэтому для обеспечения строгой неблокируемой работы требуется еще один переключатель средней ступени, что в сумме дает 2 n −1.
На схеме ниже показан наихудший случай, когда уже установленные вызовы (синий и красный) проходят через разные коммутаторы среднего уровня, поэтому для установления вызова между зеленым входом и выходом необходим еще один коммутатор среднего уровня.
Если m ≥ n , сеть Clos является перестраиваемо неблокируемой , что означает, что неиспользуемый вход на входном коммутаторе всегда может быть подключен к неиспользуемому выходу на выходном коммутаторе, но для этого существующие вызовы, возможно, придется перестроить, назначив их разным центральным коммутаторам в сети Clos. [6] Чтобы доказать это, достаточно рассмотреть m = n , при полностью загруженной сети Clos; то есть, r × n вызовов в процессе. Доказательство показывает, как любая перестановка этих r × n входных терминалов на r × n выходных терминалов может быть разбита на меньшие перестановки, каждая из которых может быть реализована отдельными коммутаторами перекрестной панели в сети Clos с m = n .
Доказательство использует теорему Холла о браке [7] , которая получила такое название, потому что ее часто объясняют следующим образом. Предположим, что есть r мальчиков и r девочек. Теорема утверждает, что если каждое подмножество из k мальчиков (для каждого k такого, что 0 ≤ k ≤ r ) между ними знает k или более девочек, то каждый мальчик может быть объединен в пару с девушкой, которую он знает. Очевидно, что это необходимое условие для объединения в пару; удивительно то, что оно достаточно.
В контексте сети Clos каждый мальчик представляет собой входной коммутатор, а каждая девочка представляет собой выходной коммутатор. Говорят, что мальчик знает девочку, если соответствующие входные и выходные коммутаторы передают один и тот же вызов. Каждый набор из k мальчиков должен знать по крайней мере k девочек, потому что k входных коммутаторов передают k × n вызовов, и их не может передавать менее чем k выходных коммутаторов. Следовательно, каждый входной коммутатор может быть сопряжен с выходным коммутатором, передающим тот же вызов, посредством сопоставления один к одному. Эти r вызовов могут передаваться одним коммутатором средней ступени. Если этот коммутатор средней ступени теперь удалить из сети Clos, m уменьшится на 1, и у нас останется меньшая сеть Clos. Затем процесс повторяется до тех пор, пока m = 1, и каждый вызов будет назначен коммутатору средней ступени.
Реальные телефонные коммутационные системы редко бывают строго неблокируемыми по соображениям стоимости, и у них есть небольшая вероятность блокировки, которую можно оценить с помощью приближений Ли или Якобеуса [8] , предполагая отсутствие перераспределения существующих вызовов. Здесь потенциальное количество других активных вызовов на каждом входящем или исходящем коммутаторе составляет u = n −1.
В приближении Ли предполагается, что каждое внутреннее соединение между этапами уже занято вызовом с определенной вероятностью p , и что это полностью независимо между различными соединениями. Это переоценивает вероятность блокировки, особенно для малых r . Вероятность того, что данное внутреннее соединение занято, равна p = uq / m , где q — вероятность того, что входящее или исходящее соединение занято. Наоборот, вероятность того, что соединение свободно, равна 1− p . Вероятность того, что путь, соединяющий входящий коммутатор с исходящим коммутатором через определенный коммутатор среднего этапа, свободен, равна вероятности того, что оба соединения свободны, (1− p ) 2 . Следовательно, вероятность того, что он будет недоступен, равна 1−(1− p ) 2 = 2 p − p 2 . Вероятность блокировки или вероятность того, что ни один такой путь не свободен, равна [1−(1− p ) 2 ] m .
Приближение Якобеуса более точное, и чтобы увидеть, как оно выводится, предположим, что некоторое конкретное отображение вызовов, входящих в сеть Clos (входные вызовы), уже существует на коммутаторах средней ступени. Это отражает тот факт, что имеют значение только относительные конфигурации входного коммутатора и выходного коммутатора. Имеется i входных вызовов, входящих через тот же входной коммутатор, что и свободный входной терминал для подключения, и имеется j вызовов, покидающих сеть Clos (выходные вызовы) через тот же выходной коммутатор, что и свободный выходной терминал для подключения. Следовательно, 0 ≤ i ≤ u и 0 ≤ j ≤ u .
Пусть A — число способов назначения j выходных вызовов m коммутаторам средней ступени. Пусть B — число этих назначений, которые приводят к блокировке. Это число случаев, в которых оставшиеся m − j коммутаторов средней ступени совпадают с m − j из i входных вызовов, что является числом подмножеств, содержащих m − j этих вызовов. Тогда вероятность блокировки равна:
Если f i — вероятность того, что i других вызовов уже активны на входящем коммутаторе, а g j — вероятность того, что j других вызовов уже активны на исходящем коммутаторе, то общая вероятность блокировки равна:
Это можно оценить, обозначив каждое из f i и g j биномиальным распределением . После значительных алгебраических манипуляций это можно записать как:
Сети Clos также могут быть обобщены на любое нечетное число ступеней. Заменяя каждый центральный переключатель крестовины на 3-ступенчатую сеть Clos, можно построить сети Clos из пяти ступеней. Применяя тот же процесс повторно, возможны 7, 9, 11,... ступеней.
Перестраиваемая неблокируемая сеть такого типа с m = n = 2 обычно называется сетью Бенеша , хотя она обсуждалась и анализировалась другими [ кем? ] до Вацлава Э. Бенеша . Количество входов и выходов равно N = r × n = 2 r . Такие сети имеют 2 log 2 N − 1 стадий, каждая из которых содержит N /2 2×2 коммутаторов-переключателей, и используют в общей сложности N log 2 N − N /2 2×2 коммутаторов-переключателей. Например, сеть Бенеша 8×8 (т. е. с N = 8) показана ниже; она имеет 2 log 2 8 − 1 = 5 стадий, каждая из которых содержит N /2 = 4 2×2 коммутатора-переключателя, и использует в общей сложности N log 2 N − N /2 = 20 2×2 коммутаторов-переключателей. Центральные три этапа состоят из двух меньших сетей Бенеша 4×4, в то время как на центральном этапе каждый перекрестный переключатель 2×2 сам по себе может рассматриваться как сеть Бенеша 2×2. Таким образом, этот пример подчеркивает рекурсивное построение этого типа сети, при этом один из двух составляющих 4×4 Бенеша выделен. Цвет линий между блоками 2×2 выбран для того, чтобы подчеркнуть нечетно-четную рекурсивную декомпозицию входов, при этом нечетные входы идут в один подблок, а четные входы идут в другой подблок.
