对等网络(Peer-to-Peer Networks,简称P2P网络)是采用对等模式工作的计算机网络,是分布式系统与计算机网络相结合的产物。目前,P2P网络已经被广泛应用于Internet环境下的文件共享中。在P2P网络中的每个结点在功能上是平等的,在行为上是自由的,在连接上是互联的,打破了传统的客户/服务器模式,让一切网络结点享有平等、自由、互联的功能,不再有客户、服务器之分,任何两个网络结点之间都能共享文件、传递信息。因此,它能够极大程度地提高网络效率、充分利用网络带宽、开发了每个网络结点的潜力,具有非常高的扩展性和容错性。这使得P2P技术迅速发展成为计算机网络的一项重要技术,在应用领域和学术界获得了广泛的重视。由于它占据了当前Internet超过一半的带宽资源,被认为是“改变Internet的新一代网络技术”。P2P网络高效的一个重要原因是它在网络应用层上构建了一个有严格拓扑结构的覆盖网络。从设计思想和体系结构来看,P2P覆盖网络的研究可分为结构化和非结构化两种,它们有各自的优缺点。本论文的研究是基于结构化P2P覆盖网络,结构化P2P覆盖网络是基于分布式哈希表(DHT)来准确、快速地路由信息和定位数据对象。针对结构化P2P网络拓扑的研究发现,构造的P2P系统性能在很大程度上与该P2P系统底层所依据的静态图的性质有关,因此在学术界对于结构化P2P网络的研究,可根据底层所依据的静态图形不同,分为常数度DHT和非常数度DHT。近年来,对于常数度DHT的研究已经引起了学术界的高度重视,尤其是对于平均路由长度与路由表规模的折衷方面的研究。常数度DHT通常是基于一定的常数度静态图来构造的,例如:CAN是基于d-维环面的;Viceroy是基于蝶形图;D2B和Koorde都是依赖于De Brujin有向图的;FissonE和Moore都是建立在静态Kautz图上的。这些基于常数度静态图构造的P2P系统,其性能不仅在某些方面优于非常数度P2P系统,而且在很大程度上与其所依赖的静态图的性质有关,因此从图论的角度来研究P2P系统成为一种行之有效的方法。本论文首先从图论的角度入手研究P2P系统,提出了另一种常数度结构化的P2P覆盖网络协议,它是基于De Brujin有向图的。此系统首先对De Brujin有向图进行修改,然后把分布式线图技术应用于修改后的De Brujin有向图,而得到的一种新的P2P协议DDBG(Distributed De Brujin Graph)协议。该协议融合了De Brujin有向图和环的优点,使得结点的动态加入和离开过程更加方便,提高了网络的容错性和自由度,具有很高的可用性。其次从图论与系统拓扑相结合的角度,针对现有的结构化P2P系统和本论文构造的P2P系统,提出了一种基于图论的结构化P2P系统理论分析的通用框架,使图的性质与P2P系统的性能更加合理地联系在一起,为以后构造结构化P2P系统提供了有利的理论指导。本文共分为五章.第一章简要介绍了P2P网络、P2P网络的发展及现状,P2P网络的核心机制与增强机制,及论文的研究内容等。第二章研究了图论中基本概念,特别是线图技术与分布式线图技术,详细研究了De Brujin有向图及对De Brujin有向图的改进。第三章构造了一种新的P2P覆盖网络协议DDBG-基于De Brujin图构造的分布式De BrujinP2P协议。第四章基于对所构造的网络协议DDBG的理论分析,提出了一种基于图论的结构化P2P系统理论分析的通用框架。第五章总结全文,并提出了下一步要解决的问题。