Сеть Clos

В области телекоммуникаций , А сеть Клоса является своим родом многоступенчатой схемы коммутации сети , которая представляет собой теоретическую идеализацию практических, многоступенчатые системы коммутации. Он был изобретен Эдсон Эрвин ^[1] в 1938 году и первый формализуется Чарльз Клоса ( французского произношения: [ʃaʁl кло] ) ^[2] в 1952 году.

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

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

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

Топология [ править ]

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

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

Блокирующие характеристики [ править ]

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

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

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

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

Если m ≥ n , сеть Clos не блокируется , что означает, что неиспользуемый вход на входном коммутаторе всегда может быть подключен к неиспользуемому выходу на выходном коммутаторе, но для этого может потребоваться перегруппировка существующих вызовов путем назначения их к различным переключателям центральной сцены в сети Clos. ^[5] Чтобы доказать это, достаточно рассмотреть m = n , когда сеть Clos полностью используется; то есть выполняется r × n вызовов. Доказательство показывает , как любая перестановка этого г × п входных клемм на г × пвыходные клеммы могут быть разбиты на более мелкие перестановки, каждая из которых может быть реализована отдельными переключающими панелями в сети Clos с m = n .

В доказательстве используется теорема Холла о браке ^[6], получившая такое название, потому что ее часто объясняют следующим образом. Предположим, есть r мальчиков и r девочек. Теорема утверждает, что если каждое подмножество из k мальчиков (для каждого k такого, что 0 ≤ k ≤ r ) между ними знает k или более девочек, то каждый мальчик может быть объединен в пару с девушкой, которую он знает. Очевидно, что это необходимое условие для того, чтобы произошло спаривание; что удивительно, так это то, что этого достаточно.

В контексте сети Clos каждый мальчик представляет входной переключатель, а каждая девушка представляет выходной переключатель. Считается, что мальчик знает девочку, если соответствующие переключатели входа и выхода передают один и тот же вызов. Каждая группа из k мальчиков должна знать по крайней мере k девочек, потому что k входных коммутаторов передают k × n вызовов, и они не могут быть переданы менее чем k выходными коммутаторами. Следовательно, каждый входной коммутатор может быть спарен с выходным коммутатором, передающим тот же вызов, посредством взаимно-однозначного сопоставления. Эти вызовы r могут передаваться одним коммутатором среднего уровня. Если этот переключатель среднего уровня теперь удален из сети Clos, mуменьшается на 1, и мы остаемся с меньшей сетью Клоса. Затем процесс повторяется до тех пор, пока m = 1, и каждый вызов назначается переключателю среднего уровня.

Вероятности блокировки: приближения Ли и Якобея [ править ]

Реальные телефонные коммутационные системы редко бывают неблокируемыми строго по соображениям стоимости, и у них есть небольшая вероятность блокировки, которая может быть оценена с помощью приближений Ли или Якобея ^[7], при условии отсутствия перегруппировки существующих вызовов. Здесь потенциальное количество других активных вызовов на каждом входящем или выходном коммутаторе u = n -1.

В приближении Ли предполагается, что каждое внутреннее звено между этапами уже занято вызовом с определенной вероятностью p , и что это полностью независимо между разными звеньями. Это переоценивает вероятность блокировки, особенно при малых r . Вероятность того, что данный внутренний канал занят, равна p = uq / m , где q - вероятность того, что входящий или выходной канал занят. И наоборот, вероятность того, что ссылка свободна, равна 1− p . Вероятность того, что путь, соединяющий входной коммутатор с выходным коммутатором через конкретный коммутатор среднего уровня, свободен, - это вероятность того, что оба канала свободны, (1− p) ² . Следовательно, вероятность его недоступности равна 1− (1− p ) ² = 2 p - p ² . Вероятность блокировки или вероятность того, что ни один из таких путей не свободен, тогда составляет [1− (1− p ) ² ] ^m .

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

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

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

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

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

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

${\ displaystyle 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 2 перекрестных переключателей. Например, сеть Бенеша 8 × 8 (т.е. с N = 8) показана ниже; у него 2 журнала₂ 8 - 1 = 5 ступеней, каждая из которых содержит N / 2 = 4 перекрестных переключателя 2 × 2, и в общей сложности используется N  log ₂ N - N / 2 = 20 переключающих перекладин 2 × 2. Три центральных этапа состоят из двух меньших сетей Beneš 4 × 4, в то время как на центральной сцене каждый перекрестный коммутатор 2 × 2 может сам по себе рассматриваться как сеть Beneš 2 × 2. Таким образом, этот пример подчеркивает рекурсивное построение этого типа сети.

См. Также [ править ]

• Перекрестный переключатель Описывает переключающий элемент сети Clos.
• Неблокирующий коммутатор с минимальным охватом Описывает алгоритм переключения сети Clos.
• Свитч Banyan Альтернативный способ подключения сетей.
• Жирное дерево Альтернативный способ подключения сетей.
• Сеть Омега Альтернативный способ подключения сетей.

Ссылки [ править ]