Топология объединенной сети гиперкуба

В компьютерных сетях сети гиперкубов представляют собой тип сетевой топологии, используемый для соединения и маршрутизации данных между несколькими процессорами или компьютерами. Сети гиперкуба состоят из $2 м$ узлы , которые образуют вершины квадратов для создания межсетевого соединения. Гиперкуб — это, по сути, многомерная ячеистая сеть с двумя узлами в каждом измерении. Из-за сходства такие топологии обычно группируются в $k$ -арное $семейство топологий d$ -мерной сетки, где $d$ представляет количество измерений, а $k$ представляет количество узлов в каждом измерении. ^[1]

Разные гиперкубы для разного количества узлов.

Топология [ править ]

Сеть взаимосвязей гиперкуба формируется путем соединения N узлов, которые можно выразить степенью 2. Это означает, что если в сети есть N узлов, это можно выразить как:

$N=2^{m}$

где m — количество битов, необходимых для маркировки узлов сети. Итак, если в сети 4 узла, для представления всех узлов в сети необходимы 2 бита . Сеть строится путем соединения узлов, которые в двоичном представлении отличаются всего на один бит. Обычно это называется бинарной маркировкой. Объединенная сеть 3D-гиперкуба будет представлять собой куб с 8 узлами и 12 ребрами . Сеть 4D-гиперкуба может быть создана путем дублирования двух 3D- сетей и добавления старшего бита. Новый добавленный бит должен быть равен «0» для одного 3D-гиперкуба и «1» для другого 3D-гиперкуба. Углы соответствующих измененных на один бит старших битов соединяются для создания сети гиперкуба более высокого уровня. Этот метод можно использовать для построения любого гиперкуба, представленного m-битами, с помощью гиперкуба, представленного (m-1)-битами. ^[2]

Маршрутизация E-Cube [ править ]

Метод маршрутизации для сети гиперкуба называется маршрутизацией E-Cube. Расстояние между двумя узлами в сети может быть задано весом Хэмминга (количество единиц в) операции XOR между их соответствующими двоичными метками.

Расстояние между узлом 1 (обозначенным как «01») и узлом 2 (обозначенным как «10») в сети, определяемое формулой:

${\mathsf {Hamming\_weight}}(01\oplus 10)={\mathsf {Hamming\_weight}}(11)=2$

Маршрутизация E-Cube — это статический метод маршрутизации , в котором используется алгоритм XY-маршрутизации . Эту модель обычно называют детерминированной моделью по измерениям упорядоченной маршрутизации . Маршрутизация E-Cube работает путем пересечения сети в k ^й размерность, где k — младший ненулевой бит в результате вычисления расстояния.

Например, пусть метка отправителя будет «00», а метка получателя — «11». Итак, расстояние между ними равно 11, а младшим битом, отличным от нуля, является бит LSB . Определение того, куда идти для «0» или «1», определяется алгоритмом маршрутизации XY. ^[3]

Метрики [ править ]

Для оценки эффективности сетевого соединения гиперкуба по сравнению с различными другими сетевыми топологиями используются различные показатели производительности. ^{[ нечеткий ]}

Степень [ править ]

Это определяет количество узлов, непосредственно примыкающих к конкретному узлу. Эти узлы должны быть непосредственными соседями. В случае гиперкуба степень равна m.

Диаметр [ править ]

Это определяет максимальное количество узлов, через которые должно пройти сообщение на своем пути от источника к месту назначения. По сути, это дает нам задержку при передаче сообщения по сети. В случае гиперкуба диаметр равен м.

Среднее расстояние [ править ]

Расстояние между двумя узлами, определяемое количеством переходов на кратчайшем пути между двумя конкретными узлами. Оно дается формулой –

$d_{a}=\sum _{d=1}^{r}{(d.N_{d}) \over N-1}$

В случае гиперкубов среднее расстояние указывается как м/2.

Ширина бисекции [ править ]

Это наименьшее количество проводов, которое следует перерезать, чтобы разделить сеть на две равные половины. Это дано как 2 ^м-1 для гиперкубов. ^[1]

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Остроухов, Г. (1 января 1987 г.). «Параллельные вычисления в гиперкубе: обзор архитектуры и некоторых приложений» (PDF) . Конференция: Симпозиум по интерфейсу информатики и статистики . Теннесси: Национальная лаборатория Ок-Ридж, Теннесси (США). ОСТИ 6487986.
^ Сюй, Ченг-Чжун. «Соединительные сети» (PDF) . Архивировано из оригинала (PDF) 17 июля 2013 г.
^ Карипис, Георгий. «Механизмы маршрутизации для межсетевых сетей» .

[ParallelOn-1] Jump up to: Перейти обратно: ^а ^б Остроухов, Г. (1 января 1987 г.). «Параллельные вычисления в гиперкубе: обзор архитектуры и некоторых приложений» (PDF) . Конференция: Симпозиум по интерфейсу информатики и статистики . Теннесси: Национальная лаборатория Ок-Ридж, Теннесси (США). ОСТИ 6487986.

[2] Сюй, Ченг-Чжун. «Соединительные сети» (PDF) . Архивировано из оригинала (PDF) 17 июля 2013 г.

[3] Карипис, Георгий. «Механизмы маршрутизации для межсетевых сетей» .

[1]

[2]

[3]