A flabellate overlay network for multi-attribute search

Peer-to-peer (P2P) technology provides a popular way of distributing resources, sharing, and locating in a large-scale distributed environment. However, most of the current existing P2P systems only support queries over a single resource attribute, such as file name. The current multiple resource attribute search methods often encounter high maintenance cost and lack of resilience to the highly dynamic environment of P2P networks. In this paper, we propose a Flabellate overlAy Network (FAN), a scalable and structured underlying P2P overlay supporting resource queries over multi-dimensional attributes. In FAN, the resources are mapped into a multi-dimensional Cartesian space based on the consistent hash values of the resource attributes. The mapping space is divided into non-overlapping and continuous subspaces based on the peer’s distance. This paper presents strategies for managing the extended adjacent subspaces, which is crucial to network maintenance and resource search in FAN. The algorithms of a basic resource search and range query over FAN are also presented in this paper. To alleviate the load of the hot nodes, a virtual replica network (VRN) consisting of the nodes with the same replicates is proposed for replicating popular resources adaptively. The queries can be forwarded from the heavily loaded nodes to the lightly loaded ones through VRN. Theoretical analysis and experimental results show that FAN has a higher routing efficiency and lower network maintenance cost over the existing multi-attribute search methods. Also, VRN efficiently balances the network load and reduces the querying delay in FAN while invoking a relatively low overhead.     

A distributed resource discovery algorithm for P2P grids

Centralized or hierarchical administration of the classical grid resource discovery approaches is unable to efficiently manage the highly dynamic large-scale grid environments. Peer-to-peer (P2P) overlay represents a dynamic, scalable, and decentralized prospect of the grids. Structured P2P methods do not fully support the multi-attribute range queries and unstructured P2P resource discovery methods suffer from the network-wide broadcast storm problem. In this paper, a decentralized learning automata-based resource discovery algorithm is proposed for large-scale P2P grids. The proposed method supports the multi-attribute range queries and forwards the resource queries through the shortest path ending at the grid peers more likely having the requested resource. Several simulation experiments are conducted to show the efficiency of the proposed algorithm. Numerical results reveal the superiority of the proposed model over the other methods in terms of the average hop count, average hit ratio, and control message overhead.     

A Self-Organized Grouping (SOG) Framework for Efficient Grid Resource Discovery

Dynamic and heterogeneous characteristics of large-scale Grids make the fundamental problem of resource discovery a great challenge. This paper presents a self-organized grouping (SOG) framework that achieves efficient Grid resource discovery by forming and maintaining autonomous resource groups. Each group dynamically aggregates a set of resources together with respect to similarity metrics of resource characteristics. The SOG framework takes advantage of the strengths of both centralized and decentralized approaches that were previously developed for Grid/P2P resource discovery. The design of SOG minimizes the overhead incurred by the process of group formation and maximizes the performance of resource discovery. The way SOG approach handles resource discovery queries is metaphorically similar to searching for a word in an English dictionary, by identifying its alphabetical group at the first place, and then performing a lexical search within the group. Because multi-attribute range queries represent an important aspect of resource discovery, we devise a generalized approach using a space-filling curve in conjunction with the SOG framework. We exploit the Hilbert space-filling curve’s locality preserving and dimension reducing mapping. This mapping provides a 1-dimensional grouping attribute to be used by the SOG framework. Experiments show that the SOG framework achieves superior look-up performance that is more scalable, stable and efficient than other existing approaches. Furthermore, our experimental results indicate that the SOG framework has little dependence on factors such as resource density, query type, and Grid size.     

基于SkipNet支持多属性范围查询的云资源共享设计

在云资源共享服务模式中,针对云资源多属性范围查询的问题,提出一种改进的E-SkipNet网络。首先,E-SkipNet在传统分布式哈希表(DHT)网络SkipNet的基础上将数据属性引入到节点NameID的设置中,将物理节点加入到单个属性域中,以支持多属性范围查询;其次,在原E-SkipNet网络的基础上,将物理节点同时映射成多个逻辑节点;同时加入多个属性域,并将资源按照不同的属性发布到不同逻辑节点上;最后,采用均匀位置保留哈希函数对资源进行映射存储,从而在各个属性域中保留属性值的顺序关系,从而支持范围查询。仿真结果表明,改进后的E-SkipNet网络与改进前的E-SkipNet和多属性可寻址网络(MAAN)相比,在路由效率方面分别提高了18.09%和20.47%。结果表明,改进后的E-SkipNet网络能支持更加高效的云资源多属性范围查询,在异构环境中能较好地实现负载均衡。     

Direction-aware resource discovery in large-scale distributed computing environments

As a system scales up, the peer-to-peer (P2P) approach is attractive to distributed computing environments, such as Grids and Clouds, due to the amount of resources increased. The major issue in large-scale distributed systems is to prevent the phenomenon of a communication bottleneck or a single point of failure. Conventional approaches may not be able to apply directly to such environments due to restricted queries and varied resource characteristics. Alternatively, a fully decentralized resource discovery service based on an unstructured overlay, which relies only on the information of resource attributes and characteristics, may be a feasible solution. One major challenge of such service is to locate desired and suitable resources without the global knowledge of distributed sharing resources. As a consequence, the more nodes the resource discovery service involves, the higher the network overhead incurs. In this paper, we proposed a direction-aware strategy which can alleviate the network traffic among unstructured information systems for distributed resource discovery service. Experimental results have demonstrated that the proposed approach achieves higher success rate at low cost and higher scalability.     

Collaborative applications over peer-to-peer systems–challenges and solutions

Emerging collaborative Peer-to-Peer (P2P) systems require discovery and utilization of diverse, multi-attribute, distributed, and dynamic groups of resources to achieve greater tasks beyond conventional file and processor cycle sharing. Collaborations involving application specific resources and dynamic quality of service goals are stressing current P2P architectures. Salient features and desirable characteristics of collaborative P2P systems are highlighted. Resource advertising, selecting, matching, and binding, the critical phases in these systems, and their associated challenges are reviewed using examples from distributed collaborative adaptive sensing systems, cloud computing, and mobile social networks. State-of-the-art resource discovery/aggregation solutions are compared with respect to their architecture, lookup overhead, load balancing, etc., to determine their ability to meet the goals and challenges of each critical phase. Incentives, trust, privacy, and security issues are also discussed, as they will ultimately determine the success of a collaborative P2P system. Open issues and research opportunities that are essential to achieve the true potential of collaborative P2P systems are discussed.     

一种自适应的网格计算资源组织与发现机制

资源发现是网格计算中一个重要的研究问题.计算资源作为支撑网格应用的基础资源,其组织与发现机制尤为重要,但现有的技术和方法在效率、可伸缩性、自适应的动态演化以及对查询方式的支持方面仍有较大的局限性.基于网格应用对计算资源需求特征的深入分析,通过引入计算资源的主属性概念,按照平衡二叉排序树对计算资源进行分类组织,提出基于资源分类树(resource category tree,简称RCT)的资源组织与发现机制.首先,讨论了基于RCT对计算资源的组织机制,包括RCT的基本概念和原理、支持资源动态加入和退出以及资源状态动态变化的自组织机制、负载感知的自适应演化机制和基于备份节点的容错机制;然后,在基于RCT的资源组织结构下,设计了支持4种查询方式的搜索算法,并对算法的复杂度进行了分析;最后,通过多组仿真实验对RCT的性能进行了评估.     

基于多属性查询的P2P网格资源发现机制

资源发现是网格环境中的关键问题,目前许多的资源发现机制并不能有效地提供资源的分类。为此,在P2P网格基础上提出一种基于多属性查询的分布式资源树的资源发现机制。该分布式资源树通过资源的主属性进行资源的组织和分类,能动态灵活地实现P2P网格中各节点的负载动态平衡。     

符合动态演变特性的网格资源发现机制研究

近年来人们对如何提高网格资源发现效率做了大量的研究,但却忽略了适应网格资源动态演变特性的重要性.针对这一问题,结合小世界理论的网络特征,提出了一种新的基于P2P分布式结构化的网格资源发现机制.通过计算资源节点间属性相似度的方法,将网格资源分类组织在不同的虚拟组织中,结合P2P技术构建出两层覆盖式资源发现模型,并设计出相应的资源查找算法DSRD (distributed structure grid resource discovery).仿真实验结果表明,DSRD算法既能够适应资源的动态特性,同时又可有效地提高资源发现效率.     

可防止无关属性干扰的属性基加密方案

为了提高属性基加密中访问结构的表达能力,同时避免访问结构中无关属性干扰,提出了一种基于简化有序二元决策图（ROBDD）访问结构的CP-ABE方案。该方案中ROBDD访问结构可有效表达具有复杂访问逻辑的访问策略,并可防止无关属性干扰,提高了加密速度。通过RSA属性认证机制进行ROBDD非叶子节点中属性认证,实现了抗串谋攻击和对用户属性集的保护。使用ROBDD中有效路径特征值和加密参数创建多项式,任何有效路径特征值经过多项式计算均可得到加密参数,降低了密文存储开销。该方案实现了用户撤销、用户属性撤销和系统属性撤销。性能分析和实验仿真表明,所提方案有更高的加解密效率,更低的密文存储开销。     

Decentralized Grid Resource Discovery Based on Resource Information Community

A decentralized Grid resource discovery solution is presented in this paper under predefined resource taxonomy, in which information nodes with the same type of registered resources are organized together to form resource information communities (RIC), and efficient navigation between different communities is achieved by a DHT P2P based bootstrap network. Periodical topology maintenance communications are used to piggyback and disseminate popular data in bootstrap network to achieve better load balance. The performance of RIC-based Grid resource discovery is evaluated by simulation under different cases, and overhead is also studied.     

一种基于对等网络的云资源多属性区间查询算法

设计了n元属性组来描述云资源, 并为属性组中的每个属性都划分区间。为解决云资源的多关键字高效查找问题, 对不同属性的不同区间的任意组合都建立索引。针对云资源属性变动时导致索引更新时网络开销太大的缺点, 提出依据索引中属性的个数对全部索引进行归类存储。仿真实验表明, 在云资源的属性发生变动时, 该算法在更新索引时在网络中产生的信息个数是一个常数n, 数目远远小于其他的多关键字区间查询算法, 查找资源时网络开销不仅小而且稳定。     

PeerRank:一种无结构P2P资源发现策略

资源发现是P2P应用所面临的最核心问题之一.相关的无结构P2P系统主要采用了查询消息泛洪和信息索引机制,这会造成严重的网络带宽负担以及巨大的索引维护开销.给出了一种无结构P2P环境下能够节约带宽、容易维护的自适应搜索策略PeerRank.PeerRank依据用户结点命中查询的历史信息赋予结点相应权值作为查询消息路由的依据,引导查询快速接近目标资源.自适应缓存机制和索引机制的引入使搜索性能大为加强.最后的实验表明,附带自适应缓存和索引的PeerRank以其高搜索成功率、多副本发现和很短的时间响应,能够显著地提高资源发现性能.     

Semantic-supported and agent-based decentralized grid resource discovery

One of the open issues in grid computing is efficient resource discovery. In this paper, we propose a novel semantic-supported and agent-based decentralized grid resource discovery mechanism. Without overhead of negotiation, the algorithm allows individual resource agents to semantically interact with neighbour agents based on local knowledge and to dynamically form a resource service chain to complete a task. The algorithm ensures the resource agent’s ability to cooperate and coordinate on neighbour knowledge requisition for flexible problem solving. The developed algorithm is evaluated by investigating the relationship between the success probability of resource discovery and semantic similarity under different factors. The experiments show the algorithm could flexibly and dynamically discover resources and therefore provide a valuable addition to the field.     

Ant colony optimization inspired resource discovery in P2P Grid systems

It is a challenge for the traditional centralized or hierarchical Grid architecture to manage the large-scale and dynamic resources, while providing scalability. The Peer-to-Peer (P2P) model offers a prospect of dynamicity, scalability, and availability of a large pool of resources. By integrating the P2P philosophy and techniques into a Grid architecture, P2P Grid system is emerging as a promising platform for executing large-scale, resource intensive applications. There are two typical resource discovery approaches for a large-scale P2P system. The first one is an unstructured approach which propagates the query messages to all nodes to locate the required resources. The method does not scale well because each individual query generates a large amount of traffic and the network quickly becomes overwhelmed by the messages. The second one is a structured approach which places resources at specified locations to make subsequent queries easier to satisfy. However, the method does not support multi-attribute range queries and may not work well in the network which has an extremely transient population. This paper proposes and designs a large-scale P2P Grid system which employs an Ant Colony Optimization (ACO) algorithm to locate the required resources. The ACO method avoids a large-scale flat flooding and supports multi-attribute range query. Multiple ants can be employed to improve the parallelism of the method. A simulator is developed to evaluate the proposed resource discovery mechanism. Comprehensive simulation results validate the effectiveness of the proposed method compared with the traditional unstructured and structured approaches.

Peer-to-peer systems for discovering resources in a dynamic grid

The convergence of the Grid and Peer-to-Peer (P2P) worlds has led to many solutions that try to efficiently solve the problem of resource discovery on Grids. Some of these solutions are extensions of P2P DHT-based networks. We believe that these systems are not flexible enough when the indexed data are very dynamic, i.e., the values of the resource attributes change very frequently over time. This is a common case for Grid metadata, like CPU loads, queue occupation, etc. Moreover, since common requests for Grid resources may be expressed as multi-attribute range queries, we think that the DHT-based P2P solutions are poorly flexible and efficient in handling them.In this paper we present two P2P systems. Both are based on Routing Indexes, which are used to efficiently route queries and update messages in the presence of highly variable data. The first system uses a tree-shaped overlay network. The second one is an evolution of the first, and is based on a two-level hierarchical network topology, where tree topologies must only be maintained at the lower level of the hierarchy, i.e., within the various node groups making up the network. The main goal of the second organization is to achieve a simpler maintenance of the overall P2P graph topology, by preserving the good properties of the tree-shaped topology.We discuss the results of extensive simulation studies aimed at assessing the performance and scalability of the proposed approaches. We also analyze how the network topologies affect the propagation of query and update messages.     

一种高效多授权中心云访问控制方案

针对已有云计算多授权访问控制方案中用户端负担过重的问题,提出一种基于属性加密的多授权中心访问控制方案HE-MA-ACS。在层次化授权结构的基础上,引入外包解密思想,将用户访问的大部分解密计算开销外包至云服务端,实现细粒度的属性撤销,并且用户端不需要参与属性的撤销操作。对方案的正确性、安全性、计算和存储性能进行了分析,证明了该方案在用户端存储开销、访问通信开销、解密时间及属性撤销时计算开销上的优越性。该方案有效地降低了用户端的负担,提高了解密效率。     

粒计算中基于属性分类的形式概念属性约简

针对目前已有的形式概念属性约简算法的不足(如属性约简的时间复杂度偏高、属性及属性值比较过程中存在冗余计算、存储开销大等问题),结合粒计算思想,提出基于属性分类的形式概念属性约简模型.首先,通过定义两个算子来划分属性之间分类关系;然后,由属性分类关系制定约简规则,并在此基础上提出基于属性分类的形式概念约简算法,该算法在保持目前最低时间复杂度不变的情况下,减少了冗余计算和存储开销,提高了属性约简的计算效率;最后,通过实例和仿真实验对基于属性分类关系的形式概念属性约简算法的有效性进行了验证.     

一种基于资源类型的网格资源发现方法

提出一种基于资源类型的非集中式网格资源发现方法，将注册有同类资源的网格信息节点组织在一起形成社区，资源发现请求的转发以及资源信息的扩散都被限制在相应的社区内，从而改善了资源发现的性能．社区的自组织和社区间的高效导航通过一个基于分布式Hash表的bootstrap网络实现，并提出了流言传播的机制来改善bootstrap网络中的负载均衡．在社区内部的搜索中引入了基于贪婪搜索的资源定位机制，只将少数较好的结果返回给用户，节省了用户比较选择的时间．探讨了该方法在通用大规模计算资源共享以及仿真网格中的应用．