Thesis Magistere 05

Rpublique Algrienne Dmocratique et PopulaireMinistre de lenseignement suprieur et de la recherche scientique Universit Abderrahmane Mira, Bejaa Ecole doctorale dinformatique Rseaux et Systmes Distribus (ReSyD)

R eSyD

Thse de MagisterOption : Rseaux et Systmes Distribus

Thme

DCOUVERTE ET LOCALISATION DE SERVICES EN MODE P2P

AMAD Mourad Directeur de thse : M r . MEDDAHI Ahmed Co-Directeur de thse : M r . VANWORMHOUDT Gilles Soutenu le 05 Novembre 2005 devant le jury :Prsident de jury : M r . KERKAR Moussa Rapporteur : Examinateur : Examinateur : Professeur Universit de Bejaa, Algrie M r . MEDDAHI Ahmed Maitre de confrences GET/ENIC TELECOM Lille1, France M r . VANWORMHOUDT Gilles Maitre de confrences GET/ENIC TELECOM Lille1, France r M . NAIT ABDESSELAM Farid Maitre de confrences Universit Lille1, Francec AMAD Mourad, Novembre 2005

ii

A ma mre A mon pre A mes frres et surs A toute ma famille A la mmoire de notre collgue Chahine A tous mes amis

iii

Table des Matires

Table des matires Liste des Tableaux Liste des Algorithmes Table des Figures Remerciements Rsum Introduction Gnrale 1 Dcouverte et localisation de services en mode P2P 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Les rseaux peer-to-peer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Les applications Peer-to-Peer . . . . . . . . . . . . . . . . . . . . . . 1.2.2 Les aspects des rseaux P2P . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Les obstacles du rseau P2P . . . . . . . . . . . . . . . . . . . . . . . 1.2.4 Les systmes bass sur la technologie P2P et leurs classications . . 1.2.5 Le futur des rseaux P2P . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Rseaux non structurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Napster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1.1 La structure de messages Napster . . . . . . . . . . . . . . 1.3.2 Gnutella . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2.1 La structure de messages Gnutella . . . . . . . . . . . . . . 1.3.2.2 Les principaux messages utiliss dans le protocole Gnutella 1.3.2.3 Mcanisme de routage . . . . . . . . . . . . . . . . . . . . 1.3.2.4 Recherche de donnes . . . . . . . . . . . . . . . . . . . . . 1.3.2.5 La tolrance aux pannes . . . . . . . . . . . . . . . . . . . . 1.3.3 Les protocoles probabilistes . . . . . . . . . . . . . . . . . . . . . . . 1.3.4 Lalgorithme de Plaxton . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Rseaux structurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Le protocole chord . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1.1 Le rseau virtuel . . . . . . . . . . . . . . . . . . . . . . . .

iv ix ix xi xiii xiv 1 4 4 5 5 6 8 9 10 10 10 11 12 12 12 13 14 15 15 16 17 18 18

. . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . .

iv

1.5

1.6 1.7 1.8

1.4.1.2 Lidenticateur du nud . . . . . . . . . . . . . . . . 1.4.1.3 Le hachage consistent (Cohrent) . . . . . . . . . . . 1.4.1.4 Placement des ressources . . . . . . . . . . . . . . . . 1.4.1.5 Recherche de donnes . . . . . . . . . . . . . . . . . . 1.4.1.6 Exemple de recherche . . . . . . . . . . . . . . . . . . 1.4.1.7 Tables des raccourcis . . . . . . . . . . . . . . . . . . 1.4.1.8 Algorithme de recherche avec des tables de raccourcis 1.4.1.9 Arrive dun nud . . . . . . . . . . . . . . . . . . . . 1.4.1.10 Construction des tables de raccourcis . . . . . . . . . 1.4.1.11 Algorithme de recherche avec tolrance aux fautes . . 1.4.1.12 Les caractristiques du protocole Chord . . . . . . . . 1.4.2 CAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2.1 Arrive dun nud . . . . . . . . . . . . . . . . . . . 1.4.2.2 Dpart dun nud . . . . . . . . . . . . . . . . . . . . 1.4.2.3 Le routage . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 Pastry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.4 Analyse des systmes bass sur les DHTs . . . . . . . . . . . . . Laspect smantique dans les rseaux P2P . . . . . . . . . . . . . . . . 1.5.1 Dtection implicite de la smantique . . . . . . . . . . . . . . . 1.5.2 Dtection explicite de la smantique . . . . . . . . . . . . . . . Performances des systmes P2P . . . . . . . . . . . . . . . . . . . . . . Problmes ouverts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . .

18 19 20 20 20 22 23 23 23 24 24 25 26 26 27 28 28 29 29 29 30 30 31 32 32 33 33 33 34 35 35 36 36 37 37 38 38 39 39 39 40 41 41 41 42

2 Internet Quatre Niveaux (I4N ) 2.1 Introduction . . . . . . . . . . . . . . . . . 2.2 Motivations . . . . . . . . . . . . . . . . . 2.3 Identication des nuds et des ressources 2.4 Architecture du rseau I4N . . . . . . . . 2.5 Placement des ressources . . . . . . . . . . 2.6 Construction de la table de routage . . . . 2.7 Recherche de donnes . . . . . . . . . . . 2.8 Arrive dun nud . . . . . . . . . . . . . 2.9 Dpart dun nud . . . . . . . . . . . . . 2.10 Acclration de la recherche . . . . . . . . 2.11 Proprits de protocole . . . . . . . . . . . 2.12 Lvolution du rseau . . . . . . . . . . . . 2.13 Conclusion . . . . . . . . . . . . . . . . . . 3 Les direntes plateformes P2P 3.1 Introduction . . . . . . . . . . . . . 3.2 XtremWeb . . . . . . . . . . . . . . 3.2.1 Principe de fonctionnement 3.3 ProActive . . . . . . . . . . . . . . 3.3.1 Principe de fonctionnement 3.4 JXTA . . . . . . . . . . . . . . . . 3.4.1 Principe de fonctionnement

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

v

3.5

Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 43 43 44 44 44 44 44 45 45 45 45 46 46 48 49 49 50 50 50 50 51 51 51 51 51 51 52 52 52 53 53 53 53 53 53 53 54 54 54 55 55 56 56

4 Les Rseaux P2P et la technologie JXTA 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Le Projet JXTA . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2.1 Les Objectifs de projet JXTA . . . . . . . . . . . . . . . 4.2.1.1 Interoprabilit . . . . . . . . . . . . . . . . . . 4.2.1.2 Lindpendance de plateformes . . . . . . . . . 4.2.1.3 Ubiquit . . . . . . . . . . . . . . . . . . . . . 4.2.1.4 Scurit . . . . . . . . . . . . . . . . . . . . . . 4.2.2 Les concepts de la technologie JXTA . . . . . . . . . . . 4.2.2.1 Les identicateurs . . . . . . . . . . . . . . . . 4.2.2.2 Peers . . . . . . . . . . . . . . . . . . . . . . . 4.2.2.3 Advertissement . . . . . . . . . . . . . . . . . 4.2.2.4 PeerGroup . . . . . . . . . . . . . . . . . . . . 4.2.2.5 Module . . . . . . . . . . . . . . . . . . . . . . 4.2.2.6 Pipe . . . . . . . . . . . . . . . . . . . . . . . 4.2.2.7 Message . . . . . . . . . . . . . . . . . . . . . 4.2.3 Larchitecture de la plateforme JXTA . . . . . . . . . . 4.2.3.1 La couche Noyau . . . . . . . . . . . . . . . . . 4.2.3.2 La couche Service . . . . . . . . . . . . . . . . 4.2.3.3 La couche Application . . . . . . . . . . . . . . 4.2.4 Les protocoles de la plateforme JXTA . . . . . . . . . . 4.2.4.1 Peer Discover Protocol (PDP) . . . . . . . . . 4.2.4.2 Peer Resolver Protocol (PRP) . . . . . . . . . 4.2.4.3 Peer Information Protocol (PIP) . . . . . . . . 4.2.4.4 Rendez vous protocol (RVP) . . . . . . . . . . 4.2.4.5 Pipe binding Protocol (PBP) . . . . . . . . . . 4.2.4.6 Endpoint routing Protocol (ERP) . . . . . . . 4.2.5 Le transport de messages Dans JXTA . . . . . . . . . . 4.2.5.1 Le transport des messages sous TCP/IP . . . 4.2.5.2 Le transport de messages sous HTTP . . . . . 4.2.5.3 Le transport de messages sous TLS . . . . . . 4.2.6 Les mcanismes de dcouverte dans la plateforme JXTA 4.2.6.1 Dcouverte base sur le rseau local . . . . . . 4.2.6.2 La dcouverte par les invitations . . . . . . . . 4.2.6.3 La dcouverte en cascade . . . . . . . . . . . . 4.2.6.4 La dcouverte par les points de rendez-vous . . 4.2.7 Le Shell JXTA . . . . . . . . . . . . . . . . . . . . . . . 4.2.7.1 La syntaxe des commandes de JXTAShell . . . 4.2.7.2 Les commandes de base de JXTAShell . . . . . 4.2.7.3 Ajout des nouvelles commandes au JXTAShell 4.2.8 La scurit dans la plateforme JXTA . . . . . . . . . . . 4.2.9 Les Firewalls et les NATs . . . . . . . . . . . . . . . . . 4.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

5 Performance de la plateforme JXTA grande chelle 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Index distribu de partage de ressources (SRDI) . . . . . . 5.3 La recherche distribue dans le rseau JXTA . . . . . . . . 5.3.1 Les avantages des approches distribues . . . . . . 5.4 La recherche en largeur et la recherche en profondeur dans 5.4.1 La recherche en largeur . . . . . . . . . . . . . . . 5.4.2 La recherche en profondeur . . . . . . . . . . . . . 5.5 Larchitecture de la recherche JXTA . . . . . . . . . . . . 5.5.1 Les objectifs de JXTA search . . . . . . . . . . . . 5.5.2 Les composantes de JXTA search . . . . . . . . . . 5.5.3 Les services de JXTA search . . . . . . . . . . . . . 5.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . JXTA . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

58 58 58 59 60 60 60 61 61 61 62 64 66 67 67 68 69 69 70 70 70 70 70 71 71 73 73 73 73 73 74 74 74 74 75 75 75 75 76 76 77 77 79 79 79 80

6 La tlphonie Internet en mode P2P 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Gnralits sur la tlphonie IP . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Les phases de la transmission de la voix sur le rseau IP . . . . . . . . 6.2.2 Le protocole IP (Internet Protocol) . . . . . . . . . . . . . . . . . . . . 6.2.3 La tlphonie IP et le RTC . . . . . . . . . . . . . . . . . . . . . . . . 6.2.4 La pile des protocoles Internet multimdia . . . . . . . . . . . . . . . 6.2.4.1 La couche Physique . . . . . . . . . . . . . . . . . . . . . . . 6.2.4.2 La couche Internet . . . . . . . . . . . . . . . . . . . . . . . . 6.2.4.3 La couche transport . . . . . . . . . . . . . . . . . . . . . . . 6.2.4.4 La couche application . . . . . . . . . . . . . . . . . . . . . . 6.2.5 Real time Transport Protocol (RTP) et RTP control protocol (RTCP) 6.2.6 Le Protocole de rservation de ressource (RSVP) . . . . . . . . . . . . 6.2.7 Codage de la parole . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.7.1 Les techniques de codage . . . . . . . . . . . . . . . . . . . . 6.2.7.1.1 La technique temporaire : . . . . . . . . . . . . . . . 6.2.7.1.2 La technique paramtrique : . . . . . . . . . . . . . 6.2.7.1.3 La technique par analyse et synthse : . . . . . . . . 6.2.8 Codecs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Protocoles de signalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1 SIP (Session Initiation Protocol) . . . . . . . . . . . . . . . . . . . . . 6.3.1.1 Bref historique du protocole SIP . . . . . . . . . . . . . . . . 6.3.1.2 Fonctionnalits . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.1.3 Adressage et nommage . . . . . . . . . . . . . . . . . . . . . 6.3.1.4 Architecture de SIP . . . . . . . . . . . . . . . . . . . . . . . 6.3.1.5 Ouverture dune session . . . . . . . . . . . . . . . . . . . . . 6.3.1.6 Format des messages SIP . . . . . . . . . . . . . . . . . . . . 6.3.1.7 Exemple dune session SIP . . . . . . . . . . . . . . . . . . . 6.3.1.8 Limites de protocole SIP . . . . . . . . . . . . . . . . . . . . 6.3.2 Le protocole H.323 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3.2.1 ITU H.32x Famille des standards . . . . . . . . . . . . . . . 6.3.2.2 Constitution de H.323 . . . . . . . . . . . . . . . . . . . . . . 6.3.2.3 Exemple dune session H.323 . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

6.4

6.5 6.6

6.7

6.8

6.3.3 SIP ou H.323 ? . . . . . . . . . . . . . . . . . . . . Les Firewalls et les NATS . . . . . . . . . . . . . . . . . . 6.4.1 Protocoles de dcouverte des Firewalls et des NATs 6.4.1.1 STUN . . . . . . . . . . . . . . . . . . . 6.4.1.2 TURN . . . . . . . . . . . . . . . . . . . La tlphonie base sur le protocole SIP . . . . . . . . . . La tlphonie IP base sur une architecture P2P . . . . . 6.6.1 La registration . . . . . . . . . . . . . . . . . . . . 6.6.2 Architecture de P2P-SIP . . . . . . . . . . . . . . . 6.6.3 La registration dutilisateur . . . . . . . . . . . . . 6.6.4 Dfaillance dun nud . . . . . . . . . . . . . . . . 6.6.5 Localisation des utilisateurs . . . . . . . . . . . . . 6.6.6 Les messages O-line . . . . . . . . . . . . . . . . . Skype . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.7.1 Architecture de Skype . . . . . . . . . . . . . . . . 6.7.2 Les composantes software de Skype . . . . . . . . . 6.7.3 Les fonctions de Skype . . . . . . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

80 81 82 82 82 83 84 85 86 86 87 88 89 89 89 90 91 93 94 96

Conclusion gnrale et perspectives Bibliographie

viii

Liste des tableaux

1.1 1.2 6.1 6.2 6.3

Quelques actions dans les messages Napster . . . . . . . . . . . . . . . . . . . . 11 Comparaison entre les dirents systmes P2P . . . . . . . . . . . . . . . . . . . 30 La famille de protocoles H.32x . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Comparaison des protocoles SIP et H.323 . . . . . . . . . . . . . . . . . . . . . 81 Les boostaps super nuds dans Skype . . . . . . . . . . . . . . . . . . . . . . . 91

ix

Liste des algorithmes

1 2 3 4 5 6 7

Algorithme probabiliste de recherche et localisation des services Simple algorithme de recherche gnrale (Chord ) . . . . . . . . Algorithme de recherche avec des tables de raccourcis (Chord ) . Algorithme de recherche avec tolrance aux fautes (Chord ) . . . Algorithme de recherche de donnes (I4N ) . . . . . . . . . . . . Algorithme de stabilisation (I4N ) . . . . . . . . . . . . . . . . . Programme dajout dune nouvelle commande au Shell JXTA .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

16 21 23 24 36 37 55

x

Table des gures

1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 1.10 1.11 1.12 1.13 1.14 1.15 1.16 1.17 1.18 1.19 2.1 2.2 2.3 4.1 4.2 4.3 4.4 4.5 4.6 5.1 5.2 5.3 5.4

Taxonomie des systmes P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . Architecture de Napster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mcanisme de routage dans Gnutella . . . . . . . . . . . . . . . . . . . . . . . . Le mcanisme de recherche dans Gnutella . . . . . . . . . . . . . . . . . . . . . Problme de tolrance aux pannes dans Gnutella . . . . . . . . . . . . . . . . . Le routage dans lalgorithme de plaxton . . . . . . . . . . . . . . . . . . . . . . Le rseau virtuel au dessus du rseau physique . . . . . . . . . . . . . . . . . . Principe de base des fonctions de hachage . . . . . . . . . . . . . . . . . . . . . Interface dapplication pour les systmes P2P structurs bass sur les tables de hachage distribues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemple de recherche dans Chord . . . . . . . . . . . . . . . . . . . . . . . . . . Les tables de raccourcis (Fingers) dans Chord . . . . . . . . . . . . . . . . . . . Le routage dans Chord avec des tables de raccourcis . . . . . . . . . . . . . . . Procdure de Join dans Chord . . . . . . . . . . . . . . . . . . . . . . . . . . . Construction des tables de raccourcis (Fingers) dans chord . . . . . . . . . . . . Espace de coordonnes cartsiennes de dimensions 2 partag entre 6 nuds CAN (a) : espace de coordonnes cartsiennes avant que le nud F arrive, (b) : espace de coordonnes cartsiennes aprs que le nud F arrive . . . . . . . . . . . . . (a) : espace de coordonnes cartsiennes avant que le nud D quitte, (b) : espace de coordonnes cartsiennes aprs que le nud D quitte . . . . . . . . . . . . . Tous les chemins amnent Roman . . . . . . . . . . . . . . . . . . . . . . . . . Exemple de routage dans Pastry . . . . . . . . . . . . . . . . . . . . . . . . . .

10 11 13 14 15 17 18 20 20 21 22 22 23 24 25 26 27 27 28

La structure du rseau P2P (I4N) . . . . . . . . . . . . . . . . . . . . . . . . . . 34 La table de routage dun nud dans I4N . . . . . . . . . . . . . . . . . . . . . 35 Lvolution du systme I4N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Les oprations de base dun peer . . . . . . . . . . . Le resolver Service pour les requtes . . . . . . . . . Les Types de Pipes JXTA . . . . . . . . . . . . . . . La communication entre les peers. . . . . . . . . . . Larchitecture logique de la plateforme JXTA . . . . La communication P2P avec la prsence des rewalls La propagation des requtes dans le rseau JXTA . . La recherche en profondeur et en largeur dans JXTA Le recherche dans JXTA . . . . . . . . . . . . . . . . La recherche distribue dans la plateforme JXTA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 48 49 49 50 56 59 61 65 66

xi

6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 6.10 6.11 6.12 6.13 6.14 6.15 6.16 6.17 6.18 6.19

La transmission de la voix sur le rseau IP . . . La tlphonie IP et le RTC . . . . . . . . . . . La pile des protocoles Internet Multimdia . . Format des messages SIP . . . . . . . . . . . . Exemple dune session SIP . . . . . . . . . . . . Tests de performances de protocole SIP . . . . Constitution de H.323 . . . . . . . . . . . . . . Exemple dune session H.323 . . . . . . . . . . La tlphonie internet classique . . . . . . . . . La recherche et lenregistrement des utilisateurs La tlphonie IP en mode P2P. . . . . . . . . . La recherche et lenregistrement des utilisateurs Diagramme dun nud P2P-SIP . . . . . . . . Node startup and outgoing registration . . . . . Dfaillance dun super nud dans le DHT . . . La localisation des utilisateurs . . . . . . . . . . Les messages o-line . . . . . . . . . . . . . . . Architecture de Skype . . . . . . . . . . . . . . Organigramme de login dans Skype . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

69 70 71 77 77 78 80 81 83 84 84 85 86 87 88 88 89 90 92

xii

Remerciements

D

ABORD je tiens exprimer mes plus vifs remerciements mon promoteur, le professeur MEDDAHI Ahmed pour les

nombreux conseils, orientations et encouragements quil a su me prodiguer durant la ralisation de ce mmoire, ainsi que mon copromoteur Vanwormhoudt Gilles. Je remercie les membres du jury davoir accept de juger ce modeste travail. Je remercie M r TARI Kamel pour ses contributions lcole doctorale (ReSyd). Je remercie spcialement mon collgue Bouaissa Mohamed Abdelghani pour ses critiques sur le protocole I4N que jai propos dans le deuxime chapitre. Je dsire galement remercier mes collgues de lcole doctorale dinformatique (reseau et systme distribu Resyd 01 et Resyd 02 ) pour leurs soutien moral. Mes vifs remerciements sadressent aussi tous les professeurs de lintrieur et de lextrieur de lAlgrie, qui ont contribu dans notre formation de premiere anne magistre lcole doctorale dinformatique de luniversit Abderrahmane Mira de Bejaa. Mes remerciement sadressent aussi tous mes tudiants, qui mont encourags durant toute lanne. Merci tous qui ont contribu la ralisation de ce travail, de prs ou de loin. Novembre, 2005 AMAD Mourad

xiii

Rsum

Rsum : Populariss par dirents logiciels de partage et dchange de chiers, les systmes Pair Pair (peer-to-peer ou P2P ) reposent sur le principe de mutualisation de ressources (par exemple les donnes, les programmes, les services, les capacits de stockage et de calcul ) lchelle de lInternet. Le modle P2P est une alternative au modle client-serveur : Les peers sont tous au mme niveau, peuvent la fois orir (rle serveur ) et demander (rle client) des ressources. Ils peuvent librement rejoindre et quitter le systme (ou tomber en panne) et fournissent les ressources de manire intermittente. Dans ce contexte, on a propos un nouveau protocole (I4N ) de dcouverte et localisation de services en mode P2P. Le modle P2P semble particulirement intressant pour les systmes dinformation rpartis grande chelle, qui sont par nature, htrognes et instables. Plusieurs types dapplications commencent se migrer de larchitecture client- serveur vers larchitecture P2P, comme la tlphonie IP. Ces dirents protocoles sont incapables dinterchanger des informations entre eux, pour cela, direntes plateformes P2P ont t mise en uvre, JXTA a pris une grande partie dans ce mmoire. Mots cls : P2P, protocole de routage, Plateforme P2P, JXTA, La telephonie Internet, I4N.

Abstact : Popularized by various softwares of sharing and exchange of les, the systems Peer to Peer (P2P ) are based on the principle of mutualisation of resources (par example data, programs, services, capacities of storage and calculation ) on the scale of the Internet. The model P2P is an alternative to the client-server model : The peers are all on the same level, can at the same time oer (role server ) and to ask (role customer ) of the resources. peers can freely join and leave the system (or to break down ) and provides the resources in manner intermittent. In this context, we have proposed a new protocol (I4N ) for the discovery and localisation of services in P2P model. The model P2P seems particularly interesting for the information systems distributed on a large scale, which by nature, are heterogeneous and unstable. Several type of applications starts to be migrated of architecture client server towards architecture P2P, as telephony IP. These various protocols are unable to interchange information between them, for that, dierent plateforms P2P were implemented, JXTA take a great part in this thesis. Keys Words : P2P, routing protocols, P2P plateform, JXTA, Internet telephony, I4N.

xiv

Introduction Gnrale

D

E nos jours, on constate une augmentation des capacits de stockage, des puissances de calcul des processeurs, des dbits des rseaux, du nombre dutilisateurs connects Internet et de la quantit de donnes hberges par les utilisateurs. Les questions qui peuvent tre poses sont : Comment construire un systme ayant pour but de stocker des donnes grande chelle ? ou qui peut faire des calculs qui consomment beaucoup de temps ? Comment faire pour quil soit robuste, extensible et peu coteux ? Comment trouver ces donnes travers Internet ?. A travers ce mmoire on va essayer de rpondre ces direntes questions. Le terme Pair Pair (P2P ) fait rfrence une classe de systmes ou dapplications qui utilisent les ressources distribues pour raliser une opration dune manire dcentralise. Un systme P2P ne dispose daucune structure centralise pour raliser ses objectifs. Depuis quelques temps, les systmes pair pair font lobjet dune attention considrable, en raison de leur architecture sous-jacente, particulirement adapte au passage lchelle des applications distribues que lon trouve sur internet. Dans un systme pair pair, il ny a aucun contrle centralis, ni aucune organisation hirarchique. Chaque pair est quivalent en fonctionnalit et coopre avec dautres pairs dans lobjectif de raliser une tache collective. Les systmes pair pair ont volu depuis le simple systme de partage de chiers comme Napster, jusquaux systmes volus de gestion de donnes distribues comme Seti@home. La caractristique fondamentale dun rseau P2P est quil permettre linterconnexion (logiquement) dun ensemble dutilisateurs de faon privilgie an que ceux ci puissent mettre en commun des donnes ou des calculs. La dicult de conception des systmes P2P provient de lextreme volatilit des utilisateurs qui se connectent et se dconnectent volont. Les utilisateurs des rseaux P2P eectuent de nombreuses requtes de recherche dans le rseau, les rponses ces requtes doivent tre donnes dans des

1

Introduction gnrale

2

dlais aussi brefs que possible. De nombreuses propositions ont t faites dans la littrature pour la construction des rseaux Pair Pair, mais quelques prototypes seulement qui ont t implements. Notre mmoire est organis en six chapitres comme suit : Dans le premier chapitre, on a dcrit les dirents protocoles P2P, leurs architectures et leurs caractristiques. On les a regroup suivant deux grands types : les rseaux structurs comme Chord, CAN, Pastry qui sont bass sur les tables de hachage distribues et les rseaux non structurs comme Napster qui est bas sur un index global et Gnutella dont laquelle la recherche est base sur la technique de diusion (Flooding). On a conclu le chapitre par une comparaison entre ces dirents protocoles P2P suivant plusieurs critres comme la scalabilit, la dcentralisation, le cot de recherche et la tolrance aux fautes. Dans le deuxime chapitre on a propos un nouveau protocole de localisation de ressources en mode P2P. I4N pour Internet Quatre Niveaux. Le protocole I4N repose sur une topologie virtuelle en anneaux imbriqus, il appartient aux protocoles de la troisime gnration (rseaux structurs). Dans le troisime chapitre, on a fait un survol sur les direntes plateformes P2P largement utilises comme XtremWeb, ProActive et JXTA. Dans le quatrime chapitre, on a tudi la plateforme open source JXTA dveloppe par SUN Microsystem. JXTA est dnie comme tant un ensemble de protocole P2P gnraliss et open sources qui permettent de faire communiquer nimportes quelles appareils dans le rseau (PDA, PC, Serveur,...). Elle est indpendante des protocoles de transport (TCP/IP, HTTP,...) et des systmes dexploitation (Windows, Linux, ...), ainsi que des languages de programmation (Java, C/C++, Perl,...). Le cinquime chapitre est consacr ltude de performances de la plateforme JXTA et lextensibilit de la recherche et la localisation de services dans les rseaux P2P grande chelle. Le sixime chapitre est consacr la tlphonie IP en mode P2P. Nous avons commenc par une introduction sur quelques protocoles de signalisation comme H.323 et SIP pour arriver dtailler deux grandes approches de la tlphonie IP en mode P2P. La premire est Skype, un protocole P2P propritaire qui est mis en oeuvre et qui est en augmentation continue dutilisateurs ces dernires annes. La deuxime est une architecture de la tlphonie IP en mode P2P pur base sur le protocole SIP pour la signalisation.

Introduction gnrale

3

Enn, notre mmoire sachve par une conclusion gnrale rsumant les grands points qui ont t abords dans ce mmoire, ainsi que des perspectives que lont souhaite accomplir prochainement.

Chapitre I

Dcouverte et localisation de services en mode P2P

1.1

Introduction

Les systmes pair pair (P2P ) constituent une plateforme rcente pour excuter des applications reparties dans des environnements grande chelle. Contrairement lapproche Client-Serveur, les nuds sont connects entre eux directement au dessus du rseau physique. Ces systmes permettent de partager les ressources et les services entre les dirents nuds, tels que : Le contenu de leurs disques durs, largeur de bande passante et leur CPU. Cela permet davoir une trs grande mmoire darchivage, des bons rsultats de recherche et une puissance de calcul plus accrue que nimporte quel utilisateur aurait pu avoir individuellement. Dans ce type de systmes, les nuds peuvent se comporter la fois comme client et serveur. En restant autonome, chaque ordinateur prend part du rseau global indpendamment de son type de connectivit. Les peers ne ncessitent pas obligatoirement une adresse IP permanente, contrairement aux serveurs dans les architectures client-serveur qui doivent avoir une adresse IP permanente [50]. Les systmes P2P sont devenus une forme commune dinterchangement on-line des donnes [61]. Ils sont par nature distribus, sans aucune organisation hirarchique ou contrle centralis. Le problme fondamental qui confronte les applications peer-to-peer est la recherche et la localisation des nuds qui stockent des donnes particulires [60], loptimisation du nombre de messages traverss dun peer un autre pour maintenir la 4

Chapitre 1 : Dcouverte et localisation de services en mode P2P

5

stabilit du systme, ainsi que pour la recherche de donnes, cest le cur de chaque systme P2P. Il y a deux grandes classes des rseaux P2P : structur et non structur. Dans les rseaux non structurs (ex : Napster, Gnutella,...) la recherche se fait par inondation. Linconvnient majeur est la dicult de trouver les cls (donnes) recherches sans utiliser largement les requtes distribues, pour cette raison les systmes P2P non structurs sont considrs inscalables [62]. Dans les rseaux structurs, les donnes sont stockes dans des emplacements bien dnis et par consquent la recherche revient trouver ces emplacements par la mme mthode de stockage (ex : Chord, Can, Pastry, Tapestry,...). Le problme de scalabilit nest pas pos dans ce type de systmes. De nombreuses approches permettent de construire un rseau reposant sur le paradigme pair pair (P2P ), structur ou non, ont rcemment mergs. Ces approches forment des systmes distribus de grande taille et amliorent lecacit de ces rseaux grande chelle.

1.2

Les rseaux peer-to-peer

Le rseau P2P est un rseau logique qui utilise un rseau physique. Le peer-to-peer est pour beaucoup de personnes synonyme de "partage de chiers", cette ide prconue donne une mauvaise image de ce domaine. En gnral, le terme P2P dcrit un environnement o les machines communiquent entre elles sans lutilisation dun point de contrle centralis pour router le trac de donnes [67]. Avec les rseaux peer-to-peer, les ordinateurs partagent les donnes et les ressources, en communiquant directement entre eux sans utiliser un serveur central. Quelques observateurs dindustrie disent que les rseaux peer-to-peer deviennent une technologie rseau signicative [6].

1.2.1

Les applications Peer-to-Peer

Il y a plusieurs types dapplications peer-to-peer quon peut les regrouper en quatre grandes classes : le partage de chiers , collaboration, traitement distribu et la communication. Partage des chiers (File Sharing) Les systmes dchange de chiers sont parmi les premiers avoir fait dcouvert


6

le concept du P2P. Ces systmes permettent le partage direct des documents de natures direntes (texte, multimdia, image, ...) comme Napster, Gnutella, Freenet, ... Le calcul distribu (distributed computing) Le calcul distribu est probablement le domaine qui peut tirer les grands bnces dune architecture P2P. Un problme qui peut tre dcomposable et paralllisable, cest--dire divis en plusieurs parties susceptibles dtre rsolues dune manire quasi-simultane par plusieurs units, sera plus protant de le faire sur une architecture P2P [12]. Dans ce type dapplications, les peers cooprent pour raliser le traitement dsir. Ce type dapplications permet lutilisation des ressources des ordinateurs non exploites, tels que la puissance du processeur ou lespace de stockage du disque dur. La mise en commun de celles-ci peut servir pour le fonctionnement de plus grosses applications, impliquant un cot dexploitation lev. Certains experts estiment que 80% 90 % de la puissance processeur des ordinateurs est non exploites. Seti@Home (1999) qui sinscrit dans un projet amricain de recherche dintelligence extraterrestre est un exemple dapplications P2P bas sur le traitement distribu. Communication Elle regroupe la messagerie instantane (AOL, ICQ, MSN Messenger, Yahoo Messenger,...), la tlphonie par Internet (WebPhone, Skype,...), ainsi que la vidoconfrence (CUseeME,...). Collaboration Celle-ci est la moins connue, elle regroupe les applications de groupeware tels que Groove Network qui facilite le travail en-ligne.

1.2.2

Les aspects des rseaux P2P

Les rseaux P2P sont caractriss par plusieurs aspects : Scalabilit Le nombre dutilisateurs dans les rseaux P2P peut augmenter dune manire imprvisible. Un systme P2P doit pouvoir grer un tel nombre dutilisateurs. Tolrance aux fautes Cest la capacit des systmes de continuer fournir des services dune manire rgulire malgr la prsence des fautes dans le software ou le hardware, ainsi que les arrives et les dparts frquents des nuds [58]. En gnral la dcentralisation


7

rend les systmes P2P robustes aux fautes. Scurit Cest la capacit des systmes de grer et de protger des informations sensibles. Plusieurs dnitions du mot scurit existent. Une approche pour dnir ce mot est de le dnir en terme de services qui peuvent tre fournis. Les services de scurit les plus appropris la couche rseau de modle OSI sont : la condentialit, lintgrit, lauthentication et la non repudiation avec preuve de lorigine de donnes. Dnition 1. La condentiali de donnes est la proprit par laquelle linformationnest pas rendue disponible ou nest pas releve aux individus, aux entits ou aux processus non autoriss [55].

La condentialit peut tre assure en utilisant les algorithmes de cryptographie asymtrique comme RSA ou les algorithmes de cryptographie symtrique comme AES et DES. Dnition 2. Lintgrit de donnes est la proprit par laquelle les donnes nont past changes, dtruites ou perdues dune faon non autorise ou accidentelle [55].

Lintgrit de donnes est assure par les fonction de hachage, comme titre dexemple : MD4, MD5 (Message Digest), SHA-1(Secure Hash Algorithm 1) ou SHA-2 . Dnition 3. Lauthentication de lorigine des donnes garantit que les donnes reues proviennent de lexpditeur dclar [55].

Dnition 4. La non repudiation avec preuve de lorigine de donnes fournit au destinataire une information qui peut tre utilise comme preuve de lorigine des donnes recues. Elle protege ainsi le destinataire contre une tentative de nier lenvoi de donnes par lorigine [55].

La non repudiation peut tre assure par les signatures digitales ou les certicats cl publique. Au dbut, les systmes P2P nont pas implment les mcanismes de scurit, mais


8

la communaut des chercheurs est de plus en plus attire vers ce problme [58]. Dans larchitecture Client-Serveur, les serveurs sont des points faibles dans le rseau (cot scurit), car ils sont peu nombreux, trs chargs et facilement identiables, cela les rend vulnrables des surcharges des requtes quelles aient une cause naturelle ou lie une attaque de type dni de service (envoi dun nombre important de requtes simultanment an de rendre un serveur inutilisable). Anonymat Elle est dnie comme tant le degr pour lequel les systmes P2P tiennent compte des oprations non identies [58]. Dynamisme Les systmes P2P doivent supporter le dynamisme, cest--dire les ressources comme par exemple les peers, peuvent joindre ou quitter le systme de manire continue, sans quils aectent le fonctionnement de ce dernier. Dcentralisation Il ny a pas un contrle centralis, ni une vue globale de tous les peers dans le rseau. La majorit des systmes P2P ne sont pas purement distribus, mais ils sont hybrides. Connectivit ad Hoc Pour permettre dtablir une communication sans aucune architecture prexistante, car les systmes P2P visent faire communiquer les dirents nuds dans les dirents types de rseaux (rseau laire, mobile, ad hoc). Robustesse La robustesse doit tre maintenue dans les trois composantes des systmes P2P suivantes : scurit, lagrgation des ressources et la abilit.

1.2.3

Les obstacles du rseau P2P

Parmi les problmes des rseaux P2P on trouve : Scurit Lutilisation des logiciels de partage de chiers P2P peut soulever des problmes srieux de scurit [56]. Les applications P2P permettent aux ordinateurs laccs direct aux autres ordinateurs, donc leurs dispositifs du stockage, par consquent,


9

la scurit sera touche. Le tlchargement des documents partir dautres systmes rend ces derniers exposs aux virus. La deuxime raison est que les machines sont incapables dauthentier les identits des machines avec lesquelles elles communiquent [6]. A un moment donn, un simple peer peut devenir un serveur pour un autre peer, mais il ne pourra pas remplir tous les aspects de scurit fournis par les serveurs. La scalabilit et la tolrance aux fautes dpendent de nombre de peers dans le rseau et de leurs interconnexion, par contre, la scurit dpend de la nature ouverte des systmes P2P et de linfrastructure de transmission, car nimporte quel peer peut entrer en contacte avec les autres [58]. Interoprabilit Dans les rseaux P2P, Les applications utilisent direntes technologies rseaux ainsi que direntes plateformes. Le fait que plusieurs plateformes puissent cohabiter au sein de celles-ci, avec dirents systmes de scurit, rend linteroprabilit dicile. Aujourdhui, les services des systmes P2P sont relativement simples comme le transfert de chiers musicaux, mais dans le futur a ne sera pas le cas. Bande passante Parce que les utilisateurs des rseaux P2P dans le monde ne cessent daugmenter, le trac caus par ce type de systmes peut saturer le rseau P2P. La dcouverte des ressources Comme il n y a pas de serveurs dans les rseaux P2P, ainsi que les adresses IP ne sont pas toujours permanentes, lutilisation dun bon algorithme de dcouverte et localisation des ressources est indispensable [6].

1.2.4

Les systmes bass sur la technologie P2P et leurs classications

Les systmes P2P peuvent tre classis suivant le type de recherche utilis, la maintenance et lorganisation de la structure du rseau comme il est montr sur la gure 1.1. Dans les architectures structures, le systme correspondant est organis suivant une topologie virtuelle connue, comme titre dexemple (Chord (Anneau), CAN(Tore),...). Dans les architectures non structures, la topologie virtuelle et la topologie physique sont les mmes. Dirents protocoles dans les deux types darchitectures sont dcrits dans [41].


10

Les protocoles P2P Recherche Exhaustive Renseign Structure Organis Non Organis

Fig. 1.1 Taxonomie des systmes P2P

1.2.5

Le futur des rseaux P2P

Laugmentation gnralise des lignes haut dbit tablissant le peer-to-peer comme un vritable moyen de communication sur internet, elle va permettre lapparition de la tlphonie et de la vidoconfrence de bonne qualit. Pour raliser les pleins avantages des applications P2P, nous devons tablir une infrastructure de calcul [30].

1.3

Rseaux non structurs

La premire grande classe est les systmes P2P non structurs, ceux-ci reposent sur une construction alatoire du graphe de connexion, un nud joint le rseau par lintermdiaire dun autre nud dj connect. La recherche des services dans un tel rseau se fait gnralement selon la technique dinondation : Un nud dsirant localiser une ressource r demande ses voisins sils connaissent cette ressource, leurs tours, ses voisins demandent leurs voisins sils ont des connaissances de cette ressource r et ce, jusqu une profondeur xe par le systme. Le nud possdant la ressource r renvoie une rponse qui parcourt le chemin initial dans le sens inverse.

1.3.1

Napster

Cest lun des plus vieux et plus clbres des systmes P2P, il est destin pour le partage de chiers musicaux. Cest un systme P2P hybride dont lequel la recherche de services est centralise. Dans Napster, les utilisateurs ont recours un serveur central possdant lindex de tous les utilisateurs connects, ainsi que leurs donnes partages. Le serveur se charge de mettre en relation un peer demandeur avec un peer possdant les chiers dsirs. Le stockage des chiers demeure sur les machines utilisateurs. Le processus de transfert seectue directement entre les peers sans passer par le serveur central. Lavantage principal de Napster est la localisation rapide et ecace, par contre, elle prsente un inconvnient majeur, qui est la rsistance aux pannes. La gure 1.2


11

prsente larchitecture gnrale de Napster.

Rponse Requte

Tlchargement Serveur Client

Fig. 1.2 Architecture de Napster

1.3.1.1

La structure de messages Napster

Les messages de Napster sont composs de trois parties : Longueur (16 bits) type (16 bits) donnes...

Longueur : Cest la taille du bloc de donne en octets. Type : laction raliser. Le tableau 1.1 dcrit quelques actions dans les messages Napster. Donnes : Chane ASCII. Type 0 2 3 4 5 6 7 8 9 10 14 110 ... Code 0000 0200 0300 0400 0400 0600 0700 0800 0900 0A00 00E0 60E0 ... Description Error message Login Login Ack Version Check Auto upgrade New user login Nick check Nick not regist Nick already regist invalid nick Login options Unchare all les ...

Tab. 1.1 Quelques actions dans les messages Napster


12

1.3.2

Gnutella

Contrairement Napster, Gnutella est un protocole de recherche P2P dcentralis. Il a pris la suite en rsolvant le problme de centralisation de Napster. Lors dune recherche, le peer envoie la requte ses voisins, qui font de mme et ainsi de suite, jusqu atteindre les nuds distance 7 du demandeur, cette distance est lquivalent du nombre de sauts maximal dune requte HTTP [23]. Linconvnient majeur est que la recherche nest pas exhaustive (la requte peut chouer mme si la donne recherche est prsente dans le systme). 1.3.2.1 La structure de messages Gnutella

Tous les messages Gnutella ont un entte commun de la forme suivante : Identicateur de message (16 octets) Type de message (1 octet) (1 octet) TTL Sauts dja accomplis (1 octet) Longueur de message qui suit (4 octets)

Avec : Lidenticateur du message : Pour identier les messages Gnutella. Type : Cest laction raliser parmi les suivantes : Ping, Pong, Query, Query Hit, Push, Bye. TTL : Le nombre de sauts non encore raliss. Sauts : Le nombre de sauts raliss. 1.3.2.2 Les principaux messages utiliss dans le protocole Gnutella

Ping [0x00] : Il est utilis pour dcouvrir les autres servents (Serveur-Client) sur le rseau. Un servent qui reoit un Ping doit rpondre avec un ou plusieurs Pong. Pong [0x01] : Cest la rponse un Ping, elle contient ladresse IP et le numro du port du servent, ainsi que le nombre et la quantit de donnes partages. Avec : Port : Le port sur lequel le pair est en attente. Adresse IP : Ladresse IP par laquelle le pair est atteignable. Query [0x80] : Est utilis pour la recherche dun chier, il a la forme suivante : Vitesse minimum des servents Critres de recherche


13

Avec : Vitesse : Dbit minimum pour quun pair rpond (ko/s) Critre : Chane de caractres termine par 0x00. Query Hit [0x81] : Pour la rponse une requte Query. Push[0x40] : Permet de tlcharger des donnes depuis un servent situ derrire un rewall . Si les deux servents sont derrire des rewalls, le tlchargement est impossible [24]. Bye : Pour quitter. 1.3.2.3 Mcanisme de routage

Un nud (peer ) se connecte sur le rseau Gnutella, il commence par rechercher tous les nuds Gnutella prsents, pour cela il transmit une trame didentication (ping) tous ses voisins qui eux-mmes le transmettons leurs voisins. Ces envois sont encapsuls dans une trame TCP. Le mcanisme de recherche joue sur le TTL (Time To Live) de la trame pour borner le nombre de sauts des messages. A chaque nud du rseau, le TTL est dcrment et lorsquil devient gal zro, la retransmission est stoppe. Un mcanisme permet dviter les boucles causes par les transmissions successives, lorsquune trame est reue, elle est stocke pendant un court laps du temps. Si le nud reoit pendant ce laps du temps une trame identique, il la rejette, car elle est dj traite. Lorsquun nud est identi, il envoie lmetteur une trame de rponse (pong). La gure 1.3 met en evidence le mcanisme de routage dans Gnutella.

D C B A TTL=1

TTL=2 TTL=3 X I TTL=2 TTL=1 K J H TTL=2

E TTL=1 F

G

Fig. 1.3 Mcanisme de routage dans Gnutella


14

1.3.2.4

Recherche de donnes

Le nud X cherche la donne D1, il transmit sa requte vers ses voisins, si un voisin ne possde pas la donne recherche, il continue de transmettre la requte vers ses voisins et ainsi de suite, jusqu lexpiration de la requte (TTL=0 ). Tous les nuds qui ont reu la requte et qui possdent la donne, la retransmettent. Le nud qui a mis la requte utilise le protocole HTTP pour tlcharger les donnes trouves. Le cot de la recherche dans Gnutella est O(n) ce qui limite la scalabilit dans ce systme [22]. la gure 1.4 met en evidence le mcanisme de recherche dans Gnutella. Dans lexemple dcrit sur la gure 1.4, le nud X recherche la donne D1, il envoie

D C B A Rech D1

Rech D1 Rech D1 X Resul G,K Rech D1 Rech D1 K Resul K J H I Resul G

E F Rech D1 Resul G

Resul K

Rech D1

G Liens entres les noeuds Requte Rponse

Fig. 1.4 Le mcanisme de recherche dans Gnutella une requte Query tous ses voisins, aprs lexpiration de TTL (TTL = 0 ), la donne est trouve dans les nud K et G, ces derniers rpondent par des Query Hit, le nud X envoie un Push aux deux nuds K et G en utilisant leurs adresses IP retournes dans Query Hit. Lavantage principal du protocole Gnutella est la simplicit du mcanisme de routage utilis, qui est bas sur linondation (diusion) : Envoi de la requte tous les voisins, puis tous les voisins de tous les voisins, etc, distance borne an de ne pas saturer le rseau. Linconvnient majeur est que la recherche nest pas exhaustive, cest--dire quune recherche sans rponse ne signie pas que la donne cherche nexiste pas dans le rseau, mais simplement elle nest pas trouve.


15

1.3.2.5

La tolrance aux pannes

Dans le protocole Gnutella, les nuds ne gardent que les liens avec leurs voisins dans leurs tables du routage, cela prsente un inconvnient majeur lors dune dconnexion involontaire (dfaillance). Si par exemple dans la gure 1.5, le nud E quitte involontairement le rseau, alors ce dernier sera divis en trois parties, qui ne sont pas relies entre elles.D C B A A B C D

E F X I X I F

G J H J H

G

K

K

Fig. 1.5 Problme de tolrance aux pannes dans Gnutella

1.3.3

Les protocoles probabilistes

Menasc [33][34] propose un protocole probabiliste de localisation de services dans les rseaux P2P. Soit s le peer qui met la requte (source) et soient les notations suivantes : r : M(a,b,c) : Le peer r reoit le message M avec les paramtres a,b,c. [X]p : Executer X avec la probabilit P. Et soient les deux fonctions suivantes : SearchRequest(s, res, rp, TTL) : Requte met par la source s pour localiser les ressources res, le message ne peut propager au maximum TTL peers, rp est la squence des peers qui ont reu le message, cette squence sera utilise dans le chemin inverse ramenant la source. RessourceFound(s, res, rp, v) : Indique que la ressource res cherche par la source s est trouve sur le peer v, le chemin amenant la source s est rp. Quand un peer reoit une requte SearchRequest, il cherche en premier lieu dans son rpertoire local (LC), ensuite dans son rpertoire de cache (DC). Si la ressource est trouve dans son rpertoire local, il envoie le message RessourceFound par le chemin


16

inverse parcouru par la requte SearchRequest jusqu atteindre la source s. Ce message met jour les DCs de chaque peer visit. Si la ressource est trouve dans le DC, un message SearchRequest est envoy au peer point par le DC. Si un peer ne trouve pas la ressource, ni dans son rpertoire local, ni point dans son DC, il envoie la requte tous ses voisins avec une certaine probabilit P. Algorithm 1 Algorithme probabiliste de recherche et localisation des services 1 : debut 2 : r : SearchRequest( source, res, (s1,s2,...sm),TTL) 3 : Si (res est dans LC) alors 4 : Envoyer RessourceFound(source, res, (s1,s2,...sm-1), r) sm 5 : Sinon 6: Si (res, loc) est dans DC alors 7: Envoyer la requte au peer point dans DC 8: Envoyer SearchRequest (source, res, (s1, ...sm, r), TTL-1) loc 9: Sinon 10 : Si (TTL > 0) alors 11 : Pour chaque peer voisin faire 12 : Envoyer [SearchRequest(source, res, (s1, ...sm, r), T T L 1)]p 13 : r : RessourceFound (source, res, (s1,...,sm), v) 14 : Si (r source) alors 15 : Envoyer RessourceFound (source, res, (s1,...sm-1), v) sm 16 : Ajouter (res, v) dans DC 17 : Sinon // La ressource est trouve 18 : Tlcharger la ressource res de peer v. 19 : Fin

1.3.4

Lalgorithme de Plaxton

Plaxton [44] propose un algorithme de localisation de ressources et de routage dans un environnement compltement distribu. Le nommage des objets et peers est construit de manire alatoire selon une fonction de hachage unique et connue. Chaque identicateur possde une longueur xe. Il est crit dans une base identique pour les objets et les peers. Chaque peer P maintient une table de routage de plusieurs niveaux. Chaque niveau N de la table contient une liste de voisins de P , dont les N premiers chires sont communs ceux de P , Dans la gure 1.6 chaque nud possde un identiant crit sous forme hexadcimale dune longueur de quatre chires. Le nud didentiant 0325 fait parvenir un message un nud didentiant 4598, il va alors consulter le premier niveau de sa table de routage et y cherche un voisin dont le dernier chire est 8 (ici


17

le nud B4F8 ), puis lui faire suivre ce message. A son tour, ce dernier va consulter le second niveau de sa table de routage et cherche un voisin dont lidentiant se termine par 98 (ici 9098 ) et lui faire suivre le message. Ce processus se rpte jusqu atteindre le nud considr. Cette mthode de routage garantit quun nud prsent dans un systme de N peers peut tre joint en lnb (n) itrations, avec b la base des identiants.

B4F8 N1 N1 N1 0325 N2 9098 N1 7598 N1 87CA 4598 N1 D598 2118 N1 N1 2BB8 0098 N1 N1 1698 3E98 N1 N4 N3

0 xxx0 xx05 x025 0325

1 ......... xxx1 xx15 x125 1325

E xxxE xxE5 xE25 E325

F xxxF xxF5 xF25 F325

Fig. 1.6 Le routage dans lalgorithme de plaxton

1.4

Rseaux structurs

La deuxime grande classe est celle des rseaux P2P structurs, ils sont dits structurs, car au dessus du rseau physique sous-jacent, les nuds sont relis par un rseau recouvrant construit sous certaines contraintes, rpondant plusieurs proprits et connectant les peers selon une structure particulire donne (Anneau (Chord)[59], Espace de coordonnes cartsiennes (CAN) [48]). Les mthodes de routage et localisation dployes dans ce type darchitectures P2P consistent organiser la topologie virtuelle en vue de la faire correspondre une topologie connue (hypercube, anneau, tore,...). Chaque topologie prsente des mthodes de nommage, routage et localisation qui lui sont propre. Les principales tudes sont bases sur les tables de hachage distribues (Distributed Hash Table). Lavantage principal de ces topologies est quelles garantissent de trouver la donne une fois elle est prsente dans le systme [2].


18

1.4.1

Le protocole chord

La base de protocole Chord [59] est le protocole de Plaxton. Chord repose sur une topologie en anneau. Un nud Chord la connaissance de son prdcesseur et de son successeur. Une fonction de hachage rgulire gnre une cl pour chaque nud partir de son adresse IP, ensuite chaque nud est plac dans lanneau de manire ordonner les cls par ordre croissant, ainsi chaque nud est responsable de lintervalle [cl (nud actuel), cl (nud suivant) [. La cl K est assigne au premier nud dont son identicateur est suprieur ou gal K dans lespace des identicateurs. La localisation de donnes peut tre implmente facilement dans le protocole Chord par lassociation de cl pour chaque donne et la sauvegarde du pair (Cl/Donne) dans le nud responsable de cette cl [59]. 1.4.1.1 Le rseau virtuel

Chord repose sur une topologie en anneau. Le prdcesseur dun nud et son successeur dans le protocole Chord ne sont pas ncessairement adjacents dans le rseau physique, comme il est montr sur la gure 1.7.

Rseau virtuell (Chord)

Internet

Rseau physique

Fig. 1.7 Le rseau virtuel au dessus du rseau physique

1.4.1.2

Lidenticateur du nud

Les systmes P2P structurs utilisent les tables de hachage distribues pour obtenir des identicateurs de donnes et de nuds dune manire unique dans le rseau. Les cls peuvent tre obtenues par le hachage des noms de donnes et les identicateurs des nuds par le hachage de leurs adresses IP [10]. Dans Chord, les identicateurs se construisent de la mme manire pour les donnes et les nuds, ils sont de la forme h(x) avec h est la fonction de hachage comme par exemple SHA-1(Secure haching


19

Algorithm) et x est ladresse IP du nud concatne avec un index dun nud virtuel entre zro et une valeur maximale. 1.4.1.3 Le hachage consistent (Cohrent)

Les algorithmes de hachage utilisent des fonctions de hachage H, pour mettre les cls correspondent aux donnes dans leurs emplacements. H : K L, o K est lensemble de toutes les cls et L est lensemble de tous les emplacements. La cl est un identicateur unique qui reprsente la donne. Les algorithmes usuels de hachage localisent les donnes en un temps constant par exemple O(ln(k)) o k est le nombre de cls dans la table de hachage. Le hachage consistent assigne chaque nud (ou donne) un identicateur de m bits (Chord utilise 128 bits) en utilisant une fonction de hachage comme SHA-1. La longueur m de lidenticateur doit tre susamment grande pour que la probabilit davoir la mme cl pour deux entits direntes par la mme fonction de hachage soit ngligeable. Avec m bits, la plage dadressage sera [0, 2m [ et donc (2m 1) valeurs direntes. Le hachage consistent permet aux nuds de joindre et de quitter le rseau avec un minimum de changement de cls, il permet donc lquilibrage de charge [60]. Chaque nud reoit presque le mme nombre de cls et donc les ressources sont uniformment distribues sur les nuds [15]. Pour maintenir la correction des successeurs, quand un nud N rejoint le rseau, certaines cls qui sont assignes au successeur de N seront assignes au nud N . Quand un nud P quitte le rseau, toutes ses cls seront assignes son successeur et donc les changements dattribution de cls lors darrive et de dpart des nuds sont petits. Avec une probabilit leve, quand un nud rejoint ou quitte le systme, uniquement O(1/N ) fraction de cls qui sera transfre vers dirents nuds. Les tables de hachage distribues sont des bonnes fondations pour les algorithmes de recherche et de localisation de services en mode P2P, car elles nimposent aucunes contraintes sur la structure des cls de donnes [2]. La gure 1.8 illustre le principe des fonctions de hachage. Un exemple de fonction de hachage est SHA-1, elle peut hacher un nombre arbitraire de donnes en L = 2160 emplacements dirents . Les fonctions de hachage doivent permettre de hacher des cls similaires en des emplacements dirents [61], par exemple dans la gure 1.8, lemplacement de H( peer ) est indpendant de lemplacement de H( peers ). Les oprations de base que doivent implementer les interfaces dapplications avec les tables de hachage distribus (gure 1.9) peuvent tre rsumes dans put(key, value), get(key), remove(key).


20

Pgm Peers 1 H (Chord)

Peer Food 2

Chord Napster L

Fig. 1.8 Principe de base des fonctions de hachage

Application P2P structureAPI Interface Put (Key, Value) API Interface Remove (Key) API Interface Value = Get (Key)

Value

Table de hachage distribu (DHT)

Peer

Peer

Peer

Peer

Fig. 1.9 Interface dapplication pour les systmes P2P structurs bass sur les tables de hachage distribues

1.4.1.4

Placement des ressources

La cl K, identicateur de ressource est gnre par le hachage du nom de la ressource (hash(ressource) = K), K est ensuite place sur Successeur (k) qui est le nud didenticateur immdiatement suprieur ou gal K. 1.4.1.5 Recherche de donnes

Chord prsente un algorithme de recherche de donnes simple, il permet la recherche dune manire exhaustive, cest--dire quil garantit la localisation de ressources si elles sont prsentes dans le systme. 1.4.1.6 Exemple de recherche

Dans la gure 1.10, la cl K16 est localise dans le nud N21 et la cl K54 dans le nud N56. La simple connaissance du prdcesseur et du successeur permet certes de construire une topologie en anneau, mais elle prsente des performances mdiocres en terme de nombre de nuds parcourir pour acheminer une requte, cette valeur


21

Algorithm 2 Simple algorithme de recherche gnrale (Chord ) 1 2 3 4 5 6 7 8 : : : : : : : : Rechercher (mon-id,cl-id) Dbut N N C->G->K->O->N C->D->H->G->K->J->N C->G->F->J->N C->G->K->O->N C->D->H->L->P->O->N C->G->K->J->N C->G->K->O->N C->D->H->L->K->O->N C->G->K->O->N C->D->H->L->K->J->N C->D->H->G->K->O->N C->D->H->G->F->J->N ..............


28

1.4.3

Pastry

Pastry [49] est un rseau recouvrant purement dcentralis, scalable et sautoorganise en anneau. Chaque nud ou donne dans Pastry un identicateur unique de 128 bits obtenu dune manire alatoire lors de la premire entre dans le systme, en basant sur son adresse IP ou sa cl publique et en utilisant un mcanisme de cryptographie et de hachage. Ce mcanisme permet de gnrer des identicateurs uniformment distribus sur lespace des identicateurs. Pastry est bas sur un mcanisme de routage fond sur la notion de prxe/suxe. Pasty assigne alatoirement chaque nud du rseau un identiant unique de n bits compris entre 0 et 2n 1 (typiquement n =128 ). Lespace dadressage est considr circulaire, ainsi lidentiant 0 est le successeur de lidentiant 2n 1. Pastry associ aux donnes des cls de la mme manire que pour les nuds. La recherche dune donne de cl K revient rechercher le nud dont son identicateur est numriquement plus proche de celui de la donne K. Lalgorithme de routage utilis dans Pastry est driv de lalgorithme de Plaxton [44], il consiste router le message de proche en proche vers les nuds qui partagent avec la cl un prxe de plus en plus grand, ainsi, pour un rseau de n nuds, le routage ncessite au plus ln2b (N ) sauts, 2b est la base de numration des identiants. La gure 1.19 est un exemple de routage dans Pastry.

xx02 8723 xxx0 xxx1 xx22 xxx3 xxx4 xxx5 xxx6 xxx7 Niveau 1 xx32 xx42 xx52 xx62 xx72 Niveau 2

x012 x112 x212 x312 x412 x512 x612

0712 1712 2712 3712 4712 5712 6712 7712

Niveau 3

Niveau 4

Fig. 1.19 Exemple de routage dans Pastry

1.4.4

Analyse des systmes bass sur les DHTs

Les tables de hachage distribues prsentent quelques limitations par lutilisation de la localit spaciale des ressources [54]. Si par exemple la ressource cherche est une page web (http ://www.cnn.comand/weather ) et qui est immdiatement prcde par la recherche de ressource (http ://www.cnn.comand ), le rseau doit tre capable


29

dutiliser les informations de la premiere recherche, an de lutiliser dans la deuxime recherche. Cette fonctionnalit nest pas prsente dans les DHTs, car les ressources sont indpendantes les unes des autres. Des nouvelles mthodes ont vues le jour pour rsoudre un tel problme, elles sont bases sur les Skip graph.

1.5

Laspect smantique dans les rseaux P2P

De nombreuses approches se penchent aujourdhui sur la smantique dans les reseaux P2P pour capter non plus la localit gographique, mais la localit dintrt (smantique). Ces techniques utilisent des similitudes dintrts entre les utilisateurs dune application donne. Les mthodes permettant de grer la localit smantique peuvent tre classes en deux grandes familles :

1.5.1

Dtection implicite de la smantique

La premiere classe regroupe les mthodes permettant de prendre en compte les aspects smantiques des nuds de manire implicite. Dans ce cas, les systmes cherchent deviner des intrts et des prfrences de chacun des utilisateurs, le plus souvent, ces systmes se basent sur lutilisation dun historique rcent, an de catgoriser les nuds du rseau P2P. En eet, direntes techniques de regroupement implicite des nuds bases sur la similarit des intrts de chacun des participants ont t proposes : LRU : Chaque nud possde une liste ordonne de voisins. Pour chaque voisin rpondant dune manire correcte une requte, celui ci est plac en tte de la liste, ainsi, par la suite, chaque requte est dabord envoye au voisin en tte de la liste, puis au suivant et ainsi de suite. Historique : La mthode historique choisit les x nuds les plus utiles durant une plage de temps dtermine. Popularit : Cette solution est une mthode hybride des deux mthodes prcdentes. Elle permet dobtenir des listes smantiques contenant la plupart du temps les nuds de mme type, en conservant la simplicit de LRU.

1.5.2

Dtection explicite de la smantique

Dans la seconde grande classe de mthodes permettant de prendre en compte laspect smantique dans les reseaux P2P, plusieurs mthodes ont t proposes.


30

La premire mthode est base sur un regroupement explicite des nuds au sein du rseau P2P. An damliorer lecacit, celle ci introduit le concept du rseau recouvrant smantique SON (Semantic Overlay Network ). Au dessus dun rseau recouvrant existant, les nuds sont regroups en plusieurs SONs en fonction de leurs intrts communs. Un nud peut appartenir plusieurs SONs, permettant ainsi un utilisateur de ne pas se limit un seul thme.

1.6

Performances des systmes P2P

Le tableau 1.2 rcapitule les performances des systmes P2P tudis dans ce chapitre. Napster Non Constant Non Non Gnutella Oui O(n) Non Non Plaxton Oui lnb (n) Non Non Can Oui d.N Oui Oui Chord Oui O(ln(n)) Oui Oui Pastry Oui ln2b (n) Oui Oui

Dcentralisation Localisation Scalabilit Equilibrage de charge

Tab. 1.2 Comparaison entre les dirents systmes P2P

1.7

Problmes ouverts

Les systmes P2P structurs comme par exemple CAN ou Chord sont gnralement bass sur lutilisation des tables de hachage distribues, ils utilisent des identicateurs uniques sur les donnes, par consquent, le rsultat de la recherche dune donne ne peut tre que unique. Contrairement aux systmes P2P non structurs, comme par exemple Napster ou Gnutella, la recherche se fait par des mots cls et les rsultats peuvent tre varis. La question qui peut tre pose est : Es ce quon peut amliorer les systmes P2P structurs pour quils puissent prendre en considration ce problme ?. Cest--dire, dans les systmes de partage de donnes, la recherche de " voiture " peut retourner " voiture de sport " ? Un rseau P2P est constitu de peers inconnus et donc potentiellement dangereux, il convient de mettre en uvre dirents mcanismes de scurit. Prendre en considration la notion de smantique au cours de recherche dans les systemes P2P structurs (bass sur les DHTs). Lutilisation ecace des rseaux P2P dans dirents domaines comme par exemple la tlphonie IP .


31

1.8

Conclusion

Dans ce chapitre, on a fait un tour dhorizon sur les systmes P2P les plus connus, on les a classis dans deux grandes classes, les systmes non structurs comme Napster, Gnutella, etc, les systmes structurs comme Pastry, CAN, Chord. On a numr leurs avantages et leurs inconvnients. Notons quil y a aussi dautres systmes P2P qui ne sont pas cits dans ce mmoire comme : KazaA, Freenet, Morpheus, Kademlia[32], Edutella[42], ... Les systmes Pair Pair (P2P ) sont confronts des problmes lis leurs tailles, leurs sensibilits la charge et leurs dynamismes. En eet, ces systmes doivent potentiellement pouvoir grer des millions de machines en restant ecaces, malgr des connexions et des dconnexions trs frquentes. Les recherches scientiques dans les rseaux P2P sont classies suivant trois grands axes : 1. Les plateformes P2P : Elles sont destines principalement pour rgler le problme dinteroprabilit dans les systmes P2P, ainsi que pour faciliter limplmentation des applications P2P, JXTA (Voir chapitres 3, 4 et 5 ) est un exemple de plateforme P2P . 2. Les algorithmes P2P : Comme le rseau Internet augmente sans cesse une grande acclration, larchitecture client-serveur commence avoir des problmes de scalabilit. Les algorithmes P2P sont devenus intressants au fur et mesure de cette augmentation, on peut citer titre dexemple CAN, Chord. 3. Les applications P2P : Une application P2P est un algorithme P2P implment au dessus dune plateforme P2P. En outre, les rseaux P2P ne doivent pas tre systmatiquement associs aux applications de partage de chiers, ces rseaux sont actuellement utiliss dans de nombreux autres domaines tels que : le travail collaboratif ou le calcul distribu . Si lon considre lvolution actuel de linformatique, avec les rseaux ad hoc, les rseaux sans ls, la mobilit, laccroissement de la puissance des machines et de la bande passante, il nous semble que dans ce contexte, les rseaux P2P prennent leur places et occupent une partie importante du trac rseau. Les architectures P2P prcdentes constituent chacune un systme distinct, incapable de communiquer avec les autres. Aux vues de ce constat, certaines entreprises, telles que Sun Micro System ont entrepris des eorts de standardisation des protocoles de communication indpendants des systmes dexploitations et des langages de programmation, comme JINI et JXTA 1 .1

JXTA se prononce juxta

Chapitre II

Internet Quatre Niveaux (I4N )

Rsum : un problme fondamental qui confronte les applications P2P est la dcouverte et la localisation ecaces des nuds qui stockent des donnes particulires. Dans ce chapitre on a propos I4N (Internet Quatre Niveaux ) : Nouveau protocole P2P scalable et distribu qui traite ce problme. Mots cls : P2P, protocole de routage P2P, systmes P2P structurs, I4N.

2.1

Introduction

Les rseaux P2P sont classis en deux grandes classes. La premire classe est les rseaux P2P non structurs comme Gnutella [24] dans laquelle la recherche se fait par la technique de diusion (ooding), en utilisant les TTLs et donc la recherche de ressources nest pas dterministe. Une requte peut chouer mme si la donne cherche est prsente dans le systme. La deuxime classe est les rseaux P2P structurs, dans ce type de systme, les nuds sont organiss suivant une architecture bien dnie comme Chord (Anneau)[60], CAN (Tore)[47]. Dans ce chapitre on va proposer un systme P2P, scalable lchelle de lInternet et compltement dcentralis, structur suivant des anneaux plusieurs niveaux.

32

Chapitre 2 : Internet Quatre Niveaux (I4N)

33

2.2

Motivations

Le routage dans les rseaux P2P est un routage au niveau applicatif et par consequent, le nombre du sauts correspondant dans la couche rseau sera plus grand. Lobjectif dans le routage P2P est de diminuer au maximum possible le nombre de sauts.

2.3

Identication des nuds et des ressources

Chaque nud est identi par un identicateur unique N qui est la iemme partie de son adresse IP (1 i 4) tel que i est le niveau o appartient ce noeud, ainsi, le nud dadresse IP : 176.210.12.14 aura comme identicateur N176 sil appartient au niveau 1, N210 sil appartient au niveau 2, N12 sil appartient au niveau 3 et N14 sil appartient au niveau 4. Plusieurs nuds peuvent avoir le mme identicateur, mais ils appartiennent des anneaux dirents, par exemple : Les nuds dadresse IP : 176.210.12.14 de niveau 1 et 176. 176.14.12 de niveau 2, ont tous les deux lidenticateur N176. Les nuds appartenant au mme niveau ont des identicateurs dirents. Les ressources leurs tours, sont identies par des identicateurs uniques gnrs par les tables de hachage distribues. La cl dune ressource est compose de quatre parties de la forme (A.B.C.D).

2.4

Architecture du rseau I4N

Le rseau est structur en plusieurs anneaux imbriqus, chaque anneau contient au maximum 256 nuds. Lanneau de niveau 1 contient les nuds dadresses IP varient entre 1.x.y.z et 255.x.y.z, de telle manire que si le nud dadresse IP : 1.214.125.16 appartient lanneau de niveau 1, alors le nud dadresse IP : 1.215.125.16 appartient un anneau de niveau suprieur (2, 3, ou 4 ), ainsi, les nuds dadresses IP : 213.16.25.114, 213.16.25.214, 213.16.25.145 et 213.16.25.146 peuvent appartenir au mme anneau (niveau 4 ) et donc ils sont logiquement et physiquement proches. Dans chaque anneau, les nuds sont ordonns suivant leur identicateurs (gure 2.1). Les nuds appartenant deux anneaux de niveaux dirents sont les nuds appartenant lensemble Z = X Y tel que : X = { lensemble des nuds appartenant lanneau de niveau i , leurs adresses IP sont de la forme P1.Pi.P3.P4 } (ici i =2 ). Y= { lensemble des nuds appartenant lanneau de niveau i + 1, leurs adresses


34

IP sont de la forme M1.M2.M3.M4 et le nud dadresse IP M1.x1x2x3x4.M3.M4 nappartient pas lanneau de niveau i 1 }. Chaque nud maintient une table de routage qui contient les adresses IP et les numros du port des nuds qui lui sont relis logiquement et qui lui sert pour la recherche de ressources. Cette table contient au maximum 2 ln(256) entres, ln(256) entres pour chaque niveau, car chaque peer peut appartenir deux anneaux de niveaux successifs.N90

N72 N74 Niveau 1 N81 N50

N69

N62

N99 N60 N41

N50

N66 Niveau 2 N38 N29 N120 N31 Niveau 3 N210 N200 N21 N52 Niveau 4 N111 N67

N61

Fig. 2.1 La structure du rseau P2P (I4N)

2.5

Placement des ressources

Les ressources sont identies par des identicateurs uniques de la forme A.B.C.D gnrs par les fonctions de hachage distribues. Une ressource didenticateur A.B.C.D sera place dans le nud dadresse IP : WXYZ tel que W (respectivement X,Y,Z ) est la plus petite valeur suprieure ou gale A (respectivement B, C, D).


35

2.6

Construction de la table de routage

Quand un nouveau nud arrive sur le rseau, il initialise sa table de routage de telle manire quelle contient 2 ln(256) (16 entres), huit (8) entres pour chaque niveau. Le dbut de lintervalle de la iemme entre doit tre suprieur ou gal N + 2i1 et la n de lintervalle doit tre gal au (dbut de lintervalle -1) de lentre suivante et ceci pour les deux niveaux. La gure 2.2 montre la table de routage du nud didenticateur N50 dans lanneau du niveau 1 et didenticateur N52 dans lanneau du niveau 2.N90

finger table N50/N52 N72 N74 Niveau 1 N50 + 1 N50 + 2 N50 + 4 N50 + 8 N50 + 16 N60 N60 N60 N60 N69

N69

Niveau 1

N81 Niveau 2 N99 N60 N52

N50

N62 Niveau 2

N60

N41

N52 + 1 N52 + 2 N52 + 4 N52 + 8 N52 + 16

N60 N60 N60 N60 N29

Niveau 2

N50

N66 Niveau 2 N38 N29 N120 N111 N31 Niveau 3 N210 N200 N20 N21 N52 Niveau 4 N67

Niveau 4

N61

Fig. 2.2 La table de routage dun nud dans I4N

2.7

Recherche de donnes

I4N prsente un algorithme de recherche simple et exhaustive, cest--dire, il garantie de trouver la donne une fois elle est prsente dans le systme P2P. Le cot de la recherche de ressources dpend du nombre de niveaux parcourus dans le rseau, il est donn en (ln(ni )), i 4, ni est le nombre de nuds dans lanneau de niveau i.


36

Un nud dsire rechercher la donne X, il calcule la cl de cette dernire (soit c1 c2 c3 c4 ) en utilisant la mme fonction de hachage par laquelle elle tait place, ensuite il invoque lalgorithme de recherche rechercher (c1 c2 c3 c4 ). Algorithm 5 Algorithme de recherche de donnes (I4N ) Rechercher (cl c1 c2 c3 c4 ) 1 : Dbut 2 : Localiser le nud X dans le mme niveau dadresse IP (P1 P2 P3 P4 ) tel que P i est la plus petite valeur suprieure ou gale Ci. 3 : Si cj tel que cj > Pj et j < i alors 4 : Aller au nuveau (i 1) et appeler Rechercher (cl c1 c2 c3 c4 ) 5 : Sinon 6: Si la donne est prsente alors 7: tlcharger la donne 8: Sinon 9: Aller au niveau (i + 1) et appeler Rechercher (cl c1 c2 c3 c4 ) (si i < 4) 10 : Fin

2.8

Arrive dun nud

Quand un nouveau nud rejoint le rseau, il obtient quelques adresses IP de nuds qui sont dj dans le rseau par le mcanisme de boostrapping[7], il contacte lun de ces nuds pour quil puisse se plac dans le systme I4N, ensuite il construit sa table de routage.

2.9

Dpart dun nud

Dans le dpart volontaire dun nud, les cls de donnes sur lesquelles il est responsable seront assignes son successeur dans tous les anneaux o il appartient (maximum deux anneaux ). Dans un dpart involontaire dun nud (dfaillance), les cls de donnes sur lesquelles il est responsable seront republies par leurs propritaires. Dans les deux types du dpart, lalgorithme de stabilisation (Algorithme 6) est lanc . Soient : n : le nud didenticateur n, ni et ni+1 les deux niveaux lesquels il appartient.


37

Algorithm 6 Algorithme de stabilisation (I4N ) depart (n, ni , ni+1 ) 1 : Dbut 2: Si (ni+1 est vide) alors 3: mettre jour la table de routage 4: Sinon 5: Si (n , ni , ni+1 ) tel que ni = ni+1 alors 6: Si (ni+1 = vide) alors 7: ni = ni ; ni+1 = ni+1 ; 8: mettre jour la table de routage 9: Sinon 10 : ni = ni ; ni+1 = ni+1 ; 11 : mettre jour la table de routage 12 : depart (n , ni , ni+1 ) 13 : Fin

2.10

Acclration de la recherche

La recherche dans I4N peut tre acclre, en adoptant la technique de broadast dans chaque niveau et donc la recherche se fera en 4 sauts maximum (un saut dans chaque niveau). Le nombre de messages pour une recherche sera videmment plus grand.

2.11

Proprits de protocole

Le protocole I4N prsente plusieurs caractristiques intressantes dans la pratique : La scalabilit : I4N est indpendant du nombre de nuds dans le rseau. La recherche se fait dune manire exhaustive, elle est de lordre de ln(ni ) sauts, ni est le nombre de nuds dans le niveau i. La dcentralisation : Le protocole I4N est compltement dcentralis, tous les nuds sont similaires (aucun nud nest important que les autres). Lquilibrage de charge : La gnration des cls de donnes se fait par les tables de hachage distribues, qui garantissent lquilibrage de charge entre les nuds. La tolrance aux fautes : le protocole I4N maintient toujours la stabilit du systme en cas de dpart (volontaire ou involantaire) ou darrive dun nouveau nud. le cot : La table de routage dans le protocole I4N est distribue sur tous les nuds, chacun deux maintient des informations sur uniquement 2 O(ln(s)) autres nuds, s 256 (le nombre maximum de nuds dans un seul anneau).


38

2.12

Lvolution du rseau

Aprs un certain temps de fonctionnement du systme, ce dernier ressemble la gure 2.3.

N3 N3 N2 N2 N3 N1 N2 N3 N3 N2

N3

N4 N3 N4 N3

N4 N4

N3 N4

N4

Fig. 2.3 Lvolution du systme I4N

2.13

Conclusion

Les protocoles P2P de la troisime gnration bass sur les tables de hachage distribues, possdent plusieurs avantages par rapport ceux de la deuxime gnration et ceux de la premiere gnration, qui sont bass respectivement sur la diusion et lindex centralis, car, le cot de recherche est considrablement diminu. Par nature, les DHTs maintiennent un quilibrage de charge, mais elles sont diciles mettre en uvre. Laspect smantique est trs loin detre implement avec ces dernires. Le protocole I4N (Internet Quatre Niveaux ) que nous avons propos dans ce chapitre, divise le rseau des rseaux en des sous rseaux imbriqus, il est quivalent au protocole Chord en cot de recherche car ln(n) = (ln(ni )) tel que n = (ni ). Il utilise les DHTs pour gnrer uniquement les cls de ressources, celles des nuds sont construites base des adresses IP.

Chapitre III

Les direntes plateformes P2P

3.1

Introduction

Les applications P2P sont en pleine expansion et les programmes P2P actuels implmentent gnralement une seule fonction (service rseau), par consquent, elles sont incapables dchanger directement des donnes avec dautres applications similaires (par exemple eDonkey avec KazaA ). Ainsi, les applications P2P ne peuvent fonctionner que sur une seule plateforme, ce qui est contradictoire avec le principe des systmes P2P. Cest pour ces raisons que plusieurs plateformes P2P ont t proposes.

3.2

XtremWeb

XtremWeb est une plateforme exprimentale de global Computing luniversit paris-sud. Lide derrire le global computing est de rcuprer le temps libre des ordinateurs connects Internet, ces ordinateurs tant repartis travers le monde. Lobjectif principal de XtremWeb est la conception et le dveloppement dun environnement de calcul pair pair et dexcuter dune manire compltement distribue de trs grosses applications pluridisciplinaires. XtremWeb est destine des applications de types SPMD1 (Single Program Multiple Data), ce type dapplications est ais la distribution. On divise le programme en des morceaux de codes indpendants et on les distribue chacun sur un peer. Avec XtremWeb, les participants ne ralisent pas1

SPMD est une sous classe de SIMD

39

Chapitre 3 : Les direntes plateformes P2P

40

seulement la tache de calcul, mais ils peuvent aussi proposer leurs applications qui ncessitent une puissance de calcul pour tre distribues. XtremWeb ncessite sur chaque peer un ensemble de serveurs et dapplications (Appache, PHP, MySQL). Ces besoins logiciels sont dicilement compatibles avec des petites machines comme les PDAs. XtremWeb peut tre utilise de deux manires direntes : 1. Volontaire : Un volontaire senregistre dabord sur un serveur dadministration dXtremWeb, tlcharge lapplication et linstalle en local ou en rseau. Pendant le temps doisivet, ces machines peuvent collaborer pour un calcul global. 2. Collaborateur : Un collaborateur aussi senregistre sur un serveur dadministration dXtremWeb, les collaborateurs tlchargent des applications leurs permettant de congurer leur propre application. Lorsque un collaborateur na pas une tache excuter et aucun travail envoyer sa communaut de PCs, il fonctionne comme tant un client formant un P2P computing.

3.2.1

Principe de fonctionnement

XtremWeb distingue trois rles essentiels pour un pair : Client, Serveur et Worker . Le rle principal de serveur, appel galement coordinateur est dassurer la mise en relation entre les demandes de ressources du calcul manant des clients et les ressources mises leurs dispositions par les Workers. Le rle de Worker est de fournir les ressources de machine dun utilisateur pour lexcution dun calcul XtremWeb. Un client soumet une tache en fournissant la rfrence de lapplication et lensemble des paramtres qui la dnissent. Lune des limites de la plateforme est labsence dun mcanisme permettant aux Workers dchanger directement ou indirectement des donnes [35]. Comme tous les environnements de calcul global en particulier et de P2P en gnral, XtremWeb doit satisfaire des contraintes svres [5] : 1. Extensibilit : Le systme doit tre extensible jusqu des centaines de milliers de nuds avec une augmentation de performances correspondantes. 2. Htrognit : Les machines possdent des congurations matriels et des congurations systmes trs varies. 3. Dynamicit : La communication dans le systme varie constamment, ainsi que la latence et le dbit de communications.


41

4. Disponibilit : Le propritaire dune ressource doit pouvoir dnir une politique qui limite la contribution de sa ressource, le systme de calcul global doit respecter cette politique. 5. Tolrance aux pannes : Une dfaillance de serveurs de calcul ou de collecteur de rsultats ne doit pas avoir dincidences sur les machines de calcul. La perte dune machine participante ou dun ensemble de machines participantes est un vnement intrinsque au systme. 6. Utilisabilit : Le systme doit tre simple utiliser, dployer et maintenir. 7. Scurit : Les machines participantes et les donnes doivent tre scurises.

3.3

ProActive

ProActive est une bibliothque JAVA pour le calcul parallle, distribu et concurrent, prenant en charge la mobilit et la scurit sur des grilles de calcul. Elle est dveloppe luniversit Sophia Antipolis de Nice, elle ore un ensemble de primitives et des APIs de programmation pour faciliter la mise en uvre des applications distribues sur des LANs, des clusters, ainsi que sur des grilles de calcul. ProActive repose sur le modle MIMD (Multiple Instruction Multiple Data), elle est base sur le concept dObjet Actif. Elle sappuie aussi sur le MOP(Meta Object Protocol ) et utilise la librairie standard JAVA RMI(Remote Method Invocation) comme une couche de transport portable.

3.3.1


Le dveloppement et la distribution des applications concurrentes en utilisant ProActive sont bass sur les objets actifs (AO), chaque objet actif a son thread qui execute ses propres mthodes invoques par dautres AOs. Les AOs peuvent tre cres sur nimporte quel hte.

3.4

JXTA

La plupart des applications P2P, actuellement existantes, sont ddies une seule fonction ou une seule classe de problmes, de plus, elles ne peuvent sexcuter que sur un seul type darchitecture et elles ne permettent pas de partager directement leurs


42

ressources avec les autres. Cest dans le cadre de cette problmatique que SUN Microsystem a cr le projet JXTA [37]. Le but de projet JXTA est de crer une plateforme P2P qui permet de construire simplement, facilement et ecacement un ensemble de services dapplications distribues pour tout dispositif qui pourrait tre un pair. JXTA permet aux dveloppeurs de concentrer sur le dveloppement de leurs applications en crant des logiciels interoprables .

3.4.1


JXTA propose un ensemble de protocoles ouverts pour interconnecter des dispositifs allant du tlphone cellulaire jusquaux serveurs, en faisant abstraction de la topologie physique. Le fonctionnement repose sur le dcoupage du rseau rel en rseaux virtuels, dans lesquels chaque pair peut accder aux ressources des autres sans se proccuper de leur localisation ou de leur environnement dexecution, JXTA propose une base de six protocoles dans lesquels la communication se fait par des messages XML. On y trouve les services de dcouverte des peers, de rendez-vous, dinformations sur les peers, de communication et de routage. JXTA est faite pour que toutes ses applications puissent sexcuter sur nimporte quelle plateforme (PC, Serveur, PDA, Station de travail, tlphone,...). La philosophie de JXTA est de fournir les mcanismes de base et de laisser les choix dimplmentation des applications aux dveloppeurs. Pour ce faire JXTA sappuie sur des standards tels que XML, JAVA.

3.5

Conclusion

Dirents protocoles P2P ont t proposs dans la littrature, chacun deux a ses avantages et ses inconvnients. Linconvenient principal de ces protocoles dans les rseaux P2P est quils sont indpendants les uns des autres, ils sont incapables dchanger des services, chacun deux cre sa communaut dutilisateurs. Pour ces raisons, plusieurs plateformes P2P ont t proposes ces dernires annes, malheureusement, la majorit de ces plateformes sont ddies une classe de problmes limite, comme par exemple ProActive pour le calcul global et le Grid computing. La plateforme la plus gnraliste est JXTA, dans laquelle la plupart des services peuvent tre implments, comme le partage de chiers, la messagerie instantane , la tlphonie IP, le calcul distribu, etc.

Chapitre IV

Les Rseaux P2P et la technologie JXTA

4.1

Introduction

Le vocabulaire Peer to Peer (P2P ) est aujourdhui un des mots les plus la mode. Il nest pas un nouveau concept, il existe depuis lapparition de lInternet en 1970 [18]. Ces dernires annes, il a attir lattention des industrielles et des universitaires. Cette nouvelle technologie est de plus en plus utilise, elle constitue une mthode ecace de partage de ressources entre membres dune mme communaut. Par ailleurs, en plus des utilisateurs grand public les plus connus (partage des chiers et messagerie instantane), cette technologie peut rsoudre un ensemble de problmes lis lutilisation optimale des ressources disponibles dans les rseaux et le

Documents

Thesis Magistere 05