Tapestry (DHT)
Tapestry (de l'anglais : tapisserie) est un réseau de recouvrement de type table de hachage distribuée pour les réseaux pair à pair (P2P).
Présentation
Les applications P2P telles que Tapestry, Chord, Pastry et CAN implĂ©mentent un mĂ©canisme de routage basĂ© sur des clĂ©s. Le routage des messages est dĂ©terministe et sâadapte aux dĂ©faillances de nĆuds dans le rĂ©seau. Tapestry et Pastry utilisent le mĂȘme algorithme de routage, celui de Plaxton et al.
Tapestry construit Ă l'initialisation des tables de routage localement optimales et maintient ces tables pour rĂ©duire l'allongement du routage. Chaque nĆud du rĂ©seau est identifiĂ© par un identifiant unique. De mĂȘme, chaque point dâentrĂ©e applicatif reçoit un GUID (globally unique identifier).
L'efficacité de Tapestry augmentant avec la taille du réseau, il est préférable de partager beaucoup d'applications dans un grand réseau.
Les tables de proximitĂ© fournissent au premier niveau les liens des nĆuds qui n'ont rien en commun, au deuxiĂšme niveau les liens de nĆuds qui ont leur premier digit en commun, etc. Un routage fait de lâordre de pas, dans un rĂ©seau de taille N avec des identifiants en base B (hex: B=16). Chaque nĆud conserve la copie primaire de sa table de proximitĂ© et des liens secondaires pour faire face aux dĂ©faillances possibles, la taille de la table de routage fait ainsi c x B x oĂč c est le nombre de liens secondaires.
Tapestry a été utilisé par des applications telles que
Notes et références
- (en) Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph, John D. Kubiatowicz et al., « Tapestry : A Resilient Global-Scale Overlay for Service Deployment », IEEE Journal on selected areas in communications, vol. 22, no 1,â , p. 1-13 (lire en ligne [PDF])
- (en) Steven Hand et Timothy Roscoe, « Mnemosyne : Peer-to-Peer Steganographic Storage » [PDF], sur cl.cam.ac.uk, nc, p. 1-6