内容分布网络缓存资源并行分配的博弈粒子场方法  

A Novel Game Particle-Field Approach to Parallel Cache Resource Allocation of CDN

作　　者：冯翔[1] 刘智满[1] 帅典勋[2] 

机构地区：[1]香港大学计算机科学系 [2]华东理工大学信息科学与工程学院

出　　处：《计算机学报》2007年第3期368-379,共12页Chinese Journal of Computers

基　　金：香港URG小项目(200607176155);国家自然科学基金重点项目(60135010);国家"九七三"重点基础研究发展规划项目基金(G1999032707);国家自然科学基金(60473044;60575040)资助

摘　　要：文章研究博弈粒子场方法对内容分布网络(CDN)缓存分配问题求解,通过建立相应的数学模型,将两阶段Web服务器-代理服务器缓存资源分配问题,映射为两个对偶力场中粒子的运动,力场中所有粒子按数学模型中定义的规则运动直至达到稳定状态,再由粒子的稳定状态反映射为Web服务器-代理服务器缓存资源分配问题的解.提出的适用于CDN的博弈广义粒子场模型(game particle-field(G-PF))置换方法,克服了现有常用的MFU、LFU、LRU等置换算法缓存间不能合作的缺点,发展成为合作的博弈置换算法.并用博弈理论简单地证明了所得到的解为全局Pareto最优解.这样,使G-PF置换算法能逼近理论上的Optimal置换算法,较Korupolu等提出合作的置换算法有更好的性能.This paper proposes a general expression for the framework of content delivery network and a novel and interesting game particle-field （G-PF） approach to content distribution problem. The game particle-field approach maps publisher-surrogate cache resource allocation problem to the movement of particles in two dual particle-fields by corresponding mathematical model in which all particles move according to certain defined rules until reaching a stable state. By anti-mapping the stable state, the solution to publisher-surrogate cache resource allocation problem can be obtained. The authors give proofs of the proposed approach in the consistency between physical model and mathematical model, the feasibility and correctness of the approach, and the existing and convergence of the solution. A distributed and parallel game particle-field replacement algorithm for cache resource allocation is introduced. As this replacement is cooperation-based, it has advantages over other replacement algorithms such as MFU, LFU, LRU. The authors prove that the replacement algorithm can reach Pareto optimization can approach the optimal solution achievable by any replacement algorithm.

关 键 词：内容分发网络 缓存资源分配 博弈粒子场 分布并行算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]