EMULE中KADEMLIA协议具体实现完整版课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《EMULE中KADEMLIA协议具体实现完整版课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- EMULE KADEMLIA 协议 具体 实现 完整版 课件
- 资源描述:
-
1、EMULEEMULE中中KADEMLIAKADEMLIA协议具体实协议具体实现现20072007年年6 6月月1919日日1 1目录Kademlia简介及应用现状节点本地行为节点初始化读取配置文件生成ID构造本地二叉树二叉树生成规则生成k-bucket节点之间的交互行为节点间距离加入网络发送加入网络请求处理请求响应查找查找其他节点查找文件(key)对查找二叉树的使用路由信息的更新现在已知节点是否仍然有效更新二叉树更新k-bucket存储发布节点自身要求其他相关节点存储发布文件信息,其他相关节点存储2 2KADEMLIA简介Kademlia协议是美国纽约大学的 Petar P.Maymounko
2、v和David Mazieres 在2002年发布的一项研究结果Kademlia:A peer-to-peer information system based on the XOR metric。Kademlia 是一种分布式哈希表(DHT)技术,Kademlia通过独特的以异或算法(XOR)为距离度量基础,建立了一种全新的DHT 拓扑结构,相比于其他算法,大大提高了路由查询速度。3 3当前应用现状在2005 年5 月著名的BitTorrent 在4.1.0 版实现基于Kademlia 协议的DHT 技术后,很快国内的BitComet 和BitSpirit 也实现了和BitTorrent 兼
3、容的DHT 技术,实现trackerless 下载方式。另外,emule 中也很早就实现了基于Kademlia 类似的技术(BT中叫DHT,emule 中也叫Kad,),和BT 软件使用的Kad 技术的区别在于key、value 和node ID 的计算方法不同。4 4EMULE中KADEMLIA网络部分CKademlia是整个Kademlia网络的主控类,可以直接开始或者停止Kademlia网,并且含有Process方法来处理日常事务。CPrefs负责处理自身的Kademlia相关信息,如自身的ID等。CRoutingZone,CRoutingBin和CContact三个类组成了每个节点所了
4、解的联系信息以及由这些联系信息所组成的数据结构。CKademliaUDPListener负责处理网络信息。CIndexed负责处理本地存储的索引信息。CSearch,CSearchManager负责处理和搜索有关的操作,其中前者表示的是一个单一的搜索任务,后者负责对所有搜索任务进行处理。CUInt128负责处理一个128位的长整数,并且内置其各种运算。5 5节点本地行为6 6节点初始化读取本地配置文件在emule中,配置文件比较多,用于Kademlia网络的配置文件是:src_index.dat key_index.dat load_index.dat(索引Indexed.cpp)nodes.
5、dat(上次程序启动时连接上的节点 RoutingZone.cpp)preferencesKad.dat(上次程序启动时本地节点的IP、ID、Port信息 Prefs.cpp)生成IDKad 网络中每个节点都有一个160bit 的ID值作为标志符。节点ID 的生成,可以是根据特定信息Hash或者简单的随机生成(emule中ID为随机生成)。在emule中,CUInt128类中定义了ID的生成方式,结点之间ID做的异或运算也在CUInt128里;emule中定义了4个ULong的数组,总共正好是128位;在Prefs.cpp中Init函数中对m_uClientID进行了随机值的设置:m_uCli
6、entID.SetValueRandom();函数中调用 cryptlib中的函数生成16位的数据块,然后填充,填充8次,共128位;7 7构造本地结点二叉树在Kad 网络中,所有节点都被当作一颗二叉树的叶叶子子,并且节点的位置都由其ID值的最短前缀唯一的确定。每一个节点都在本地维护一个二叉树,来标示网络中节点与自己的距离远近,自己则是二叉树的根节点;本地结点二叉树生成规则:最高层的子树,由整颗树不包含自己的树的另一半组成;下一层子树由剩下部分不包含自己的一半组成;依此类推,直到分割完整颗树。8 8每一个节点都在本地维护一个二叉树,来标示网络中节点与自己的距离远近,自己则是二叉树的根节点;否则
7、测量自己和t 的距离,并从自己对应的K 桶中选择 个节点的信息给x。在emule中,配置文件比较多,用于Kademlia网络的配置文件是:计算到t 的距离:d(x,y)=x y也就是说,每个结点都对自己附近的情况非常了解,而随着距离的增大,了解的程度不断降低降低。dat(上次程序启动时连接上的节点 RoutingZone.由于每次查询都能从更接近目标节点的K 桶中获取信息,这样的机制保证了每一次递归操作都能够至少获得距离减半(或距离减少1bit)的效果,从而保证整个查询过程的收敛速度为O(logN),这里N 为网络全部节点的数量。否则测量自己和t 的距离,并从自己对应的K 桶中选择 个节点的信
8、息给x。在2005 年5 月著名的BitTorrent 在4.需要说明的是,只有第一步查询的节点101,是节点0011 已经知道的,后面各步查询的节点,都是由上一步查询返回的更接近目标的节点,这是一个递归操作的过程。在Kad 网络中,所有节点都被当作一颗二叉树的叶子,并且节点的位置都由其ID值的最短前缀唯一的确定。另外,emule 中也很早就实现了基于Kademlia 类似的技术(BT中叫DHT,emule 中也叫Kad,),和BT 软件使用的Kad 技术的区别在于key、value 和node ID 的计算方法不同。uint32 CRoutingZone:GetClosestTo没有迅速响应
9、的节点将被迅速排除出候选列表,直到其响应。的新K 桶,并对原K 桶内的节点信息按照新的K 桶前缀值进行重新分配Kademlia协议包括四种远程RPC 操作:PING、STORE、FIND_NODE、FIND_VALUE。生成K-BUCKETK-bucket构造了Kademlia网络的路由表每个节点都保存和自己一定距离范围内的节点信息,k-bucket存储这些信息(IP address,UDP port,Node ID)数据列表。K 桶内部信息存放位置是根据上次看到的时间顺序排列,最近(least-recently)看到的放在头部,最后(most-recently)看到的放在尾部。每个桶都有最大
10、不超过k 个的数据项,这里k 是为平衡系统性能和网络负载而设置的一个常数,但必须是偶数;在emule中k=10k=10。1111由于每个K桶覆盖距离的范围呈指数关系增长,这就形成了离自己近的节点的信息多,离自己远的节点的信息少,从而可以保证路由查询过程是收敛。也就是说,每个结点都对自己附近的情况非常了解,而随着距离的增大,了解的程度不断降低降低。经过证明,对于一个有N 个节点的Kad 网络,最多只需要经过logN 步查询,就可以准确定位到目标节点。1212EMULE中生成K-BUCKET具体实现在RoutingBin.h中定义了一个list:ContactList m_listEntries;
11、即为k-bucketCRoutingZone实际上是一个二叉树,当当前的CRoutingZone类为整个二叉树的叶节点时,这个指向CRoutingBin类型的指针才有意义。(此时CRoutingZone作为网络中的节点应该包含一个k-bucket),由于CRoutingBin中定义了一个ContactList,这个ContactList即为k-bucket。1313节点间交互行为1414KADEMLIA协议的操作与EMULE中对应关系Kademlia协议包括四种远程RPC 操作:PING、STORE、FIND_NODE、FIND_VALUE。PING 操作的作用是探测一个节点,用以判断其是否仍
12、然在线。对应于emule中PING-PONG操作,即发送KADEMLIA_HELLO_REQ和KADEMLIA_HELLO_RES请求STORE 操作的作用是通知一个节点存储一个对。对应emule中publish操作以及Store操作FIND_NODE 操作使用一个160bit 的ID 作为参数。本操作的接受者返回它所知道的更接近目标ID 的K 个节点的(IP address,UDP port,Node ID)信息。对应emule中查找节点的操作FIND_VALUE 操作和FIND_NODE 操作类似,不同的是它只需要返回一个节点的(IP address,UDP port,Node ID)信息
13、。如果本操作的接受者收到同一个key 的STORE 操作,则会直接返回存储的value 值。对应emule中文件检索的操作1515节点间距离节点间距离判断两个节点x,y 的距离远近是基于数学上的异或的二进制运算,d(x,y)=x y,既对应位相同时结果为0,不同时结果为1。异或操作具有如下性质:非负性对称性三角不等式单向性传递性异或运算提供了一种在Kad网络上进行可靠距离度量的方法。假如Kad网络上所有其他用户都按照和你之间距离的远近而排成一条长队,如果已知另一个结点的ID,那么你很容易计算出他在这条长队中的位置;如果给定一个距离,你也能很容易从这条长队里找出与你的距离最接近给定距离的那些结点
展开阅读全文