Коммутация в сетях с использованием асинхронного метода переноса и доставки (стр. 10 из 17)

Рисунок 3.21- Двойная коммутационная система 8x8 с перестановкой

Это учитывается в следующем алгоритме. Сначала 2´2 аналогичных коммутационных элемента SN и USN объединяются и образуют 4x4 коммутационных элемента для того, чтобы можно было коммутировать ячейки между SN и USN. На рисунке 3.21 представлена двойная SN, образованная 4´4 коммутационными элементами. Используется новая схема маркирования. Четыре ввода/вывода коммутационного узла помечаются 00, 01, 10, 11 сверху вниз. Выходы 00 и 01 соединяются со следующим каскадом по примеру USN, а выводы 10 и 11 соединяются со следующим каскадом по примеру SN.

Вводы 00 и 01 соединяются с предыдущим каскадом по SN образцу, а вводы 10 и 11 соединяются с предыдущим каскадом по образцу USN. Канал с меткой <la,0b> - это не тасующий канал, а канал с меткой <0a,1b> - тасующий. Два узла (a₁, a_n-1) И (b_i, b_n-1) соединены не тасующим каналом, если <0b₁, 1a_n-1> и они соединены тасующим каналом, если a₁...a_n-2 = b₂...b_n-1 Так как каждый коммутационный узел имеет четыре вывода, то для определения требуемого вывода ячейки на каждом каскаде, необходимо два бита маршрутизации. Ячейка с назначением D=d₁...d_n может трассироваться как через USN, так и через SN. Соответственно, изначальный ярлык маршрутизации ячейки установлен на 0d₁…0d_n (USN) или на 1d_n...1d₁ (SN) Состояние ячейки в определенные временные интервалы обозначается (c₁r₁..c_kr_kx₁…x_n-1) Возможны две регулярные передачи в коммутационный узел. Ячейка будет отправлена в не тасующий канал, если c_k=0 и в тасующий, если c_k=1 [14,19].

Соответственные состояния передачи выражаются:

Ячейки с начальной трассировкой, установленной на 0d₁…0d_n (1d_n …1d₁) будут оставаться в каналах USN (SN) в течение всего процесса трассировки, пока он не завершится в одном из каналов USN(SN).

Направление трассировки:

1. Если вывод c_kr_k доступен и k=1, ячейка доходит по назначению. Выводим ячейку перед следующем перемешиванием, если с=1 и после следующей не тасовки, если с=0.

2. Если вывод c_kr_k доступен и k>l, удаляем два наименее значимых бита из ярлыка трассировки и отправляем ячейку в следующий каскад.

3. Если вывод c_kr_k недоступен и k<n выбираем любой другой доступный вывод, присоединяем к ярлыку трассировки два соответствующих бита для исправления ошибок и отправляем ячейку в следующий каскад.

Если вывод c_kr_k недоступен и k=n устанавливаем исходное значение ярлыка трассировки 0d₁…0d_n (1d_n …1d₁), чтобы предотвратить рост длины ярлыка.

На рисунке 3.22 представлен полный алгоритм для исправления ошибок [14].

Рисунок 3.22 - Полный алгоритм исправления ошибок

Для любого узла с меткой (x₁...x_n-1) ярлык исправления ошибок выводов 00 и 01 x_n-1 и выводов 10 и 11 0х. В обоих случаях ярлык исправления ошибок - второй компонент

в канальном ярлыке <cr, > где x=x_c+c(n-1). Поэтому, ячейка, отклонившаяся в канал будет возвращена в предыдущее состояние через канал <cr, > в следующем каскаде (рисунок 3.23 [20].

Рисунок 3.23- Пример исправления ошибок трассировки в DSN

3.5.4 КОПИРУЮЩИЕ СИСТЕМЫ ДЛЯ МНОГОАДРЕСНОЙ ПЕРЕДАЧИ

На рисунке 3.24 показана серийная комбинация копирующей сети и двухточечного коммутатора для обеспечения многоточечной связи. Копирующая система одновременно тиражирует ячейки из разных вводов и затем трассирует копии ячеек широкой рассылки по их назначению с помощью двухточечного коммутатора [12,14].

Копирующая система состоит из следующих основных частей (рисунок 3.25) [14]:

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

2. шифратор адресов (DAE), создающий новые заголовки ячеек из соседних текущих сумм.

3. коммутационная широкополосная Баньян сеть (BBN), в которой коммутационные узлы широкой рассылки делают копии ячеек с заголовками в два бита.

Рисунок 3.24 - Коммутатор многоадресной рассылки

4. шифратор адресов (DAE), создающий новые заголовки ячеек из соседних текущих сумм.

5. коммутационная широкополосная Баньян сеть (BBN), в которой коммутационные узлы широкой рассылки делают копии ячеек с заголовками в два бита.

6. транслятор номеров каналов (TNT), определяющий номера выходных каналов для каждой копии ячейки.

Рисунок 3.25 - Основные компоненты не блокирующей копирующей системы

Механизм многоадресной передачи копирующей системы основан на передаче и преобразовании заголовков (рисунок 3.26). Номера копий (CN), указанные в заголовках ячеек рекурсивно суммируются в схеме сумматора. На основе полученных сумм шифраторы адресов создают новые заголовки ячеек с двумя полями: поле фиктивного адресного интервала и поле индексного эталона (IR). Поле адресного интервала образовано соседними текущими суммами, минимальными (MIN) и максимальными (МАХ). Индексный эталон приравнивается минимуму адресного интервала и впоследствии используется транслятором номеров каналов для определения индекса копии (СI).Широкополосная Баньян сеть копирует ячейки по алгоритму логического деления интервалов на основе адресного интервала в новом заголовке. Когда копия прибывает в нужный вывод, TNT вычисляет ее CI на основе адреса вывода и индексного эталона. Номер канала широкой рассылки (BCN) и CI образуют уникальный идентификатор, указывающий на номер канала (TN), который добавляется заголовку ячейки и используется для ее трассировки по назначению [14,20].

Рисунок 3.26 - Трансляция заголовков в копирующей системе

4 ШИРОКОПОЛОСНАЯ БАНЬЯН СЕТЬ

4.1 ОСНОВЫ ШИРОКОПОЛОСНАЯ БАНЬЯН СЕТЬ

4.1.1 ОБОБЩЕННЫЙ АЛГОРИТМ САМОТРАССИРОВКИ

Широкополосная Баньян сеть - это сеть с коммутационными узлами, копирующими ячейки. Ячейка, прибывающая в каждый узел, может быть либо трассирована в один из выводных каналов, либо дублирована и отправлена по двум выводным каналам. Существует три варианта Log₂3=1.585, а это значит, что минимальный объем информации заголовка = 2 бит а каждый узел [1,10].

На рисунке 4.1 представлен обобщенный алгоритм одно - битовой самотрассировки для ряда N-битных адресов с произвольным назначением. Когда ячейки прибывает в узел k-каскада, трассировка ячейки определяется k битами заголовков всех адресов назначения. Если все они равны 0 или 1, тогда ячейка отправляется в выводы 0 или 1 соответственно. В противном случае, копии ячеек отправляются в оба вывода, и соответственно копиям этих двух ячеек в заголовках изменяются адреса назначения: заголовки копий ячеек, отправленных в вывод 0 или 1, содержат адреса первоначальных заголовков в k бит, равных 1 или 0 соответственно.

Рисунок 4.1 - Обобщенный алгоритм самомаршрутизации

На рисунке 4.2 дерево ввода-вывода, образуемое обобщающим алгоритмом самомаршрутизации.

Рисунок 4.2 - Дерево ввода-вывода, образуемое обобщающим алгоритмом самомаршутизации

При выполнении обобщенного алгоритма самотрассировки могут возникнуть трудности [12,18].

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

oпри модификации заголовков ячеек учитывается вся совокупность адресов, что усложняет работу коммутационных узлов.

oсхема всех каналов выводов и вводов образует дерево в сети.

Деревья, образованные произвольным рядом входных ячеек, зависят от каналов. Таким образом, из-за нерегулярности ряда абсолютных адресов назначения в заголовках ячеек, система является блокирующей. Но в копирующей системе, где ячейки копируются, но не отправляются по абсолютным адресам, вместо абсолютных адресов могут использоваться фиктивные.

Фиктивные адреса каждой ячейки могут выстраиваться непрерывно, так чтобы весь ряд фиктивных адресов представлял интервал (адресный), состоящий из MIN и МАХ текущих сумм. Адресный интервал входных ячеек можно сделать монотонным для обеспечения деблокирования в нижеописанной широкополосной Баньян сети.

4.1.2 АЛГОРИТМ ЛОГИЧЕСКОГО ДЕЛЕНИЯ ИНТЕРВАЛОВ

Адресный интервал - это непрерывный ряд двоичных N-битных номеров, которые можно представить двумя номерами: минимальным и максимальным. Допустим, что узел в k каскаде получает ячейку, заголовок которой содержит адресный интервал, состоящий из двух бинарных номеров min(k-1)=m₁...m_N и max(k-1)=M₁...M_N, где k-1 обозначает каскад, из которого ячейка прибыла в k каскад. По обобщенному алгоритму самотрассировки маршрут ячейки определяется так (рисунок 4.3) [14]: