文档介绍：P2P网络体系(3)1大纲第一代P2P网络:混合式P2P体系第二代P2P网络:无结构P2P体系第三代P2P网络:结构化P2P体系(*)2第三代P2P网络:结构化P2P体系Chord&CFSCANTapestry&OceanStorePastry&ViceroyKoordeCycloid3其他著名结构化P2P网络实践系统:,提出更加容错、实用的P2P系统,如Kademlia(2002),路由方式类似Chord,但采用异或的距离量度,并将网络结构配置信息融合到每条消息中;(2003)模型,类似Chord,但采用跳表SkipList数据结构,提供结点路由、对象语义两方面的局部性,以前的结构化P2P网络都没有做到理论模型:具有特殊性质的新型结构化P2P模型——常数度P2P网络,其路由、定位、自组织方式与过去的模型区别不大,但每个结点的“度”(即连接数)是固定的,不随网络规模改变,保持路由效率的同时减小了自适应开销,常见模型有Viceroy(2002)、Koorde(2003)、Cycloid(2004)4实践系统一、Kademlia二、5一、Kademlia:基于异或度量的P2P信息系统由于“异或”是对称的,因此Kademlia结点能从路由消息中获得有用的网络配置信息,这种“捎带更新”方法使得Kademlia以很小的开销获得了很大的自适应性Kademlia不像Chord需要严格的路由表,可以发送消息给其路由表任意一段(interval)中的每一个结点,让基于时延选择路由下一跳,现已被整合到eDonkey2000中eDonkeyHybrid混合式eDonkey软件mlDonkey运行于多平台、-28版之后aMuleAll-platformeMule,eMule的多平台扩展版RevConnect基于DirectConnect协议的P2P文件共享软件,网络中发布、,,使用Kad网络为无Tracker的torrents服务BitSpirit基于BitTorrent协议的一个客户端,,用以取代BT中原有的Trackers7Kademlia的异或度量、结点状态和自组织Kademlia结点、对象ID分配、以及索引负责方式同经典的P2P网络设Kad网络中有两个结点,ID分别为x,y,其距离d(x,y)=x⊕y,d(x,y)=d(y,x),具有对称性和三角属性,类似CAN、Tapestry和Pastry,不同于Chord与Chord的顺时针环形度量一样具有单向性,保证了所有对相同数据对象的定位最终将会聚于相同的路径,且越往后走会聚的可能性越高8Kademlia的结点状态和自组织每个Kad结点维护一个称为k-buckets的路由表,以采用160位ID为例,对每位i,结点都保存一个链表,称为一个k-bucket,其中记录到自己的异或距离在2i与2i+1之间的一些结点,并按照最近访问时间从尾到头排列每个链表项是形如(IP,UDPport,nodeID)的三元组i越大,其链表项越多,并呈指数增长,因此Kad网络给出链表长度上限k9Kademlia概况■距离的概念:两个标识符之间位异或的值。数学依据:1)d(x,x)=02)ifx!=y,d(x,y)!=03)d(x,y)+d(x,z)>=d(x,z)■Kad路由表--K桶nullnullnullK桶[0]K桶[1]K桶[2]距离[1,2]距离[2,4]距离[4,8]K桶[159]Last-recentlymost-recently0=<i<160,每个节点保存K个离本节点距离为2^i~2^(i+1)的节点信息。■Kad表动态更新策略:当受到来自其他节点的消息时,即更新Kad桶。发送节点在K桶中,移至列表尾部。若K桶没满,则移至尾部。若K桶满,则对列表头节点发送Ping命令。若没回复,则删除节点。10