中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
移动环境中的Cache技术研究
作者: 周桓
答辩日期: 2001
专业: 计算机软件与理论
授予单位: 中国科学院软件研究所
授予地点: 中国科学院软件研究所
学位: 博士
关键词: 移动计算 ; 断连操作 ; 移动性 ; 数据收集 ; cache一致性
摘要: 迅速发展的无线数字通讯网络和便携式计算设备引入了一种全新的移动计算范型。在移动计算系统中,人们可以通过手持设备随时随地访问信息,甚至在移动中访问信息。软件是推动移动计算的最主要因素。然而,移动性约束打破了传统的分布式系统对计算环境的假定,使得传统的数据访问技术和算法在性能和可用性等方面不能满足移动计算系统的要求。Cache技术是提高数据访问性能的经典技术,已经在计算技术的多个方面得到了成功的应用。在移动计算环境中,由于设备的网络资源的限制,cache将发挥更加重要的作用。本文研究移动环境中的cache管理,着重解决其中的两个关键问题:自动数据收集和cache验证。论文首先考察了支持断连操作的数据收集问题。断连操作是移动计算中一个具有挑战性的问题,集中体现了移动环境的约束。数据收集算法就是确定用户将来最有可能访问的数据集的算法,它是影响断连操作成功率的主要因素。我们提出了一种基于概率图的自动数据收集算法-PDH算法。和其它的自动数据算法相比,PDH算法不仅可以有效地提高cache命中率,还具有很低的计算和存储开销,尤其适用于存储窨小的手持设备,是一种非常实用的算法。Cache验证算法的目的是确认客户本地缓存中的数据和服务吕上的数据是否一致,以保证应用系统不会读到脏数据。为了解决传统的回调算法在移动计算环境中所面临的两个主要问题:可扩展性和客户断连,我们提出了一种基于client/agent/server结构的卷回调验证算法。代理可以分担服务器的负载,提高系统的可扩展性;卷回调可以增大验证的粒度,加速因客户断连而造成的重新验证过程。在上述验证算汉的基础上,本文还从以下两个方面分别对基本算法进行了扩充。首先我们针对Web访问应用考察了分组策略,提出了基于文件修改时间的动态卷调整机制。这种动态调整机制通过拆分和合并两个过程使得每个卷保持合适的大小,并且使得经常被修改的文件趋向于分配到同一个卷中。试验结果表明改进后的验证算法可以在保证数据强一致性的前提下极大地减少客户断连后造成的重新验证开销,在总体性能上已经接近只提供弱数据一致性保证的ATTL算法。我们还考察了客户越区移动对基于client/agent/server结构的卷回调验证算法造成的影响,提出了支持客户移动的cache状态迁移协义-CSTP协议。CSTP协议允许同一个客户的cache状态分布在多个代理上,并利用伪代理来优化请求转发过程,从而同时具有注册过程快和对服务器完全透蝗的特点。我们利用模型检查工具形式化地验证了包含了CSTP协议的完整的cache验证算法的有效性。
英文摘要: Recent advances in wireless data networking and portable computing devices have engendered a new paradigm of computing, called mobile computing. In a mobile computing system, users access information anytime anywhere with their handheld devices, even when they are moving. Software is the most important factor to prompting mobile computing. Mobility constraints break key assumptions associated with distributed computing. As a result, most traditional mechanisms and algorithms have low performance in mobile environment. Caching is a classical technology to improve the performance of data access. It has been successfully applied to different fields of computing technology. Caching will be even more important in mobile systems because of resources limitations of mobile devices and wireless networks. This dissertation studies cache management in mobile computing environment from the perspective n the following issues: automated data hoarding and cache validation. The dissertation first addresses data hoarding problem, which is raised by disconnected operation. Disconnected operation is a challenging issue to all mobile systems. Data hoarding algorithm predicts data set of user's operation in the future. It is a major factor which affects cache hit rate when disconnected. We put forward the PDH algorithm which is an automated data hoarding algorithm based on probability graph. PDH algorithm effectively improves cache hit rate with light overhead. It is a practical algorithm, specially for handheld devices with small capacity of storage. To assure that applications never read dirty data, cache manager uses cache validation algorithm to determine whether data in local cache is consistent with the primary copy on the server. We propose a client/agent/server based volume callback-based algorithm to address two key issues of callback-based algorithms: scalability and client disconnection. Agents improve system scalability by mitigating load on servers; volume callbacks accelerate revalidation process by increasing granularity of validation. We also extend the above client/agent/server based volume callback algorithm from the following aspects. First, we propose a dynamic volume resizing mechanism for mobile Web browsing. Based on file's modify time, this dynamic mechanism, which is composed of splitting and combining procedures, keeps each volume at proper size. Frequently changed files incline to be moved to the same volume. Simulation results show that performance of the above strongly consistent algorithm is close to the weakly consistent ATTL algorithm. Second, we consider the impact of client mobility. To support seamless roaming of mobile clients, we develop a cache status migration protocol, named CSTP. It allows cache status of one client to be distributed on one or more agents. Shadow agent is introduced to optimize message relay. CSTP is distinguished by its fast registration process and server transparency. The whole validation algorithm, which supports CSTP, is formally verified with the Spin model checker.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/6006
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
LW004427.pdf(2443KB)----限制开放-- 联系获取全文

Recommended Citation:
周桓. 移动环境中的Cache技术研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 2001-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[周桓]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[周桓]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace