PBST*: UNE NOUVELLE VARIANTE DES SDDS

Amina ChikhaouiESI

Algeriaa_chikhaoui@esi.dz

Pr. Djamel Eddine ZegourESI

Algeriad_zegour@esi.dz

Dr. Walid Khaled HidouciESI

Algeriaw_hidouci@esi.dz

Rencontres sur la Recherche en Informatique R2I 201112-14 Juin 2011

Tizi-Ouzou, Algérie

Difficultés d’adaptation des structures de données classiques aux environnements distribués

Les structure de données distribuées et scalables (SDDS)

CONTAXTE

Problématiques

Solution

2

PLAN

SDDS

PBST

PBST*

Architecture et protocoles de communication

Tests

Conclusion

3

SDDS

Définition

Les SDDS constituent une nouvelle famille de structures de données définies spécifiquement pour les multiordinateurs.

Caractéristiques

Scalabilité

Distribution

Disponibilité

4

SDDS

Basées sur le hachageBasées sur les arbres

Multidimensionnelle

Variantes à haute disponibilité IH*

UnidimensionnelleUnidimensionnelle Multidimensionnelle

LH*LH

LH*M LH*S LH*g, LH*SA ,

LH* RS

k-RP*dPI-tree

RP*N, RP*C , RP* S.

RP*RS

Variantes à haute disponibilité

SDDS

PBST*

5

PBST(n)

Définition

Une nouvelle vue de structure de données arborescentes, il permet de partitionner un ensemble de données ordonnées.

Propriétés

1- La taille maximale d’une case est n-1.

2- Deux cases sœurs ne peuvent pas avoir une différence de hauteur supérieure à un.

3- La somme des tailles de deux cases sœurs est supérieure à n-1.

4- Toutes les cases feuilles ont la même profondeur.

6

PBST

50

30 65

15 43 57 73

6 26 36 48 52 60 71 78

case 1

case 2case 3case 4case 5

PBST(5):

7

PBST*

Description PBST*

La SDDS PBST* représente une variante pour les SDDS qui est basée sur le partitionnement des données

PBST* est basé sur le modèle Client/Serveur

Un fichier PBST* est distribué sur plusieurs serveurs

Chaque serveur S contient un ensemble d’enregistrements organiser en arbre de recherche binaire équilibré et un intervalle ]λ,β[.

8

PBST*

Le client PBST* a une image partielle ou complète sous forme d’un arbre de recherche binaire

il existe deux types de serveurs PBST*:

1. serveur de données

2. Serveur de donnée index

20

2530

25

S2 S3

S1 ] -,+l[

S2 ] -, a[

S3]a,- [

Description PBST*

9

PBST*

Description PBST*

Le paramètre de partitionnement (n)

Le seuil minimale(smin) 

Le seuil intermédiaire(sint) 

10

PBST*

Évolution du fichier PBST*

serveur 1: ]-∞,+∞[ S1 : ]-∞ , +∞ [

Image initiale d'un client PBST*

11

PBST*

25

30 20

Insertion 15

Insertion 50 Éclatement

15 50

serveur 1: ]-∞,+∞[

Évolution du fichier PBST*

12

PBST*

25

20

15

30

50

S2 S3

serveur 1: ]-∞,+∞[

serveur 2: ]-∞,25[

serveur 3: ]25,+∞[

Insertion 23

Insertion 10

Insertion 18 Éclatement

23

10 18

Évolution du fichier PBST*

13

PBST*

25

18

S2 S4

S3

15

10

20

23

30

50

server1:]-∞,+∞[

server3:]25,+∞[server4:]15,25[server2:]-∞,15[

Évolution du fichier PBST*

14

PBST*

S1:]- ,+[

S2:]- ,13[

S4:]13 ,25[

S3:]25 ,+[

Image client

15

Architecture et prototype de communication

Architecture générale de la plate forme SDDS PBST*

Application 1

Application 2

Application n

Dialogue app/client

Client 1

Client 2

Client m

Dialogue client/fns

Serveur de noms

Dialogue fns/coord

coordinateur

Dialogue serveur/serveur Dialogue serveur/serveur

Dialogue coord/serveur Dialogue coord/serveur

Dialogue client/serveur

16

Protocole de recherche

Client

Application

Requête derecherche

Ack

Recherche de C

réponse

redire

ction

redirection

redirection

Architecture et prototype de communication

IAM

IAM

IAM

17

Architecture et prototype de communication

Protocole d’insertion

Application

Client

Ack

Ensemble des serveurs

libres

coordinateur

Allocation d’un serveur

Insertio

n de C

IAM

redirecti

on redirection

IAM

IAM

redirection

Éclatem

entReq

uête

d’in

sert

ion R

éponse

18

Nombre d’éclatement par opération d’insertion

Plus la capacité d’un serveur est grande moins on a d’éclatements.

Le nombre moyen d’éclatement par opération d’insertion est très faible et reste constant quelque soit la taille des fichiers

Confirme la Scalabilité de la SDDS PBST*

La capacité de serveur est le responsable du nombre de serveurs à alloués pour un fichier.

Tests

19

Nombre moyen de redirections

La moyenne des erreurs d’adressage est à voisine de 0,4

Tests

20

Les SDDS sont un domaine de recherche pleine d’expansion

PBST* est une nouvelle variante de SDDS basé sur les arbres de recherche binaire

Conclusion

Conclusion

Perspectives

Adapter PBST* à un environnement en grille

Sécuriser les échanges de données entre les différents composants.

21

Merci

22