Блог

Я пытаюсь реализовать Kademlia (двоичное дерево) DHT на python. Насколько я понимаю, таблица маршрутизации должна сравнивать отдельные биты из идентификатора корневого узла с новой записью. Если биты идентификатора не совпадают, вы идете налево, если они совпадают, вы идете направо. Это можно сделать рекурсивно, и условием остановки является либо то, что вы достигли конца длины идентификатора, либо то, что вы достигли конечного узла. Тогда каждый конечный узел содержит свой собственный kbucket (массив).

В настоящее время я попробовал следующее:

 #!/usr/bin/python

class Node:
    def __init__(self, id, data):
        self.id = id
        self.data = data
        self.left = None
        self.right = None

    def __str__(self):
        return '{id:'   self.id   ','   self.data   '}'

class Tree:
    def __init__(self):
        self.root = None

    def find_placement(self, node, previous_node, id_index):
        if (node == None):
            return previous_node, id_index
        elif (node.right == None and node.left == None):
            return node, id_index
        elif (node.id[id_index] == previous_node.id[id_index]):
            return self.find_placement(node.right, node, id_index 1)
        elif (node.id[id_index] != previous_node.id[id_index]):
            return self.find_placement(node.left, node, id_index 1)
 
    def add(self, id, data):
        new_node = Node(id, data)
        if (self.root == None):
            self.root = new_node
            return
        previous_node = current_node = self.root
        id_index = 0
        current_node, id_index = self.find_placement(current_node, previous_node, id_index)
        if (current_node.id[id_index] == new_node.id[id_index]):
            current_node.right = new_node
        elif (current_node.id[id_index] != new_node.id[id_index]):
            current_node.left = new_node
        new_node.parent = current_node

    def printtree(self, node=None, level=0, lr = ''):
        if (node == None):
            node = self.root
        
        print (lr, level, node)
        if (node.left != None):
            self.printtree(node.left, level 1, 'L')
        if (node.right != None):
            self.printtree(node.right, level 1, 'R')



if __name__ == "__main__":
    t = Tree()
    t.add('0000','test')
    t.add('0100','test')
    t.add('0010','test')
    t.add('0001','test')
    t.add('0101','test')

    t.printtree()

  

В настоящее время я пытаюсь найти конечный узел, дочерним элементом которого может быть новый узел.

Может ли кто-нибудь помочь мне понять, что именно я делаю неправильно? Если я пропустил что-то необходимое, я заранее приношу извинения и приветствую любые предложения о том, как я мог бы улучшить этот пост!

Я думаю, в чем моя проблема:

В настоящее время мои узлы сортируются в соответствии с первым битом, который противоречит биту с тем же индексом корневого узла. Вместо этого мне нужно отсортировать узлы таким образом, чтобы самый правый узел был вашим собственным узлом после начальной загрузки.

Если это так, каким будет корневой узел? Есть ли способ сделать это, когда корневой узел является вашим собственным узлом, сохраняя при этом целостность сети?

После добавления нового узла в сеть, как мне реструктурировать дерево, чтобы поддерживать правило, согласно которому ветви, которые вы проходите (каждая новая ветвь), представляют один бит в идентификаторе конечного узла? До такой степени, что крайний правый узел является ближайшим к вашему собственному узлу, а крайний левый будет самым удаленным.

Подробнее о дереве можно узнать здесь: https://www.researchgate.net/publication/2492563_Kademlia_A_Peer-to-peer_Information_System_Based_on_the_XOR_Metric