это 0, ячейка будет выдвинута на высший, исходящий уровень; если это 1,то ячейка отправляется на низший уровень. На следующем уровне проверяется бит b1, передача сигнала происходит аналогично.
Рисунок 3.2 - Баньян сеть 8´8
Внутренняя блокировка происходит в случае когда ячейка потеряна из-за конфликтных ситуаций на уровне сети. Рисунок 3.3 приводит пример внутренней блокировки внутри Баньян сети 8x8. Тем не менее, Баньян сеть не будет иметь внутренних блокировок, если будут соблюдены следующие условия [12]:
· Нет свободного входного сигнала между любыми двумя активными входами.
· Выходные адреса ячеек находятся либо в прямом, либо в обратном порядке.
Рисунок 3.3 - Блокировка в Баньян сети 8´8
Рисунок 3.4
(a) - Не блокируемая Баньян сеть для входных сигналов
(b) - Сортирующая Баньян сеть
Рассмотрим рисунок 3.4. Предположим, что Баньян сети предшествует сети которая накапливает ячейки и сортирует их, учитывая их выходные значения. Получившаяся в результате структура является деблокирующей сортирующей Баньян сетью.
Эта сеть формируется серией объединенных сетей различных размеров [12,14]. Рисунок 3.5 демонстрирует сортирующую Батчер сеть 8x8, состоящую из объединенных сетей трех различных размеров. Объединенная сеть на рис.3.6 состоит из 2´2 сортирующих элементов в каскадах, и схема соединения между каждой парой смежных каскадов аналогична схеме Баньян сети. Можно заметить, что если адреса первой половины входящих ячеек расположены в возрастающем порядке, а адреса второй половины - в убывающем, то объединенная сеть будет сортировать ячейки на выходе в прямом порядке. Сортирующая сеть 8´8 будет сформирована, если 8´8 объединенной сети предшествуют две объединенных сети 4´4 и четыре объединенных (сортирующих) элемента 2´2. Произвольный список из восьми входных ячеек будет распределен сначала на четыре списка по две ячейки, а затем - в два списка по четыре ячейки и наконец - в список из восьми ячеек.
Объединенная сеть N´N состоит из log2N уровней и (N log2N)/2 уровней. Сортирующая сеть имеет 1+2+......+ log2N=(log2N)(log2N+l)/2 уровней и (N log2N)(log2N+l)/2 элементов [14].
Рисунок 3.5 - Сортирующая Батчер сеть 8´8
Рисунок 3.6 - Структура передающей сети
Следующий 3-х эталонный алгоритм является решением для выходного спорного сигнала в Батчер-Баньян коммутаторе.(рис 3.7(а)).
Рисунок 3.7 - 1 этап: отправка запроса
В первую фазу алгоритма (фазу арбитража) каждый вводной порт I посылает в сортирующую сеть краткий запрос, содерж6щий только информацию об источнике и назначении (ячейки). В сортирующей сети ячейки рассматриваются в порядке возрастания, по адресам их назначения. Запросы сортируются все вместе и выбирается тот, чей адрес назначения отличен от предыдущего в сортировочном списке [14,17].
Поскольку результаты арбитража не известны входным портам, выбранные запросы посылают уведомление своим вводным портам через взаимосвязанную сеть во вторую фазу (фазу уведомления). Сеть с обратной связью представлена на рисунке 3.7(в), состоит из N фиксированных соединений, каждый выход сети Батчера соединен с входом сети Батчера.
Рисунок 3.8 - 2 этап: уведомление решающих портов
Каждое подтверждение несет источник, который получил разрешение на вход Батчер сети. Эти источники проходят через всю Батчер-Баньян сеть на различные выхода, учитывая адрес источника. Когда трассировка уведомлений обратно через идентичную специализированную сеть ко вводам закончена, выводы узнают свои результаты арбитража. Вводам, получившим уведомление, обеспечивается бесконфликтный вывод ячеек.
Рисунок 3.9 - 3 этап: отправка ячеек с информацией
Эти входные порты перемещают полную ячейку на третьем последнем этапе, через такую же Батчер-Баньян сеть (рисунок 3.7(с)). Вводы, не получившие уведомления, сохраняют свои ячейки в буфере следующего трехфазового цикла.
В Баньян коммутаторе с накопителем предусмотрено кольцевое резервирование (рисунок 3.10). Этот коммутатор состоит из Баньян коммутационной системы с накопителем, нескольких коммутационных интерфейсов, кольцевой адаптер (RHE) и синхронизатора [17,19].
Рисунок 3.10 - Батчер - Баньян коммутатор с кольцевым резервирование
Интерфейс коммутатора осуществляет кольцевое резервирование, буферизацию входящих ячеек, синхронизацию ячеек, отправленных в коммутационную систему и буферизацию ячеек на выходе. Входящие в коммутатор ячейки буферизуются в FIFO, до резервирования. Когда резервирование на выводе успешно завершено, ячейка доставляется в коммутационную систему в начале следующего цикла. После этого следующая ячейка из очереди может проходить резервирование. При выходе из коммутационной системы, ячейка буферизуется в интерфейс, чтобы затем быть переданной по назначению RHE дает два сигнала синхронизации в коммутаторе: (синхронизации битов и начала цикла), три сигнала кольцевого резервирования (сигнал включения в работу кольца, сигнал данных кольца и синхронизации кольца). Сигнал данных кольца - это серия битов выходного резервирования, а сигнал синхронизации кольца указывает местоположение первого выходного порта в серии кольцевых данных. Эти два сигнала циркулируют через RHE и интерфейсы коммутатора по одному биту каждый раз, в течение всего процесса резервирования. Кольцевое резервирование происходит в начале каждого цикла, после того, как каждый кольцевой интерфейс получает заголовки копий самых старших ячеек. С началом каждого цикла данные кольца в RHE и каждый кольцевой интерфейс устанавливаются в исходное состояние («свободно»). Серии кольцевых данных начинают затем циркулировать через интерфейс бит за битом. Каждый интерфейс имеет портовой счетчик, который увеличивается (дает приращение) при каждом прохождении бита кольцевых данных. Каждый временной интервал портовой счетчик сравнивается с адресом назначения самой старшей ячейки для того, чтобы определить, должна ли ячейка быть отправлена на выход в следующий промежуток. При прохождении бита данных кольца, все интерфейсы коммутатора рассматривают кольцевую синхронизацию и кольцевые данные бита. Если сигнал кольцевой синхронизации верен, (это значит, что следующий бит кольцевых данных соответствует первому выводу), тогда портовой счетчик устанавливается в исходное состояние при прохождении следующего бита. Если назначение ячейки согласовано с портовым счетчиком и бит данных кольца свободен, интерфейс коммутатора делает на кольце запись «занято», означающую, что в следующий коммутационный цикл вывод будет занят. Если бит данных кольца уже занят, или если портовой счетчик не согласован с назначением старшей ячейки, бит данных кольца не изменяется. Т.к. каждый коммутационный цикл интерфейса делает не более одного резервирования, конфликтные ситуации в коммутационной системе исключены. Во время кольцевого резервирования, ячейки, зарезервированные в предыдущий коммутационный цикл, отправляются в коммутационную систему.
На рисунке 3.11 показано, что в первый промежуток времени согласуются адреса выходных портов ячеек из вводов 1 и 5, и используются пункты, обозначающие, что ячейки могут пройти в эти порты. Ячейкам которые отмечены битами X1 и Х5 присваивается одно значение, указывающее на то, что выходные порты 1 и 5 уже заняты. Все отмеченные биты сдвигаются в сторону одного, и значения счетчиков так же увеличиваются на один по модулю во второй временной интервал. Во второй и третий промежутки времени согласования не происходит. В четвертый согласовываются адреса выходных портов ячеек из 0 и 2 вводов. Т.к. выходной порт 5 уже был зарезервирован для ячейки (на которой указано значение отмеченного бита X5)
Рисунок 3.11 - Схема реализации кольцевого резервирования
в предыдущий временной интервал, то ячейка у входа 2 не может быть отправлена. В пятый и шестой промежутки времени ячейки у вводов 3 и 4 так же не могут быть отправлены к выводам 1 и 3 соответственно, т.к. уже были зарезервированы в предыдущий временной интервал. В итоге ячейки у входных проверенных портов оказываются в конфликтной ситуации. В данном примере арбитражный цикл может быть завершен за шесть временных интервалов, поскольку имеется шесть входных портов. В этой схеме используется серийный механизм, и в целом арбитражный цикл может состоять из N бит временных интервалов, где N обозначает число портов ввода и вывода коммутатора, что может стать критическим параметром при большом количестве портов. Однако, эта схема обеспечивает равноправие портов, произвольно устанавливая нужные значения счетчиков перед арбитражем. Эта схема может быть использована на вводах любой коммутационной системы.
В этом коммутаторе сочетается сортирующая Батчер сеть и параллельно-направляющая Баньян сеть. Таким образом, к каждому выводу подходит более одного канала. На рис. 3.12 дана блок-схема строения этого коммутатора [17,18,19]. Параллельная сеть маршрутизации с автоблокировкой k обеспечивает k отдельных трактов каждому выводу. Если более, чем k ячеек делают запрос на определенный вывод за один временной интервал, тогда часть ячеек отправляется в очередь общей рециркуляции и затем снова передаются в коммутационную систему к назначенным вводам. Очередь рециркуляции состоит из Т параллельных цепей и Т назначенных вводов в сортирующую сеть с накопителем. Каждая цепь рециркуляции может сохранять одну ячейку. В каждой цепи имеется блок задержки для выстраивания рециркулирующих ячеек с ячейками, прибывшими из контролирующих устройств вводных
Рисунок 3.12 - Блок-схема солнечного коммутатора
каналов (IPC) в следующий временной интервал. В течение каждого интервала сеть с накопителем сортирует новоприбывшие и рециркулирующие ячейки в порядке приоритета и адресов назначения. Это позволяет заграждающей сети, выбирая k ячейки высшего приоритета для каждого вывода, разрешать конфликты у выходных портов. Поскольку в устройстве существует k параллельных сетей с автоблокировкой, каждый вывод может принимать k ячеек каждый временной интервал. Если для одного вывода назначено больше, чем k ячеек, их излишек будет отправляться в очередь рециркуляции. Концентратор и селектор направляют лишние ячейки в цепи рециркуляции, а выбранные ячейки будут направлены в сети с автоблокировкой. Каждая ячейка проходит в контролер входного порта со служебным заголовком.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
