语义对等网构造及搜索机制研究

对等网文件共享系统能否成功极大地取决于搜索机制的多样性和扩展性。当前支持分布式Hash表(DHT)功能的结构化系统(如CAN)易扩展但不能有效地支持部分匹配的查询，而基于扩散的非结构化系统(如Gnutella)支持多样化查询但不易扩展。提出了一种新的对等网体系结构。基于CAN构造的pGroup介于结构化和非结构化之间：结点根据内容的类别自组织在一起，具有相同类别的结点相互关联构成语义对等网(semantic peer-to-peer networks，SPNs)。针对不同的查询行为，提出了相应的搜索算法。实验表明，pGroup比Gnutella的扩展性好，搜索效率高。     

SELF-ORGANIZING PEER-TO-PEER SOCIAL NETWORKS

Peer-to-peer (P2P) systems provide a new solution to distributed information and resource sharing because of its outstanding properties in decentralization, dynamics, flexibility, autonomy, and cooperation, summarized as DDFAC in this paper. After a detailed analysis of the current P2P literature, this paper suggests to better exploit peer social relationships and peer autonomy to achieve efficient P2P structure design. Accordingly, this paper proposes Self-organizing peer-to-peer social networks (SoPPSoNs) to self-organize distributed peers in a decentralized way, in which neuron-like agents following extended Hebbian rules found in the brain activity represent peers to discover useful peer connections. The self-organized networks capture social associations of peers in resource sharing, and hence are called P2P social networks. SoPPSoNs have improved search speed and success rate as peer social networks are correctly formed. This has been verified through tests on real data collected from the Gnutella system. Analysis on the Gnutella data has verified that social associations of peers in reality are directed, asymmetric and weighted, validating the design of SoPPSoN. The tests presented in this paper have also evaluated the scalability of SoPPSoN, its performance under varied initial network connectivity and the effects of different learning rules.     

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

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

模式异构P2P网络中支持复杂查询的策略

结构化P2P重叠网络不能高效支持模式异构环境下的复杂查询,这限制了它在基于模式的P2P系统中的应用,使其在可扩展性和路由性能等方面的优势得不到充分利用.通过用关键字作为模式元素的索引键和垂直分区关系元组,设计了用结构化重叠网络索引模式和数据的方法,提出了在这两级索引上支持复杂查询处理的算法.定性分析和比较表明该方法较现有成果更接近P2P数据管理的理想目标.     

Associative search in peer to peer networks: Harnessing latent semantics

The success of a P2P file-sharing network highly depends on the scalability and versatility of its search mechanism. Two particularly desirable search features are scope (ability to find infrequent items) and support for partial-match queries (queries that contain typos or include a subset of keywords). While centralized-index architectures (such as Napster) can support both these features, existing decentralized architectures seem to support at most one: prevailing unstructured P2P protocols (such as Gnutella and FastTrack) deploy a “blind” search mechanism where the set of peers probed is unrelated to the query; thus they support partial-match queries but have limited scope. On the other extreme, the recently-proposed distributed hash tables (DHTs) such as CAN and CHORD, couple index location with the item’s hash value, and thus have good scope but can not effectively support partial-match queries. Another hurdle to DHTs deployment is their tight control of the overlay structure and the information (part of the index) each peer maintains, which makes them more sensitive to failures and frequent joins and disconnects.We develop a new class of decentralized P2P architectures. Our design is based on unstructured architectures such as Gnutella and FastTrack, and retains many of their appealing properties including support for partial match queries, and relative resilience to peer failures. Yet, we obtain orders of magnitude improvement in the efficiency of locating rare items. Our approach exploits associations inherent in human selections to steer the search process to peers that are more likely to have an answer to the query. We demonstrate the potential of associative search using models, analysis, and simulations.     

Gnutella网络文件共享属性的测量与分析

以Gnutella网络为测量对象,分析了Gnutella网络的基本特点和关键协议,利用Limewire的源代码设计了一个Gnutella网络内容爬虫,测量了Gnutella网络中用户的共享文件类型、共享文件数目、共享空间、文件副本、用户日均在线时长和节点应用层带宽,并对以上测量结果进行统计分析。统计分析表明文件共享数目与共享空间存在显著的相关关系,应用层带宽与日均在线时长则存在弱相关关系。此外,对Gnutella网络中的用户按照共享文件数目、共享空间、应用层带宽、日均在线时长这4个方面进行了聚类分析,分析结果表明,Gnutella网络中的平庸用户占所统计用户数的97%。     

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.     

非结构化对等计算系统中多维范围搜索

对等计算数据管理中的一个重要问题是如何有效地支持多维数据空间上的相似性搜索.现有的非结构化对等计算数据共享系统仅支持简单的查询处理方法,即匹配查询处理.将近似技术和路由索引结合在一起,设计了一种简单、有效的索引结构EVARI(扩展近似向量路由索引).利用EVARI,每个节点不仅可以在本地共享的数据集上处理范围查询,而且还可以将查询转发给最有希望获得查询结果的邻居节点.为了建立EVARI,每个节点使用空间划分技术概括本地的共享内容,并与邻居节点交换概要信息.而且,每个节点都可以重新配置自己的邻居节点,使得相关节点位置相互邻近,优化了系统资源配置,提升了系统性能.仿真实验证明了该方法的良好性能.     

基于P2P的个性化Web搜索系统的设计与实现

针对中心化的Web信息搜索系统在覆盖率、及时性、个性化、可扩展性等方面存在的问题,提出了一种基于Peer-to-Peer(P2P)的可扩展、个性化的Web搜索系统PeerBridge。PeerBridge基于分布式哈希表组织大量的网络结点形成有组织的P2P覆盖网络,每个对等体作为一个主题搜索引擎,根据用户兴趣从Web中搜索特定主题相关的信息,而具有相似主题的对等体被聚集在一起形成基于主题的对等体簇,协作进行Web搜索与信息共享。并采用主题驱动的Web爬行、基于语义概念的文档分类、个性化的链接分析和基于主题划分的P2P搜索等机制来改善PeerBridge的性能。     

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.     

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.     

A congestion-aware search protocol for heterogeneous peer-to-peer networks

Peer-to-Peer (P2P) file sharing is the hottest, fastest growing application on the Internet. When designing Gnutella-like applications, the most important consideration is the scalability problem, because P2P systems typically support millions of users online concurrently. Gnutella suffers from poor scaling due to its flooding-based search, resulting in excessive amounts of repeated query messages. Therefore, a good search protocol plays an important role in a system’s scalability. However, congestion, due to large query loads from users, definitely impacts on the performance of search protocols, and this consideration has received little attention from the research community. In this paper, we propose a congestion-aware search protocol for unstructured P2P networks. Our protocol consists of three parts—Congestion-Aware Forwarding, Random Early Stop and Emergency Signaling. The aim of our protocol is to integrate congestion control and object discovery functionality so that the search protocol can achieve good performance under congested networks and flash crowds. We perform extensive simulations to study our proposed protocol. The results show that our protocol can significantly reduce the hit delay while maintaining the high hit rate and also the congestion problems such as query loss and the peer overloading problem can be effectively alleviated.     

利用多级局部性实现可扩展的无结构P2P 搜索

无结构P2P网络拓扑随着规模的增大会出现一定的统计特性,充分应用该现象提出了一种多级局部覆盖网络(multi-level local overlay,简称ML2O)的无结构P2P覆盖网,对ML2O中节点间的连接进行恰当的数学控制后,就能使产生的拓扑具有从微观到宏观的多个粒度上的局部性.理论分析表明,ML2O的网络直径和节点平均度都是网络规模n的对数,为其上建立可扩展的无结构P2P搜索奠定了基础.给出了应用ML2O多粒度局部特性的索引机制:首先以局部为单位建立信息索引;然后在局部索引的基础上建立更大粒度局部的索引,从而形成一棵索引树;最后提出了一种局部渗透定向搜索算法(local pervasion and directed search,简称LPDS).LPDS用局部渗透收集到的信息建立部分索引树,并在树上找到更接近搜索目标的下一跳.理论分析表明,LPDS搜索算法的平均搜索跳数和通信负载都是O(logn).模拟实验结果表明,ML2O上LPDS的可扩展性接近结构化P2P搜索,其鲁棒性接近无结构P2P搜索.     

An adaptive secure communication framework for mobile peer-to-peer environments using Bayesian games

Peers in Mobile P2P (MP2P) networks exploit both the structured and unstructured styles to enable communication in a peer-to-peer fashion. Such networks involve the participation of two types of peers: benign peers and malicious peers. Complexities are witnessed in the determination of the identity of the peers because of the user mobility and the unrestricted switching (ON/OFF) of the mobile devices. MP2P networks require a scalable, distributed and light-weighted secure communication scheme. Nevertheless, existing communication approaches lack the capability to satisfy the requirements above. In this paper, we propose an Adaptive Trusted Request and Authorization model (ATRA) over MP2P networks, by exploiting the limited historical interaction information among the peers and a Bayesian game to ensure secure communication. The simulation results reveal that regardless of the peer’s ability to obtain the other such peer’s trust and risk data, the request peers always spontaneously connect the trusted resource peers and the resource peers always preferentially authorize the trusted request peers. Performance comparison of ATRA with state-of-the-art secure communication schemes over MP2P networks shows that ATRA can: (a) improve the success rate of node typing identification, (b) reduce time required for secure connections found, (c) provide efficient resource sharing, and (d) maintain the lower average cost.     

P2P网络中基于谣言传播机制的资源搜索算法

当前许多P2P网络如KaZaA和Gnutella模型仅使用“洪泛”广播机制,从而造成严重的通信拥塞。针对这种现状,提出了一种基于谣言传播机制的资源搜索算法,任何运行该算法的源节点只需要相对少的节点参与通信,就能以相对大的概率找到资源。仿真结果表明,该算法是优异的。     

P2P文件共享网络中信任管理系统的设计

针对P2P文件共享网络,设计了一个信任管理系统来评估、分发网络中各个实体的信任信息,并利用信任指导协作实体的选择,以隔离恶意实体,改善网络性能.之后的仿真实验证明了系统的有效性.     

Gnutella环境下资源定位方法的改进

本文在已有研究的基础上提出了一种基于节点间部分通路的资源定位方法,加入节点基于邻居节点的逻辑度选择要建立链接的节点,请求节点通过所构建的逻辑结构来定位资源。仿真实验的结果表明,与传统广播方法相比,所提出的方法能有效地降低Gnutella网络的通讯负载,减少冗余消息,提高Gnutella网络的可扩展性,这些对于未来智能网络打印机的研发具有深远意义。     

Linking identical neighborly partitions for efficient high-dimensional similarity search in unstructured peer-to-peer systems

Peer-to-Peer (P2P) computing has recently attracted a great deal of research attention. In a P2P system, a large number of nodes can potentially be pooled together to share their resources, information, and services. However, existing unstructured P2P systems lack support for content-based search over data objects which are generally represented by high-dimensional feature vectors. In this paper, we propose an efficient and effective indexing mechanism to facilitate high-dimensional similarity query in unstructured P2P systems, named Linking Identical Neighborly Partitions (LINP), which combines both space partitioning technique and routing index technique. With the aid of LINP, each peer can not only process similarity query efficiently over its local data, but also can route the query to the promising peers which may contain the desired data. In the proposed scheme, each peer summarizes its local data using the space partitioning technique, and exchanges the summarized index with its neighboring peers to construct routing indices. Furthermore, to improve the system performance with peer updates, we propose an extension of the LINP, named LINP⁺, where each peer can reconfigure its neighboring peers to keep relevant peers nearby. The performance of our proposed scheme is evaluated over both synthetic and real-life high-dimensional datasets, and experimental results show the superiority of our proposed scheme.     

DiCAS: An Efficient Distributed Caching Mechanism for P2P Systems

Peer-to-peer networks are widely criticized for their inefficient flooding search mechanism. Distributed Hash Table (DHT) algorithms have been proposed to improve the search efficiency by mapping the index of a file to a unique peer based on predefined hash functions. However, the tight coupling between indices and hosting peers incurs high maintenance cost in a highly dynamic network. To properly balance the tradeoff between the costs of indexing and searching, we propose the distributed caching and adaptive search (DiCAS) algorithm, where indices are passively cached in a group of peers based on a predefined hash function. Guided by the same function, adaptive search selectively forwards queries to "matched” peers with a high probability of caching the desired indices. The search cost is reduced due to shrunk searching space. Different from the DHT solutions, distributed caching loosely maps the index of a file to a group of peers in a passive fashion, which saves the cost of updating indices. Our simulation study shows that the DiCAS protocol can significantly reduce the network search traffic with the help of small cache space contributed by each individual peer.     

Implications of the file names and user requested queries on Gnutella performance

The Gnutella file sharing system allows a large number of peers to share their local files. However, it does not coordinate the way by which these shared objects are named or how they are searched by other users; such decisions are made independently by each peer. In this work, we investigate the practical performance implications of this design. We collected the shared filenames and user generated queries over a three-year period. We show the mismatch between these naming mechanisms. We show the fundamental limitations of Gnutella performance that cannot be addressed by improvements in overlays or by varying the search mechanisms alone. Based on our observations, we describe two practical approaches to improve Gnutella performance. We describe a mechanism to build the file term synopsis using the observed popularity of queries routed through the ultrapeer. We also describe a query transformation mechanism that improves the success rates for failed queries.