Однокаскадные коммутационные матрицы не могут полностью устранить проблемы конфликтов при одновременном поступлении

ячеек к одному выходу. Такие матрицы непригодны для обработки напряженного трафика. В связи с этим широкое применение находят многокаскадные коммутационные матрицы, в которых существует один или несколько путей, называемых еще маршрутами, между заданной парой вход/выход. Примером матрицы с одним маршрутом может служить баньяновидная матрица, изображенная на рисунке 6.7 (Баньян – тропическое дерево, у которого от каждой почки растет корень и ветвь).

На основе баньяновидной матрицы может быть построена схема коммутаторов с одним маршрутом между парой вход/выход.

На рисунке 6.8 приведена схема коммутатора, состоящая их трех каскадов, на 8 входов и 8 выходов (8x8).

Процесс маршрутизации ячеек в таком коммутаторе состоит в следующем. В заголовке каждой ячейки находится специальное маршрутное поле, представляющее собой последовательность двоичных символов, число которых совпадает с числом каскадов. В каждом каскаде декодируется разряд маршрута. Если он равен «1», то КЭ реализует операцию «Кросс». Если он равен «0», то КЭ реализует операцию «Транзит».

Для приведенного на рисунке 6.8 примера число каскадов и число входов/выходов связаны соотношением:
n = lg₂N, где n = 3, N = 8.

Одномаршрутный коммутатор баньяна может создать состояние, когда ячейка ATM не может быть принята коммутационным элементом следующего каскада из-за одновременного поступления запроса от другого каскада. Это называется внутренней блокировкой (конфликтом или коллизией).

Частично решить проблему конфликтов можно созданием буфера при каждом коммутационном элементе. Известны четыре способа построения буферов у коммутационных элементов: КЭ с входными очередями; КЭ с выходными очередями; КЭ с центральными очередями и смешанные. Примеры указанных структур приведены на рисунках 6.9, 6.10, 6.11. Принцип обслуживания очередей FIFO (First In First Out) – пришел первый, ушел первый.

Возможные размеры требуемых буферов очереди при вероятности потери ячейки 10^–9 (пределы 10^–8...10^–n) отмечены в таблице 6.1.

Полностью устранить конфликты ячеек при маршрутизации даже с буферами невозможно из-за случайности трафика и возникающих переполнений буферов. Кроме того, буферы создают зна-чительные задержки, которые далеко не всегда допустимы, например, для телефонного трафика или видеосвязи. Снизить количество конфликтов и потерь ячеек можно при использовании коммутационных матриц со многими маршрутами. Примерами коммутаторов со многими маршрутами могут служить:

В схеме Бенеша каскады выбора маршрута обеспечивают организацию маршрутов. При этом число каскадов в ступени выбора маршрута определяется необходимым числом возможных маршрутов. Например, при одном каскаде – 2 маршрута, при 2-х каскадах – 4 маршрута, при 3-х каскадах – 8 маршрутов и так далее.

Тип буфера	Размер буфера для матриц (вход/выход)
Тип буфера	16x16	32x32
Центральная очередь	113	199
Входная очередь	320	640
Выходная очередь	896	1824

В схеме Бетчера, при подаче на оба входа КЭ «Сортировщика» 2-х ячеек, производится сравнение разрядов маршрутных полей этих двух ячеек. Если сравниваемые разряды имеют разные значения («0» и «1»), то ячейки с разрядами «0» направляются по стрелке. Другие ячейки передаются на второй выход. Если сравниваемые разряды имеют одинаковое значение («0» и «0» или «1» и «1»), тогда производится последовательное сравнение других следующих разрядов маршрута, включая разряды информационных полей ячеек до обнаружения различия.

При этом, если на один из входов КЭ не поступают ячейки, то считается, что на вход поступает пассивная ячейка с разрядами «0» во всех ее частях.

Число каскадов в схеме Бетчера для реализации полной сортировки равно ,

где N – число входов.