文档介绍：P2P网络体系(3)
1
大纲
第一代P2P网络:混合式P2P体系
第二代P2P网络:无结构P2P体系
第三代P2P网络:结构化P2P体系(*)
2
第三代P2P网络:结构化P2P体系
Chord&CFS
CAN
Tapestry&OceanStore
Pastry&Past
Kademlia
Viceroy
Koorde
Cycloid
3
其他著名结构化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)中的每一个结点,让基于时延选择路由下一跳,甚至让它们发送并行的异步消息
6
Kademlia的应用
网络
现已被整合到eDonkey2000中
eDonkeyHybrid
混合式eDonkey软件
mlDonkey
运行于多平台、多网络的eDonkey扩展版软件
Kad网络
eMule

mlDonkey
-28版之后
aMule
All-platform eMule,eMule的多平台扩展版
RevConnect
基于DirectConnect协议的P2P文件共享软件,以Kademlia作为分布式散列表
KadC
网络中发布、获取信息的C语言库
Azureus
,使用Kad网络作为BitTorrent Trackers失效时的替代方法
,使用Kad网络为无Tracker的torrents服务
BitSpirit
基于BitTorrent协议的一个客户端,
eXeem
基于BitTorrent网络的一个P2P文件共享软件,用以取代BT中原有的Trackers
7
Kademlia的异或度量、结点状态和自组织
Kademlia结点、对象ID分配、以及索引负责方式同经典的P2P网络
设Kad网络中有两个结点,ID分别为x,y,其距离d(x,y)=x⊕y,d(x,y)=d(y,x),具有对称性和三角属性,类似CAN、Tapestry和Pastry,不同于Chord
与Chord的顺时针环形度量一样具有单向性,保证了所有对相同数据对象的定位最终将会聚于相同的路径,且越往后走会聚的可能性越高
8
Kademlia的结点状态和自组织
每个Kad结点维护一个称为k-buckets的路由表,以采用160位ID为例,对每位i,结点都保存一个链表,称为一个k-bucket,其中记录到自己的异或距离在2i与2i+1之间的一些结点,并按照最近访问时间从尾到头排列
每个链表项是形如(IP, UDP port, nodeID)的三元组
i越大,其链表项越多,并呈指数增长,因此Kad网络给出链表长度上限k
9
Kademlia概况
■距离的概念:两个标识符之间位异或的值。
数学依据:1)d(x,x)=0
2)if x!=y, d(x,y)!=0
3)d(x,y)+d(x,z)>=d(x,z)
■Kad路由表--K桶
null
null
null
K桶[0]
K桶[1]
K桶[2]
距离[1,2]
距离[2,4]
距离[4,8]
K桶[159]
Last-recently
most-recently
0=<i<160,每个节点保存K个离本节点距离为2^i~2^(i+1)的节点信息。
■Kad表动态更新策略:
当受到来自其他节点的消息时,即更新Kad桶。
发送节点在K桶中,移至列表尾部。
若K桶没满,则移至尾部。
若K桶满,则对列表头节点发送Ping命令。若没回复,则删除节点。
10