（计算机软件与理论专业论文）基于p2p的异构即时通讯系统的研究与实现.pdf

j = ：) 毒7 7 三 餐 ”1 掌 “ ： + f “ 鼍 1j1、，j j?1l11j at h e s i si nc o m p u t e rs o f t w a r ea n dt h e o r y i 嘲y 1 帆8 洲4 眦m 1 叭9 帆0 l 8 眦 r e s e a r c ha n di m p l e m e n t a t i o no fap 2 pb a s e d h e t e r o g e n e o u si n s t a n tm e s s a g i n gs y s t e m b yc h e n x i n z h a o s u p e r v i s o r ：p r o f e s s o rg u i r a nc h a n g n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 r i 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 谢意。 学位论文作者签名： e l 期：洲 盘盖匀 弛屈何 1 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年口一年i一年半口两年口 导师繇弛 导师签名：锄饪澎 签字日期：硼目7 夕 他 过 隆 嚣一 一 嗍 槲 坏 靴 描 怖 黼 吼 方 其 皑 地 能 涮 的 获 嗾 谢 为 币罴 和 衣 涨 潮 荆 黼 标 包 澌 炯 碱 新 的 左 幺7 名 签 ， 者 l 作 ： 文期沦日位字学签 东北大学硕士学位论文摘要 基于p 2 p 的异构即时通讯系统的研究与实现 摘要 p 2 p 技术作为互联网领域的一项新兴技术，以其非中心化、可扩展性强、负载均衡 和健壮性等特点迅速成为计算机领域研究及应用的热点。当今的p 2 p 技术正以日新月异 的速度向前发展，财富杂志更将p 2 p 列为影响i n t e r a c t 未来的四项科技之一。在即时通 讯( m ) 领域，由于多家公司和组织都推出了自己富有特色的即时通讯平台，但由于商 业、协议兼容性等因素造成这些平台大多不能彼此通信，这给互联网用户的交流带来了 极大不便。本文所设计实现的基于p 2 p 的异构即时通讯系统就是为了解决该问题而提出 的，该系统的核心思想是在p 2 p 网络中快速定位一个中转节点用于异构通讯双方的消息 传输。 本文首先对包括p 2 p 拓扑结构、d h t 路由原理等关键技术进行了研究与分析，并 结合异构即时通讯需求提出了合理的解决方案，构造了系统原型，并对该系统中的网络 实体进行了结构分析和功能设计。在系统设计的核心部分，本文提出了一种适合该系统 应用需求的d h t 节点命名机制，并对传统的d h t 资源发现算法进行了扩展，然后基于 d h t 完全分布式结构化网络提出了一种高效的中转节点发现算法，并在此基础上设计 了中转服务资源在p 2 p 网络上的发布和定位算法。随后本文就异构通信的关键流程进行 了研究与设计，针对该系统应用修改了d h t 网络中节点的加入和退出算法并初步确定 了系统的管理和更新策略。 该系统原型采用了基于x m p p 开源协议的s i p c o m m u n i c a t o r 和o p e n c h o r d 平台， 并在此基础上实现了用于异构通信的关键模块。由于时间和实验条件所限，在实现部分 对系统进行了适当的简化。最后，通过系统关键模块和中转节点发现算法的测试，发现 本系统在充分保证命中率的同时可以兼顾网络的负载均衡，进而论证了该系统在因特网 上大规模部署的可行性。 关键词：p 2 p ；d h t ；c h o r d ；即时通讯系统；资源定位 一i i 一 ，；，j k；，；j，_二*劳￥0、 1 譬 0 1 t ； ：夕 u答o 东北大学硕士学位论文 a b s t r a c t r e s e a r c ha n di m p l e m e n t a t i o no fap 2 pb a s e dh e t e r o g e n e o u s i n s t a n tm e s s a g i n gs y s t e m a b s t r a c t p 2 pt e c h n o l o g y , a san e w l ye m e r g i n gt e c h n o l o g yo ni n t e r n e t , w i t hi t sf e a t u r e ss u c ha s d e c e n t r a l i z a t i o n ，h i g hs c a l a b i l i t y , l o a db a l a n c ea n dr o b u s t n e s s ，i sb e c o m i n gah o tt o p i co n i n t e r n e tr e s e a r c hr a p i d l y n o wi ti sd e v e l o p i n g 、加t he a c hp a s s i n gd a ya n di sc o n s i d e r e dt ob e o n eo ft h ef o u rm o s ti n f l u e n t i a lt e c h n o l o 西e so ni n t e r n e ti nt h ef u t u r e i nt h ei n s t a n tm e s s a g i n g ( i m ) f i e l d ，m a n yc o m p a n i e sa n do r g a n i z a t i o n sh a v el a u n c h e dt h e i ro w nd i s t i n c t i v ei n s t a n t m e s s a g i n gs y s t e m s ，b u tm o s to ft h e mc a n n o tc o m m u n i c a t ew i me a c ho t h e rf o rr e a s o n so f b u s i n e s s ，p r o t o c o lc o m p a t i b i l i t y , e t c ，w h i c hb r i n g s al o to fi n c o n v e n i e n c et ot h e i n t e r - c o m m u n i c a t i o nb e t w e e ni n t e r n e tu s e r s t h i st h e s i sp r e s e n t sah e t e r o g e n e o u si ms y s t e m t h a ta d d r e s s e st h ep r o b l e m t h ec o r ei d e ai st of a s tl o c a t eap r o x yn o d ef o rh e t e r o g e n e o u s m e s s a g et r a n s m i s s i o n i nt h i st h e s i s ，ah e t e r o g e n e o u si ms y s t e mp r o t o t y p ei sd e s i g n e da n dt h e nas p e c i f i c a n a l y s i si sm a d eo nt h es t r u c t u r ea n df u n c t i o n so fn e t w o r ke n t i t i e sw i mt h eh e l po fp r e v i o u s r e s e a r c ha n da n a l y s i so np 2 pt e c h n o l o g ya n dd h tr o u t i n gm e c h a n i s m an e wn a m i n g m e c h a n i s mi s d e v e l o p e dt om e e tt h ea p p l i c a t i o nr e q u i r e m e n t s t h es y s t e me x t e n d st h e t r a d i t i o n a ld h tr e s o u r c el o c a t i o na l g o r i t h ma n db r i n g su pah i g he f f i c i e n tp r o x yn o d e d i s c o v e r ya l g o r i t h mo nf u l l yd e c e n t r a l i z e ds t r u c t u r e dd h tn e t w o r k ，b a s e do nw h i c ht h e r e s o u r c el o c a t i o n a l g o r i t h ma n dt h ek e yp r o c e s s o fh e t e r o g e n e o u sc o m m u n i c a t i o na r e s p e c i f i e d n o d ej o i n i n ga n dq u i t t i n ga l g o r i t h ma sw e l la sa no r i g i n a ls y s t e mm a n a g e m e n ta n d u p d a t i n gs t r a t e g ya r ep r o p o s e di ns y s t e md e s i g n o p e ns o u c ep r o t o c o lx m p pb a s e ds i p - c o m m u n i c a t o ra n do p e n - c h o r da r eu s e da su p p e r i mi n t e r f a c ea n du n d e r l y i n gc h o r dp l a t f o r mr e s p e c t i v e l y , b a s e do nw h i c ht h ec o r es y s t e m m o d u l e sf o rh e t e r o g e n e o u sc o m m u n i c a t i o na r ei m p l e m e n t e d b e c a u s eo ft h el i m i t a t i o no f t i m ea n de x p e r i m e n te n v i r o n m e n t ，t h es y s t e mi ss i m p l i f i e dt os o m ee x t e n t r e s u l t sf r o m s i m u l a t i o n sa n dt e s t ss h o wt h a tt h eh e t e r o g e n e o u si ms y s t e mc a ng u a r a n t e et h eh i tr a t i oa n d t h el o a db a l a n c ea tt h es a m et i m e t h e s em e r i t st o g e t h e rw i t hi t sh i 。g hs t a b i l i t ym a k et h e s y s t e ma p p l i c a b l et ol a r g es c a l en e t w o r kd e p l o y m e n t k e y w o r d s ：p 2 p ；d h t ；c h o r d ；i ms y s t e m ；r e s o u r c el o c a t i o n i i i 一 j；i ，。譬；j 、，j，夕哼 蠢1。、。，。，- ，、 ， j ； 7 i i 9 东北大学硕士学位论文 目录 目录 独创性声明i 摘要 a b s t r a c t i i l 第l 章绪论l 1 1 研究背景。1 1 2 研究意义j 2 1 3 研究内容。2 1 4 本论文所完成工作。3 1 5 论文组织安排3 第2 章p 2 p 网络拓扑及算法分析5 2 1p 2 p 的定义j 5 2 2p 2 p 网络中的拓扑结构研究5 2 3 复杂p 2 p 网络拓扑模型7 2 3 1i n t e m e t 拓扑模型7 2 3 2s m a l lw b d d 网络8 2 4d h t 路由原理_ 9 2 5 主流d h t 协议介绍1 0 2 5 1 缓冲阵列路由协议。1 0 2 5 2 一致性哈希1 1 2 6 非结构化p 2 p 搜索算法1 3 2 6 1g n u t e l l a 洪泛1 4 2 6 2 迭代加深1 4 2 6 3 随机漫步：。1 4 2 6 4g n u t e l l a 2 1 4 2 7 对研究内容有重大影响的几个方面：1 5 2 7 1 度数和直径的折衷关系( t r a d e o f f ) 对发现算法的影响1 5 2 7 2s m a l lw | o d d 理论对p 2 p 发现技术的影响1 6 2 7 3 语义查询和d h t 的矛盾16 2 8p 2 p 发现技术研究的成果与不足1 7 2 9 j 、结1 7 一一 东北大学硕士学位论文目录 第3 章基于p 2 p 的异构即时通讯系统设计1 9 3 1 传统即时通讯实现原理分析1 9 3 1 1i m 技术原理和工作方式。1 9 3 1 2i m 通讯方式2 0 3 2 现有即时通讯协议接入p 2 p 网络可行性研究。2 l 3 3 主流d h t 网络和方案选取2 2 3 3 1 主流d h t 网络介绍。2 2 3 3 2c h o r d 简介2 3 3 4 基于p 2 p 的异构即时通讯系统原型设计2 4 3 5 系统中相关网络实体的结构和功能设计。2 6 3 6p 2 p 网络中即时通讯实体命名机制2 7 3 7p 2 p 网络中中转服务的发布和定位2 9 3 7 1 中转服务资源发布方式的选取2 9 3 7 2 中转服务资源在p 2 p 网络上的发布。3 2 3 7 3 中转服务资源在p 2 p 网络上的定位3 5 3 8 异构即时通讯平台互联关键流程研究与设计3 7 3 9 管理和更新策略3 9 3 9 1 系统全局变量更新策略3 9 3 9 2 节点的加入和离开4 0 3 1o 小结4 l 第4 章基于p 2 p 的异构即时通讯系统实现4 3 4 1 系统模块划分4 3 4 1 1 客户端模块划分4 3 4 1 2 中转节点模块划分4 4 4 2 各模块详细设计4 5 4 2 1 散列模块设计4 5 4 2 2 定位模块设计4 6 4 2 3 发布模块设计4 7 4 2 4 转发模块设计4 8 4 3 系统封装4 9 4 3 1o s g i 平台介绍4 9 4 3 2 封装具体实现5 1 4 4 ，j 、结51 第5 章系统测试与分析：5 3 一v 一 j 。 i ! j j ； ， 东北大学硕士学位论文目录 5 1 测试环境5 3 5 2 系统测试5 3 5 3 有关发布域的测试5 4 5 3 1 理论证明5 4 5 3 2 模拟测试5 6 5 4d 、结。5 8 第6 章总结与展望5 9 6 1 总结。5 9 6 2 未来展望6 0 参考文献。6 3 致谢6 7 一一 气 一；j 东北大学硕士学位论文目录 东北大学硕士学位论文第1 章绪论 1 1 研究背景 第1 章绪论 当代互联网上流行着很多即时通讯( 蹦：i n s t a n tm e s s a g i n g ) 软件，如m s n 、q q 、 i c q 、s k y p e 等，这些丰富的软件资源所提供的诸多富有特色的功能也使互联网上的用 户做出了不同的选择。然而，由于商业利益、协议兼容性或其他方面的原因，通常这些 软件客户端都不能与其他软件客户端互联互通，这给互联网用户之间的交流带来了极大 不便，也违背了即时通讯软件设计的初衷。 j a b b e r 是著名的l i n u x 即时通讯服务服务器，它是一个自由开源软件，能让用户自 己架即时通讯服务器，可以在i n t e m e t 上应用，也可以在局域网中应用【l 】。可扩展的消 息和出席信息协议x i p p l 2 1 ( t h ee x t e n s i b l em e s s a g i n ga n dp r e s e n c ep r o t o c 0 1 ) 作为从j a b b e r 开源社区发展起来并由因特网工程任务组( i e t f ：i n t e m e te n g i n e e r i n gt a s kf o r c e ) 标准 化的即时通讯协议，一直致力于即时通讯软件平台的融合。但可惜的是，现在已经实现 的多协议平台，如p s i 、m i r a n d ai m ，以及本文中使用的s i p c o m m u n i c a t o r 等，都仅仅 是实现了对特定即时通讯软件的替代，即在一个软件平台上安装不同即时通讯协议以达 到使用多账户登录的目的，即在该平台上可以同时实现m s n m s n 、i c q i c q 等交流。 但这种方式仅仅部分减少了对本地资源的占用，并没有解决异构即时通讯软件互联的问 题，例如：在没有i c q 账户的情况下，一个m s n 用户如何与i c q 用户交流的问题。 传统的即时通讯软件，如m s n 、q q 、i c q 等，都是基于客户服务器( c s ： c l i e n t s e r v e r ) 架构提出并实现的。基于c s 架构的即时通讯软件有其明显的优点，如 建立连接的时间短，易于读取好友在线状态，方便管理等。但由于商业和法律因素，这 些软件相互兼容的可能性很小，使所有这些带有商业性质的即时通讯软件兼容的可能性 更是趋近于零。 与此同时，对等网络技术，也称为p 2 p 【3 】( p e e r - t o p e e r ) 技术在近几年也得到迅速 发展。p 2 p 技术是一种基于对等计算模型和对等应用层重叠网络架构的技术，其中的参 与者共享他们所拥有的一部分软硬件资源( 处理能力、存储能力、网络连接能力) ，这 些共享资源需要向网络提供服务和内容，能被其他p e e r 直接访问而无需经过中间实体。 在此网络中的参与者既是资源( 服务和内容) 提供者，又是资源( 服务和内容) 获取者。 基于p 2 p 网络架构的应用在互联网上取得了飞速的发展，包括p 2 p 文件共享、p 2 p 东北大学硕士学位论文第1 章绪论 通信、p 2 p 计算、p 2 p 音频视频服务等。常见的p 2 p 应用系统有k a z a a 4 1 、s k y p 0 5 1 等。 1 2 研究意义 由于现今互联网上存在的诸多即时通讯软件给互联网用户之间的交流造成了障碍， 这使得异构即时通讯软件之间的互联互通成为一种迫切的需求。 种类繁多的即时通讯软件在提供给互联网用户不同体验的同时也造成了不同软件 用户群之间交流的壁垒。几乎没有谁愿意仅仅为了与互联网上另一个人交流而颇费周折 的安装一个新软件并同时注册一个新账户，尤其在这种交流是临时性的时候。即使用户 愿意使用不同的软件与他人交流，对本地资源也造成了一定程度上的浪费。如何解决这 个问题无论从用户使用方便性的角度还是从软件工程的角度都有突出性的意义。 本文提出的异构即时通讯系统设计的出发点就是为了满足多种类即时通讯软件互 联互通的需求，使用户只安装一个客户端软件就可以方便的与任何一个即时通讯软件用 户交流，无论本地是否安装了与对方一样的客户端软件，抑或对方在使用何种软件。而 且集成多种即时通讯协议客户端的实现很好地解决了软件重复安装和本地资源无效占 用的问题，即使有新的协议提出，需要做的仅仅是安装一个插件而已。 此外，由于p 2 p 应用在互联网上的日益普及，使得p 2 p 网络可扩展性，健壮性，隐 私保护和负载均衡等特点日益凸显，本文提出的基于p 2 p 的异构即时通讯系统充分利用 了p 2 p 的以上特点，实现了该系统的高安全性和可靠性。 1 3 研究内容 本文在j a b b e r 社区s i p c o m m u n i c a t o r t 6 1 开源项目基础上结合p 2 p 应用，采用了p 2 p 资源发现和查找算法，在p 2 p 网络中寻找合适的对等点作为呼叫代理，实现异构即时通 讯软件之间的互联，在此基础上提出了基于p 2 p 的异构即时通讯系统原型，并给出了关 键部分的设计与实现。 本文首先探讨了p 2 p 相关协议和规范，提出了异构即时通讯系统实现的可行性，随 后对系统中主要网络实体进行了功能模块划分，分析设计了相关模块的关键行为，设计 了消息处理的关键流程，对整个系统进行了合理的简化，最后给出了系统中关键模块的 具体实现。 一2 一 东北大学硕士学位论文第1 章绪论 1 4 本论文所完成工作 本文首先介绍了p 2 p 协议相关规范，在此基础上提出了基于p 2 p 的异构即时通讯系 统原型，并对功能划分后的模块和网络实体给出了关键实现和处理流程。 主要内容包括：典型p 2 p 网络研究与比较；即时通讯协议接入p 2 p 网络可行性研究； 系统原型设计；实体命名机制；即时通讯实体在p 2 p 网络中资源查找和定位；异构即时 通讯平台互联关键流程研究与设计；管理和更新策略；该系统未来可能面临问题的研究 及可能的解决途径。 ， # 1 5 论文组织安排 本文讨论了p 2 p 相关协议和技术，并在此基础上对异构即时通讯系统进行了研究和 原型设计，对系统所涉及的关键问题提出了可行的解决方案。本文分如下几个部分： 第1 章：介绍本论文的研究背景、研究意义、研究内容、本人所完成工作及论文 组织安排。 第2 章：对p 2 p 网络进行分析与研究。包括p 2 p 基本概念，拓扑结构，d h t 路 由原理，对p 2 p 研究有重大影响的几个方面，p 2 p 发现技术研究的成果与不足，复杂 p 2 p 网络拓扑模型和非结构化p 2 p 搜索算法等。 第3 章：分析了基于p 2 p 的异构即时通讯系统基本概念，并给出了关键部分详细 设计。包括传统即时通讯实现原理，即时通讯协议接入p 2 p 网络可行性研究，用于实 现的d h t 协议选取，系统原型设计，网络实体结构功能设计，实体命名机制，资源 的发布和定位，关键流程研究和管理更新策略等。 第4 章：完成基于p 2 p 的异构即时通讯系统的关键实现。包括散列模块、定位模 块、发布模块和转发模块等关键模块的实现。最后介绍了这些模块在o s g i 平台上的 封装。 第5 章：讨论了该系统所面临的问题和可能的解决方案，并对该系统与一些新兴 技术的结合提出了展望。 一3 一 东北大学硕士学位论文第1 章绪论 钿一 飞 ， 东北大学硕士学位论文第2 章p 2 p 网络拓扑及算法分析 第2 章p 2 p 网络拓扑及算法分析 2 1p 2 p 的定义 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部份资源，比如处理 器能力、存储能力、网络连接能力、打印机等，这些共享资源需要有网络提供服务和 内容，能被其他对等体直接访问而不需进过中间实体。在此网络中的参与者既是资源 ( 服务和内容) 提供者，又是资源获取者【3 1 1 9 。 2 2p 2 p 网络中的拓扑结构研究 拓扑结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，节点之 间的拓扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使用集中式、层 次式等拓扑结构，i n t e m e t 本身是世界上最大的非集中式的互联网络，但是九十年代所 建立的一些网络应用系统却是完全的集中式的系统、很多w e b 应用都是运行在集中式 的服务器系统上。集中式拓扑结构系统目前面临着过量存储负载、d o s 攻击等一些难 以解决的问题【7 1 。 p 2 p 系统一般要构造一个非集中式的拓扑结构，在构造过程中需要解决系统中所 包含的大量节点如何命名、组织以及确定节点的加入离开方式、出错恢复等问题。 根据拓扑结构的关系可以将p 2 p 主要分为4 种形式【8 】： ( 1 ) 中心化拓扑( c e n t r a l i z e dt o p o l o g y ) ：其最大的优点是维护简单发现效率高。 由于资源的发现依赖中心化的目录系统，发现算法灵活高效并能够实现复杂查询。最 大的问题与传统客户机服务器结构类似，容易造成单点故障【1 0 1 ，如图2 1 所示。 卜 s e a r c h 一一- - - - i - d o w n l o a d 图2 1 中心化拓扑p 2 p 网络 f i g 2 1p 2 p n e t w o r ki nc e n t r a l i z e dt o p o l o g y 一5 一 东北大学硕士学位论文第2 章p 2 p 网络拓扑及算法分析 ( 2 ) 全分布非结构化网络( d e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ) ：在重叠网络 ( o v e r l a y ) 采用了随机图的组织方式，节点度数服从“p o w e r - l a w ”规律，从而能够较 快发现目的节点，面对网络的动态变化体现了较好的容错能力，因此具有较好的可用 性，同时可以支持复杂查询，如图2 2 所示。 图2 2 全分布式非结构化拓扑p 2 p 网络 f i g 2 2p 2 pn e t w o r k i nd e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y ( 3 ) 完全分布式结构化拓扑网络( d e c e n t r a l i z e ds t r u c t u r e dt o p o l o g y ，也称作d h t 网络) ：这种网络拓扑结构采用了分布式散列表( d h t ) ，d h t 类结构能够自适应节点 的动态加入退出，有着良好的可扩展性、鲁棒性、节点d 分配的均匀性和自组织能 力。由于重叠网络采用了确定性拓扑结构，d h t 可以提供精确的发现。只要目的节点 存在于网络中d h t 总能发现它，发现的准确性得到了保证。但d h t 的维护机制较为 复杂，尤其是节点频繁加入退出造成的网络波动( c h u r n ) 会极大增加d h t 的维护代 价【1 1 1 。d h t 所面临的另外一个问题是d h t 仅支持精确关键词匹配查询，无法支持内 容语义等复杂查询。 ( 4 ) 半分布式结构( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ，也称作h y b r i ds t r u c t u r e ) ：吸 取了中心化结构和全分布式非结构化拓扑的优点，选择性能较高( 处理、存储、带宽 等方面性能) 的节点作为超级点( 英文文献中多称作：s u p e r n o d e s 3 6 1 ，h u b s ) ，在各 个超级点上存储了系统中其他部分节点的信息，发现算法仅在超级点之间转发，超级 点再将查询请求转发给适当的叶子节点。半分布式结构也是一个层次式结构，超级点 之间构成一个高速转发层，超级点和所负责的普通节点构成若干层次，如图2 3 所示。 一6 一 j 东北大学硕士学位论文 第2 章p 2 p 网络拓扑及算法分析 。 普通节点 超级节点 图2 3 半分布式p 2 p 网络结构 f i g 2 3h y b r i ds t r u c t m e dp 2 pn e t w o r k 4 种结构的性能比较如下表所示： 表2 14 种p 2 p 网络结构性能比较 t a b l e2 1s t r u c t u r ea n dp e r f o r m a n c ec o m p a r i s o no f4p 2 pn e t w o r k s 2 3 复杂p 2 p 网络拓扑模型 2 3 1 i n t e r n e t 拓扑模型 i n t e m e t 作为当今人类社会信息化的标志，其规模正以指数速度高速增长。如今 i n t e m e t 的“面貌 已与其原型a r p a n e t 大相径庭，依其高度的复杂性，可以将其看 作一个由计算机构成的“生态系统 。虽然 n t e r n e t 是人类亲手建造的，但却没有人能 说出这个庞然大物看上去到底是个什么样子，运作得如何。i n t e m e t 拓扑建模研究就是 探求在这个看似混乱的网络之中蕴含着哪些还不为我们所知的规律。发现i n t e m e t 拓扑 的内在机制是认识i n t e r n e t 的必然过程，是在更高层次上开发利用i n t e r n e t 的基础。然而， 一7 一 东北大学硕士学位论文第2 章p 2 p 网络拓扑及算法分析 i n t e m e t 与生俱来的异构性动态性发展的非集中性以及如今庞大的规模都给拓扑建模带 来巨大挑战。i n t e r n e t 拓扑建模至今仍然是一个开放性问题，在计算机网络研究中占有 重要地位。 i n t e r n e t 拓扑作为i n t e m e t 这个自组织系统的“骨骼 ，与流量协议共同构成模拟 i n t e m e t 的3 个组成部分，即在拓扑网络中节点问执行协议，形成流量。i n t e m e t 拓扑模 型是建立i n t e r n e t 系统模型的基础，由此而体现的拓扑建模意义也可以说就是l n t e m e t 建模的意义，即作为一种工具，人们用其来对i n t e m e t 进行分析预报决策或控制。i n t e r n e t 模型中的拓扑部分刻画的是l n t e r n e t 在宏观上的特征，反映一种总体趋势，所以其应用 也都是在大尺度上展开的。对i n t e m e t 拓扑模型的需求主要来自以下几个方面：( 1 ) 许多 新应用或实验不适合直接应用于i n t e r n e t ，其中一些具有危害性，如蠕虫病毒在大规模 网络上的传播模拟；( 2 ) 对于一些依赖于网络拓扑的协议( 如多播协议) ，在其研发阶 段，当前i n t e r n e t 拓扑只能提供一份测试样本，无法对协议进行全面评估，需要提供多 个模拟拓扑环境来进行实验；( 3 ) 从国家安全角度考虑，需要在线控制网络行为，如美 国国防高级研究计划局( d a r p a ) 的n m s ( n e t w o r km o d e l i n ga n ds i m u l a t i o n ) 项目。 2 3 2s m ai lw o rid 网络 在现实的i n t e r n e t 环境中，网络拓扑并不完全满足随机网络拓扑。w a t t 和s t r o g a t z 发现，只需要在规则网络上稍作随机改动就可以同时具备以下两个性质。 s m a l l 、o d d 【1 2 】【1 3 】模型的特性：网络拓扑具有高聚集度和短链的特性。改动的方法是，对 于规则网络的每一个顶点的所有边，以概率p 断开一个端点，并重新连接，连接的新的 端点从网络中的其他顶点里随机选择，如果所选的顶点已经与此顶点相连，则再随机选 择别的顶点来重连【1 4 1 。当p = 0 时就是规则网络，p = l 则为随机网络，对于0 p l 的 情况，存在一个很大的p 的区域，同时拥有较大的集聚程度和较小的最小距离。 ( 1 ) 平均路径。被随机选择又重新连结后的线称为捷径，它对整个网络的平均路径 有着很大影响，分析表明：在保证系统中至少出现一条捷径的情况下，系统的平均路径 开始下降。即使是相当少的捷径也能够显著地减小网络的平均路径长度。这是因为每出 现一条捷径，它对整个系统的影响是非线性的，它不仅影响到被这条线直接连着的两点， 也影响到了这两点的最近邻、次近邻，以及次次近邻等。 ( 2 ) w s 网络的集团系数。r 1 初始固定的节点数可计算t l ( p = o 时规则网络的聚集系 数为c ( o ) ，c ( o ) 取决于网络结构而与尺寸n 无关，因此有相对较大的值。随着边按一定 一8 一 东北大学硕士学位论文 第2 章p 2 p 网络拓扑及算法分析 的概率p 随机化，聚集系数在c y o ) 的附近变化。 ( 3 ) 度分布。w s 模型是介于规则网络和随机网络之间的模型，p = 0 时规则网络的度 分布是中心点位于k = k 的s 函数，p = i 时随机网络符合p o i s s o n 分布，在k = k 点达到极 大值。p 从0 变化到1 的过程中，原来s 函数形式的度分布逐渐拓宽最终形成p o i s s o n 分布。在s m a l lw o r l d 网络的研究兴起之后，越来越多的科学家投入到复杂网络的研究 中去。大家发现其实更多的其他几何量的特征也具有很大程度上的普适性和特定的结构 功能关系。s c a l ef r e e 网络就是其中的一个重要方面。s c a l ef r e e 网络指的是网络的度分 布符合幂率分布，由于其缺乏一个描述问题的特征尺度而被称为无标度网络。我们都知 道在统计物理学相变与临界现象，以及在自组织临界性( s o c ) 中幂率具有特殊地位。 s c a l e f r e e 其实也具有s m a l lw o r l d 的特性。 。 ， 2 4d h t 路由原理 7 分布式散列表( d h t ) t 3 5 1 实际上是一个由广域范围大量节点共同维护的巨大散列表。 散列表被分割成不连续的块，每个节点被分配给一个属于自己的散列块，并成为这个散 列块的管理者。d h t 的节点既是动态的节点数量也是巨大的，因此非中心化和原子自 组织成为两个设计的重要目标。通过加密散列函数，一个对象的名字或关键词被映射为 1 2 8 位或1 6 0 位的散列值。一个采用d h t 的系统内所有节点被映射到一个空间l = 0 ，1 ) ， 如果散列函数映射一个h 位的名字到一个散列值h ，则有h 2 “l 。 d h t 使用分布式哈希算法来解决结构化的分布式存储问题。分布式哈希算法的核 心思想是通过将存储对象的特征( 关键字) 经过哈希运算，得到键值( h a s hk e y ) ，对 象的分布存储依据键值来进行。具体来讲，大致有以下步骤： ” 对存储对象的关键字进行哈希运算，得到键值。这样就将所有的对象映射到了一个 具体的数值范围中。 重叠网中的每个节点负责数值范围中的特定段落。例如，节点a 负责存储键值从 8 0 0 0 到8 9 9 9 的对象；而节点b 负责7 0 0 0 - 7 9 9 9 的对象。这样就将对象集合分布地存储 在所有的节点中。 节点可以直接存储对象本身，如文件中的一个片段；也可以存储对象的索引，如该 对象所在节点的i p 地址。 结构化的分布式存储问题解决后，剩下的问题就是用户如何才能找到存储着目标信 息的节点。在有着大量节点( 如1 0 0 万个) 的p 2 p 系统中，任何节点都不可能拥有全部 - 9 - 一 东北大学硕士学位论文 第2 章p 2 p 网络拓扑及算法分析 的节点键值内容的对应关系；因此用户获得了键值之后，如何找到该键值对应的节点 就被称为d h t 的路由问题。d h t 协议必须定义优化的查找( 路由) 算法来完成这一搜 寻的工作。不同的d h t 协议之间区别很大程度上就在于定义了不同的路由算法。 d h t 的应用非常简洁a p i 简单到只有一项输入和一项输出： 应用层将数据对象( 文件、数据块或索引) 通过哈希算法获得键值，将该键值提交 给d h t 后，返回结果就是键值所在节点的i p 地址。图2 4 显示了这种应用结构： 2 5 主流d h t 协议介绍 2 5 1 缓冲阵列路由协议 图2 4 d h t 的应用结构 f i g 2 4d h ta p p l i c a t i o ns t r u c t u r e 囊t协议简介 穸 c a r p 1 5 1 ( c a c h ea r r a yr o u t i n gp r o t o c 0 1 ) 是由微软公司的v i n o dv a l l o p p i l l i l 和宾西 法尼亚大学的k e i t hw r o s s 在1 9 9 7 年提出的。该协议可以将u r l 空间映射到一个仅有 松散关联关系的w 曲c a c h e 服务器( 在协议中称为“代理 ，p r o x y ) 阵列中。支持该协 议的h t t p 客户端可以根据要访问的u r l 智能选择目标代理。该协议解决了在代理阵 列内分布存储内容的问题，避免了内容的重复存储，提高了客户端访问时w e bc a c h e 命 鼍中