Новосибирский государственный университет Факультет информационных технологий

А.М.Федотов

Словарь-справочник по информатике (онтология информатики)

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

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

Среди баньян-сетей наибольшее распространение получили так называемые сети «Дельта», предложенные Пателом в 1981 году. Дельта-сеть на n входов и n выходов имеет log₂n ступеней коммутации, каждая из которых состоит из n/2 базовых коммутирующих элементов (БКЭ). Различные варианты сетей класса «Дельта» («Омега», «базовая линия», «баттерфляй», «косвенный» n-куб и др.) различаются тем, какие функции маршрутизации использованы между ступенями сети и на ее входе. По отношению к произвольному трафику все сети обеспечивают эквивалентную производительность.
Существенным достоинством этих сетей, определившим их популярность, является свойство самомаршрутизации. Чтобы доставить сообщение к узлу-получателю, используется адрес этого узла, содержащийся в заголовке передаваемого пакета. Этот адрес не только определяет маршрут сообщения к нужному узлу, но и используется для управления прохождением сообщения по этому маршруту. Число битов в двоичном представлении адреса равно числу ступеней сети, причем каждый бит соответствует определенной ступени: старший бит - нулевой (левой) ступени, младший бит - последней (правой) ступени.
Каждый БКЭ, куда попадает пакет, просматривает один бит адреса (соответствующий ступени сети, где этот БКЭ расположен), и в зависимости от его значения направляет сообщение на верхний или нижний выход. Если значение бита равно нулю, то сообщение пропускается через верхний выход БКЭ, а при единичном значении - через нижний.

Литература
• Patel, J.H. «Performance of Processor-Memory Interconnection for Multiprocessor», IEEE Transactions on Computer, Vol. 30, № 10, Oct. 1981, pp. 881-780.
• Цилькер Б.Я. Организация ЭВМ и систем: учебник для вузов / С.А. Орлов, Б.Я. Цилькер. - СПб.: Питер, 2011. - 688 с.

Ключевые термины, связанные с термином "Топология «Дельта»":

1. Блокирующая топология
2. Топология «Баньян»
3. Топология «Омега»

Литература

Основная:

1. Цилькер Б.Я. Организация ЭВМ и систем : Учебник для вузов / Б.Я. Цилькер, С.А. Орлов. - 2-е изд. - СПб.: Питер, 2011. - 688 с. - ISBN 978-5-49807-862-5.

Ключевые термины (головные):  Динамическая топология;   Блокирующая топология;   Многоступенчатая сеть;   Топология «Баньян»;   Топология «Омега»;   «Баттерфляй»;   «Базовая линия»;

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

Федотов Анатолий Михайлович

НГУ ФИТ НГУ ИВТ СО РАН