Some statistical characteristic will emerge in unstructured P2P networks because of its large scale. Using above phenomena, an unstructured P2P overlay called Multi-Level Local Overlay, or ML²O is presented in this paper. The mathematical control on the links can generate a topology with locality in multiple scale. Theoretical analyses show that the diameter of network and the average degree of peers are all O(logn) where n is the size of peers. Based on the multi-level locality, a recursive indexing mechanism is devised in this paper, in which the index for larger locality is build from the indexes of smaller localities Finally, an unstructured P2P search algorithm called Local Pervasion and Directed Search, or LPDS is presented in this paper. LPDS will collect information from local scope by executing local pervasion. Moreover, a part of the index tree can be achieved from the collected information. LPDS can find the next hop approaching the destination in the partial index tree. Theoretical analyses show that the expectation of average search hops and communication loads produced by LPDS are all O(logn). Experimental results illustrate the scalability of LPDS on ML²O is close to structured P2P search and its robustness is close to unstructured P2P search.

国家自然科学基金(60803148, 60973124)