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 $\log _{B}N$ 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 $\log _{B}N$ où c est le nombre de liens secondaires^{[à vérifier]}.

Tapestry a été utilisé par des applications telles que

• OceanStore, un utilitaire de stockage distribué sur PlanetLab ;
• Mnemosyne, un système de fichiers stéganographique ;
• Bayeux, une application de multidiffusion auto-organisée ;
• Spamwatch, un filtre antispam décentralisé.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Tapestry » (voir la liste des auteurs).

Articles connexes

• Pastry
• Kademlia
• Chord
• Content Adressable Network