2003/06/25 by Hui Zhang, Ashish Goel, Ramesh Govindan · 1 citation
Computer Science · #Caching and Content Delivery #Peer-to-Peer Network Technologies #Opportunistic and Delay-Tolerant Networks
paper · doi:10.1109/infcom.2002.1019373
openalex publication_date 2003/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Efficient data retrieval in a peer-to-peer system like Freenet is a challenging problem. We study the impact of cache replacement policy on the performance of Freenet. We find that, with Freenet's LRU (least recently used) cache replacement, there is a steep reduction in the hit ratio with increasing load. Based on intuition from the small-world models and the recent theoretical results by Kleinberg, we propose an enhanced-clustering cache replacement scheme for use in place of LRU. Such a replacement scheme forces the routing tables to resemble neighbor relationships in a small-world acquaintance graph - clustering with light randomness. In our simulation, this new scheme improved the request hit ratio dramatically while keeping the small average hops per successful request comparable to LRU. A simple, highly idealized model of Freenet under clustering with light randomness proves that the expected message delivery time in Freenet is O(log/sup 2/n) if the routing tables satisfy the small-world model and have the size /spl theta/(log/sup 2/n).