Topologia di rete Hypercube - Hypercube internetwork topology

Nelle reti di computer , le reti hypercube sono un tipo di topologia di rete utilizzata per collegare più processori con moduli di memoria e instradare accuratamente i dati . Le reti Hypercube sono costituite da nodi di 2 ^m , che formano i vertici dei quadrati per creare una connessione Internet . Un ipercubo è fondamentalmente una rete mesh multidimensionale con due nodi in ogni dimensione. A causa della somiglianza, tali topologie sono solitamente raggruppate in una famiglia di topologia mesh k -aria d -dimensionale, dove d rappresenta il numero di dimensioni e k rappresenta il numero di nodi in ciascuna dimensione.

Diversi ipercubi per un numero variabile di nodi

Topologia

La rete di interconnessione Hypercube è formata collegando N nodi che possono essere espressi come una potenza di 2. Ciò significa che se la rete ha n nodi può essere espressa come:

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

dove m è il numero di bit necessari per etichettare i nodi della rete. Quindi, se ci sono 4 nodi nella rete, sono necessari 2 bit per rappresentare tutti i nodi nella rete . La rete è costruita collegando i nodi che differiscono solo di un bit nella loro rappresentazione binaria . Questo è comunemente indicato come etichettatura binaria. Una rete di ipercubo 3D sarebbe un cubo con 8 nodi e 12 bordi . Una rete ipercubo 4D può essere creata duplicando due reti 3D e aggiungendo un bit più significativo. Il nuovo bit aggiunto dovrebbe essere "0" per un ipercubo 3D e "1" per l'altro ipercubo 3D. Gli angoli dei rispettivi MSB modificati a un bit sono collegati per creare la rete dell'ipercubo superiore. Questo metodo può essere utilizzato per costruire qualsiasi ipercubo rappresentato da m-bit con un ipercubo rappresentato da (m-1)-bit.

E-Cube Routing

Il metodo di instradamento per una rete hypercube è denominato instradamento E-Cube. La distanza tra due nodi nella rete può essere data dal peso di Hamming (numero di unità) dell'operazione XOR tra le rispettive etichette binarie.

La distanza tra il Nodo 1 (rappresentato come '01') e il Nodo 2 (rappresentato come '10') nella rete data da:

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

Il routing E-Cube è un metodo di routing statico che utilizza l' algoritmo di routing XY . Questo è comunemente indicato come modello di instradamento deterministico , dimensionale ordinato . L'instradamento E-Cube funziona attraversando la rete nella dimensione k- ^esima dove k è il bit diverso da zero meno significativo nel risultato del calcolo della distanza.

Ad esempio, lascia che l'etichetta del mittente sia "00" e l'etichetta del destinatario sia "11". Quindi, la distanza tra loro è 11 e il bit diverso da zero meno significativo è il bit LSB . Capire in che modo andare per uno '0' o '1' è determinato dall'algoritmo di routing XY.

Metrica

Diverse misure di prestazioni vengono utilizzate per valutare l'efficienza di una connessione di rete ipercubo rispetto a varie altre topologie di rete.

Grado

Questo definisce il numero di nodi immediatamente adiacenti a un particolare nodo. Questi nodi dovrebbero essere vicini immediati. In caso di ipercubo il grado è m.

Diametro

Definisce il numero massimo di nodi che un messaggio deve attraversare nel suo percorso dalla sorgente alla destinazione. Questo ci dà fondamentalmente il ritardo nella trasmissione di un messaggio attraverso una rete. In caso di ipercubo il diametro è di m.

Distanza media

La distanza tra due nodi definita dal numero di salti nel percorso più breve tra due nodi particolari. È dato dalla formula -

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

Nel caso degli Ipercubi la distanza media è espressa in m/2.

Larghezza di bisezione

Questo è il numero più basso di fili che dovresti tagliare per dividere la rete in due metà uguali. È dato come 2 ^m-1 per Hypercubes.

Riferimenti