Garcés-Erice, L., Biersack, E.W., Ross, K.W., Felber, P.A. and Urvoy-Keller, G. (2003), “Hierarchical peer-to-peer systems”, in Parallel Processing Letters, Vol. 13, No. 4, pp. 643-657.
2级Chord。先找组,再在组内找节点。
学习Internet的等级路由。
好处:
- 减少查找的跳数
- 在组内查找快
- 以组为单位进行管理。组可以用不同的DHT协议。
每组挑出一些超级节点作为网关节点。网关节点组成顶级Overlay,负责组间消息的路由。
合作缓存机制:减少数据传输延时
算法:
- 分配节点到组
- 选出超级节点
- 维护顶级Overlay
具体分析了用Chord做顶级overlay的性能:
- 模型
- 分析了期望的查找跳数
查询:到本组超级节点,到负责该Key的组的超级节点,再到负责该key的节点。
关键问题也就是这些问题:
- 到本组超级节点:集中的超级节点列表(不论是中央服务器还是作为键值对存在网络中)
- 组间路由:明确指定组ID/ID空间划分间接组寻址
当多级的时候,总是先路由到顶级。然后一级级下来。
节点加入组g。
- 在网络中存g-超级节点list。
- 节点查询key=g,得到超级节点的list,然后向这些节点申请加入。(所以ID空间是独立的)
超级节点维护候选超级节点列表,并定时发给各节点。
- 监视组内节点特点:开机时间、CPU、带宽、
当一个超级节点失败时,候选超级节点列表中的第一个节点主动加入上一级Overlay。并通知组内节点和上一级Overlay的邻居节点。
用组内的对应于该Key的节点做Cache。改善性能。
修改Chord。变邻居IP为邻居IP列表,其中包括邻居组的超级节点列表
当组的超级节点变化时,立刻更新前驱和后继的路由表,但Lazily更新finger表的自己。
模型分析:
性能改善来自稳定节点的选取和环内节点数的减少
P个节点、I个组。两种节点:稳定节点(宕机概率Ps)、不稳定节点(宕机概率Pr)。Pr>>Ps
考虑(N,p)。
假设:
- N个Peer在2^m上均匀分布,距离2^m/N
- finger table里的项有p的概率宕机,但后继总是对的:因此,总能前进
随机选择的查询节点和产生的Key,H:跳数。T:查询节点和Key之间的距离(随机变量),求E[H]。
要求h(n)=E[H|T=n]. h(1)=1
jn: finger表中n前面的finger表项的个数。
所以:如果第jn项的peer没宕机,一跳能前进x=(2^jn)*(2^m/N)这么多的距离。h(n)=h(n-x)+1
如果第jn项的peer宕机,而第jn-1项的peer没宕机,一跳能前进x=(2^(jn-1))*(2^m/N)这么多的距离。h(n)=h(n-x)+1
这样就得到回归方程式。
忽略组内查表(组很小,64-256)。模型Chord的查询跳数与N, Pr的关系。
参考:
<100个节点的全连接网络用CARP [18].
100-1000用consistent hashing [19]
[14] 测量与M个landmark的RTT,将结果排序,判断自己属于M!个组中的哪一个。然后获得这个空间的ID。由此实现位置敏感的Overlay。用CAN做了实验。
KaZaA:高可用和高性能节点做超级节点,新节点联到RTT最近的超级节点。超级节点组成一个Overlay. CAP[15]用类似的结构
Brocade [16] 类似于[14]+[15]. 但如果有[14]了,它为何还要[15]呢?需要看一下它的论文。
[17]:改进了Pastry, 每一跳路由时选择最近的节点。但越往后,可供选择的余地越小,而最后一跳往往是最长的。
14. S. Ratnasamy, M. Handley, R. Karp, and S. Shenker,
“Topologically-aware overlay construction and server selection,”
in Proceedings of Infocom’02, (New York City, NY), 2002.
15. B. Krishnamurthy, J. Wang, and Y. Xie,
“Early measurements of a cluster-based architecture for p2p systems,”
in ACM SIGCOMM Internet Measurement Workshop, (San Francisco, CA), November 2001.
16. B. Y. Zhao, Y. Duan, L. Huang, A. D. Joseph, and J. D. Kubiatowicz,
“Brocade: Landmark routing on overlay networks,”
in In Proceedings of IPTPS’02, (Cambridge, MA), March 2002.
17. M. Castro, P. Druschel, Y. C. Hu, and A. Rowstron,
“Exploiting network proximity in peer-to-peer overlay networks,”
Tech. Rep. MSR-TR-2002-82, Microsoft Research, One Microsoft Way, Redmond, WA 98052, 2002.
18. K. W. Ross, “Hash-routing for collections of shared web caches,”
IEEE Network Magazine, vol. 11, 7, pp. 37–44, Nov-Dec 1997.
19. D. Karger, A. Sherman, A. Berkhemier, B. Bogstad, R. Dhanidina, K. Iwamoto, B. Kim, L. Matkins, and Y. Yerushalmi,
“Web caching with consistent hashing,”
in Eighth International World Wide Web Conference, May 1999.