云环境下副本优化放置策略研究

为了提高云计算数据调度和副本访问的效率,对副本策略中的副本放置问题进行研究,提出一种基于蚁群算法的副本放置策略。根据自然界中蚁群觅食的原理,把蚁群算法应用于副本放置的整个过程; 利用信息素的动态更新以及拉普拉斯概率分布改进的蚁群算法得出一组最优解进行副本放置。在CloudSim平台上进行了仿真模拟,实验结果表明,提出的方案在平均作业完成时间、网络利用率和负载均衡度上均优于原始蚁群算法,并在一定程度上降低了副本放置的时间消耗和网络负载。     

副本放置中的更新策略及算法

副本技术广泛应用于云计算及分布式系统中,合理的数据副本放置是降低网络运行成本的重要手段,也是副本技术的核心问题。副本更新是针对网络中数据访问请求的动态变化而进行的副本添加与删除。针对副本放置问题,提出了一种基于多访问策略的副本动态更新算法MPFSF(min_placement far servers first)。该算法在引入通信距离限制的同时,尽可能多地重用网络中已存在的副本,并根据需要实施必要的副本更新,最大使用每个副本的处理能力,以便降低数据访问的时延,提高数据访问效率。最后通过实验结果和分析证明,该算法在不同的通信距离限制下,网络的运行成本得到了明显的降低,对原有算法的改进最高可达84.6%。     

树上时延约束的代理服务器放置问题

该文考虑网络数据更新,需要控制代理服务器与目标服务器的距离时,树状网络上代理服务器的放置问题。利用二叉树结构和动态规划方法,得到了一个时间复杂度O(nhk)为多项式时间算法,其中n为网络结点数,k为代理服务器要放置的个数,h为树高。     

虫孔路由二维网孔机器上的最优图论算法

连通分量和最小生成树是图论中的两个基本问题 ,在许多领域都有很多应用 .对于顶点数为 n的图和规模为 p× p的虫孔路由二维网孔机器 ,该文针对 p n和 n

相似文献   

基于贪心算法思想的凸多边形最优三角剖分算法研究

当将多边形分割成互不相交的三角形的弦长之和最小时,称为最优三角剖分。在动态规划算法实现此功能的时间复杂度O(n3),空间复杂度O(n2)[1],采用贪心算法的时间复杂度是O(n2),空间复杂度是O(n),算法效率有明显的提升。贪心算法思想的最优剖分算法推广到三维空间,实现对多面体最优三角形椎体的剖分能得到非常现实的应用。     

一种构建最优二叉查找树的贪心算法

分析最优二叉查找树与哈夫曼树的异同,提出解决最优二叉查找树问题的贪心算法,证明算法的正确性,并用C++程序设计语言编码实现。该算法时间复杂度为O(n2),空间复杂度为O(n),实现了空间复杂度阶的突破。实验结果表明:所提出的贪心算法的效率明显优于动态规划算法。     

基于改进搜索策略的Live-Wire医学图像分割算法

Live-Wire 分割算法提供了一种精确的、可再现的交互式医学图像分割方法。Live-Wire算法中最优路径的搜索通常采用Dijkstra算法,其时间复杂度为O[n2]。提出从两个方面对Live-Wire医学图像分割算法的搜索策略进行改进以提高Live-Wire算法的实时性：（1）在最短路径的搜索过程中应用二叉堆排序,使算法的时间复杂度从原来的O[n2]降为O[n ln n];（2）在最短路径搜索中加入到达目标节点即停止的限制条件,可明显减少搜索节点数,使算法的时间复杂度远小于O[n ln n]。经算法分析及实验表明,搜索策略的改进可显著提高Live-Wire算法的运行效率。     

最长递增子序列问题研究

本文采用分治策略和动态规划策略探讨了最长递增子序列问题的两种解法,并分析了算法的计算复杂度。结果表明,本文算法的时间复杂度和空间复杂度分别为O(nlogn)和O(n)。     

求解区间图K-连接最短路径问题的在线算法

针对含有n个区间的区间图K-连接最短路径(K-SP)问题,提出一种求解区间图K-SP问题的在线算法。分析区间图及其最短路径问题的特有性质,利用改进的动态规划算法和贪心算法,优化在线算法的时间复杂度。理论分析结果表明,该算法的时间复杂度为O(nK+nlgn),与目前已知最优的离线算法复杂度相同。     

RNA二级结构预测算法

1引言 热动力学最小自由能量方法预测RNA二级结构起始于Tinoco等人[1].1975年Pipas与Mcmahom首先进行了最小化自由能量的计算方法的研究[2],其时间复杂度为O(2n),且仅用于小于200个核苷酸的短序列.Studnicka等进一步定义了折叠RNA分子的精密的拓朴规则[3],其算法的时间复杂度为O(n5),该算法需要人为干预,对较长序列的解一般是次最优的.Nussinov首次引入动态规划算法[5],算法只考虑临近碱基的相互作用,其时间复杂度为O(n3).Zuker首次将动态规划算法用于复杂的Tinoco自由能量模型,设计了mfold算法,算法的时间复杂度为O(n3)[6].Sankoff对mfold算法的性质进行了严格的理论分析[7].     

QoS-aware,access-efficient,and storage-efficient replica placement in grid environments

In this paper, we study the quality-of-service (QoS)-aware replica placement problem in grid environments. Although there has been much work on the replica placement problem in parallel and distributed systems, most of them concern average system performance and have not addressed the important issue of quality of service requirement. In the very few existing work that takes QoS into consideration, a simplified replication model is assumed; therefore, their solution may not be applicable to real systems. In this paper, we propose a more realistic model for replica placement, which consider storage cost, update cost, and access cost of data replication, and also assumes that the capacity of each replica server is bounded. The QoS-aware replica placement is NP-complete even in the simple model. We propose two heuristic algorithms, called greedy remove and greedy add to approximate the optimal solution. Our extensive experiment results demonstrate that both greedy remove and greedy add find a near-optimal solution effectively and efficiently. Our algorithms can also adapt to various parallel and distributed environments.     

网络中时延受限的代理服务器放置问题

该文考虑网络数据更新,需要控制代理服务器与客户的距离时,网络中的代理服务器的放置问题。找到代理服务器的最优数量和放置位置,使网络中数据访问的总花费（包括数据读取和更新）最小。利用二叉树结构和动态规划方法,得到了一个时间复杂度O（n²）的多项式时间算法,其中n为网络结点数。     

QoS-aware replica placement for content distribution

The rapid growth of new information services and business-oriented applications entails the consideration of quality of service (QoS) in content distribution. This paper investigates the QoS-aware replica placement problems for responsiveness QoS requirements. We consider two classes of service models: replica-aware services and replica-blind services. In replica-aware services, the servers are aware of the locations of replicas and can therefore optimize request routing to improve responsiveness. We show that the QoS-aware placement problem for replica-aware services is NP-complete. Several heuristic algorithms for fast computation of good solutions are proposed and experimentally evaluated. In replica-blind services, the servers are not aware of the locations of replicas or even their existence. As a result, each replica only serves the requests flowing through it under some given routing strategy. We show that there exist polynomial optimal solutions to the QoS-aware placement problem for replica-blind services. Efficient algorithms are proposed to compute the optimal locations of replicas under different cost models.     

蚊子产卵交配和模拟退火的混合优化数据副本放置机制

为了提高云存储系统的可扩展性、可靠性,同时改善用户访问能力,通常为其配备多数据副本机制,则不仅需要为数据副本选择合适的存储场地,而且需要实现用户访问请求对数据副本的优化分配。为此,提出了一种基于蚊子产卵交配和模拟退火混合优化数据副本放置机制。该机制以最小化总代价为优化目标,基于蚊子产卵交配思想确定数据副本候选放置方案,基于模拟退火进一步求精得到最优解。基于CloudSim,对该机制进行了仿真实现和性能评价,并且与现有的机制进行了对比分析,结果表明,该机制具有更好的性能,是可行和有效的。     

On Minimizing the Cost of Location Management in Mobile Environments

A mobile host typically has a home agent that maintains a registry of its current location. This registry is normally updated every time a host changes its current network. The update cost could be reduced using a two-tier update process in which a registry is updated using special agents, called proxy agents. We study the problem of selecting proxy agents to minimize the cost of search associated with this two-tier update approach. We show that the problem can be formulated as p-center or p-median finding problems. We focus on the p-center formulation. Due to the intractability of the problem, we introduce a distributed strategy to solve the general problem and show that it yields an approximate solution for arbitrary networks. We present an implementation of the distributed strategy that produces an optimal solution for ring networks. We prove that the optimal solution for rings is fault tolerant and resilient to topology changes.     

云存储智能多数据副本放置机制

数据副本管理机制是云存储系统的重要组成部分。为了提高云存储系统的可伸缩性、可靠性,同时改善用户访问时间,通常采用多数据副本机制,并且需要解决数据副本放置问题。为此,提出了一种用于云存储系统的智能多数据副本放置机制。该机制基于p-中心模型,以最小化访问代价为优化目标,基于遗传算法（genetic algorithm,GA）确定优化的数据副本放置方案,基于生物地理学优化（biogeography-based optimization,BBO）算法确定用户访问请求对数据副本的优化分配。基于CloudSim进行了仿真实现和性能评价,结果表明,云存储智能多数据副本放置机制是可行和有效的。     

An optimized strategy for update path selection in unstructured P2P networks

With the growth of P2P file sharing systems, people are no longer satisfied with the sharing of the read-only and static files, and thus the systems with mutually writable and dynamic files have emerged, resulting in the replica inconsistency problem. To maintain the replica consistency, too many update messages need to be redundantly propagated due to the lack of the sharing of globally updated path information in the existing strategies. To address this problem, we propose an optimized strategy for update path selection, which makes the nodes share the update path information by using clone, variation and crossover operations for the update paths. We also present a repeated update strategy to cope with the churn problem so as to maintain replica consistency as far as possible even if some nodes temporarily leave the network. The simulation results show that our strategy can significantly reduce the number of the redundant update messages without lowering the message coverage, thus improving the availability of the unstructured P2P networks.     

Optimized QoS-aware replica placement heuristics and applications in astronomy data grid

This paper studies the Quality-of-Service (QoS)-aware replica placement problem in a general graph model. Since the problem was proved NP-hard, heuristic algorithms are the current solutions to the problem. However, these algorithms cannot always find the effective replica placement strategy. We propose two algorithms that can obtain better results within the given time period. The first algorithm is called Cover Distance algorithm, which is based on the Greedy Cover algorithm. The second algorithm is an optimized genetic algorithm, in which we use random heuristic algorithms to generate initial population to avoid enormous useless searching. Then, the 0-Greedy-Delete algorithm is used to optimize the genetic algorithm solutions. According to the performance evaluation, our Cover Distance algorithm can obtain relatively better solution in time critical scenarios. Whereas, the optimized genetic algorithm is better when the replica cost is of higher priority than algorithm execution time. The QoS-aware data replication heuristic algorithms are applied into the data distribution service of an astronomy data grid pipeline prototype, and the operation process is studied in detail.     

基于萤火虫优化的副本放置方法

在云计算环境下分布式存储系统中,通常采用副本技术保证存储系统的可用性和可靠性,放置策略是副本技术的一个关键问题。针对现有副本放置策略中存在的副本访问开销大的问题,提出一种基于离散型萤火虫优化的副本放置算法。考虑副本放置对用户访问性能的影响,对其建立数学模型,计算萤火虫位置的适应度函数,并朝着荧光素值最大即最优值移动,进而得到合适的副本放置节点。通过仿真实验评估提出的方法,并与基于蚁群算法的副本放置策略进行比较。实验结果证明该算法能够选择合适的副本放置节点,具有较好的收敛性,并有效地降低存储系统的副本访问开销。