（计算机系统结构专业论文）网络文件存储和共享系统的资源搜索研究和实现.pdf

摘要 计算机网络的迅速发展，使i n t e m e t 上汇集了成千上万的计算资源、数据资源，人们希望利用对 等计算技术把物理互连的网络设各的计算能力、存储能力以及网络带宽等聚集起来，以实现资源共 享、协同工作和联合计算。p 2 p 网络使节点以更自由、更主动的方式加入和离开网络。共享信息资 源。如何方便快捷地定位、检索这些资源，从而合理有效的利用它们，成为人们所关注的焦点问题。 本论文主要研究和分析了p 2 p 网络的路由机制和资源搜索技术。在首先介绍了p 2 p 网络的基本 概念、体系结构和具体应用后，重点研究和分析了p 2 p 网络路由算法。通过对现有的几种p 2 p 网络 的路由搜索模型的分析和比较，着重介绍了基于分布式哈希表的路由机制。由于分布式哈希路由算 法只能提供精确的资源定位，不能满足人们灵活的查找需求，因此本论文也讨论了一种便于扩展， 灵活的多关键字资源搜索与信息服务技术，提出类似分布式数据库的过滤器连接算法，并采用增量 式查找算法减少查询延迟及带宽消耗，利用缓存策略加速查询，以期为大规模的p 2 p 网络提供高性 能的资源搜索与数据访问服务。 在对相关理论分析和研究的基础上，本论文采用了广泛应用的j x t a 平台设计协议底层通信机制， 设计和开发了基于分布式哈希路由机制下的资源搜索与数据访问系统。通过对节点之间的通信消息 报文格式的设计，完成节点之间的相互协同搜索。最后论文对未来的工作做了总结和相关的展望。 关键字：p 2 p分布式哈希表 过滤器增量式查找 a b s t r a c t m i l l i o n so fc o m p u t i n gr e s o u r c e s 、d a t ar e s o u r c e sh a v ec o n v e r g e di ni n t e m e ta sc o m p u t e rn e t w o r k d e v e l o p sq u i c k l y p e o p l eh o p et h a tc o m p u t i n gc a p a c i t i e sa n dm e m o r yc a p a c i t i e so ft h ei n t e r c o n n e c t i n g n e t w o r kd e v i c e sa g g r e g a t et o g e t h e rt or e a l i z et h er e s o u r c es h a r i n g 、c o o p e r a t i v ew o r ka n d j o i n tc o m p u t i n g b yp e e r - t o p e e rt e c h n o l o g y i np e e r - t o p e e rn e t w o r kn o d e sc a nj o i na n dl e a v ef r e e l ya n da c t i v e l y i ti sa f o c u si s s u ch o wt ol o c a t eo rl o o k u pt h er e s o u r c e ss ot h a tw ec a nm a k eu s eo f t l l e m t h ep a p e ro u t l i n e sar e s e a r c ha b o u tt h er o u t i n gm e c h a n i s ma n dr e s o u r g e sq u e r yf a c i l i t i e so np 2 p n e t w o r k a f t e rd e s c r i b i n gt h eb a s i cc o n c e p t s 、a r c h i t e c t u r e 、a p p l i c a t i o na l e a sa n dk e y p r o b l e m so f p 2 p t e c h n o l o g y , t h ep a p e re m p h a s i z e s o nt h ea n a l y s i so f t h er o u t i n gm e c h a n i s mo f p 2 et oc l a d f yc o m p a r i s o n s w i t hc u r r e n tp 2 p r o u t i n gm o d e l s ，t h ep a p e rf o c u s o nt h er o u t i n gm e t h o d sb a s e do nd i s t r i b u t e dh a s ht a b l e ( d h d ，b e c a u s ed h tm e t h o d s j u s tp r o v i d e e x a c t - m a t c h q u e r yf a c i t i t y ，n o ts a r i s f y i n gt h e f l e x i b l eq u e r y r e q u i r e m e n t s ，t h ep a p e r a l s od i s c u s s e sas c a l a b l e ，f l e x i b l em u l t i - k e y w o r dr e s o u r c el o c a t e dt e c h n o l o g y t h e p a p e rp r o p o s e s t h ef i l t e r i n gc o n j u n c t i v eo p e r a t i o ns c h e m es i m i l a rw i t hd i s t r i b u t e dd a t a b a s e i t a l s oi n c l u d e sa ni n c r c m e n t a ls e a r c ho v e rt h ep e e r st od e c r e a s et h eq u e r yl a t e n c ya n db a n d w i d t h c o n s u m e d ，l a s t l yw ei n v e s t i g a t e t h ep o p u l a r i t yo f u s e rs e a r c hb e h a v i o r sa n d p r o v i d e t h ec a c h e s t r a t e g yt or e d u c e 山eo v e r h e a da s s o c i a t e dw i t ho p e r a t i o n ss p r e a da c r o s st h ew i d e a r e at op r o v i d et h e e 艏c i e n tr e s o u r c eq u e r ya n da c c e s si ns c a l a b l ep 2 ps y s t e m a c c o r d i n g t ot h er e l a t e dt h e o r yr e s e a r c h e sa n da n a l y s e s ，t h ep a p e ra d o p t sc o m m u n i c a t i o nm e t h o d so f j x t a p l a t f o r mw i d e l yu s e da n di m p l e m e n t s t h eo v e r m ld e s i g n so ft h er o u t i n gm e c h a n i s mb a s e do nd h z b y t h ec o m m u n i c a t i o nm e s s a g ef o r m a td e s i g n s ，t h es y s t e mr e a l i z e st h ec o o p e r a t i v es e a r c h e sa m o n gn o d e s a tl a s tt h ep a p e rd i s c u s s e st h ec o n c l u s i o na n df u t u r ew e r k k e y w o r d s ：p e e r - t o p e e l d i s t r i b u t e dh a s ht a b l e 。f i l t e r , i n c r e m e n t a ls e a r c h i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 研究生签名：墨三途 日期：型盘壹：! ! 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研 究生院办理。 研究生签名：圣墨盗导师签名：。垒! ! 垫i 日期：之! 竖至：i j j ) j 堕查兰堡主堡壅 筮= 兰塑童 1 1 论文背景 第一章前言 随着网络技术的飞速发展与迅速普及，i n t e m e t 已经逐渐深入到人们的日常生活中。基于t c p f l p 协议的网络通信体系结构开放性特征，使网络的规模越来越大，连入网络中的设备、计算单元的数 量和种类也越来越多，信息资源的获取和发布也变得非常方便和快捷。基于计算机网络的各种应用 通过对信息资源的采集、存储、传输、处理和利用，在全球范围内把人类社会更紧密地联系起来， 并以不可抗拒之势影响和冲击着人类社会的各个方面。 网络上的信息资源呈爆炸性增长趋势，如何方便快捷地存储、定位、检索和传输这些资源，从 而合理有效的利用它们，成为人们所关注的焦点问题。当前普遍的文件服务器模型，如某个n d 服务 器或者s a m b a 服务器，在一定程度上满足了人们对存贮和资源共享服务的需求。它们大都采用客户 机朋务器( c l i e n t s e r v e r ) 模式，客户机通过i m e m e v i n t r a n e t 与服务器互连，整个网络依赖于中心节点 来提供服务。这样用户所能得到的存贮、共享性能往往在一定网络范围内，对一定数量的分布文件 进行访问，如校园网等，无法满足规模化发展的需要。客户机朋务器模式实质上是一种集中式体系 结构，它在海量信息的组织、访问等方面存在着服务瓶颈、易于崩溃等缺点 7 ，1 0 ，1 8 1 。 随着网络技术的飞速发展与互联网在社会生活各个领域的广泛应用和迅速普及，现有的c s 模 式已经难以满足和支持大规模的网络应用，全面的分布式计算成为一种商业需求。i n t e m e t 应用的新 趋势是服务器与客户机的概念逐渐消失，取而代之的是“网络就是计算机”，即将整个因特网的各种 自治资源和系统组合起来，以实现资源共享。p 2 p ( p e e r - t o p e e r ) 计算模型 4 ，7 ，1 0 ，1 2 正是在资 源规模不断增多的情况下，用于解决海量信息资源的合理利用问题而提出的分布式计算模型。在这 种模式下，服务器与客户机的界限消失了，网络应用的核心从服务器向网络终端设备边缘化，无需 依赖集中式服务器。成员之间主动协作，直接从其他成员而不是从服务器的参与中获益。由于数据 存储、处理能力和网络带宽等都以一种完全分散、异步的方式运行，各种负载可以得到合理的均移 和平衡，有效的解决了资源服务的瓶颈问题，并易于扩展。 1 2 论文研究目标 p 2 p 网络中既没有身份固定不变的客户机，也没有身份永久固定的服务器，网络中每个实体都 是主动参与者，都可以给网络贡献一定的资源。随着越来越多的对等实体加入网络，网络提供的资 源和功能会更加丰富，性能也就越来越强。如何以少量的数据查询开销，保证用户定位到感兴趣的 资源对象成为p 2 p 网络在性能、可收缩性等方面的巨大挑战。 本论文针对p 2 p 网络的特点。根据当前国内外研究的现状，设计和开发一个便于扩展、灵活的 多关键字资源搜索与信息服务系统，该系统的目标是为大规模的p 2 p 网络提供高性能的资源搜索与 数据访问。系统涉及到p 2 p 网络的体系结构和路由算法等内容，在实现过程中将做一定的理论研究 和分析。 1 3 论文章节安排 本论文大致可分为三部分：第一部分包括第一章至第三章，内容为p 2 p 网络综述及p 2 p 网络 路由算法的理论研究；第二部分包含第四章至第六章，提出一个灵活的p 2 p 网络资源搜索定位模型， 并介绍了系统总体设计和原型实现；第三部分包括第七章，是论文总结及未来相关展望。 第一章前言：主要讲述论文的研究背景以及研究目标和主要内容。 东南大学硕士论文第一章前言 第二章p 2 p 网络综述；首先阐述p 2 p 网络的基本概念着重介绍了p 2 p 网络的应用领域、体 系结构和相关研究热点。 第三章p 2 p 网络的路由定位算法研究：首先提出了p 2 p 网络路由算法面临的问题，通过对现 有p 2 p 网络路由算法的简单分类，对它们的相关研究内容做了详细描述，同时分析了它们的优缺点。 第四章p 2 p 网络资源搜索定位模型：根据当前搜索技术的发展，对基于分布式哈希表的p 2 p 网络面临的问题进行了分析，由此提出了一个灵活的资源搜索定位模型，并指出相应的应用。 第五章资源搜索系统的总体设计：主要描述了分布式资源搜索模型的层次结构和相关实现技 术。 第六章原型系统的实现：介绍系统中功能模块和实现方法。 第七章论文总结和相关展望：对论文进行总结性的叙述，并探讨了同p 2 p 网络技术相关的研 究领域和未来工作展望。 最后是致谢、参考文献和论文发表情况。 2 查里查兰堡主丝壅 塑三童丝呈塑竺签堕 2 1p 2 p 网络的概念 第二章p 2 p 网络综述 p 2 p 称为对等网或点对点技术，是在i n t e m e t 上实施网络计算的一种新的计算模型。在这种网络 中所有的节点是对等的( 称为对等节点) ，各节点具有相同的责任与能力并协同完成任务。对等节点 之间通过直接互连，共享信息资源、处理器资源、存储资源甚至高速缓存资源等，无需依赖集中式 服务器就可完成。 从技术角度来说，p 2 p 并不是新的技末，而是一种新的应用技术模式。t c p h p 是i m e m e t 整体 架构的基础，它的最初设计就是提供固定节点间的点对点通信，并不存在客户机和服务器的概念。 发送方指定接收方的i p 地址，i p 层将数据报文投递到指定i p 地址的固定节点。这种简单的点对点 通信模型后来随着网络的发展逐步被c s 模式替代。c s 模式形成互联网上的集中，信息资源向同 一方向集中，这样的模式符合一对多、强对弱的社会形式，满足了计算机网络的发展需求。但是随 着计算机网络的发展，越来越多的资源加入到系统中。大量资源集聚在少数服务器节点上，使服务 器的负载越来越重，难以向客户提供快捷的服务，从而形成系统的瓶颈。 p 2 p 模式与客户机服务器的模式明显不同，c s 模式中服务器是网络的控制核心，而p 2 p 模 式的节点则具有很高的自治性和随意性。每个对等节点都是一个活动的参与者，都向网络贡献一定 的资源。p 2 p 技术把网络计算模式从集中式引向分布式，网络应用的核心从服务器向网络边缘设备 扩散，有效地解决了负载平衡和单点失效问题。同时节点的资源总和构成了整个网络的资源，使闲 置资源得到高效的利用，形成具有海量存储能力和巨大计算处理能力的超级计算机，解决了i n t e r n e t 上节点之间不能共享异构资源，不能聚集分散计算能力而造成的资源“孤岛”问题【9 。 2 2p 2 p 技术的应用领域 p 2 p 技术使网络计算模式从集中式向分布式偏移，网络应用的核心不再以服务器为主t 而是向 边缘设各扩散，对等节点之间可以方便的建立连接，使网络上的应用达到了更高的层次。目前p 2 p 计算技术主要应用领域包括：信息资源存储与共享、分布式计算、协同工作、实时通信技术。 2 2 1 信息资源存储与共享 信息资源存储与共享一直是网络技术发展的重要推动力，也是p 2 p 技术最典型的应用。由于网 络资源的急剧增长，大量信息的处理和传输对信息存储系统提出了新的要求，人们开始将传统的分 布式操作系统、局域存储技术向基于i n t e m e t 的文件存储系统发展。利用基于分布式计算的p 2 p 技 术，可以方便地组织和存储信息资源，对等节点通过不同的查询机制定位含有所需资源的对等节点 后，直接与其建立连接，并下载所需要的信息资源。采用这种方式来共享信息资源可以为用户提供 透明的存储访问，充分利用网络中的带宽资源，提高资源访问的健壮性。目前有很多研究项目都是 针对p 2 p 的文件存储共享，如g n u t e l l a 【2 】、f r e e n e t 3 和o c e a n s t o r e 4 等 2 2 2 分布式计算 分布式计算是伴随着互联网而迅速发展起来的针对复杂网络应用的新型计算模式。由于单一计 算单元的计算能力总是有限的，因此可借助于分布式技术将多个计算单元节点联合起来共同完成大 规模的计算任务。同时人们期望能够充分利用网络中的闲散计算单元，使网络中所蕴含的海量计算 能力得到更加充分的利用。p 2 p 计算技术为分布式计算的发展提供了新的机遇。 东南大学硕士论文 第二章p 2 p 网络综述 分布式计算可以完成大规模的网络应用，如交互式远程教育、科研、数字化图书馆、虚拟实验 室等，参与计算的计算机之间可以直接共享计算中的中间结果。通过整合网络上的各种高性能计算 机、服务器、工作站等，为企业提供动态变化的、智能的、协作式的信息服务。s e t i h o m e 【5 】是目 前基于p 2 p 的分布式计算的典型代表。 2 2 3 协同工作 协同工作是指多个用户之间利用网络中的计算机支持环境互相协同，共同完成计算任务，共享 信息资源等。计算机支持的协同工作( c o m p u t e r - s u p p o r t e dc o o p e r a t i v ew o r k ) 是当前典型的研究方 向之一。在现代的信息社会中，人的生活方式和劳动方式具有群体性、交互性、分布性和协作性等 特点，协同系统为企业规范管理、提高效率、降低成本起着不可替代的作用。 传统的协同应用平台大多采取客户机朋旺务器模式来完成员工之间、企业和合作伙伴之间的协同 工作，但这种模式不适合大规模协作和经济发展的全球化趋势。基于分布式技术的p 2 p 解决方案提 供了高度的可伸缩性、可靠性、可管理性和灵活性，有效地克服了客户机服务器模式的弊端。通过 采用p 2 p 计算技术个人和组织可以随时采用各种方式建立在线、非在线的协同应用环境，多个应 用服务器分布性特征也避免了单点失效问题，提高了可靠性。g r o o v e 6 是基于i n t e m e t 的p 2 p 协同 应用软件的典型代表，其用户可以直接进行实时的协同工作。 2 2 4 实时通信技术 实时通信技术是p 2 p 网络的重要应用之一，并吸引了数以万计的在线用户。i c q 、o i c q 、m s n 等是典型的实时通信系统。p 2 p 的实时通信技术完全是点对点进行，不依赖服务器的性能和网络带 宽。尽管仍使用一个中心服务器，但中心服务器仅是用来控制用户认证等基本信息，帮助完成节点 之间的初始互联工作。 2 3p 2 p 网络的体系结构 p 2 p 网络是种o v e r l a y n e t w o r k 。即在原有的网络基础设施之上，覆盖上另一层更抽象的网络， 使不同的网络都互联，以实现资源共享。覆盖网络能做到相对独立于某一个具体网络技术，无须改 变现有的网络结构。加入到覆盖网络的节点，可以更加精确地控制下层网络数据的路径。通过可增 加的配置性和适应性，一个覆盖网络比下层的网络设施更加健壮。显然p 2 p 网络的这种特性为i n t e m e t 上的文件存储和共享技术带来了极大的便利。 ip 2 p 应用协议i lp 2 p 通信协议i1p 2 p 服务协议| | p 2 p 控制报文协议l l。-_。_-_。_。一 lp 2 p 的核心协议i i t c p i p 协议栈 li 非t c p i p 协议栈 l 图2 - 1p 2 p 网络体系结构 p 2 p 系统独立于具体的物理网络设备以及物理拓扑结构，其协议可采用类似t c p i p 协议结构， 独立于传输层之上，以便应用在不同的环境下。各层之间通过消息进行信息交换。p 2 p 网络通信协 4 东南大学硕士论文 第二章p 2 p 网络综述 议基本功能包括：对等节点的核心协议、对等节点之间的通信协议、对等节点之间的服务协议、对 等节点之间的控制报文协议、p 2 p 网络上的应用层协议等，见图2 - 1 。 2 3 1 对等节点核心协议 为p 2 p 对等节点提供建立和处理节点之间通信的功能函数，如制定通信模式、通信类型、通信 信息参数、通信报文格式等。 通信模式包括通告模式和应答模式，通告模式是节点在没有收到任何请求而主动通告的通信方 式，如节点离开时采用通告模式。应答模式是节点之间的请求和响应的通信方式，如节点加入时即 采用应答模式。通信类型包括单播和多播类型，取决于不同的应用程序。通信信息参数包括通信双 方的源和目的地址等。通信报文格式包括路由信息格式、资源信息格式等，它封装上层的协议报文， 提供给下层协议。 2 3 2 对等节点之间的通信协议 为通信双方提供通信函数。包括p 2 p 对等点的会话函数，对等点之间的资源信息交换函数等。 p 2 p 对等点的会话包括r e q u e s t r e s p o n s e 函数以及r e l e a s e 函数。当对等点初始化连接时，发出 r e q u e s t 报文，另一个对等点响应r e s p o n s e 报文。而对等点释放连接时，发出r e l e a s e 报文。对等点 之间的资源信息交换函数包括资源通告函数以及资源请求和应答函数等。 2 3 3 对等节点之间的服务协议 它是控制节点为普通p 2 p 节点提供的基本服务协议，包括引导节点的发现协议、报文路由协议、 网络的故障恢复协议、节点标识的解析函数等。 引导节点发现协议指新加入的对等节点至少找到系统中的一个节点作为其引导节点( b o o t s t r a p n o d e ) ，并向这个节点发出一个加入请求消息，引导节点进行响应。由于每个节点只与一部分节点保 持邻接，节点之间的通信是依靠邻接关系采用消息转发的方式进行的。报文路由协议则定义了路由 报文信息在应用层上的转发策略。 由于在p 2 p 系统中任意节点都是不确定的，对等节点可以随时离开也可能随时出错而不可访问 使系统分成互不可达的若干部分，所以网络的故障恢复协议实现发现和恢复异常功能，提供良好的 恢复策略使系统从错误中恢复来。 节点标识的解析函数实现节点标识与物理地址的转换。 2 3 4 对等节点之间的控制报文协议 对等点在通信过程中可能会出现对等节点会话时阔超时、转发报文错误等，协议可提供一定的 诊断函数以便检测。 2 3 5p 2 p 应用协议 依赖具体的应用，可以被开发者进行扩展。 2 4p 2 p 网络研究热点 p 2 p 计算技术可以归结为一种特殊的分布式计算技术，从而p 2 p 计算技术也面临着分布式计算 技术共有的很多问题，如并发控制、事务处理等基本的分布式系统问题。同时在p 2 p 系统中也有其 自身的技术需求。 东南大学硕士论文 第二章p 2 p 网络综述 2 4 1 路由机制和资源定位的研究 与分布式计算相似，路由机制和资源定位也是p 2 p 技术主要问题之一。p 2 p 系统一般要构造一 个非集中式的分布式结构，在路由过程中解决大量节点命名、组织以及加入、离开方式、出错恢复 等问题。但是在一个缺少集中化服务器的动态环境下，各个节点很难能够维持一致的网络拓扑信息。 同时频繁的节点加入和离开，使传统路由扩散的方法难以解决这些问题。本文将在第三章重点讨论 p 2 p 的路由算法。 p 2 p 网络中大量的信息资源、存储资源、计算资源分布在各个独立的节点上，如何高效地索引、 查找、定位以及访问这些资源是另一个需要关注的重要问题。资源的索引信息应存放在系统中的每 一个节点上而不是存储在中心服务器上，在数据的访问过程中则期望能够采用流水、并行或者选择 优化的路由路径来加快数据的访问速度。 2 4 2 异构网络环境的互操作性和扩展性 p 2 p 网络连接了各种自治资源和系统，它需要考虑如何屏蔽操作系统、网络协议的异构性和复 杂性，使分布在网络上的不同机器能够相互传递消息协同工作。 p 2 p 网络形成初期的计算规模较小，随着大量计算单元的不断加入，系统的资源规模也随之扩 大。需要考虑在资源规模不断扩大、应用不断增长的情况下系统的可扩展性，以不降低网络的整体 性能。 2 4 3p 2 p 网络管理 p 2 p 技术弱化了集中服务器的功能，重视网络中所有个体的作用，强调的是个体之间、系统之 间、计算机之间，不需要服务中介的直接通信和联系，进行收发信息、共享资源等。每一个参与者 既是客户机又是服务方，这使人们在i n t c m e t 上的共享行为被提升到了一个更广泛的层次，以更主动、 更自由的方式参与到网络中去。 用户可以依据自己的兴趣爱好等个人因素，与p 2 p 网络中符合自己要求的用户组建一个逻辑上 的p 2 p 组。这种逻辑上独立的p 2 p 组可以是临时的，也可能是长期的，其成员却是动态变化的。p 2 p 网络和p 2 p 组虽然均为逻辑组织，但又具有现实世界的许多特征，如个人情感、社会道德、政治信 仰，甚至还要受法律的约束。 对匿名性进行支持是很多p 2 p 系统所要考虑的一个重要功能。p 2 p 网络需要对系统中信息资源 的操作者的操作行为的隐私进行保护，如信息提供者、信息检索者、信息所在服务器a 这些特点都 决定了p 2 p 网络环境的管理是个及其复杂的问题。 2 4 4p 2 p 网络的安全问题 安全问题是一直伴随着互联网发展的重要问题。安全问题包括很多相关的问题，比如应该防止 他人控制整个系统，增加恶意信息等，同时应能够保证系统中信息资源的正确性。在p 2 p 系统中系 统安全同样面临着巨大的挑战。由于在p 2 p 网络中对等点的存储资源需要被其他节点访问，对等节 点用户安全意识的缺乏以及p 2 p 协议和p c 操作系统的安全漏洞，使得节点很容易受到黑客攻击， 共享的资源被修改甚至文件被病毒感染。同时恶意的消息重发和虚假消息应答造成大量的垃圾消息， 急剧增加p 2 p 网络的负担，甚至造成网络拥塞。p 2 p 系统需要在没有中心节点的情况下，提供身份 的认证、授权以及数据信息的安全存储、数字签名、加密、安全传输等工具，同时p 2 p 系统要有能 力抵抗过量存储负载、拒绝服务攻击等行为。p 2 p 中的安全问题直接决定了p 2 p 能否被大规模进行 商用，因此安全因素是优先需要解决的问题a 6 至壹查堂雯主望塞 蔓三主：垦! 塑垒堕宴塞垡兰堕里塞 3 1 引言 第三章、p 2 p 网络路由定位算法研究 基于t c p i p 协议的i n t e m e t 己逐步发展成为当今世界上规模最大、拥有用户和资源最多的一个 超大型计算机网络。在这个网络里，各个节点通过路由设备互连，这些路由设备根据i p 分组中的目 的地址转发收到的数据包，以确定传送的外出路线。基于i p 层的路由算法形式多样，得到广泛应用 的有两种：距离矢量路由算法和链路状态路由算法。目前大多数路由协议都是基于这两种路由算法 之- 1 l 】。 距离矢量路由算法是让每个路由器维护一张路由表，表中列出了该路由器与其他所有可达目的 节点之间的链路距离。各个路由器定期地向其他路由器广播报文，然后根据反馈回来的确认信息更 新路由表。路由器根据与其他主机的链路距离信息，可以计算出与其他主机通信时，在距离最短的 条件下，数据包“下一跳”的目的地应是自己的哪一个邻居。这样数据包就可以经过中间路由器，以 最短的距离从发送端传送到接收端。距离矢量路由算法理论上是有效的，但在实际工作中却有很大 的缺陷：它以波动的方式计算路由，收敛速度极慢，而且在计算过程中，网络处于一种过渡状态， 极可能发生循环并造成暂时的拥塞。距离矢量路由算法协议的这种特性不仅造成了网络收敛的延时， 而且消耗了带宽。 链路状态路由算法有时也称为最短路径优先算法( s h o r t e s tp a t hf i r s t ) 。与距离矢量路由算法不 同的是，这种算法通过节点之间的信息交换，来获得网络的拓扑结构数据。各路由器收集与发送信 息链路状态数据报文，测量到它各相邻节点的延迟或开销。所有路由器根据收集到的信息建立完整 的拓扑结构信息，利用d i j k s t r a 算法计算到其它路由器的最短路径并更新路由表。由于链路状态算 法要求各路由器的网络拓扑结构数据库相互一致，因此当链路状态发生变化时，最先检测到这一变 化的路由器需要将变化的情况发送给其他的路由器。链路状态路由算法采用扩散方式发送报文，这 会占用大量的带宽。同时链路状态路由协议使用的算法比较复杂，对路由器的c p u 和内存要求很高， 在一些低档路由器上运行困难。 距离矢量路由算法和链路状态路由算法都是基于局部最优的思想：每个路由器为所处理的数据 报文尽可能地选择某种距离测度下的最优路由。这种测度的选择都是基于准确的查询结果之上的， 它不适合网络拓扑结构动态变化的环境。 3 2 p 2 p 网络应用层路由面临的问题 p 2 p 网络是基于网络基础设施之上的一个逻辑层，其特性为路由算法的设计提出了新的问题和 挑战，主要有以下几点： 1 动态变化的网络拓扑结构 动态变化的网络拓扑结构是p 2 p 网络的一个显著特点。p 2 p 网络的精髓是给予用户极大的自 由。它弱化了集中服务器的功能，重视网络中所有个体的作用，每个对等点随时都可以进入或退 出网络，它们仅仅关注于自己的行为。在它们短暂的活动期间，尝试完成自己的任务，任务一旦 完成，它们可能就会退出。p 2 p 网络的自组织特+ l 生( a d - h o e ) 使得很难预测和定位网络中的节点资源， 传统的i p 层路由算法已经不适合p 2 p 路由的要求。 2 按需要求的特性 文件共享系统的需求直接引发了p 2 p 网络技术热潮，同时也成为p 2 p 系统中最主要的应用之 一。p 2 p 技术的文件共享系统是基于内容寻址的方式 1 0 】，用户只有在需要的时候系统才进行路 由，很少考虑网络带宽、系统负载和历史查询记录。大多数的传统i p 层路由网络中的主机是通 东南大学硕士论文第三章、p 2 p 网络路由定位算法研究 过周期性交互路由信息，得到所有其它主机的路由。但彼此交换的路由信息可能并不需要，这些 无用信息浪费了网络资源。 3 无集中控制的系统 对等节点之闻作为对等实体连接，而不借助于任何已经建立的网络基础设施或集中管理。这 样的系统结构把网络的控制功能分散配置到各个对等节点中，网络的建立和调整是通过各个节点 的有机配合实现的，这使路由选择已经从本质上脱离了传统网络的集中控制机制。 4 应用层上的路由 无论是i n t e m e t 早期的简单五类地址分类，还是为了降低路由表规模增长速度的无类域间路 由( c l a s s l e s si n t e r - d o m a i nr o u t i n g ) 地址结构以及i p v 6 地址，从本质上讲，整个i p 地址空间仍然是 一种层次结构，节点利用最长地址的前缀匹配算法进行路由查找。但p 2 p 网络的路由是基于应用 层之上，并不一定采用类似i p 地址的层次结构路由。一般情况下，p 2 p 网络利用自己的节点标识 策略实现系统的路由，如t a p e s t r y 1 9 ，c h o r d 2 2 。 5 双向链路传输方式 p 2 p 网络中每个节点既是客户机，同时又是服务器，系统的流量表现为双向传输特性，与诸 如w e b 服务之类的现有应用不同，这些应用的特点是下行数据传输量远远大于上行数据传输量。 t c p 传输协议利用确认报文进行数据的差错恢复，研究表明在双向传输情况下会产生确认报文丢 失，从而引起系统吞吐量降低1 3 1 ，因此在路由设计过程中必须考虑路由控制信息报文的数量， 避免带宽浪费和性能下降。 综上所述，良好的p 2 p 网络路由算法需要满足以下基本要求：不依赖集中控制的分布式实现， 避免过量的通信报文；每个节点均与一定数量的节点保持邻接关系；节点之间通过多个节点传递 消息来完成通信；任何两个节点的消息通信的路由跳数( h o p ) ，尽量维持在一个较小的数量级：一 定数量节点的失效不会影响系统可用性：各个节点应能够维持一致的网络拓扑信息；节点可以很 容易( 传递消息的数量少) 地加入和离开系统，并满足一定的可扩展性；网络在分割后能提供良 好的恢复策略使系统从错误中恢复来提高系统的健壮性：综上所述，p 2 p 网络路由算法应该考虑 节点的命名、定位、加入、离开咀及节点之间的邻接关系、系统容错性等。 3 3 p 2 p 网络路由算法的分类 鉴于p 2 p 网络路由的上述要求，设计一个合适的路由算法具有一定的挑战性，很多研究组织 和机构参与其中的研究，并提出和实现了很多不同的算法。按照层次结构可把它们分为四类：中 心式控制、全分布式控制、分层中心式控制和分层分布式控制4 种基本模式a 这些模式具有各自 不同的特点，以下进行详细说明。 3 3 1 中心式控制模式 中心式控制模式又称为混合模式的p 2 p 网络该模式采用一个核心实体( 或者称为集中服务器) 专门提供服务，而不向其它节点提出请求。对等节点通过核心实体来定位通信方的信息，但核心实 体并不参与对等节点之间的实际通信。见图3 - 1 。 图3 1 、中心式p 2 p 网络 图3 2 、全分布的p 2 p 网络 8 东南态学硕士论文第三章、p 2 p 网络路由定位算法研究 显然这种模式依赖于中心服务器，服务器成为系统的一个主要瓶颈，所有的请求都要服务器来 回答，这不符合p 2 p 最初的设想。但中心式控制模式中控制节点可进行路由优化和系统管理，使系 统具有较好的可维护性和安全性。 3 3 2 全分布控制模式 全分布控制模式下的p 2 p 网络实际上又称为纯p 2 p 网络。纯p 2 p 网络是指所有参与的计算机都 是对等的，各对等节点之间直接通信，自始至终完全没有中心服务器对对等节点间的信息交换进行 控制、协调或处理，网络中的任意一个节点离开时，都不会对整个网络的服务产生影响 1 2 1 。见图 3 2 。 完全分布式控制结构网络的基本特点是网络所有节点在网络控制和流量管理上是平等的，各节 点要监测系统的连通性，进行拥塞、流量和路由信息的控制，因此网络的抗毁能力强，设备的成本 也比较低。这种p 2 p 网络存在的问题是网络的通信流量会随着用户的增多而迅速增加，使得网络负 载增加，而且网络全局拓扑结构是不完全的，因此它主要适用于小型网络的控制和管理。但是这种 结构的优点也是非常明显的，任何节点的离开或者故障不会对系统的性能产生致命的影响，同时没 有节点会成为查询的瓶颈。 3 3 3 分层中心式控制模式 分层中心式控制模式实际上是一种树形拓扑结构。网络被划分为若干群( c l u s t e r ) ，每个群由一 个群首( c l u s t e r h e a d e r ) 和多个群成员( c l u s t e r m e m b e r ) 组成。这些群首形成了高一级的网络，在高一 级网络中，又可以分群，形成更高一级的网络，直至最高级。分层中心式控制的设计思想是集中管 理、区域控制。如图3 - 3 。 它将复杂的网络系统结构分解为若干个子区域，每个子区域部分能相对独立工作，又能保证全 系统协调一致。分层中心式结构可以在树的任意区域上增加信息资源，易于扩展，但是群首的选择 以及节点的动态性仍会带来信息资源管理的复杂性。分层中心式结构比起集中式系统具有较好的容 错能力，但是根节点仍然是系统中的单点瓶颈所在，其安全策略也比集中式系统难以实现。由于系 统具有大量节点，有时很难检测出那个节点发生错误。节点依赖性也太大，如果系统中的一个高层 节点出现问题，那么它的子节点都会受到影响。同样当一个节点把消息传送给树的根节点的时候， 中问节点很可能会篡改信息的内容。 图3 3 、分层中心式p 2 p 网络 图3 - 4 、分层分布式p 2 p 网络 9 丕曼奎兰堡圭堡奎 苎三童：望! 里塑塑旦塞垡兰鎏堕塞 3 3 4 分层分布式控制模式 分层分布式控制模式实际上是集中模式和分布式网络的结合。分层分布式网络通常是由若干节 点组成的几个群相互连接而构成的。每个群由若干节点组成，群内的某个节点被选作群首，不同群 之间通过网关传输控制或业务信息。每个节点至少属于个群，群内的各节点可作为群首、网关或 普通节点，这由网络控制算法所决定。群首负责监管所属群内的节点，完成网络的路由选择、流量 控制、优先级的分配和节点加入退出处理等。如图3 4 。 分层分布式控制模式吸取了全分布式和分层中心式的优点，网络的管理通过多个控制节点来协 调处理完成，拥有前面所述的优势。分层分布式控制模式是p 2 p 网络发展的趋势。 3 3 5 平面结构和分层结构的比较 在前面的分类中，前两种属于平面结构的网络，也是对等网络发展经历的第一代技术。平面结 构的网络比较适合规模较小的网络。无论是基于目录服务器还是基于泛洪的模式它们的最大缺点 都是网络规模受限，不适合网络规模化的发展。 分层结构的最大优点是可扩充性好，网络规模不受限制，必要时可以通过增加群的个数或级数 来提高网络的容量。其次，分层结构中群内成员的功能比较简单，群内节点无需知道其他群的拓扑 结构，这大大减少了网络中路由控制信息的数量。但分层结构中群首节点设计相对复杂一些，需要 维护或设计到达其它群首的路由，以及节点与群的所属关系。但总的来说，在相同网络规模条件下 路由开销要比平面结构的小。如果群内通信的信息量占较大比例时，各群组可以互不干扰地进行通 信，系统的吞吐量要高于平面结构设计。但是分级结构也有它的缺点，需要设计复杂的算法，如群 大小的选择以及动态环境下如何选举群首等。 3 4p 2 p 网络路由算法现状 在拓扑结构动态变化的p 2 p 环境下，固定i n t e m e t 网络设计的路由协议无法适应这种情况。像 r i p 和o s p f 这样的传统路由协议，要依靠定期广播来维护路由状态，当网络拓扑结构变化快速， 使协议无法及时收敛，就会在路由表中产生大量的不可靠路由和路由环路。为了加快收敛速度，只 能缩短广播周期，从而加大了路由负荷。大量的路由信息会占用宝贵的带宽资源，而且也无法保证 路由收敛。为了适应p 2 p 的需要，许多新的路由算法被提出来，如n a p s t e r 1 、g n u t e l l a 2 、c a p 7 、 j x t a 8 1 、c a n 1 8 、t a p e s 时【1 9 ，2 0 、c h o r d 2 2 等。根据3 2 节和3 3 节所述的路由算法研究的 基本需求以及分类原则，本节对它们分别介绍。 3 4 1n a p s t e r n a p s t e r 1 是p 2 p 网络技术的先驱，它对p 2 p 网络的发展起了巨大的推进作用。n a p s t e r 利用一 个类似于服务器的节点集中提供对等节点标识和资源索引信息。当节点加入网络时，首先向服务器 发送共享资源的信息列表，而服务器把它的i p 地址和端e l 号作为其在网络中的标识。当需要查找资 源时，p 2 p 网络中的用户通过登陆服务器，向集中索引服务器发出搜索请求，服务器返回资源所在 节点的地址信息。查询发起的对等节点收到应答后，p i n g 每一台拥有资源的节点，根据网络流量和 延迟信息进行选择，以便与合适的对等节点直接建立连接。如图3 - 5 所示。 在n a p s t e r 网络中，系统并不关心网络拓扑结构和节点离开行为，实际上也没有提供节点的逻辑 命名机制，仍然以i p 地址和端口作为节点的标识。显然n a p s t e r 属于中心式的控制模式。 l o 东南大学硕士论文 第三章、p 2 p 网络路由定位算法研究 搬中式h h 势绺 图3 - 5 、n a p s t e r 路由查找算法 3 4 2g n u t e l l a g n u t e l l a 2 络没有中央目录服务器，是全分布式的p 2 p 网络。初始状态下，通过访问某些节 点提供的g n u t e l l a 网络中的活动节点地址缓存列表，新加入的对等节点可以任选一个地址。一旦获 得该地址，新加入的节点就可以与该地址所代表的活动对等点建立t c p i p 连接，从而接入g n u t e l l a 网络。 一旦加入g n u t e l l a 网络，对等节点就可以直接和其它节点通信。g n u t e l l a 采用泛洪策略( f l o o d i n g ) 进行路由搜索。对等节点通过“扩散”方式向所有与之连接的节点发出p i n g 描述符，而接收到p i n g 描 述符的对等点或者响应一个p o n g 描述符，或者在不能满足请求时，将该请