diagnostyce sieci komputerowych
Formalnie,
n
-wymiarowym hipersześcianem binarnym nazywamy graf
zwykły o 2
n
węzłach z których każdy opisany jest innym wektorem binarnym
( , ,(
2
1
krawędziach, łączących te węzły,
których opisy mają odległość Hamminga równą jeden.
oraz o
n
n
z
z
z
{,},
011
i
n
)
1
n
i
Istnieje wiele (izomorficznych) sposobów przedstawiania (rysowania) n-
wymiarowego hipersześcianu binarnego, które mają określone cechy, przydatne
przy rozwiązywaniu określonych zadań z zakresu systemów, kodów
autokorekcyjnych, sieci telekomunikacyjnych, sieci multiprocesorowych oraz z
zakresu diagnostyki sieci logicznych i sieci komputerowych.
1100
1101
0101
0100
0110
1110
1111
0111
0010
1010
1011
0011
0000
1000
1001
0001
Przykład 4-wymiarowego hipersześcianu binarnego
Zbiór
Z
wektorów binarnych
zz z z
można
(
,...,
), (
{ , },
011
i
n
)
1
n
i
traktować jako zbiór wierzchołków
n
- wymiarowego hipersześcianu binarnego,
oznaczonych zgodnie z przyjętą orientacją tego hipersześcianu.
Oznaczmy:
s
{,, }
x
in
0 1
.
i
(
s s
,...,
)
{
zZsx
:((
)
(
zs
))
((
sx
)
(
z
{ , }))},
0 1
1
n
i
i
i
i
i
1
Tak więc, wektor
ss s s
011 1
można traktować jako
(
,...,
), (
{ , , },
x
i
nn
,
)
1
n
i
r
-wymiarowy, (
rC ds s
1
0
sześcian binarny, który jest
określonym podsześcianem
n
-wymiarowego hipersześcianu binarnego.
Dla przykładu, na rys. przedstawiono 4-wymiarowy hipersześcian binarny,
którego wierzchołki opisują wektory binarne
(
{' { ,..., }: '
s sx
},
rn
)
n
, a na
z
,...,
z
), (
z
{ , },
0 11
i
n
)
1
n
i
rys.2-2 zaznaczono niektóre jego podsześciany: 3-wymiarowy
(
xxx
1
, 2-
)
wymiarowy
(
x
1 0
, 1-wymiarowy
(
oraz podsześcian 0-wymiarowy (1000).
)
00 0
x
)
Niech
S
r
n
oznacza zbiór sześcianów
r
-wymiarowych, które są
podsześcianami
n-
wymiarowego hipersześcianu binarnego.
Zauważmy, że:
n
r
)
,
n
n
r
Card S
2
,(
0
rn n
,
1
r
n
r
bowiem na
sposobów można wybrać
r
składowych wektora
s
, które mają
wartość
x
, a (dla każdego takiego wyboru) pozostałe
nr
składowych może
stanowić dowolną kombinację wartości binarnych.
Niech
S
n
oznacza zbiór wszystkich możliwych podsześcianów
n
-
wymiarowego hipersześcianu binarnego, a
Z
()
-zbiór podsześcianów
0
-
wymiarowych (zbiór wektorów
podsześcianu
z
(
z
,...,
z
),
(
z
{
},
1
i
n
))
1
n
i
.
ss S
n
,(
)
Oczywiście:
,
rs
()
Card Z s
()
2
gdzie
r
()
oznacza wymiar podsześcianu
s
.
Tak więc, jeżeli
to działania na podsześcianach
s
'
i
s
"
mają sens działań na zbiorach
Z
(')
i
Z
(")
, które są określonymi podzbiorami
zbioru
Z
.
Dla przykładu, (rys.):
n
n
('
sS
)
s S
"
Z
((
00
x
0
))
{(
0010
),
(
0000
)};
Z
((
x
1
x
0
))
Z
((
xxx
1
))
;
Z
((
x
1
x
0
))
Z
((
1
xx
0
))
Z
((
11
x
0
));
Z
((
x
1
x
0
))
Z
((
x
0
x
0
))
Z
((
xxx
0
));
Z
((
xxxx
))
\
Z
((
xxx
0
))
Z
((
xxx
1
)),
Z
3
Z
4
1111
1110
1
101
0111
1011
Z
1
0110
110
0
0101
1010
0011
1001
Z
2
0100
1000
0010
0001
0000
Rys. Hipersześcian binarny 4-wymiarowy
(
xxxx
)
Z
3
Z
4
(x1x0)
Z
1
Z
2
(xxx1)
(1000)
(00x0)
Rys. Podsześciany
(
110 001000
hipersześcianu binarnego
(
xxx
), (
x x
), (
x
), (
)
xxxx
)
REKONFIGURACJA STRUKTURY PIERŚCIENIOWEJ SIECI
KOMPUTEROWEJ W SYTUACJI USZKODZENIA SIĘ
NIEKTÓRYCH Z NADMIAROWYCH LINII TRANSMISJI
DANYCH
Formalnie,
n
-wymiarowym hipersześcianem binarnym nazywamy graf
zwykły
G’
, (
G’
= <
E
,
U
’>, |
E
| = 2
n
, |
U’
| =
n
2
n
-1
) o 2
n
węzłach, z których
każdy
opisany
jest
innym
wektorem
binarnym
z
,
2
1
krawędziach, łączących te
węzły, których opisy mają odległość Hamminga równą jeden.
Mówimy, że sieć komputerowa, zawierająca 2
n
komputerów i |
U
|, (2
n
oraz o
n
n
n
(
zz zz
(
,...,
),
{ , },
011
i
nzZ
,
)
1
n
i
2
n
-1
) linii transmisji danych, ma architekturę typu hipersześcianu
n
-
wymiarowego (architekturę zagnieżdżoną w
n
-wymiarowym hipersześcianie
binarnym), jeżeli graf
G
, (
G
= <
E
,
U
>,
U
|
U
|
n
U’
) opisujący tę architekturę ,
jest grafem Hamiltona (grafem, w którym istnieje cykl Hamiltona - cykl
przechodzący przez każdy węzeł grafu jeden i tylko jeden raz).
Zauważmy, że każda architektura pierścieniowa [pętlowa], (ang. ring network,
loop network) o 2
n
komputerach jest beznadmiarową (w sensie liczby
możliwych wadliwych linii transmisji danych) architekturą typu hipersześcianu
oraz, że architektura typu hipersześcianu jest szczególnym rodzajem
architektury oczkowej (ang. mesh network).
Jednym z powodów stosowania architektury typu hipersześcianu jest
możliwość zapewnienia efektywnego funkcjonowania komputerów w
pierścieniu pomimo, iż niektóre linie transmisji danych utraciły całkowicie (na
skutek zniszczenia) lub częściowo (na skutek zakłóceń) zdolność do
funkcjonowania z wymaganą poprawnością.
Dla przykładu, na rysunku przedstawiono sieć komputerową o architekturze
hipersześcianu 4-wymiarowego, która ma 27 linii transmisji danych oraz
zaznaczono jeden z 35 możliwych, dla tej sieci, pierścieni.
1100
1101
0101
0100
0110
1110
1111
0111
0010
1010
1011
0011
0000
1000
1001
0001
Sieć komputerowa typu hipersześcianu 4-wymiarowego z zaznaczonym
pierścieniem