Kademlia
Kademlia (alias Kad) est un réseau de recouvrement créé pour décentraliser les autres réseaux d'échange de fichiers poste-à-poste (Peer-to-Peer ou P2P en anglais).
Le protocole précise la structure du réseau Kademlia, les communications entre les nœuds et l'échange d'information. Les nœuds communiquent grâce au protocole UDP (cf le modèle OSI.)
Principe
À l'intérieur d'un réseau existant (Internet), Kademlia crée un nouveau réseau, à l'intérieur duquel chaque nœud est identifié par un numéro d'identification, un ID (nombre binaire à 156 bits.)
Passée une phase d'amorçage consistant à contacter un nœud du réseau puis à obtenir un ID, un algorithme calcule la «distance» entre deux nœuds, et interroge plusieurs nœuds suivant cet algorithme afin de trouver l'information recherchée. Cet algorithme utilise une notion de distance entre deux nœuds, calculée grâce à une opération mathématique (OU exclusif, aussi appelée XOR) délivrant un résultat sous forme de nombre entier : la «distance». Cette dernière n'a rien à voir avec la situation géographique des participants, mais modélise la distance à l'intérieur de la chaîne des ID. Il peut donc arriver qu'un nœud en Allemagne et un nœud en Australie soient «voisins».
Une information dans Kademlia est conservée dans des «valeurs», chaque valeur étant jointe à une «clé». On dit de Kademlia qu'il est un réseau <valeur,clé>.
Lors de la recherche d'une certaine clé, l'algorithme explore récursivement le réseau au cours de différentes étapes, chaque étape s'approchant plus près de la clé recherchée, jusqu'à ce que le nœud contacté retourne la valeur, ou que plus aucun nœud ne soit trouvé. La taille du réseau n'influe pas énormément sur le nombre de nœuds contactés durant la recherche ; si le nombre de participants du réseau double, alors le nœud de l'utilisateur doit demander l'information à un seul nœud de plus.
D'autres avantages sont inhérents à une structure décentralisée, augmentant par exemple la résistance à une attaque de déni de service. Même si tout une rangée de nœuds est submergée, cela n'aura que des effets limités sur la disponibilité du réseau, qui «recoudra» le réseau autour de ces trous.
Utilisation effective
L'algorithme Kademlia est utilisé par plusieurs clients poste-à-poste (les réseaux sont incompatibles les uns avec les autres) :
- VarVar (premier client Kademlia, possède son propre réseau)
- réseau Overnet : Overnet, eDonkeyHybrid et mlDonkey
- réseau Kad : eMule (depuis la version 0.40) - mlDonkey (depuis la version 2.5-28)
- Revconnect DC++ - voir aussi [[1]] (depuis la version 0.403)
- KadC: [[2]] une librairie C pour publier et recevoir de l'information vers/depuis le réseau Overnet.
Voir aussi
« Kademlia: A Peer to peer information system Based on the XOR Metric », http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf