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.     

结构化对等网测量方法研究

网络测量是深入开展结构化对等网研究的基础,结构化对等网络协议设计、共享内容检索、态势感知乃至安全性的研究都需要以网络测量为前提.在节点分布对等、实时变化显著、未知瞬发扰动频繁的结构化对等网络中,获得其准确、完整的网络信息更是十分困难的.通过形式化分析结构化对等网节点搜索过程,研究节点信息在全网分布情况与查询返回率之间的关系,将历史测量数据与具体对等网特征信息相结合挖掘节点搜索优化策略,提出了一种网络资源占用显著降低、搜索速度较快、信息完备率较高的搜索测量优化方法.KAD 网络是目前得到大规模部署运行的为数不多的结构化对等网络之一,以KAD 网络为主要研究对象开发了KadCrawler 对等网搜索系统,进行了大量测量和分析,验证了搜索优化方法的可行性和有效性;同时,对当前KAD 网络拓扑结构特征、节点重名等现象进行了初步分析,发现KAD 网络近年来发生了显著的变化.     

一种分组P2P网络模型

Internet的飞速发展使对等网络(P2P)及其相关领域的研究成为热点,但是当前P2P网络的结构并不完善。文中介绍了几种P2P模型,并在综合这几种模型优点的基础上,针对P2P网络的动态特性提出了一种分组P2P模型。该模型使用组节点管理对等点的加入和退出,有助于提高对等网络的稳定性。     

基于节点兴趣的非结构化P2P搜索机制

针对P2P系统缺乏有效信息搜索机制的问题,提出一种基于节点兴趣的非结构化P2P搜索机制。通过挖掘每个节点的兴趣,将节点按照其相关性组成网络,使相关性高的节点在网络中距离较近。在P2P网络中进行信息搜索时,只将查询消息路由到相关兴趣的节点上,以改善搜索效率。     

基于多媒体特征的抗扰动P2P搜索算法

基于多媒体特征的分布式文件搜索算法应用在扰动的P2P环境时,因节点频繁加入、退出,导致拓扑破坏和搜索效果大幅下降。针对上述问题,提出能够克服网络扰动、适用于P2P环境的搜索算法,该算法将分布式多媒体搜索算法与P2P动态更新机制集成。实验结果表明,该算法在高强度的扰动环境下能保持稳定和高效的性能。     

Optimizing P2P streaming throughput under peer churning

High-throughput P2P streaming relies on peer selection, the strategy a peer uses to select other peer(s) as its parent(s) of streaming. Although this problem has been thoroughly investigated in the classical optimization framework under static settings, it still remains unaddressed as how to sustain throughput competitive to the optimum under highly dynamic peer churning. To accommodate such peer dynamics, we extend the classical optimization framework and propose a distributed online peer selection algorithm. This basic algorithm is further extended to a variety of settings commonly seen in operational P2P networks, such as multi-parent streaming, admission control, delay constraint, etc. We prove approximation bound of our algorithm to the optimal throughput. Through evaluation under different topological setups and peer churning sequences, we show that our solution can consistently deliver competitive throughput, which greatly outperforms its theoretical bound. This work was supported by NSF award 0643488, Vanderbilt Discovery grant, and a gift from Microsoft Research. Views and conclusions of this paper are those of authors, which should not be interpreted as representing the official policies, either expressed or implied, of the funding agencies.     

Distributed Throughput Maximization in P2P VoD Applications

In peer-to-peer (P2P) video-on-demand (VoD) systems, a scalable source coding is a promising solution to provide heterogeneous peers with different video quality. In this paper, we present a systematic study on the throughput maximization problem in P2P VoD applications. We apply network coding to scalable P2P systems to eliminate the delivery redundancy. Since each peer receives distinct packets, a peer with a higher throughput can reconstruct the video at a higher quality. We maximize the throughput in the existing buffer-forwarding P2P VoD systems using a fully distributed algorithm. We demonstrate in the simulations that the proposed distributed algorithm achieves a higher throughput compared to the proportional allocation scheme or the equal allocation scheme. The existing buffer-forwarding architecture has a limitation in total upload capacity. Therefore we propose a hybrid-forwarding P2P VoD architecture to improve the throughput by combining the buffer-forwarding approach with the storage-forwarding approach. The throughput maximization problem in the hybrid-forwarding architecture is also solved using a fully distributed algorithm. We demonstrate that the proposed hybrid-forwarding architecture greatly improves the throughput compared to the existing buffer-forwarding architecture. In addition, by adjusting the priority weight at each peer, we can implement the differentiated throughput among different users within a video session in the buffer-forwarding architecture, and the differentiated throughput among different video sessions in the hybrid-forwarding architecture.      

P2ST：基于带权搜索树的P2P搜索模型

针对非结构化P2P系统搜索效率低的问题,提出了一种基于K叉带权搜索树的P2P搜索模型P2ST.模型构建了服务于搜索的k叉带权树,节点按查询命中率大小在树中由上至下排列,命中率大且稳定的节点处于树的上层,搜索时可由此确定消息扩散的方向.采用缓存上层节点、建立搜索结果和发起节点索引、过热资源复制、为叶节点添加远程邻居等方法进一步提高搜索效率和平衡负载.分析和仿真结果表明,提出的模型能大量减少无效消息,具有较高的搜索效率,且维护搜索树的开销较小.     

基于P2P的信息共享Agent的研究

Napster和Gnutella各有其优点和不足,为了克服它们的不足之处,该文提出了基于Agent的Super-Peers网络结构。网络中的信息剧增,为了克服传统的关键字查找方法的不精确性,Agent采用元数据进行精确查找。每个节点的Agent提供主动服务和智能搜索功能。在P2P搜索过程中,提出了一种解决双方都不在线情况下的基于元数据的查找及下载所需信息的方法。     

Web search results caching service for structured P2P networks

This paper proposes a two-level P2P caching strategy for Web search queries. The design is suitable for a fully distributed service platform based on managed peer boxes (set-top-box or DSL/cable modem) located at the edge of the network, where both boxes and access bandwidth to those boxes are controlled and managed by an ISP provider. Our solution significantly reduces user query traffic going outside of the ISP provider to get query results from the respective Web search engine. Web users are usually very reactive to worldwide events which cause highly dynamic query traffic patterns leading to load imbalance across peers. Our solution contains a strategy to quickly ease imbalance on peers and spread communication flow among participating peers. Each peer maintains a local result cache used to keep the answers for queries originated in the peer itself and queries for which the peer is responsible for by contacting the Web search engine on-demand. When query traffic is predominantly routed to a few responsible peers our strategy replicates the role of “being responsible for” to neighboring peers so that they can absorb query traffic. This is a fairly slow and adaptive process that we call mid-term load balancing. To achieve a short-term fair distribution of queries we introduce a location cache in each peer which keeps pointers to peers that have already requested the same queries in the recent past. This lets these peers share their query answers with newly requesting peers. This process is fast as these popular queries are usually cached in the first DHT hop of a requesting peer which quickly tends to redistribute load among more and more peers.     

一种基于SSL协议的点对点通信架构

P2P打破传统的C／S模式,每个节点在网络中的地位都是对等的,既充当服务器,同时也共享其它服务。早期P2P网络仅考虑可用性,安全问题一直没有得到很好的解决。以下提出一种基于SSL协议的点对点通信架构,将安全套接字层SSL协议植入P2P网络,实现点对点安全通信,最后通过仿真实验和数据分析说明该实现方法的可行性。     

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

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

一种面向服务的P2P存储系统模型

P2P存储系统以功能对等的方式组成存储网络,面向服务的体系结构为存储资源的有效管理以及按需服务的实现提供了一种思路。提出的P2P存储系统模型采用分层思想,建立在结构化覆盖网络之上,将异构节点存储资源封装成服务块,以用户需求为出发点,通过服务的动态选取和组合,形成可定制的个人存储视图,并给出一种对等节点的功能部署结构。模型达到分散控制,具有良好的可扩展性。     

面向分布式协同设计的对等信息共享系统

为了实现分布式协同设计中的共享信息快速检索以及多副本同步,提出了基于对等网结构的信息共享系统,给出了该信息共享系统的节点模型、管理策略及信息检索模型,提出了一种结合分布式哈希表和聚类的检索方法,保证了用户能够在协同设计系统中快速地精确检索和“盲目”检索,实现了系统的用户透明。为了保证分布式多副本同步,提出“对等锁”作为一致性维护方法。该文给出了系统的具体实现方法,并给出了实例。     

基于幂律分布的P2P信誉评估机制

P2P网络具有良好的可扩展性和健壮性,但其匿名性、开放性等特征成为恶意行为的理想环境。针对上述问题,提出一种基于幂律分布的信誉评估机制识别网络中的良性行为,抵制恶意行为。仿真测试表明,运用该机制后计算节点信誉分值具有较小的计算开销和良好的准确度,支持节点的动态加入和退出,对于恶意节点的骚扰具有很强的健壮性。     

MANET adaptive structured P2P overlay

This paper presents an efficient structured P2P overlay over MANET which better matches to the physical network in term of routing. This feature is achieved by locally building up the minimum-spanning tree (MST) at each peer using the information of the peer’s logical neighbors which are either directly connected (1-hop) or 2-hops away. Using this interconnection structure among the peers, we design a new algorithm to distribute the contents information in the overlay by partitioning the identifier (ID) space among the peers. In this algorithm, each peer maintains a disjoint portion of the ID space. The ID space at a peer may be non-contiguous and each contiguous part is consecutive to the ID space of its directly connected neighbor peers. To route the file-lookup query, each peer builds up a binary search tree (BST) using the knowledge of the ID space of itself and of its directly connected neighbor peers. Simulation results show that our approach outperforms the existing approaches in term of routing overhead, average file-discovery delay, false-negative ratio and average path-stretch value.     

非结构化P2P网络拓扑结构的改进机制

非结构化的P2P网络由于方便的全局部署和支持模糊匹配,而越来越受到欢迎,但是非结构化的P2P网络采用了洪泛的广播方式,因而导致网络的缩放性比较差,该文则在研究非结构化P2P网络拓扑结构存在问题的基础之上,提出采用平衡二叉树作为非结构化P2P网络的拓扑结构,设计相应的网络节点加入,节点退出,资源搜索等算法,并通过相应的仿真来展示改进的效果。     

IGSS:一种基于兴趣组的非结构P2P网络模型

针对非结构P2P网络中搜索机制效率低下的问题,提出一种基于兴趣组的高效搜索模型。通过计算节点的相似性,得到兴趣节点,从而建立快捷链接,形成兴趣组。搜索请求首先在兴趣组中传播,提高了搜索效率。实验结果表明该模型对搜索请求具有较高的效率和准确性。     

一种新型的层次P2P搜索模型

在分析现有P2P模型的基础上，提出了一种新的P2P搜索模型，该模型是分层的混合结构，利用分组和建立搜索空间的机制，来提高搜索的效率，增强系统的可扩展性。同时为低带宽节点引入了搜索代理的机制，提高了带宽的利用率，减少了搜索延迟。而且为了增强网络的自恢复性，利用缓存机制引入了备用连接，使搜索模型具有较好的容错能力。     

PHIRST: A distributed architecture for P2P information retrieval

Recent progress in peer to peer (P2P) search algorithms has presented viable structured and unstructured approaches for full-text search. We posit that these existing approaches are each best suited for different types of queries. We present PHIRST, the first system to facilitate effective full-text search within P2P databases. PHIRST works by effectively leveraging between the relative strengths of these approaches. Similar to structured approaches, agents first publish terms within their stored documents. However, frequent terms are quickly identified and not exhaustively stored, resulting in a significant reduction in the system's storage requirements. During query lookup, agents use unstructured search to compensate for the lack of fully published terms. Additionally, they explicitly weigh between the costs involved in structured and unstructured approaches, allowing for a significant reduction in query costs. Finally, we address how node failures can be effectively addressed through storing multiple copies of selected data. We evaluated the effectiveness of our approach using both real-world and artificial queries. We found that in most situations our approach yields near perfect recall. We discuss the limitations of our system, as well as possible compensatory strategies.