A node-link-based P2P cache deployment algorithm in ISP networks

Peer-to-peer (P2P) systems are imposing a heavy burden on internet services providers (ISPs). P2P caching is an effective way of easing this burden. We focus on the cache deployment problem as it has a significant impact on the effectiveness of caching. An ISP backbone network is usually abstracted to a graph comprising nodes representing core routers and links connecting adjacent core routers. While deploying P2P caches at nodes (NCD, node-based cache deployment) can reduce the amount of P2P traffic transmitted from access networks to the ISP backbone network, deploying P2P caches on links (LCD, link-based cache deployment) can directly reduce the amount of P2P traffic on the ISP backbone network. However, neither NCD nor LCD maximizes the performance of P2P caches. In this paper, we propose a node-link-based cache deployment method (NLCD), which optimally selects nodes or links as deployment locations during the cache deployment process. First, we propose an analysis model and define an optimal cache deployment problem for NLCD. Then, we prove that this problem is NP complete and develop a corresponding deployment algorithm. Experimental results show that the average link utilization of NLCD is 5-15% lower than that of LCD, and 7-30% lower than that of NCD.