Клос сеть

В области телекоммуникаций сеть Clos представляет собой своего рода многоступенчатую сеть коммутации каналов , которая представляет собой теоретическую идеализацию практических многоступенчатых систем коммутации. Его изобрел Эдсон Эрвин ^[1] в 1938 году и впервые официально оформленный Американским ^[2] инженер Чарльз Клос ^[3] в 1952 году.

Добавляя этапы, сеть Clos уменьшает количество точек пересечения, необходимых для создания большого перекрестного коммутатора . Топология сети Clos (показанная ниже) параметризуется тремя целыми числами n , m и r : n представляет количество источников, которые подаются на каждый из ; перекрестных коммутаторов входного каскада каждый ригельный выключатель входной ступени имеет m розеток; и имеется m перекладинных переключателей средней ступени.

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

Когда сеть Clos была впервые разработана, количество точек пересечения было хорошим приближением к общей стоимости системы коммутации. Хотя это было важно для электромеханических поперечин, оно стало менее актуальным с появлением СБИС , в котором межсоединения могли быть реализованы либо непосредственно в кремнии, либо в относительно небольшом кластере плат. С появлением сложных центров обработки данных с огромными межсетевыми структурами, каждый из которых основан на оптоволоконных линиях, сети Clos вновь приобрели значение. ^[4] Подтип сети Clos, сеть Бенеша, также недавно нашла применение в машинном обучении . ^[5]

Топология

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

Сети Clos определяются тремя целыми числами n , m и r . n представляет количество источников, которые подаются на каждый из перекрестных переключателей входного каскада . Каждый перекрестный переключатель входной ступени имеет m розеток, а также m перекрестных переключателей средней ступени. Между каждым переключателем входной ступени и каждым переключателем промежуточной ступени имеется ровно одно соединение. Имеются переключатели ступени регресса , каждый из которых имеет m входов и n выходов. Каждый переключатель промежуточной ступени подключается ровно один раз к каждому переключателю выходной ступени. Таким образом, входной каскад имеет r переключателей, каждый из которых имеет n входов и m выходов. Средний каскад имеет m переключателей, каждый из которых имеет r входов и r выходов. Выходной каскад имеет r переключателей, каждый из которых имеет m входов и n выходов.

Характеристики блокировки

Относительные значения m и n определяют характеристики блокировки сети Clos.

Неблокирующие сети Clos в строгом смысле ( m ≥ 2 n −1): первоначальный результат Clos 1953 года.

Если m ≥ 2 n −1, сеть Clos в строгом смысле является неблокируемой , что означает, что неиспользуемый вход входного коммутатора всегда может быть подключен к неиспользуемому выходу выходного коммутатора без необходимости переупорядочивания существующих вызовов . Этот результат лег в основу классической статьи Клоса 1953 года. Предположим, что на входе входного переключателя есть свободная клемма, и ее необходимо подключить к свободной клемме на конкретном выходном переключателе. В худшем случае n на рассматриваемом входном коммутаторе активны n -1 других вызовов, а на рассматриваемом выходном коммутаторе активны -1 других вызовов. Предположим также в худшем случае, что каждый из этих вызовов проходит через отдельный коммутатор промежуточного уровня. Следовательно, в худшем случае 2 n -2 коммутаторов промежуточного этапа не смогут передать новый вызов. Следовательно, чтобы гарантировать неблокирующую работу в строгом смысле, требуется еще один переключатель промежуточного каскада, что в общей сложности составляет 2 n -1.

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

Перестраиваемо неблокирующие сети Clos ( m ≥ n )

Если 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 ). ². Следовательно, вероятность того, что он недоступен, равна 1−(1− p ) ² = 2 п - п ². Тогда вероятность блокировки или вероятность того, что ни один такой путь не является свободным, равна [1−(1− p ) ²] ^м.

Приближение Якобеуса является более точным, и чтобы увидеть, как оно выводится, предположим, что некоторое конкретное сопоставление вызовов, входящих в сеть Clos (входящие вызовы), уже существует на коммутаторах промежуточного уровня. Это отражает тот факт, что только относительные важны конфигурации входного и выходного коммутаторов. Имеется i входных вызовов, поступающих через тот же входной коммутатор, что и подключаемый свободный входной терминал, и есть j вызовов, покидающих сеть Clos (выходные вызовы) через тот же выходной коммутатор, что и подключаемый свободный выходной терминал. Следовательно, 0 ⩽ i ⩽ u и 0 ⩽ j ⩽ u .

Пусть A — количество способов назначения j выходных вызовов m переключателям промежуточной ступени. Пусть B — количество этих назначений, которые приводят к блокировке. Это количество случаев, в которых оставшиеся m − j переключателей средней ступени совпадают с m − j входных вызовов i , что равно числу подмножеств, содержащих m − j этих вызовов. Тогда вероятность блокировки равна:

\beta _{ij}={\frac {B}{A}}={\frac {\left({\begin{array}{c}i\\m-j\end{array}}\right)}{\left({\begin{array}{c}m\\j\end{array}}\right)}}={\frac {i!j!}{(i+j-m)!m!}}

Если f _i — вероятность того, что i других вызовов уже активны на входном коммутаторе, а g _j — вероятность того, что j других вызовов уже активны на выходном коммутаторе, общая вероятность блокировки равна:

P_{B}=\sum _{i=0}^{u}\sum _{j=0}^{u}f_{i}g_{j}\beta _{ij}

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

P_{B}={\frac {(u!)^{2}(2-p)^{2u-m}p^{m}}{m!(2u-m)!}}

Закрытые сети с более чем тремя этапами

Сети Clos также можно обобщить на любое нечетное количество этапов. Заменив каждый перекрестный переключатель центральной ступени трехступенчатой сетью Clos, можно построить сети Clos из пяти ступеней. При многократном применении одного и того же процесса возможны 7, 9, 11,... этапы.

Сеть Бенеша ( m = n = 2)

Перестраиваемую неблокирующую сеть этого типа с m = n = 2 обычно называют сетью Бенеша , хотя она обсуждалась и анализировалась другими. ^{[ ВОЗ? ]} перед Вацлавом Э. Бенешем . Количество входов и выходов равно N = r × n = 2 r . Такие сети имеют 2 log ₂ N − 1 каскада, каждый из которых содержит N /2 2×2 перекрестных переключателя, и в общей сложности используют N log ₂ N − N /2 перекрестных переключателей 2×2. Например, сеть Бенеша 8×8 (т.е. с N ниже показана = 8); он имеет 2 log ₂ 8 − 1 = 5 ступеней, каждая из которых содержит N /2 = 4 перекладинных переключателя 2×2, и в общей сложности он использует N log ₂ N − N /2 = 20 перекладинных переключателей 2×2. Три центральных этапа состоят из двух меньших сетей Бенеша 4×4, в то время как на центральном этапе каждый перекрестный переключатель 2×2 сам по себе может рассматриваться как сеть Бенеша 2×2. Таким образом, этот пример подчеркивает рекурсивное построение сети этого типа.

См. также

Переключатель Banyan , альтернативный способ соединения сетей
Жирное дерево , альтернативный способ соединения сетей
Сеть Omega , альтернативный способ объединения сетей

Ссылки

^ Патент США 2244004.
^ «Место рождения Нью-Йорк» , перепись США 1940 года; Нью-Йорк, Квинс; стр. 41-320-19А, строка 17.
^ Кло, Чарльз (март 1953 г.). «Исследование неблокирующих коммутационных сетей» . Технический журнал Bell System . 32 (2): 406–424. дои : 10.1002/j.1538-7305.1953.tb01433.x . ISSN 0005-8580 .
^ Хогг, Скотт (11 января 2014 г.). «Clos Networks: старое снова стало новым» . Сетевой мир.
^ Мур, Сэмюэл (31 октября 2018 г.). «Flex Logix заявляет, что решила проблему DRAM в глубоком обучении» . ИИЭЭ . IEEE-спектр . Проверено 1 ноября 2018 г.
^ Бенеш, Вацлав Э. (11 сентября 1965 г.). Математическая теория соединения сетей и телефонного трафика . Академическая пресса . ISBN 0-12-087550-0 .
^ Холл, Филип (январь 1935 г.). «О представителях подмножеств» (PDF) . Журнал Лондонского математического общества . с1. 10 (1): 26–30. дои : 10.1112/jlms/s1-10.37.26 . Проверено 18 июня 2015 г.
^ Хуэй, Джозеф Ю. (1990). Теория коммутации и трафика для интегрированных широкополосных сетей . Клювер Академик. ISBN 0-7923-9061-Х .

[1] Патент США 2244004.

[2] «Место рождения Нью-Йорк» , перепись США 1940 года; Нью-Йорк, Квинс; стр. 41-320-19А, строка 17.

[3] Кло, Чарльз (март 1953 г.). «Исследование неблокирующих коммутационных сетей» . Технический журнал Bell System . 32 (2): 406–424. дои : 10.1002/j.1538-7305.1953.tb01433.x . ISSN 0005-8580 .

[4] Хогг, Скотт (11 января 2014 г.). «Clos Networks: старое снова стало новым» . Сетевой мир.

[5] Мур, Сэмюэл (31 октября 2018 г.). «Flex Logix заявляет, что решила проблему DRAM в глубоком обучении» . ИИЭЭ . IEEE-спектр . Проверено 1 ноября 2018 г.

[6] Бенеш, Вацлав Э. (11 сентября 1965 г.). Математическая теория соединения сетей и телефонного трафика . Академическая пресса . ISBN 0-12-087550-0 .

[7] Холл, Филип (январь 1935 г.). «О представителях подмножеств» (PDF) . Журнал Лондонского математического общества . с1. 10 (1): 26–30. дои : 10.1112/jlms/s1-10.37.26 . Проверено 18 июня 2015 г.

[8] Хуэй, Джозеф Ю. (1990). Теория коммутации и трафика для интегрированных широкополосных сетей . Клювер Академик. ISBN 0-7923-9061-Х .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]