Topologia de internetwork Hypercube - Hypercube internetwork topology

Em redes de computadores , as redes de hipercubos são um tipo de topologia de rede usada para conectar vários processadores com módulos de memória e rotear dados com precisão . Redes Hypercube consistem de 2 ^m nodos , que formam os vértices de quadrados para criar um conjunto de redes de ligação. Um hipercubo é basicamente uma rede de malha multidimensional com dois nós em cada dimensão. Devido à similaridade, tais topologias são geralmente agrupadas em uma família de topologia de malha k -ary d- dimensional, onde d representa o número de dimensões ek representa o número de nós em cada dimensão.

Diferentes hipercubos para vários números de nós

Topologia

A rede de interconexão de hipercubo é formada pela conexão de N nós que podem ser expressos como uma potência de 2. Isso significa que se a rede tiver n nós, pode ser expressa como:

${\ displaystyle N = 2 ^ {m}}$

onde m é o número de bits necessários para rotular os nós na rede. Portanto, se houver 4 nós na rede, serão necessários 2 bits para representar todos os nós da rede . A rede é construída conectando os nós que diferem apenas por um bit em sua representação binária . Isso é comumente referido como rotulagem binária. Uma internetwork de hipercubo 3D seria um cubo com 8 nós e 12 arestas . Uma rede hipercubo 4D pode ser criada duplicando duas redes 3D e adicionando um bit mais significativo. O novo bit adicionado deve ser '0' para um hipercubo 3D e '1' para o outro hipercubo 3D. Os cantos dos respectivos MSBs alterados de um bit são conectados para criar a rede de hipercubo superior. Este método pode ser usado para construir qualquer hipercubo representado de m bits com hipercubo representado por (m-1) bits.

Roteamento E-Cube

O método de roteamento para uma rede hipercubo é conhecido como roteamento E-Cube. A distância entre dois nós na rede pode ser dada pelo peso de Hamming (número de unidades ) da operação XOR entre seus respectivos rótulos binários.

A distância entre o Nó 1 (representado como '01') e o Nó 2 (representado como '10') na rede dada por:

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

O roteamento E-Cube é um método de roteamento estático que emprega o algoritmo de roteamento XY . Isto é comumente referido como determinística , Dimension Ordered Routing modelo. O roteamento E-Cube funciona atravessando a rede na k- ^ésima dimensão, onde k é o bit diferente de zero menos significativo no resultado do cálculo da distância.

Por exemplo, deixe o rótulo do remetente ser '00' e o rótulo do destinatário ser '11'. Portanto, a distância entre eles é 11 e o bit diferente de zero menos significativo é o bit LSB . Descobrir qual caminho seguir para um '0' ou '1' é determinado pelo algoritmo de roteamento XY.

Métricas

Diferentes medidas de desempenho são usadas para avaliar a eficiência de uma conexão de rede hipercubo em relação a várias outras topologias de rede.

Grau

Isso define o número de nós imediatamente adjacentes a um determinado nó. Esses nós devem ser vizinhos imediatos. No caso de um hipercubo, o grau é m.

Diâmetro

Isso define o número máximo de nós pelos quais uma mensagem deve passar em seu caminho da origem ao destino. Isso basicamente nos dá o atraso na transmissão de uma mensagem pela rede. No caso de um hipercubo, o diâmetro é m.

Distância média

A distância entre dois nós definida pelo número de saltos no caminho mais curto entre dois nós específicos. É dado pela fórmula -

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

No caso de hipercubos, a distância média é dada em m / 2.

Largura da bissecção

Este é o menor número de fios que você deve cortar para dividir a rede em duas metades iguais. É dado como 2 ^m-1 para hipercubos.

Referências