Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS

Словарь терминов в коллекции "Вычислительные системы"

Топология Бенеша

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

В качестве коммутаторов в сетях Бенеша используются β-элементы. В сети n×n общее количество базовых коммутирующих элементов (БКЭ) равно nlog2n. Ввиду того, что эти сети не обладают свойством самомаршрутизации, то есть для коммутации маршрута недостаточно информации, содержащейся во входном пакете, для определения состояния всех β-элементов необходим специальный контроллер. Сущность реконфигурирования и достигаемый при этом эффект иллюстрирует рисунок (см. дополнительно файл .pdf). На рисунке показана топология сети Бенеша, обеспечивающая одновременную пересылку трех сообщений: с входа 010 (0002) на выход 410 (1002), входа 110 (0012) на выход 010 (0002) и входа 210 (0102) на выход 210 (0102). Как видно, блокировки сообщений не происходит. При попытке одновременно с этим передать пакет с входа 310 (0112) на выход 110 (0012) передача блокируется. Однако блокировки можно избежать, если изменить топологию сети. Благодаря изменению трактов прохождения всех четырех сообщений конфликт не возникает.
Все тракты передачи сообщений должны формироваться одновременно. Если новый тракт формируется при уже функционирующих других трактах, неблокируемость без реконфигурирования «старых» трактов не гарантируется.
Сеть Бенеша может рассматриваться как частный случай сети Клоза, для которой выполняется условие mn. В этом случае, как доказал Бенеш, сеть Клоза можно отнести к неблокирующим сетям с реконфигурацией.
С добавлением к такой сети дополнительной ступени БКЭ число возможных маршрутов удваивается. Дополнительные пути позволяют изменять трафик сообщения с целью устранения конфликтов. Сеть Бенеша с n входами и n выходами имеет симметричную структуру, в каждой половине которой (верхней и нижней) между входными и выходными БКЭ расположена такая же сеть Бенеша, но с n/2 входами и n/2 выходами.


См. дополнительно: Топология Бенеша

Ключевые термины, связанные с термином "топология бенеша":

  1. Реконфигурируемая топология

Ключевые термины:  динамическая топология;   неблокирующая топология;   реконфигурируемая топология;   многоступенчатая сеть;   топология клоза;


Контекстный поиск: Задайте образец для поиска:
    

|Список основных тем курса|
   
Федотова Ольга
[SBRAS]

НГУ
ФИТ НГУ
ИВТ СО РАН
© 2012-2024, Новосибирский государственный университет, Новосибирск
© 2004-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 2004-2024, Федотов А.М.
    Дата последней модификации: 14.08.2013