论文部分内容阅读
数据缓存是提高系统性能的一种有效方法,协同缓存通过一组节点相互共享缓存内容,可以极大提高分布式系统中信息访问的效率。
本文关注如何设计高效的协同缓存管理策略,研究的内容涉及有线网络和无线网络的缓存策略。在有线网络环境中,以优化系统的数据访问性能为目标,研究了基于层次式和分布式的协同缓存放置和替换策略。在无线环境中,研究了面向移动自组网的节能协同缓存替换策略,并提出了维护移动自组网缓存一致性的几种缓存失效策略。
本文的主要贡献归纳如下:
(1)提出了一种层次式协同缓存的放置和替换机制。本文首先提出了一个理论模型来分析在层次式网络中放置一组缓存副本带来的收益,然后,把缓存放置和替换问题形式化描述为一个最优化问题。这个最优化问题被证明可以分解为子问题,因此提出了使用动态规划来求问题最优解的算法。进一步证明可以证明,如果预先知道某些节点属于最优解的话,动态规划的计算开销可以进一步降低,提出了基于划分的动态规划解法。另外,本文还提出一种易于实现的启发式算法求近似解。
(2)提出了一种分布式协同缓存的放置和替换机制。通过对分布式缓存中缓存一组对象的收益进行理论分析。协同缓存放置和替换问题可以划归为一个最优化问题。它被证明可以划分为子问题,从而可以使用动态规划算法求出最优解。由于动态规划算法的复杂度较大,也可以使用启发式算法来求近似解。
(3)提出了移动自组网中一种节能的缓存替换策略。通过使用理论模型分析移动自组网中的数据访问的能量消耗,本文证明节能的缓存替换问题是一个0-1背包问题,并给出了求最优解的ECORP—OPT算法和求近似解的ECORP—Greedy算法。
(4)提出了移动自组网中三种缓存失效策略:POD,MAT andPAT。POD和MAT策略是从蜂窝网络中的基于“拉”和基于广播的简单策略修改而成。PAT是一种基于“拉”的策略,它保证缓存的△一致性。本文给出了这三种策略的缓存命中率的理论分析结果,并建立起仿真实验来比较几种策略的性能。理论和实验结果都表明PAT策略性能最好。关键词:协同缓存;层次式缓存;分布式缓存;移动自组网;节能;缓存失效数据缓存是提高系统性能的一种有效方法,协同缓存通过一组节点相互共享缓存内容,可以极大提高分布式系统中信息访问的效率。
本文关注如何设计高效的协同缓存管理策略,研究的内容涉及有线网络和无线网络的缓存策略。在有线网络环境中,以优化系统的数据访问性能为目标,研究了基于层次式和分布式的协同缓存放置和替换策略。在无线环境中,研究了面向移动自组网的节能协同缓存替换策略,并提出了维护移动自组网缓存一致性的几种缓存失效策略。
本文的主要贡献归纳如下:
(1)提出了一种层次式协同缓存的放置和替换机制。本文首先提出了一个理论模型来分析在层次式网络中放置一组缓存副本带来的收益,然后,把缓存放置和替换问题形式化描述为一个最优化问题。这个最优化问题被证明可以分解为子问题,因此提出了使用动态规划来求问题最优解的算法。进一步可以证明,如果预先知道某些节点属于最优解的话,动态规划的计算开销可以进一步降低,提出了基于划分的动态规划解法。另外,本文还提出一种易于实现的启发式算法求近似解。
(2)提出了一种分布式协同缓存的放置和替换机制。通过对分布式缓存中缓存一组对象的收益进行理论分析。协同缓存放置和替换问题可以划归为一个最优化问题。它被证明可以划分为子问题,从而可以使用动态规划算法求出最优解。由于动态规划算法的复杂度较大,也可以使用启发式算法来求近似解。
(3)提出了移动自组网中一种节能的缓存替换策略。通过使用理论模型分析移动自组网中的数据访问的能量消耗,本文证明节能的缓存替换问题是一个0-1背包问题,并给出了求最优解的ECORP—OPT算法和求近似解的ECORP—Greedy算法。
(4)提出了移动自组网中三种缓存失效策略:POD,MAT andPAT。POD和MAT策略是从蜂窝网络中的基于“拉”和基于广播的简单策略修改而成。PAT是一种基于“拉”的策略,它保证缓存的△一致性。本文给出了这三种策略的缓存命中率的理论分析结果,并建立起仿真实验来比较几种策略的性能。理论和实验结果都表明PAT策略性能最好。