基于改进DHT算法的分布式资源发现模型的研究*

为了解决大型分布式系统由集中管理导致的扩展性和鲁棒性差的问题,利用改进的结构化对等网组织分布式计算资源,构造一个SRDM（scalable resource discovery model,可扩展资源发现模型）。SRDM将逻辑空间中的节点分为主机节点和资源节点。主机节点对应分布式环境中的计算节点,用于存储peer关联信息,通过相容性hash映射到逻辑空间上;资源节点对应分布式环境中资源属性信息,其与逻辑空间的映射通过分段hash再合并的方法得到。通过对属性值采用位置保留hash方法,使改进后的DHT算法支持有效的资源节点范围查询和多属性范围查询。最后通过实验证明,基于改进DHT算法的资源发现方法比集中式的方法有更好的扩展性,更适用于大规模分布式系统下的资源发现。     

基于实时拓扑属性的虚拟网络映射算法（英文）

研究目的:基于虚拟网络请求和底层物理网络实时拓扑属性,提出一种高效的两步式虚拟网络映射算法。创新要点:分别利用中介中心性和物理节点相关性对虚拟网络请求和底层物理网络中节点进行重要性评估,在此基础上给出一种两步式映射算法(算法1,2)。研究方法:首先给出中间中心性、接近中心性以及节点相关性计算模型,结合节点本地资源分别提出虚拟网络请求和物理网络中节点排名计算方式。当虚拟网络请求到达后,根据虚拟节点排名,将其映射到拥有足够资源的物理节点中排名最靠前的节点。节点映射完成后,使用K-th最短路径算法进行链路映射。映射过程中采用文献(Yu et al.,2008)中所使用的时间窗口模式进行接入控制。重要结论:利用节点本地资源,针对性分析虚拟网络请求和物理网络实时拓扑属性,提出两步式映射算法。该算法提高请求接受率、开销收益比的同时减少算法映射时间,取得更好的映射效果(图3-10)。     

基于物理拓扑分组的Chord算法

为了解决Chord模型中节点物理拓扑结构和逻辑拓扑结构不统一,以及查询绕路问题,提出了基于物理拓扑分组的改进的Chord模型。在节点加入Chord网络时考虑了节点的物理位置信息,对节点进行了分域管理。在此基础上建立了节点的邻居表,根据Chord原始查询算法,设计了一种同时考虑节点指取表与邻居表的查询算法,从而有效解决了节点查询的绕路问题。使用Peersim作为仿真软件,选用事件驱动器,对不同规模网络进行了仿真实验,实验结果表明查询物理路径明显减少,查询效率提高。     

层次化的分布式路由结构

在P2P网络中构建了一种基于IPv6地址的分层的分布式路由结构,旨在解决目前分布式哈希表路由中存在的物理拓扑与逻辑网络不匹配造成的寻路效率低下的问题。通过对IPv6地址的每一级集聚标识符分别进行哈希构建节点标识符,构造有层次的节点路由信息,使得物理上相邻的节点在覆盖网络中也邻近,很好地降低了查询时延,提高了查询效率。同时,使用多关键字映射,根据各关键字的权值建立分层的关键字标识符,形成相似节点的聚集,实现了多关键字查找,并提高了相似数据的查询效率。     

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

为了研究多维属性云资源在云对等网络中快速定位问题,结合云对等网络的优势,提出了一种基于云对等网络的多属性云资源的查找算法。在分层云对等网络的基础上,分别利用云资源的类型和属性值建立多维索引。首先根据类型索引将相关的数据聚集在同一个资源簇内;然后将属性值的值域划分为多个区段,并将相应资源存储其中。同时建立资源簇融合、区间邻居维护等机制使算法更具效率和扩展性。仿真实验表明,该算法实现了多属性云资源的快速定位。并且它不会随着网络节点和类型维度增加而产生较大查询迟延,具有很好的扩展性。     

基于IPv6地址聚类特性的Chord协议改进方法

从IPv6地址的层次分配所体现出的网络聚类特性出发,创造性地提出了分段构造节点标识符的思想,将节点标识符分成两部分,分别通过哈希IP地址的前缀和剩余部分来获得,使具有相同标识符前缀的节点被映射到邻近逻辑空间中,实现了逻辑网络和物理网络的有效吻合,进而在Chord协议基础上巧妙地设计了改进系统Chord6。从仿真分析结果可以看出,Chord6的寻路性能较Chord有了显著的改善。     

基于位置关联Chord的名址分离映射系统

名址分离网络中需要一个高性能、可扩展、分布式的映射解析系统,用来管理名称和地址之间的绑定信息,可靠有效地处理名称的位置查询。在映射系统的设计中,结构化分布式哈希表技术是使用最广的,为解决其中物理网络与逻辑网络的失配问题,以及高移动场景下的高更新成本问题,设计了一个基于位置关联Chord的名址分离映射系统。通过在逻辑网络中节点的路由表内添加物理网络的拓扑信息,改变了Chord环的递归查找过程。此外名称与地址的绑定关系分域内域外两级管理,域内直接绑定IP地址,域外更换绑定信息为名称与网络地址,通过增加一跳的查询将绑定信息更新范围尽可能地缩小在域内,提高了系统的映射解析性能。经理论分析和仿真测试验证,相较于LISP-DHT,基于位置关联Chord的映射系统的平均查询时延更小。     

基于拓扑结构感知的节点多属性网络映射算法

针对当前节点多属性网络链路映射长度较长、网络请求接受率和收益开销较低的问题,提出基于拓扑结构感知的节点多属性网络映射算法.根据无向图描述节点多属性网络映射问题,采用拓扑结构感知,构建节点多属性网络模型和节点链路映射评测指标,利用回溯算法,计算sumTR值,获得备选网络节点集合.使用子区域作为物理节点映射区域进行资源分配,按照映射优先级排列网络节点依次映射,分析节点多属性,使用最短路径算法,排序跳数最小链路映射,实现节点多属性网络映射.实验结果表明,所提算法能够有效缩短链路映射长度,提高网络请求接受率和收益开销.     

关于跨域虚拟网络的优化狼群映射研究仿真

虚拟网络映射的目的是将网络底层物理资源,以高可用低开销的方式配置到虚拟网络中,进而提高物理网络的业务扩展性能.针对分布式跨域带来的网络资源异构特性,现有映射算法往往存在节点或链路负载不均衡,资源开销过大,以及报文抖动等问题,提出了优化狼群的跨域虚拟网络映射算法.由于跨域虚拟网络映射过程中,额外的资源开销主要来源于域间,因此算法将映射处理分为域内与域间两部分进行独立分析.对于域内映射只引入元胞结构,增强单目标优化处理性能,将节点采用二进制表示,并设定每一位作为一个元胞,建立节点元胞模型,通过更新元胞与近邻得到域内节点与链路资源的最优配置;对于域间映射,则在元胞基础上,引入优化狼群算法,元胞结构提高搜索的分布能力,优化狼群提高全局寻优性能,利用探狼四处游走,在元胞向量中搜索解,同时得到头狼信息,头狼产生召唤行为通知猛狼目标解的信息,从而利用分工协作实现节点与链路最优解的搜索.仿真结果表明,提出的优化狼群网络映射算法能够有效应对跨域异构资源问题,均衡节点和链路的负载,显著降低网络映射开销和网络映射执行时间.     

StratoNet:一种基于DHT的P2P内容定位系统

提出了一种层次化分布式哈希表系统:StratoNet。该系统按物理网络的远近把节点划分为多个组,使得节点动态加入和退出的影响局限在单个组中,具有良好的稳定性和扩展性,部分查询的性能优越,适合在广域范围部署P2P应用。     

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.     

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

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

MAAN: A Multi-Attribute Addressable Network for Grid Information Services

Recent structured Peer-to-Peer (P2P) systems such as Distributed Hash Tables (DHTs) offer scalable key-based lookup for distributed resources. However, they cannot be simply applied to grid information services because grid resources need to be registered and searched using multiple attributes. This paper proposes a Multi-Attribute Addressable Network (MAAN) that extends Chord to support multi-attribute and range queries. MAAN addresses range queries by mapping attribute values to the Chord identifier space via uniform locality preserving hashing. It uses an iterative or single attribute dominated query routing algorithm to resolve multi-attribute based queries. Each node in MAAN only has O(logN) neighbors for N nodes. The number of routing hops to resolve a multi-attribute range query is O(logN+N×s_min), where s_min is the minimum range selectivity on all attributes. When s_min=, it is logarithmic to the number of nodes, which is scalable to a large number of nodes and attributes. We also measured the performance of our MAAN implementation and the experimental results are consistent with our theoretical analysis.     

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.

多关键字云资源搜索算法

云计算的核心是在虚拟化技术的基础上,通过互联网技术为用户提供动态易扩展的计算资源。利用中心服务器的计算模式来管控网络上大量云资源使得中心服务器成为整个系统的瓶颈,不利于云计算的大规模应用,因此提出使用对等网络技术构建分布式的云资源索引存储和查询系统,但是结构化拓扑系统维护比较复杂,一般不支持复杂搜索条件查询。本文提出了一种多关键字云资源搜索算法。在基于分层超级节点的云资源搜索算法基础上进行路由算法改进,希望实现多关键字的精确查询。对多关键字的生成、分割及存储做出了详细说明,提出一种有效的基于数据集的索引搜索策略,实现了包含三个或三个以上的关键字高效、准确查询。分析实验结果证明了算法明显提高了资源搜索的命中率,尤其是随着关键字数目的增多,不仅保证了资源搜索的命中率,同时大大增加了资源的召回率。     

PSON: A scalable P2P file sharing system with efficient complex query support

A desired P2P file sharing system is expected to achieve the following design goals: scalability, routing efficiency and complex query support. In this paper, we propose a powerful P2P file sharing system, PSON, which can satisfy all the three desired properties. PSON is essentially a semantic overlay network of logical nodes. Each logical node represents a cluster of peers that are close to each other. A powerful peer is selected in each cluster to support query routing on the overlay network while the less powerful peers are responsible for the maintenance of shared contents. To facilitate query routing, super peers are organized in form of a balanced binary search tree. By exploiting the concept of semantics, PSON can support complex queries in a scalable and efficient way. In this paper, we present the basic system design such as the semantic overlay construction, query routing and system dynamics. A load balancing scheme is proposed to further enhance the system performance. By simulation experiments, we show that PSON is scalable, efficient and is able to support complex queries.     

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.     

A P2P-based intelligent resource discovery mechanism in Internet-based distributed systems

Internet-based distributed systems enable globally-scattered resources to be collectively pooled and used in a cooperative manner to achieve unprecedented petascale supercomputing capabilities. Numerous resource discovery approaches have been proposed to help achieve this goal. To report or discover a multi-attribute resource, most approaches use multiple messages, with one message for each attribute, leading to high overhead of memory consumption, node communication, and subsequent merging operation. Another approach can report and discover a multi-attribute resource using one query by reducing multi-attribute to a single index, but it is not practically effective in an environment with a large number of different resource attributes. Furthermore, few approaches are able to locate resources geographically close to the requesters, which is critical to system performance. This paper presents a P2P-based intelligent resource discovery (PIRD) mechanism that weaves all attributes into a set of indices using locality sensitive hashing, and then maps the indices to a structured P2P overlay. PIRD can discover resources geographically close to requesters by relying on a hierarchical P2P structure. It significantly reduces overhead and improves search efficiency and effectiveness in resource discovery. It further incorporates the Lempel–Ziv–Welch algorithm to compress attribute information for higher efficiency. Theoretical analysis and simulation results demonstrate the efficiency of PIRD in comparison with other approaches. It dramatically reduces overhead and yields significant improvements on the efficiency of resource discovery.     

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.     

Cache共享架构下的多属性范围查询

结构化对等网络的多属性范围查询研究有两类:一类通过空间填充曲线或在每个属性维上复制信息以降维;另一类通过构建分布式索引树以实现多属性查询.这两类解析每个查询的跳数和消息数依赖于范围大小和节点个数.前者属性值改变时产生大量的消息;后者导致高的维护开销.提出cache共享架构下的多属性范围查询.仿真实验显示和SWORD相比,跳数和消息数均减少;属性值改变时,所需消息数减少;查询准确率下降不到5%.维护开销低.