Итак, в Баньяновидной сети N´N n-й каскад выбирает направление передачи ячейки по n-му биту выходного адреса. При N=2n такая сеть состоит из (N/2)\log N элементарных двоичных кроссов. Сети MIN способны автоматически обновлять таблицы маршрутизации (т.е. имеют свойство самомаршрутизации), в случае если выходной адрес полностью определяет маршрут следования ячейки через сеть.
Популярность Баньяновидных сетей объясняется использованием простых коммутационных элементов для обеспечения процесса коммутации; при этом ячейки передаются параллельно и все элементы действуют с одной и той же скоростью (так как нет дополнительных ограничений на размер N или скорость V). При создании больших коммутаторов указанные свойства позволяют легко реализовать модульный рекурсивный подход на уровне аппаратных средств. Коммутаторы Sunshine компании Bell-core и 1100 подразделения Alcatel Data Networks — типичные примеры устройств, в которых применяется данный подход.
Отрицательным свойством Баньяновидных сетей является их принадлежность к блокирующим схемам, причем вероятность блокировки ячейки при ее маршрутизации быстро возрастает с ростом сети [8]. Очевидно, что в таких сетях существует единственный путь с любого входного порта на любой выходной. Регулярные Баньяновидные сети используют только один тип коммутационных элементов. В их разновидности (так называемых SW-Баньяновидных сетях) вероятность блокировки ячеек удается уменьшить, применяя кроссы больших размеров, — они строятся рекурсивно из коммутационных элементов размером L´М, где L>2 и М>2.
Дельта-сети представляют собой подкласс SW - Баньяновидных сетей и обладают свойством самомаршрутизации. Существует несколько типов дельта-сетей: прямоугольная (кроссы имеют одинаковое число входов и выходов), базовая (baseline), омега, флип, куб, обратный куб и др. Сеть дельта-b размером N´N содержит logbN каскадов, причем каждый каскад состоит из N/b коммутационных элементов b´Ь.
Как уже говорилось, число точек коммутации в Баньяновидных сетях меньше N2, что может приводить к конфликту маршрутов двух ячеек, адресованных на разные выходные порты. При возникновении подобной ситуации, именуемой внутренней блокировкой, лишь одна из двух ячеек способна достичь следующего каскада, а в результате общая производительность снижается.
Одно из решений проблемы состоит в добавлении специальной сети предварительной сортировки (например, так называемого сортировщика Батчера), которая направляет ячейки в Баньяновидную сеть. Сортировщик позволяет избежать блокировок при адресации ячеек на различные выходные порты, но если они одновременно адресуются на один и тот же выход, единственным решением становится буферизация [8,1,14].
Число и размер буферов имеют важное значение при разработке коммутатора. В устройствах с общей памятью централизованный буфер зачастую имеет преимущество перед средствами статистического разделения. Принимая интенсивный поток ячеек на некоторый выходной порт, коммутатор выделяет для них максимально возможную часть буферного пространства, что приводит к экономии последнего, поскольку ячейки поступают на различные порты случайным образом [1,12].
Для коммутационного поля с TDM-шиной и N выходными буферами большая группа ячеек, одновременно поступивших на какой-либо выход, естественно, не может быть принята другим выходным буфером. Тем не менее каждый выходной буфер способен статистически мультиплексировать трафике N входов.
В структурах с N2 выходными буферами, имеющих полносвязную топологию, статистическое мультиплексирование между выходными портами или на любом выходном порте невозможно. В этом случае размер буферного пространства растет экспоненциально.
Буферы могут быть установлены на входе сети Батчера (рисунок 2.6).
Рисунок 2.6 - Входная буферизация
Однако в этом случае возможна блокировка очереди ячейкой, находящейся в ее начале направляемой на занятый выходной порт, даже если выходные порты ячеек, расположенных позади данной, свободны [1,3,5].
В такой ситуации способна выручить дисциплина «пришедший первым обслуживается в случайном порядке» (First In Random Out, FIRO), но, к сожалению, она не имеет простой реализации. Другой способ избежать конфликтов маршрутов — установить буфер непосредственно внутри коммутационных элементов Баньяновидной сети. Если две ячейки одновременно направляются в один и тот же выходной канал, одна из них буферизуется внутри коммутационного элемента. Внутренняя буферизация используется и механизмом управления с помощью обратной блокировки (backpressure): очереди в одном каскаде сети задерживают ячейки предыдущего каскада сигналом обратной связи. Влияние процедуры обратной блокировки может достигнуть первого каскада и привести к созданию очередей на входах. Следует отметить, что внутренняя буферизация способна вызвать блокировку ячейки в начале очереди на каждом коммутационном элементе и, следовательно, не позволяет достичь максимальной производительности.
Еще один вариант — использование рециркуляционного буфера, внешнего к коммутационному полю (рисунок 2.7).
Рисунок 2.7 - Рециркуляционные буферы
Этот подход применяется в широкополосных цифровых коммутаторах Sunshine фирмы Bellcore и Starlite компании AT&T. В данном случае конфликты на выходе обнаруживаются после прохождения сортировщика Батчера, затем сеть выбирает ячейку для дальнейшей передачи, а оставшиеся ячейки через рециркуляционный буфер возвращаются на входные порты сети Батчера. К сожалению, данный метод требует сложного приоритетного
управления для сохранения исходной последовательности передаваемых ячеек и применения сети Батчера большего размера для размещения рециркулированных ячеек.
Помимо рассмотренных выше видов Баньяновидных сетей существует немало типов сетей.M1N с множественными путями между входными и выходными портами. Классическими примерами являются неблокирующие сети Бэнеша и Клоза, сети со свойством самомаршрутизации и распределением нагрузки, снижающими потребность во внутренней буферизации, групповые
Баньяновидные коммутационные структуры (например, тандем Баньянов).
Для формирования таких сетей возможно параллельное использование нескольких Баньяновидных соединительных сетей [8,9].
Сети MIN с множественными путями обеспечивают более однородное распределение трафика, необходимое для минимизации внутренних блокировок и повышения отказоустойчивости [14]. Тем не менее если ячейки направляются по независимым путям с переменными задержками, необходимо предусмотреть сохранение исходной последовательности ячеек в виртуальном соединении на выходном порте. Поскольку данный процесс может потребовать значительных затрат вычислительных ресурсов процессора, предпочтительнее выбирать путь передачи ячеек на стадии установления и использовать его в течение всего времени существования соединения. Особое внимание должно уделяться предотвращению блокировки последовательных вызовов.
Поскольку надежность является существенным аспектом функционирования коммутационных систем, необходимо обеспечить избыточность их критически важных компонентов. Поле маршрутизации и структура буферов, являющиеся важнейшими элементами коммутационной системы, могут быть продублированными или избыточными, что влияет на организацию механизмов обнаружения отказов и восстановления работоспособности [15].
Простейший способ повышения надежности сводится к разбиению всей совокупности коммутируемых ячеек на непересекающиеся подмножества, распределяемые между параллельными плоскостями поля маршрутизации. Этот метод весьма эффективен, так как он обеспечивает наименьшую избыточность, а каждая плоскость несет лишь малую долю общего трафика. Другой вариант — тождественное дублирование всего множества ячеек — обеспечивает большую отказоустойчивость при меньшей производительности. Компромиссным решением может быть использование частично перекрывающихся подмножеств.
Распараллеливание плоскостей поля маршрутизации и структуры буферов поднимает степень отказоустойчивости, однако гораздо важнее повысить избыточность в пределах отдельных плоскостей. Баньяновидные сети склонны к отказам, поскольку содержат единственный путь в каждой паре «вход—выход»; сети с множественными путями отличаются большей отказоустойчивостью. Для повышения избыточности следует включать в состав Баньяновидных сетей дополнительные коммутационные элементы и каскады, избыточные и альтернативные соединения либо увеличивать число входных и выходных портов. Платой за это становится усложнение как схем буферизации и маршрутизации, так и средств управления [8].
Для организации эффективного контроля за отказоустойчивостью коммутационной системы применяются разнообразные тестирующие
механизмы. Маршрутизация специальных ячеек через тестовые элементы и отслеживание их появления на выходах, а также добавление служебной информации в заголовок ячейки позволяют обнаружить потери ячеек, ошибочные пути или неоправданные задержки. При выявлении отказа трафик перераспределяется до устранения причины сбоя, причем функция перераспределения может выполняться как концентраторами, так и самим коммутационным полем.
Отличительное свойство Баньян сети - это существование перехода от любого входа к любому выходу [8],
Рисунок 3.1- показывает четыре вида сетей, принадлежащих к этому классу:
а) смешанные (Омега) сеть;
b) реверсная смешанная сеть;
c) особо чувствительная Баньян сеть;
d) обыкновенная сеть;
Основное свойство этих сетей:
1. Они состоят из n=log2N и N/2 узлов на уровень.
2. Они имеют самонастраивающееся свойство - уникальный n-битный адрес назначения может использоваться для передачи ячейки от любого входа к любому выходу, по одному биту на каждый уровень.
3. Их регулярность и взаимосвязная схема очень привлекательна для применения в VLSI (VLSI - сверх большая степень интеграции).
Рисунок 3.2 показывает пример соединения в Баньян сети 8´8, где темные линии отражают передающие пути. С правой стороны адрес каждого выходного сигнала обозначен как ряд n-битов, b1...bn. Адрес ячейки сигнала закодирован в заголовке ячейки. На первом уровне проверяется бит b1, если
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15