При конфликте в узле, только одна ячейка будет трассирована верно, а все остальные не попадут к нужным выходам. Отклонившаяся ячейка может начать трассировку вновь (с трассировочным ярлыком в исходном состоянии dn...d1) с того места, где произошло отклонение. Поэтому, если расширить SN систему так, чтобы она включала более n каскадов, то отклонившиеся ячейки могут достигнуть своего вывода на последующих каскадах. Т.к. некоторые ячейки достигнут своего вывода позже других на несколько каскадов, необходим мультиплексор для сбора ячеек, достигающих физических каналов одного и того же логического адреса на разных каскадах. В итоге, ячейка попадет по адресу своего назначения, при условии, что число L каскадов достаточно велико. Если она не находит своего вывода и на последнем из L каскадов, она считается потерянной.
SN система с исправлением ошибок очень эффективна, особенно при большом значении п. Так как, при каждом отклонении ячейки, ее трассировка должна начинаться снова [20]. Рассмотрим диаграмму состояний на рисунке 3.16.
Рисунок 3.16 - Фазовая диаграмма ячейки в SN сети
Состояние (положение) - это расстояние или число каскадов до вывода. Требуемая сеть должна быть такой, как показано на рис. 3.17, в которой штраф - это возврат только на один каскад [18,14].
Рисунок 3.17 - Фазовая диаграмма со штрафным состоянием
На рисунке 3.18 изображена коммутационная система 8x8 без перестановки (USN). Она является зеркальным отражением системы SN. Трассировка через последовательность каскадов основана на принципе наименее значимый бит через наиболее значимый бит
Рисунок 3.18 - Коммутационная система без перестановки с пятью Каскадами
Пользуясь той же схемой вычислений, как в случае с SN, канал ячейки с адресом источника S=s1...sn и адресом назначения D=d1...dn может быть выражен так[18,14]:
(n-1) разрядное окно, перемещающееся по двоичной цепи d2...dn, s1...sn-1 на один бит каждый каскад справа на лево, представляет последовательность узлов на канале трассировки.
Первоначальное состояние ячейки (d1...dn, s1...sn-1) и состояние перехода дано как:
На последнем каскаде ячейка находится в состоянии (-d1d2...dn) и достигает назначения [18].
Предположим, что USN наложена на SN и каждый узел USN соединен с соответствующим узлом SN, так, что ячейка из любого ввода может попасть в любой вывод узла. Взаимосвязи с перестановкой и без перестановки между соседними каскадами компенсируют друг друга, таким образом, что ошибка, вызванная отклонением ячейки в SN, может быть исправлена в USN возвратом только на один шаг. Рассмотрим рисунок 3.19.
Рисунок 3.19 - Исправление ошибок в сетях SN с помощью USN
Рисунок 3.20
На рисунке 3.20 ячейка А поступает в SN из входа 010 и выходит из вывода 101, ячейка В поступает во ввод 100 и выходит через вывод 100. Во втором каскаде они сталкиваются, когда обе прибывают в узел 01 и делают запрос выводу 0. Допустим, что ячейка В выигрывает, а ячейка А отклоняется и попадает в 11 узел третьего каскада. Допустим, что ячейка А попадает в аналогичный 11 узел в USN и коммутируется в вывод 0. Затем она возвращается в узел 01, тот самый узел, где произошла ошибка в двух каскадах. В этом месте ошибка отклонения была исправлена и ячейка А продолжила свой путь по нужному каналу в SN. Любая ошибка трассировки исправляется в SN обратной операцией трассировки в USN. Более точно этот процесс можно сформулировать так. Рассмотрим ячейку в состоянии (r1…rk, x1…xn-1) Ячейка должна быть трассирована в канал <rk, x1> в SN. Положим, она отклонилась, вместо того, чтобы попасть в канал <rk, x1> ячейка достигает узла (x2.....хn-1rk) в следующем каскаде. Исправление ошибки трассировки начинается с присоединения бита x1 к ярлыку трассировки, вместо перемещения бита rk, таким образом, состояние ячейки в следующем каскаде будет x1. Затем ячейка перемещается в аналогичный узел в USN для исправления ошибки. В случае успешной трассировки, она будет направлена в канал rk и вернется в предыдущее состояние (r1…rk x1, x2…xn-1 rk). Taким же образом, ошибка, происходящая в USN исправляется с помощью SN за один шаг. Т.е. ячейка в SN может отклониться в канал USN и наоборот [14,20].
Рисунок 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> - тасующий. Два узла (a1, an-1) И (bi, bn-1) соединены не тасующим каналом, если <0b1, 1an-1> и они соединены тасующим каналом, если a1...an-2 = b2...bn-1 Так как каждый коммутационный узел имеет четыре вывода, то для определения требуемого вывода ячейки на каждом каскаде, необходимо два бита маршрутизации. Ячейка с назначением D=d1...dn может трассироваться как через USN, так и через SN. Соответственно, изначальный ярлык маршрутизации ячейки установлен на 0d1…0dn (USN) или на 1dn...1d1 (SN) Состояние ячейки в определенные временные интервалы обозначается (c1r1..ckrkx1…xn-1) Возможны две регулярные передачи в коммутационный узел. Ячейка будет отправлена в не тасующий канал, если ck=0 и в тасующий, если ck=1 [14,19].
Соответственные состояния передачи выражаются:
Ячейки с начальной трассировкой, установленной на 0d1…0dn (1dn …1d1) будут оставаться в каналах USN (SN) в течение всего процесса трассировки, пока он не завершится в одном из каналов USN(SN).
Направление трассировки:
1. Если вывод ckrk доступен и k=1, ячейка доходит по назначению. Выводим ячейку перед следующем перемешиванием, если с=1 и после следующей не тасовки, если с=0.
2. Если вывод ckrk доступен и k>l, удаляем два наименее значимых бита из ярлыка трассировки и отправляем ячейку в следующий каскад.
3. Если вывод ckrk недоступен и k<n выбираем любой другой доступный вывод, присоединяем к ярлыку трассировки два соответствующих бита для исправления ошибок и отправляем ячейку в следующий каскад.
Если вывод ckrk недоступен и k=n устанавливаем исходное значение ярлыка трассировки 0d1…0dn (1dn …1d1), чтобы предотвратить рост длины ярлыка.
На рисунке 3.22 представлен полный алгоритм для исправления ошибок [14].
Рисунок 3.22 - Полный алгоритм исправления ошибок
Для любого узла с меткой (x1...xn-1) ярлык исправления ошибок выводов 00 и 01 xn-1 и выводов 10 и 11 0х. В обоих случаях ярлык исправления ошибок - второй компонент в канальном ярлыке <cr, > где x=xc+c(n-1). Поэтому, ячейка, отклонившаяся в канал будет возвращена в предыдущее состояние через канал <cr, > в следующем каскаде (рисунок 3.23 [20].
Рисунок 3.23- Пример исправления ошибок трассировки в DSN
На рисунке 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].
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
