Stochastic maintenance of overlays in structured P2P systems
- 作者：Peter Kersch ; Robert Szabo ; Lawrence Cheng ; Kerry Jean ; Alex Galis
- 关键词：Peer-to-peer routing ; Overlay ; “ ; Small-worlds” ; network ; Stochastic maintenance ; Poisson process
- 刊名：Computer Communications
- 出版年：2008
- 期刊代码：21_01403664
- 类别：cp
- 出版时间：25 February 2008
- 卷：31
- 期：3
- 页码：603-619
- 文件大小：570 K
摘要
Peer-to-peer networks have widespread and got commonly used in our every day life. The maintenance strategy of overlays is a key factor in structured peer-to-peer networks. Most of these routing overlays scale well even for a very large number of nodes in static and quasi-static networks. However, providing good performance in dynamic network environments is still an open question. We analyse maintenance of routing overlays in structured P2P systems under churn. We exploit the inherent difference in the role of local (short-range) and long-range connections. We propose a dual strategy for the routing overlays: (i) we reuse strict, proactive and self-stabilizing short-range connection maintenance and (ii) we define a novel, loose and stochastic long-range connection maintenance mechanism, which can significantly reduce maintenance overhead in large networks with high churn rates without affecting routing performance. We use Kleinberg’s small worlds model to describe and (re)construct long-range connections. We formally describe the evolution of our proposed system under churn by a Markov chain model and we derive its steady state maintenance traffic (overhead). We formally show that our maintenance method scales logarithmically with the system’s size, which is the theoretical lower bound for maintenance traffic to ensure connectivity of the network. Finally, we numerically analyse overlay and maintenance behaviour using various protocol parameter settings and conclude that an overlay with our maintenance method is stable at very high levels of churn.