Détecteurs de défaillances adaptables

11

Détecteurs de Détecteurs de défaillancesdéfaillances adaptablesadaptables

Marin BERTIERMarin BERTIER

Thèmes SRCLaboratoire d'Informatique de Paris 6Université Pierre & Marie Curie

2

Introduction

Détection de défaillancesDétection de défaillances► Impossibilité de résoudre le consensus dans Impossibilité de résoudre le consensus dans

un système asynchrone [FLP85]un système asynchrone [FLP85]► Caractéristiques :Caractéristiques :

Fournissent une liste non fiable des processus Fournissent une liste non fiable des processus suspectés d’être défaillantssuspectés d’être défaillants

Complétude : Un processus défaillant doit être Complétude : Un processus défaillant doit être considéré comme défaillant par les autresconsidéré comme défaillant par les autres

Justesse : Un processus correct ne doit pas être Justesse : Un processus correct ne doit pas être considéré défaillantconsidéré défaillant

►Modèle partiellement synchrone Modèle partiellement synchrone (GTS)(GTS)

3

Techniques de détectionTechniques de détection► Applicatif (refus de services)Applicatif (refus de services)► PingingPinging

► HeatbeatHeatbeat

Détecteur sur q p up

p down

p up

p

q

Détecteur sur q p up

p down

p up

p

q

Introduction

4

Qualité de serviceQualité de service►MétriquesMétriques

Temps de détectionTemps de détection Temps entre deux erreurs (TTemps entre deux erreurs (TMRMR)) Durée des erreurs (TDurée des erreurs (TMM))

Introduction

DF

TM

TMR

Processus p up

5

Détecteurs de défaillancesDétecteurs de défaillances►Fonctionnement « hearbeat »Fonctionnement « hearbeat »►Défaillances: Défaillances:

crash / ‘recovery’crash / ‘recovery’ perte de messagesperte de messages

►Adaptable :Adaptable : Estimations dynamiquesEstimations dynamiques Intervalle d’émissionIntervalle d’émission

►Permet le transport d’informationPermet le transport d’information

6

OrganisationOrganisation►Organisation hiérarchique Organisation hiérarchique ► CommunicationCommunication

IP-Multicast au niveau localIP-Multicast au niveau local UDP au niveau globalUDP au niveau global

LAN 1

LAN 3

LAN 2

Organisation Hiérarchique

7

Niveaux HiérarchiquesNiveaux Hiérarchiques►Visions:Visions:

Niveau Local :Niveau Local :►Liste des sites du LANListe des sites du LAN

Niveau global :Niveau global :►Liste des LANsListe des LANs

►Qualité de service différentesQualité de service différentes

Organisation Hiérarchique

8

ComportementComportement

S1.1

S1.5

S1.2

S1.4

S1.3

S1.2

S2.1

S3.5

LAN 1

LAN 2

LAN 3LENT

S1.5

S1.5

S1.5 S1.4

S1.5

Organisation Hiérarchique

9

Avantages / DésavantagesAvantages / Désavantages►Avantages:Avantages:

Nombre de messages Nombre de messages (n: nb sites, k: nb (n: nb sites, k: nb groupes)groupes)►Système plat: n * (n -1)Système plat: n * (n -1)►Hiérarchique: nHiérarchique: n22 / k + k / k + k22 – k – 1 – k – 1►Si n > kSi n > k22 un leader gère moins de messages un leader gère moins de messages

►Partitionnement des informationsPartitionnement des informations►Mise en place de mécanismeMise en place de mécanisme

Élection de leaderÉlection de leader

Organisation Hiérarchique

10

Election de leaderElection de leader► Liste triée de leadersListe triée de leaders► Leader suspecté par une majorité Leader suspecté par une majorité

changement de leaderchangement de leader

Organisation Hiérarchique

11

ArchitectureArchitecture► Emission de message Emission de message

« I-am-alive »« I-am-alive »► Estimation de baseEstimation de base

Compromis entre le Compromis entre le temps de détection et temps de détection et le nombre de fausses le nombre de fausses detectiondetection

► Fournit : Fournit : Liste de sites suspectsListe de sites suspects Informations sur la Informations sur la

détectiondétection► Adaptation de Adaptation de

l’intervalle d’émissionl’intervalle d’émission Couche de base Blackboard

Liste de sites suspectsIntervalle d’émissionMarge de détectionQoS observée

Couche d’adaptation 1 Couche d’adaptation 2

Application 1 Application 2

QoS 1 QoS 2Liste desuspects

Liste desuspects

i 1i 2

12

ArchitectureArchitecture

Couche de base Blackboard

Liste de sites suspectsIntervalle d’émissionMarge de détectionQoS observée

Couche d’adaptation 1 Couche d’adaptation 2

► Spécifique à Spécifique à l’applicationl’application

► Adapte la QoSAdapte la QoS Différents algorithmesDifférents algorithmes

► Adaptation de Adaptation de l’interfacel’interface Pop ou PushPop ou Push

► Permet différentes Permet différentes vision du systèmevision du système

Application 1 Application 2

QoS 1 QoS 2Liste desuspects

Liste desuspects

i 1i 2

13

ArchitectureArchitecture

Couche de base Blackboard

Liste de sites suspectsIntervalle d’émissionMarge de détectionQoS observée

Couche d’adaptation 1 Couche d’adaptation 2

Application 1 Application 2

QoS 1 QoS 2Liste desuspects

Liste desuspects

i 1i 2

► Représente l’utilisateur Représente l’utilisateur des détecteurs de des détecteurs de défaillance :défaillance : Service de nommageService de nommage

► Fournir le besoin en QoS Fournir le besoin en QoS locallocal

► Utilise la liste des sites Utilise la liste des sites suspectssuspects

14

Couche de baseCouche de baseFonctionnementFonctionnement

Architecture

Processus q

FD de q

Processus phi-1 hi hi+1 hi+2

i

i i+1 i+2Freshness points: i-1

Ai

to

15

Couche de baseCouche de baseEstimation de la date d’arrivéeEstimation de la date d’arrivée

► Calcul de la date butoirCalcul de la date butoir Timeout (Timeout (k+1)= date théorique ()= date théorique (EAEAk+1k+1) + marge ) + marge

dynamique (dynamique (k+1k+1))►Date théorique : estimation de ChenDate théorique : estimation de Chen

►Marge dynamique (algorithme de Marge dynamique (algorithme de jacobson)jacobson)

111

1

1

..

.

kkk

kkkk

kkk

kkkk

vadelay

vaerrorvava

delaydelaydelay

delayEAAerror

i

k

kiiik kiA

nEA

.1.1

11

Architecture

16

Adaptation du délai Adaptation du délai d’émissiond’émission

►Motivation :Motivation : Besoins variables des applicationsBesoins variables des applications Etat du réseauEtat du réseau

►Négocier entre récepteurs et Négocier entre récepteurs et l’émetteurl’émetteur

Architecture

17

Plateforme de testPlateforme de test► Utilisation de « dummynet » Utilisation de « dummynet » (simulateur reseau)(simulateur reseau)

Introduction de délai de propagationIntroduction de délai de propagation Variation du délai de propagationVariation du délai de propagation Introduction de perte de messagesIntroduction de perte de messages

Group 3Toulouse

Group 2San Francisco

Group 1Paris

Délai : 50ms +/- 10msPerte de messages : 1.2%

Délai : 10ms +/- 4msPerte de messages : 0.5%

Délai : 150ms +/- 25msPerte de messages : 3%

Performances couche d’adaptation

18

AdaptateurAdaptateur► Adaptateur 1: Réévaluation de la marge périodiquementAdaptateur 1: Réévaluation de la marge périodiquement► Adaptateur 2: Réévaluation de la marge à chaque fausse détectionAdaptateur 2: Réévaluation de la marge à chaque fausse détection► Expérimentation: durée Expérimentation: durée 32h32h, intervalle , intervalle 1000ms1000ms

DétecteurDétecteur Adaptateur Adaptateur 11

Adaptateur Adaptateur 22

Durée Durée totaletotale

Temps détectionTemps détection 1216,11216,1 2089,92089,9 2311,92311,9Nb fausses Nb fausses détectiondétection 4343 66 88

Durée des erreursDurée des erreurs 1100,61100,6 272,5272,5 101,4101,4

InitialisationInitialisation

Temps détectionTemps détection 1113,21113,2 1749,31749,3 1351,91351,9Nb fausses Nb fausses détectiondétection 88 55 44

Durée des erreursDurée des erreurs 953,2953,2 339,3339,3 529,1529,1

Performances couche d’adaptation

19

OrganisationOrganisation► Conditions:Conditions:

i = 700msi = 700msNb de sitesNb de sites 44 66 99 11

221166

Nb de sites par groupe Nb de sites par groupe locallocal 22 33 33 44 44

Nb de groupes localNb de groupes local 22 22 33 33 44

0

0,04

0,08

0,12

0,16

4 9 16

Organisation à platLeader en hiérarchique

Non leader en hiérarchique

Performances couche d’adaptation

20

Conclusion et perspectivesConclusion et perspectives► Service de détection de défaillances:Service de détection de défaillances:

ScalableScalable PartagéPartagé AdaptableAdaptable Fournissant une QoS localeFournissant une QoS locale

► PerspectivesPerspectives Gestion du partitionnementGestion du partitionnement Utilisation pour un service de nommageUtilisation pour un service de nommage Application de gestion de verrouApplication de gestion de verrou

►Web : Web : http://www-src.lip6.fr/http://www-src.lip6.fr/darxdarxhttp://regal.lip6.fr/http://regal.lip6.fr/publipubli (DNS’2002 adaptation, DSN’2003 hiérarchie)(DNS’2002 adaptation, DSN’2003 hiérarchie)

21

Comportement de la Comportement de la détectiondétection

Initialisation

Performances couche de base

22

Performances avec chargePerformances avec chargePerformances couche de base

23

PerformancePerformance

► Adaptation :Adaptation : Court terme (Marge)Court terme (Marge) Moyen terme (Estimation date)Moyen terme (Estimation date)

► ConclusionConclusion Bon compromis entre temps de détection et le Bon compromis entre temps de détection et le

nombre de fausses détectionsnombre de fausses détections

DynamiqueDynamique RTTRTT ChenChenNb fausses Nb fausses détectionsdétections 2424 5454 2929

Durée erreurs Durée erreurs (ms)(ms) 31,631,6 25,2325,23 36,6136,61

Temps de Temps de détection (ms)détection (ms) 5131,75131,7 5081,795081,79 5672,535672,53

Performances couche de base