Topologia intersieci hipersześcianu

W sieciach komputerowych sieci hipersześcianu to rodzaj topologii sieci używanej do łączenia wielu procesorów z modułami pamięci i dokładnego kierowania danymi . Sieci hipersześcianu składają się z 2 ^m węzłów , które tworzą wierzchołki kwadratów, tworząc połączenie międzysieciowe . Hipersześcian jest w zasadzie wielowymiarową siecią siatkową z dwoma węzłami w każdym wymiarze. Ze względu na podobieństwo takie topologie są zwykle grupowane w k -ary d -wymiarowa rodzina topologii siatki, gdzie d oznacza liczbę wymiarów, a k oznacza liczbę węzłów w każdym wymiarze.

Różne hipersześciany dla różnej liczby węzłów

Topologia

Sieć połączeń hipersześcianu jest tworzona przez połączenie N węzłów, które można wyrazić jako potęgę liczby 2. Oznacza to, że jeśli sieć ma N węzłów, można to wyrazić jako:

${\ Displaystyle N = 2 ^ {m.}}$

gdzie m to liczba bitów potrzebnych do oznaczenia węzłów w sieci. Tak więc, jeśli w sieci są 4 węzły, potrzebne są 2 bity, aby reprezentować wszystkie węzły w sieci . Sieć jest budowana przez łączenie węzłów, które różnią się tylko o jeden bit w swojej binarnej . Jest to powszechnie określane jako etykietowanie binarne. Trójwymiarowa intersieć hipersześcianu byłaby sześcianem z 8 węzłami i 12 krawędziami . Sieć hipersześcianów 4D można utworzyć, powielając dwa obiekty 3D sieci i dodanie najbardziej znaczącego bitu. Nowo dodany bit powinien mieć wartość „0” dla jednego hipersześcianu 3D i „1” dla drugiego hipersześcianu 3D. Narożniki odpowiednich jednobitowych zmienionych MSB są połączone w celu utworzenia wyższej sieci hipersześcianu. Tej metody można użyć do skonstruowania dowolnego hipersześcianu reprezentowanego przez m-bit z hipersześcianem reprezentowanym przez (m-1)-bit.

Routing e-Cube

Metoda routingu dla sieci hipersześcianu jest określana jako routing E-Cube. Odległość między dwoma węzłami w sieci może być określona przez wagę Hamminga (liczbę jedynek) operacji XOR między ich odpowiednimi etykietami binarnymi.

Odległość między Węzłem 1 (oznaczonym jako „01”) a Węzłem 2 (oznaczonym jako „10”) w sieci określona wzorem:

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

Routing E-Cube to statyczna metoda trasowania wykorzystująca algorytm wyznaczania tras XY . Jest to powszechnie określane jako deterministyczny model routingu uporządkowanego według wymiarów . Routing E-Cube działa na zasadzie przemierzania sieci w k- ^tym wymiarze, gdzie k jest najmniej znaczącym niezerowym bitem w wyniku obliczania odległości.

Na przykład niech etykietą nadawcy będzie „00”, a etykietą odbiorcy „11”. Tak więc odległość między nimi wynosi 11, a najmniej znaczącym niezerowym bitem jest LSB . Ustalenie, w którą stronę wybrać „0” lub „1”, jest określane przez algorytm routingu XY.

Metryka

Do oceny wydajności połączenia sieciowego hipersześcianu w porównaniu z różnymi innymi topologiami sieci stosuje się różne miary wydajności.

Stopień

Określa to liczbę bezpośrednio sąsiadujących węzłów z danym węzłem. Te węzły powinny być bezpośrednimi sąsiadami. W przypadku hipersześcianu stopień ten wynosi m.

Średnica

Określa maksymalną liczbę węzłów, przez które musi przejść wiadomość w drodze od źródła do miejsca docelowego. Zasadniczo daje nam to opóźnienie w przesyłaniu wiadomości przez sieć. W przypadku hipersześcianu średnica wynosi m.

Średni dystans

Odległość między dwoma węzłami określona przez liczbę przeskoków na najkrótszej ścieżce między dwoma określonymi węzłami. Daje to wzór -

${\ Displaystyle d_ {a} = \ suma _ {d = 1} ^ {r} {(d.N_ {d}) \ nad N- 1}}$

W przypadku Hipersześcianów średnia odległość jest podawana w m/2.

Szerokość przecięcia

Jest to najmniejsza liczba przewodów, które należy przeciąć, aby podzielić sieć na dwie równe połowy. Podaje się ją jako 2 ^m-1 dla hipersześcianów.