基于双层ID空间的Peer-to-Peer文件系统设计与实现

提出并实现了一种建立在Peer-to-Peer搜索策略上的自组织,自适应,高效和可靠的文件系统DISPES（Double ID Space Based Peer-to-peer File System)。它在双层ID空间中构造虚拟存储节点,不仅有效地取得了文件系统的负载均衡,提高系统利用率,而且保证了动态环境中文件的可靠,快速获取,试验数据表明,DISPFS在系统接近满负荷运行和文件插入/删除操作频繁的双重压力下依然保持优良的性能。     

基于Kademlia的负载平衡云存储算法

针对采用主从式结构的主流云存储系统可能出现的性能瓶颈和可扩展问题,基于分布式哈希表(DHT)技术的完全分布式云存储系统成为一种新的选择。解决好节点的负载平衡问题,是此类技术获得推广的关键。研究了Kademlia算法应用于云存储系统的负载平衡性能。考虑到算法在异构环境下负载平衡性能有明显下降,改进算法在Kademlia找出的候选存储节点中根据节点的存储能力来分配负载。仿真结果表明,改进后算法的负载平衡性能有非常明显的提高,在系统模拟运行时间足够长(如1500 h以上)时,过载节点平均下降7.0%(轻载)和33.7%(重载);文件保存成功率平均提高27.2%(轻载)和35.1%(重载),而增加的通信开销可接受。     

Adaptive component composition and load balancing for distributed stream processing applications

Providing real-time and QoS support to stream processing applications running on top of large-scale overlays is challenging due to the inherent heterogeneity and resource limitations of the nodes and the multiple QoS demands of the applications that must concurrently be met. In this paper we propose an integrated adaptive component composition and load balancing mechanism that (1) allows the composition of distributed stream processing applications on the fly across a large-scale system, while satisfying their QoS demands and distributing the load fairly on the resources, and (2) adapts dynamically to changes in the resource utilization or the QoS requirements of the applications. Our extensive experimental results using both simulations as well as a prototype deployment illustrate the efficiency, performance and scalability of our approach.

Adaptive and scalable load balancing for metadata server cluster in cloud-scale file systems

Big data is an emerging term in the storage industry, and it is data analytics on big storage, i.e., Cloud-scale storage. In Cloud-scale (or EB-scale) file systems, load balancing in request workloads across a metadata server cluster is critical for avoiding performance bottlenecks and improving quality of services.Many good approaches have been proposed for load balancing in distributed file systems. Some of them pay attention to global namespace balancing, making metadata distribution across metadata servers as uniform as possible. However, they do not work well in skew request distributions, which impair load balancing but simultaneously increase the effectiveness of caching and replication. In this paper, we propose Cloud Cache (C²), an adaptive and scalable load balancing scheme for metadata server cluster in EB-scale file systems. It combines adaptive cache diffusion and replication scheme to cope with the request load balancing problem, and it can be integrated into existing distributed metadata management approaches to efficiently improve their load balancing performance. C² runs as follows: 1) to run adaptive cache diffusion first, if a node is overloaded, loadshedding will be used; otherwise, load-stealing will be used; and 2) to run adaptive replication scheme second, if there is a very popular metadata item (or at least two items) causing a node be overloaded, adaptive replication scheme will be used, in which the very popular item is not split into several nodes using adaptive cache diffusion because of its knapsack property. By conducting performance evaluation in trace-driven simulations, experimental results demonstrate the efficiency and scalability of C².     

Application of load balancing based on symmetric balanced incomplete block design to random networks

In a load balancing algorithm [O. Lee, M. Anshel, I. Chung, Design of an efficient load balancing algorithm on distributed networks by employing symmetric balanced incomplete block design, IEE Proceedings - Communications 151 (6) (2004) 535-538] based on the SBIBD (Symmetric Balanced Incomplete Block Design), each node receives global workload information by only two round message exchange with traffic overhead, where v is the number of nodes. It is very efficient and works well only when v=p²+p+1 is used for a prime number p. In this paper, we generated a special incidence structure using the SBIBD and then propose a new load balancing algorithm, which executes well for an arbitrary number of nodes. To accomplish this, we add a number of links to nodes in order for each node to receive more than 80% of the workload information by two round message exchange. For performance of our algorithm, we carried out an experiment for the number of nodes, w, which was up to 5000. Traffic overhead is less than in a round and standard deviation of traffic overhead shows that each node has a mostly well-balanced amount of traffic.     

Achieving strong consistency in a distributed file system

Distributed file systems need to provide for fault tolerance. This is typically achieved with the replication of files. Existing approaches to the construction of replicated file systems sacrifice strong semantics (i.e. the guarantees the systems make to running computations when failures occur and/or files are accessed concurrently). This is done mainly for efficiency reasons. This paper puts forward a replicated file system protocol that enforces strong consistency semantics. Enforcing strong semantics allows for distributed systems to behave more like their centralized counterparts-an essential feature in order to provide the transparency that is so strived for in distributed computing systems. One characteristic of our protocol is its distributed nature. Because of it, the extra cost needed to ensure the stronger consistency is kept low (since the bottleneck problem noticed in primary-copy systems is avoided), load balancing is facilitated, clients can choose physically close servers, and the work required during failure handling and recovery is reduced. Another characteristic is that, instead of optimizing each operation type on its own, file system activity is viewed at the level of a file session and the costs of individual operations were able to be spread over the life of a file session. We have developed a prototype and compared its performance to both NFS and a nonreplicated version of the prototype that also achieves strong consistency semantics. Through these comparisons, the cost of replication and the cost of enforcing the strong consistency semantics are shown     

基于DHT的P2P系统负载均衡的有效算法

基于DHT的P2P系统中,各种因素例如结点异构性和不同的文件访问率等,都可能会影响DHT系统的效率。本文提出一个基于DHT的P2P系统中有效的负载均衡算法。该算法提出一个全分布机制来维护文件访问的历史信息,用来预测未来文件访问频率。设计了一个新的负载均衡算法,当新结点加入时,历史信息和结点异构性一起用来决定最佳负载分配。在系统运行期间如果有过载结点出现也可动态执行负载重分配。该算法不使用虚服务器,减少了维护路由元数据的处理开销。     

Dynamic storage and access load balancing for answering range queries in peer-to-peer networks

Recently, many applications have used Peer-to-Peer (P2P) systems to overcome the current problems with client/server systems such as non-scalability, high bandwidth requirement and single point of failure. In this paper, we propose an efficient scheme to support efficient range query processing over structured P2P systems, while balancing both the storage load and access load. The paper proposes a rotating token scheme to balance the storage load by placing joining nodes in appropriate locations in the identifier space to share loads with already overloaded nodes. Then, to support range queries, we utilize an order-preserving mapping function to map keys to nodes in order preserving way and without hashing. This may result in an access load imbalance due to non-uniform distribution of keys in the identifier space. Thus, we propose an adaptive replication scheme to relieve overloaded nodes by shedding some load on other nodes to balance the access load. We derive a formula for estimating the overhead of the proposed adaptive replication scheme. In this study, we carry simulation experiments with synthetic data to measure the performance of the proposed schemes. Our simulation experiments show significant gains in both storage load balancing and access load balancing.     

An adaptive threshold based hybrid load balancing scheme with sender and receiver initiated approach using random information exchange

The primary objective of load balancing for distributed systems is to minimize the job execution time while maximizing the resource utilization. Load balancing on decentralized systems need effective information exchange policy so that with minimum amount of communication the nodes have up to date information about other nodes in the system. Periodic, event‐based and on‐demand information exchange are some important policies used for the same. All these approaches involve a lot of overhead and even sometime leading toward obsolete data with the nodes if there is a delay in the updation. This work presents an adaptive threshold‐based hybrid load balancing scheme with sender and receiver initiated approach (HLBWSR) using random information exchange (RIE). RIE ensures that the information is exchanged in such a way that each node in the system has up‐to‐date state of the other nodes with much reduced communication overhead. Further, the adaptive threshold ensures that almost an average numbers of jobs are executed by all the nodes in the system. The study of the effect of the use of RIE on sender initiated, receiver initiated and hybrid of sender and receiver initiated load balancing approach establishes the superior performance of HLBWSR among its RIE‐based peers. A comparative analysis of HLBWSR, with periodic information exchange strategy, modified estimated load information scheduling algorithm and load balancing on arrival reveals its effectiveness under various test conditions. Copyright © 2016 John Wiley & Sons, Ltd.     

Toward Performance-Driven System Support for Distributed Computing in Clustered Environments

With the proliferation of workstation clusters connected by high-speed networks, providing efficient system support for concurrent applications engaging in nontrivial interaction has become an important problem. Two principal barriers to harnessing parallelism are: (1) efficient mechanisms that achieve transparent dependency maintenance while preserving semantic correctness and (2) scheduling algorithms that match coupled processes to distributed resources while explicitly incorporating their communication costs. This paper describes a set of performance features and their properties and implementation in a system support environment called DUNES that achieves transparent dependency maintenance—IPC, file access, memory access, process creation/termination, process relationships—under dynamic load balancing. The two principal performance features are push/pull-based active and passive end-point caching and communication-sensitive load balancing. Collectively, they mitigate the overhead introduced by the transparent dependency maintenance mechanisms. Communication-sensitive load balancing, in addition, affects the scheduling of distributed resources to application processes where both communication and computation costs are explicitly taken into account. DUNES' architecture endows commodity operating systems with distributed operating system functionality while achieving transparency with respect to their existing application base. DUNES also preserves semantic correctness with respect to single processor semantics. We show performance measurements of a UNIX-based implementation on Sparc and x86 architectures over high-speed LAN environments. We show that significant performance gains in terms of system throughput and parallel application speedup are achievable.     

The design and analysis of an efficient load balancing algorithm employing the symmetric balanced incomplete block design

In order to maintain load balancing in a distributed network, each node should obtain workload information from all the nodes in the network. To accomplish this, this processing requires O(v²) communication complexity, where v is the number of nodes. First, we present a new synchronous dynamic distributed load balancing algorithm on a (v, k + 1, 1)-configured network applying a symmetric balanced incomplete block design, where v = k² + k + 1. Our algorithm designs a special adjacency matrix and then transforms it to (v, k + 1, 1)-configured network for an efficient communication. It requires only communication complexity and each node receives workload information from all the nodes without redundancy since each link has the same amount of traffic for transferring workload information. Later, this algorithm is revised for distributed networks and is analyzed in terms of efficiency of load balancing.     

Hybrid work stealing of locality-flexible and cancelable tasks for the APGAS library

Since large parallel machines are typically clusters of multicore nodes, parallel programs should be able to deal with both shared memory and distributed memory. This paper proposes a hybrid work stealing scheme, which combines the lifeline-based variant of distributed task pools with the node-internal load balancing of Java’s Fork/Join framework. We implemented our scheme by extending the APGAS library for Java, which is a branch of the X10 project. APGAS programmers can now spawn locality-flexible tasks with a new asyncAny construct. These tasks are transparently mapped to any resource in the overall system, so that the load is balanced over both nodes and cores. Unprocessed asyncAny-tasks can also be cancelled. In performance measurements with up to 144 workers on up to 12 nodes, we observed near linear speedups for four benchmarks and a low overhead for cancellation-related bookkeeping.     

The grid, the load and the gradient

An important concern for an efficient use of distributed computing is dealing with load balancing to ensure all available nodes and their shared resources are equally exploited. In large scale systems such as volunteer computing platforms and desktop grids, centralized solutions may introduce performance bottlenecks and single points of failure. Accordingly fully distributed alternatives have been considered, due to their inherent robustness and reliability. In extremely dynamic contexts, scheduling middlewares should adapt their job scheduling policies to the actual availability and overcome the volatility and heterogeneity typical of the underlying nodes. To deal with the dynamicity of a large pool of resources, self-organizing and adaptive solutions represent a promising research direction. Solutions based on bio-inspired methodologies are particularly suitable, as they inherently provide the desired features. In this paper we present a fully distributed load balancing mechanism, called ozmos, which aims at increasing the efficiency of distributed computing systems through peer-to-peer interaction between nodes. The proposed algorithm is based on a Chord overlay, and employs ant-like agents to spread information about the current load on each node, to reschedule tasks from overloaded systems to underloaded ones, and to relocate incompatible tasks on suitable resources in heterogeneous grids. By means of several evaluation scenarios we demonstrate the effectiveness of the proposed solution in achieving system-wide load balancing, both with homogeneous and heterogeneous resources. In particular we consider the load balancing performance of our approach, its scalability, as well as its communication efficiency.     

面向多媒体系统的负载均衡策略研究

随着多媒体应用的普及,面向多媒体应用的并行文件系统负载均衡策略的研究具有现实意义。本文根据视频点播等多媒体应用的特点,提出了面向多媒体应用的并行文件系统动态负载均衡策略,构建了该策略的均衡模型,提出了适于多媒体服务系统的动态调度算法,并对该算法进行了性能分析。最后建立了NFS文件系统负载均衡实验环境,测试了该策略的高效性,充分证明了所提出的面向多媒体应用的并行文件系统负载均衡策略的优势。     

Handling distributed authorization with delegation through answer set programming

Distributed authorization is an essential issue in computer security. Recent research shows that trust management is a promising approach for the authorization in distributed environments. There are two key issues for a trust management system: how to design an expressive high-level policy language and how to solve the compliance-checking problem (Blaze et al. in Proceedings of the Symposium on Security and Privacy, pp. 164–173, 1996; Proceedings of 2nd International Conference on Financial Cryptography (FC’98). LNCS, vol.1465, pp. 254–274, 1998), where ordinary logic programming has been used to formalize various distributed authorization policies (Li et al. in Proceedings of the 2002 IEEE Symposium on Security and Privacy, pp. 114–130, 2002; ACM Trans. Inf. Syst. Secur. (TISSEC) 6(1):128–171, 2003). In this paper, we employ Answer Set Programming to deal with many complex issues associated with the distributed authorization along the trust management approach. In particular, we propose a formal authorization language providing its semantics through Answer Set Programming. Using language , we cannot only express nonmonotonic delegation policies which have not been considered in previous approaches, but also represent the delegation with depth, separation of duty, and positive and negative authorizations. We also investigate basic computational properties related to our approach. Through two case studies. we further illustrate the application of our approach in distributed environments.     

A proactive low-overhead file replication scheme for structured P2P content delivery networks

File replication is a widely used technique for high performance in peer-to-peer content delivery networks. A file replication technique should be efficient and at the same time facilitates efficient file consistency maintenance. However, most traditional methods do not consider nodes’ available capacity and physical location in file replication, leading to high overhead for both file replication and consistency maintenance. This paper presents a proactive low-overhead file replication scheme, namely Plover. By making file replicas among physically close nodes based on nodes’ available capacities, Plover not only achieves high efficiency in file replication but also supports low-cost and timely consistency maintenance. It also includes an efficient file query redirection algorithm for load balancing between replica nodes. Theoretical analysis and simulation results demonstrate the effectiveness of Plover in comparison with other file replication schemes. It dramatically reduces the overhead of both file replication and consistency maintenance compared to other schemes. In addition, it yields significant improvements in reduction of overloaded nodes.     

Many-to-Many Communication in Radio Networks

Radio networks model wireless data communication when the bandwidth is limited to one wave frequency. The key restriction of such networks is mutual interference of packets arriving simultaneously at a node. The many-to-many (m2m) communication primitive involves p participant nodes from among n nodes in the network, where the distance between any pair of participants is at most d. The task is to have all the participants get to know all the input messages. We consider three cases of the m2m communication problem. In the ad-hoc case, each participant knows only its name and the values of n, p and d. In the partially centralized case, each participant knows the topology of the network and the values of p and d, but does not know the names of the other participants. In the centralized case, each participant knows the topology of the network and the names of all the participants. For the centralized m2m problem, we give deterministic protocols, for both undirected and directed networks, working in time, which is provably optimal. For the partially centralized m2m problem, we give a randomized protocol for undirected networks working in time with high probability (whp), and we show that any deterministic protocol requires time. For the ad-hoc m2m problem, we develop a randomized protocol for undirected networks that works in time whp. We show two lower bounds for the ad-hoc m2m problem. One lower bound states that any randomized protocol for the m2m ad hoc problem requires expected time. Another lower bound states that for any deterministic protocol for the m2m ad hoc problem, there is a network on which the protocol requires time when n−p(n)=Ω(n) and d>1, and that it requires Ω(n) time when n−p(n)=o(n). The results of this paper appeared in a preliminary form in “On many-to-many communication in packet radio networks” in Proceedings of the 10th Conference on Principles of Distributed Systems (OPODIS), Bordeaux, France, 2006, Lecture Notes in Computer Science 4305, Springer, Heidelberg, pp. 258–272. The work of B.S. Chlebus was supported by NSF Grant 0310503.     

基于动态副本技术的云存储负载均衡研究

以系统总响应时间最小化为目标,以文件热度为依据,提出了一种多时间窗负载均衡策略。在计算文件热度时,不仅考虑了访问的次数和大小,还将I/O访问时序引入到文件热度统计中,该方法能有效控制短时间突发性数据访问导致的不必要副本创建。在多时间窗负载均衡策略中,设置了三种不同大小的时间窗口,分别实现了存储节点负载均衡、文件副本的负载均衡以及低热度文件多余副本的删除工作。实验数据表明,多时间窗负载均衡策略能显著降低I/O访问响应时间。