Characteristics of Random Walk Search on Embedded Tree Structure for Unstructured P2Ps

We propose a random-walk-based file search for unstructured P2P networks. In the proposal, each node keeps two pieces of information, one is on the hop-limited shortest path tree rooted at itself and the other is on the indexes of files owned by neighbor nodes, referred to as the file list. A random-walk search is conducted along the concatenation of hop limited shortest path trees. To find a file, a node first checks its file list. If the requested file is found in the list, the node sends the file request message to the file owner, otherwise, it sends a file-search message to a randomly-selected leaf node on the hop-limited shortest path trees. Numerical examples show that our proposal is much more efficient than the normal random-walk search, while it waists much less network bandwidth than the flooding (network-broadcast) based search.