| Now,the main structure of Internet is still traditional C/S or B/S, whose remarkable characteristic of content center exactly creates the bottleneck question of visiting the server. Therefore, the P2P(peer to peer) network model was proposed, all nodes in the P2P network are at the same status, they both serve as the server and the client. The P2P network architecture made up the insufficiency of the traditional C/S structure, the two have its respective adaption scope, thus they inevitably exist and develop simultaneously, so any one would replace the other one completely is impossible.In view of the fact that to the P2P network model research, we discovered a core question that the P2P network architecture needs to solve is the efficient location question of distributed object in the network. Revolving this question, we carry on the analysis and comparison to each distributed object location method and the mechanism of the existing network, do the comparison and the summary to the performance of the existing P2P route algorithm .At present, the method that the distributed object localization generally uses is"the address inquires", in each kind of distributed system, because of the difference between system scale and the concrete demand, there are different realization method for the distributed object localization. According to the system structure, the distributed object localization mechanism could mainly divide into three kinds: the central structure, the level structure and the P2P network architecture. Considing the supports to the distributed system scale, the level structure is better than the central structure, and the P2P network architecture is better than the level structure. The P2P network architecture eliminates the bottleneck of the system performance, which extremely suits the large-scale distributed system.The P2P route question is how to determine the news transmission ways between any two nodes in the system. Similarly, the P2P route algorithm is how to determine the method of news transmission way between any two nodes in the system. There is corresponding relations between one kind of route algorithm and a P2P network, some characteristics of route algorithm could be saw through some network characteristics. By the topology research of the P2P network, the existing P2P route algorithm may divide into four kinds: the complete map, the ring(bidirectional), the tree and the typical P2P route algorithm. In recent years, the Plaxton, Can, Chord, Tapstry and Pastry proposed belong to the classics P2P route algorithm, they have considered the expansibility,correspondence efficiency and correspondence reliability synthetically, made effective compromise, so they are more suitable for large scale distributed system than the first three.The core of this article is that we expatiate the Chord protocol algorithm in detail, mapped the object and node to the identifier with the standard Hash function, the Consistent Hashing function completes the mapping from object to the node, and make improvement to the original Chord protocol algorithm.To be specific, the Chord protocol refers to how the object finds the node it rely on, how the new node join the system, as well as how the system recover to the perfect condition in the dynamic change process. In the application based on the Chord protocol, the node response for saving the object related, the Chord assign the object to the relevant node with Consistent Hashing function, each node share almost the same amount object, at the same time, only very few object needs to be moved when the node joins or leaves. In the Chord system, the node doesn't need to know all the nodes, only saving route information of a few nodes is ok, one node can correspond with other node and carry on the inquiry according to its route table. When node join or leave the system, make sure the route information and system change keeping synchronous. The Chord protocol has the characteristic of the load balance,the distributing,the expansibility,the usability and the naming flexible.The Chord has realized a kind of operation: assigns an object a key, then maps the key to some node, if assigns a key for all the objects in the peer-to-peer network, the object search question of the peer-to-peer network would be solved very easily. The Consistent Hashing function assigns m bits identifier for each node and the keyword, the node identifier can get by hash the IP of the node, and the keyword identifier can hash the keyword directly. Simultaneously, the length of expression must be long enough, so that two nodes or keywords hashing to the same identifier is impossible. In the hash function, each keyword is saved in its successor node, the successor node is the first node whose identifier is bigger than or equal to the keyword identifier. When node n joins the network, some keywords that belong to the successor of n will be assigned for n. When node n leave the network, all the keywords it has will be distributed to the successor of n. In addition, there's no other change in the network.One kind of simple but low effect object search algorithm of the Chord route algorithm is like this: in the Chord ring, each node only needs to establish connection with its successor, then the inquiry request will be transferred along the successor finger until find the node n, whose identifier is less than the keyword identifier and successor node is bigger, as a result the successor of node n is the node which inquired. This simple inquiry way is good at the expansibility, contrarily, the low speed is its fault, moreover its speed is unacceptable when the scale of network is bigger.Now let's introduce the expandable search algorithm of the Chord protocol. In order to accelerate the search speed, the Chord protocol maintain extra route information, as it makes each node maintain a route table, namely pointer table. This design has two important characteristics: first, every node only needs to know the one that close to it on the identifier ring, but doesn't need to know the farther nodes; second, each finger table has not enough information to determine the position of any object directly.For ensuring the inquiry can go on successfully when nodes changes, we must make sure that the successor finger of every node keep updating, the Chord protocol periodic transfers the"stabilization"function though background, leading the finger table and the change of successor node keep consistent.In the interest of keeping maintain the correct successor finger in the process of dealing with the disabled nodes, each node all manage a successor list including r immediate successors. If node n notice its successor node is disabled, it would replace the disabled one with the first normal node in the successor list.Making the improvement to the existing Chord protocol, we modify the search strategy of the Chord algorithm. We add another table to every node on the Chord ring, then put the frequently visited node into the table, in the case of this table dose not occupy too much space to accept, here the table is called quick search table. The search process lookups the quick table first, if find it, it's over; otherwise, goes on according to expandable search algorithm.Here we use P2PSim to carry on the simulation test, there are two groups simulation, making the compare between original expandable Chord protocol and the improved protocol from the mean lookup delay time and the mean lookup hops two aspects. The test result indicated that, the improved Chord route algorithm has certain improvement at the mean lookup delay protocol. In order to accelerate the search speed, the Chord protocol maintain extra route information, as it makes each node maintain a route table, namely pointer table. This design has two important characteristics: first, every node only needs to know the one that close to it on the identifier ring, but doesn't need to know the farther nodes; second, each finger table has not enough information to determine the position of any object directly. For ensuring the inquiry can go on successfully when nodes changes, we must make sure that the successor finger of every node keep updating, the Chord protocol periodic transfers the"stabilization"function though background, leading the finger table and the change of successor node keep consistent. In the interest of keeping maintain the correct successor finger in the process of dealing with the disabled nodes, each node all manage a successor list including r immediate successors. If node n notice its successor node is disabled, it would replace the disabled one with the first normal node in the successor list. Making the improvement to the existing Chord protocol, we modify the search strategy of the Chord algorithm. We add another table to every node on the Chord ring, then put the frequently visited node into the table, in the case of this table dose not occupy too much space to accept, here the table is called quick search table. The search process lookups the quick table first, if find it, it's over; otherwise, goes on according to expandable search algorithm. Here we use P2PSim to carry on the simulation test, there are two groups simulation, making the compare between original expandable Chord protocol and the improved protocol from the mean lookup delay time and the mean lookup hops two aspects. The test result indicated that, the improved Chord route algorithm has certain improvement at the mean lookup delay... |
PDF Full Text Request