Scalable replica selection based on node service capability for improving data access performance in edge computing environment

The replica strategies in traditional cloud computing often result in excessive resource consumption and long response time. In the edge cloud environment, if the replica node cannot be managed efficiently, it will cause problems such as low user’s access speed and low system fault tolerance. Therefore, this paper proposed replica creation and selection strategy based on the edge cloud architecture. The dynamic replica creation algorithm based on access heat (DRC-AH) and replica selection algorithms based on node service capability (DRS-NSC) were proposed. The DRC-AH uses data block as replication granularity and Grey Markov chain to dynamically adjust the number of replicas. After the replica is created, when client receives the user’s request, the DRS-NSC selects the best replica node to respond to the user. The experiments show that the proposed algorithms have significant advantages in prediction accuracy, user’s request response time, resource utilization, etc., and improve the performance of the system to a certain extent.

     

数据网格中请求呈现分组特性的副本管理策略研究

在数据网格中,数据使用模式将影响系统性能.根据一些实际系统的测试结果,数据请求呈现出分组特性.为研究当数据请求呈现分组特性时请求分布与副本分布的关系,首先定义了数据网格中副本复制策略的模型,然后研究在数据请求呈现分组特性时平均访问延迟最小的最优策略.采用拉格朗日乘子法以及二分法对上述模型进行求解,得到了一个在请求分组模式下的最优下载副本策略.通过模拟实验对最优策略以及均匀复制策略、比例复制策略、平方根复制策略、LRU缓存策略的性能进行了比较.结果表明,最优策略所需广域网带宽最少,平均访问延迟最小.     

个体QoS受限的数据网格副本管理与更新方法

数据网格系统通常采用副本技术提高系统总体性能,传统副本放置技术通过总体QoS需求确定副本数目和部署方式.针对QoS需求严格的一类数据网格应用,建立了个体服务质量受限的数据网格模型IQDG,提出一种启发式个体QoS受限的副本放置算法qGREP和基于逻辑环结构的一致性维护方法.IQDG采用的启发信息综合考虑了个体QoS约束的满足和副本开销的控制,能获得合理的副本策略.理论分析论证了算法的正确性和收敛性,模拟实验结果表明了算法能有效解决个体QoS受限的副本放置问题,在多种网络拓扑、访问模式和负载条件下均能取得较好的访问效果.     

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.     

云存储副本优化选择策略

为了提高云计算环境中系统的整体数据调度效率,对云存储系统中的副本选择问题进行研究,提出一种基于蚁群觅食原理的云存储副本优化选择策略。该策略利用蚁群算法在解决优化问题上的优势,将自然环境中蚁群的觅食过程与云存储中的副本选择过程相结合;再充分应用信息素的动态变化规律以及高斯概率分布特性优化副本的选择方式,得出一组副本资源的最优解,从而为数据请求响应合适的副本。在OptorSim仿真平台上对该算法进行实现,实验结果表明该算法具有不错的表现,如在平均作业用时这一性能指标上相比原始蚁群算法提升了18.7%,从而在一定程度上减少了副本选择过程的时间消耗,降低了网络负载。     

基于流媒体服务器集群副本放置策略的研究

网络流媒体服务具有数据流量大、服务时间长的特点,同时,高并发的服务请求会造成流媒体服务质量明显下降等性能瓶颈问题。针对这种现象,设计了一种基于Zipf分布规律的两阶段副本放置策略,并成功应用于某市中小学心理辅导的视讯平台。实践结果表明,与传统的方法相比,该方法具有较好的实用值和健壮性。     

磁道复制--多媒体数据读取的磁盘寻道优化策略

由于寻道是磁盘I／O操作中的主要浪费之一,采用磁道复制可以减少寻道．针对单盘与盘阵情况,磁道复制可以有两种不同的方法：n-way和n-d-way,并经推导可得出二者平均寻道距离的解析表达式.进行的模拟实验不仅证明了解析表达式的准确性,而且表明在相同的空间开销下,磁道复制策略比传统的以空间换取时间的策略如n-way striping和D-way mirror有更少的寻道距离．     

一种基于Grid的多媒体内容分布框架

基于互联网的大规模多媒体内容分发系统中,广泛地采用了数据复制技术来提高系统的性能。网格技术在构建大规模分布式信息系统方面,有着广阔的前景。本文提出了一种基于网格的多媒体内容分布框架,在网格基础服务的基础上,可以实现适用于流媒体应用的副本管理、传输和查找定位机制。此外,本文还对广域分布式信息系统中,副本的放置算法和用户请求调度机制等关键技术进行了深入探讨。     

Optimal positioning of read/write heads in mirrored disks

This work is concerned with finding the expected-travel-distance-minimizing anticipatory positions of disk arms in mirrored disk systems. In such systems, data is duplicated across two or more disk drives. A ‘read’ request may choose to read from any copy, and thus do so from the disk whose arm is closest to the request location. Since a ‘write’ must update all copies, the response time for such a request will depend on the distance of the arm which is furthest away from the request's location. Some problems of optimally positioning emergency service units on a line and of positioning idle elevators can be viewed mathematically as a special case of the mirrored disks scenario in which there are ‘read’ requests only. We show that, for any request location distribution, if there are more write than read requests then both arms should be located as if read requests did not exist — both at the median of the distribution. For situations where most requests are of ‘read’ type, we derive necessary conditions for optimal locations.     

P2P存储系统副本一致性维护策略

副本策略是提高P2P存储系统的可扩展性、容错性、可用性的有效手段。随着新的应用发展,P2P中副本应用从只读静态文件共享转变为读写动态文件交互,副本的一致性维护变得越来越重要。提出一种副本信息传播树的维护策略,该策略把文件副本的相关信息保存在二叉树上,通过订阅和取消订阅算法维护副本的一致。实验证明该策略能有效减少维护开销,避免相关问题的出现。     

Combination of data replication and scheduling algorithm for improving data availability in Data Grids

Data Grid is a geographically distributed environment that deals with large-scale data-intensive applications. Effective scheduling in Grid can reduce the amount of data transferred among nodes by submitting a job to a node, where most of the requested data files are available. Data replication is another key optimization technique for reducing access latency and managing large data by storing data in a wisely manner. In this paper two algorithms are proposed, first a novel job scheduling algorithm called Combined Scheduling Strategy (CSS) that uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers the number of jobs waiting in queue, the location of required data for the job and the computing capacity of sites. Second a dynamic data replication strategy, called the Modified Dynamic Hierarchical Replication Algorithm (MDHRA) that improves file access time. This strategy is an enhanced version of Dynamic Hierarchical Replication (DHR) strategy. Data replication should be used wisely because the storage capacity of each Grid site is limited. Thus, it is important to design an effective strategy for the replication replacement. MDHRA replaces replicas based on the last time the replica was requested, number of access, and size of replica. It selects the best replica location from among the many replicas based on response time that can be determined by considering the data transfer time, the storage access latency, the replica requests that waiting in the storage queue and the distance between nodes. The simulation results demonstrate the proposed replication and scheduling strategies give better performance compared to the other algorithms.     

基于随机因子和年龄的副本维护策略

副本技术是提高结构化P2P网络中数据可用性、数据访问效率的一种主要技术。ARMS策略虽然可以选择到稳定的副本节点,但是它也带来了副本分布不均衡的问题。为了选择稳定的副本节点并避免单个节点保存过多副本,在充分分析ARMS策略不足的基础上,提出基于随机因子和年龄的副本维护策略。该策略在ARMS策略的基础上加入随机因子s,使得副本既保持稳定又在一定程度上分散。对该策略的分析以及最后的模拟实验表明,该策略结合了随机邻居选择策略和ARMS策略的优点,能够达到以上效果。同时,对随机因子s的选择进行充分分析后得出,s为l/r时效果比较好。     

Network and data location aware approach for simultaneous job scheduling and data replication in large-scale data grid environments

Data Grid integrates graphically distributed resources for solving data intensive scientific applications. Effective scheduling in Grid can reduce the amount of data transferred among nodes by submitting a job to a node, where most of the requested data files are available. Scheduling is a traditional problem in parallel and distributed system. However, due to special issues and goals of Grid, traditional approach is not effective in this environment any more. Therefore, it is necessary to propose methods specialized for this kind of parallel and distributed system. Another solution is to use a data replication strategy to create multiple copies of files and store them in convenient locations to shorten file access times. To utilize the above two concepts, in this paper we develop a job scheduling policy, called hierarchical job scheduling strategy (HJSS), and a dynamic data replication strategy, called advanced dynamic hierarchical replication strategy (ADHRS), to improve the data access efficiencies in a hierarchical Data Grid. HJSS uses hierarchical scheduling to reduce the search time for an appropriate computing node. It considers network characteristics, number of jobs waiting in queue, file locations, and disk read speed of storage drive at data sources. Moreover, due to the limited storage capacity, a good replica replacement algorithm is needed. We present a novel replacement strategy which deletes files in two steps when free space is not enough for the new replica: first, it deletes those files with minimum time for transferring. Second, if space is still insufficient then it considers the last time the replica was requested, number of access, size of replica and file transfer time. The simulation results show that our proposed algorithm has better performance in comparison with other algorithms in terms of job execution time, number of intercommunications, number of replications, hit ratio, computing resource usage and storage usage.     

Adaptive popularity-driven replica placement in hierarchical data grids

Data grids support access to widely distributed storage for large numbers of users accessing potentially many large files. Efficient access is hindered by the high latency of the Internet. To improve access time, replication at nearby sites may be used. Replication also provides high availability, decreased bandwidth use, enhanced fault tolerance, and improved scalability. Resource availability, network latency, and user requests in a grid environment may vary with time. Any replica placement strategy must be able to adapt to such dynamic behavior. In this paper, we describe a new dynamic replica placement algorithm, Popularity Based Replica Placement (PBRP), for hierarchical data grids which is guided by file “popularity”. Our goal is to place replicas close to clients to reduce data access time while still using network and storage resources efficiently. The effectiveness of PBRP depends on the selection of a threshold value related to file popularity. We also present Adaptive-PBRP (APBRP) that determines this threshold dynamically based on data request arrival rates. We evaluate both algorithms using simulation. Results for a range of data access patterns show that our algorithms can shorten job execution time significantly and reduce bandwidth consumption compared to other dynamic replication methods.     

Understanding and improvement of the selection of replica servers in key–value stores

In current large-scale distributed key–value stores, the tail latency of the hundreds of key–value access operations generated by an end-user request determines the response time of this request. Therefore, this tail latency has great impacts on the user experience and revenue. Replica selection algorithms, which select the best replica server for the service of each key–value access operation as much as possible, is the key to cut the tail latency of these key–value access operations. This paper summarizes current replica selection algorithms, including both the algorithms employed by current key–value stores and the classic algorithms of other similar systems. These algorithms are classified into three categories: information-agnostic, client-independence and feedback, according to their demanded information. As a step further, simulation-based performance analysis of these algorithms is conducted. The result brings us the insights that the response time (RPT) is useful to measure the service rate, but will lead to the herd behaviors. Moreover, the number of outstanding key–value access operations (OSKs) is helpful to both the selection of the fastest replica server and the avoidance of herd behaviors. Based on these insights, we design the L2 algorithm by assembling the basic ideas of the Least OSK algorithm and the Least RPT algorithm. The L2 algorithm is much simpler than the recently proposed C3 algorithm and has a similar best performance with C3 as confirmed by the simulation and experimental results.     

Optimal dynamic pricing for deteriorating items with reference-price effects

In this paper, a dynamic pricing problem for deteriorating items with the consumers’ reference-price effect is studied. An optimal control model is established to maximise the total profit, where the demand not only depends on the current price, but also is sensitive to the historical price. The continuous-time dynamic optimal pricing strategy with reference-price effect is obtained through solving the optimal control model on the basis of Pontryagin's maximum principle. In addition, numerical simulations and sensitivity analysis are carried out. Finally, some managerial suggestions that firm may adopt to formulate its pricing policy are proposed.     

Adaptive data replication strategy in cloud computing for performance improvement

Cloud computing is becoming a very popular word in industry and is receiving a large amount of attention from the research community. Replica management is one of the most important issues in the cloud, which can offer fast data access time, high data availability and reliability. By keeping all replicas active, the replicas may enhance system task successful execution rate if the replicas and requests are reasonably distributed. However, appropriate replica placement in a large-scale, dynamically scalable and totally virtualized data centers is much more complicated. To provide cost-effective availability, minimize the response time of applications and make load balancing for cloud storage, a new replica placement is proposed. The replica placement is based on five important parameters: mean service time, failure probability, load variance, latency and storage usage. However, replication should be used wisely because the storage size of each site is limited. Thus, the site must keep only the important replicas.We also present a new replica replacement strategy based on the availability of the file, the last time the replica was requested, number of access, and size of replica. We evaluate our algorithm using the CloudSim simulator and find that it offers better performance in comparison with other algorithms in terms of mean response time, effective network usage, load balancing, replication frequency, and storage usage.     

A new marketing strategy map for direct marketing

Direct marketing is one of the most effective marketing methods with an aim to maximize the customer’s lifetime value. Many cost-sensitive learning methods which identify valuable customers to maximize expected profit have been proposed. However, current cost-sensitive methods for profit maximization do not identify how to control the defection probability while maximizing total profits over the customer’s lifetime. Unfortunately, optimal marketing actions to maximize profits often perform poorly in minimizing the defection probability due to a conflict between these two objectives. In this paper, we propose the sequential decision making method for profit maximization under the given defection probability in direct marketing. We adopt a Reinforcement Learning algorithm to determine the sequential optimal marketing actions. With this finding, we design a marketing strategy map which helps a marketing manager identify sequential optimal campaigns and the shortest paths toward desirable states. Ultimately, this strategy leads to the ideal design for more effective campaigns.     

无结构P2P覆盖网络的拓扑优化

研究了全分布无结构P2P(peer-to-peer)网络拓扑的最优化问题.通常认为,无结构P2P网络拓扑属于Power-Law结构.然而,Power-Law并非对所有应用都是最好的选择.首先研究了无结构P2P覆盖网络结构对无结构P2P搜索的影响,给出了结点度分布、访问频率模式和搜索成功率之间的关系.然后基于数据访问频率分布,给出了结点度的优化分布模型.实验结果表明,该无结构P2P拓扑优化结构在提高搜索成功率方面是有效的.该工作对构造合理的覆盖网络拓扑具有重要意义,同时将加深对无结构P2P环境下数据部署问题的认识.     

基于模拟退火算法的数据网格副本部署策略

副本管理是提高网格性能、降低客户端延迟的有效手段。针对副本部署策略问题,提出基于模拟退火算法的副本部署策略,给出优化模型及算法。OptorSim的仿真结果表明,该策略可减少作业对文件请求的响应时间,提高系统的整体性能。目前该策略已在大庆油田海量数据中心副本部署中得到成功应用。