Tuesday, August 11, 2015

Let's coding mainline dht.(3) implements 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.

Let's coding RootingTable

  • Implements KId
  • Implements kBucket
  • Implements RootingTable
Let's coding RootingTable,

Implements KID

express  InfoHash and PeerID as KID.

We must tot calc xor distance of InfoHash and InfoHash, Peer ID and InfoHash, Peer ID and Peer. Those ID can define 20 byte array.  It's call KID in sentense.

- It isn't necessary to change KID into the numerical value.

KID is 160bit valiue. but, dartlang support 53bit only. SO I have usually implemented biginteger. but It isn't necessary to change KID into the numerical value to use in kbucket rooting table.

First.  First definition, KID has 20 byte array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class KId {
  List<int> _values = null;
  List<int> get value => new List.from(_values);
  KId(List<int> id) {
    if(id == null || id.length != 20) {
      throw {};
    }
    this._values = new Uint8List.fromList(id);
  }
  int get length => _values.length;
  int operator [](int idx) => _values[idx];
  Iterator<int> get iterator => _values.iterator;
}

- add  func that calc xor 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class KId {
  ...
  ...
  ...
  KId xor(KId b, [KId output = null]) {
    if (output == null) {
      output = new KId.zeroClear();
    }
    for (int i = 0; i < b._values.length; i++) {
      output._values[i] = this._values[i] ^ b._values[i];
    }
    return output;
  }
}

- add func that big small comparison

We must to add big and small comparison function to sort KID in rooting table.
We has become possible to find close peer in  KID list by sorting function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class KId {
  ...
  ...
  ...
  bool operator >(KId b) {
    for (int i = 0; i < b._values.length; i++) {
      if (this._values[i] == b._values[i]) {
        continue;
      } else if (this._values[i] > b._values[i]) {
        return true;
      } else {
        return false;
      }
    }
    return false;
  }

  bool operator ==(KId b) {
    for (int i = 0; i < b._values.length; i++) {
      if (this._values[i] != b._values[i]) {
        return false;
      }
    }
    return true;
  }

  bool operator >=(KId b) {
    return (this == b ? true : (this > b ? true : false));
  }

  bool operator <(KId b) {
    return (this == b ? false : !(this > b));
  }

  bool operator <=(KId b) {
    return (this == b ? true : (this > b ? false : true));
  }
}

https://github.com/kyorohiro/dart_hetimatorrent/tree/master/lib/src/dht


Implements kBucket

kBucket is container that can contain K-number of peer info. We can implements as list with limit on when you want to add value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class KBucket {
  int _k = 8;
  int get k => _k;
  List<KPeerInfo> peerInfos = null;

  KBucket(int kBucketSize) {
    this._k = kBucketSize;
    this.peerInfos = [];
  }

  add(KPeerInfo peerInfo) {
    if (peerInfos.contains(peerInfo) == true) {
      peerInfos.remove(peerInfo);
    }
    peerInfos.add(peerInfo);
    if (peerInfos.length > k) {
      peerInfos.removeAt(0);
    }
  }

  int get length => peerInfos.length;
  KPeerInfo operator [](int idx) => peerInfos[idx];
  Iterator<KPeerInfo> get iterator => peerInfos.iterator;
}

https://github.com/kyorohiro/dart_hetimatorrent/tree/master/lib/src/dht


Implements RootingTable

Rooting table has 161- number of kBucket.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class KRootingTable {
  List<KBucket> _kBuckets = [];
  int _kBucketSize = 0;

  KRootingTable(int k_bucketSize) {
    this._kBucketSize = k_bucketSize;
    for (int i = 0; i < 161; i++) {
      _kBuckets.add(new KBucket(k_bucketSize));
    }
  }
}


Implements calc rooting table index.

I explain kid into the numerical value to calc rooting table index in previous section.

2進index
00001
2, 3010, 0112
4, 5, 6, 7 100, 101, 110, 1113

And went to check one by 1bit from left to right, by the first place was a 1, you will see that kBucket position is determined.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class KRootingTable {
  List<KBucket> _kBuckets = [];
  int _kBucketSize = 0;
  KId _ownerKId = null;
  KId get ownerKId => _ownerKId;

  KRootingTable(int k_bucketSize, KId ownerKId) {
    this._kBucketSize = k_bucketSize;
    for (int i = 0; i < 161; i++) {
      _kBuckets.add(new KBucket(k_bucketSize));
    }
    this._ownerKId = ownerKId;
  }

  int getRootingTabkeIndex(KId v) {
    // calc xor
    v = v.xor(_ownerKId);

    // clac index
    for (int i = 0, ret = 19; i < 20; i++, ret--) {
      if (v[i] != 0) {
        for (int j = 0; j < 9; j++) {
          if (v[i] < (0x1 << j)) {
            return (ret * 8) + j;
          }
        }
        return i;
      }
    }
    return 0;
  }
}

Add peer info in kBucket.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class KRootingTable {
  ...
  ...
  ...
  Future update(KPeerInfo info) {
    return new Future(() {
      _kBuckets[getRootingTabkeIndex(info.id)].add(info);
    });
  }
  ...
  ...
}

Now, the creation of RootingTable is complete.  I will explain findNode in next section. and append fincNode function in RootingTable class.

Ref

http://www.bittorrent.org/beps/bep_0005.html
http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

- GitBook Nazenani Torrent for japanese

https://www.gitbook.com/book/kyorohiro/doc_hetimatorrent/details

- kyorohiro work torrent library and dht demo

 https://github.com/kyorohiro/dart_hetimatorrent
 https://github.com/kyorohiro/dart_hetimatorrent/tree/master/example/TorrentDHT

-------
Kyorohiro work

http://kyorohiro.strikingly.com

No comments:

Post a Comment