of 61 /61
1 De la médiation au Pair-à-Pair Georges Gardarin Georges Gardarin Nicolas Travers Nicolas Travers

1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

Embed Size (px)

Citation preview

Page 1: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

11

De la médiationau

Pair-à-Pair

Georges GardarinGeorges Gardarin

Nicolas TraversNicolas Travers

Page 2: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

22

1. Introduction1. Introduction

Inspiré de NapsterInspiré de Napster– un service distribué d'échange de fichiers musicauxun service distribué d'échange de fichiers musicaux– recherche des noms de fichiers des abonnésrecherche des noms de fichiers des abonnés– controversé pour des raisons économiques (droits controversé pour des raisons économiques (droits

d'auteur)d'auteur)

Intégration client et serveurIntégration client et serveur– les serveurs centralisent l'informationles serveurs centralisent l'information– il devient souhaitable d'accéder à toute information il devient souhaitable d'accéder à toute information

distribuée sur des réseaux de PCdistribuée sur des réseaux de PC– tout calculateur connecté au réseau peut fournir un tout calculateur connecté au réseau peut fournir un

service à un autre calculateur connecté au réseauservice à un autre calculateur connecté au réseau

Page 3: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

33

Médiateur ou P2P ?Médiateur ou P2P ?

ProblèmesProblèmes– bande passante et bande passante et

puissance du médiateurpuissance du médiateur

– fiabilité du médiateurfiabilité du médiateur

PromessesPromesses– pas de centralisationpas de centralisation– passage à l'échellepassage à l'échelle– nœuds hétérogènesnœuds hétérogènes– réseau évolutifréseau évolutif

P2PMédiateur

Page 4: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

44

PlanPlan

DéfinitionsDéfinitions

Typologie des réseauxTypologie des réseaux

Exemple de systèmes: Chord, CANExemple de systèmes: Chord, CAN

Application à la médiation: MediaPeerApplication à la médiation: MediaPeer

La sémantique: OntologieLa sémantique: Ontologie

Projets P2PProjets P2P

ConclusionConclusion

Page 5: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

55

Définitions : PairDéfinitions : Pair

Pair (Peer)Pair (Peer)– nœud sur un réseau P2P à la fois client et serveurnœud sur un réseau P2P à la fois client et serveur– communique avec ses pairscommunique avec ses pairs– est caractérisé par un identifiant (PID)est caractérisé par un identifiant (PID)

Rôles d'un pair Rôles d'un pair – clientclient : : demandedemande des services au réseau P2P des services au réseau P2P– serveurserveur : : offreoffre des services au réseau P2P des services au réseau P2P– routeurrouteur : : routeroute les demandes de service des pairs les demandes de service des pairs

Page 6: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

66

Définitions : ClusterDéfinitions : Cluster

Groupe (Cluster)Groupe (Cluster)– ensemble de pairs fournissant un service ensemble de pairs fournissant un service

communcommun

– les groupes de pairs ont un intérêt partagé ou les groupes de pairs ont un intérêt partagé ou un but communun but commun

– exemple : exemple : partager des types de données, partager des types de données,

décrire des sources d'informations similaires,décrire des sources d'informations similaires,

participer à une même application, participer à une même application,

avoir un même niveau de sécuritéavoir un même niveau de sécurité

Page 7: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

77

Définitions: TransportDéfinitions: Transport

Point terminalPoint terminal– source initiale ou destination finale de toute requête transmise sur source initiale ou destination finale de toute requête transmise sur

le réseaule réseau

ConnexionConnexion– liaison de communication entre deux points terminaux ou deux liaison de communication entre deux points terminaux ou deux

pairs, virtuelle et asynchronepairs, virtuelle et asynchrone

RequêteRequête– demande de fonction transmise sur un canal de point terminal à demande de fonction transmise sur un canal de point terminal à

point terminalpoint terminal

Le réseau physique est généralement IPLe réseau physique est généralement IP– Le protocole de transport est souvent HTTP Le protocole de transport est souvent HTTP

Le réseau logique (overlay network) Le réseau logique (overlay network) – est indépendant du réseau physiqueest indépendant du réseau physique– peut être plus ou moins structurépeut être plus ou moins structuré

Page 8: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

88

Définitions : ServiceDéfinitions : Service

ServiceService– ensemble de fonctions sémantiquement apparentées ensemble de fonctions sémantiquement apparentées

offertes par un pair serveur à un pair clientoffertes par un pair serveur à un pair client– un service se caractérise par une interface décrivant, un service se caractérise par une interface décrivant,

pour chaque fonction, les messages d'entrée et de pour chaque fonction, les messages d'entrée et de sortiesortie

ExempleExemple– transférer un fichier, effectuer un calcul, fournir une transférer un fichier, effectuer un calcul, fournir une

information d'état, localiser une ressource, …information d'état, localiser une ressource, …

Les services Web (WSDL, SOAP) sont de plus en Les services Web (WSDL, SOAP) sont de plus en plus souvent utilisés pour décrire et invoquer les plus souvent utilisés pour décrire et invoquer les servicesservices

Page 9: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

99

Services génériquesServices génériques

déclarerdéclarer un service un servicedécouvrirdécouvrir un service un serviceinvoquerinvoquer un service un servicerouterrouter les requêtes les requêtesjoindrejoindre ou ou quitterquitter un réseau, un cluster un réseau, un clusterobtenir l'état d'un pairobtenir l'état d'un pairlister les services d'un pairlister les services d'un pair……

Page 10: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1010

2. Typologie des réseaux2. Typologie des réseaux

Architectures non structuréesArchitectures non structurées– tous les pairs sont au même niveau sur le réseau logiquetous les pairs sont au même niveau sur le réseau logique– la découverte s'effectue par diffusion aux voisinsla découverte s'effectue par diffusion aux voisins– le temps de recherche n'est pas garantile temps de recherche n'est pas garanti

Architectures structuréesArchitectures structurées– tous les pairs sont au même niveau sur le réseau logiquetous les pairs sont au même niveau sur le réseau logique– le réseau logique est fortement structuré (par hachage)le réseau logique est fortement structuré (par hachage)– les données ou leurs références sont placées sur les pairsles données ou leurs références sont placées sur les pairs– le temps de recherche est garanti < log(n)le temps de recherche est garanti < log(n)

Architectures hybridesArchitectures hybrides– certains pairs sont distingués pour gérer des indexcertains pairs sont distingués pour gérer des index– ils sont appelés super-pairsils sont appelés super-pairs– le temps de recherche est partiellement garantile temps de recherche est partiellement garanti

Page 11: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1111

Réseaux non structurés (1)Réseaux non structurés (1)

Répertoire centralisé (Napster, Répertoire centralisé (Napster, Publius)Publius)

– Un serveur maintient un Un serveur maintient un répertoire des ressources et répertoire des ressources et des pairsdes pairs

– La découverte des La découverte des ressources s'effectue par ressources s'effectue par requête au serveurrequête au serveur

– Le pair se connecte Le pair se connecte directement au pair directement au pair découvertdécouvert

Page 12: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1212

Réseaux non structurés (2)Réseaux non structurés (2)Répertoire distribué Répertoire distribué (Gnutella, FreeHaven)(Gnutella, FreeHaven)– Chaque pair gère son Chaque pair gère son

répertoire de répertoire de ressourcesressources

– La découverte se fait La découverte se fait par demande aux par demande aux voisins de proche en voisins de proche en proche (flooding)proche (flooding)

– Les requêtes de Les requêtes de recherche sont recherche sont propagées dans un propagées dans un rayon de voisinage rayon de voisinage limitélimité

– Il est possible de gérer Il est possible de gérer des indices à chaque des indices à chaque nœudnœud

Page 13: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1313

Réseaux structurés (1)Réseaux structurés (1)

Chord, CAN, PastryChord, CAN, Pastry

Les données ou les références de données Les données ou les références de données sont placées sur des pairs spécifiquessont placées sur des pairs spécifiques

Le placement se fait en général par fonction Le placement se fait en général par fonction de hachagede hachage

La recherche s’effectue à partir d’une cléLa recherche s’effectue à partir d’une clé trouver rapidement un objet à partir de sa clé trouver rapidement un objet à partir de sa clé

sur un grand réseau sans structure centraliséesur un grand réseau sans structure centralisée

Page 14: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1414

Réseaux structurés (2)Réseaux structurés (2)

Typiquement, deux commandes sont gérées :Typiquement, deux commandes sont gérées :– put (key, content)put (key, content)

permet de placer une référence ou un objet (contenu) de clé key sur un pairpermet de placer une référence ou un objet (contenu) de clé key sur un pair

– lookup (key)lookup (key)

permet de retrouver un contenu à partir de sa clépermet de retrouver un contenu à partir de sa clé

Généralement, les réseaux structurés utilisent des DHTGénéralement, les réseaux structurés utilisent des DHT– DDistributed istributed HHash ash TTableable

– Temps de recherche < log(N), N étant le nombre de nœudsTemps de recherche < log(N), N étant le nombre de nœuds

– Supporte les évolutions du réseau: les pairs se connectent et se Supporte les évolutions du réseau: les pairs se connectent et se déconnectentdéconnectent

– Différentes structures de réseau : anneau, hypercube, grid, tore …Différentes structures de réseau : anneau, hypercube, grid, tore …

Page 15: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1515

DHTDHTMécanisme Mécanisme distribuédistribué et et décentralisédécentralisé permettant d’associer des valeurs de permettant d’associer des valeurs de clés à un contenu par hachage de la cléclés à un contenu par hachage de la clé– Chaque participant gère Chaque participant gère une partieune partie de la table de hachage. de la table de hachage.

– Performance en recherche de l’ordre de log(N) plus rapide qu’en non structuré (de Performance en recherche de l’ordre de log(N) plus rapide qu’en non structuré (de l’ordre de N) et hybrides (de l’ordre de sqrt(N))l’ordre de N) et hybrides (de l’ordre de sqrt(N))

– Facilement reconfigurable lorsqu’un site se connecte ou se déconnecteFacilement reconfigurable lorsqu’un site se connecte ou se déconnecte

Mécanisme général pour la localisation de ressources distribuées identifiées Mécanisme général pour la localisation de ressources distribuées identifiées par des cléspar des clés– Indexation de fichiers (clé = nom, contenu = adresse)Indexation de fichiers (clé = nom, contenu = adresse)

– Partage de documents par contenu (clé = mots-clés, contenu = document)Partage de documents par contenu (clé = mots-clés, contenu = document)

– Identification de personnes (clé = nom, contenu = clé public)Identification de personnes (clé = nom, contenu = clé public)

– Fourniture de services persistants, e.g., indexation Fourniture de services persistants, e.g., indexation

Fonction, de hachage consistante comme MD5, SHA1 pour éviter les Fonction, de hachage consistante comme MD5, SHA1 pour éviter les collisions et bien équilibré la chargecollisions et bien équilibré la charge

Page 16: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1616

Réseaux HybridesRéseaux Hybrides

Architectures où certains pairs ont des Architectures où certains pairs ont des rôles différentsrôles différents– Super-pairs : généralement chargés de gérer Super-pairs : généralement chargés de gérer

des index pour les données des pairsdes index pour les données des pairs– Pairs : gère les données indexées par les Pairs : gère les données indexées par les

super-pairssuper-pairs

Le réseau des super-pairs peut être Le réseau des super-pairs peut être structuré structuré – Hiérarchie d’index (XPeer, MediaPeer)Hiérarchie d’index (XPeer, MediaPeer)– DHT (Satine)DHT (Satine)

Page 17: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1717

Exemple de Réseau HybrideExemple de Réseau Hybride

Page 18: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1818

Domaines d'applicationsDomaines d'applications

Recherche de fichiersRecherche de fichiers

Médiation d’informationMédiation d’information– Basée schéma, données structuréesBasée schéma, données structurées

– Optimisation de requêtes distribuéesOptimisation de requêtes distribuées

Moteur de recherche distribuéMoteur de recherche distribué– Basé mots-clés, données peu structuréesBasé mots-clés, données peu structurées

Toutes ces applications ont besoin d’unifier Toutes ces applications ont besoin d’unifier et intégrer des données ….et intégrer des données ….

Page 19: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

1919

Interrogation versus DistributionInterrogation versus Distribution

Any RDBMS

AmosIIObjectGlobeTSIMMISTukWila

EdutellaPiazza

NapsterDirectConnect

GnutellaKaZaA, P-GRID

CANCHORD

Fixed schemaFixed schema/keywords/keywords

keykey

schema-basedschema-based

locallocal distributeddistributed P2PP2PP2P P2P

researchresearch

Database Database researchresearch

Page 20: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2020

3. Exemple: Chord [Stoica 2001]3. Exemple: Chord [Stoica 2001]

Table de hachage distribuéeTable de hachage distribuéeLes clés et les pairs (adresse IP) sont hachés sur le Les clés et les pairs (adresse IP) sont hachés sur le même anneau (cercle)même anneau (cercle)Fonction de hachage de Fonction de hachage de mm bit bit – Clés et pairs sont affectés à un identifiant ds [0..2Clés et pairs sont affectés à un identifiant ds [0..2mm-1] -1] – Au plus 2Au plus 2m m pairs– Succ(kid) : le plus petit identifiant de pair qui soit supérieur ou Succ(kid) : le plus petit identifiant de pair qui soit supérieur ou

égal à k mod 2égal à k mod 2mm

– Pred(kid) : le plus grand identifiant de pair inférieur à k mod 2Pred(kid) : le plus grand identifiant de pair inférieur à k mod 2mm

Chaque clé d’identifiant k est gérée par le pair suivant Chaque clé d’identifiant k est gérée par le pair suivant ou égal, i.e., d’identifiant supérieur ou égalou égal, i.e., d’identifiant supérieur ou égal– Pred(Succ(kid)) < kid ≤ Succ(kid)Pred(Succ(kid)) < kid ≤ Succ(kid)

Page 21: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2121

Exemple

6

1

2

6

0

4

26

5

1

3

7

2identifier

circle

identifier

node

X key

succ(1) = 1

succ(2) = 3

succ(6)= 0

1) indexation

Page 22: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2222

Recherche naïveRecherche naïve

Une recherche est adressée à un pair qcqUne recherche est adressée à un pair qcq– Le Peer[p] reçoit lookup(k)Le Peer[p] reçoit lookup(k)

Il retourne la clé et son contenu si la clé est Il retourne la clé et son contenu si la clé est chez luichez lui– Si clé k dans Peer[p] retourner (k, contenu)Si clé k dans Peer[p] retourner (k, contenu)

Sinon, il passe à son voisin lookup(k)Sinon, il passe à son voisin lookup(k)– Il suffit de maintenir le pointeur Succ.Il suffit de maintenir le pointeur Succ.

Problème : la recherche est en O(N) !Problème : la recherche est en O(N) !

Page 23: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2323

Amélioration : FingersAmélioration : Fingers

Chaque pair maintient dans une table de Chaque pair maintient dans une table de routage appelée « fingers » les adresses routage appelée « fingers » les adresses IP d’au plus m voisins IP d’au plus m voisins La i-eme entrée des « fingers » du pair p La i-eme entrée des « fingers » du pair p désigne le premier pair successeur de p désigne le premier pair successeur de p par au moins par au moins 22i-1 i-1 sur l’anneausur l’anneau– s = succ(p+2s = succ(p+2i-1i-1))

ss est appelé le est appelé le iithth « finger » « finger » du nœud pdu nœud p

Page 24: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2424

ExempleExemple

0

4

26

5

1

3

7

124

130

finger tablestart succ.

keys1

235

330

finger tablestart succ.

keys2

457

000

finger tablestart succ.

keys6

0+20

0+21

0+22

For.

1+20

1+21

1+22

For.

3+20

3+21

3+22

For.

Page 25: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2525

Routage amélioréRoutage amélioré

Chaque nœud connait ses successeurs Chaque nœud connait ses successeurs (N° et adresse IP) en puissances de 2 (N° et adresse IP) en puissances de 2 successives sur l’anneausuccessives sur l’anneauIl envoie ainsi la recherche au moins à Il envoie ainsi la recherche au moins à moitié chemin de la distance restant à moitié chemin de la distance restant à parcourir sur l’anneau pour trouver la cléparcourir sur l’anneau pour trouver la cléLa recherche s’effectue ainsi par La recherche s’effectue ainsi par dichotomiedichotomie– le temps de recherche est en O(logN).le temps de recherche est en O(logN).

Page 26: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2626

ExempleExemple

M=6 (N0 à N63)M=6 (N0 à N63)

Chemin suivi pour lookup(54) issue à N8Chemin suivi pour lookup(54) issue à N8

Page 27: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2727

Restructuration DynamiqueRestructuration Dynamique

Ajout d’un pair PAjout d’un pair P– Succ(P) est trouvé et le pointeur Succ. est initialiséSucc(P) est trouvé et le pointeur Succ. est initialisé– Les clés ≤ P de Succ(P) sont déplacées sur PLes clés ≤ P de Succ(P) sont déplacées sur P– Le pointeur Succ. de pred(P) est mis à P Le pointeur Succ. de pred(P) est mis à P

Retrait d’un pair PRetrait d’un pair P– Ses clés sont déplacées vers son successeurSes clés sont déplacées vers son successeur– Le pointeur Succ. de pred(P) est mis à Succ(P)Le pointeur Succ. de pred(P) est mis à Succ(P)

Il faut mettre à jour les tables de routageIl faut mettre à jour les tables de routage– Ceci est fait périodiquementCeci est fait périodiquement

Le lien Succ. correct garantie la correctionLe lien Succ. correct garantie la correction– Opération testSucc et testPred périodiquesOpération testSucc et testPred périodiques

Page 28: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2828

Bilan ChordBilan Chord

Algorithmes simples et robustesAlgorithmes simples et robustes

Recherche en log(N)Recherche en log(N)

Fiabilisation en maintenant n successeursFiabilisation en maintenant n successeurs– Anneau résistant en cas de panne d’un pairAnneau résistant en cas de panne d’un pair

Comment mapper l’anneau virtuel sur le Comment mapper l’anneau virtuel sur le réseau réel ?réseau réel ?– Prise en compte de la distance réseauPrise en compte de la distance réseau

Page 29: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

2929

Autres StructuresAutres Structures

CAN = espace à N dimensions

HyperCuP, Pastry = hypercube

P-GRID = Arbre binaire auto-adaptatif

Plateformes– JXTA de Sun

Page 30: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3030

4. Médiation P2P: MediaPeer4. Médiation P2P: MediaPeer

Il existe un grand nombre de sources (sites Il existe un grand nombre de sources (sites web) et il faut cibler les recherches pour chaque web) et il faut cibler les recherches pour chaque requêterequêteChaque pair publie une vue ontologique des Chaque pair publie une vue ontologique des données géréesdonnées géréesUtiliser des chemins de concepts pour retrouver Utiliser des chemins de concepts pour retrouver les sources de donnéesles sources de donnéesIdée clé: Idée clé: – indexé le web sémantique par des index distribués indexé le web sémantique par des index distribués

gérés par des super-pairsgérés par des super-pairs

Page 31: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3131

Architecture de réseau Architecture de réseau

Réseau hybride:Réseau hybride:– Pairs/Super-pairs.Pairs/Super-pairs.

Topologie d'arbreTopologie d'arbre– équilibrer les chargeséquilibrer les charges– structure dynamiquestructure dynamique

Groupage sémantique:Groupage sémantique:– Paires attachés à un super-Paires attachés à un super-

pair selon les concepts pair selon les concepts exportés exportés

– Super-pairs regroupés Super-pairs regroupés sous super-pairsous super-pair

peer

super-peer

Page 32: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3232

Réseau en arbreRéseau en arbre

Avantages:Avantages:– Partage des méta-données:Partage des méta-données:

Recherche efficaceRecherche efficace Routage rapide des requêtesRoutage rapide des requêtes

– Passage à l'échellePassage à l'échelleMécanisme d'éclatement si nœud trop chargéMécanisme d'éclatement si nœud trop chargé

– Mises à jour facilitéesMises à jour facilitées– Réorganisation rapide en cas de panneRéorganisation rapide en cas de panne

Inconvénients:Inconvénients:– La racine reçoit toutes les requêtesLa racine reçoit toutes les requêtes– Saturation de la racine ?Saturation de la racine ?

Page 33: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3333

Routage de requêtesRoutage de requêtes

Routage selon XPath (de concepts)Routage selon XPath (de concepts)

Basé sur des indexes de cheminsBasé sur des indexes de chemins– Gérés par les super-pairsGérés par les super-pairs

Politique de routage d'un nPolitique de routage d'un nœœudud Toujours: passer la requête à son parent Toujours: passer la requête à son parent

Selon l'index: passer la requête aux enfantsSelon l'index: passer la requête aux enfants

Page 34: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3434

Exemple: Extraction des cheminsExemple: Extraction des chemins For $h in collection("PLAYERS"),For $h in collection("PLAYERS"),

$i in collection("TEAMS")$i in collection("TEAMS")

Where $h/player/team=$i/clubWhere $h/player/team=$i/club

Return {$h/player/name} {$i/stade}Return {$h/player/name} {$i/stade}

1

2

3 3

0PLAYERS

player

teamname

stade1

2 2

0

TEAMS

club

For $h in collection("PLAYERS")Return <result>{$h/player/name}{$h/player/team}</result>

For $i in collection("TEAMS")Return <result>{$i/club}{$i/stade}</result>

Page 35: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3535

Le routageLe routage

PLAYERS1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

PLAYERS1

2

3 3

0

player

teamname

1

2

3 3

0

player

teamname

Page 36: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3636

Optimisation des indexesOptimisation des indexes

Problème:Problème:– La racine indexe tous les chemins de conceptsLa racine indexe tous les chemins de concepts– Taille de l'index racine ?Taille de l'index racine ?

Solution: Index partiel de type Patricia triéSolution: Index partiel de type Patricia trié– Index avec précision adaptableIndex avec précision adaptable– Pour chaque concept on garde les n premiers Pour chaque concept on garde les n premiers

caractèrescaractères– Précision de plus en plus faible en montant les Précision de plus en plus faible en montant les

niveauxniveaux– Routage rapide sur reconnaissance de préfixesRoutage rapide sur reconnaissance de préfixes

Page 37: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3737

Index TriéIndex Trié

<players><player><name>Zidane</name> <team>Real de Madrid</team> <age>30</age> <Address>

<city>Versailles</city> </Address>

</player></players>

0,4

0,5

0,6

0,7

0,8

0,9

1

L0 L1 L2 L3 L4 Ln

Level

Siz

e r

ed

uct

ion

(%)

0

1

2

3

PLAYERS

player

name3 3 3teamage

address

4street

0

1

2

3

PLAYERS

player

name3 3 3teamage

address

4street

0

1

2

3

PLAYE

playna

3 3 3te aaddre

4stree

0

1

2

3

PLAYE

playna

3 3 3te aaddre

4stree

0

2

3

PLAYE

na

3 3te aaddre

4

0

2

3

PLAYE

na

3 3te aaddre

4

Page 38: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3838

Médiation des donnéesMédiation des données

Découverte des sources pertinentes par les super-pairsDécouverte des sources pertinentes par les super-pairs

Réduction des données et transferts par les pairsRéduction des données et transferts par les pairs

Traitement de la requête globale par le médiateur XLiveTraitement de la requête globale par le médiateur XLive

XLive Mediator

DataSourceDataSource DataSource

Page 39: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

3939

Bilan MediaPeerBilan MediaPeer

Ce qui est proposéCe qui est proposé– Architecture de médiation sémantiqueArchitecture de médiation sémantique– Découverte des sources en pair à pairDécouverte des sources en pair à pair– Des premières mesures de performanceDes premières mesures de performance

Ce qui reste à faireCe qui reste à faire– Valider par plus de mesuresValider par plus de mesures– Développer les techniques de reprisesDévelopper les techniques de reprises– Intégrer les mappings sémantiquesIntégrer les mappings sémantiques– Lever le goulot d’étranglement de la racineLever le goulot d’étranglement de la racine

Page 40: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4040

5. Médiation P2P: PathFinder5. Médiation P2P: PathFinder

Besoin d’interroger un grand nombre de sources sur le Besoin d’interroger un grand nombre de sources sur le webwebMoteur de recherche distribué pour XML/XQueryMoteur de recherche distribué pour XML/XQueryIl faut localiser les sources pertinentes pour chaque Il faut localiser les sources pertinentes pour chaque requête requête Chaque pair publie une vue « ontologique » des Chaque pair publie une vue « ontologique » des données géréesdonnées géréesUtiliser des chemins de concepts pour retrouver les Utiliser des chemins de concepts pour retrouver les sources de donnéessources de donnéesIdée clé: Idée clé: – Utiliser une DHT pour localiser les cheminsUtiliser une DHT pour localiser les chemins

En cours de réalisation à PRiSMEn cours de réalisation à PRiSM

Page 41: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4141

ObjectivesObjectives

P2P network architecture suitable for:P2P network architecture suitable for:– Indexing of XML fragments (XML paths + Data). Indexing of XML fragments (XML paths + Data). – Processing XML queries (path and twig-queries) by routing Processing XML queries (path and twig-queries) by routing

XML paths. XML paths. – Easy to extend to a semantic level.Easy to extend to a semantic level.

Optimized architecture based on the observations of Optimized architecture based on the observations of the previously proposed archirecture: the previously proposed archirecture: – MediaPeer: A Safe, Scalable P2P Architecture for XML Query MediaPeer: A Safe, Scalable P2P Architecture for XML Query

Processing. Processing. DEXA Workshops 2005DEXA Workshops 2005– Routing Xquery in a P2P Network using Adaptable Trie-Routing Xquery in a P2P Network using Adaptable Trie-

indexes. IADIS International Conference WWW/Internet 2005, indexes. IADIS International Conference WWW/Internet 2005, Lisbon, Portugal, October 2005Lisbon, Portugal, October 2005

Page 42: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4242

Network modelNetwork model

DHT network:DHT network:– Decentralized.Decentralized.– Self-organizing.Self-organizing.– Scalable.Scalable.– Fault tolerance.Fault tolerance.– Guaranteed lookup complexity.Guaranteed lookup complexity.– Chord model:Chord model:

Model adapted to our path indexing requirements. Model adapted to our path indexing requirements.

Easy to extend.Easy to extend.

Page 43: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4343

Indexing methodIndexing method

Path clustering (observation from [MediaPeer]):Path clustering (observation from [MediaPeer]):– Index paths with similar structure at the same peer in Index paths with similar structure at the same peer in

the DHT.the DHT.– Adapt to Chord indexation method:Adapt to Chord indexation method:

Assign IDs from 0..2^m to peers and keys: consistent Assign IDs from 0..2^m to peers and keys: consistent hashing.hashing.

Store each key at the first node with an identifier that is Store each key at the first node with an identifier that is equal or follows the key identifier. equal or follows the key identifier.

– Map paths to identifiers in 0..2^m so that paths with Map paths to identifiers in 0..2^m so that paths with similar structure (similar prefix) are mapped to close similar structure (similar prefix) are mapped to close IDs. IDs.

– What about consistent hashing ? What about consistent hashing ? Index distribution. Index distribution.

Page 44: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4444

Path mapping methodPath mapping method

XML paths:XML paths:– Path := element ("/" element )* Path := element ("/" element )* – Example: catalog/book/isbnExample: catalog/book/isbn

Hash each element to a numerical value:Hash each element to a numerical value:– Example: Hl(“catalog”)=2 ; Hl(“book”)=1; Hl(“isbn”)=3Example: Hl(“catalog”)=2 ; Hl(“book”)=1; Hl(“isbn”)=3– Hash function distributed to each peerHash function distributed to each peer– Hash function may keep lexical order (range query)Hash function may keep lexical order (range query)

Based on the element values compute the path value:Based on the element values compute the path value:– Pi = t1/(2a+1)^1 +t2/(2a+1)^2 + … + tn/(2a+1)^n Pi = t1/(2a+1)^1 +t2/(2a+1)^2 + … + tn/(2a+1)^n – t1= Hl(element1) ; t2 = Hl(element2) ; …. ; tn = Hl(elementn) t1= Hl(element1) ; t2 = Hl(element2) ; …. ; tn = Hl(elementn) – a = hashing domain. a = hashing domain. – Example: Example:

P(catalog/book/isbn)= 2/41 + 1/41^2 + 3/ 41^3. P(catalog/book/isbn)= 2/41 + 1/41^2 + 3/ 41^3. Where hashing domain = 20. Where hashing domain = 20.

Page 45: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4545

Path mapping method IIPath mapping method II

Based on the previous Based on the previous mapping method, mapping method, index XML paths in index XML paths in ChordChord

XML paths with similar XML paths with similar prefix indexed by the prefix indexed by the same peer same peer

Several elements have Several elements have associated values: associated values: “author”,“title” “author”,“title”

Chord Network

1/(2 x α +1 )

2/(2 x α +1 )

5/(2 x α +1 )

Peer1

Peer2Peer3

0

1

2

catalog

book

3 3 33 isbn price

title author

PeterAlonDavidAgnesRicardo

XML …Indexing …Benchmark ..Algorithm …Routing …

Page 46: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4646

Index distributionIndex distribution

Path clustering Path clustering no no consistent hashing:consistent hashing:– The path load not The path load not

uniformly distributed to uniformly distributed to peers.peers.

Clustering solution:Clustering solution:– Re-index sub-paths from Re-index sub-paths from

an overloaded peer. an overloaded peer.

Observations:Observations:– Keep maximal prefix at Keep maximal prefix at

the same peer.the same peer.– Clustering to the same Clustering to the same

peer peer cluster on different cluster on different prefix. prefix.

– Uniform path distribution Uniform path distribution might not be reached BUT might not be reached BUT clustering maintained. clustering maintained.

Chord Network

1/(2 x α +1 )

2/(2 x α +1 )

5/(2 x α +1 )

Peer1

Peer2Peer3

0

1

2

catalog

book

33

33 isbn price

title author

PeterAlonDavidAgnesRicardo

2

3

title

XML …Indexing …Benchmark ..Algorithm …Routing …

Page 47: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4747

Query evaluationQuery evaluation

Network model adapted to twig-query Network model adapted to twig-query evaluation:evaluation:

Evaluate the common prefix.Evaluate the common prefix.Starting from the peer indexing the common prefix, Starting from the peer indexing the common prefix, evaluate the rest of sub-paths. evaluate the rest of sub-paths.

Example:Example:– for $b in collection(“catalog”)/book where contains for $b in collection(“catalog”)/book where contains

($b/author, “Alon”) and contains ($b/title,”XML”) return ($b/author, “Alon”) and contains ($b/title,”XML”) return $b/price$b/price

First route: /catalog/book –> Map to numerical value and First route: /catalog/book –> Map to numerical value and route all the query to the corresponding peer.route all the query to the corresponding peer.Depending on the local indexed values evaluate the Depending on the local indexed values evaluate the remaining sub-paths. remaining sub-paths.

Page 48: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4848

6. Semantic Web6. Semantic Web

Nouvelle vision du WebNouvelle vision du Web

Avec une sémantique communeAvec une sémantique commune

Page 49: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

4949

Web SémantiqueWeb Sémantique

Évolution du Web pour rendre l'information Évolution du Web pour rendre l'information plus accessibleplus accessible

Un vaste espace de documents semi-Un vaste espace de documents semi-structurés (XML)structurés (XML)

Décrire le contenu avec un formalisme à Décrire le contenu avec un formalisme à base de connaissances (RDF)base de connaissances (RDF)

Utiliser des ontologies communes (RDF Utiliser des ontologies communes (RDF Schema, OWL) pour annoter les Schema, OWL) pour annoter les documentsdocuments

Page 50: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5050

Qu'est-ce que la sémantique?Qu'est-ce que la sémantique?

signification des mots composéssignification des mots composésrapports de sens entre les motsrapports de sens entre les motsOpposé à syntaxe (fond/forme)Opposé à syntaxe (fond/forme)

Dégager du sens des motsDégager du sens des mots

Page 51: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5151

Qu'est ce qu'une Ontologie ?Qu'est ce qu'une Ontologie ?

Définition de termes et relations entre termes Définition de termes et relations entre termes utilisés pour décrire un domaine de utilisés pour décrire un domaine de connaissanceconnaissance

Exemples: Exemples: – Finance, Tourisme, Transport, Médecine, Immobilier ...Finance, Tourisme, Transport, Médecine, Immobilier ...

Utilisée par les gens, les bases de données et Utilisée par les gens, les bases de données et les applications pour partager l'information et les applications pour partager l'information et son sensson sens

Définition des concepts de base, de leurs Définition des concepts de base, de leurs propriétés et relationspropriétés et relations

Page 52: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5252

Cas d'usageCas d'usage

Portails WebPortails Web– Description des informations publiéesDescription des informations publiées

Objets multimedia Objets multimedia – Description des images, films, ...Description des images, films, ...

Site Web d'entrepriseSite Web d'entreprise– Unifier les informationsUnifier les informations

Documentation de conceptionDocumentation de conception– Description des documents d'ingénierieDescription des documents d'ingénierie

Agents et services Agents et services – Description de connaissances échangéesDescription de connaissances échangées

Calculateurs embarqués et mobilesCalculateurs embarqués et mobiles– Description des capacités des mobiles et terminauxDescription des capacités des mobiles et terminaux

Page 53: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5353

Objectifs de ConceptionObjectifs de Conception

Ontologies partagéesOntologies partagées

Ontologies évolutivesOntologies évolutives

Ontologies interoperablesOntologies interoperables

Détection d'incohérencesDétection d'incohérences

Equilibre entre puissance d'expression et Equilibre entre puissance d'expression et échelleéchelle

Facilité d'utilisationFacilité d'utilisation

Compatibilité avec autres standardsCompatibilité avec autres standards

InternationalisationInternationalisation

Page 54: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5454

Exemple d'Ontologie (OTA)Exemple d'Ontologie (OTA)

Page 55: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5555

Sémantique Web et Web ServicesSémantique Web et Web Services

Le Web Sémantique vise à:Le Web Sémantique vise à:– Faciliter les liens sémantiques pour le partage Faciliter les liens sémantiques pour le partage

d'information et l'interopérabilitéd'information et l'interopérabilité– Automatiser les communications et les évaluations de Automatiser les communications et les évaluations de

requêtes basées sur la composition de Web Servicesrequêtes basées sur la composition de Web Services

Semantic Web et Web Services sont Semantic Web et Web Services sont complémentaires:complémentaires:– Semantic Web= Interopérabilité sémantique des Semantic Web= Interopérabilité sémantique des

contenuscontenus– Web Services= Interopérabilité syntaxique des Web Services= Interopérabilité syntaxique des

échangeséchanges

Page 56: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5656

Sémantique Web et MédiationSémantique Web et Médiation

Finance Ontology

OntologyBoursorama

OntologyFirstInvest

Wrapper Wrapper

Mediator

Boursorama

SchemaLocal 2

SchemaLocal 1

XQuery

SchemaGlobal

Finance Ontology

Mapping Mapping

FirstInvest

wrapper

Page 57: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5757

MappingMapping

CentraliséCentralisé– Passage par une ontologie de référencePassage par une ontologie de référence– Chaque site :Chaque site :

Décrit ses données en fonction de son ontologie locale (dans son Décrit ses données en fonction de son ontologie locale (dans son langage) langage) Schéma local Schéma localMap ses descriptions (types …) en fonction d’une ontologie globale Map ses descriptions (types …) en fonction d’une ontologie globale (langage pivot) (langage pivot) Schéma exporté Schéma exporté

– Le schéma global est l’intégration des schémas exportésLe schéma global est l’intégration des schémas exportés

DécentraliséDécentralisé– Un site map ses descriptions vers ses voisinsUn site map ses descriptions vers ses voisins– Risque d’explosion combinatoire Risque d’explosion combinatoire – N² mapping au lieu de N N² mapping au lieu de N il faut limiter l’horizon des voisinsil faut limiter l’horizon des voisins

Page 58: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5858

Exemple de Mapping d’OntologieExemple de Mapping d’Ontologie

Tourism Organisation 1

Address- Street&Number- PostalCode- City

Tourism Organisation 2

Location- Street- StrNumber- City&ZIP

Page 59: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

5959

Sémantique Web et P2P Sémantique Web et P2P ComputingComputing

PC, Win2K,

Java

Mobile, Symbian,

C

MainFrame, UNIX, C++

Mac, MacOsX,

Python

Sensor, TinyOS,

Obj-crefridgerator, TinyOS, Perl

Page 60: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

6060

Bilan Sémantique WebBilan Sémantique Web

Pertinence des ontologiesPertinence des ontologies– Web ServicesWeb Services

Description du profileDescription du profileDescription des servicesDescription des services

– MédiationMédiationDescription des sourcesDescription des sourcesDescription des schémas d'intégrationDescription des schémas d'intégration

– P2PP2PDéfinition des mots-clésDéfinition des mots-clésDéfinition des mappingsDéfinition des mappings

Page 61: 1 De la médiation au Pair-à-Pair Georges Gardarin Nicolas Travers

6161

8. Conclusion8. Conclusion

P2P et médiation s’intègrentP2P et médiation s’intègrent

Nécessité de parler des mêmes objets Nécessité de parler des mêmes objets dans le même langagedans le même langage– OntologieOntologie– Mapping d’ontologieMapping d’ontologie

Besoin de passer à l’échelle du WebBesoin de passer à l’échelle du Web

Autre projet : PiazzaAutre projet : Piazza– Mappings décentralisésMappings décentralisés