Estimation Algorithms of Popular Objects on Distributed Hash Table Using Local Lookup Logs

Peer-to-Peer (P2P) systems are getting great inter- ests for infrastructures of various network services. For many purposes, such as decreasing delays, load balancing, and stability, many replica placement schemes are proposed for P2P systems. But it is difficult to place a large amount of replicas by some reasons such as limitation of storage and increase of control messages. Thus it is important to judge which data object must be replicated. The popularity of data objects is key information to decide the number of replicas, but it is difficult to know the whole popularity in pure P2P systems. In this paper, estimation algorithms of popular objects using local lookup logs stored in each peer are proposed. Experimental results show how well the algorithms can estimate popular objects. I. INTRODUCTION However, popularity of all objects cannot be observed in P2P systems without a/some centralized control(s), which is called pure P2P systems. That is, estimation of whole popularity in P2P systems is difficult, but is very important as fundamental research to decide the optimal number of replicas. In this paper, we discuss estimation methods for popularity of all objects using lookup logs, each of which is recorded locally on each peer. Our proposal is based on Chord(4) as the representative example of a DHT. At first, an esti- mation algorithm on a single peer using its local lookup log is described. Then the modified algorithm considering the nonuniform probability distribution of lookups is shown. Because the content of lookup log stored in a peer relies greatly on both where the peer is located and where data objects are located, it is difficult to estimate the popularity of whole system using only one lookup log on a peer. Thus, an algorithm, which estimates the whole popularity by merging some results of local estimations, is proposed. In addition, a modified algorithm, which focuses on coocurrence of objects' lookup among peers, is considered. Experimental results show how well proposed algorithms can estimate popular objects using measures of precision, recall, and f-measure. Also, the effectiveness of two modi- fications to the base algorithms are verified. The remainder of this paper is organized as follows. Section II mentions related work. Section III briefly describes Chord and our assumption for our proposal. Section IV proposes estimation algorithms of popular objects using local lookup logs on peers. In Section V, experimental results are shown to evaluate our proposal. Finally, Section VI concludes this paper.