主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2020年专刊出版计划 微信服务介绍 最新一期:2019年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李文中,陈道蓄,陆桑璐.分布式缓存系统中一种优化缓存部署的图算法.软件学报,2010,21(7):1524-1535
分布式缓存系统中一种优化缓存部署的图算法
Graph-Based Optimal Cache Deployment Algorithm for Distributed Caching Systems
投稿时间:2008-01-06  修订日期:2009-03-05
DOI:
中文关键词:  分布式缓存系统  缓存放置  图算法
英文关键词:distributed caching system  cache placement  graph-based algorithm
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60803111, 90718031, 60721002 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z199 (国家高技术研究发展计划(863)); the National Basic Research Program of China under Grant No.2009CB320705 (国家重点基础研究发展计划(973)); the Jiangsu Provincial Natural Science Foundation of China under Grant No.BK2009100 (江苏省自然科学基金)
作者单位
李文中 南京大学 计算机软件新技术国家重点实验室,江苏 南京 210093 
陈道蓄 南京大学 计算机软件新技术国家重点实验室,江苏 南京 210093 
陆桑璐 南京大学 计算机软件新技术国家重点实验室,江苏 南京 210093 
摘要点击次数: 3837
全文下载次数: 4184
中文摘要:
      数据缓存技术可以有效地减少网络拥塞,减轻服务器负载,加快信息访问速度.通过部署一组地域分布的缓存节点相互协作处理用户请求,可以进一步提高系统性能.在分布式缓存系统中,一个值得关注的问题是优化缓存的放置,使访问开销最小化.首先建立了一个理论模型来分析缓存副本放置对系统访问开销的影响.基于这个模型,缓存放置问题可以形式化地描述成一个最优化问题,提出了一种图算法来解决该问题.图算法使用修改的Dijkstra算法在访问代价图中寻找一条最短路径,该路径对应一种最优的缓存部署.理论上证明了图算法的正确性,并使用仿真实验对其性能进行评估.实验结果表明,图算法的性能优于大部分现有的分布式缓存机制.
英文摘要:
      Data caching has emerged as an effective way to reduce network traffic, alleviate server load and accelerate information access. Deploying a group of distributed caching nodes to cooperate with each other in serving client requests will further improve the system performance. One of the important issues in distributed caching system is coordinating cache placement to achieve access cost minimization. In this paper, a theoretical model is introduced to analyze the access cost of placing a set of data objects in distributed caching systems. In this model, the cache placement problem is formulated as an optimization problem. A graph-based algorithm is proposed to solve the problem. The algorithm applies a modified Dijkstra’s algorithm to look for the shortest path in the access cost graph, which corresponds to an optimal cache deployment for the system. The correctness of the graph-based algorithm is proved theoretically and its performance is evaluated by simulations. Experimental results show that the graph-based algorithm outperforms most existing distributed caching schemes.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利