P2P文件共享系统概览

主要内容 现有P2P文件共享系统的简介 P2P文件共享系统的三个主要问题 现在研究问题的总结 P2P文件共享系统测量的相关工作 搜索与定位 数据传输 信誉、激励及安全相关问题 现在研究问题的总结 P2P文件共享系统测量的相关工作

Part1

P2P文件共享系统的发展 1999 2000 2001 2002 现在 Napster Gnutella FastTrack LimeWire iMesh&Grokster Morpheus Kazaa 99 eDonkey OverNet eDonkey2000 DC++ BitTorrent eXeem

同时连接到DHT的OverNet网络和一个中心服务器模式的网络 其中一个中心服务器上有45万用户，6137万个文件

P2P文件共享系统分类 覆盖网络 集 中 程 度 结构化 非结构化 中心服务器模式 Napster, Maze 混合型 Kazaa FastTrack eDonkey BitTorent 完全无中心服务器 Kademlia(OverNet) Chord Pastry(PAST) Tapestry(OceanStore) Napstry Gnutella LimeWire Morphus

P2P文件共享系统研究的三个方面

文件定位和搜索 定位-基于DHT的覆盖网络 搜索-非结构化的P2P覆盖网络 研究的重点 可扩展性好，流行文件能在1-Hop内找到 不需要搜索，资源的定位和底层的覆盖网络的设计紧密相关，一般为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导致的失效问题 这里与Chord最大的差别就是他会在一个区段内保存一系列的邻居节点来减少Churn的影响，而不是像Chord一样只保存一个。

基于其上的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，包括以物理位置为依据的分层，以兴趣为依据的分层等 邻接表的消耗可以忍受 Overnet中一个文件名可能要分成多个Key，发布到网络中去，而当文件大量变多的时候，这些Key的发布开销可能会过大，事实上Overnet中保存的一般是热门文件，而Gnutella这样的网络非常适合查询热门文件，那还要DHT做什么呢？ 有些弱节点必须负担更多的关键字，由于关键字的分布也不均匀

非结构化的P2P覆盖网络 Napster Overnet/eDonkey2000 DC++ Kazaa Gnutella 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会选择物理位置较近的SN进行连接，该SN会保存其文件的索引信息 SN间不断的通过Gossip协议来交换邻接表数据和查询请求，SN间存在长连接和短连接。这样让SN形成一个符合Power-law分布的随机网络（实际的测量验证了这一点） ON的搜索首先会转发给自己的SN，然后再由SN负责此次查询 都是测量的结果

Gnutella Flooding搜索算法的改进 一般文章的假设 网络的度的分布服从Power-law分布 统计表明网络的拓扑结构和小世界网络模型类似：网络的平均路径长度和随机网络一样比较小，但是网络的节点聚集度会远远大于随机网络的 所以，其中95%的节点通过Flooding的方式在7-hop内能够遍历到 一般假定用户的搜索也服从Power-law分布 测量表明文件的流行度，也就是副本数也服从Zip-f分布 采用Flooding可以很好的找到热门文件，存在问题：可扩展性差、冗余消息过多，负载不平衡

1-Random walk K-Random walk：每个节点随机的选取K个邻居节点进行消息转发 改进1：采用两级TTL的改进，如果在L1步内没有找到，再启动第二步L2的搜索 相关工作1，如果采用副本的方式来提高命中率，在random walk情况下，当文件的副本数和文件的查询流行度呈平方根分布时（和uniform和等比分布相比），效果最好。 相关工作2：每个节点保存周围半径为R的所有节点的信息，来减少消息数

2-根据邻接节点特性改进 BFS Direct BFS根据邻接节点的各个属性来选择转发对象 根据关键字和邻接节点的关键字集的相似度来选择 上次返回结果数最多的邻居节点 返回节点中跳数最少的节点，也就是说最近的节点 最稳定的邻居节点（相互间消息最多，度很高） 最空闲的节点 根据关键字和邻接节点的关键字集的相似度来选择 自适应的BFS：根据上次是否返回结果来给邻接节点评分，来不断的调整优先级

针对节点异质性的改进 SIGCOMM03的一篇文章提出的改进的Gnutella的GIA 结论：可以很好的提高Gnutella的可扩展性 采用随机漫步 每个节点保存1-hop邻居的资源 根据节点的负载动态调整搜索消息的转发和邻居节点 结论：可以很好的提高Gnutella的可扩展性 在带宽，机器性能，资源上的

非结构化P2P搜索现在研究的问题 对于Gnutella这样的网络，可以继续在邻居节点的选择上进行研究，包括如何利用把Locality，Social Network以及搜索历史记录等信息结合起来,让搜索算法可以在物理跳数，逻辑跳数以及路由消息数等方面继续的最优。 在多层的拓扑设计中，也可以在如何选择和组织SuperNode，让Overlay的拓扑更加符合物理网络的拓扑这个方向上进行更多研究。

非结构化P2P搜索需要研究的问题2 研究Churn对文件可用性的影响 采用分布式构架更多的是法律问题。eDonkey的一台服务器(64bit双CPU, 8G SDRAM)可以负载50万的用户。所以很多实用系统采用无中心服务器的设计很大方面也是出于法律的考虑。 文件的副本数在P2P文件共享网络上呈现Zip-f分布是Flooding这类算法能够得以应用的统计基础。由于流行的文件的副本数比较高，所以在一定的TTL内，一般可以找到自己需要到文件。但是，对于那些比较稀少的文件，极有可能在一定的TTL内找不到。

两大类方法的比较 非结构化的Gnutella网络更适合查找热门资源，而且统计表明人们的行为也是这样的，所以其运作得非常好。 结构化的P2P网络定位快速，所以可以快速的定位资源。但是问题在于：首先冷门资源的文件数目也同样巨大，在Churn高的网络上维护这么多key开销也很大。OverNet也是用来维护热门资源，所以DHT和Gnutella相比的优势何在？ eDonkey2000那种模式现在来看还不错，用DHT去定位热门资源的，避免中心服务器失效；采用一系列的中心服务器来提供更全面的非热门的搜索。

文件传输方面的工作-工程化但很重要 单对单传输 多对单传输 多对多传输 （ad-hoc的激励模型） 高级特性 断点续传 多协议支持（FTP,HTTP等） 内嵌的播放 Fake-file监测（如何快速计算一个文件的校验值？MD5太慢，Kazaa有自己的算法，但是被破解）

BitTorrent 多对多传输 Tracker即时接收所有下载者信息（IP地址和端口），并且给每个下载者一份随机的peer列表 下载者每隔一段时间连一次Tracker，告知自己的进度和取得列表，这样就可以和那些已经直接连接上的peer进行数据的上传下载 在进行文件传输时，每个文件一般被划分成256K的大小的块，每个块都计算其校验值。用户间互相的Choke和UnChoke对方，来交换这些文件块

Choke & UnChoke 算法 客户端每10秒钟更换一下自己的上载列表。包括给4个给它上载速度最快的节点上载数据，并且，如果节点有更好的上载速度，它将会被激活(UnChoke)，现有这4个中上载最慢的被Choke。对于下载完成的人来说，根据自己的上传速度来进行Choke。 还有一个UnChoke的节点不根据上传速率来决定。这个每30秒刷新一次，为了给那些新进入网络的还没有任何块的用户一个得到完整块的机会 在请求块的时候，节点会随即的选取那些它没有而别人有的块来下载，以让网络中这个文件的每个块更加均匀的分布

研究的问题 BitTorrent内建的激励机制能让用户更多的上载资源以达到自己更快的下载速度 SIGCOMM’03，对这种激励机制的建模分析 IPTPS’05 对BitTorrent用户的到达离开率等数据的统计分析 现在这方面的研究主要集中在建模分析上，可以根据这些模型去改进系统。 NAT对传输的影响 Fake-file，Broken-file的检测

激励、声誉以及安全 为什么要去研究激励、声誉 现有的方法-效果不是很明显，不成系统 最近的测量表明80%的eDonkey用户不共享任何资源，大概60%的Maze用户不上传资源。 我们的分析还发现用户为了降低自己的负载，倾向于把热门资源移出共享而保留那些非热门的资源，我们认为是另一种形式的Free-rider。 Fake-file、共谋等不合作行为 现有的方法-效果不是很明显，不成系统 Ad-hoc的下载激励方式 (BitTorrent)只针对某一次传输 DC++，限制加入网络的人必须共享一定数目的文件 eDonkey、Maze都根据你的历史上载记录来提高你的下载排名 默认的把下载资源添加到共享里（几乎所有的系统都是这样）

必须建立在安全计算环境下 纯分布式的系统需要一个安全的计算环境来支持激励和信誉机制，很难但是相关研究很多 中心服务器或者一些文章采用的Agent可以解决一部份安全计算的问题 假设有安全计算环境，构建一个激励机制，分析如何应付系统中的各种欺骗问题是一个比较有价值的研究点 激励机制分为基于信誉和基于积分系统(MAZE)

一个重要的信任模型EigenTrust 类似于PageRank的计算方法 可以采用中心服务器或者分布式的计算 首先每个节点i根据自己在节点j上下载东西的质量给j一个分值 然后归一化 叠加的计算其他的节点的分值

叠代计算 右边是带Good Peer加权的算法

我们的相关研究工作 准备着手验证这类Rank算法在实际系统中运算的效果，以及存在的缺陷：比如，现在发现这类算法存在对于一个主要在局域网内进行共享的人计算不公平的情况，尝试着改进这个方法 现在工作集中在比较热门的Free-rider, Colluding方面分析和建模的工作 其他的工作包括P2P蠕虫和病毒传播的建模

在P2P文件共享系统中我们可以去研究的点 一个更好的激励模型，在P2P文件共享系统中，如何减少Free-rider的数目，让用户把文件共享出来，是系统良好运作很关键的一个环节。现有系统和文章都没有很好的解决这个问题，而建立这方面的模型需要实际的系统测量工作相结合，也是我们的优势所在。现在针对White-washer、Free-rider、Colluding以及Fake file都在做一些研究，希望在测量的基础上找到问题所在，并提出新的激励模型来进行部署。 根据统计规律去改进Overlay的结构和搜索定位方法一直是P2P领域研究的热点。 a) 让其可以和实际的物理网络可以更好的吻合，更有效的利用现有的Internet的带宽资源。 b) 提供不论是热门还是冷门资源的都比较快速的搜索与定位。 整个P2P文件共享系统的各项指标的测量与建模 文件传输的研究，包括流传输，多点互传的相关研究，这个更工程。 安全相关以及语义相关的研究，这个需要一个长期的过程。 在这一点上，采用层次结构的Overlay结构可能可以获得比较好的效果，而且易于利用locality的信息（例如eDonkey的模式）。同时，作P2P的代理可能也能在一定程度上解决带宽耗费的问题。需要研究的还包括如何对NAT内的用户提供更好的支持。

Part2

P2P文件共享系统进行测量的意义 P2P文件共享系统作为现在互联网上的新兴的最主要的应用系统之一，缺乏像基础网络测量，WWW测量多年的积累；而且不同的P2P文件共享系统在一直不断出现和流行开来，更需要不断的进行分析比较。 作为一个大型的复杂系统，需要对现有运行系统不断统计和分析，发现问题和解决问题。 可以通过测量来分析系统是否达到了设计要求。 出于以后系统设计的考虑，通过现有的测量分析来建立一些基本的模型，为以后的系统设计提供模拟和测试环境。可以为以后的系统设计者在如何设计这个系统提供理论基础。

测量的方法学 – 数据的获取 在主干网或者主节点上进行测量 模拟客户端行为-构建Crawler 搭建自己的P2P系统或者一个P2P服务器 需要收集的数据类型 相互间交互的数据

几个重要的测量工作 E. Adar 2000 Free-rider in Gnutella S. Saroiu (OSDI 2002) 对P2P文件共享系统一些全局的特性的测量 Adriana Iamnitchi, 对Kazaa网络特性是否符合Small world等的一个测量 S. Saroiu (MMCN’02,SOSP’03) 对Kazaa和Gnutella的测量与建模 workload的分析 S. B. Handurukande (2005)对eDonkey系统的测量，文件的聚集程度 D. Qiu (SIGCOMM 04)对BitTorrent的建模与分析

重要结论 Gnutella,Kazaa里面节点度的分布服从Power-law，并且拓扑结构符合小世界模型 P2P文件共享系统的异质性 (带宽，CPU，资源，在线时间) 文件传输特性 文件的副本数服从power-law分布 文件的下载流行度数不服从Zip-f分布，可以看作是两阶段的Zip-f 文件的搜索流行度可能符合Zip-f分布 文件的类型以多媒体文件为主 语义相关和Locality 在物理网络相近，文件内容的相似度也偏大 在自己以往下载或得到搜索结果的节点上更容易找到自己需要的东西 Free-rider 现在的每个P2P系统中都存在很大比例的Free-rider 可用性方面的结论和模型 每个用户的平均在线时间为60分钟，所以Churn对P2P文件共享系统可用性影响很大 平均路径小，节点的聚集度远远高于随机网络

什么样的文章是有价值的测量、分析与建模呢 首先是有创新性的测量手段，得到了别人拿不到的数据，比如说首先通过模拟Gnutella客户端去测量整个网络的工作。这样通过这些数据可以发现了以前别人没有发现的规律和现象。 其次是通过大量的数据，来进行系统的详细分析，提出自己的统计模型，而这些统计模型可以为以后的研究工作提供坚实的理论基础。

我们可以去关注的问题 优势：可以知道所有节点的相互传输关系（别的工作都没有很全面的这些数据）劣势：需要说明Maze的和其他P2P文件系统有着同样的规律 文件在P2P文件系统中的传播规律的研究，这也是最近大家趋向去研究的方向，也可以为作内容控制等做准备 测量不同Incentive Model对P2P文件共享系统影响，包括用户行为(Free-rider等行为)的测量。 提出一个统一规范的P2P文件共享系统特性的统计模型或者实际数据用于模拟和测试 构建分布式的Log系统，已经有人作了类似的工作P2PLog

Future work – Find resources Stabilize our central servers How to lead people to new resource Reduce the rebuild period of central indexer servers A new P2P search mode Base on Friends list? Base on Physical address? Mix type Change index strategy to balance the system load Return the low points users URL first…? A well define catalog (Seeds list)

Future work – Transfer mode Add M-FTP protocols Associate with Seed mechanism Associate with incentive mechanism New feature of playing while transferring Not urgency Try to support RM, RMVB, AVI first

Future work – Incentive mechanism How to prevent the cheat in system Investigate the user action impact by the incentive mode Reduce the population of free-rider

Future work – CNGI Port to IPV6 PlateLab Application Layer Multicast

谢谢 各位老师、同学！