Caching routing indices in structured P2P overlays

Because of the omnipresence of node dynamic activities, large scale P2P systems built on structured overlays suffer high maintenance overhead and compromised routing performance. In this paper, we study the characteristics of P2P node dynamic behaviors and present a novel routing indices caching scheme, called SORIC, which solves this problem by fully exploiting the round-trip pattern in node dynamic behaviors and heterogeneity among peers in the system. SORIC selectively caches routing indices of transient departed nodes in other relatively stable and capable nodes for two purposes. First, rejoin of the cached nodes is drastically simplified to O(1) complexity, thus cutting off a large portion of system maintenance overhead. Second, caching routing indices of departed nodes minimizes the negative effects of node departures and rejoins, and thus enables the system to sustain an uninterruptedly high quality routing service.