s
19 708 Pages

en informatique et télécommunications Kademlia est un Protocole réseau peer-to-peer conçue par Petar Maymounkov et David de Mazières Université de New York, pour un réseau informatique décentralisé.

Indique la structure du réseau, régule la communication entre les noeuds et la manière dont doit être l'échange d'informations. Les noeuds Kademlia communiquent entre eux en utilisant le protocole de transport UDP.

Utilisation dans les réseaux de partage de fichiers

Kademlia est utilisé par de nombreux programmes le partage de fichiers pour sa caractéristique d'être basée sur des tables distribuées des noeuds de réseau sans serveur plantes. Recherches Kademlia peuvent être effectuées pour des mots-clés pour trouver le fichier a demandé et la tâche de stocker l'index des fichiers existants est un partage égal entre tous client. Le nœud qui possède un fichier que vous souhaitez partager, analyse et calcule un nombre hachis qui permettra d'identifier les fichiers sur le réseau de partage de fichiers. Hash et les ID doivent être de la même longueur.

Le moteur de recherche de noeud par tous les autres noeuds qui ont l'ID à la distance minimale du hachage du fichier, et de stocker leurs propres adresse IP sur ce noeud. Le client utilisera la recherche Kademlia va commencer à rechercher l'ID du client qui a la distance minimale du hachage du fichier que vous recherchez, puis récupérer la liste de contacts (par exemple IP) qui sont stockés dans ce nœud. Les contacts stockés dans le réseau sont en constante évolution, car les noeuds connecter et déconnecter. Merci à une redondance intrinsèque des informations sur Kademlia ces contacts sont répliqués dans des noeuds différents.

traits

Kademlia est basé sur la technologie Distributed Hash Table (DHT). sur un LAN/WAN (comme Internet) Existe déjà, un nouveau réseau virtuel est créé où chaque nœud Il est identifié par un numéro ( « Noeud »). Ce numéro sert non seulement dans le but de la reconnaissance d'un nœud, mais l'algorithme Kademlia utilise pour localiser des valeurs (par exemple, le code hachis le nom de fichier ou un -keyword de mot-clé) que l'ID de noeud permet de cartographier les valeurs qui doivent être stockées.

Le réseau définit une notion de distance qui permet de déterminer la proximité entre deux noeuds de sorte que, étant donné un « noeud A » est toujours possible de déterminer si un noeud « B » est plus proche d'un noeud « C ». Chaque noeud dispose d'une connaissance du réseau Kademlia qui diminue à mesure que la distance depuis le même noeud, et, par conséquent, présente une très bonne connaissance détaillée du réseau dans leur environnement, une bonne connaissance du réseau à moyenne distance et seulement une connaissance clairsemée des noeuds très loin.

Le but de Kademlia est de stocker et de récupérer des valeurs qui peuvent être de tout type, mais, en général, sont des pointeurs vers des fichiers. Les valeurs sont indexées par « touches » ( « Keys »). ID de nœud et les touches ont le même format, vous pouvez calculer la distance entre deux nœuds exactement comment. Il en résulte que chaque noeud est en mesure de calculer la distance entre lui-même et deux touches « K1 » et « K2 », la compréhension qui des deux est plus proche. De même, le « A » noeud est en mesure de déterminer lequel des deux « K1 » et les touches « K2 » est plus proche d'un « nœud B ». « A » et « B » sont toujours cohérentes dans ce calcul.

Pour mémoriser une valeur, le nœud demandeur:

  • calculer la clé correspondante (généralement la valeur de hachage à stocker),
  • recherchera les nœuds du réseau avec « ID noeud » plus proche du hachage de la valeur à stocker,
  • exiger que le stockage de la valeur dans tous ces nœuds.

Lors de la recherche d'une clé, l'algorithme explore le réseau par étapes successives et à chaque étape, il se rapproche de la clé de recherche jusqu'à ce que le noeud contacté ne retourne pas la valeur ou il n'y a pas plus de nœuds à requêtés. Le nombre de noeuds contactés lors de la recherche ne dépend que marginalement par la taille du réseau: si le nombre de participants au réseau double, le noeud d'un utilisateur doit interroger un seul nœud pour chaque autre recherche, pas deux fois ceux qui ont contacté avant.

D'autres avantages se trouvent en particulier dans la structure décentralisée qui augmente nettement la résistance contre les attaques déni de service. Bien qu'un ensemble complet de nœuds sont vous être ciblés auront des effets très limités sur le réseau, il passera automatiquement le problème en isolant le réseau autour de ces zones à problèmes.

Détails d'opération

La première génération de réseaux peer-to-peer pour l'échange de fichiers, tels que Napster par exemple, il a été basé sur une base de données centralisée pour coordonner la recherche et de stockage au sein du réseau. La deuxième génération, tels que Gnutella, exécute une information de recherche en interrogeant chaque massif du noeud de réseau connu. La troisième génération utilise Distributed Hash Table (DHT) pour rechercher des fichiers sur le réseau. Les valeurs de magasin de DHT (par exemple les adresses des ressources à partager) et les rendre disponibles à l'ensemble du réseau. L'objectif principal de ces protocoles est la vitesse dans la recherche d'information.

L'algorithme est basé sur Kademlia calculer la distance entre deux noeuds. La distance est calculée en tant que XOR entre deux « Noeud » et en prenant pour toute la valeur. « Noeud » et « clés » ont le même format et la même longueur, de manière à pouvoir calculer les distances entre les noeuds et entre ceux-ci et les clés de la même façon.

La distance calculée comme il n'a rien à voir avec la distance géographique et deux noeuds qui sont voisins à l'algorithme peuvent être situés sur deux continents différents.

L'algorithme itérativement à la recherche des clés à travers le réseau, approche un peu le résultat à chaque pas. Il en résulte qu'un réseau Kademlia avec nœuds, il faudra au plus n étapes pour trouver le noeud recherché.

Table d'adressage (table d'acheminement)

La table de routage Kademlia consiste en une liste pour chaque bit le « Noeud » (à savoir si le « Noeud » est longue 128 bit, le noeud conservera 128 de ces listes). Chaque liste a beaucoup de revenus. Chaque entrée dans la liste contient les informations nécessaires pour localiser un noeud; les données principales sont l'adresse IP, le port et le « Noeud » d'un autre noeud sur le réseau. Chaque liste correspond à une distance spécifique à partir du noeud. Les noeuds qui finissent dans énième liste doit avoir au moins la nième bit différent de celui du noeud: la première n-1 bits doivent être égaux à ceux du noeud considéré. Cela signifie qu'il est possible de soumettre au remplissage de la première moitié des noeuds de liste qui sont situés plus éloignés du nœud courant. La liste suivante peut être utilisée 1/4 les noeuds du réseau qui sont plus proches d'un bit, et ainsi de suite.

Avec un « Noeud » de 128 bits, chaque nœud peut être classé dans l'une des 128 distances possibles, un pour chaque bit de différence.

Quand ils se rencontrent dans les nœuds du réseau Kademlia, ceux-ci sont ajoutés à la liste de la table de routage. Cela se produit lors de l'opération de recherche et de stocker et même dans le cadre de l'assistance pour les activités de recherche au nom d'un autre nœud. Chaque noeud sera atteint candidat à l'inscription sur les listes. Il en résulte que la connaissance du réseau est très dynamique, tient des informations à jour et offre une résistance aux anomalies et aux attaques.

Dans la littérature de la liste est appelée Kademlia k-bucket, où k Il est une valeur constante pour l'ensemble du réseau (génériquement de k = 20). Chaque k-seau est donc une liste contenant jusqu'à k entrées (dans notre cas 20) qui se réfèrent à k k loin de nœuds de bits du noeud considéré.

Étant donné que le nombre de noeuds possibles pour un k-godet déterminé diminue rapidement avec la distance décroissante, les k-seaux avec peu inférieur décrivent complètement le réseau environnant au noeud. Étant donné que le nombre d'ID possible de nœud est beaucoup plus grande que toute la population possible de noeuds appartenant au réseau, des k-seaux correspondant à de courtes distances à partir du nœud resteront vides.

Kademlia
Un exemple de partitionnement de réseau

Considérons le réseau indiqué sur la figure sur le côté. Avec n = 3, la possible « Noeud » est de 8, par voie 000 à 111. Dans ce réseau simplifié il y a sept noeuds représentés par des cercles en bas: le noeud courant est le six et est représenté par le cercle noir ( « ID node « = 110). Le noeud avec le cercle noir (et même d'autres) a 3 k-godet. Les nœuds de zéro, un et deux (par exemple 000, 001 et 010) sont des candidats pour être inclus dans le premier k-bucket; quatre et cinq noeuds (100 et 101) sont des candidats pour être inclus dans la seconde k-bucket; le troisième k-godet contient seulement sept noeud. Les k-seaux sont enfermés dans des cercles gris. Si la taille du k-seau était 2 (k = 2), le premier 2-seau ne contiendrait que deux des noeuds possibles, le second et tous deux, alors que le troisième aurait une seule entrée améliorée.

Il est statistiquement connu que les noeuds qui sont connectés au réseau le plus long sont plus susceptibles de rester connecté plus longtemps à l'avenir. En raison de cette distribution statistique, Kademlia sélectionne les noeuds connectés par le temps supplémentaire pour être stockés dans un k-seau. Cela augmente la connaissance des nœuds disponibles à l'avenir et rend le réseau plus stable.

Quand un k-seau est plein et a découvert un nouveau nœud pour ce k-bucket particulier, le nœud moins récemment vu est PING-ato; si le nœud est encore en vie, le nouveau nœud est placé dans une liste de remplacement (cache de remplacement). La liste de remplacement est utilisée uniquement si un noeud d'un k-seau cesse de répondre. En d'autres termes, les nouveaux nœuds ne sont utilisés que lorsque les anciens noeuds cessent de répondre.

Messages du protocole

Kademlia a quatre postes:

  • PING - utilisé pour vérifier qu'un noeud est vivant;
  • STORE - pour stocker une paire (clé, valeur) dans un noeud;
  • FIND_NODE - pour essayer nœuds; le noeud de réception du message fournit les noeuds k qui sont contenus dans son « ID de noeud » k-plus proche du godet recherchée;
  • FIND_VALUE - comme FIND_NODE, mais si le récepteur est clé demandée, au lieu de noeuds k fournit la valeur correspondant à la clé.

Chaque message RPC inclut une valeur aléatoire générée par l'initialiseur de la demande. Cette valeur est utilisée pour faire en sorte que la réponse est effectuée sur l'application.

une localisation de noeud

La recherche d'un nœud peut procéder de manière asynchrone. La quantité de recherches simultanées est désigné par α et est typiquement trois. Un noeud commence une recherche en envoyant une demande de FIND_NODE les noeuds contenus dans le k-seau plus proche de la « Noeud » pour trouver. Lorsque les noeuds de réception reçoivent le message, la recherche dans leur k-seau et retourner les k clés les plus proches du nœud souhaité. Sur la base des réponses reçues, le demandeur met à jour sa liste de réponses, seules les meilleures économies réponses k (ie k « ID de noeud » plus proche du noeud recherché). À ce stade, le demandeur réitère sa demande aux nouveaux nœuds résultant tant qu'il n'y a plus de noeuds les plus proches du noeud recherché. Depuis au cours du réseau de connaissances de la recherche autour de la valeur recherchée devient de plus en plus précis, l'algorithme converge rapidement vers k « ID comme » noeud proche de la valeur recherchée.

Lorsque vous ne pouvez pas trouver plus de noeuds voisins, l'algorithme de recherche se termine le retour le plus proche des valeurs de k-nœud recherché (y compris peut-être le nœud lui-même, si elle existe).

Les informations contenues dans le nœud peut être enrichi avec Round Trip Time ou RTT. Ces informations seront utilisées pour déterminer le délai d'expiration des requêtes envoyées à un noeud spécifique. Lorsqu'une demande est le temps, vous pouvez présenter une nouvelle demande évitant ainsi de dépasser le nombre α de requêtes simultanées.

Localisation des valeurs

L'information est localisé en traçant une clé. Cette mise en correspondance se fait avec l'algorithme qui calculehachis la valeur et l'utilise comme une clé. Le noeud de memorizer a obtenu la valeur au moyen d'un message STORE précédent. La localisation de la valeur est à la recherche du noeud « ID de noeud » plus proche de la valeur de clé, à l'exception que la recherche se termine lorsque trouvé un nœud qui contient la valeur de clé recherchée dans ce cas, le nœud question revient correspondant à la valeur de clé.

Les valeurs sont stockées (redondant) sur plusieurs nœuds pour permettre à chaque noeud d'entrée et de sortie du réseau, sans que cela affecte le fonctionnement du même. A intervalles de temps réguliers un nœud qui stocke une valeur explorera le réseau à la recherche des k plus proches nœuds à la valeur de la clé et nous allons reproduire la même valeur (au moyen d'une instruction STORE). Ce processus permet d'éviter la disparition des nœuds. Cette nouvelle mémoire est appelée un cache. Les valeurs les plus recherchées et populaires auront la capacité à répartir sur plusieurs nœuds à proximité de la valeur de la clé recherchée, en évitant la concentration des demandes sur quelques nœuds. Dans certaines implémentations le cache est à son tour répliqué par un processus itératif dans les noeuds les plus proches de celui qui détient le cache, contribuant ainsi à diffuser les valeurs à travers le réseau. Les informations contenues dans le cache sont supprimés après une période de temps déterminée en fonction de la distance de la clé, ce qui permet au réseau de supprimer les valeurs ne sont plus mises à jour. Etant donné que même à la fin de la demande également le demandeur est titulaire de la valeur, il en résulte que les applications les plus populaires sont accélérés par la disponibilité des informations à de nombreux nœuds.

Certaines implémentations (KAD) ne possèdent pas de mécanismes de réplication et de mise en cache, car il est important d'enlever immédiatement des informations obsolètes. Seul le nœud qui veut partager le fichier responsable de l'actualisation périodique des informations contenues dans le réseau (par une opération de NODE_LOOCKUP et STORE). Lorsque tous les noeuds qui possèdent les fichiers quittent le réseau, les informations sont pas répliquées plus et disparaît du réseau.

Entrer dans le réseau

Un nœud qui veut rejoindre le réseau doit d'abord commencer un processus appelé bootstrap. A ce stade, le noeud a besoin de connaître le 'adresse IP d'un autre noeud (obtenu auprès de l'utilisateur ou à partir d'une liste stockée) qui sont déjà dans le réseau Kademlia. Si le nœud qui doit faire bootstrap n'a jamais participé au réseau, il calcule un numéro d'identification aléatoire qui n'a pas encore été affecté à un autre nœud. Utilisez cet ID jusqu'à ce qu'il quitte le réseau.

Le nœud entrant insère le noeud de départ dans l'un de ses k-seau, puis procède all'autoricerca. De cette façon, l'ID du nœud entrant est stocké dans le k-seau des noeuds participant à la recherche, tandis que les réponses alimenter le k-seau avec les ID des noeuds inclus dans le chemin entre le noeud d'amorçage et le nœud entrant. A ce stade, le processus est terminé avec la recherche d'une valeur aléatoire du plus éloigné du noeud d'amorçage à partir du nœud entrant.

Recherche accélérée

Kademlia calcule les distances entre les noeuds en utilisant un XOR métrique. Le calcul de la distance est effectuée en réalisant une opération XOR (OU exclusif) entre deux ou entre un ID de nœud Node ID et une clé: le résultat, en binaire, on suppose que la distance.

Pour chaque bit, la fonction XOR renvoie 0 si les deux bits sont égaux ou 1 si les deux bits sont différents. en métrique XOR reste valable l'inégalité du triangle valide suivant dans la géométrie classique: la distance entre deux points A et B est inférieure ou égale à la somme des distances entre un point A et C et à une distance quelconque entre C et B.

la XOR métrique Kademlia permet d'étendre les tables d'adressage en plus de la limite des bits individuels. Les bits du groupe peuvent être regroupées en K-seaux. Pour un préfixe donné de m-bits, il y aura k-seaux de 2 m-1. Le manque k-godet est l'adresse d'extension d'arbre supplémentaire qui contient le noeud-ID. Un préfixe m bits réduit le nombre de recherches dans la table de routage à partir de n log2 maximal à n log2b. Le nombre moyen de recherches sera beaucoup plus petite, puisque l'augmentation prossibilità de trouver un nœud dans son k-seau qui partage nombre de bits en plus de leur préfixe.

Logiciel en utilisant Kademlia

Il est actuellement mis en œuvre à différents niveaux et avec des fins diverses, dans le client peer-to-peer:

  • kad
    • aMule: A partir de la version 2.1.0
    • eMule: A partir de la version 0.40
    • MLDonkey: A partir de la version 2,5-28
    • iMule
    • lphant
  • réseau Overnet
    • KADC: bibliothèque C pour obtenir et envoyer des informations de / au réseau Overnet
    • MLDonkey
    • Overnet: maintenant incorporée dans eDonkey2000
  • d'autres implémentations
    • Azureus: Depuis la version 2.3.0.0
    • Bitcomet: De 0h59 Version
    • BitTorrent: 4.1.0 prend en charge le réseau Kademlia pour torrent traqueur à partir d'une mise en œuvre de Khashm
    • uTorrent: A partir de la version 1.2
    • RevConnect: La version 0403
    • BitSpirit: Version 3.2.2.215
    • Osiris: Version 0.6
    • RevConnect: DC ++ mod

liens externes