Development of a fast routing algorithm for DHT at frequent joining of nodes

针对分布式软件系统的弹性问题，提出了一种在恒定度覆盖网络中的简单路由算法。该算法可用于P2P等分布式系统中提供特定资源的节点的高效定位，数学评价表明，该算法的期望度与节点数无关，期望路径长度与节点数成对数关系。该算法具有可扩展性，因为度数是恒定的，即当节点数量变大时，更新邻居的负载不会变得很大。仿真结果表明，与Chord算法相比，该算法丢失的消息数更少。

We propose a simple routing algorithm in a constant degree overlay network for resilience of distributed software systems. This algorithm can be used to efficiently locate nodes that provide a particular resource in distributed systems such as peer-to-peer (P2P) systems.Mathematical evaluation of the proposed algorithm shows the expected degree is constant not depending on the number of nodes, and the expected path length is logarithmic with the number of nodes. The proposed algorithm is scalable because the degree is constant, that is, the load of updating neighbors does not become high when the number of nodes becomes large. A simulation shows the number of lost messages for the proposed algorithm is less than that of Chord algorithm.