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.     

Resolving the Topology Mismatch Problem in Unstructured Peer-to-Peer Networks

Prior studies show that more than 70 percent of communication paths in a popular unstructured peer-to-peer (P2P) system (i.e., Gnutella) do not exploit the physical network topology, leading to the topology mismatch problem, and thus, lengthen communication between participating peers. While previous efforts in solving overlay topology matching problems do not guarantee the bounds of performance metrics (e.g., the communication delay between any two overlay peers and the broadcasting scope of any participating peer), in this paper, we present a novel topology matching algorithm that has provable performance qualities. In our proposal, each participating node creates and manages a constant number of overlay connections to other peers in a distributed manner. In rigorous performance analysis, we show that 1) the expected overlay communication delay between any two nodes in our P2P network is a constant; 2) in addition, any joining node has the exponential broadcasting scope in expectation; 3) furthermore, a participating node takes a polylogarithmic overhead to exploit the physical network locality and maintain its flooding scope. Together with extensive simulations, we present our proposal that significantly outperforms two recent solutions, i.e., THANCS and mOverlay, in terms of overlay communication latency and/or broadcasting scope.     

A novel approach to improving search efficiency in unstructured peer-to-peer networks

The decentralized peer-to-peer (P2P) technique has been widely used to implement scalable file sharing systems. It organizes nodes in a system into a structured or unstructured network. The advantages of the unstructured P2P systems are that they have lower maintenance complexity and can better adapt to node heterogeneity as well as network dynamics. However, the search process in unstructured systems is not as efficient as in structured P2P systems because the same search message may go through a node multiple times. To facilitate the complex search and improve the search efficiency, we propose a novel approach of assigning identifications to nodes in an unstructured system. Our method can prevent a node from receiving duplicate search messages and retain the low maintenance overhead for the system. The performance evaluations demonstrate that the proposed approach can improve the search efficiency of unstructured P2P systems while keeping the maintenance overhead at a comparable or even lower level, compared with the traditional unstructured systems.     

Assisted Peer-to-Peer Search with Partial Indexing

In the past few years, peer-to-peer (P2P) networks have become a promising paradigm for building a wide variety of distributed systems and applications. The most popular P2P application till today is file sharing, e.g., Gnutella, Kazza, etc. These systems are usually referred to as unstructured, and search in unstructured P2P networks usually involves flooding or random walking. On the other hand, in structured P2P networks (DHTs), search is usually performed by looking up a distributed inverted index. The efficiency of the search mechanism is the key to the scalability of a P2P content sharing system. So far, neither unstructured nor structured P2P networks alone can solve the search problem in a satisfactory way. In this paper, we propose to combine the strengths of both unstructured and structured P2P networks to achieve more efficient search. Specifically, we propose to enhance search in unstructured P2P overlay networks by building a partial index of shared data using a structured P2P network. The index maintains two types of information: the top interests of peers and globally unpopular data, both characterized by data properties. The proposed search protocol, assisted search with partial indexing, makes use of the index to improve search in three ways: first, the index assists peers to find other peers with similar interests and the unstructured search overlay is formed to reflect peer interests. Second, the index also provides search hints for those data difficult to locate by exploring peer interest locality, and these hints can be used for second-chance search. Third, the index helps to locate unpopular data items. Experiments based on a P2P file sharing trace show that the assisted search with a lightweight partial indexing service can significantly improve the success rate in locating data than Gnutella and a hit-rate-based protocol in unstructured P2P systems, while incurring low search latency and overheads.     

SSW: A Small-World-Based Overlay for Peer-to-Peer Search

Peer-to-peer (P2P) systems have become a popular platform for sharing and exchanging voluminous information among thousands or even millions of users. The massive amount of information shared in such systems mandates efficient semantic-based search instead of key-based search. The majority of existing proposals can only support simple key-based search rather than semantic-based search. This paper presents the design of an overlay network, namely, semantic small world (SSW), that facilitates efficient semantic-based search in P2P systems. SSW achieves the efficiency based on four ideas: 1) semantic clustering, where peers with similar semantics organize into peer clusters, 2) dimension reduction, where to address the high maintenance overhead associated with capturing high-dimensional data semantics in the overlay, peer clusters are adaptively mapped to a one-dimensional naming space, 3) small world network, where peer clusters form into a one-dimensional small world network, which is search efficient with low maintenance overhead, and 4) efficient search algorithms, where peers perform efficient semantic-based search, including approximate point query and range query in the proposed overlay. Extensive experiments using both synthetic data and real data demonstrate that SSW is superior to the state of the art on various aspects, including scalability, maintenance overhead, adaptivity to distribution of data and locality of interest, resilience to peer failures, load balancing, and efficiency in support of various types of queries on data objects with high dimensions.     

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

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

P2P系统的性能优化：研究综述

Peer-to-Peer(P2P)计算模型在利用和管理日益增长的分布式信息和资源方面是一种非常成功的计算模型。但是这种计算模式也有一些缺点,特别是decentralized unstructured P2P系统,它将随机选择邻居和blind floodingsearch机制联合起来使用,使系统的网络开销急速地增加,严重地影响了系统的性能。本文介绍了减少decentralizedunstructured P2P系统网络开销的各类方法,对它们的优缺点进行了详细的比较,并根据比较的结果对今后的发展趋势进行了展望。     

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.     

改进的基于概率的非结构化对等网搜索算法

资源发现是P2P应用所面临的最核心问题之一.无结构P2P主要采用了查询消息泛洪和信息索引机制,会造成严重的网络带宽负担以及巨大的索引维护开销.提出了一种无结构P2P环境下一种改进的概率自适应的、动态缓存和索引算法EAPS,EAPS算法依据用户结点和用户结点的邻居节点命中查询的历史信息赋予结点相应权值作为查询消息路由的依据,引导查询快速接近目标资源,同时能够解决由搭便车结点所带来的网络带宽消耗.自适应缓存机制和索引机制的引入使搜索性能大为加强.最后的实验表明,附带自适应缓存和索引的EAPS,以其高搜索成功率、很短的时间响应,能够显著地提高资源发现性能.     

A Two-Hop Solution to Solving Topology Mismatch

The efficiency of Peer-to-Peer (P2P) systems is largely dependent on the overlay constructions. Due to the random selection of logical neighbors, there is serious topology mismatch problem between the overlay and the physical topologies in many P2P systems. Such mismatching causes unnecessary query message duplications on both overlay and IP level, as well as increase query response time. In this research, we define the optimal overlay problem, and prove its NP-hardness. To address this issue, we propose a distributed overlay optimization algorithm, THANCS, and evaluate its effectiveness through trace driven simulations. The proposed THANCS has four major strengths. First, it does not need any global knowledge. Second, its optimization convergent speed is fast. Third, it is orthogonal to other types of advanced search approaches. Fourth, it reduces both the traffic cost and the search latency.     

一种高效的无结构对等网查询机制

提出一种提高无结构型对等网络查询效率的机制。在该机制下,节点根据地理位置自动聚类,类之间用Chord方式组合起来,从而减轻了逻辑网络与物理网络拓扑结构的不匹配。为了进一步提高查询效率,引入了一种类间索引技术。该技术使得查询消息不需要遍历所有的类就能获得全局搜索结果。与Gnutella中的洪泛滥查询相比,在TTL=5的情况下,该机制最多能减少超过80%的资源开销,最多可以将响应时间缩短59%。     

一种基于兴趣协助的P2P网络共享文件搜索方法

分析了传统的结构化P2P网络和非结构化P2P网络搜索方法的优点和缺点,提出了一种基于兴趣协助的搜索方法,通过在结构化P2P网络节点上发布兴趣来加速非结构化P2P网络上的查询。实验结果表明,此方法在查询成功率和搜索延迟等方面都有着较好的性能。     

Survey on Anonymity in Unstructured Peer-to-Peer Systems

Although anonymizing Peer-to-Peer （P2P） networks often means extra cost in terms of transfer efficiency, many systems try to mask the identities of their users for privacy consideration. By comparison and analysis of existing approaches, we investigate the properties of unstructured P2P anonymity, and summarize current attack models on these designs. Most of these approaches are path-based, which require peers to pre-construct anonymous paths before transmission, thus suffering significant overhead and poor reliability. We also discuss the open problems in this field and propose several future research directions.     

Semantic indexing in structured peer-to-peer networks

The past few years have seen tremendous advances in distributed storage infrastructure. Unstructured and structured overlay networks have been successfully used in a variety of applications, ranging from file-sharing to scientific data repositories. While unstructured networks benefit from low maintenance overhead, the associated search costs are high. On the other hand, structured networks have higher maintenance overheads, but facilitate bounded time search of installed keywords. When dealing with typical data sets, though, it is infeasible to install every possible search term as a keyword into the structured overlay.     

RAP2P：一种基于资源广告的非结构化P2P系统

研究了非结构化P2P系统的数据管理和相应的资源查询算法。提出了基于资源广告的非结构化P2P系统，即RAP2P。设计了一种类似谣言传播机制的资源信息广告算法AdGossip来传播共享资源广告，并且通过共享资源广告缓存限制机制来保证局部区域缓存空间对共享资源节点的最大覆盖率。分析和模拟结果表明，在获得100％查询命中率的条件下，RAP2P的资源定位消息开销约为泛洪查询的25％，查询的时延为泛洪查询的30%~50%，并且远远低于k-random walks。     

非结构化P2P系统Overlay优化技术综述

非结构化P2P Overlay网络的结构松散, 网络中资源的分布没有明确的限制, 这使得非结构化P2P Overlay网络中的资源搜索在很大程度上依赖于通信开销巨大的泛洪法, 因而非结构化P2P系统在伸缩性, 可用性等方面, 存在明显的不足. 非结构化P2POverlay网络的上述特点决定了非结构化P2P Overlay优化技术的重要性. 本文分四大类别, 对非结构化P2P Overlay优化技术进行了介绍, 分析比较了各类方法的优劣以及它们的适用场合, 并在此基础上对未来工作进行了展望.     

Limited Scale-Free Overlay Topologies for Unstructured Peer-to-Peer Networks

In unstructured peer-to-peer (P2P) networks, the overlay topology (or connectivity graph) among peers is a crucial component in addition to the peer/data organization and search. Topological characteristics have profound impact on the efficiency of a search on such unstructured P2P networks, as well as other networks. A key limitation of scale-free (power-law) topologies is the high load (i.e., high degree) on a very few number of hub nodes. In a typical unstructured P2P network, peers are not willing to maintain high degrees/loads as they may not want to store a large number of entries for construction of the overlay topology. Therefore, to achieve fairness and practicality among all peers, hard cutoffs on the number of entries are imposed by the individual peers, which limits scale-freeness of the overall topology, hence limited scale-free networks. Thus, it is expected that the efficiency of the flooding search reduces as the size of the hard cutoff does. We investigate the construction of scale-free topologies with hard cutoffs (i.e., there are not any major hubs) and the effect of these hard cutoffs on the search efficiency. Interestingly, we observe that the efficiency of normalized flooding and random walk search algorithms increases as the hard cutoff decreases.     

基于紧缩状态表的高效数据定位方法

数据定位是松散式P2P系统面临的挑战性难题。本文提出了一种新的数据定位方法--紧缩状态表方法（CSTM）。在CSTM中,每个结点上维护一个状态表,保存了丁跳（Hop）内全部邻居上数据的关键字信息,各个结点按照状态表来转发数据定位消息。CSTM方法采用Bloom Filter技术来压缩表示状态表,采用查询Cache建立与最近访问的结点之间的快捷连接。模拟结果表明,与广播泛洪和二路随机转发方法相比,CSTM方法大大减低了P2P网络中数据定位的消息开销,并能够获得较短的查询路径长度。     

HAPS: Supporting Effective and Efficient Full-Text P2P Search with Peer Dynamics

Recently, peer-to-peer (P2P) search technique has become popular in the Web as an alternative to centralized search due to its high scalability and low deployment-cost. However, P2P search systems are known to suffer from the problem of peer dynamics, such as frequent node join/leave and document changes, which cause serious performance degradation. This paper presents the architecture of a P2P search system that supports full-text search in an overlay network with peer dynamics. This architecture, namely HAPS, consists of two layers of peers. The upper layer is a DHT (distributed hash table) network interconnected by some super peers (which we refer to as hubs). Each hub maintains distributed data structures called search directories, which could be used to guide the query and to control the search cost. The bottom layer consists of clusters of ordinary peers (called providers), which can receive queries and return relevant results. Extensive experimental results indicate that HAPS can perform searches effectively and efficiently. In addition, the performance comparison illustrates that HAPS outperforms a flat structured system and a hierarchical unstructured system in the environment with peer dynamics.     

Distributed middleware architectures for scalable media services

The fusion of Multimedia and Internet technology has introduced an ever-increasing demand for large-scale reliable media services. This exposes the scalability limitations of current middleware architectures, as they traditionally operate on either very large-server configurations or on tightly coupled distributed systems. On the other hand, the wide availability of high-speed networks and the widespread deployment of powerful personal computing units by end users, has emphasized the advantages of the peer-to-peer (P2P) computing model. In this paper, we evaluate a number of different middleware architectures that facilitate the timely and reliable delivery of media services in P2P networks. Our evaluated architectures exploit features including availability of high-performance links, replication and caching of popular items and finally state-of-the-art search techniques proposed in the context of structured and unstructured P2P overlay networks. Through detailed simulation we investigate the behavior of the suggested P2P architectures for video provision and examine the involved trade-offs. We show that under realistic assumptions, the evaluated architectures are resilient to multiple peer-failures, are scalable with respect to dropped requests when the number of messages in the network increases and provide good response times to the user requests.