On the Relationship between Caching and Routing in DHTs

Although distributed hash tables (DHTs) are well suited for wide-area distributed applications, they suffer from high latencies (O (log N) in the average case). Such high latencies hinder them from being employed in many relevant wide-area applications such as DNS. To cope with this, a promising solution appears to be the caching of popular files. For effective caching, this requires that the caching protocol places the replicas in such a way that lookups paths are shortened. This implies to delve into the relationship between routing geometries and caching. In this paper, we explore the impact of routing on proactive caching using Chord as case study. To be specific, we clarify the role that path convergence plays upon caching and how this can be used to place file replicas. Also, we present a caching technique to increase the amount of path convergence for randomized topologies such as symphony, wherein the presence of a certain degree of path convergence is not guaranteed.