PP文件共享系统概览.ppt

P2P文件共享系统概览 主要内容 现有P2P文件共享系统的简介 P2P文件共享系统的三个主要问题 搜索与定位 数据传输 信誉、激励及安全相关问题 现在研究问题的总结 P2P文件共享系统测量的相关工作 Part1 P2P文件共享系统的发展 P2P文件共享系统分类 P2P文件共享系统研究的三个方面 文件定位和搜索 定位-基于DHT的覆盖网络 不需要搜索，资源的定位和底层的覆盖网络的设计紧密相关，一般为O(LogN)的量级 搜索-非结构化的P2P覆盖网络 Gnutella 网络 热门的很快，最差可能是O(N) 研究的重点 Kazaa等Super-Node 网络 可扩展性好，流行文件能在1-Hop内找到 eDonkey、DC++、Maze等有强大中心索引服务器的网络 1-Hop 的强大搜索 实时性较差，新资源需要中心服务器索引更新后才能被别的检索到 结构化的P2P覆盖网络 Kademlia(IPTPS 2002) OverNet Pastry 2001 Tapestry 2001 Chord 2001 CAN 2001 共性：基本上都是，O(LogN)的邻接表，O(LogN)的跳数，以及上下线节点需要O(LogN)的修复 Kademlia 基于XOR的P2P覆盖网络 NodeID和Key Hash到160bit 为了定位一个{key, value}对，如下定义两个ID之间的距离： 满足三角定理 对于一个给定ID如x，以及距离d，只存在一个其他的节点y，使得d(x, y) = d。 邻接表和资源发布 (增加冗余) 每个节点保存i=LogN个bucket，每个bucket中有K个和自己距离为2i至2i+1的邻居的地址{IP地址，UDP端口，NodeID}。bucket里面的节点按照最近访问次序排序，最近访问的放在尾部，最少访问的的放在首部。为了在一段时间内一个bucket内的所有节点不要都失效，K在系统的实现中一般取20（OverNet中） 节点定位的时候也采取一种冗余的做法。先随机选取距离目标节点最近的非空bucket里面K2个节点传递转发消息，如果没有返回任何的更近的节点，节点会对所有bucket内最近的k个节点重新发出这个请求。 在发布一个key的时候，会发布到距离这个key最近的K3个节点。每个小时这个key都会重新发布过。这样，如果一个节点在一小时内的离线概率为1/2，这个key存在系统的概率为1-2k3。 增加冗余来减少Churn导致的失效问题 基于其上的OverNet的搜索的设计 在发布资源的时候，首先对文件名进行切词，然后把短关键字删掉（1char 或者2char），然后分别将剩下的关键字进行Hash，发布到Kademlia中去。比如ring_king会被切为ring king两个Hash值 搜索的时候，对搜索的词也同样的切词，然后并行的寻找所有的符合其中一个关键字的资源，最后需要在你自己的客户端作一次Merge，把那些不包含你全部关键字的结果滤掉，其实带宽已经浪费掉了 DHT存在的问题和研究重点 解决P2P系统中固有的Churn高的现象，每个节点上下线都要O(LogN）的修复操作，研究方向：增大邻接表，增加发布及搜索冗余。 模糊查询的支持 OverNet的查询存在的问题：Key不能太多，切词准确性 让DHT支持复杂查询，不按照NodeID组织DHT，而按照关键字来组织（这方面MSRA那边在作些尝试） 其他办法2：用DHT维护拓扑，而资源的定位仍然采用广播方式查询;分级的索引 文件的本地存储特性的消失 目录的结构信息 (本地相同目录下两个相关文件可能被Hash到不同别的节点) DHT这种架构更容易受到攻击 (研究重点) 伪装节点 拒绝转发消息等 不能吻合系统中节点的异质性(可能弱节点被分配到热门关键字)：a) 对热门关键字作Cache b)采用分层DHT结构如Kelips，包括以物理位置为依据的分层，以兴趣为依据的分层等 非结构化的P2P覆盖网络 Napster 1-hop的带Metedata的搜索，单点失效 Overnet/eDonkey2000 混合型的搜索，同时支持DHT和中心服务器，中心服务器采用倒排表,需要重建 DC++ 采用BloomFilter去进行估计，然后采用本地搜索的办法来精确搜索，这样中心服务器就不用做倒排表了。 采用4字的BloomFilter的设计，不清楚效果怎么样？abcdefg = {abcd, bcde, cdef, defg} Kazaa Gnutella 可扩展性问题 Kazaa的拓扑与搜索 通过机器的CPU和网络带宽来确定SuperNode(SN) 每个SN连接40个左右的其他SN以及100-200个OrdinaryNode(ON) ON会选择物理位置