Placement of Data Replicas for Optimal Data Availability in Ring Networks

This paper discusses the problem of placing data replicas in a ring network to maximize data availability. For read-any/write-all protocol, we prove that the equally spacing placement is optimal for read-dominant systems, while the grouping placement is optimal for write-dominant systems. For majority-voting protocol, we give some necessary conditions for optimal placements.     

Optimal replica placement in hierarchical Data Grids with locality assurance

In this paper, we address three issues concerning data replica placement in hierarchical Data Grids that can be presented as tree structures. The first is how to ensure load balance among replicas. To achieve this, we propose a placement algorithm that finds the optimal locations for replicas so that their workload is balanced. The second issue is how to minimize the number of replicas. To solve this problem, we propose an algorithm that determines the minimum number of replicas required when the maximum workload capacity of each replica server is known. Finally, we address the issue of service quality by proposing a new model in which each request must be given a quality-of-service guarantee. We describe new algorithms that ensure both workload balance and quality of service simultaneously.     

Replica Placement Strategies in Data Grid

Replication is a technique used in Data Grid environments that helps to reduce access latency and network bandwidth utilization. Replication also increases data availability thereby enhancing system reliability. The research addresses the problem of replication in Data Grid environment by investigating a set of highly decentralized dynamic replica placement algorithms. Replica placement algorithms are based on heuristics that consider both network latency and user requests to select the best candidate sites to place replicas. Due to dynamic nature of Grid, the candidate site holds replicas currently may not be the best sites to fetch replicas in subsequent periods. Therefore, a replica maintenance algorithm is proposed to relocate replicas to different sites if the performance metric degrades significantly. The study of our replica placement algorithms is carried out using a model of the EU Data Grid Testbed 1 [Bell et al. Comput. Appl., 17(4), 2003] sites and their associated network geometry. We validate our replica placement algorithms with total file transfer times, the number of local file accesses, and the number of remote file accesses.     

Optimal Replica Placement under TTL-Based Consistency

Geographically replicating popular objects in the Internet speeds up content distribution at the cost of keeping the replicas consistent and up-to-date. The overall effectiveness of replication can be measured by the total communication cost consisting of client accesses and consistency management, both of which depend on the locations of the replicas. This paper investigates the problem of placing replicas under the widely used TTL-based consistency scheme. A polynomial-time algorithm is proposed to compute the optimal placement of a given number of replicas in a network. The new replica placement scheme is compared, using real Internet topologies and Web traces, against two existing approaches which do not consider consistency management or assume invalidation-based consistency scheme. The factors affecting their performance are identified and discussed     

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.     

Analysis of Replica Placement under Expiration-Based Consistency Management

Expiration-based consistency management is widely used to keep replicated contents up-to-date in the Internet. The effectiveness of replication can be characterized by the communication costs of client accesses and consistency management. Both costs depend on the locations of the replicas. This paper investigates the problem of placing replicas in a network where replica consistency is managed by the expiration-based scheme. Our objective is to minimize the total cost of client accesses and consistency management. By analyzing the communication cost of recursive validations for cascaded replicas, we prove that in the optimal placement scheme, the nodes not assigned replicas induce a connected subgraph that includes the origin server. Our results are generic in that they apply to any request arrival patterns. Based on the analysis, an O(D)-time algorithm is proposed to compute the optimal placement of the replicas, where D is the sum of the number of descendants over all nodes in the routing tree     

Modeling a Dynamic Data Replication Strategy to Increase System Availability in Cloud Computing Environments

Failures are normal rather than exceptional in the cloud computing environments. To improve system avai- lability, replicating the popular data to multiple suitable locations is an advisable choice, as users can access the data from a nearby site. This is, however, not the case for replicas which must have a fixed number of copies on several locations. How to decide a reasonable number and right locations for replicas has become a challenge in the cloud computing. In this paper, a dynamic data replication strategy is put forward with a brief survey of replication strategy suitable for distributed computing environments. It includes: 1) analyzing and modeling the relationship between system availability and the number of replicas; 2) evaluating and identifying the popular data and triggering a replication operation when the popularity data passes a dynamic threshold; 3) calculating a suitable number of copies to meet a reasonable system byte effective rate requirement and placing replicas among data nodes in a balanced way; 4) designing the dynamic data replication algorithm in a cloud. Experimental results demonstrate the efficiency and effectiveness of the improved system brought by the proposed strategy in a cloud.     

Secure Data Objects Replication in Data Grid

Secret sharing and erasure coding-based approaches have been used in distributed storage systems to ensure the confidentiality, integrity, and availability of critical information. To achieve performance goals in data accesses, these data fragmentation approaches can be combined with dynamic replication. In this paper, we consider data partitioning (both secret sharing and erasure coding) and dynamic replication in data grids, in which security and data access performance are critical issues. More specifically, we investigate the problem of optimal allocation of sensitive data objects that are partitioned by using secret sharing scheme or erasure coding scheme and/or replicated. The grid topology we consider consists of two layers. In the upper layer, multiple clusters form a network topology that can be represented by a general graph. The topology within each cluster is represented by a tree graph. We decompose the share replica allocation problem into two subproblems: the Optimal Intercluster Resident Set Problem (OIRSP) that determines which clusters need share replicas and the Optimal Intracluster Share Allocation Problem (OISAP) that determines the number of share replicas needed in a cluster and their placements. We develop two heuristic algorithms for the two subproblems. Experimental studies show that the heuristic algorithms achieve good performance in reducing communication cost and are close to optimal solutions.     

Analyzing User-Perceived Dependability and Performance Characteristics of Voting Algorithms for Managing Replicated Data

User-perceived dependability and performance metrics are very different from conventional ones in that the dependability and performance properties must be assessed from the perspective of users accessing the system. In this paper, we develop techniques based on stochastic Petri nets (SPN) to analyze user-perceived dependability and performance properties of quorum-based algorithms for managing replicated data. A feature of the techniques developed in the paper is that no assumption is made regarding the interconnection topology, the number of replicas, or the quorum definition used by the replicated system, thus making it applicable to a wide class of quorum-based algorithms. We illustrate this technique by comparing conventional and user-perceived metrics in majority voting algorithms. Our analysis shows that when the user-perceiveness is taken into consideration, the effect of increasing the network connectivity and number of replicas on the availability and dependability properties perceived by users is very different from that under conventional metrics. Thus, unlike conventional metrics, user-perceived metrics allow a tradeoff to be exploited between the hardware invested, i.e., higher network connectivity and number of replicas, and the performance and dependability properties perceived by users.     

A timeout-based message ordering protocol for a lightweight software implementation of TMR systems

Replicated processing with majority voting is a well-known method for achieving reliability and availability. Triple modular redundant (TMR) processing is the most commonly used version of that method. Replicated processing requires that the replicas reach agreement on the order in which input requests are to be processed. Almost all synchronous and deterministic ordering protocols published in the literature are time-based in the sense that they require replicas' clocks to be kept synchronized within some known bound. We present a protocol for TMR systems that is based on timeouts and does not require clocks to be kept in bounded synchronism. Our design efforts focus on keeping the ordering delays small, without an unnecessary increase in message overhead. Consequently, we are able to show that no symmetric protocol that works only with unsynchronized clocks can provide a smaller worst-case delay. We also demonstrate through analysis and experiments that our protocol is faster than a time-based one of identical message complexity in certain situations which can prevail in many application settings.     

云存储中动态副本放置机制研究

数据副本管理是云计算系统管理的重要组成部分,在云计算系统的海量数据处理过程中,针对目前已知的数据存放与资源调度算法存在考虑副本动态性和可靠性的不足,提出了一种动态的副本放置机制。该机制基于区域结构,考虑数据处理时其副本的数量和放置位置,以及副本的产生对于内存和带宽等系统资源的开销:首先根据云存储中的副本信息,对被访问频率高且访问平均响应时间长的数据信息进行复制,并给出副本数量的计算方法;考虑缩小副本分布的节点选择范围,提出动态的副本放置算法——DRA,将一定范围内的节点根据提出的域的划分,进行放置筛选,以存放数据副本。实验结果表明,提出的动态放置机制不仅减少了低访问率副本对系统存储空间的浪费;同时也减少了高访问率副本所需跨节点的传输延迟,有效提高了云存储系统中的数据文件的访问效率、负载的均衡水平,以及云存储系统的可靠性和可用性。     

The column protocol: A high availability and low message cost solution for managing replicated data

This paper presents a quorum-based replica control protocol which is resilient to network partitioning. In the best case, the protocol generates quorums of a constant size. When some replicas are inaccessible, the quorum size increases gradually and may be as large as O(n), where n is the number of replicas. However, the expected quorum size is shown to remain constant as n grows. This is a desirable property since the message cost for accessing replicated data is directly proportional to the quorum size. Moreover, the availability of the protocol is shown to be comparably high. With the two properties—constant expected quorum size and comparably high availability—the protocol is thus practical for managing replicated data.     

Optimal sensor placement for target localisation and tracking in 2D and 3D

This paper analytically characterises optimal sensor placements for target localisation and tracking in 2D and 3D. Three types of sensors are considered: bearing-only, range-only and received-signal-strength. The optimal placement problems of the three sensor types are formulated as an identical parameter optimisation problem and consequently analysed in a unified framework. Recently developed frame theory is applied to the optimality analysis. We prove necessary and sufficient conditions for optimal placements in 2D and 3D. A number of important analytical properties of optimal placements are further explored. In order to verify the analytical analysis, we present a gradient control law that can numerically construct generic optimal placements.     

Efficient algorithms of video replication and placement on a cluster of streaming servers

A cost-effective approach to building up scalable video streaming servers is to couple a number of streaming servers together in a cluster so as to alleviate the inherent storage and networking constraints of streaming services. In this article, we investigate a crucial problem of video replication and placement on a distributed storage cluster of streaming servers for high quality and high availability services. We formulate it as a combinatorial optimization problem with objectives of maximizing the encoding bit rate and the number of replicas of each video and balancing the workload of the servers. The objectives are subject to the constraints of the storage capacity and the outgoing network-I/O bandwidth of the servers. Under the assumption of single fixed encoding bit rate for all video objects with different popularity values, we give an optimal replication algorithm and a bounded placement algorithm, respectively. We further present an efficient replication algorithm that utilizes the Zipf-like video popularity distributions to approximate the optimal solutions, which can reduce the complexity of the optimal replication algorithm. For video objects with scalable encoding bit rates, we propose a heuristic algorithm based on simulated annealing. We conduct a comprehensive performance evaluation of the algorithms and demonstrate their effectiveness via simulations over a synthetic workload set.     

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.     

Distributed data possession checking for securing multiple replicas in geographically-dispersed clouds

Distributing multiple replicas in geographically-dispersed clouds is a popular approach to reduce latency to users. It is important to ensure that each replica should have availability and data integrity features; that is, the same as the original data without any corruption and tampering. Remote data possession checking is a valid method to verify the replicas?s availability and integrity. Since remotely checking the entire data is time-consuming due to both the large data volume and the limited bandwidth, efficient data-possession-verifying methods generally sample and check a small hash (or random blocks) of the data to greatly reduce the I/O cost. Most recent research on data possession checking considers only single replica. However, multiple replicas data possession checking is much more challenging, since it is difficult to optimize the remote communication cost among multiple geographically-dispersed clouds. In this paper, we provide a novel efficient Distributed Multiple Replicas Data Possession Checking (DMRDPC) scheme to tackle new challenges. Our goal is to improve efficiency by finding an optimal spanning tree to define the partial order of scheduling multiple replicas data possession checking. But since the bandwidths have geographical diversity on the different replica links and the bandwidths between two replicas are asymmetric, we must resolve the problem of Finding an Optimal Spanning Tree in a Complete Bidirectional Directed Graph, which we call the FOSTCBDG problem. Particularly, we provide theories for resolving the FOSTCBDG problem through counting all the available paths that viruses attack in clouds network environment. Also, we help the cloud users to achieve efficient multiple replicas data possession checking by an approximate algorithm for tackling the FOSTCBDG problem, and the effectiveness is demonstrated by an experimental study.     

Optimizing vote and quorum assignments for reading and writingreplicated data

In the weighted voting protocol which is used to maintain the consistency of replicated data, the availability of the data to ready and write operations not only depends on the availability of the nodes storing the data but also on the vote and quorum assignments used. The authors consider the problem of determining the vote and quorum assignments that yield the best performance in a distributed system where node availabilities can be different and the mix of the read and write operations is arbitrary. The optimal vote and quorum assignments depend not only on the system parameters, such as node availability and operation mix, but also on the performance measure. The authors present an enumeration algorithm that can be used to find the vote and quorum assignments that need to be considered for achieving optimal performance. When the performance measure is data availability, an analytical method is derived to evaluate it for any vote and quorum assignment. This method and the enumeration algorithm are used to find the optimal vote and quorum assignment for several systems. The enumeration algorithm can also be used to obtain the optimal performance when other measures are considered     

Cooperative strategies of wireless access technologies: A game-theoretic analysis

The wireless Internet has to overcome the problem of spectrum scarcity as the number of mobile equipments could increase even by an order of magnitude in the next decade; the cooperation of mobile devices is foreseeable as a feasible solution to the problems. There exists a large body of literature on opportunistic ad hoc networking including Pelusi et al. (2006) [25], Chen et al. (2006) [26], Hui et al. (2005) [27]; however, the impact of the location of the devices on their access method selection is not yet appropriately dealt with. In this paper, we address this issue based on game-theoretic analyses. The key contribution of our work is threefold. First, we model the access method selection of mobile devices by extending the classical forwarding game with position, mobility, and availability of the devices. Second, we apply the model in game-theoretic analyses to better understand the optimal cooperation strategies in the presence of heterogeneous wireless technologies. We further extend our framework to include uncertainty. Finally, we present the applicability of the model in a cognitive radio scenario where complex structures of parameters are included.     

Multiclass replicated data management: exploiting replication toimprove efficiency

Research efforts in replication-control protocols primarily use replication as a means of increasing availability in distributed systems. It is well-known, however, that replication can reduce the costs of accessing remotely-stored data in distributed systems. We contribute a classification of replicas and a replication-control protocol which introduce the availability benefits of replication and, at the same time, exploit replication to improve performance, by reducing response time. Each replica class has different consistency requirements. Metareplicas keep track of up-to-date replicas for recently-accessed objects and help exploit data-reference localities. Thus they allow many transaction operations to execute synchronously at only a single (and often local) replica. Pseudoreplicas are nonpermanent replicas that facilitate “localized execution” of transaction operations. True replicas are ordinary, permanent replicas as used in other replication schemes. For many commonly occurring replication scenarios, the protocol outperforms both replication-control protocols in the literature and nonreplicated systems, while offering the availability benefits of replication