Monday, August 10, 2015

Let's coding mainline dht.(2) About kBucket RootingTable

My English skill is poor. If I make mistakes in my English,please pardon me.
I will make description and implementation about Mainline DHT.

MainlineDHTはKademuliaのkBucketを利用している

  • Mainline DHT use Kademulia
  • Mainline DHT distance is XOR
  • Mainline DHT have kBucket RootingTable

Torrent support DHT is Kademulia.(http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf)
I explain kBucket and rooting table in this section.

Mainline DHT use XOR distance

 I exlaine that DHT must to define distance in previous section. Kademulia use xor distance as DHT distance definition.
Do you know how about xor distance? Would you try check with me about xor distance!!

- It cab be express number as binary

Number can be express as binary in computer science.  Binary have only 1 and 0. for example, 256 can express as 11111111 , 1 can express as 00000001, 2 ca express as 00000010, 3 can expressed as 00000011 and 5 can express as 0000101.

- calculate XOR after converting binary

  We can get xor distance to calculate xor after converting binary. and I write as A ^ B , to be calulate xor A and B .

First, what is xor? xor is logical operation. that is outputs true only when both inputs differ,

Value AValue B A ^ B 
110
101
011
110

This logical operation execute about each digit.
"256(11111111) ^ 3(00000011) --> 252 (11111100)"and "252 (11111100) ^ 256(11111111) --> 3(00000011)"

XOR is symmetric distance 

XOR is symmetric distance,  It is same value A ^ B  and B ^ A .
For example. "256(11111111) ^ 3(00000011) --> 252 (11111100)"" 3(00000011) ^ 256(11111111) --> 252 (11111100)".

KBucket and  RootingTable come together, It will appear excellent features.


MainLine DHT use kBucket's RootingTable

I explain DHT have peer list in previous section.  and peer list have bias.   Kademulia use kBucket RootingTable to realize those characteristic.

kBucket is container that  K of peer, grouping. Only that. kBucket cound not cotain more than  K.  if cotain more peer info, We must to remove peer info from kBucket.

Kademulia 's RootingTable can possess K of kBucket, 0-160.  those kBucket can possess,  smaller than 0st power of 2 ,  1st power of 2,  and Kst power of 2.

It's slightly complicated, isn't it? I'll see specifically.

The intuitive structure to be convert a figure.

First,  Would you check xor distance!! but , this part use 3bit ID. Because it's promotion to handle  160bit (20byte).

Value BinaryA ^ 010table index
000022
100132
201000
301111
410063
510173
611043
711153

as above table. I wrote about a peer which's id is 010.
for example, In case of value is 5, Binary is 101, xor distance is 7, and kBucket's number is 3.



Next , show figure. How is it?  Isn't it intuitive arrangement? Every time a branch moves, the value of index becomes big.


PS

----------
Kyorohiro work

No comments:

Post a Comment