Коммутирующие элементы сетей с динамической топологией

По типу коммутирующих элементов, применяемых в ступенях коммута- ции сетей с многоступенчатой топологией, различают:

§ сети на основе перекрестной коммутации;

§ сети на основе базового коммутирующего элемента.

В сетях, относящихся к первой группе, в качестве базового коммутирую-щего элемента используется кроссбар n×m. Для второй категории роль комму-тирующего элемента играет «полный кроссбар» 2 × 2. Потенциально такой ком-мутатор управляется четырехразрядным двоичным кодом и обеспечивает 16 ва-риантов коммутации, из которых полезными можно считать 12. На практике обычно используются только четыре возможных состояния кроссбара 2 × 2, ко- торые определяются двухразрядным управляющим кодом (рис. 6.3). Подобный кроссбар называется базовым коммутирующим элементом (БКЭ) или β- элемен-

Рис. 6.3. Состояния β-элемента

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

Рис. 6.4. Структура β-элемента

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

Сложность β-элемента находится в зависимости от логики принятия ре- шения. В ряде архитектур БКЭ их состояние определяется только битом актив-ности пакета. В иных архитектурах используются адреса источника и получа- теля данных, хранящиеся в заголовке пакета, что может потребовать поддер- жания в БКЭ специальных таблиц. Тем не менее во всех своих вариантах β-элементы достаточно просты, что позволяет реализовать их на базе интеграль- ных микросхем.

5. Топология “Баньян”

Данный вид сети получил свое название из-за того, что его схема напо-минает воздушные корни дерева баньян (индийской смоковницы). В топологии «Баньян» между каждой входной и выходной линиями существует только один путь. Сеть n × n (n = 2 ^m ) состоит из mn /2 базовых коммутирующих элементов.

Сеть «Баньян» 4×4 по топологии совпадает с сетью «Баттерфляй». На рис. 6.5 показана сеть «Баньян» 8×8. Передаваемый пакет в своем заголовке со-держит трехразрядный двоичный номер узла назначения. Данная сеть относится к сетям с самомаршрутизацией (self-routing), поскольку адрес пункта назна-

Рис. 6.5. Топология типа «Баньян»

чения не только определяет маршрут сообщения к нужному узлу, но и ис-пользуется для управления прохождением сообщения по этому маршруту. Каж-дый БКЭ, куда попадает пакет, просматривает один бит адреса и в зависимости от его значения направляет сообщение на выход 1 или 2. Состояние β-элемен- тов первой ступени сети (левый столбец БКЭ) определяется старшим битом ад-реса узла назначения. Средней ступенью (второй столбец) управляет средний бит адреса, а третьей ступенью (правый столбец) – младший бит. Если значение бита равно 0, то сообщение пропускается через верхний выход БКЭ, а при единичном значении – через нижний. На рисунке показан маршрут сообщения с входного узла 2 (010₂) к выходному узлу 5 (101₂). Адрес узла назначения содержится в заголовке сообщения.

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

6. Топология «Омега»

Сеть с топологией «Омега» является подклассом «баньян»-сетей и пред-ставляет собой многоуровневую структуру, где смежные уровни связаны между собой согласно функции идеального тасования. Сеть n × n, где n =2 ^m, состоит из m уровней БКЭ при общем числе БКЭ – mn /2. Количество соединений, обеспечи-ваемых сетью «Омега», равно n ^{n / 2}, что гораздо меньше, чем n!, то есть топология «Омега» является блокирующей. Так, при n =8 процент комбинаций, возможных в сети «Омега», по отношению к потенциально допустимому числу комбина- ций составляет или 10,16%.

Рис. 6.6. Сеть с топологией «Омега»

Рассмотрим порядок установки β-элементов сети для соединения входно- го и выходного терминальных узлов, двоичное n -разрядное представление но-меров которых есть соответственно (a _n a _{n -1}… a ₁) и (b _n b _{n -1}… b ₁). Состояние, в кото-рое переключается БКЭ на i -ой ступени, определяется с помощью операции сложения по модулю 2 значений i -го бита в адресах входного и выходного терминальных узлов. Если , то БКЭ, расположенный на i -ой ступени сети, обеспечивает прямую связь входа с выходом, а при – перекрест-ное соединение. На рис. 6.6 показан процесс прохождения сообщения по сети «Омега» 8×8 от входного терминала 2 (010₂) к выходному терминалу 6 (110₂). Таким образом, если в сообщении присутствуют адреса источника и получате- ля сообщений, то сеть может функционировать в режиме самомаршрутизации.

7. Топология «Дельта»

Важный подкласс «баньян»-сетей образуют сети «Дельта», предложенные Пателом в 1981 году. В них основание системы счисления при адресации узлов для маршрутизации может отличаться от 2. Сеть соединяет a ⁿ входов с b ⁿ вы-ходами посредством n ступеней кроссбаров a × b (в сетях с такими топологиями, как «Омега», «базовая линия» и «косвенный» n -куб, используется двоичная сис-тема счисления, то есть a =2 и b= 2). Адрес получателя задается в заголовке

Рис. 6.7. Структура сети «Дельта»: а – по базе 4; б – с дополнительной ступенью

сообщения числом в системе счисления с основанием b, а для прохождения со-общения по сети организуется самомаршрутизация. Каждая цифра адреса имеет значение в диапазоне от 0 до b –1 и выбирает один из b выходов коммутирую-щего элемента типа кроссбар a × b. Пример сети «Дельта» показан на рис. 6.7.

В отличие от сети «Омега» входы не подвергаются тасованию. Это не влияет на алгоритм маршрутизации, поскольку важен не адрес источника, а ад- рес получателя. На рис. 6.7, а связь между ступенями соответствует идеальному тасованию – коммутаторы соединены так, что для связи любого входа с любым выходом образуется единственный путь, причем пути для любой пары равны по длине. В сеть «Дельта» могут быть введены и дополнительные ступени (рис. 6.7, б), чтобы обеспечить более чем один маршрут от входа к выходу.

Дата добавления: 2014-01-20