（计算机软件与理论专业论文）基于p2p技术qos中间件的研究与设计.pdf

摘要 本文在对当前i p 网络保证q o s ( q u a l i t yo fs e r v i c e ) 技术研究的基础上，提 出通过使用p 2 p 技术为端到端应用构造端到端覆盖网协助数据的传输，以提高应 用的服务质量的新方法。本文首先分析了服务质量( q o s ) 关键技术和l i n u x 操作系 统对主机端q o s 的支持，接着研究了p 2 p 模型及其关键技术。在此基础上提出了 基于非结构化p 2 p 的端到端覆盖网q m p 2 p 协议，并详细论述了0 5 1 p 2 p 协议下分布 式环境节点发现机制，覆盖网拓扑结构生成算法和根据网络状况拓扑结构自调整 的算法。并基于端到端覆盖网o m p 2 p 协议设计了q o s 中间件，提出主机端资源预 留方法，代理节点的选择方法和数据传输流量分配方案。通过使用代理节点协助 数据传输，q o s 中闻件提高了端到端网络通信质量。最后通过n s 2 网络仿真程序模 拟q o s 中间件在网络中的运行，验证q o s 中间件的有效性。 关键词：q o sp 2 p 中间件覆盖网分布式 a b s t r a c t b a s e do nq o s ( q u a l i t yo fs e r v i c e ) t e c h n o l o g yr e s e a r c ho v e rc u r r e n ti p n e t w o r k 。t h i sp a p e rp r o p o s ean e wm e t h o dt oi m p r o v ea p p l i c a t i o n s q u a l i t y o fs e r v i c eb yu s i n gp 2 pt e c h n o l o g yt oc o n s t r u c te n d t o 。e n do v e r l a yt oh e l p e n d t o e n d a p p l i c a t i o n s d a t at r a n s f e r a tf i r s t t h i sp a p e ra n a l y z e s t h ek e yt e c h n o l o g yo fq o sa n dl i n u xs u p p o r to fh o s te n dq o s t h e ns t u d y t h ek e yt e c h n o l o g yo fp 2 pa n dp 2 pm o d e l s f o u n d e do ns t u d ya b o v e ，t h i s p a p e rp r o p o s ea n e wu n s t r u c t u r e dp 2 pe n d t o e n do v e r l a yp r o t o c o lq m p 2 pa n d e x p l a i nd i s t r i b u t e d e n v i r o n m e n tp e e r f i n d i n gm e c h a n i s m ，t o p o l o g y g e n e r a t i o na l g o r i t h mo ft h eo v e r l a ya n da l g o r i t h mo fa d j u s t i n gt h et o p o l o g y r e a c t i n gt ot h en e t w o r ks t a t u su n d e rq m p 2p t h e nd e s i g nq o sm i d d l e w a r eb a s e d o nt h ee n d t o e n do v e r l a yq m p 2 pp r o t o c o la n dp r o p o s e st h em e t h o dt or e s e r v e r e s o u r c ef r o mo p e r a tin gs y s t e m ，t h ep r o x yn o d es e l e c ta n dd a t a t r a n s f e r a l g o r i t h m t h r o u g hu s i n go fp r o x yn o d et oh e l pt h ed a t at r a n s f e r ，q o s m i d d l e w a r eo p t i m i z e se n d t o e n dc o m m u n i c a t i o nq o s f i n a l l yt a k i n gu s eo f n s 2n e t w o r ks i m u l a t o rt os i m u l a t et h ef u n c t i o n o fq o sm i d d l e w a r eo v e r n e t w o r ka n dv e r i f yt h ee f f i c i e n to fq o sm i d d l e w a r e k e y w o r d ： q o sp 2 pm i d d l e w a r ed i s t r i b u t e 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外。论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：毯毖 关于论文使用授权的说明 日期越主：星 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生 在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕业 离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。学 校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部 或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在 解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名： 日期越互：! 日期：塑! ! ! ：i 第一章绪论 第一章绪论 1 1 论文研究背景 随着i n t e r n e t 的发展，涌现出许多以v o i p ( v o i c eo v e ri p ) 为代表的应用， 它们不再满足于i n t e r n e t 单一的尽力而为的服务方式，而对带宽、吞吐量、延迟 等提出了更多的要求，这就引起了人们对q o s ( q u a l 脚o fs e l c e ) 的需求。在过去的 十年里，人们做出了许多努力，以在i n t e r n e t 中以合适的方式提供q o s ，如提出 综合服务框架和区分服务框架。与这些努力的结果相反，当前的i n t e r n e t 还是仅 提供尽力而为的服务方式，最主要的原因之一就是这些建议要求在源节点和目标 节点的所有网络元素都必须提供q o s 机制，由于i n t e r n e t 的复杂性和网络提供商 很难为如此大范围的网络设备更新找到合适的理由，改变i n t e r n e t 的框架是如此 的困难以至于遥遥无期，并最终损害了综合服务框架和区分服务框架的采纳。既 然网络节点( 主要指i p 路由器) 最终也无法为我们提供所需要的q o s 保证，是否 有一种方法在网络节点不具备q o s 机制的前提下提供较好的q o s 保证呢? 我们将目光转向p 2 p ( p e e rt op e e r ) 技术，采用p 2 p 技术，人们在i n t e r n e t 之上提出并构建了各种覆盖网( o v e r l a yn e t w o r k ) 方案，相对于i n t e r n e t ，覆盖网 具有更大的潜力来寻找两个节点间更好( 相对路由器选路) 的路径，将数据包有 选择地经过更好的路径传输到目的地，从而提高应用的服务质量，但是，一般覆 盖网研究的重点是寻找覆盖网中任意两节点间最好的路径( 延迟小，带宽高，抖 动小等) ，以提高覆盖网的整体性能，这些路径的判断需要覆盖网中各个节点不断 交换信息并进行计算以保证路由选择的准确性，这是一个费时费力的过程，并且 对于某些应用而言，最优路径并不意味着就是最好的路径。比如一般的实时端到 端应用，它们需要的只是在它们可接受的延迟内将指定数量的数据发送到目的端， 这是一个“合适”而非“最优”的概念，而且在一个具有大量节点的覆盖网络中， 两个节点通信的概率很小，很可能计算和维护两个节点间的最优路径永远都不会 被使用，造成极大的资源浪费。 1 2 论文的研究目标 本文的主要研究目标是针对端到端应用特点，实时性、带宽需求稳定，根据 国内外研究的现状，结合p 2 p 技术和覆盖网技术，提出一个适用于当前i n t e r n e t 现状的低代价、高效的端到端覆盖网生成算法，并结合主机端q o s 保障技术设计 一个基于p 2 p 技术的q o s 中间件，通过覆盖网中q o s 中间件的相互协作满足端到 2 基于p 2 p 技术q o s 中间件的研究与设计 端应用的q o s 要求。 1 3 本文的研究内容和结构组织 本文建立一种基于p 2 p 技术的q o s 中间件模型，提出q o s 中间件的设计方法， 通过生成端到端覆盖网来提高服务质量，并通过模拟实验验证该方案能有效地改 善传输质量，证实基于p 2 p 技术的o o s 中间件比使用直接链路传输能得到更好的 服务质量。本文的研究内容包括： 研究服务质量( q o s ) 关键技术，分析了q o s 机制研究现状、综合服务模型 和区分服务模型的优点与缺点；研究了l i n u x 操作系统对主机端o o s 的支 持，分析了流量控制模块( t c ) 的工作方式；研究了p 2 p 技术的特点、对 比分析了当前主要的p 2 p 网络模型，提出基于纯p 2 p 网络模型组织q o s 中 间件。 提出非结构化p 2 p 端到端覆盖网的q m p 2 p 协议。这个系统解决了分布式环 境下节点发现机制，通过上层应用选择算法生成覆盖网拓扑结构，并根据 网络状况进行拓扑结构调整。 提出基于p 2 p 技术q o s 中间件的设计方案，提出主机端资源预留方法，代 理节点的选择方法和数据传输流量分配方案，通过使用代理节点协助数据 传输，提高端到端网络通信质量。并通过n s 2 网络仿真程序模拟q o s 中间 件在网络中的运行，验证g o s 中间件的有效性。 本文具体各章安排如下： 第一章介绍研究背景与意义，当前国内外相关技术的发展状况，以及存在的问 题。 第二章分析服务质量( q o s ) 相关技术和当前提出解决方案及其不足，分析p 2 p 技术特点及主流p 2 p 模型。 第三章提出端到端覆盖网设计方法及其相关算法。 第四章提出基于p 2 p 技术g o s 中间件的设计方法及其节点选择、流量分配等策 略。 第五章通过在n s 2 网络仿真器上实现q o s 中间件，并进行实验验证q o s 中间件 对端到端促进作用，证实了g o s 中间件的实用性与有效性。 第二章研究背景和相关工作 3 第二章研究背景和相关工作 2 1q o s 的概念 i pq o s 脚脚是指i p 网络的一种能力，它是指i p 分组在网络流通中的性能， 这种性能可以通过一系列可度量的参数来描述。q o s 包括多个方面的内容，如带宽、 时延、时延抖动等，每种具体的业务都对q o s 有特定的要求，有些应用对其中的 某些指标要求高一些，而对另一些要求低一些。衡量i pq o s 的性能指标主要包括 以下几个： 1 、时延：也称延迟( l a t e n c y ) ，指数据包从一个发送端系统发送到网络中一个 接收端系统的时间间隔，也就是分组的第一个b i t 离开发送端和分组的最 后一个b i t 到达接收端之间的时间间隔，所有实时应用对时延都有一定要 求，如v o i p 业务，一般要求网络时延小于2 0 0 m s ，当网络时延大于4 0 0 m s 时，通话将无法忍受。 2 、时延抖动：反应分组延迟的变化程度，即在同一条路由路径上发送的一组 数据包之间的时间差异，抖动对具体业务的影响不同，有些应用可以通过 缓冲来减少时延抖动对业务的影响，而对于语音业务，时延抖动将引起质 量的下降。 3 、吞吐量：指网络中两个节点之间特定应用业务流的速率，主要衡量应用从 网络中取得业务数据的能力，所有的实时应用对带宽都有一定的要求，并 且具体应用对带宽的需要可能是可变的，如语音电话，当传输速率低于音 频编码要求的速率时，声音质量将无法保证，而电话会议，根据发言人数 的不同和发言时间的不同对带宽需求是不一样的，因此吞吐量可以使用平 均发送速率或峰值发送速率来表示。 4 、丢包率：指在网络中传输数据包时丢失的比率，用以衡量网络正确传输用 户数据的能力，不同的业务对丢包率的敏感度不同，在v o i p 应用中，丢包 是导致通话质量恶化的主要原因之一，数据包的丢失一般是由于网络链路 的波动和网络拥塞引起的。 此外，q o s 还可能包含其它一些指标，如网络可靠性、误码率等，q o s 指标“川m 实际上反映了网络元素( 例如应用程序、主机或路由器) 在保证信息传输和满足服 务要求方面的能力，对于不同的应用，当q o s 缺乏保障时，它们的表现是不样 的。提出q o s 机制的目标是为i n t e r n e t 应用提供服务区分和性能保证：服务区分 是指根据不同应用的需求为其提供不同的服务；性能保证则要解决诸如带宽、丢 失、延迟、抖动等性能指标的保证问题。 4 基于p 2 p 技术q o s 中间件的研究与设计 2 2 综合服务( i n t s e r v ) 模型与区分服务( d i f f s e r v ) 模型概述 2 2 1 综合服务( i n t s e r v ) 模型 针对i pq o s 的问题，i e t f 在早期提出了i n t s e r v ( i n t e g r a t e ds e r v i c e s ) 模型。i n t s e r v 模型又称为综合服务模型，它完全借用了传统电路交换的思想，发 送端在传送数据之前，先通过q o s 信令在发送端和接收端之间建立一条虚连接通 路，并根据业务的o o s 需求进行网络资源预留，然后才开始在此通路上传递数据 包，因此可以为该数据流提供端到端的q o s 保证。 资源预留协议r s v p t = j ( r e s o u r c er e s e r v a t i o np r o t o c 0 1 ) 是i n t s e r v 模型中的 主要q o s 信令协议。主机通过使用r s v p 为特定应用的数据流请求服务质量，而路 由器也可以使用r s v p 向数据流上的所有节点发通告网络质量的变化，通常，使用 r s v p 会在数据传输路径的所有节点上都预留资源。r s v p 具有以下特性： a ) r s v p 可以为单播和多对多组播程序预留资源。 b ) r s v p 是单工的，意味着它只能为非双向数据流预留资源。 c ) r s v p 是面向接收者的，数据流的接收方需要发起和维护那个流的资源预留。 d ) r s v p 会在主机和路由器上维持一个“软状态”，以适应路由变化和支持动 态成员改变。 e ) r s v p 并不是一个路由协议，但依赖于当前或未来的路由协议。 r s v p 直接工作在i p 层之上，和t c p u d p 处于相同层次，但对于一些缺乏r a w 套接字支持的系统，r s v p 也可以工作在u d p 层之上，因此r s v p 是一个相当灵活的 协议。r s v p 提供两种基本消息类型：p a t h 消息和r e s v 消息，其工作流程如图2 - 1 所示： 图2 - 1r s v p 工作流程 发送端依据带宽需要、传输迟延以及抖动来表明发送业务。r s v p 从含有“业 务类别( t s p e c ) ”信息的发送端发送一个路径信息( p a t hm e s s a g e ) 给目的地址( 单点 广播或多点广播的接收端) ，消息中包含有描述业务流的传输属性和路由的信息。 每一个支持r s v p 的路由器沿着下行路由建立一个“路径状态表”，其中包括路径 信息里先前的源地址( 例如，朝着发送端的上行的下一跳) ，为了获得资源预留， 接收端发送一个上行的r e s v ( 预留请求) 消息。除了t s p e c ，r e s v 消息里有“请求 类别( r s p e c ) 8 ，表明所要求的综合服务类型，还有一个“过滤器类别”，表示正在 为分组预留的资源( 如传输协议和端口号) 。r s p e c 和过滤器类别合起来代表一个 第二章研究背景和相关工作 5 “流的描述符”，路由器就是靠它来识别每一个预留资源的。当每个支持r s v p 的 路由器沿着上行路径接收r e s v 的消息时，它采用输入控制过程证实请求，并且配 置所需的资源。如果这个请求得不到满足( 可能由于资源短缺或未通过认证) ，路 由器向接收端返回一个错误消息。如果这个消息被接受，路由器就发送上行r e s v 到下一个路由器当最后一个路由器接收r e s v ，同时接受请求的时候，它再发送一 个证实消息给接收端。如果接受资源预留请求，则必须为业务流保持所需的链路 带宽和必要的缓冲区等“软状态”，这种预约软状态不需要明确的删除请求，而由 r s v p 控制信息周期性的刷新。在无刷新信息的情况下，“软状态”会超时并被删除。 从技术层面上讲，r s v p 是一种有效的q o s 保障方法。但是，由于i p 网络流量 模型的特点，如果为每一路呼叫都建立一条虚电路，那么相应的，网络上的路由 器也需要为每条数据流维护一个状态，这极大的影响了路由器的效率，并且对于 大规模网络，维护数据流状态将使核心网络路由器不堪重负，对于运营商来说， 要更换很多不支持r s v p 的网络设备，需要的成本和时间也是很难接受的，这些都 严重制约了i n t s e r v 在实际网络中的应用。 因此，如果要实现端到端的o o s 保障，在目前使用r s v p 是不合适的。 2 2 2 区分服务( d i f f s e r v ) 模型 由于i n t s e r v 的局限性，i e t f 又提出了d i f f s e r v 】【矧( d i f f e r e n t i a t e d s e r v i c e s ) 模型，又称为区分服务模型。在区分服务模型中，引入了o i f f s e r v 域 ( d o m a i n ) 的概念，它是指一系列协同满足区分服务策略管理的、连续的i n t e r n e t 网络的一部分。一个区分服务域可以包括不同的主机与路由器、管理区域、自治 域，不同的信任域与不同的网络技术( 比如信元或帧) 等等。区分服务域也叫d s ( d i f f e r e n t i a t e ds e r v i c e ) 域。 区分服务模型的基本思想是在网络的入口处为每个数据包分类，并在数据包中 标记相应的区分服务标记( d s c p ，d i f f s e r vc o d e p o i n t ) ，用于指示数据包在网络 转发路径的中间节点上被处理的方式。在网络内部的核心路由器中只保存简单的 d s c p 与p h b ( 每跳行为) 的对应机制，根据数据包头部中的d s c p 值对数据包进行 相应的优先级转发，而业务流状态信息的保存与流量控制机制的实现等都在网络 边界节点进行，内部节点是与状态无关的。 d i f f s c r v 将复杂度转移到网络的边缘上，而在网络核心只需实现最简单的服 务保证机制，更为重要的一点是d i f f s c r v 模型通过约定的d s c p 值来表示不同的 服务等级，从而只需在网络边缘进行用户服务请求到d s c p 的映射，免去了在网 络的核心节点上采用显式资源预留信令的必要，从而降低了其实现复杂度，目前 在i p 网中区分服务得到了绝大部分厂家的支持。但区分服务也有自己的局限性， 6 基于p 2 p 技术q o s 中间件的研究与设计 主要体现在： ( 1 ) 区分服务只承诺相对的服务质量，不能保障每个流的绝对服务质量。 在d i f f s e r v 模型中，边界路由器对分组做适当的分类和标识；内部路由器仅 仅需要根据其标识作简单的处理。这意味着内部路由器识别单个流，而是处理聚 合的类，因此，d i f f s e r v 不能保证每个流的绝对的服务质量。 ( 2 ) 无法提供端到端的0 0 s 保障。 在m 网上传送数据时，业务的q o s 保证不是单靠链路上某一个路由器就能单 独完成的，它是链路上所有节点合作的结果。d i f f s e r v 没有办法完全依靠自己来 提供端到端的o o s 结构，它需要大量网络单元的协同运作，才能向用户提供端到 端的服务质量。鉴于这些组件高度分散的特点和对它们进行集中管理的需要，必 须有一个全局的带宽管理对全局资源进行动态管理。 2 2 3i n t s e r v 与d i f f s e r v 结合 目前业界还提出了把i n t s e r v 与d i f f s e r v 结合的方式，其思路为：在用户网 络仍使用r s v p ，在运营商的d i f f s e r v 网络边界将i n t s e r v 的业务类型映射为 d i f f s e r v 的业务类型，这样利用i n t s e r v 的架构来解决端到端的q o s ，同时也利 用d i f f s e r v 来提供好的扩展性。但这种方法仍然存在i n t s e r v 的信令复杂、参于 管理等问题，而且由于在运营商的网络采用d i f f s e r v ，因此在这一段网络也只能 提供相对的q o s ，从而使端到端的服务质量得不到硬性的带宽保证。 2 3 主机端q o s 的支持 以上各小节简单概述了当前在网络架构层次上对解决0 0 s 问题所进行的研究， 但是，仅仅从网络层次是无法解决0 0 s 问题的，如果在主机端无法保证应用的资 源要求，应用的0 0 s 仍然是不能满足的，因此提供质量保证主要问题之一在于主 机端必须支持资源预留。 2 3 1l i n u x 系统0 0 s 实现概述 l i n u x 作为现在流行的网络操作系统，具有高效、灵活的网络能力。一台运行 l i n u x 机器可以同时作为路由器、防火墙使用l i n u x 从k e r n e l2 1 1 0 5 开始， 就提供了对q o s 的支持，其核心机理是在网络拥塞情况下，如何实现对不同数据 进行调度和处理。l i n u x 内核对q o s 的实现基本原理可用图2 2 表示 第二章研究背景和相关工作 7 图2 - 2l i n u x 流量控制 当一个数据包到达后，首先进行输入数据包的分析，如果目的端是本地的话， 将送到协议栈的上层进行处理；否则将送到数据包转发模块做进一步的转发。上 层协议需要传输的数据也交给转发模块转发。数据包转发模块进行路由选择后， 将数据包送入选择的输山接口的相应队列中，排队准备输出。作用于输出队列上 的流量控制模块所起的作用是：对输出队列进行排队控制，实现分级服务以提供 不同的q o s 。 l i n u x 的流量控制模块( t c 嘲州嘲t r a f i cc o n t r 0 1 ) 由三个基本模块组成：排 队策略( q u e u i n gd i s c i p l i n e s ) ，包分类器( c l a s s e s ) 和包过滤器( f i l t e r s ) 。每个 网络设备( 主要指路由器、交换机等) 接口都对应一个根排队策略，此策略将用来 指定该网络设备接口相关队列中的数据包处理方式。包分类器和包过滤器与排队 策略有着紧密的关系。包过滤器根据队列中取出的数据包的属性对其进行分类， 根据分类的结果决定将该数据包放入某一队列：每个类别都有一个队列与其对应 并包含相应的排队策略 2 3 2t c 组成部分 2 3 2 1 排队策略 l i n u x 排队策略主要实现的就是数据包的入队和出队操作，不同的入队出队 操作体现了不同的队列调度方式，从而实现了对数据包的不同处理方式。目前 l i n u x 内核支持的排队策略有多种，这里只介绍常用且与本文具体实现相关的几种 排队策略。 ( 1 ) f i f o ( 先进先出排队) ：这种排队策略并不对到达的数据包做任何的处 理，仅仅按照其到达的先后顺序进行调度，为缺省的队列规则。这种排队策略只 有一个参数：l i m i t ，用来设置队列的长度，队列的长度用该队列可以容纳的最大 数据包个数或字节数表示。 ( 2 ) c b q ( 基于类的排队，c l a s sb a s e dq u e u i n g ) ：这种排队策略是优先队列的 变体，它实现了一个丰富的连接共享类别结构，可以为每个输出队列指定优先级 和允许的最大流量，从丽既达到限制带宽( s h a p i n g ) ，又达到带宽优先级管理的能 力。c b q 通过时间片轮转不同的优先级队列，防止了因任一级别的业务量独占系统 资源和带宽，造成其他业务量出现饥饿这一现象，从而很好地为不同类型的数据 8 基于p 2 p 技术q o s 中间件的研究与设计 流提供一定的公平性。 ( 3 ) t b f ( t o k e nb u c k e tf l o w ，令牌桶算法) ：这是一个简单的排队策略：只 允许以不超过事先设定的速率到来的数据包通过，但允许短暂突发流量。利用t b f 可以控制传送到网络上的数据流最和速率。 在t b f 中以恒定的速率：产生令牌，放入容量为b 的令牌桶中，如果桶满则 多余的令牌将被丢弃。假设数据传送、调度服务的单位为字节( b y t e ) ，这样表明 每个令牌能够传送一个字节。输入数据进入后，将面临三种情况： 情况一：数据流到达速率等于令牌产生速率。这种情况下，每个到来的数据 包都能从令牌桶中取出相应数量的令牌，然后无延迟地通过队列。 情况二；数据流到达速率小于令牌产生速率。这种情况下，通过队列的数据 包只消耗了一部分令牌，剩下的令牌会在令牌桶中积累下来。直到桶被装满。这 样可以满足短暂的高于令牌流速率的到达数据流的需要，即对突发流提供定的 支持。 情况三：数据流到达速率高于令牌产生速率。在这种情况中，令牌桶中的令 牌很快就会被耗尽，此时到达的数据将在等待队列中排队，等待桶中有相应数量 的令牌的出现。如果数据包持续到来，还将可能发生丢包现象。由于传输的数据 需要在等待队列中排队，所以将导致传输延迟。 ( 4 ) r e d ( 随机早期检测，r a n d o me a r l yd e t e c t i o n ) 早期i p 网中的拥塞控制机制由端系统根据分组丢弃来估计网络中是否出现拥 塞，如果出现拥塞则通过降低发送速率来减轻网络的负担；拥塞时网络中的传输 节点采用尾部丢弃策略。这些措施具有很明显的缺点：没有达到避免拥塞出现的 作用，而只是在拥塞出现后才采取某种措施，实际上此时拥塞已经对网络的传输 造成了一定的影响。 r e d 算法基于平均队列长度预测可能到来的网络拥塞，并采用随机选择的策略 对分组进行标记或丢弃该分组，在拥塞尚未出现时提示端系统降低其发送速率， 以达到避免拥塞的目的。此外因为采用了随机早期标记的策略处理到达的分组， 使得不同端系统对拥塞指示的响应更加分散提高了网络资源的利用率。 r e d 算法中有三个重要的参数：m i n ，脑x 和b u r s t m i n ：设置了队列到达多少字节时开始丢包。 m a x ：为一软上限，达到该上限后，将丢弃所有到达的数据包。 b u r s t ：设置最多有多少个数据包能够突发通过。 r e d 算法中，当平均队列长度小于阀值m i n 时，所有到达的分组都被允许进入 队列；当平均队列长度处于两个阀值m i n 和m a x 之间的时候，将按照一定的概率 标记或丢弃分组：当平均队列长度大于阀值m a x ，则所有到达的分组都将被丢弃。 ( 5 ) g r e d ( g e n e r i cr a n d o me a r l yd e t e c t i o n ，一般的随机早期检测) ： 第二章研究背景和相关工作 9 g r e d 是r e d 的扩展，它提供了多路r e d 队列的能力，每个r e d 队列在这里也 被称为虚拟队列( v q ) 。目前g r e d 最多同时支持1 6 个虚拟队列。每个v q 根据优先 级设定权值，并依次分配一定的带宽。g r e d 算法根据d i f s e r v 的d s c p 值来决定选 择哪个虚拟队列。当达到一定拥塞时将首先丢弃具有高丢弃概率的队列中的数据 包。 2 3 2 2 分类 在l i n u x 中类与队列是紧密联系在一起的。当一个数据包到达一个队列时， 排队策略首先调用包过滤器来确认包的类别，然后将其放入与之对应的队列。每 个分类都对应一个队列，a 包含相应的排队策略。一个类代表了该队列规范中的一 类数据包，这些数据包有着某种相同特性( 如它们具有相同的源i p 地址) ，并且 接受相似的处理( 因为每个类下面都有唯一的一个队列规范，属于同一类的数据包 都将进入该队列，接受相同的调度方式) 。所有的类别都是由一个c l a s s i d 和 i n t e r n a l l d 来标识的。其中i n t e r n a l l d 由排队策略分配，内核通过它来识别一个 类，而c l a s s l d 则由用户分配。多个。c l a s s i d 可能对应一个i n t e r n a l i d ， c l a s s l d 是一个3 2 位的无符号整数，表示为一组主序号和次序号的句柄，即 。其中m a j o r ( 主序号) 对应于一个队列的实例队 列和类就是通过主序号对应的；m i n o r ( 次序号) 用来标识与该队列关联的不同类。 2 3 2 3 过滤器 过滤就是根据数据包的某些属性将数据包进行分类，可以用来进行数据包分 类的属性有：i p 的源目的端地址、端口号、t o s 值等。如果某个排队策略中含有 多个类，则该排队策略将调用过滤器来决定数据包属于哪个类。目前l i n u x 支持 的过滤器有很多种，这里仅仅介绍其中的几种。 ( 1 ) u 3 2 过滤器 u 3 2 过滤器是目前所能用到的最先进的过滤器它可以根据包的目的地址、目 的端口、源地址、t o s 域等任何数据字段进行分类过滤。u 3 2 过滤器完全是基于哈 希表所以它能够很好地适应于多种过滤规则。u 3 2 过滤器是一张记录表，每个记录 包括两项：选择器和对应的动作。输入的i p 包将按顺序与u 3 2 过滤器记录表中每 个选择器进行比较，直到发现匹配的选择器为止，然后将执行该选择器所对应的 动作。 ( 2 ) 路由分类过滤器 该过滤器根据路由表对数据进行分类。其实现过程为：当一个数据包到达一 个标记有”r o u t e ”的过滤器的时候，将按照路由表内的信息进行分类。 1 0 基于p 2 p 技术q o s 中间件的研究与设计 2 4p 2 p 技术的特点 非中心化( d e c e n t r a l i z a t i o n ) ：网络中的资源和服务分散在所有节点上，信 息的传输和服务的实现都直接在节点之间进行，可以无需中间环节和服务器的介 入，避免了可能的瓶颈。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 网络中，由于信息的传输分散在各节点之间进行而无需经 过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前 解决i n t e r n e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏 在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某 些中继服务器节点。而在p 2 p 中，所有参与者都可以提供中继转发的功能，因而 大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对传 统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点， 更好的实现了整个网络的负载均衡。 2 5p 2 p 网络模型 p 2 p “2 网络是一种具有较高扩展性的分布式系统结构，其对等概念是指网络中 的物理节点在逻辑上具有相同的地位，而并非处理能力的对等。以n a p s t e r 软件 为代表的p 2 p 技术其实质在于将互联网的集中管理模式引向分散管理模式，将内 容从中央单一节点引向网络的边缘，从而充分利用互联网中众多终端节点所蕴涵 第二章研究背景和相关工作 的处理能力和潜在资源。相对于传统的集中式客户服务器( c s ) 模型，p 2 p 弱化了 服务器的概念，系统中的各个节点不再区分服务器和客户端的角色关系，每个节 点既可请求服务，也可提供服务，节点之间可以直接交换资源和服务而不必通过 服务器。 p 2 p 系统最大的特点就是用户之间直接共享资源，其核心技术就是分布式对象 的定位机制，这也是提高网络可扩展性、解决网络带宽被吞噬的关键所在。迄今 为止，p 2 p 网络已经历了三代不同网络模型，各种模型各有优缺点，有的还存在着 本身难以克服的缺陷，因此在目前p 2 p 技术还远未成熟的阶段，各种网络结构依 然能够共存，甚至呈现相互借鉴的形式。 2 6 1 集中目录式结构 集中目录式p 2 p 结构是最早出现的p 2 p 应用模式，因为仍然具有中心化的特点 也被称为非纯粹的p 2 p 结构。用于共享m p 3 音乐文件的n a p s t e r 是其中最典型的 代表，其用户注册与文件检索过程类似于传统的c s 模式，区别在于所有资料并 非存储在服务器上，而是存贮在各个节点中。查询节点根据网络流量和延迟等信 息选择合适的节点建立直接连接，而不必经过中央服务器进行。 2 5 2 纯p 2 p 网络模型 纯p 2 p 模式也被称作广播式的p 2 p 模型。它取消了集中的中央服务器，每个用 户随机接入网络，并与自己相邻的一组邻居节点通过端到端连接构成一个逻辑覆 盖的网络。对等节点之间的内容查询和内容共享都是直接通过相邻节点广播接力 传递，同时每个节点还会记录搜索轨迹，以防止搜索环路的产生。 g n u t e l l a 模型是现在应用最广泛的纯p 2 p 非结构化拓扑结构，它解决了网络 结构中心化的问题，扩展性和容错性较好，但是g n u t e l l a 网络中的搜索算法以泛 洪的方式进行，控制信息的泛滥消耗了大量带宽并很快造成网络拥塞甚至网络的 不稳定。同时，局部性能较差的节点可能会导致g n u t e l l a 网络被分片，从而导致 整个网络的可用性较差，另外这类系统更容易受到垃圾信息，甚至是病毒的恶意 攻击。 2 5 3 混合式网络模型 k a z a a 模型是p 2 p 混合模型的典型代表，它在纯p 2 p 分布式模型基础上引入了 超级节点的概念，综合了集中式p 2 p 快速查找和纯p 2 p 无中心的优势。k a z a a 模型 将节点按能力不同( 计算能力、内存大小、连接带宽、网络滞留时间等) 区分为普 通节点和搜索节点两类( t g 有的进步分为三类节点，其思想本质相同) 。其中搜 基于p 2 p 技术q o s 中间件的研究与设计 索节点与其临近的若干普通节点之间构成一个自治的簇，簇内采用基于集中目录 式的p 2 p 模式，而整个p 2 p 网络中各个不同的簇之间再通过纯p 2 p 的模式将搜索 节点相连起来，甚至也可以在各个搜索节点之间再次选取性能最优的节点，或者 另外引入一新的性能最优的节点作为索引节点来保存整个网络中可以利用的搜索 节点信息，并且负责维护整个网络的结构。 由于普通节点的文件搜索先在本地所属的簇内进行，只有查询结果不充分的时 候，再通过搜索节点之间进行有限的泛洪。这样就极为有效地消除纯p 2 p 结构中 使用泛洪算法带来的网络拥塞、搜索迟缓等不利影响。同时，由于每个簇中的搜 索节点监控着所有普通节点的行为，这也能确保一些恶意的攻击行为能在网络局 部得到控制，并且超级节点的存在也能在一定程度上提高整个网络的负载平衡。 总的来说，基于超级节点的混合式p 2 p 网络结构比以往有较大程度的改进。 然而，由于超级节点本身的脆弱性也可能导致其簇内的节点处于孤立状态，因此 这种局部索引的方法仍然存在一定的局限性。这导致了结构化的p 2 p 网络模型的 出现。 2 5 4 结构化网络模型 所谓结构化与非结构化模型的根本区别在于每个节点所维护的邻居是否能够 按照某种全局方式组织起来以利于快速查找。结构化p 2 p 模式是一种采用纯分布 式的消息传递机制和根据关键字进行查找的定位服务，目前的主流方法是采用分 布式哈希表( d h t n 3 m 6 ”脚。1 1 蚴d i s t r i b u t e dh a s ht a b l e ) 技术，这也是目前 扩展性最好的p 2 p 路由方式之一。由于d h t 各节点并不需要维护整个网络的信息， 只在节点中存储其临近的后继节点信息，因此较少的路由信息就可以有效地实现 到达目标节点，同时又取消了泛洪算法。该模型有效地减少了节点信息的发送数 量，从而增强了p 2 p 网络的扩展性。同时，出于冗余度以及延时的考虑，大部分 d h t 总是在节点的虚拟标识与关键字最接近的节点上复制备份冗余信息，这样也避 免了单一节点失效的问题。 目前基于d h t 的代表性的研究项目主要包括加州大学伯克利分校的c a n 哺1 项目 和t a p e s t r y 项目，麻省理工学院的c h o r d “”1 项目，以及微软研究院的p a s t r y 啪j 这些系统一般都假定节点具有相同的能力，这对于规模较小的系统较为有效。但 这种假设并不适合大规模的i n t e r n e t 部署。同时基于d h t 的拓扑维护和修复算法 也比g n u t e l l a 模型和k a z a a 模型等无结构的系统要复杂得多，甚至在c h o r d 项目 中产生了“绕路”的问题。事实上，目前大量实际应用还大都是基于无结构的拓 扑和泛洪广播机制，现在大多采用d h t 方式的p 2 p 系统缺乏在i n t e r n e t 中大规模 真实部署的实例，成功应用还比较少见。 第二章研究背景和相关工作 2 6 小结 由上述可以发现，现有o o s 的研究主要集中在改变网络框架上，即试图从根本 上解决i p 网络o o s 问题，而在当前i n t e r n e t 环境下，这些很难一蹴而就，因此 很大豹尴尬是q o s 研究做了很多，却始终发挥不了作用，因此，如何在现有条件 下利用现有技术实现o o s 才是我们研究的关键。结构化p 2 p 技术由于对节点的管 理采用一种全局性的方式，在路由选择方面具有较大优势，但是，针对本文提出 的端到端通信而言，维护一个结构化p 2 p 网络代价过高，因此，本文的端到端覆 盖网采用非结构化p 2 p 技术。 1 4 基于p 2 p 技术q 0 s 中间件的研究与设计 第三章o o s 中间件底层端到端覆盖网的设计 覆盖网( o v e r l a yn c t 、) l ，o f k 【矧吲【3 1 】) 是p 2 p 节点相互协作的基础，一般指 节点互联的拓扑结构和节点在与相邻节点保持连接时的行为规范。覆盖网可以用 一个图结构来表示，节点由图中的顶点表示，如果两个节点间有网络连接，则在 图中对应的顶点间连边，这两个节点互相称为邻居节点。那么覆盖网的设计目标 就是，为p 2 p 网络中的顶点构造一个连通的图结构，并在其上建立了特定的节点 逻辑组织，这个逻辑组织决定了节点间的互连方式。除此以外，覆盖网协议决定 路由算法。所谓路由( 搜索) 算法是指从一个节点出发，沿着节点之间的连接进 行消息转发，最终到达目标节点或实现路由目标的过程。覆盏网结构与路由算法 一般是一一对应的，特定的结构决定了其上的路由特性和搜索性能。 本文所设计的端到端覆盖网为了避免不必要的计算，所生成的拓扑结构仅服务 于一次具体的端到端通信，在通信开始时动态生成建立，通信结束后拆除。上层 应用节点从作为基础设施的覆盖网得到一些可以连接的邻居节点，并根据网络状 况更新这个列表，动态选择邻居节点进行数据发送。因此，本文端到端覆盖网的 设计目标是：在一个动态、异构的网络环境中，以较低的开销为节点提供高效的 节点信息收集、信息查询和数据发送的服务，尽