Рисунок 3.26 - Трансляция заголовков в копирующей системе
Широкополосная Баньян сеть - это сеть с коммутационными узлами, копирующими ячейки. Ячейка, прибывающая в каждый узел, может быть либо трассирована в один из выводных каналов, либо дублирована и отправлена по двум выводным каналам. Существует три варианта Log23=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 и МАХ текущих сумм. Адресный интервал входных ячеек можно сделать монотонным для обеспечения деблокирования в нижеописанной широкополосной Баньян сети.
Адресный интервал - это непрерывный ряд двоичных N-битных номеров, которые можно представить двумя номерами: минимальным и максимальным. Допустим, что узел в k каскаде получает ячейку, заголовок которой содержит адресный интервал, состоящий из двух бинарных номеров min(k-1)=m1...mN и max(k-1)=M1...MN, где k-1 обозначает каскад, из которого ячейка прибыла в k каскад. По обобщенному алгоритму самотрассировки маршрут ячейки определяется так (рисунок 4.3) [14]:
1. если mk=Мk=0 или mk=Мk=1, тогда отправьте ячейку в выводы 0 или 1 соответственно.
2. Если mk=0 и Мk=1, тогда копируйте ячейку, модифицируйте заголовки обеих копий (по ниже данной схеме) и отправьте копии в соответствующий канал.
Рисунок 4.3 - Логическая схема коммутационного узла в k каскаде широкополосной Баньян сети
Модификация заголовка ячейки заключается в делении исходного адресного интервала на два подинтервала, что выражается в следующей рекурсии: для ячейки, отправленной в канал 0
min(k)=min (k-1)=sm1...mN,
max(k)=M1.....Mk-101....1,
И для ячейки, отправленной в канал 1
min(k)=m1....mk-1 10....0,
max(k)=max(k-1)=M1.....МN
На рисунке 4.4 (а) представлена схема алгоритма логического деления интервалов. Из правил ясно, что mi=Mi, i=1...k-1 действительно для каждой прибывающей в каскад k ячейки. Событие mk=1 и Mk=0 исключено.
Рисунок 4.4 (а) - Схема алгоритма логического деления интервалов
На рисунке 4.4 (b) представлено дерево, которое образуется при копировании ячеек в соответствии с их адресными интервалами [12,14].
Рисунок 4.4 (b) - Дерево, образованное при копировании ячеек в соответствии с их адресными интервалами
Широкополосная Баньян сеть является не блокирующей, если активные входы х1…xk и соответствующие выходы Y1...Yk соответствуют следующим требованиям [13,18]:
- Монотонность Y1<Y2 <....<Yk или Y1>Y2>...>Yk
- Концентрация: любой ввод между двумя активными вводами так же является активным.
Неравенство Yi<YJ означает, что каждый адрес выхода в YJ меньше адреса выхода в YJ. На рисунке 4.5 дан пример неблокирования с активными вводами x1=7, х2=8, х3=9 и соответствующими выходами Y1={1,3}, Y1= {4,5,6}, Y3={7,8,10,13,14}.
Рисунок 4.5 - Условия не блокирования в широкополосной Баньян сети
Схема сумматора (RAN), совместно с шифратором адресов (DAE), используется для организации адресов назначения каждой ячейки таким образом, чтобы каждая существенная ячейка была копирована без конфликтов в широкопосной Баньян сети. В ней проходят два процесса копирования ячеек: процесс кодирования и процесс декодирования. В процессе кодирования осуществляется преобразование рядов номеров копий, указанных в заголовках входящих ячеек, в ряд монотонных адресных интервалов, образующих заголовки ячеек в широполосной Баньян сети. Этот процесс осуществляется схемой сумматора и рядом шифраторов фиктивных номеров. От процесса декодирования зависит адрес назначения копий с транслятора номеров канала (TNT) [12,14].
Рекурсивная структура log2N схемы сумматора показана на рисунке 4.6.
Рисунок 4.6 - Схема сумматора и шифратора фиктивных адресов
Схема сумматора состоит из (N/2)log2N сумматоров, каждый с двумя вводами и выводами. Вертикальная линия обозначает пересылку. Восточный ввод равен сумме западного и северного вводов, а южный вывод продолжает северный ввод. Текущие суммы CN генерируются у каждого порта в конце log2N каскадов, а затем шифраторы фиктивных адресов образуют новые заголовки из соседних текущих сумм. Новый заголовок содержит два поля: интервал фиктивных адресов, представленный двумя 1оg2N-битовыми двоичными номерами (минимальным и максимальным). Другое поле содержит индексный эталон, равный минимуму адресного интервала. Заметьте, что длина каждого интервала равна соответствующему номеру копии в обоих адресных схемах. Примем за Si i-текущую сумму. Тогда последовательность интервалов фиктивных адресов производится так [18]:
(0,S0-1),(S0,S1)……..(SN-2,SN-1-1)
где адрес размещается, начиная с 0. Эта последовательность обеспечивает деблокирование в баньян сети широкой рассылки.
Для того, чтобы широкополосная Баньян сеть была не блокирующей, необходимо сократить число свободных вводов, находящимися между активными вводами. Это должно быть сделано до ввода ячеек в сеть, т.е. до RAN или сразу же после DAE.
Так обратная Баньян сеть используется для концентрации активных вводов в непрерывный список [11,13]. Для получения ряда непрерывных монотонных адресов в обратной Баньян сети трассировочный адрес определяется текущими суммами на бит активности, (рисунок 4.6).
Рисунок 4.7 - Входной концентратор состоящий из сумматора адресов и обратной Баньян сети
Когда ячейка выходит из баньян сети широкой рассылки, адресный интервал в ее заголовке содержит только один адрес, т.е. по алгоритму логического разделения интервалов[13]:
min(log2N)=max(log2N)=Выходному адресу
Копии ячеек, из одного и того же канала широкой рассылки отмечаются CI, который определяется на выходе широкополосной Баньян сети следующим образом (рисунок 4.7):
СI=Выходной адрес-индексный эталон
Рисунок 4.7 - Вычисление индексов копий
Индексный эталон изначально приравнивается минимуму адресного интервала. TNT (транслятор номера канала) присваивает абсолютный адрес каждой копии ячейки, и она трассируется к своему конечному назначению в последующий двухточечный коммутатор. Присвоение TN (номера канала) завершается простым табличным поиском, при котором идентификатор состоит из BCN (канала широкой рассылки) и CI (индекса копии), связанными с каждой ячейкой. Когда TNT (транслятор номера канала) получает копию ячейки, сначала он преобразует выходной адрес и IR (индексный эталон) в CI (индекс копии), а затем заменяет BCN (канал широкой рассылки) и CI (индекс копии) соответствующими TN (номерами каналов) в таблице перевода [14]. Процесс пересчета иллюстрирован на рисунке 4.8.
Рисунок 4.8 - Пересчет номера канала с помощью табличного поиска
В RAN (схеме сумматоров) копирующей системы происходит перегрузка, в том случае, когда число запросов копий превышает пропускную способность копирующей системы. Если частичное обслуживание (которое так же называется разделением вызова) невозможно при копировании ячейки, и ячейка должна произвести все свои копии за один временной интервал, тогда в случае переполнения пропускная способность может снижаться. На рисунке 4.9 показано переполнение, которое произошло у 3-го порта, и пропускаются только пять копий ячеек, при наличии более восьми запросов [14].
Рисунок 4.9 - Не блокирующая копирующая система 8´8 без разделения вызовов
Переполнение также делает входящие ячейки неравноправными, так как начало работы RAN (схема сумматоров) фиксирована. Поскольку вычисление текущей суммы начинается всегда с 0-го входного порта каждый временной интервал, входные порты с малыми номерами имеют высший приоритет обслуживания, чем входные порты с большими номерами. С этой трудностью можно справиться, если разработать RAN таким образом, чтобы подсчитывать текущие суммы циклично, начиная с любого входного порта. Начало вычисления текущих сумм каждый промежуток времени адаптивно определяется состоянием переполнения в предыдущий промежуток времени. Такая цикличная RAN (CRAN) показана на рисунок 4.10. Текущий исходный пункт - порт 3, разделение вызова происходит у порта 6, поэтому в следующий временной интервал исходным пунктом будет порт 6. Отрицательный индексный эталон -3, данный DAE, значит, что запрос копии из порта 3 является остаточным, и в предыдущий временной интервал были созданы три копии [18,19].
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
