一种基于点路结合的骨干网P2P缓存部署方法

摘要

P2P应用的广泛流行给ISP骨干网络带来了前所未有的流量压力,P2P缓存(peer-to-peer caching)技术是目前缓解这种流量压力的最有效手段之一,缓存部署方法对P2P缓存系统的运行效率有重要影响.已有缓存部署方法分为两类:基于骨干节点的部署方法(node-based cache deployment,NCD)和基于骨干链路的部署方法(link-based cache deployment,LCD).在不同的P2P流量分布情形下,NCD与LCD各有优劣,但是,这两类方法未能充分发挥缓存的性能.提出一种基于点路结合的骨干网P2P缓存部署方法(node-Link based cache deployment,NLCD),根据缓存部署过程中P2P流量分布和缓存存储状态的动态变化,灵活选择骨干节点或骨干链路作为部署位置.建立了以网络负载最小化为目标的缓存部署模型,基于该模型将P2P缓存部署问题建模为一个最优化问题,由于流量分布和缓存状态会在部署过程中不断变化,不具有最优子结构性质.证明了该最优化问题为NP完全问题,并设计了一种启发式贪婪算法进行求解.实验结果表明,针对典型的H&S型、Ladder型骨干网络拓扑,使用NLCD的平均链路使用率比使用LCD低5％～15％,比使用NCD低7％～30％.%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.