Коммутация в сетях с использованием асинхронного метода переноса и доставки (стр. 6 из 17)
2.18 МЕТОД ПРОСТРАНСТВЕННОГО РАЗДЕЛЕНИЯ
Простейшим примером системы с пространственным разделением является коммутатор матричного типа, обеспечивающий физическую взаимосвязь с любым из N входных и N выходных портов. Хорошо известны коммутаторы матричного типа с производительностью в сотни гигабит в секунду, в которых применяются входная и/или выходная буферизация и двунаправленный алгоритм разделения памяти. В целях сокращения числа коммутационных элементов (кроссов), которые необходимы для внутренней коммутации каналов, организации взаимосвязей между вычислительными узлами в многопроцессорных системах и, позднее, коммутации пакетов и ячеек ATM, были разработаны многокаскадные сети (Multistage Interconnection Network, MIN), представляющие собой древовидные структуры [6,12].
Баньяновидные сети (свое название они получили потому, что схожи по форме с одноименным тропическим деревом), один из наиболее широко представленных типов сетей MIN, строятся путем формирования каскадов коммутационных элементов [5,6,12]. Основной коммутационный элемент 2x2 обрабатывает входящую ячейку в соответствии с управляющим битом выходного адреса. Если этот бит равен нулю, то ячейка направляется на верхний выходной порт кросса, в противном случае — на нижний.
Рисунок 2.5 - Баньяновидная сеть 8x8
На рисунке 2.5 показано последовательное соединение коммутационных элементов, формирующих Баньяновидную сеть 8x8. Сеть 8x8 формируется рекурсивно, при этом первый бит применяется для транспортировки ячейки через первый каскад, а последние два бита — для маршрутизации ячейки через сеть 4x4 на соответствующий выходной порт.
Итак, в Баньяновидной сети 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].
2.19 РАЗДЕЛЕНИЕ БУФЕРОВ
Число и размер буферов имеют важное значение при разработке коммутатора. В устройствах с общей памятью централизованный буфер зачастую имеет преимущество перед средствами статистического разделения. Принимая интенсивный поток ячеек на некоторый выходной порт, коммутатор выделяет для них максимально возможную часть буферного пространства, что приводит к экономии последнего, поскольку ячейки поступают на различные порты случайным образом [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]. Тем не менее если ячейки направляются по независимым путям с переменными задержками, необходимо предусмотреть сохранение исходной последовательности ячеек в виртуальном соединении на выходном порте. Поскольку данный процесс может потребовать значительных затрат вычислительных ресурсов процессора, предпочтительнее выбирать путь передачи ячеек на стадии установления и использовать его в течение всего времени существования соединения. Особое внимание должно уделяться предотвращению блокировки последовательных вызовов.
2.20 ОТКАЗОУСТОЙЧИВОСТЬ
Поскольку надежность является существенным аспектом функционирования коммутационных систем, необходимо обеспечить избыточность их критически важных компонентов. Поле маршрутизации и структура буферов, являющиеся важнейшими элементами коммутационной системы, могут быть продублированными или избыточными, что влияет на организацию механизмов обнаружения отказов и восстановления работоспособности [15].
Простейший способ повышения надежности сводится к разбиению всей совокупности коммутируемых ячеек на непересекающиеся подмножества, распределяемые между параллельными плоскостями поля маршрутизации. Этот метод весьма эффективен, так как он обеспечивает наименьшую избыточность, а каждая плоскость несет лишь малую долю общего трафика. Другой вариант — тождественное дублирование всего множества ячеек — обеспечивает большую отказоустойчивость при меньшей производительности. Компромиссным решением может быть использование частично перекрывающихся подмножеств.