KAD网络模拟调研和初步设计报告.docx
《KAD网络模拟调研和初步设计报告.docx》由会员分享，可在线阅读，更多相关《KAD网络模拟调研和初步设计报告.docx（11页珍藏版）》请在冰点文库上搜索。
KAD网络模拟调研和初步设计报告
Kademlia网络模拟
调研和初步设计报告
撰写人：
单子非，王文虎
组员名单
由于涉及隐私，故下文用路人甲乙丙丁代替。
目录
问题调研
调研目标
调研方法
主要调研结果
其他相关信息
系统功能设计
项目初步分工
附录1：
主要参考文献和资料
附录2：
要求组员注意的代码规范
问题调研
调研目标
研究KAD网络的实现机理，对KAD网络的运行过程形成清楚的认识，找到模拟KAD网络的方法步骤。
并在调研过程中锻炼每位组员的能力，组员之间相互了解和沟通，建立初步的默契。
调研方法
组员充分阅读文献资料，形成各自的认识并发现问题，之后小组进行集体讨论，统一对KAD网络的认识，形成系统清晰的思路。
主要调研结果
Kademlia（KAD）协议是一种分布式哈希表（DHT）技术，不过和其他DHT实现技术比较，如Chord、CAN、Pastry等，KAD通过以异或（XOR）算法为距离度量基础，建立了一种全新的DHT拓扑结构，提高了路由查询速度。
1、节点
KAD中节点可以被看作二叉树的叶子，其位置由其ID值的最短前缀唯一的确定。
对于任意节点，都可以把这颗二叉树分解为一系列连续且不包含自己的子树。
最高层的子树，由整棵树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整棵树。
节点的ID值在节点加入网络时得到，并保持不变。
ID是节点的标识符，与IP地址和UDP端口一同作为节点的基本信息被存储。
2、节点距离
KAD网络中每个节点都有一个32bit（实际应用中为160bit）的ID值作为标志符，每一个加入KAD网络的计算机都会被分配一个32位二进制数作为节点ID值。
判断两个节点的距离远近是基于数学上的异或的二进制运算，即两个节点距离为其节点ID异或得到的二进制数。
异或又称为环和，具有循环特性。
采用异或操作作为距离的度量方法，可以将全部ID映射到一个环上（比如，采用格雷码作为映射方法）。
3、节点路由表
KAD中每个节点维护一个路由表，用以保存如何连接到其他节点的信息。
路由表是通过一些称之为K桶的表格构造起来的。
对每一个0≦i<32，对应一个K桶，保存着与本节点已知距离介于区间[2^i,2^（i+1）]的若干个节点的信息。
K桶中存储的信息有：
节点ID、节点IP地址和UDP端口信息（题目的基本要求只保存节点ID）。
本题目中要求每个K桶中保存最多10个节点信息，其中信息更新依据Least-recentlySeenEviction原则。
节点与K桶的关系如下图所示：
节点0
节点1
……
……
节点n-1
节点n
图1：
K桶结构示意图
进一步分析，每一个K桶实际上都对定位了ID的一个二进制位。
根据异或的运算性质分析，可以得到K桶中ID的储存规律。
设节点的ID为id，对于该节点第i位的K桶，满足：
K桶中的节点ID的第i位与id的第i位不同，第i+1—31位与id的第i+1—31位相同。
如下表：
（设ID简化为5位，K桶容量简化为5个节点）
节点ID
11001（由高到低）
K桶位数
0
1
2
3
4
内容规律
11000
1101X
111XX
10XXX
0XXXX
K桶可能的存放内容
11000
11010
11100
10000
00000
11011
11101
10001
01000
11110
10010
00010
11111
10011
00110
10100
01111
图2：
K桶内节点ID规律示意图
由此我们可以看到，低位的K桶定位更加精准，且难以达到桶满状态；高位的K桶低位都是随意的，定位不够精准，且容易达到桶满状态。
K桶的信息更新机制如下：
每当节点x收到一个远程操作消息（包括下面要提到的四种消息）时，都要用发送者y的节点信息更新自己的K桶。
具体步骤为：
1．计算自己和发送者的距离：
d（x,y）=ID（x）xorID（y）。
2．通过距离d选择对应的K桶进行更新操作：
3．如果y的IP地址已经存在于这个K桶中，则把对应项移到该K桶的尾部。
4．如果y的IP地址没有记录在该K桶中：
⑴如果该K桶的记录项小于k个，则直接把y的（IPaddress,UDPport,NodeID）信息插入队列尾部。
⑵如果该K桶的记录项大于k个，则选择k桶头部的节点z进行PING操作：
1如果z没有响应，则从K桶中移除z的信息，并把y的信息插入队列尾部
2如果z有响应，则把z的信息移到队列尾部，同时忽略y的信息。
（这种操作基于“长时间在线的节点，未来长时间在线的可能性更大”的统计规律）
4、KAD网络基本操作
KAD协议包括四种远程操作：
PING、STORE、FIND_NODE、FIND_VALUE。
注意这四种消息都是要即时更新接受者的K桶的。
PING操作：
探测一个节点是否在线。
（分布式版本需要）
STORE：
通知一个节点储存一个对，以便日后查询需要。
Key值为资源ID，也是32位二进制数，用散列算法得到；value是资源信息，可以用来存放资源的实际地址，这样即可实现分布式网络的资源查找。
（即为题目要求的Put操作）
发布资源时，资源用散列算法得到一个ID，这个ID在网络上很可能是没有对应节点的。
我们找到距离这个ID最近的几个节点，将这个资源的信息存放在这些节点上面，以便查找发布者。
FIND_NODE（ID,k）：
使用一个32bit的ID作为参数。
返回节点所知道的更接近目标ID的k个节点的信息。
这些节点的信息可以从一个单独的K桶获得，也可以从多个K桶获得（如果最接近目标ID的K桶未满）。
不管是哪种情况，接受者都将返回K个节点的信息给操作发起者。
如果接受者存储的节点总数不到K个，则返回全部存储节点。
FIND_VALUE（key）：
和FIND_NODE操作类似，不同的是它只需要返回一个节点的（IPaddress,UDPport,NodeID）信息。
如果本操作的接受者存有所查找的key的value，则会直接返回存储的value值（资源信息）。
5、路由查询
通过K桶实现路由（查找）操作时，将由远及近，依次定位节点ID，在O（logN）（N为ID空间，此处为232）的时间内完成查询操作。
具体步骤如下：
（注意使用迭代而不是递归）
在节点查询的时候，它先得到它K桶中离所查询的键值最近的K（题目要求为5）个节点，然后向这K个节点发起FIND_NODE消息请求，消息接收者收到这些请求消息后将在他们的K桶中进行查询，如果他们知道离被查键更近的节点，他们就返回这些节点（最多K个）。
消息的请求者在收到响应后将使用它所收到的响应结果来更新它的结果列表，这个结果列表总是保持K个响应FIND_NODE消息请求的最优节点（即离被搜索键更近的K个节点）。
然后消息发起者将向这K个最优节点发起查询，不断地迭代执行上述查询过程。
如果本次响应结果中的节点没有比前次响应结果中的节点离被搜索键值更近了，这个查询迭代也就终止了。
当这个迭代终止的时候，响应结果集中的K个最优节点就是整个网络中离被搜索键值最近的K个节点。
6、加入网络
想要加入网络的节点首先要经历一个引导过程。
在引导过程中，节点需要知道其他已加入该网络的某个节点的IP地址和端口号（可从用户或者存储的列表中获得）。
假如正在引导的那个节点还未加入网络，它会计算一个目前为止还未分配给其他节点的随机ID号，直到离开网络，该节点会一直使用该ID号。
正在加入Kademlia网络的节点在它的某个K桶中插入引导节点（负责加入节点的初始化工作），然后向它的唯一邻居（引导节点）发起FIND_NODE操作请求来定位自己，这种“自我定位”将使得Kademlia的其他节点（收到请求的节点）能够使用新加入节点的节点ID填充他们的K桶，同时也能够使用那些查询过程的中间节点（位于新加入节点和引导节点的查询路径上的其他节点）来填充新加入节点的K桶。
七、发布和获取资源
结点发布资源的过程为：
先计算资源的ID（通过散列函数），资源ID与结点ID一样，是一个32位二进制数；寻找距离ID最近的k（5）个结点，用STORE操作通知他们存储资源信息（资源ID，资源所在节点信息）对。
查找资源时，凭借资源的散列得到的ID，到距离ID最近的k个结点询问资源地址，再访问资源地址获取资源。
其他相关信息
关于拓展实现中的分布式版本，我们需要利用网络编程的相关技术，来实现网络传输。
可以利用的技术有：
朴素的windowssocket编程库，或boost库中的网络部分和多线程部分。
服务器端（Server）的基本操作有：
初始化，创建套接字（socket），bind套接字，侦听（listen）套接字，接受（accept）连接，收发数据，断开连接。
客户端（Client）的基本操作有：
初始化，创建套接字（socket），连接服务器，收发数据，断开连接。
需要注意数据发送中，网络环境可能是不稳定的，有可能出现数据发送中断开或发送超过需要量的情况。
因此需要注意对接收的数据流的安全处理。
可以考虑对数据包进行断点续传，必要时可要求重新传输。
系统功能设计
本系统将实现如下功能：
一、完成上文提到的Kademlia网络操作的全部模拟。
二、采取分布式版本设计实现网络模拟。
具体如下：
a）能够利用windowssocket库或boost库，进行网络连接。
b）可以实现在多台机器上的互联以及多线程之间的互联。
c）为使本系统既能满足题目测试要求，又具有实用价值，将允许在每个程序进程中插入多个节点。
即：
允许多个不同ID的节点共用一个IP地址和UDP端口。
这样一来，每个程序就可以模拟实现网络中的多个客户端；又可以模拟多个程序、多台机器上的不同客户端。
d）本系统期望实现在线数据传输、下载的功能。
三、使用MFC进行界面编程。
由于本系统期望具有一定的实用性，因此应该具有友好而功能丰富的界面。
由于MFC与C程序的易整合性，我们将利用MFC进行界面编程。
项目初步分工
每个组员都应该充分了解项目的整体框架，并熟悉其他人的工作。
每个组员都应独立提交自己的cpp文件，并经过充分的调试，严格确保自己提交的代码的正确性。
每个组员提交的cpp文件应该严格遵守代码规范，并进行规范、充足的注释。
项目分工：
路人甲：
主要负责MFC界面编程部分；
设计系统框架；
设计头文件和函数接口；
进行系统的整合与调试；
修改和完善文档。
路人乙：
主要负责网络编程的实现：
PING、STORE、FIND_NODE、FIND_VALUE函数的实现。
保证网络数据传输的稳定性和安全性。
实现多线程的支持。
路人丙：
实现KAD协议的基本操作。
（需要用到高可言编写的网络部分函数接口）
实现一些基于KAD协议底层功能的扩展性操作。
路人丁：
协助实现KAD协议的基本操作；
实现一些其他可能的优化；
撰写实习报告、程序文档等。
附录1：
主要参考文献和资料
XX百科Kademlia：
维基百科Kademlia（中文翻译）：
http:
//zh.wikipedia.org/zh-cn/Kademlia
Windows网络编程库（MSDN）：
Boost库中的网络编程部分：
http:
//www.boost.org/doc/libs/1_42_0/doc/html/boost_asio.html
C++Reference：
附录2：
要求组员注意的代码规范
我是这篇文章的注释
首先，推荐使用VS2008进行编程。
文件头需要加的注释：
//文件名称：
//项目名称：
//创建者：
//创建时间：
//最后修改时间：
//功能：
//与其他文件的依赖关系：
需要包含"TS.h"，"classes.h"两个文件
#include"foo.h"
#include"bar.h"
#include
在文件开始部分，要引用要求给出的若干头文件。
全局的include命令、库引用命令、全局变量声明、全局函数声明、类的声明，都要放在头文件里。
不在其他文件里使用的头文件，可以在文件里单独引用。
讲一下全局变量的声明：
要把extern（外部）关键字加在每个变量的前面，像这样：
externcharthe_name[256][256];
如果不加extern的话可是会被当做变量定义的。
而且在变量的声明里是不能初始化的，比如
externcharthe_name[256][256]={};
这就是不行的。
逻辑上有分隔的单元之间空一行。
注释统一使用//，尽量不要用/**/。
相邻行的注释尽量使用tab对齐。
尽量不要使用全局变量。
函数头要写如下注释：
//函数名称：
ClassA:
:
FuncA
//函数功能描述：
解释一下这个函数是干什么的。
写呀写呀写呀写呀，换一行
//空两格，接着写……每行字符数最好不超过99个，中文算两个字符
//函数的输入参数：
（没有的话这一行就删掉）
//返回值：
（没有的话这一行就删掉）这些注释是顶着下面的函数名写的，中间不要空行
DTNode*DTNode:
:
GetLeftChild（）{注意花括号前面要空一格，不要顶着小括号写
returnleft;
要培养好的代码风格，空格是要特别注意的：
以下运算符前后都不加空格：
.（点）->（箭头）:
:
（作用域运算符）等
以下运算符只有后面加空格：
（逗号，这个挺重要）:
（冒号，初始化列表里可能用到）
其他大部分运算符两边都加空格，比如：
+-*/===!
=
还有一些小的地方，比如二维数组]和[之间不能加空格啦……
另外行尾最好不要有多余空格。
}
要培养好的代码风格，函数名和变量名是要特别注意的：
形成一套自己的规范就好。
我的习惯是：
函数名不加下划线，每个单词首字母大写，本身就由大写字母组成的单词都大写。
如：
GetID，GetInfo，WeAreEECSers
变量名单词之间加下划线，没有大写，如num_books
如果有全局变量，在前面加the。
如the_macs
升级会员 