A Node-Link Based Cache Deployment Algorithm for P2P Traffic in ISP Networks

Peer-to-peer (P2P) systems are generating a large portion of the total Internet traffic and imposing a heavy burden on Internet services providers (ISPs). P2P caching is an effective means 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 topology is usually abstracted to a graph comprised of nodes representing core routers and links connecting adjacent core routers. While deploying caches at nodes (node-based cache deployment, NCD) can reduce the amount of P2P traffic transmitted from lower access networks to the ISP backbone network, deploying caches on links (link-based cache deployment, LCD) can directly reduce the amount of P2P traffic on the ISP backbone network. It is difficult to conclude whether NCD or LCD is better, because the ISP cost is dynamically changing as the P2P traffic matrix changes. In this paper, we propose a node-link based cache deployment method (NLCD). Firstly, we propose an analysis model and a corresponding deployment algorithm for NLCD. Then, we prove this problem is NP-complete and develop an optimal cache deployment problem based on this model. Experimental results show that NLCD outperforms NCD and LCD for both Hub and Spoke (H&S) networks and Ladder networks. The average link utilization of NLCD is 5%~15% lower than that of LCD, and 7%~30% lower than that of NCD.