Research And Design On Peer To Peer Overlay And It's Routing Algorithm

Peer-to-Peer systems (abbreviated to"P2P systems") have being experiencing a rapid growth in the past several years. And its goal is that, to create an inter-connected network environment for terminal users at the edge of network, in order to meet the direct -communication among users. So, the basic problems of which are how to construct such an overlay based peer-to-peer technology and how to route messages over this overlay. In this dissertation, we just focus on such problems. Main contribution of this dissertation is as follows.Firstly, the emergence and development of Peer-to-Peer technology are surveyed. In contrast with the traditional distributed system, new characteristic and application case and significance of research of P2P technology are presented.Sencondly, currently popular P2P overlay and it's relevant routing algorithm are presented and analized. Their shortcoming and strongpoint are brought out, and some methods to improve them are proposed. In addition, relevant theory of complex networks is introduced, emphases on property of small world of complex network.After this, according as sociology and histology and theory of complex network, Seizing the small world property and power law property of peer-to-peer overlay network, a Community Based Distributed Routing algorithm (CBDR) is proposed. The method is simple, fully distributed, applicable, and provable correctness. The CBDR Algorithm consists of dependable routing rule, performance routing rule, peer adding, peer deleting, community initializing and routing table information updating. The connectness of CBDR network is also proved, by method of modeling CBDR overlay using mathmatics.And then, proposing a new bidding-electing algorithm.A additive modulebased bidding-electing function, is proposed. The fairness, correctness and probability of success are argued. A multi-winner bidding-electing algorithm suitable for CBDR is also designed. This electing algorithm is based on ring topology and can be used to elect more than one winner. The details about how this algorithm can be used in CBDR to elect community eyes (CE) are also presented.Finally, some application system and network emulator are designed and implemented. Through the experience and data analysis, the applicable and validness of CBDR is proved.