DHT网络的搜索技术解析课件.ppt
《DHT网络的搜索技术解析课件.ppt》由会员分享,可在线阅读,更多相关《DHT网络的搜索技术解析课件.ppt(34页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、DHT网络的搜索技术网络的搜索技术哈尔滨理工大学网络信息中心 姚 亮P2P网络的分类Hash函数概述DHT原理几种典型的DHT网络总结主要内容1.P2P网络分类网络分类l非结构化非结构化P2P网络拓扑是任意的网络拓扑是任意的内容的存储位置与网络拓扑无关内容的存储位置与网络拓扑无关l结构化结构化P2P网络拓扑结构是有规律的网络拓扑结构是有规律的l每个节点都随机生成一个标识每个节点都随机生成一个标识(ID)内容的存储位置与网络拓扑相关内容的存储位置与网络拓扑相关l内容的存储位置与节点标识之间存在着映射关系内容的存储位置与节点标识之间存在着映射关系P2P网络分类网络分类在结构化在结构化P2P网络中,
2、内容一般使用内容索引网络中,内容一般使用内容索引来表示来表示,内容索引包括内容索引包括key和和value两部分两部分,其中其中key是内容的关键字是内容的关键字,value是存放内容的实际是存放内容的实际位置位置,因此内容索引也表示为因此内容索引也表示为对对l内容索引内容索引表示电影夜宴可表示电影夜宴可以从以从http:/ Digest),一般用于消息的完整性检验。),一般用于消息的完整性检验。lHash函数有以下特性:函数有以下特性:给定给定 P,易于计算出,易于计算出 MD(P)只给出只给出 MD(P),几乎无法找出),几乎无法找出 P无法找到两条具有同样消息摘要的不同消息无法找到两条具
3、有同样消息摘要的不同消息lHash函数函数MD5:消息摘要长度固定为:消息摘要长度固定为128比特比特SHA-1:消息摘要长度固定为:消息摘要长度固定为160比特比特Hash函数应用于函数应用于P2P的特性的特性l唯一性:不同的输入明文,对应着不同的输唯一性:不同的输入明文,对应着不同的输出摘要出摘要将节点将节点IP地址的摘要作为节点地址的摘要作为节点ID,保证了节点,保证了节点ID在在P2P环境下的唯一性环境下的唯一性SHA-1(“202.38.64.1”)=24b92cb1d2b81a47472a93d06af3d85a42e463eaSHA-1(“202.38.64.2”)=e1d9b2
4、5dee874b0c51db4c4ba7c9ae2b766fbf273.DHT原理原理(1)l将内容索引抽象为将内容索引抽象为对对K是是内容关键字的内容关键字的Hash摘要摘要lK=Hash(key)V是存放内容的实际位置,例如节点是存放内容的实际位置,例如节点IP地址等地址等l所有的所有的对组成一张大的对组成一张大的Hash表,因此该表存储了表,因此该表存储了所有内容的信息所有内容的信息l每个节点都随机生成一个标识每个节点都随机生成一个标识(ID),把,把Hash表分割成许表分割成许多小块,按特定规则多小块,按特定规则(即即K和节点和节点ID之间的映射关系之间的映射关系)分布分布到网络中去,
5、节点按这个规则在应用层上形成一个结构化到网络中去,节点按这个规则在应用层上形成一个结构化的的重叠网络重叠网络l给定查询内容的给定查询内容的K值,可以根据值,可以根据K和节点和节点ID之间的映射关之间的映射关系在重叠网络上找到相应的系在重叠网络上找到相应的V值,从而获得存储文件的节值,从而获得存储文件的节点点IP地址地址DHT原理原理(2)内容内容内容关键字内容关键字key内容存储位置等信息内容存储位置等信息value内容索引内容索引K=Hash(key)提取提取k vHash表表电影电影夜宴夜宴电影、夜宴电影、夜宴http:/ va.Hash表表b.分布式分布式Hash表表规则规则?K VN1
6、N48N16N32N8K VK VK VK VChord、CAN、Tapestry、Pastry在许多情况下在许多情况下,节点节点ID为节点为节点IP地址的地址的Hash摘要摘要DHT原理原理(4)插入插入(K1,V1)K VK VK VK VK VK VK VK VK VK VK V(K1,V1)查询查询(K1)A128.1.2.3BK1=Hash(xyz.mp3)V1=128.1.2.3xyz.mp3Cl索引发布和内容定位索引发布和内容定位DHT原理原理(5)l定位定位(Locating)节点节点ID和其存放的和其存放的对中的对中的K存在着映射关系,因此存在着映射关系,因此可以由可以由K获
7、得存放该获得存放该对的节点对的节点IDl路由路由(Routing)在重叠网上根据节点在重叠网上根据节点ID进行路由,将查询消息最终发送到进行路由,将查询消息最终发送到目的节点。每个节点需要有到其邻近节点的路由信息,包目的节点。每个节点需要有到其邻近节点的路由信息,包括节点括节点ID、IP等等l网络拓扑网络拓扑拓扑结构由节点拓扑结构由节点ID和其存放的和其存放的对中的对中的K之间的映射之间的映射关系决定关系决定拓扑动态变化,需要处理节点加入拓扑动态变化,需要处理节点加入/退出退出/失效的情况失效的情况在重叠网上节点始终由节点在重叠网上节点始终由节点ID标识,并且根据标识,并且根据ID进行路由进行
8、路由4.Chord:概述:概述lBerkeley和和MIT共同提出共同提出l采用环形拓扑采用环形拓扑(Chord环环)l应用程序接口应用程序接口Insert(K,V)l将将对存放到节点对存放到节点ID为为Successor(K)上上Lookup(K)l根据根据K查询相应的查询相应的VUpdate(K,new_V)l根据根据K更新相应的更新相应的VJoin(NID)l节点加入节点加入Leave()l节点主动退出节点主动退出Chord:Hash表分布规则表分布规则lHash算法算法SHA-1lHash节点节点IP地址地址m位位节点节点ID(表示为表示为NID)lHash内容关键字内容关键字m位位K
9、(表示为表示为KID)l节点按节点按ID从小到大顺序排从小到大顺序排列在一个逻辑环上列在一个逻辑环上l存储在后继节点上存储在后继节点上Successor(K):从:从K开开始顺始顺时针方向距离时针方向距离K最最近的节点近的节点 ID=hash(IP)=14N56K=hash(key)=54N1N8N14N21N32N38N42N48N51m=6Chord:简单查询过程:简单查询过程l每个节点仅维护其后继节每个节点仅维护其后继节点点ID、IP地址等信息地址等信息l查询消息通过后继节点指查询消息通过后继节点指针在圆环上传递针在圆环上传递l直到查询消息中包含的直到查询消息中包含的K落在某节点落在某节
10、点ID和它的后继和它的后继节点节点ID之间之间l速度太慢速度太慢 O(N),N为网为网络中节点数络中节点数N56K54Lookup(K54)N56N1N8N14N21N32N38N42N48N51m=6Chord:指针表:指针表N56指针表指针表N8+1N8+2N8+4N8+8N8+16N8+32N14N14N14N21N32N42节点节点S的第的第i个指针个指针successorn+2(i-1),1im Chord:基于指针表的扩展查找过程:基于指针表的扩展查找过程l指针表中有O(log N)个节点l查询经过大约O(log N)跳N56K54指针表指针表N8+1N8+2N8+4N8+8N8+
11、16N8+32N14N14N14N21N32N42Lookup(K54)指针表指针表N42+1N42+2N42+4N42+8N42+16N42+32N48N48N48N51N1N14Chord:网络波动:网络波动(Churn)lChurn由节点的加入、退出或者失效所引起由节点的加入、退出或者失效所引起l每个节点都周期性地运行探测协议来检测新每个节点都周期性地运行探测协议来检测新加入节点或退出加入节点或退出/失效节点,从而更新自己失效节点,从而更新自己的指针表和指向后继节点的指针的指针表和指向后继节点的指针 Chord:节点加入:节点加入l新节点新节点N事先知道某个或者某些结点,并且事先知道某个
12、或者某些结点,并且通过这些节点初始化自己的指针表,也就通过这些节点初始化自己的指针表,也就是说,新节点是说,新节点N将要求已知的系统中某节点将要求已知的系统中某节点为它查找指针表中的各个表项为它查找指针表中的各个表项 l在在其其它它节节点点运运行行探探测测协协议议后后,新新节节点点N将将被被反反映映到到相相关关节节点点的的指指针针表表和和后后继继节节点点指指针针中中 l新新结结点点N的的第第一一个个后后继继结结点点将将其其维维护护的的小小于于N节点的节点的ID的所有的所有K交给该节点维护;交给该节点维护;Chord:节点退出:节点退出/失效失效l当当Chord中某个结点中某个结点M退出退出/失
13、效时,所有在指针失效时,所有在指针表中包含该结点的结点将相应指针指向大于表中包含该结点的结点将相应指针指向大于M结结点点ID的第一个有效结点即节点的第一个有效结点即节点M的后继节点的后继节点l为了保证节点为了保证节点M的退出的退出/失效不影响系统中正在进失效不影响系统中正在进行的查询过程,行的查询过程,每个每个Chord节点都维护一张包括节点都维护一张包括r个最近后继节点的后继列表个最近后继节点的后继列表。如果某个节点注意。如果某个节点注意到它的后继节点失效了,它就用其后继列表中第到它的后继节点失效了,它就用其后继列表中第一个正常节点替换失效节点一个正常节点替换失效节点 Chord:拓扑失配问
14、题:拓扑失配问题lO(LogN)逻辑跳数,但是每一逻辑跳可能跨逻辑跳数,但是每一逻辑跳可能跨越多个自治域,甚至是多个国家的网络越多个自治域,甚至是多个国家的网络l重叠网络与物理网络脱节重叠网络与物理网络脱节l实际的寻路时延较大实际的寻路时延较大Chord:总结:总结l算法简单算法简单l可扩展:查询过程的通信开销和节点维护的可扩展:查询过程的通信开销和节点维护的状态随着系统总节点数增加成对数关系状态随着系统总节点数增加成对数关系(O(log N)数量级数量级)l存在拓扑失配问题存在拓扑失配问题Pastry:概述:概述l英国剑桥英国剑桥Microsoft研究院和研究院和Rice大学共同提出大学共同
15、提出l考虑网络的本地性考虑网络的本地性,解决物理网络和逻辑网络的解决物理网络和逻辑网络的拓扑失配的问题拓扑失配的问题基于应用层定义的邻近性度量基于应用层定义的邻近性度量,例如例如IP路由跳数、地理路由跳数、地理距离、往返延时等距离、往返延时等l节点节点ID分布采用环形结构分布采用环形结构Pastry:Hash表分布规则表分布规则lHash算法算法SHA-1lHash节点节点IP地址地址m位位节点节点ID(表示为表示为NID)lHash内容关键字内容关键字m位位K(表示为表示为KID)lNID和和KID是以是以2b为基的数为基的数,共有共有m/b个数位个数位b是一个配置参数是一个配置参数,一般为
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- DHT 网络 搜索 技术 解析 课件
限制150内