Коммутация в сетях с использованием асинхронного метода переноса и доставки (стр. 11 из 17)
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]:
- Монотонность 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 - Условия не блокирования в широкополосной Баньян сети
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 (индекса копии), связанными с каждой ячейкой. Когда TNT (транслятор номера канала) получает копию ячейки, сначала он преобразует выходной адрес и IR (индексный эталон) в CI (индекс копии), а затем заменяет BCN (канал широкой рассылки) и CI (индекс копии) соответствующими TN (номерами каналов) в таблице перевода [14]. Процесс пересчета иллюстрирован на рисунке 4.8.
Рисунок 4.8 - Пересчет номера канала с помощью табличного поиска
4.2 ПЕРЕПОЛНЕНИЕ И РАЗДЕЛЕНИЕ ВЫЗОВА
В RAN (схеме сумматоров) копирующей системы происходит перегрузка, в том случае, когда число запросов копий превышает пропускную способность копирующей системы. Если частичное обслуживание (которое так же называется разделением вызова) невозможно при копировании ячейки, и ячейка должна произвести все свои копии за один временной интервал, тогда в случае переполнения пропускная способность может снижаться. На рисунке 4.9 показано переполнение, которое произошло у 3-го порта, и пропускаются только пять копий ячеек, при наличии более восьми запросов [14].
Рисунок 4.9 - Не блокирующая копирующая система 8´8 без разделения вызовов
4.2.1 ПЕРЕПОЛНЕНИЕ И РАВНОДОСТУПНОСТЬ ВВОДОВ
Переполнение также делает входящие ячейки неравноправными, так как начало работы RAN (схема сумматоров) фиксирована. Поскольку вычисление текущей суммы начинается всегда с 0-го входного порта каждый временной интервал, входные порты с малыми номерами имеют высший приоритет обслуживания, чем входные порты с большими номерами. С этой трудностью можно справиться, если разработать RAN таким образом, чтобы подсчитывать текущие суммы циклично, начиная с любого входного порта. Начало вычисления текущих сумм каждый промежуток времени адаптивно определяется состоянием переполнения в предыдущий промежуток времени. Такая цикличная RAN (CRAN) показана на рисунок 4.10. Текущий исходный пункт - порт 3, разделение вызова происходит у порта 6, поэтому в следующий временной интервал исходным пунктом будет порт 6. Отрицательный индексный эталон -3, данный DAE, значит, что запрос копии из порта 3 является остаточным, и в предыдущий временной интервал были созданы три копии [18,19].
Рисунок 4.10 - Циклическая схема сумматоров (CRAN) в копирующей системе 8´8
4.2.2 ЦИКЛИЧЕСКАЯ СХЕМА СУММАТОРА (CRAN)
На рисунке 4.10 показано строение 8´8 CRAN. Ассоциированный формат заголовка ячейки состоит из трех полей: 1 - поля индикатора запуска (SI), 2 - текущая сумма (RS), 3 - адрес трассировки (RA). Только один порт, являющийся исходным пунктом, изначально имеет SI, отличный от нуля. RS поле первоначально устанавливается в число копий, запрашиваемых входной ячейкой [11,14]. Поле RA первоначально устанавливается в 1, если порт является активным. Если порт свободен, оно устанавливается в 0. На выходе RAN поле RA переносит текущую сумм на биты активности, чтобы использовать ее в качестве адреса трассировки в следующем концентраторе. В каждом каскаде CRAN используется ряд цикличных трактов, и таким образом, рекурсивное вычисление текущих сумм может производиться циклично. Для эмуляции вычисления фактической текущей суммы из исходного пункта, некоторые тракты должны быть удалены, как показано на рисунке 4.10.
Рисунок 4.10- Циклическая RAN 8´8
Это равносильно тому, как если, имея теневые (вспомогательные) узлы, не учитывать их каналы при вычислении текущих сумм. Эти узлы следуют за заголовком ячейки с поле SI, равным 1, во время передачи его через CRAN из исходного пункта. Модификация заголовка представлена на рисунке 4.11.