Z. Zieliński – Diagnostyka i wiarygodność systemów
1
Metody diagnostyki
systemowej
Z. Zieliński – Diagnostyka i wiarygodność systemów
1
Metody diagnostyki
systemowej
Z. Zieliński –Diagnostyka systemowa sieci procesorów
2
Plan wykładu
Wprowadzenie do diagnostyki systemowej
Strategie i metody diagnostyczne
Interpretacja wyników testów – modele diagnostyczne
Diagnoza i jej rodzaje
Typy systemów samodiagnozowalnych i ich własności
Systemy jednoznacznie diagnozowalne - opiniowanie
diagnostyczne
Struktury samodiagnozowalne i ich rodzaje
Algorytmy diagnozowania sieci
Podsumowanie
Z. Zieliński –Diagnostyka systemów
3
Wprowadzenie - Systemy tolerujące uszkodzenia
System tolerujący uszkodzenia –
to system, który może wykonywać zadane
funkcje użytkowe pomimo występujących
w nim uszkodzeń (pewnej klasy).
Warunkiem koniecznym tolerowania
uszkodzeń jest poprawna ich diagnostyka.
Jej jakość ma decydujące znaczenie dla
przywrócenia zdatności systemu:
- wymiana uszkodzonych jednostek,
- odłączenie niezdatnych jednostek i
rekonfiguracja zadań (łagodna degradacja
systemu).
Z. Zieliński –Diagnostyka systemów
4
Cechy systemów tolerujących uszkodzenia
Jednostki systemu (tzn. (mikro)procesory, komputery) posiadają
oprócz zadanych możliwości użytkowych także określone
zdolności do oceny poprawności wykonania własnych funkcji
i/lub funkcji realizowanych przez inne jednostki;
Systemy takie nie są w pełni bezpieczne, tzn. zawsze
można wskazać pewne uszkodzenia, których pojawienie
się dezorganizuje pracę systemu. Innymi słowy, są to
systemy z niezawodnym jądrem, którego niezawodność
powinna znacznie przewyższać niezawodność
pozostałych elementów systemu.
Z. Zieliński –Diagnostyka systemów
5
Cechy systemów tolerujących uszkodzenia
System samodiagnozowalny
-
jest to system zdolny do diagnozy własnych uszkodzeń.
Istota metod diagnostyki systemowej (1)
Nie zakłada się w nich istnienia niezawodnego jądra
systemu (testera).
Diagnozowany system rozpatrywany jest jako zbiór
jednostek, każda z których zdolna jest do realizowania
funkcji testowania innych jednostek systemu.
Diagnostyka systemowa sieci komputerowej
(procesorowej) bazuje na tym, że wyróżnione węzły sieci
(jednostki przetwarzające) mają zdolność do testowania
innych węzłów (jednostek przetwarzających).
Zakłada się, że istnieje pewien zbiór testów, który
umożliwia funkcjonalne sprawdzenie jednostek
przetwarzających (JP) sieci komputerowej oraz systemu
(sieciowego) jako całości.
Z. Zieliński –Diagnostyka systemów
6
Istota metod diagnostyki systemowej (2)
Celem testowania przeprowadzanego przez określoną JP
(lub grupę jednostek), którego obiekt testowania stanowi
inna JP sieci, jest wydanie opinii, że testowana JP jest
(lub nie jest) w funkcjonalnym stanie zdatności.
Rozpoznanie funkcjonalnego stanu niezawodnościowego
testowanej JP realizowane jest na bazie prób
funkcjonalnych.
Przy takim podejściu podstawowym problemem jest to, że
opinie o stanie niezawodnościowym jednostek
testowanych mogą być wydawane przez jednostki
niezdatne,
a o jednostce wykonującej testowanie nie
wiadomo a priori czy jest w stanie zdatności, czy nie.
Z. Zieliński –Diagnostyka systemów
7
Z. Zieliński –Diagnostyka systemów
8
Diagnoza
Opinia globalna (syndrom) systemu jest zmienną losową,
zależną od zmiennej losowej n, którą jest nieznany stan
niezawodnościowy oraz od grafu G opiniowania
diagnostycznego tego systemu.
Diagnozą
nazywamy identyfikację stanu
niezawodnościowego systemu na podstawie syndromu.
Diagnoza
Z. Zieliński –Diagnostyka systemów
9
Niech
S
oznacza zbiór możliwych wartości wyników testów (syn-
dromów) dla określonego przydziału testów.
Diagnozą nazywamy identyfikację zbioru niezdatnych procesorów
sieci (stanu niezawodnościowego systemu) na podstawie zbioru
wyników testów (syndromu globalnego) i możemy przedstawić ją
przy pomocy funkcji:
:
2 .
E
Diag
S
Diagnoza - rodzaje
Z. Zieliński –Diagnostyka systemów
10
Diagnozę nazywamy kompletną, jeżeli na podstawie uzyskanego
syndromu
s
S
zidentyfikowany podzbiór niezdatnych procesorów
( )
Diag s
E
zawiera wszystkie niezdatne procesory, występujące w
rzeczywistym (rozpoznawanym) stanie niezawodnościowym
*
n
, to
jest
1
*
( )
E n
E
.
Diagnozę nazywamy poprawną, jeżeli
0
*
( )
E
E n
, to jest, w
procesie diagnozy procesory zdatne nie są identyfikowane jako nie-
zdatne.
Z. Zieliński –Diagnostyka systemów
11
Rodzaje diagnozy
Stan niezawodnościowy systemu n jest jednoznacznie
diagnozowalny, jeżeli jego syndrom d(n) jest unikalny dla
wszystkich możliwych (prawdopodobnych) stanów
niezawodnościowych
.
Diagnoza jest kompletna
, jeżeli wszystkie niezdatne jednostki
systemu mogą być zidentyfikowane na podstawie syndromu dla danego
stanu niezawodnościowego, w przeciwnym przypadku diagnoza jest
niekompletna.
Diagnoza jest poprawna
, jeżeli na bazie syndromu systemu
jednostki zdatne nie są identyfikowane jako niezdatne.
Z. Zieliński –Diagnostyka systemów
12
Jeżeli istnieją stany niezawodnościowe {n
1
, n
2
, . . . , n
p.
}, dla których
system generuje identyczne syndromy, najczęściej stosuje się jedną z
następujących
strategii diagnostycznych
:
1 -
identyfikacja częściowego zbioru niezdatnych jednostek
{E
1
(n
1
) ∩
E
1
(n
2
) ∩ …
∩ E
1
(n
p
) };
2 -
określenie rozszerzonego zbioru jednostek niezdatnych
{E
1
(n
1
) U E
1
(n
2
) U … U E
1
(n
p
) };
Z. Zieliński –Diagnostyka systemów
13
Strategie diagnostyczne - scentralizowane
Decyzje
testy
przepływ informacji diagnostycznych
Z. Zieliński –Diagnostyka systemów
14
Strategia rozproszona
Z. Zieliński –Diagnostyka systemów
15
Strategie diagnostyczne
Strategia off-line
jest strategią, w której jednostki biorące udział
w diagnozowaniu nie uczestniczą w realizacji zadań użytkowych
Strategia on-line
jest strategią, w której stan systemu jest wyznaczany
na bieżąco bez zawieszania zadań użytkowych
Strategia jednokrokowa
polega na wykonaniu wszystkich
dopuszczalnych testów w systemie i wyznaczeniu wszystkich
uszkodzonych jednostek na podstawie otrzymanego syndromu
W przypadku
strategii wielokrokowej
proces diagnozy i naprawy
przeplatają się nawzajem. Przyjmuje się, że na podstawie syndromu
jesteśmy w stanie określić tylko pewien niepusty podzbiór uszkodzonych
jednostek. Następnie wymienia się je na zdatne i ponawia się testowanie.
Proces powtarzany jest dopóty, dopóki nie stwierdzi się poprawnego
funkcjonowania wszystkich jednostek systemu
Z. Zieliński –Diagnostyka systemów
16
Podstawowe metody diagnostyki systemowej
metody opiniowania diagnostycznego
metody dialogu diagnostycznego
metody porównawcze
metody adaptacyjne
Z. Zieliński –Diagnostyka systemów
17
Podstawowe metody diagnostyki systemowej – (1)
Metody opiniowania diagnostycznego - zalicza się do
grupy scentralizowanych metod diagnozowania sieci
komputerowych – możliwa jest też implementacja
rozproszona.
Cechą charakterystyczną tej metody jest to, że
identyfikacji stanu niezawodnościowego sieci
komputerowej dokonuje się po uzyskaniu wszystkich
wyników testowań (opinii globalnej), wykonanych przez
każdą jednostkę sieci.
Z. Zieliński –Diagnostyka systemów
18
Podstawowe metody diagnostyki systemowej – (2)
Metody dialogu diagnostycznego należą do grupy
rozproszonych metod diagnozowania sieci
komputerowych.
W przypadku tych metod proces testowania inicjowany
jest przez dowolny komputer sieci komputerowej
i obejmuje zazwyczaj pewien podzbiór komputerów
sieci przyległych do komputera inicjującego.
Proces testowania inicjowany jest w momencie, gdy
komputer inicjujący oraz komputer testowany nie
realizują zadań obliczeniowych na potrzeby systemu.
Z. Zieliński –Diagnostyka systemów
19
Podstawowe metody diagnostyki systemowej – (3)
Metody porównawcze polegają na wnioskowaniu z
wyników określonego zbioru testów porównawczych, w
każdym z których uczestniczą trzy procesory. Jeden z
nich zwany komparatorem, zleca przyległym
procesorom jednakowe zadanie funkcjonalne oraz
sprawdza, czy wyniki wykonania tego zadania są
identyczne.
Metody porównawcze znajdują szczególne
zastosowanie w jednorodnych sieciach
(mikro)procesorowych i dają możliwości testowania
sieci podczas wykonywania zadań funkcjonalnych.
Z. Zieliński –Diagnostyka systemów
20
Podstawowe metody diagnostyki systemowej – (4)
W metodach adaptacyjnych (w odróżnieniu od
pozostałych metod diagnostyki systemowej) nie zakłada
się istnienia stałego przydziału testów.
Przydział testów konstruowany jest w sposób
dynamiczny i jest on zależny od wyników testowania się
między określonymi procesorami sieci tj.
dostosowywany jest do stanu niezawodnościowego
sieci procesorów.
Proces testowania ma charakter rozproszony i zwykle
(DSD, HiDSD) zakłada się możliwość bezpośredniej
komunikacji między wszystkimi węzłami sieci.
Z. Zieliński –Diagnostyka systemów
21
Typy systemów samodiagnozowalnych
Systemy jednoznacznie diagnozowalne
Systemy częściowo diagnozowalne
Systemy nadmiarowo diagnozowalne
Systemy sekwencyjnie diagnozowalne
Systemy przyrostowo diagnozowalne
Systemy diagnozowalne adaptacyjnie
Z. Zieliński –Diagnostyka systemów
22
Sposoby testowania
Test asymetryczny
Test symetryczny
(wzajemne testowanie się jednostek)
Z. Zieliński –Diagnostyka systemów
23
Sposoby testowania
Testowanie porównawcze (comparison method)
KOMPARATOR
Z. Zieliński –Diagnostyka systemów
24
Przydział testów
Z. Zieliński –Diagnostyka systemów
25
Wynik testu
}
1
,
0
{
ij
d
Niech
d
ij
oznacza
, wynik testu, za pomocą którego
e
i
opiniuje stan niezawodnościowy
e
j
.
Wynik testu ma zawsze binarną klasyfikację, tj. jednostka
przeprowadzająca testowanie ocenia testowany moduł
zawsze jako „zdatny” lub „niezdatny”.
Wyniki testu są zawsze poprawne: zdatna (wolna od
błędów) jednostka jest zawsze opiniowana jako „zdatna”.
Z. Zieliński –Diagnostyka systemów
26
Model z symetrycznym unieważnianiem testu (PMC)
d
ij
= 0
Oznaczenia:
- jednostka zdatna
- jednostka niezdatna
x -
wartość przypadkowa (0 lub 1)
e
i
e
j
e
i
e
j
e
i
e
j
d
ij
= 1
d
ij
= x
d
ij
= x
e
i
e
j
Modele diagnostyczne
Z. Zieliński –Diagnostyka systemów
27
Modele diagnostyczne (1)
Model z asymetrycznym unieważnianiem testu (BGM)
d
ij
= 0
Oznaczenia:
- jednostka zdatna
- jednostka niezdatna
x -
wartość przypadkowa (0 lub 1)
e
i
e
j
e
i
e
j
e
i
e
j
d
ij
= 1
d
ij
= x
d
ij
= 1
e
i
e
j
Z. Zieliński –Diagnostyka systemów
28
Opinia globalna (syndrom systemu)
Wynik testu
Dla ustalonego G (G=<E, U>) po
określonym uporządkowaniu opinii
(wydanych przez wszystkie komputery,
które testują inne komputery)
otrzymamy |U| - wymiarowy wektor binarny nazywany
opinią globalną
systemu (syndromem systemu).
Opinia globalna
d
12
d
23
d
34
d
41
Niezdatności
A
e
1
B
e
2
C
e
3
D
e
4
E
e
2
, e
3
e
1
e
2
e
3
e
4
x
0
0
1
Opinia globalna
Z. Zieliński –Diagnostyka systemów
29
Opinia globalna (syndrom systemu)
Dla ustalonego G (G=<E, U>) po
określonym uporządkowaniu opinii
(wydanych przez wszystkie komputery,
które testują inne komputery)
otrzymamy |U| - wymiarowy wektor binarny nazywany
opinią globalną
systemu (syndromem systemu).
Opinia globalna
d
12
d
23
d
34
d
41
Niezdatności
A
e
1
B
e
2
C
e
3
D
e
4
E
e
2
, e
3
e
1
e
2
e
3
e
4
x
0
0
1
1
x
0
0
0
1
x
0
0
0
1
x
1
x
x
0
Opinia globalna
Z. Zieliński –Diagnostyka systemów
30
Interpretacja wyników testów – niezdatności przemijające
Model z symetrycznym unieważnianiem testu
0
1
x
x
x
x
x
x
x
- jednostka zdatna
- jednostka z niezdatnością trwałą
- jednostka z niezdatnością przemijającą
Z. Zieliński –Diagnostyka systemów
31
Interpretacja wyników testów – niezdatności przemijające
Model z asymetrycznym unieważnianiem testu
0
1
1
x
1
x
x
x
x
- jednostka zdatna
- jednostka z niezdatnością trwałą
- jednostka z niezdatnością przemijającą
Z. Zieliński –Diagnostyka systemów
32
Struktura komunikacyjna
Struktura hipersześcianu
,
G
E U
(001)
(000)
(010)
(110)
(101)
(111)
(011)
(100)
|
| 2
n
E
1
|
|
2
n
U
n
H
3
Z. Zieliński –Diagnostyka systemów
34
Graf opiniowania diagnostycznego - przykład
e
3
e
2
e
1
e
0
e
4
e
5
e
6
e
7
Przykład grafu opiniowania diagnostycznego o postaci
cyklu Hamiltona dla |E| = 8.
35
Oznaczenia
Niech oznacza stan niezawodnościowy sieci ,
- stan zdatności
- oznacza zbiór takich stanów niezawodnościowych systemu, że
.
Dla modelu PMC: jeżeli element jest w stanie zdatności, to jego
opinia o stanie niezawodnościowym elementu
jest poprawna (zgodna z rzeczywistym stanem niezawodnościowym
elementu ) natomiast w przeciwnym przypadku - przypadkowa, to
jest
oraz
1
( ,...,
)
E
n
n
n
0
( )
0
E
n
m
N
1
E
n
n
m
i
e
(
,
, ,
)
i
j
i
j
d
e e
n n
j
e
j
e
(
,
, 0,
)
i
j
j
j
d
e e
n
n
(
,
,1,
)
(
{0,1})
i
j
j
d
e e
n
x x
Inne modele diagnostyki systemowej
i
n
j
n
(
,
, ,
)
i
j
i
j
d e e
n n
D
W
D
BGM
D
Y
D
D
D
PMC
D
pT
D
0
D
0
0
0
0
0
0
0
0
0
0
x
0
1
1
1
1
1
1
1
1
x
x
1
0
0
1
x
0
0
1
x
x
x
1
1
1
1
1
0
x
x
x
x
x
i
e
j
e
Z. Zieliński –Diagnostyka systemów
37
Miary diagnozowalności
System jest jednokrokowo m–diagnozowalny
, jeżeli
wszystkie uszkodzone jednostki mogą być zlokalizowane
na podstawie jednego syndromu wyników testowania, o
ile liczba aktualnie uszkodzonych jednostek nie
przekracza m.
System jest wielokrokowo m–diagnozowalny
, jeżeli co
najmniej jedna niezdatna jednostka może być
zlokalizowana na podstawie jednego syndromu wyników
testowania, o ile liczba aktualnie uszkodzonych jednostek
nie przekracza m
.
Z. Zieliński –Diagnostyka systemów
38
Przykład – system 1-diagnozowalny – model PMC
1
2
5
4
3
d
12
d
23
d
34
d
45
d
51
n
(węzły
niezdatne)
a
x
0
0
0
1
1
b
1
x
0
0
0
2
c
0
1
x
0
0
3
d
0
0
1
x
0
4
e
0
0
0
1
x
5
f
x
x
0
0
1
{1,2}
Opinie (syndromy)
nierozróżnialne
Z. Zieliński –Diagnostyka systemów
39
Problemy diagnostyki systemowej
1. Problem opisowy:
określenie warunków koniecznych i wystarczających,
które musi spełniać przydział testów (struktura
diagnostyczna), aby uzyskać określone właściwości
diagnostyczne.
2. Problem diagnozowalności:
ocena poziomu diagnozowalności systemu.
Struktura opiniowania diagnostycznego
Strukturę opiniowania diagnostycznego systemu (sieci
komputerowej), przedstawia się w postaci spójnego digrafu
(unigrafu zorientowanego)
bez pętli, w którym łuk oznacza, że element systemu
(komputer), wyraża opinię (na podstawie wyniku testowania) o
stanie niezawodnościowym elementu .
7
1
2
6
5
3
4
,
G
E U
,
e e
e
e
42
Wzorzec opinii diagnostycznych
Numerując łuki grafu G i znając stan niezawodnościowy
elementu, który jest początkowym węzłem łuku (o określonym
numerze), w stanie niezawodnościowym n
wyznaczamy parę
którą nazwiemy wzorcem opinii diagnostycznych struktury G ,
dla stanu niezawodnościowego n.
:
( ),
d n n
1
( ( )
( ( ),...,
( ) ),
( ) {0,1, },
i
U
d n
d n
d
n
d n
x
{1,...,
}),
i
U
43
Oznaczenia
Wektor
przedstawiający wszystkie możliwe opinie, wyrażone przez
elementy systemu nazywamy opinią globalną.
Opinia globalna jest syndromem stanu niezawodnościowego
systemu - stanowi podstawę do wnioskowania o rozpoznawanym
stanie niezawodnościowym systemu.
1
( ,...,
),
{0,1},
i
U
d
d
d
d
{1,...,
},
i
U
44
Oznaczenia
Znajomość zbioru
pozwala określić, dla zaobserwowanej opinii globalnej
zbiór alternatywnych stanów niezawodnościowych systemu -
(zbiór, którego elementem jest rozpoznawany
stan niezawodnościowy systemu),
{
( ),
:
}
m
d n n
n
N
( )
N d
( )
N d
{
:
( )
})
m
n
N
d
d n
[
( )
]
d
d n
[
{1,...,
}: ( ( )
)
(
( ))]
i
i
i
i
U
d n
x
d
d n
([(
( )
)]
[
( )
])
d
d n
d
d n
d
45
Status niezawodnościowy
Niech oznacza zbiór tych elementów
systemu, które w każdym z alternatywnych stanów niezdatności
(dla opinii globalnej d), mają jednakowy stan niezawodnościowy.
Opinia globalna d, określa status niezawodnościowy elementów
zbioru
Elementy zbioru
nie mają określonego statusu.
( ) (
{0,1})
E
d
1
( )
E d
0
( )
E d
( )
\
E d
E
1
{
( )
E d
0
( )}
E d
46
Wnikliwość rozpoznania stanu niezdatności
Wektor
taki, że
oraz
nazywamy bezpośrednią wnikliwością rozpoznania stanu
niezdatności systemu przez opinię globalną d.
:
1
( )
( ( ),...,
( )), ( ) {0,1, }
i
E
n d
n d
n
d
n d
x
(
( ))
( ( )
)
i
i
e
E
d
n d
(
i
e
( ))
E d
( ( )
)
i
n d
x
Klasy struktur opiniowania diagnostycznego
Dwie podstawowe klasy struktur:
- struktury jednoznacznie (jednokrokowo-)
m-diagnozowalne
- struktury (niejednoznacznie) sekwencyjnie
m-diagnozowalne
Dla struktury (jednokrokowo) m-diagnozowalnej, każda
(możliwa) opinia globalna identyfikuje stan
niezawodnościowy systemu;
Dla struktury sekwencyjnie m-diagnozowalnej - każda
(możliwa) opinia globalna nie identyfikuje każdego stanu
niezdatności systemu lecz określa status, co najmniej,
jednego niezdatnego elementu systemu.
:
0
( , ) \
:
( )
1
d
D m G
d
N d
1
0
( , ) \
:
( )
d
D m G
d
E d
Z. Zieliński –Diagnostyka systemów
48
Warunki konieczne – model PMC
Twierdzenie o warunkach koniecznych
W m-diagnozowalnym systemie S z grafem opiniowania diagnostycznego
G (G =<E, U>) spełnione są warunki:
a)
2
1,
| E |
m +
b)
( )
,
;
-
e m e
E
Z. Zieliński –Diagnostyka systemów
49
Warunki konieczne – model PMC - przykład
Warunki a) i b) twierdzenia są konieczne lecz nie są wystarczające :
1
2
4
3
węzły
niezdatne
d
12
d
13
d
21
d
34
d
43
(1)
x
x
1
0
0
(2)
1
0
x
0
0
(3)
0
1
0
x
1
(4)
0
0
0
1
x
Ponieważ syndromy testu przy niezdatnych węzłach (1) i (2) są nierozróżnialne –
system nie jest 1- diagnozowalny jednokrokowo
Z. Zieliński –Diagnostyka systemów
50
Warunki konieczne – model BGM
Jeżeli system S z grafem opiniowania diagnostycznego G (G =<E, U>) jest
systemem m-diagnozowalnym to:
a)
|
|
2,
E
m
b)
( )
,
e
m
Z. Zieliński –Diagnostyka systemów
51
Warunki konieczne i wystarczające (PMC)
m
Z
Z
Z
E
Z
2
/
)
(
:
)
(
1
Dla modelu PMC warunki wystarczające m-diagnozowalności systemu zostały
sformułowane przez:
[Allan, Kameda, Toida] :
System S z grafem opiniowania diagnostycznego G (G =<E, U>) jest systemem m-
diagnozowalnym wtedy i tylko wtedy, gdy spełnione są warunki konieczne oraz
gdzie
)
(
1
Z
jest zbiorem testerów elementów należących do Z.
[ Hakimi, Amin ] :
( 0
1
:
2
) :
(
)
p m - E
E | E | = | E | - m + p |
E |> p
Z. Zieliński –Diagnostyka systemów
52
Warunki konieczne i wystarczające (PMC)
[Kohda] :
System S z grafem opiniowania diagnostycznego G (G =<E, U>) jest systemem
m-diagnozowalnym wtedy i tylko wtedy, gdy dla każdej pary
takiej że |E
1
| = |E
2
|= m istnieje co najmniej jeden test z ( E - E
1
– E
2
)
do ( E
1
– E
2
) U ( E
2
– E
1
).
E
E
E
2
1
,
Z. Zieliński –Diagnostyka systemów
53
Wyznaczanie optymalnych oraz najtańszych struktur OD
1.
Spójna, optymalna struktura OD ma dokładnie jedną składową
silnej spójności.
2.
Jeżeli podgraf < E \ {e’}>
G
spójnego grafu G, jest
m-diagnozowalnym grafem OD oraz ||Γ
-1
(e’)||≥ m,
to graf G również jest m-diagnozowalnym grafem OD.
Z. Zieliński –Diagnostyka systemów
54
Wyznaczanie optymalnych oraz najtańszych struktur OD
Składową silnej spójności spójnej 1-diagnozowalnej struktury
OD jest albo cykl zorientowany rzędu co najmniej trzeciego
albo para incydentnych cykli elementarnych.
a)
b)
Przykłady 1-diagnozowalnych struktur OD rzędu ósmego
(a-spójna struktura 1-optymalna; b)-spójna struktura 1-quasi-optymalna)
Z. Zieliński –Diagnostyka systemów
55
Tabela. Uogólnione koszty testowania
u
a b c d e f g h i
j k l
ł m n o
K(u)
5 4 1 2 3 2 3 2 2 5 3 3 5 4 4 4
1
2
4
3
5
6
7
a
b
c
d
e
f
g
h
i
j
l
k
m
n
o
ł
Przykład ekonomicznego grafu
opiniowania diagnostycznego
Najtańsze (względem struktury
przedstawionej obok) struktury 1-diagnozowalne
Przykład najtańszych struktur 1-diagnozowalnych
Z. Zieliński –Diagnostyka systemów
56
Struktury optymalne 2-diagnozowalne
(dla modelu PMC) rzędu piątego
Z. Zieliński –Diagnostyka systemów
57
Systemy częściowo diagnozowalne
Klasyczne podejście do systemów m-diagnozowalnych nie
zdaje egzaminu przy identyfikacji stanów
niezawodnościowych, dla których liczba niezdatnych
jednostek jest większa niż m.
W konkretnym systemie interesuje nas często określenie,
czy dany (krytyczny ze względu na aplikacje ) zbiór stanów
niezawodnościowych jest jednoznacznie diagnozowalny.
Z. Zieliński –Diagnostyka systemów
58
Systemy częściowo diagnozowalne
Przykład.
System typu D
δ,m
, składający się z k=7 jednostek, z których każda
(i=0, 1, …, k-1) testuje m innych jednostek wg zależności:
i + δ mod k,
i + 2 δ mod k, …, i + (m-1)δ mod k.
Dla δ=1 i m=2 :
7
1
2
6
5
3
4
System jest 2-diagnozowalny dla modelu z
symetrycznym unieważnianiem testu.
Rozpatrując ten system w odniesieniu do klasy
niezdatności o liczności ≤ 3 mamy
jednoznacznie diagnozowalne:
wszystkie stany niezawodnościowe o liczbie
niezdatności 1;
14 z 21 stanów o liczbie niezdatnych jednostek 2
;
21 z 35 stanów o liczbie niezdatności 3
.
Z. Zieliński –Diagnostyka systemów
59
Systemy nadmiarowo diagnozowalne
System jest
m/p
– diagnozowalny, jeżeli syndrom systemu dla stanu
niezawodnościowego
pozwala na izolację wszystkich jednostek ze zbioru , z których co
najwyżej p jednostek może być wolnych od niezdatności
gdzie jest zbiorem niezdatnych jednostek w stanie .
,
'
m
N
n
W systemach tego typu dopuszcza się pewną liczbę (p)
niepoprawnie diagnozowanych jednostek.
n
)
(n
F
,
)
(
p
n
F
F
F
Z. Zieliński –Diagnostyka systemów
60
Systemy sekwencyjnie diagnozowalne
System jest sekwencyjnie (wielokrokowo) m – diagnozowalny,
jeżeli co najmniej jedna niezdatna jednostka może być
zlokalizowana na podstawie jednego syndromu wyników
testowania, o ile liczba aktualnie uszkodzonych jednostek nie
przekracza m.
W tym przypadku proces diagnozy i naprawy przeplatają się nawzajem.
Przyjmuje się, że na podstawie syndromu jesteśmy w stanie określić
tylko pewien niepusty podzbiór uszkodzonych jednostek. Następnie
wymienia się je na zdatne i ponawia się testowanie. Proces powtarzany
jest dopóty, dopóki nie stwierdzi się poprawnego funkcjonowania
wszystkich jednostek systemu (wymagana liczba iteracji
m, gdzie m
jest liczbą niezdatności).
Z. Zieliński –Diagnostyka systemów
61
Systemy sekwencyjnie diagnozowalne
Można wykazać, że silnie spójny graf posiadający węzeł, który
jest testowany przez m innych węzłów, a każdy z nich z kolei jest
testowany przez co najmniej jeden (inny) węzeł jest grafem
sekwencyjnie
m-diagnozowalnym.
Przykład grafu 3-diagnozowalnego
sekwencyjnie
7
1
2
6
5
3
4
Z. Zieliński –Diagnostyka systemów
62
Przykłady struktur
7
1
2
6
5
3
4
Struktura jednokrokowo
3-diagnozowalna
7
1
2
6
5
3
4
Struktura sekwencyjnie
3-diagnozowalna
Z. Zieliński –Diagnostyka systemów
63
Ogólna charakterystyka struktur opiniowania diagnostycznego dla strategii
wielokrokowej
Struktura , jest strukturą sekwencyjnie m-diagnozowalną wtedy i
tylko wtedy, gdy
:
0
[
\
:
( )
]
m
n N
N
N
n
d n
(
( ) )]
n N
E
n
0
Z. Zieliński –Diagnostyka systemów
64
Ogólna charakterystyka struktur opiniowania diagnostycznego dla strategii
wielokrokowej
Charakterystyka grafu G, który jest grafem m-diagnozowalnym
sekwencyjnie (m.d.s) jest znacznie trudniejsza niż w przypadku
systemów jednoznacznie diagnozowalnych i jak do dzisiaj ogólne
warunki dla struktury m.d.s. nie zostały określone.
W projektowaniu struktur typu m.d.s należy kierować się
własnościami wielokrotnych zbiorów niezdatności (stanów
niezawodnościowych) lub poszukiwać struktur m.d.s określonej
klasy.
:
Z. Zieliński –Diagnostyka systemów
65
Struktura diagnostyczna OD typu cykl zorientowany
podzbiór alternatywnych stanów niezdatności systemu
dla opinii globalnej
(100100100)
d
1
0
0
Cykl zorientowany rzędu dziewiątego, nie jest strukturą sekwencyjnie
4-diagnozowalną typu PMC
*
*
1
( ) :
( )
P
n N
N
N
d
E n
1
0
0
0
1
0
1
n
2
n
3
n
*
1
2
3
{ ,
,
}
N
n n n
Z. Zieliński –Diagnostyka systemów
66
Wyznaczanie wnikliwości diagnostycznej struktury OD
(
,
, )
d e e
n
1
2
3
4
1
e
2
3
4
1
3
e
n
x
0
0
1
x
(1000)
1
x
0
0
0
(0100)
0
1
x
0
1
(0010)
0
0
1
x
0
(0001)
x
x
0
1
x
(1100)
x
1
x
1
x
(1010)
x
0
1
x
x
(1001)
1
x
x
0
1
(0110)
1
x
1
x
0
(0101)
0
1
x
x
1
(0011)
1
4
3
2
Wzorzec opinii diagnostycznych tej struktury
2
( )
W G
23.03.12; STAC
24.03.2012 NSTAC
Z. Zieliński –Diagnostyka systemów
67
Wyznaczanie wnikliwości diagnostycznej struktury OD
Wzorzec nie pozwala, z wyjątkiem struktur jednokrokowo m-
diagnozowalnych, określić (w sposób bezpośredni) wnikliwość diagnostyczną
struktury.
Należy go przedstawić w postaci rozłącznych podsześcianów sześcianu
:
( )
m
W
G
U
H
(
( )
{
,
( ) :
( , )})
m
G
N
m G
0
[
( )]
[ ( )
](
\
)
m
n N
d n
N
N
N
N
n
Wyznaczanie wnikliwości diagnostycznej
Zastosowanie działań na sześcianach binarnych
1
n
8
n
2
n
6
n
9
n
3
n
5
n
7
n
10
n e
4
n
d
a
c b
( , )
d u n
1
d a
4
e
2
c b
3
u
n
( )
j n
a
b
c
d
e
x
0
0
1
x
(1000)
1
1
x
0
0
0
(0100)
2
0
1
x
0
1
(0010)
3
0
0
1
x
0
(0001)
4
x
x
0
1
x
(1100)
5
x
1
x
1
x
(1010)
6
x
0
1
x
x
(1001)
7
1
x
x
0
1
(0110)
8
1
x
1
x
0
(0101)
9
0
1
x
x
1
(0011)
10
69
Przykład działania algorytmu WWD
1
2
3
4
10
9
8
7
6
5
(x001x)
(1x000)
(01x01)
(001x0)
(x01xx)
(x1x1x)
(xx01x)
(1x1x0)
(1xx01)
(01xx1)
1
1
0
2
0
1
1
0
70
Przykład działania algorytmu – iteracja 1.
(1x000)
(0100)
( )
N
( )
n
Rezultat działania algorytmu WWD
( )
N
( )
n
1
x
0
0
0
(0100)
x
0
0
1
x
(1000)(1100)
(1x00)
0
1
x
0
1
(0010)(0011)
(001x)
0
0
1
x
0
(0001)(1001)
(x001)
1
0
1
x
0
(1001)(0101)
(xx01)
1
1
1
1
0
(1010)(0101)
(xxxx)
0
1
1
1
0
(1010)
1
1
1
1
1
(1010)
1
1
1
0
0
(0101)
1
0
1
0
1
(0110)(1001)
(xxxx)
1
0
0
0
1
(0110)
1
1
x
0
1
(0110)
0
0
1
0
1
(1001)
x
0
1
1
1
(1001)
0
1
0
1
1
(1100)(1010)(0011)
(xxxx)
0
1
0
1
0
(1100)(1010)
(1xx0)
1
1
0
1
x
(1100)(1010)
(1xx0)
0
1
1
1
1
(0011)(1010)
(x01x)
Miary własności diagnostycznych struktury
Jedną z miar własności diagnostycznych struktury
G
, która nie jest strukturą
(jednokrokowo)
m
-diagnozowalną, może być wektor
( , )
(
m G
1
( , ),
m G
2
( , ),
m G
3
( , ))
m G
,
gdzie:
0
1
( )
1
: ( )
\
( , )
(
( , )
1)
2
m
r
n
N
n
m G
D m G
;
2
( , )
m G
(
)
1
1
( )
: ( )
(
( , )
1)
2
E G
x
r
n
H
D m G
;
3
( , )
m G
(
)
1
( )
: ( ) ( )
(
( , )
1)
2
E G
r
n
x
D m G
,
przy czym
1
E
x
H
oznacza zbiór takich
E
-wymiarowych podsześcianów, które
zawierają składową równą
x
i składową równą 1.
Dla podanego przykładu:
(2, )
(11/ 28,14 / 28,3/ 28)
G
.
Analiza struktur sekwencyjnie diagnozowalnych
Struktura sekwencyjnie
3-diagnozowalna
7
1
2
6
5
3
4
Struktura sekwencyjnie
3-diagnozowalna
7
1
2
6
5
3
4
Która struktura jest lepsza?
Analiza struktur sekwencyjnie diagnozowalnych
Struktura sekwencyjnie
3-diagnozowalna
7
1
2
6
5
3
4
Struktura sekwencyjnie
3-diagnozowalna
7
1
2
6
5
3
4
1
166 / 376
2
210 / 376
3
0
1
174 / 354
2
180 / 354
3
0
Wzorzec alternatywnych stanów niezdatności struktury
Daje możliwość sprawdzenia różnych miar jakości
struktury opiniowania diagnostycznego opartych o
wnikliwość.
Może być również wykorzystany do realizowania
określonej strategii eksploatowania sieci komputerowej
tj. diagnozowania, regeneracji oraz rekonfiguracji sieci.
Można go także zastosować bezpośrednio w algorytmie
diagnozowania dla struktur sekwencyjnie
diagnozowalnych.
Uogólnienie diagnozowalności struktur OD
Wnikliwość diagnostyczna może stanowić podstawę
określania wielu miar diagnozowalności struktur OD
m-diagnozowalnych (jednoznacznie diagnozowalnych) –
strategia jednokrokowa
sekwencyjnie m-diagnozowalnych (strategia
wielokrokowa)
sekwencyjnie (m,k)-diagnozowalnych (strategia
wielokrokowa)
m/p –diagnozowalnych
i innych
Z. Zieliński –Diagnostyka systemów
77
ALGORYTMY DIAGNOZOWANIA SYSTEMU ROZPROSZONEGO
WG METODY PMC
Ruting IP
Algorytm NEW_SELF.
Algorytm EVENT_SELF.
Algorytmy adaptacyjne
Z. Zieliński –Diagnostyka systemów
78
Algorytm NEW_SELF
Założenia:
1. Maksymalna liczba niezdatnych węzłów jest ograniczona ≤ m;
2. Dla sieci określony jest stały (niezmienny) przydział testów;
3. Każdy węzeł jest testowany przez co najmniej m+1 innych węzłów;
4. Węzły zdatne przekazują raport z testowania do węzłów sąsiednich,
raporty docierają do wszystkich węzłów poprzez węzły pośrednie;
5. Nie przyjmuje się założeń, dotyczących zachowania węzłów
niezdatnych;
6. Każdy węzeł niezależnie od innych określa diagnozę stanu
niezawodnościowego sieci, wykorzystując wyniki testów własnych
oraz otrzymane raporty z węzłów sąsiednich.
Z. Zieliński –Diagnostyka systemów
79
Algorytm NEW_SELF
Sposób działania:
Każdy węzeł testuje swoich sąsiadów i generuje raport dla każdego
otrzymanego rezultatu testu. Raport ten jest przechowywany lokalnie i jest
stopniowo przesyłany do wszystkich węzłów testujących dany węzeł.
Algorytm zapewnia poprawność przesyłanych raportów poprzez
ograniczenie przesyłania raportów pomiędzy węzłami zdatnymi.
Węzeł akceptuje jedynie informacje z innych węzłów, które są przez niego
testowane i ich stan został określony jako zdatny. Potwierdzony raport
wyniku jest przesyłany pomiędzy węzłami zdatnymi w odwrotnym kierunku
niż testy.
i
k
n
j
l
m
o
Z. Zieliński –Diagnostyka systemów
80
Algorytm NEW_SELF
Schemat testowania i walidacji:
1)
węzeł i testuje węzeł j, wynik testu – zdatny;
2)
węzeł i otrzymuje raport od węzła j;
3)
węzeł i testuje węzeł j – wynik – zdatny;
4)
węzeł i zakłada, że informacje diagnostyczne otrzymane w
kroku 2 są potwierdzone (wiarygodne).
W celu zapewnienia poprawnej diagnozy algorytm NEW_SELF
zakłada, że każdy zdatny węzeł otrzymuje raporty
generowane przez inne zdatne węzły. Warunek ten może być
spełniony jeżeli każdy węzeł jest testowany przez m+1
węzłów.
Z. Zieliński –Diagnostyka systemów
81
Algorytm NEW_SELF
Ocena efektywności algorytmu NEW_SELF
Rozważmy system składający się z K węzłów, która ma być
m-diagnozowalny.
Liczba testów:
≥ K
(m + 1)
Liczba komunikatów, potrzebna do przesłania wyników testów:
K
2
(m + 1)
2
Dla 2-diagnozowalnego systemu o K=8 węzłach liczba przesyłanych
komunikatów: 576.
Z. Zieliński –Diagnostyka systemów
82
Algorytm EVENT_SELF
Modyfikacja NEW_SELF
Raport o wynikach testowania jest przekazywany przez dany
węzeł dalej (do innych węzłów), jeżeli jego dane różną się
od dotychczasowych wyników, przechowywanych w tym
węźle.
W algorytmie EVENT_SELF liczba przesyłanych komunikatów
jest znacznie zredukowana.
Istotnym parametrem jest opóźnienie diagnozy – jest to czas
jaki upływa od momentu wykrycia niezdatności do momentu
przekazania tej informacji do wszystkich węzłów.
Z. Zieliński –Diagnostyka systemów
83
Wady algorytmów: NEW_SELF i EVENT_SELF
1.
Ograniczona diagnozowalność.
0
1
7
6
5
2
3
4
W przypadku niezdatnych węzłów 3 i 4 rezultaty testów nie będą
przekazywane do pozostałych zdatnych węzłów. Przykładowo, węzeł nr 2
nie otrzyma informacji o stanie węzła nr 5.
2. Występuje znaczna redundancja w testowaniu między poszczególnymi
węzłami, jak i przy przesyłaniu komunikatów.
Z. Zieliński –Diagnostyka systemów
84
Adaptacyjny algorytm DSD
(Distributed System
Diagnosing)
Struktury danych
Każdy węzeł n
X
przechowuje tablicę TESTED_UP
X
, zawierającą K
elementów.
TESTED_UP
X
[i] = j wskazuje, że węzeł n
X
otrzymał informację
diagnostyczną od zdatnego węzła: n
i
przetestował n
j
i określił jego stan jako
zdatny.
Adaptacyjny algorytm DSD wykonywany jest w każdym węźle i identyfikuje
pierwszy wolny od niezdatności węzeł, a następnie aktualizuje lokalne
informacje diagnostyczne na podstawie informacji otrzymanych z tego węzła.
Osiągane jest to w sposób następujący:
Ustalana jest lista węzłów w porządku sekwencyjnym (n
0
, n
1
, … , n
K-1
).
Węzeł n
X
identyfikuje stan kolejnych węzłów z listy tj.:
n
X+1
, n
X+2
, …. ,
dopóki nie określi węzła zdatnego.
Dodawanie wykonywane jest modulo K.
Z. Zieliński –Diagnostyka systemów
85
Adaptacyjny algorytm DSD
(Distributed System
Diagnosing)
/* Adaptacyjny algorytm DSD */
y=x;
REPEAT
{ y=(y+1) mod K
request n
y
to forward
TESTED_UP
y
to n
x;
} UNTIL (n
x
tests n
y
as “FAULT-FREE”);
TESTED_UP
X
[x] = y
for i=0 to K-1
if (i ≠ x) TESTED_UP
X
[i] = TESTED_UP
y
[i];
Z. Zieliński –Diagnostyka systemów
86
Adaptacyjny algorytm DSD
(Distributed System
Diagnosing)
Przykład
0
1
7
6
5
2
3
4
2
x
3
6
x
x
7
0
TESTED_UP
2
:
Z. Zieliński –Diagnostyka systemów
87
DSD
symetryczne przekazywanie raportów
5
2
3
4
6
7
0
1
Z. Zieliński –Diagnostyka systemów
88
DSD
asymetryczne przekazywanie raportów
5
2
3
4
6
7
0
1
Z. Zieliński –Diagnostyka systemów
89
DSD -
sposoby przekazywania raportów
5
2
3
4
6
7
0
1
Wykorzystanie transmisji typu multicast
0
1
2
5
4
3
Z. Zieliński –Diagnostyka systemów
90
Adaptacyjny algorytm Adapt2
Adapt2 jest adaptacyjnym algorytmem służącym diagnozowaniu węzłów w
sieciach i systemach wieloprocesorowych (wielokomputerowych). Algorytm
dopuszcza dynamiczne uszkodzenia i naprawy węzłów i połączeń między
węzłami w czasie jego działania.
W wyniku jego działania konstruowany jest przydział testów, który
gwarantuje, że każde uszkodzenie węzła zostanie wykryte przez co najmniej
jeden sprawny węzeł sieci. Adapt2 wykonuje się w dwóch fazach: pasywnej i
aktywnej.
W fazie pasywnej węzeł okresowo testuje sąsiadów wg przydziału testów.
Faza aktywna jest inicjowana w momencie wykrycia zmiany stanu węzła
(uszkodzenie bądź restart po naprawie). Prawidłowo działające węzły
konstruują wtedy nowy przydział testów i odświeżają swoją diagnozę
wszystkich jednostek w sieci.
Z. Zieliński –Diagnostyka systemów
91
Adaptacyjny algorytm Adapt2
Pakiet nazywany jest kompletnym, kiedy przejdzie przez wszystkie zdatne
węzły i powróci do pierwotnego nadawcy (zwanego root). Ścieżka przebyta
przez pakiet determinuje przydział testów. Przydział testów ma strukturę
drzewa. Każdy węzeł testuje węzeł, od którego otrzymał dany pakiet (ojca) i
wszystkie węzły do których go wysłał (dzieci).
Algorytm Hi-A-DSD
Testowanie innych węzłów w sposób hierarchiczny
Algorytm Hi-A-DSD
Zdatne węzły
Niezdatne węzły
Algorytm Hi-A-DSD
Węzeł 0 rozpoczyna testowanie.
Algorytm Hi-A-DSD
Testowanie - n
astępny klaster
Algorytm Hi-A-DSD
Testowanie z perspektywy
węzła 0
następny klaster
Algorytm Hi-A-DSD
Następny klaster
Algorytm Hi-A-DSD
Następny węzeł
Algorytm Hi-A-DSD
Więcej klastrów już nie ma – runda testowania kończy się.
Przetestowane węzły
Sieć SNMP
Agent -> Zarządca -> Super Zarządca
Interfejs użytkownika – wynik
Z. Zieliński –Diagnostyka systemów
102
Podsumowanie
Podstawowymi modelami opiniowania diagnostycznego są modele
PMC i BGM;
Niezdatności przemijające nie wnoszą nic istotnego z punktu
widzenia projektowanej struktury diagnostycznej
Niektóre typy systemów samodiagnozowalnych rozszerzają
możliwości diagnostyczne kosztem utraty pewnej liczby jednostek
zdatnych;
W ogólnym przypadku wyznaczanie struktur diagnostycznych
charakteryzuje się dużą złożonością obliczeniową – należy
poszukiwać metod niwelujących złożoność wynikającą z
izomorfizmu struktur
Algorytmy adaptacyjne można lepiej dostosować dla zapewnienia
min. czasu opóźnienia diagnozy.