HSkip plus : A Self-Stabilizing Overlay Network for Nodes with Heterogeneous Bandwidths

被引：0
作者：
Feldotto, Matthias [1 ,2 ]
Scheideler, Christian [3 ]
Graffi, Kalman [4 ]
机构：
[1] Univ Paderborn, Heinz Nixdorf Inst, Paderborn, Germany
[2] Univ Paderborn, Dept Comp Sci, Paderborn, Germany
[3] Univ Paderborn, Dept Comp Sci, Theory Distributed Syst Grp, Paderborn, Germany
[4] Univ Dusseldorf, Technol Social Networks Grp, Dept Comp Sci, Dusseldorf, Germany
来源：
14-TH IEEE INTERNATIONAL CONFERENCE ON PEER-TO-PEER COMPUTING (P2P) | 2014年
关键词：
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper we present and analyze HSkip+, a self-stabilizing overlay network for nodes with arbitrary heterogeneous bandwidths. HSkip+ has the same topology as the Skip+ graph proposed by Jacob et al. [1] but its self-stabilization mechanism significantly outperforms the self-stabilization mechanism proposed for Skip+. Also, the nodes are now ordered according to their bandwidths and not according to their identifiers. Various other solutions have already been proposed for overlay networks with heterogeneous bandwidths, but they are not self-stabilizing. In addition to HSkip+ being self-stabilizing, its performance is on par with the best previous bounds on the time and work for joining or leaving a network of peers of logarithmic diameter and degree and arbitrary bandwidths. Also, the dilation and congestion for routing messages is on par with the best previous bounds for such networks, so that HSkip+ combines the advantages of both worlds. Our theoretical investigations are backed by simulations demonstrating that HSkip+ is indeed performing much better than Skip+ and working correctly under high churn rates.
引用
收藏
页数：10
相关论文
共 23 条
  • [11] Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs
    Jacob, Riko
    Ritscher, Stephan
    Scheideler, Christian
    Schmid, Stefan
    [J]. THEORETICAL COMPUTER SCIENCE, 2012, 457 : 137 - 148
  • [12] A Distributed Polylogarithmic Time Algorithm for Self-Stabilizing Skip Graphs
    Jacob, Riko
    Richa, Andrea
    Scheideler, Christian
    Schmid, Stefan
    Taeubig, Hanjo
    [J]. PODC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2009, : 131 - 140
  • [13] Kniesburges S., 2013, P INT S DISTR COMP D
  • [14] Kniesburges S, 2011, SPAA 11: PROCEEDINGS OF THE TWENTY-THIRD ANNUAL SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, P235
  • [15] Peer-to-peer streaming in heterogeneous environments
    Meier, Remo
    Wattenhofer, Roger
    [J]. SIGNAL PROCESSING-IMAGE COMMUNICATION, 2012, 27 (05) : 457 - 469
  • [16] Nejdl Wolfgang., 2003, WWW 2003, P536, DOI [10.1145/775152.775229, DOI 10.1145/775152.775229]
  • [17] Nor RM, 2011, LECT NOTES COMPUT SC, V6976, P356, DOI 10.1007/978-3-642-24550-3_27
  • [18] Pussep K, 2010, MODELING TOOLS NETWO, P447
  • [19] Scheideler C, 2009, LECT NOTES COMPUT SC, V5556, P571, DOI 10.1007/978-3-642-02930-1_47
  • [20] SELF-STABILIZATION
    SCHNEIDER, M
    [J]. COMPUTING SURVEYS, 1993, 25 (01) : 45 - 67
123