An Application Of P2P To Instant Messaging Systems

At the present time, Instant Messaging (IM) systems are widely used and becoming more and more important in people's life. In the past, most IM Systems were designed based on C/S model, in which the Server should perform all the tasks: identity verification, locating and looking up objects, routing and so on, all of these tasks cause the Server a heavy burden. Hence, for a system demanding instantaneity and high-quality service, especially for an IM system which emphasizes audio/video service, Server becomes the main bottle-neck. The emergence of P2P brings a feasible solution to the problem. Chapter 1 briefly outlines the history of the development of the IM systems, the history of the development of P2P, and the application of P2P as well as the research on it. The research project and research work of this thesis are also clarified in chapter 1.According to the technical features of P2P,problems of the research on P2P and application of it mainly concentrate on the Overlay network, including self-organization, extensibility, self-adaptation, locating and looking up objects, routing, etc. Surrounding those properties, the directions in current research include the compromise between state and efficiency, fault-tolerance, hot-routing, match with physical network and isomer and so on. A combination of those research leads to an outstanding P2P protocol, which is also the key part of research on P2P and the application of it.The thesis, which is supported by an IM project - Virtual Date(VDate) system, overall designs the VDate system according to the project requirement analysis and the technical features of P2P, divides the VDate system into 4 modules, and designs a complete P2P protocol: VDate as well as a locating and looking up objects, routing algorithm with good performance: KAD-VDate. At last, VDate protocol and KAD-VDate algorithm are both implemented in VDate system.From centralized P2P initially to the more mature hybrid P2P, P2P's Overlay network topology is developing towards pure P2P now. After analyzing the principles, merits and feasibility of those three modes, the thesis selects hybrid P2P as VDate's Overlay network topology, studies and designs VDate protocol. In compliance with VDate protocol, VDate's Overlay network can establish independently and adapt well with kinds of dynamic circumstances, which make the Overlay have good self-organization and self-adaptation.In addition, the Overlay network topology relate closely to the going through method of NAT/FW in VDate protocol. In the protocol, UDP Hole Punching is used for going through NAT while HTTP Tunnel is used for going through FW. Combining with routing strategies, nodes on the Overlay network are made to communicate with each other as directly as possible, which reduces the burdens ofSN furthest. This design transcends the traditional topology with "fixed" agent of SN, and gives a more flexible, more Self-organizational one.As the kernel of P2P technology, locating, looking up the objects and routing algorithm has developed from the original Flooding model to Distributed Hash Table (DHT) model. DHT provides p2p systems a serial of nice performance, such as the consistent distributing of mega data, the exact locating and routing with few hops, etc. However, DHT also faces several difficult problems while it brings advantages, of these problems the most important ones are: (1) while high, uniform distribution is the characteristics of DHT, it's difficult to reduce the search routing hops; (2)as we know that the real network is heavy dynamic because nodes can join or leave at any time, while DHT algorithm orders each key in its fixed positions, which makes Overlay network become structured, then the structural network can not adapt those dynamic changes neatly; (3) The flat topology and the logical network's mismatch even independence with the physical network make the nodes selected unreliable, which lead to less accuracy and lower effectiveness of locating and routing than expected. Based on the two former problems, a lot of algorithms were designed, such as the well-known CAN, Chord, Kademlia and so on. All of those algorithms have their own features, but they all did not take the third problem into account, this is also a common disadvantage of all DHT algorithms that has existed.Inspired by the small-world theory in the real world, after analyzing those three issues above, especially the last one, based on Kademlia algorithm, a new DHT algorithm-KAD-VDate algorithm is designed. Compared with previous DHT algorithms, KAD-VDate makes improvements mainly in following areas:(1) The topology of algorithm. Though the flat topology of CAN, Chord and Kademlia is relatively simple, it is poor in management and unreliable on selecting nodes. In contrast, KAD-VDate designs a hierarchical topology with the binary tree topology to improve that. Based on the binary tree used in Kademlia, KAD-VDate adds the evaluation of the capability of nodes. Factors considered include the ability of communications, bandwidth of Internet access and speed, stability, time online and calculating ability and so on. Nodes are divided into different hierarchies. The node's ability and the physical distance between each other are also recoded to facilitate future management and routing.(2) The strategy of routing. KAD-VDate adds node's ability: physical distance as the second gist to the traditional logical distance's fulfilling. This is an attempt to solve the problem that the logical network mismatches with the physical network in DHT.The proving process of correctness and performance in theory of KAD-VDate is the same as that of Kademlia,so it is not described in the thesis. The results of simulating Test for KAD-VDate algorithm and test in the real physical network for VDate system both show that the performance of algorithm considering physical network has improved greatly, especially when the network changes dynamically, the algorithm can reducing routing time and improve the possibility of the success of locating to great extent. Those results mean that the correlation of physical networkis an important issue, considering it can enhance the accessibility and reliability of nodes, and then make each routing more effective and improve the Overlay network's performance. Meanwhile, the testing results also show that KAD-VDate algorithm and VDate protocol are correct, feasible.As the third generation network technology, P2P is more and more popular in research and application. The significance of the research work in this thesis is not only to provide customers an excellent IM system, but also to provide a feasible solution to some of the issues and problems existing in P2P's application as well as to offer a feasible,meaningful evidence and basis for further research and application, which is the most important. VDate protocol and KAD-VDate algorithm are not only proper for IM area but also for some other application areas of P2P.