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

发布时间：2019-10-13 02:12

【摘要】：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完全问题,并设计了一种启发式贪婪算法进行求解.实验结果表明,针对典型的HS型、Ladder型骨干网络拓扑,使用NLCD的平均链路使用率比使用LCD低5%～15%,比使用NCD低7%～30%.
【图文】：

示意图,缓存,示意图,骨干

置的不同，而是实现方式的差异：ＮＣＤ通过降低ＩＳＰ骨干流量总和达到降低网络负载的目的，ＬＣＤ则是通过减少ＩＳＰ流量传输跳数以及均衡流量分布来缓解骨干网络压力．ＮＣＤ与ＬＣＤ的提出说明缓存部署于骨干节点或骨干链路均可以有效降低ＩＳＰ网络负载，然而ＮＣＤ单纯将部署位置限定于骨干节点，ＬＣＤ单纯将部署位置限定于骨干链路，能否通过在骨干节点与骨干链路的混合部署进一步提升缓存性能？Ｆｉｇ．１ＩＳＰｎｅｔｗｏｒｋｄｉａｇｒａｍｗｉｔｈＰ２Ｐｃａｃｈｅｓ．图１ＩＳＰ网络中Ｐ２Ｐ缓存部署示意图本文提出一种基于点路结合的骨干网Ｐ２Ｐ缓存部署方法（ｎｏｄｅ－ｌｉｎｋｂａｓｅｄｃａｃｈｅｄｅｐｌｏｙｍｅｎｔ，ＮＬＣＤ），同时将骨干节点和骨干链路作为备选部署位置．ＮＬＣＤ并不是ＮＣＤ与ＬＣＤ的简单叠加，本质上是融合ＮＣＤ和ＬＣＤ两种实现方式达到最小化ＩＳＰ骨干负载的目的，从而既能够降低ＩＳＰ骨干流量总和，也能够减少ＩＳＰ流量传输跳数和均衡流量分布．ＮＬＣＤ基本思想如下：建立以网络负载最小化为目标的缓存部署模型，该模型基于实际缓存替换算法进行缓存内容更新和缓存命中率估算；并将缓存１２３翟海滨等：一种基于点路结合的骨干网Ｐ２Ｐ缓存部署方法

示意图,缓存,示意图,流量

存的命中率为相同的定值以简化求解过程．如图２所示为利用ＬＣＤ部署缓存的示意图，假设图中节点１从节点４的Ｐ２Ｐ下载流量为４００Ｍｂｐｓ，节点３从节点４的Ｐ２Ｐ下载流量为６００Ｍｂｐｓ，无其他流量，缓存命中率为５０％．当缓存部署于链路３后，链路１和链路２上的流量不受影响，而链路３的流量由１Ｇｂｐｓ变为５００Ｍｂｐｓ，网络总流量减少了５００Ｍｂｐｓ．Ｆｉｇ．２ＣａｃｈｅｄｅｐｌｏｙｍｅｎｔｄｉａｇｒａｍｗｉｔｈＬＣＤ．图２ＬＣＤ缓存部署示意图文献［１２－１３］提出了基于骨干节点的缓存部署算法（ＮＣＤ），，其缓存部署位置即为图１所示的位置Ｂ，通过减少骨干节点对应的接入网络流入骨干网络的Ｐ２Ｐ流量，达到降低骨干网络负载的目的．建立了以缓存部署后单位字节平均传输跳数最小化为目标的最优化问题，然后利用动态规划法进行求解．目前不少Ｐ２Ｐ缓存产品［１４－１６］采用ＮＣＤ方法进行缓存部署，只是缓存部署位置稍有差别，为图１所示的位置Ｃ．如图３所示，为利用ＮＣＤ部署缓存的示意图，同样假设图中节点１从节点４的Ｐ２Ｐ下载流量为４００Ｍｂｐｓ，节点３从节点４的Ｐ２Ｐ下载流量为６００Ｍｂｐｓ，缓存命中率为５０％．当缓存部署于节点１后，链路２上的流量不受影响，而链路１和链路３的流量均减少２００Ｍｂｐｓ，因此总流量减少４００Ｍｂｐｓ．Ｆｉｇ．３ＣａｃｈｅｄｅｐｌｏｙｍｅｎｔｄｉａｇｒａｍｗｉｔｈＮＣＤ．图３ＮＣＤ缓存部署示意图ＮＣＤ算法的时间复杂度低于ＬＣＤ
【作者单位】：中国科学院计算技术研究所;中国科学院大学;
【基金】：国家“九七三”重点基础研究发展计划基金项目(2012CB315802) 国家自然科学基金项目(61070188,61100176) 中国博士后科学基金项目(2011M500401)
【分类号】：TP393.02

【参考文献】