论文部分内容阅读
P2P系统的广泛应用推动了当前P2P相关技术的发展,随着应用的不断增加,数据查询已经不再仅限于最初的单一关键字查询或关键字精确匹配。目前,结构化P2P系统中对于复杂查询的支持,例如区间查询、前缀查询和聚合查询等,已成为一项具有积极意义的课题。P2P系统所特有的易变性和规模大等特点,使这一技术变得更为复杂。传统的结构化P2P覆盖网络大都基于分布式哈希表(以下简称DHT)技术构建,这一技术可以实现高效的资源查找,并使系统实现负载平衡,但也存在破坏数据顺序的缺点,从而使得区间查询在这类系统中难以实现。为了解决这一问题,一类非基于DHT技术构建的系统被相应提出,用以解决结构化覆盖网络中的区间查询问题。此外,对于已有的覆盖网络进行修改,使其能够支持区间查询也是解决这一问题的一种方法。De Bruijn图是一种特殊的图结构,它具有常数度和最优网络直径的特点。我们通过使用多层后缀树和De Bruijn图相结合的拓扑结构,设计了DBST覆盖网络,该网络既有树形结构对数据顺序保留的特点,使系统能够支持区间查询,同时也具备De Bruijn图在静态网络中节点常数度的优点,为基于De Bruijin图和DHT技术构建的结构化P2P覆盖网络提供了一种解决区间查询问题的方法。跳图(skip graph)是一种本身支持区间查询的图结构,它是树形结构的一种变形,可以保留数据顺序,同时,一个节点在网络中还存在多个复本,这使得使用该结构的网络具有较高的容错性。通过使用该结构我们设计了一种非基于DHT技术的P2P覆盖网络,称为SGPO覆盖网,它是一种基于跳图的并可实现拓扑意识路由的P2P覆盖网络。通过设计该系统,我们在解决区间查询问题的同时,还解决了物理网络与逻辑网络不一致的问题。本文主要对支持区间查询功能的结构化P2P覆盖网络进行设计与分析,全文共分为五章。第一章绪论说明了研究的背景和问题的提出,以及论文所做的工作和组织结构;第二章是对现有的解决区间查询问题的方法的概述;第三章是构造基于De Bruijn有向图的多层后缀树覆盖网络(DBST);第四章是设计基于跳图的具有拓扑意识路由的区间查询系统(SGPO);第五章是本文的总结以及对下一步工作的展望。