Коммутация в сетях с использованием асинхронного метода переноса и доставки
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ржит адресный интервал, состоящий из двух бинарных номеров 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) - Дерево, образованное при копировании ячеек в соответствии с их адресными интервалами
4.1.3 УСЛОВИЯ НЕ БЛОКИРОВАНИЯ В ШИРОКОПОЛОСНЫХ БАНЬЯН СЕТЯХ
Широкополосная Баньян сеть является не блокирующей, если активные входы х1…xk и соответствующие выходы Y1...Yk соответствуют следующим требованиям [13,18]:
- Монотонность Y1Yk
- Концентрация: любой ввод между двумя активными вводами так же является активным.
Неравенство 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 - Условия не блокирования в широкополосной Баньян сети
4.1.4 ПРОЦЕСС КОДИРОВАНИЯ
Схема сумматора (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. Эта последовательность обеспечивает деблокирование в баньян сети широкой рассылки.
4.1.5 КОНЦЕНТРАЦИЯ
Для того, чтобы широкополосная Баньян сеть была не блокирующей, необходимо сократить число свободных вводов, находящимися между активными вводами. Это должно быть сделано до ввода ячеек в сеть, т.е. до RAN или сразу же после DAE.
Так обратная Баньян сеть используется для концентрации активных вводов в непрерывный список [11,13]. Для получения ряда непрерывных монотонных адресов в обратной Баньян сети трассировочный адрес определяется текущими суммами на бит активности, (рисунок 4.6).
Рисунок 4.7 - Входной концентратор состоящий из сумматора адресов и обратной Баньян сети
4.1.6 ПРОЦЕСС ДЕКОДИРОВАНИЯ
Когда ячейка выходит из баньян сети широкой рассылки, адресный интервал в ее заголовке содержит только один адрес, т.е. по алгоритму логического разделения интервалов[13]:
min(log2N)=max(log2N)=Выходному адресу
Копии ячеек, из одного и того же канала широкой рассылки отмечаются CI, который определяется на выходе широкополосной Баньян сети следующим образом (рисунок 4.7):
СI=Выходной адрес-индексный эталон
Рисунок 4.7 - Вычисление индексов копий
Индексный эталон изначально приравнивается минимуму адресного интервала. TNT (транслятор номера канала) присваивает абсолютный адрес каждой копии ячейки, и она трассируется к своему конечному назначению в последующий двухточечный коммутатор. Присвоение TN (номера канала) завершается простым табличным поиском, при котором идентификатор состоит из BCN (канала широкой рассылки) и CI (