（计算机软件与理论专业论文）son中自组织行为与自适应路由协议的设计与实现.pdf

at h e s i sf o rt h ed e g r e eo f m a s t e ri nc o m p u t e rs 。脚a r ea n d t h e o q ii lrlri iii i i i l lil l u l y 18 4 3 0 14 d e s i g na n di m p l e m e n t a t i o no f s e l f - o r g a n i z i n g b e h a v i o r sa n d a d a p t i v er o u t i n gp r o t o c o li n s o n b yf uy a o s u p e r v i s o r ：p r o f e s s o rw a n gx i n g w e i 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 ， 7 、一1 k 、 p 夕 ； 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 - - o , - _ k 思。 学位论文作者签名：付盘一 日期：2 , o o g 石 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年一年口一年半口两年口 学位论文作者签名：付遥_ 签字日期： 枷多p 乡 聊虢住别 签字日期：矽 、n 7 v 1 东北大学硕士学位论文摘要 s o n 中自组织行为与自适应路由协议的设计与实现 摘要 计算机网络和通信技术的发展不断改变着人们工作和生活的方式。自组织网络概念 的提出使网络具备更加灵活、快速、可伸缩的组网能力。i p v 6 是n g i 的核心协议，但 现有基于i p v 6 的路由协议不能有效地提供q o s 保证，同时自组织网络中的分布式路由 。 算法又难于部署在实际网络中。为此，需要设计兼容i p v 6 协议族的自组织行为与自适 应路由协议，捆绑分布式路由算法并提供q o s 保证，能够快速、有效地部署于实际网络。 本文设计与实现了自组织网络中的自组织行为协议与自适应路由协议。通过扩展 o s p f v 3 协议，设计自组织行为协议，加入自组织网络中节点所具有的生物特性行为。 通过扩展o s p f v 3 协议和b g p 4 + 协议，设计自适应单播路由协议，引入q o s 状态报文， 建立邻居信息表以实现域内和域间q o s 信息的收集与存储。以自适应单播路由协议为基 础，设计自适应组播路由协议，对m l d v 2 和p i m 。s s m 协议进行业务自适应扩展，实 现基于i p v 6 的业务自适应源特定组播；为了提供组播q o s 控制，扩展了r s v p 协议， 设计了自适应分层组播和流量控制机制，基于博弈分析确定为用户分配的带宽量，优化 网络带宽利用率。 对本文设计的自组织网络中自组织行为与自适应路由协议进行实现和部署。通过基 于i p v 6 的q o s 控制视频会议和视频直播系统，测试了该路由协议的互操作性、实用性 、 和有效性。实验结果表明，本文设计的路由协议具有良好的性能。 i l 关键词：自组织网络；自组织行为；服务质量；协议；单播；组播 一i i ， ，a ! = i r 、 、二 东北大学硕士学位论文 d e s i g na n di m p l e m e n t a t i o no fs e l f - o r g a n i z i n gb e h a v i o r sa n d a d a p t i v er o u t i n gp r o t o c o li ns o n a b s t r a c t t h ed e v e l o p m e n to fc o m p u t e rn e t w o r k a n dc o m m u n i c a t i o n t e c h n o l o g yh a sb e e n c h a n g i n gp e o p l e sw a yo fl i f ea n dw o r kg r a d u a l l y t h ec o n c e p to fs o n ( s e l f - o r g a n i z i n g n e t w o r k ) i n s u r e st h en e t w o r kh a sf a s t e r , m o r ef l e x i b l ea n dm o r er e t r a c t a b l eo r g a n i z i n g c a p a b i l i t y i p v 6i st h ec o r ep r o t o c o lo fn g i h o w e v e r ，c u r r e n tp r o t o c o l sb a s e do ni p v 6d o n t s u p p o aq o s ，a n dd i s t r i b u t e dr o u t i n ga l g o r i t h m si ns o na l ed i f f i c u l tt ob ed e p l o y e di na c t u a l n e t w o r k t h u s ，t h ed e s i g no fs e l f - o r g a n i z i n gb e h a v i o r sa n da d a p t i v er o u t i n gp r o t o c o ls h o u l d b ec o m p a t i b l ew i t hi p v 6 p r o t o c o lf a m i l i e s ，b o n dw i t hd i s t r i b u t e dr o u t ea l g o r i t h m s ，a n d g u a r a n t e e dw i t hq o s ，w h i c hc o u l db ed e p l o y e di na c t u a ln e t w o r kf l e e t l ya n de a s i l y i nt h i st h e s i s ，s e l f - o r g a n i z i n gb e h a v i o r sa n da d a p t i v er o u t i n gp r o t o c o li ns o na r e d e s i g n e da n di m p l e m e n t e d t h r o u g he x t e n d i n go s p f v 3p r o t o c o la n dd e s i g n i n g s e l f - o r g a n i z i n gb e h a v i o r sa n da d a p t i v er o u t i n gp r o t o c o l ，b i o l o g i c a lb e h a v i o r so fn o d e si n s o na r ea p p e n d e d t h r o u g he x t e n d i n go s p f v 3a n db g p 4 + p r o t o c o l ，d e s i g n i n ga d a p t i v e u n i c a s tr o u t i n gp r o t o c o l ，d e f i n i n gq o ss t a t em e s s a g ea n dc r e a t i n gn e i g h b o ri n f o r m a t i o nt a b l e ， q o si n f o r m a t i o nw i t h i no ra m o n ga u t o n o m o u ss y s t e m si sc o l l e c t e da n ds t o r e d t h r o u g h d e s i g n i n ga na d a p t i v em u l t i c a s tr o u t i n gp r o t o c o lb a s e do nt h ea d a p t i v eu n i c a s tr o u t i n g p r o t o c o l ，m l d v 2p r o t o c o la n dp i m - s s mp r o t o c o la r ee x t e n d e dt oi m p l e m e n tt h ea d a p t i v e s e r v i c eo fs o u r c es p e c i f i cm u l t i c a s tr o u t i n gb a s e do ni p v 6 b ye x t e n d i n gr s v pp r o t o c o l ，a m u l t i l a y e r e dm u l t i c a s ta n dt r a f f i cc o n t r o ls c h e m ei sd e s i g n e dt op r o v i d eq o sc o n t r 0 1 i t d e t e r m i n e st h ea l l o c a t e db a n d w i d t hf o rt h eu s e rb yg a m i n ga n a l y s i s ，o p t i m i z i n gt h e n e t w o r kb a n d w i d t hu t i l i z a t i o nr a t i o t h es e l f - o r g a n i z i n gb e h a v i o r sa n da d a p t i v er o u t i n gp r o t o c o ld e s i g n e di nt h i st h e s i sa r e i m p l e m e n t e da n dd e p l o y e d t h ei n t e r o p e r a t i o n a l i t y , p r a c t i c a l i t ya n de f f e c t i v i t yo ft h e d e s i g n e dr o u t i n gp r o t o c o la r et e s t e d 、斫t i la ni p v 6b a s e dq o sc o n t r o lv i d e oc o n f e r e n c ea n d v i d e ob r o a d c a s ts y s t e m e x p e r i m e n tr e s u l t ss h o wt h a tt h ed e s i g n e dr o u t i n gp r o t o c o lh a sb e t t e r c a p a b i l i t y k e y w o r d s ：s e l f - o r g a n i z i n gn e t w o r k ；s e l f - o r g a n i z i n gb e h a v i o r ；q u a l i t yo fs e r v i c e ；p r o t o c o l ； u n i c a s t ；m u l t i c a s t i i i 一 、，声 ，。 柙 、， 一 7 ： 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第1 章绪论。1 1 1 自组织网络1 1 1 1 自组织网络的概念和特点1 1 1 2 自组织网络与传统计算机网络的区别2 1 1 3 自组织网络面临的问题2 1 2m v 6 协议族3 1 2 1i p v 6 简介3 1 2 2p v 6 单播路由协议7 1 2 3i p v 6 组播路由协议7 1 2 4i p v 6 组管理协议9 1 3 课题来源j 1 0 第2 章网络自组织行为协议设计1l 2 1 网络模型l1 2 2 业务q o s 特性1 2 2 3 自组织行为协议设计1 3 2 3 1 网络节点对周围环境的感知1 4 2 3 2 网络节点间关系的建立与消除1 6 2 3 3 网络节点的迁移1 7 2 3 4 网络节点的复制2 l 2 3 5 网络节点的休眠、苏醒与唤醒2 2 2 3 6 网络节点的再生2 3 2 3 7 网络节点的死亡与救醒2 3 第3 章自适应路由协议设计2 5 3 1 自适应单播路由协议设计。2 5 3 1 1 域内o s p f v 3 路由协议扩展2 5 一一 ；q - i【jii【fll 东北大学硕士学位论文目录 3 1 2 域间b g p 4 + 路由协议扩展3 0 3 1 3 邻居信息表的设计3 3 3 1 4 单播路由表的设计3 4 3 1 5 节点状态变迁图及协议流程3 5 3 1 6 与标准协议族的兼容性3 9 3 2 自适应组播路由协议设计4 0 3 2 1 组播成员管理4 0 3 2 2 业务自适应组播路由4 1 3 2 3 博弈分析4 2 3 2 4 带宽分配4 3 3 2 5 自适应分层组播4 6 3 2 6 组播路由表的设计5 0 3 2 7 组播树建立5 2 3 2 8 组播成员加入与退出5 3 3 2 9 组播树重构5 6 3 2 1 0 与标准协议的兼容性5 8 3 3 重路由协议设计5 9 第4 章协议实现与性能评价6 1 4 1 开发平台6 1 4 1 1 路由器平台6 1 4 1 2 网络平台6 l 4 2 协议实现6 2 4 2 1 自组织行为协议实现6 2 4 2 2 自适应单播路由协议实现6 3 4 2 3 自适应组播路由协议实现6 7 4 3 运行实例7 0 4 3 1 视频会议。7 0 4 3 2 视频直播7 2 4 3 3 路由表7 3 4 4 性能评价7 4 4 4 1 自组织行为协议性能评价7 4 一v 一 一 ，_ 门 i 东北大学硕士学位论文目录 4 4 - 2 自适应单播路由协议性能评价7 6 4 4 3 自适应组播路由协议性能评价7 8 第5 章结束语8l 参考文献。8 3 致谢8 7 攻读硕士学位期间发表的论文。8 9 一v i 一 。、 1 i；ill 一 _ 一 、 l h 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 自组织网络 1 1 1 自组织网络的概念和特点 计算机网络和通信技术的发展不断改变着人们工作和生活的方式。具有更大带宽、 融合诸多类型有线和无线网络的下一代互联网n g i ( n e x tg e n e r a t i o ni n t e m e t ) 【1 】为人们 提供了更灵活、更多样、更高服务质量q o s ( q u a l i t yo f s e r v i c e ) 的网络服务1 2 1 。但是， n g i 的异构性、移动性、不稳定性等又为提供可靠q o s 带来困难，目前i n t e m e t 中许多 机制、协议需要重新考虑和设计。 下一代互联网具有大规模、异构和动态的特点。随着互联网的发展，网络规模的不 断扩大，网络节点数目的不断增多，往往在一个网络中可能包含上百万个具有不同的计 算和连网能力的节点，而且这些节点也可以动态地加入或离开网络。基于网络的这种大 规模、异构和动态的特点，相应的网络服务或应用需要具有如下特点： ( 1 ) 可伸缩性自动扩展大规模节点的能力； ( 2 ) 自适应性网络能够自发地适应网络环境的变化； ( 3 ) 可生存性在动态的网络环境中持续地提供服务的能力，尤其是在可能发生 网络中断的情况下； ( 4 ) 简单自治性在理想情况下，为了减少运作和维护的费用，这种网络应当能 够在没有人为管理和干预的情况下自动地运作【3 1 。 在这样的背景下，人们通过自然界中群体智能现象的启发( 简单智能的主体通过合 作表现出复杂智能行为的特性) 【4 】，比如自组织、涌现、冗余、自然选择和多样性【5 1 等， 提出自组织网络( s e l f - o r g a n i z i n gn e t w o r k s ，s o n ) 1 6 】的概念，并对其进行研究。 自组织网络的特点类似于生物灵感网络所具备的生物网络结构阴，该网络不需全局 协调与通信，由自治个体组织成群体，通过本地的局部环境交互，根据局部环境动态调 整全局属性和行为，使网络具有可伸缩性、自适应性、可生存可用性以及简单自治性f 8 】， 而网络中的单个节点也类似群体智能中个体一样，具备个体或个体与个体之间的能量交 换、迁移、复制、繁殖、死亡、冬眠、建立关系、感知环境等特性，从而使网络具有良 好的适应性和健壮性。 一1 一 r 和技术上的问题： ( 1 ) 路由系统建模 基于生物灵感联网思想，引入群体智能知识，建模s o n 路由机制：每个路由节点 都具有局部视图，模拟人工自治生命体的简单行为。路由节点通过与其局部环境交互而 实现彼此之间的隐式协调，通过彼此之间的对等交互而完成全局寻路，从而使路由系统 具备群体的“自组织、涌现、冗余、自然选择和多样性等全局属性【1 3 】，满足s o n 路 由的可伸缩、自适应、可生存、可用、简单与自治等需要，同时最小化路由节点需维护 的状态。 ( 2 ) 路由节点局部视图建模 一2 一 * 必 _ 东北大学硕士学位论文第1 章绪论 。 引入模糊数学与微观经济学等相关知识，描述链路参数( 如链路类型、总带宽、可 用带宽、延迟、出错率和成本等) 、链路资源分配规则与策略、支持容错和负载均衡等 实现的链路优选规则、网络提供方与用户方在链路上的效用计算方法与平衡策略等建立 局部路由视图所需的信息、规则与策略等。 ( 3 ) 路由节点局部行为建模 引入生物学等方面相关知识，模拟人工自治生命体的局部环境感知、与局部环境之 间以及彼此之间的关系建立、与局部环境之间以及彼此之间的能量交换、迁徙、复制、 再生、休眠以及死亡等行为，完成局部行为建模，适应s o n 大规模【1 4 】、异构与动态环 境的需要。 ( 4 ) q o s 的需求 用户( 应用) 对q o s 的要求不同，网络保证q o s 的能力也不同。自组织网络环境 下要让各个网络很好的协作，要能很好的选择承载业务的网络以满足应用，尤其是多媒 体应用的q o s 。 ( 5 ) 资源管理 过去的资源管理都是管理同种网络中的资源。在自组织网络下，网络中的各个节点 要自发的管理和协调多种网络的资源，满足用户需求，均衡网络负载，提高网络运营效 率和性能。 ( 6 ) 公平性问题 用户、运营商都是网络通信的参与者。网络必须保证用户的付费是“值得的 ，又 要保证运营商是“有利可图的”，以保证会有用户愿意使用网络服务，运营商也愿意提 供网络服务。 1 2i p v 6 协议族 1 。2 1i p v 6 简介 1 2 1 1i p v 6 特点 目前的i n t e m e t 主要是基于i p v 4 协议的。这协议的成功促成了i n t e m e t 的迅速发 展。但是，随着i n t e m e t 的发展，i p v 4 潜在的问题也日益显现出来。早在1 9 9 0 年，研究 t c p i p 的专家们就已察觉出它潜伏的三大危机：地址枯竭、网络号匮乏、路由表急剧膨 胀，如不采取措旌，i n t e m e t 可能在地址枯竭之前就会瘫痪，i p v 4 已经直接制约i n t e m e t 的发展。为了从根本上克服上述三大危机，需要一个全新的n g i 协议来代替现有的i p v 4 3 一 东北大学硕士学位论文第1 章绪论 协议。 为此，匝t f 下一代网络协议i p n g 工作组于1 9 9 4 年9 月提出“t h er e c o m m e n d a t i o n f o rt h ei pn e x tg e n e r a t i o np r o t o c o l ”草案，并在1 9 9 5 年底确定i p n g 协议规范，成为口 版本6 ，即i p v 6 。1 9 9 6 年i p v 6 的基本协议规范发表，1 9 9 8 年发表了i p v 6 修订版。 与i p v 4 相比，i p v 6 具有如下主要特剧1 5 】： ( 1 ) l v 6 提供的地址长度由i p v 4 的3 2 位扩展到t 2 8 位，几乎可以不受限制地提 供地址。 ( 2 ) i p v 6 采用类似无类域间路由c i d r ( 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 ) 的地址聚 类机制层次的地址结构。网络前缀可以分为多个层次，可以定义非常灵活的地址层次结 构，而且同一层次上的多个网络在上层路由器中表示为一个统一的网络前缀，可以明显 减少路由器必须维护的路由表项。 ( 3 ) i p v 6 数据包可以远远超过6 4 k b ，采用了简化的报头定长结构和更合理的分段 方法，可以使路由器加快数据包的处理速度，提高了转发效率，从而提高了网络的整体 吞吐量。 ( 4 ) i p v 6 报头中提供业务级别和流标记字段，允许发送业务流的源节点在数据包 上加上标记，通过路由器的配置，可以识别和分开处理任何数据流，实现优先级控制和 q o s 保证。 ( 5 ) i p v 6 采用i p s e c ( i ps e c u r i t y ) ，实现了数据包来源认证、数据加密、数据完整 性、抗数据重发攻击等，且定义了封装安全性载荷协议、验证头协议和密钥交换协议等， 可以为上层协议和应用提供有效的端到端安全保证。 ( 6 ) i p v 6 限定了路由器范围，可以区分永久性与临时性地址，更有利于组播功能 的实现。 ( 7 ) i p v 6 为主机接口提供不同类型的地址配置，如全球地址、全球单播地址、区 域地址、链路本地地址、地区本地地址、广播地址、组播地址、传播地址、移动地址、 家乡地址等。通过启动动态主机配置协议来支持“即插即用 网络连接，允许从特殊的 启动协议服务器或动态主机配置协议服务器获取配置信息与网络和子网信息，构造有效 的链路地址。 i p v 6 作为新一代的网络互联协议，其先进性和灵活性已经得到了越来越多的认可， 使其成为构筑n g i 的重要基础，建设基于i p v 6 的n g i 已成为重要的发展方向。 一4 一 东北大学硕士学位论文第1 章绪论 1 2 1 2i p v 6 协议简介 i p v 6 作为i p 协议的新版本，其根本目的是继承和取代m v 4 。i p v 6 相对i p v 4 而言具 有极大扩展的地址空间和更加结构化的路由层次。i p v 6 的报头简化了基本报头结构，并 增加了可选的扩展报头【1 6 】。i p v 6 报文头格式如图1 1 所示。 03l l 1 52 33 l 版本类别流标签 净荷长度下一个头跳极限 源i p 地址 目的i p 地址 图1 1i p v 6 报文头格式 f i g 1 1i p v 6m e s s a g eh e a d e rf o r m a t 在r f c 2 3 7 3 中定义各字段含义如下： ( 1 ) 版本：长度为4 位，对于i p v 6 ，该字段必须为6 。 ( 2 ) 类别：长度为8 位，指明为该包提供某种“区分服务 。最初定义该字段只有 4 位，在最新的i p v 6 草案中，称之为“业务流类别 。该字段的定义独立于i p v 6 ，目前 尚未在任何r f c 中定义。该字段的默认值是全o 。 ( 3 ) 流标签：长度为2 0 位，指定发送数据的序列。 ( 4 ) 净荷长度：1 6 位无符号整数，以字节为单位记录i p v 6 的数据报负载，即除去 i p v 6 报头自身长度以外的分组长度。一个i p v 6 数据报可以容纳6 5 5 3 5 字节的数据。 ( 5 ) 下一个头：这个字段指出了i p v 6 头后所跟的头字段中的协议类型。与i p v 6 协 议字段类似，可以用来指出高层是t c p 还是u d p ，也可以用来指明i p v 6 扩展头的存在。 ( 6 ) 跳极限：8 位无符号整数。在每个传输此包的节点处递减