KAD算法及实现 郝伟 2020/06/03
1. 前言
KAD是一种基于离散值的随机组网算法，本代码主要用于Kad算法的模拟测试，以理解其工作原理。
2. 代码解释
在主函数中，首先会生成一个随机的Kad网络，然后通过输入起点ID和终点ID，返回查找过程。本Kad网络的容量为 2^8^，即共256个节点。
3. 源代码
// package test;
import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;
import static java.lang.System.out;
import java.io.IOException;
public class KadNode {
static Random rand = new Random(0);
static ArrayList<KadNode> nodes = new ArrayList<KadNode>();
public static void main(String[] args) throws IOException {
// create nodes.
for (int i = 0; i < 256; i++)
nodes.add(new KadNode(i));
// create neighbors
for (int i = 0; i < 100000; i++)
nodes.get(rand.nextInt(nodes.size())).ping(nodes.get(rand.nextInt(nodes.size())));
// print nodes
for (KadNode node : nodes)
System.out.println(node);
// by-hand testing
Scanner inp = new Scanner(System.in);
while (true) {
System.out.println("Please Input source id and target id:\n");
String input = inp.next();
if (input.equals("exit"))
break;
int srcid = Integer.parseInt(input.split(",")[0]);
int tarid = Integer.parseInt(input.split(",")[1]);
KadNode src = nodes.get(srcid);
System.out.printf("Search %d on %d...\n", tarid, srcid);
while (true) {
int nid = src.findNode(tarid);
if (nid > -1)
src = nodes.get(nid);
System.out.println(" -> found " + nid);
if (nid == -1 || nid - tarid == 0)
break;
}
}
}
public int id = 0;
public ArrayList<ArrayList<KadNode>> buckets = new ArrayList<ArrayList<KadNode>>();
public static final int BitLength = 8;
static int[] maxsizes = { 0, 1, 2, 4, 8, 8, 8, 8, 8, 8 };
static String[] bstr = { "00000000", "00000001", "00000010", "00000011", "00000100", "00000101", "00000110",
"00000111", "00001000", "00001001", "00001010", "00001011", "00001100", "00001101", "00001110", "00001111",
"00010000", "00010001", "00010010", "00010011", "00010100", "00010101", "00010110", "00010111", "00011000",
"00011001", "00011010", "00011011", "00011100", "00011101", "00011110", "00011111", "00100000", "00100001",
"00100010", "00100011", "00100100", "00100101", "00100110", "00100111", "00101000", "00101001", "00101010",
"00101011", "00101100", "00101101", "00101110", "00101111", "00110000", "00110001", "00110010", "00110011",
"00110100", "00110101", "00110110", "00110111", "00111000", "00111001", "00111010", "00111011", "00111100",
"00111101", "00111110", "00111111", "01000000", "01000001", "01000010", "01000011", "01000100", "01000101",
"01000110", "01000111", "01001000", "01001001", "01001010", "01001011", "01001100", "01001101", "01001110",
"01001111", "01010000", "01010001", "01010010", "01010011", "01010100", "01010101", "01010110", "01010111",
"01011000", "01011001", "01011010", "01011011", "01011100", "01011101", "01011110", "01011111", "01100000",
"01100001", "01100010", "01100011", "01100100", "01100101", "01100110", "01100111", "01101000", "01101001",
"01101010", "01101011", "01101100", "01101101", "01101110", "01101111", "01110000", "01110001", "01110010",
"01110011", "01110100", "01110101", "01110110", "01110111", "01111000", "01111001", "01111010", "01111011",
"01111100", "01111101", "01111110", "01111111", "10000000", "10000001", "10000010", "10000011", "10000100",
"10000101", "10000110", "10000111", "10001000", "10001001", "10001010", "10001011", "10001100", "10001101",
"10001110", "10001111", "10010000", "10010001", "10010010", "10010011", "10010100", "10010101", "10010110",
"10010111", "10011000", "10011001", "10011010", "10011011", "10011100", "10011101", "10011110", "10011111",
"10100000", "10100001", "10100010", "10100011", "10100100", "10100101", "10100110", "10100111", "10101000",
"10101001", "10101010", "10101011", "10101100", "10101101", "10101110", "10101111", "10110000", "10110001",
"10110010", "10110011", "10110100", "10110101", "10110110", "10110111", "10111000", "10111001", "10111010",
"10111011", "10111100", "10111101", "10111110", "10111111", "11000000", "11000001", "11000010", "11000011",
"11000100", "11000101", "11000110", "11000111", "11001000", "11001001", "11001010", "11001011", "11001100",
"11001101", "11001110", "11001111", "11010000", "11010001", "11010010", "11010011", "11010100", "11010101",
"11010110", "11010111", "11011000", "11011001", "11011010", "11011011", "11011100", "11011101", "11011110",
"11011111", "11100000", "11100001", "11100010", "11100011", "11100100", "11100101", "11100110", "11100111",
"11101000", "11101001", "11101010", "11101011", "11101100", "11101101", "11101110", "11101111", "11110000",
"11110001", "11110010", "11110011", "11110100", "11110101", "11110110", "11110111", "11111000", "11111001",
"11111010", "11111011", "11111100", "11111101", "11111110", "11111111", };
public KadNode() {
id = rand.nextInt(256);
for (int i = 0; i < 9; i++)
buckets.add(new ArrayList<KadNode>());
}
public KadNode(int id) {
this.id = id;
for (int i = 0; i < 9; i++)
buckets.add(new ArrayList<KadNode>());
}
// Returns the bucket id of the specified node n.
public int getBucketID(KadNode n) {
return getBucketK(n.id, getDistance(n.id, id));
}
// Returns the bucket id of the specified node id1 with the id2.
public int getBucketByID(int id1, int id2) {
return getBucketK(id1, id1 ^ id2);
}
/**
* Return the number of k-th bucket, i.e the value of k.
*
* @param id The node id.
* @param distance The xor result of node id and target id.
* @return
*/
public static int getBucketK(int id, int distance) {
int d = distance, v = 0b10000000, k = 8;
do {
if ((d & v) > 0)
break;
v = v >> 1;
k--;
} while (k > 0);
return k;
}
public static int getDistance(int id1, int id2) {
return id1 ^ id2;
}
static void test1() {
KadNode n1 = new KadNode();
KadNode n2 = new KadNode();
for (int i = 0; i < 256; i++) {
n2.id = i;
out.println(bstr[n1.id] + " to " + bstr[i] + " -> " + n1.getBucketID(n2));
}
}
public void ping(KadNode node) {
if (node != null && node.id != this.id)
node.accept(this);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("ID: " + id);
for (int i = 0; i < buckets.size(); i++) {
sb.append(" " + i + ": ");
for (KadNode node : buckets.get(i))
sb.append(node.id + " -> ");
sb.append("END\n");
}
return sb.toString();
}
private void accept(KadNode node) {
int bid = this.getBucketID(node);
// out.println("bid = " + bid + ", buckets.size() = " + buckets.size());
ArrayList<KadNode> bk = buckets.get(bid);
if (bk.contains(node)) {
bk.remove(node);
bk.add(node);
} else {
if (bk.size() < maxsizes[bid])
bk.add(node);
else {
// TODO: evict several least recently nodes that do not response
}
}
}
// find node by id
public int findNode(int id) {
int bid = getBucketByID(this.id, id);
return buckets.get(bid).size() == 0 ? -1
: buckets.get(bid).stream().sorted((n1, n2) -> Integer.compare(n1.id ^ id, n2.id ^ id))
.findFirst().get().id;
}
}
4. 数据
ID: 0 0: END
1: 1 -> END
2: 2 -> 3 -> END
3: 5 -> 6 -> 7 -> 4 -> END
4: 10 -> 11 -> 8 -> 12 -> 9 -> 15 -> 14 -> END
5: 27 -> 23 -> 29 -> 21 -> 28 -> 18 -> 24 -> 25 -> END
6: 60 -> 55 -> 45 -> 56 -> 42 -> 61 -> 47 -> 35 -> END
7: 107 -> 87 -> 85 -> 73 -> 83 -> 104 -> 89 -> 71 -> END
8: 153 -> 244 -> 193 -> 148 -> 129 -> 144 -> 205 -> 200 -> END
ID: 1 0: END
1: 0 -> END
2: 3 -> 2 -> END
3: 6 -> 4 -> END
4: 9 -> 13 -> 14 -> 15 -> 10 -> 12 -> 8 -> 11 -> END
5: 20 -> 19 -> 17 -> 28 -> 22 -> 16 -> 27 -> 29 -> END
6: 43 -> 41 -> 36 -> 48 -> 37 -> 63 -> 35 -> 59 -> END
7: 78 -> 70 -> 95 -> 101 -> 82 -> 94 -> 104 -> 66 -> END
8: 164 -> 137 -> 199 -> 248 -> 158 -> 237 -> 170 -> 207 -> END
ID: 2 0: END
1: 3 -> END
2: 0 -> END
3: 7 -> 6 -> 5 -> END
4: 12 -> 14 -> 15 -> 10 -> 8 -> 13 -> 9 -> END
5: 31 -> 16 -> 30 -> 22 -> 29 -> 18 -> 27 -> 21 -> END
6: 42 -> 41 -> 50 -> 36 -> 48 -> 47 -> 52 -> 63 -> END
7: 118 -> 114 -> 83 -> 111 -> 70 -> 77 -> 119 -> 123 -> END
8: 212 -> 187 -> 213 -> 236 -> 243 -> 252 -> 205 -> 139 -> END
ID: 3 0: END
1: 2 -> END
2: 1 -> 0 -> END
3: 7 -> 4 -> 5 -> END
4: 15 -> 13 -> 11 -> 10 -> 8 -> 14 -> 9 -> 12 -> END
5: 29 -> 22 -> 17 -> 18 -> 27 -> 25 -> 16 -> 26 -> END
6: 40 -> 57 -> 49 -> 36 -> 45 -> 33 -> 35 -> 37 -> END
7: 105 -> 67 -> 86 -> 110 -> 117 -> 79 -> 127 -> 73 -> END
8: 247 -> 231 -> 232 -> 135 -> 139 -> 209 -> 211 -> 204 -> END
#（中间省略约2500行）
ID: 251 0: END
1: 250 -> END
2: 249 -> 248 -> END
3: 254 -> 253 -> 252 -> END
4: 244 -> 242 -> 245 -> 243 -> 246 -> END
5: 225 -> 231 -> 226 -> 239 -> 234 -> 236 -> 232 -> 227 -> END
6: 214 -> 204 -> 209 -> 220 -> 196 -> 202 -> 197 -> 222 -> END
7: 158 -> 144 -> 133 -> 191 -> 189 -> 187 -> 128 -> 172 -> END
8: 31 -> 101 -> 126 -> 80 -> 20 -> 65 -> 97 -> 95 -> END
ID: 252 0: END
1: 253 -> END
2: 255 -> 254 -> END
3: 250 -> 249 -> 248 -> 251 -> END
4: 240 -> 245 -> 247 -> 244 -> 246 -> 242 -> END
5: 230 -> 227 -> 233 -> 238 -> 232 -> 224 -> 236 -> 229 -> END
6: 207 -> 215 -> 196 -> 218 -> 208 -> 213 -> 219 -> 203 -> END
7: 179 -> 134 -> 154 -> 141 -> 177 -> 132 -> 142 -> 164 -> END
8: 64 -> 27 -> 0 -> 9 -> 97 -> 54 -> 102 -> 25 -> END
ID: 253 0: END
1: END
2: 254 -> END
3: 249 -> 250 -> 248 -> 251 -> END
4: 246 -> 240 -> 242 -> 243 -> 247 -> 244 -> 241 -> END
5: 228 -> 238 -> 237 -> 233 -> 232 -> 226 -> 227 -> 230 -> END
6: 204 -> 208 -> 199 -> 209 -> 217 -> 220 -> 219 -> 195 -> END
7: 175 -> 148 -> 177 -> 129 -> 131 -> 159 -> 166 -> 134 -> END
8: 123 -> 41 -> 46 -> 58 -> 75 -> 79 -> 23 -> 82 -> END
ID: 254 0: END
1: END
2: 252 -> END
3: 251 -> 250 -> 249 -> 248 -> END
4: 245 -> 244 -> 246 -> 242 -> 241 -> 240 -> END
5: 239 -> 226 -> 224 -> 225 -> 231 -> 238 -> 228 -> 233 -> END
6: 206 -> 221 -> 204 -> 199 -> 193 -> 216 -> 217 -> 194 -> END
7: 151 -> 138 -> 141 -> 180 -> 164 -> 158 -> 147 -> 128 -> END
8: 19 -> 18 -> 106 -> 34 -> 74 -> 76 -> 101 -> 71 -> END
ID: 255 0: END
1: 254 -> END
2: 253 -> 252 -> END
3: 251 -> 248 -> 249 -> END
4: 245 -> 244 -> 246 -> 240 -> 247 -> 243 -> 241 -> 242 -> END
5: 224 -> 231 -> 229 -> 225 -> 238 -> 234 -> 227 -> 233 -> END
6: 222 -> 197 -> 196 -> 206 -> 193 -> 207 -> 195 -> 201 -> END
7: 149 -> 164 -> 143 -> 155 -> 138 -> 160 -> 146 -> 166 -> END
8: 79 -> 90 -> 22 -> 38 -> 93 -> 61 -> 66 -> 70 -> END
Please Input source id and target id:
1,4
Search 4 on 1...
Looking for 4
-> found 4
Please Input source id and target id:
1,252
Search 252 on 1...
Looking for 252
-> found 248
-> found 252
Please Input source id and target id:
exit