（计算机软件与理论专业论文）基于动态聚合树模型的网络路由协议研究.pdf

大连理工大学硕士学位论文 摘要 本文围绕目前下一代互联网发展中亟待解决的多维可扩展路由体系结构的问题展 开，根据下一代互联网的发展趋势，建立具有多维可扩展性的路由模型及协议，以期能 够满足网络中多服务种类、多数据流类型对网络服务质量、流量调度等方面的需求。本 文选择互联网在空间和时间两个维度上的路由模型作为研究的切入点，分别针对下一代 互联网在空间维度上的大规模特点和在时间维度上的动态性特点提出了全新的路由解 决方案，并且通过模拟仿真实验与传统路由技术进行了性能的对比。 首先，本文针对下一代互联网大规模的特性，提出了基于链路通讯能力的聚合树路 由协议。通过对聚合树路由协议的通讯复杂度分析和建模特点的分析，从理论上论证了 聚合树路由协议具有高准确率和高收敛性能的原因，为设计与实现具有高效率、低空间 复杂性的最佳路由协议奠定了理论基础。 其次，本文对下一代互联网的动态特性进行了研究，针对网络链路状态变化量的不 同，提出了基于增量思想的增量路由寻径算法。该增量路由寻径算法所包含的三个部分 ( 链路删除算法、链路增加算法和链路权值更新算法) 可以有效地处理网络拓扑结构两 方面的变化链路权值随时间变化和拓扑结构随时问变化。 再次，本文对下一代互联网的大规模性和动态性两种路由模型的融合过程进行了研 究，将空间维度和时间维度上设计的新模型进行融合，修改了大量两种模型互相冲突的 机制，设计了动态聚合树模型。该模型既能够为网络在空间规模上提供良好的扩展性， 同时又能及时地反映网络状态的动态变化，提供了一个可以综合考虑空间和时间的多维 模型。 最后，文章将动态聚合树模型分别模拟仿真应用在互联网和无线a dh o c 网络中， 并且分别与传统的网络路由协议做了比较，得到了更优的性能和效果。并且针对实验结 果总结了动态聚合树模型的优缺点，分析了大规模性和动态性路由模型在融合过程中出 现的难点和可能解决的办法。 关键词：动态拓扑变化；聚合树路由协议；增量路由寻径算法：动态聚合树模型 大连理工大学硕士学位论文 r e s e a r c ho f n e t w o r k sr o u t i n gp r o t o c o l sb a s e do nd y n a m i ca g g r e g a t i o n t t e em o d e l s a b s t r a c t t h i sp a p e rf o c u s e so i lt h ep r o b l e mo ft h eu r g e n te x t e n d i n gr o u t i n gs y s t e ms t r u c t u r ei n n e x tg e n e r a t i o ni n t e m e t ( n g i ) b a s e do nt h ed e v e l o p m e n tc u r r e n to f n g i ，i t sr o u t i n gm o d e l n e e d h a v et h e c h a r a c t e r i s t i c so fm o i et h a no n ed i m e n s i o n a l i t ya n dc a nb ee x t e n d e dt o d i f f e r e n tn e t w o r k s t h i st h e s i s d e s i g n sn o v e lr o u t i n gm o d e l sa sw e l la st h er e l a t e dr o u t i n g p r o t o c o l sb a s e do ut h e m t h ep e r f o r m a n c ee v a l u a t i o n sa r ea c h i e v e db ys i m u l a t i o n s f i r s t ，f o rt h el a r g es c a l ec h a r a c t e ro fn g i ，t h et h e s i sp r e s e n t st h ea g g r e g a t i o n t r e e r o u t i n gm o d e la n dt h et h e o r e mo fr o u t i n go p t i m i z a t i o n t h er o u t i n gp r o t o c o lb a s e do n a g g r e g a t i o n t r e er o u t i n gm o d e li n c l u d e s t h e a g g r e g a t i o n t r e ec l u s t e r i n ga l g o r i t h m ，t h e a g g r e g a t i o n - t r e er o u t i n ga l g o r i t h m a n dt h e a g g r e g a t i o n s c h e m ef o r r o u t i n g c o n t r o l i n f o r m a t i o n i ti sp r o v e di nt h e o r yt h a ta g g r e g a t i o n t r e er o u t i n gm o d e lh a sah i g hr o u t i n g a c c u r a c ya n dt h el o wc o m m u n i c a t i o nc o m p l e x i t y s e c o n d ，f o rt h ed y n a m i cc h a r a c t e ro f n g l ，t h es o l u t i o ni st h ei n c r e m e n t a lr o u t i n gm o d e l t h i sm o d e lu s et h en o v e li n c r e m e n ta l g o r i t h m ，w h i c hi sb a s e do nt h eu n d e r s t a n d i n go ft h e d y n a m i ct o p o l o g yu p d a t ep r o c e d u r ea p p l i c a b l e i n l a r g e s c a l en e t w o r k st oa v o i dt h e d i s a d v a n t a g e s ( e g r e d u n d a n tc o m p u t a t i o n ) c a u s e db ye x i s t i n gu p d a t ea l g o r i t h m s t h e e f f i c i e n c yo fo u ra l g o r i t h mi si m p r o v e db e c a u s ei to n l yp a y sa t t e n t i o nt ot h el i n k sr e a l l yc o u n t f o rt h eu p d a t ep r o c e s s t h i r d ，t w om o d e l sm e n t i o n e di nt h ef o r m e r s e c t i o na r eu n i t e dt o g e n e r a t et h e c o m b i n a t i o nm o d e l d y n a m i ca g g r e g a t i o n - t r e em o d e l t h i sm o d e lh a se x t e n d e dt h el a r g e s p a c es c a l ed i m e n s i o nf o rn e t w o r k s ，a n da l s oc a nr e f l e c tt h ed y n a m i cc h a n g e so fn e t w o r k s t a t e si ng o o dt i m e ，s oi tp r o v i d e sam u l t i d i m e n s i o n a lm o d e lt h a tc a nc o n s i d e rb o t ht h es p a c e c h a r a c t e ra n dt i m ec h a r a c t e ro f n g i l a s t ，t h en o v e ld y n a m i ca g g r e g a t i o n - t r e em o d e li sa p p l i e dt oi n t e m e ta n dw i r e l e s sa d h o en e t w o r k s ，a n di ss i m u l a t e du n d e rn s 2p l a t f o r m b a s e do nt h er e s u l t so fs i m u l a t i o n ，t h e d y n a m i ca g g r e g a t i o n t r e em o d e li sa n a l y z e di nt h et i m e ，c o m m u n i c a t i o nc o m p l e x i t ya n d t h r o u g h p u t ，a n di ss e p a r a t e l yc o m p a r e di ns e v e r a lp e r f o r m a n c e sw i t ht h ee x i s t i n gp r o t o c o l s a sa r e s u l t ，t h ep r o b l e ma n dp r o s p e c to f t h ec o m b i n a t i o nm o d e l i sa n a l y z e da n de v a l u a t e d k e yw o r d s ：d y n a m i ct o p o l o g yc h a n g e s ；a g g r e g a t i o nt r e ep r o t o c o l ；i n c r e m e n t a l r o u t i n ga l g o r i t h m ：d y n a m i ca g g r e g a t i o nt r e em o d e l 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：建宝宝日期：坦：! 兰! 筌 大连理工大学硕上研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名： 建宝宝 盗! 昭 型皇年l 月堕日 大连理工大学硕士学位论文 1 绪论 1 1 研究背景及意义 1 1 1 下一代互联网的介绍及所面临的问题 随着信息通信网络用户的爆炸性增长，电子商务多媒体业务、个人网络电视电话等 公众服务项目的增多，使得网上的信息量猛增，现有的网络基础设施和所采取的传输管 理技术已经远远不能满足人们的要求。网络阻塞了不同类型网络间的互连互通，成为用 户和运营商最头疼的问题。于是建造新一代公用通信网，即下一代互联网n g i 的要求被 提了出来 ”。 下一代互联n n g i ( n e x tg e n e r a t i o ni n t e m e t ) 指的是比现在的互联网具有更快的传输 速率、更强的功能、更多的网址和更好的安全性能，能基本达到信息高速公路计划目标 的新一代互联网。它的发展经历了如下过程：首先在1 9 9 5 年，由美国科学基金会( n s f ) 资助下一代因特网m g i ) 研究计划，建立t n g i 主干网( v b n s ) 。1 9 9 6 年1 0 月，美国政府 出面倡议，由多个机构共同研究，主要涉及协议、开发、部署高端试验网等。1 9 9 8 年， 美国大学先进网络联盟m c a i d ) 成立，设立i n t e m e t 2 研究计划，建立主干网a b i l e n e 。同 年，亚太地区先进网络组织( a p a n ) 成立，建立a p a n 主干网。2 0 0 1 年，欧共体资助下一 代因特网研究计划，建立主干网g e a n t 。这样，全球就初步建成了大规模先进网络的 试验网，攻克了一些网络关键技术，突破了一些网络设备和应用技术，并促进了标准化 的发展 2 1 。 2 0 0 2 年以来，国际n g i 的发展非常迅速，美国的n g i 主干网a b i l e n e 和欧洲的n g i 主 干网g e a n t ，在带宽方面不断升级，并且推出了向新一代的互联网协议i p v 6 发展的政策， 大力开展技术试验和应用试验。i n t e m e t 2 和g e a n t 在2 0 0 2 年完成了5 g b i t s 的高速互联。 美国的i n t e r n e t 2 还与欧洲的g e a n t 以及亚太地区的a p a n 发起“全球高速因特网g t r n ” 计划，推动全球n g i 的研究与开发。在我国，n g i 的研究与发展很快，已经有了重要进 展。中国高速互联研究试验网于2 0 0 1 年7 月建成，是n g i 试验床。在国内连接了清华、北 大、北邮、北航、中科院计算机网络信息中心，国家自然科学基金委员会等单位的节点。 在国际上，也与国际n g i 交换中心和亚太地区高速交换中心完成了互联 3 1 。 目前，下一代互联网发展过程中主要应该解决“社会对下一代互联网应用需求的不 断增长与网络理论技术本身发展不充分之间的矛盾”，这是下一代互联网发展中所面临 的基础矛盾和发展瓶颈。 社会对下一代互联网应用需求主要表现在以“更大、更快、更及时、更方便、更安 韩宁宁：基于动态聚合树模型的网络路山协议研究 全、更可管理和更有效”为标志的新一代互联网发展：应具有巨大的地址空间，能够有 效容纳网络的高速发展；网络的数据传输率要大幅度提高，以适应多媒体数据流的要求； 在路由结构上必须支持组播和面向服务质量控制的传输机制；需要支持更方便有效的接 入方式；需要支持以无线网和移动电话网为主的异构网络融合；需要提高网络服务的可 靠性、信息的安全性并且有很强的抗攻击能力；需要一个更加灵活有力的管理机制，对 于网络中的端到端的行为、骨干网的流量调整均需提供高效的管理；提供类似电信网络 的精确计费手段，提供合理的互联网运营盈利模式【4 j 。 面对这些发展需求，仅在原有互联网模型的基础上升级i p 协议是远远不够的。要满 足下一代网络平台发展的多种需求，就要在互联网体系结构方面研究新模型、新机制， 以期能够从统计学、数学等基础学科的角度对网络行为进行建模，创建全新的适合互联 网发展的体系结构，以及设计适应于新的网络体系结构的路由选择协议扣j 。 目前，发展下一代互联网络的技术所面临的基本问题主要体现在以下四个方面： 第一，网络体系结构本身的多维可扩展性很难解决 6 1 。互联网传统的体系模型仅考 虑到网络在联通方面的扩展性，未能在其它维度上给出可扩展性高的路由模型，主要表 现在：随着网络规模的扩大，尽力而为的路由结构将面对越来越大自治域系统和路由表 长度，传统路由基础理论在路由表的快速查找、路由信息的聚合等方面已捉襟见肘，面 向网络空间维度的路由模型己成为研究的热点领域：随着互联网和以无线网、移动电话 网为代表的电信网络的融合，网络动态行为特征己逐步成为下一代互联网的标志性特 征。传统路由理论，对于动态的网络行为采取启发式的算法，对网络链路、节点的动态 行为规律不予理会，其结果导致路由机制对网络状态的动态变化反应迟缓甚至错误、路 由的频繁重新计算消耗了大量的计算和存储资源。面对网络的强动态特性，传统模型及 方法已力不从心，建立一种能够准确感知网络状态动态变化并迅速进行路由调度的路由 模型成为研究的必由之路；随着网络服务和数据类型的增加，数据对路由的质量要求在 提高，用传统路由方法保证服务质量的难度很大。许多基于传统路由模型的q o s 路由算 法都只能在特定的条件下对服务质量进行局部的优化，见效甚微。种清晰的解决方案 就是在服务维度新建路由模型，从基础上解决传统路由结构忽视服务质量维度信息的设 计缺陷，m p l s 技术就是这方向上成熟的研究成果。 第二，基于分组交换的互联网络的流量模型和行为模型还没有得到很好的研辩6 1 。 流量模型的缺乏，导致互联网管理人员的工作缺乏有力的流量控制和管理理论的指导， 只能凭借经验完成流量调度、接入控制、服务质量控制等重要的工作，这也远远不能满 足下一代互联网更方便、更可管理和更有效的发展目标。 第三，互联网络作为一个巨大的人工系统，有其固有的脆弱性。从规模上看互联网 大连理工大学硕士学位论文 的用户数量巨大且不断增长；从网络协议栈角度看，无论在垂直方向还是在水平方向上， 网络协议都呈现出多样化的特点，这大大增加了网络中通讯的复杂程度和难度。如何从 复杂巨系统的角度对网络的复杂性和脆弱性进行描述和保护，已经成为新的基础理论研 究的关键口1 。 第四，用户和服务提供者对服务需求的复杂性和多样性使得互联网运营商在如何构 建大规模互联网服务方面缺乏指导。 如何根据下一代互联网的体系结构建立可扩展性强的服务模式，如何快速灵活的为 用户提供具有良好互操作性和高性能的服务，如何对现有的服务模型做出调整，如何对 服务进行有效的管理，都是急需互联网基础理论的研究和创新。 1 1 2 下一代互联网的多维可扩展问题的研究 近年来，发展下一代互联网络的技术所面临的第一个问题中的“如何解决下一代互 联网体系结构的多维可扩展性问题”已经成为目前国内外学者重点研究的方向，大量深 入的对多维可扩展性网络体系的研究，以及运用在这一体系结构中的路由协议的提出， 为下一代互联网络的进一步发展奠定了理论基础【8 】。 ( 1 ) 下一代互联网体系结构的大规模分层可扩展性问题 对该问题的研究将解决现有网络体系结构的单一可扩展性和网络功能的复杂多样 性之间的矛盾。 随着网络单元技术的不断发展和新的网络应用的不断出现，研究人员不断地给互联 网络增加新的功能，但是随着功能的不断增加，原有的基于“边缘论”的互联网络体系 结构的局限性也暴露的越来越明显，集中体现在网络的分层可扩展性方面。互联网络在 最初设计时是以互联互通为第一目标，因此才确定了“边缘论”的设计思想，网络提供 尽量简单的服务模式，采用基于尽力发送的分组交换模式。保证数据可靠传输和其他的 应用功能都由用户主机在网络边缘实现。但是在应用要求网络能够提供多种多样不同的 目标和要求的服务的今天，这种单一模式的基于层次结构的网络体系结构已经力不从心 了。为了使网络能够对不同的应用提供服务质量保证，研究人员投入了大量的精力，但 是仍然难以使其投入实用。这一方便是由于网络的控制和管理方面还没有取得重大的理 论突破，另一方面也是受现有网络体系结构的限制，因为在现有网络体系结构下，网络 核心能够提供的功能非常有限。因此，下一代互联网络要解决的第一个关键科学问题就 是现有网络体系结构的单一可扩展性功能和网络功能的复杂多样性之间的矛盾问题，重 点研究下一代互联网络的多维分层可扩展性问题。 韩宁宁：基于动态聚合树模型的网络路由协议研究 网络体系结构的多维分层可扩展性问题主要体现：体系结构对于网络规模的可扩展 性，也就是说体系结构必须能够适应网络规模的不断增长，包括网络层次结构、路由模 型、地址结构等等。 在研究下一代网络体系结构的时候，将首先解决下一代网络的体系结构模型问题， 对现有网络的分层体系结构进行深入研究，下一代网络体系结构将解决分层体系结构由 于层次功能固定而难以进行扩展的问题，同时将吸收主动性网络和应用层网络的优点， 设计出可扩展的、可管理的、高性能的、安全可靠的网络体系结构模型，为实现下一代 互联网络的发展目标提供保证。 ( 2 ) 下一代互联网体系结构的动态可扩展性问题 网络动态行为的研究将解决未知的网络行为与确定的传输控制目标之间的矛盾。 互联网络发展至今，已成为一个庞大的非线性复杂巨系统。具体表现为：系统的规 模和用户数量巨大且仍在不断增长，异质异构的网络融合发展；网络协议体系庞杂，垂 直方向上呈现出多样化的层次结构，而水平方向上又以地域和功能为标准进一步形成分 布且多极的架构；网络节点问、节点与数据分组间由于协议而产生的非线性作用以及用 户之间的合作与竞争，使网络行为呈现出相当的复杂性并且难以预测。如何建立系统、 科学与本质地刻画用户及其流量动态特性以及网络自身行为特征的模型是深刻认识和 把握当前乃至新一代互联网的关键所在。它必将对网络行为状态的描述与预测，新协议 的设计、开发与应用，下一代互联网络的规划、管理与控制，以及构建安全、可信赖的 网络基础设施起到至关重要的指导作用。 路由协议是网络体系结构的关键组成部分，研究可扩展路由协议的验证和测试理论 将是解决面向下一代互联网络的关键问题所在。 1 1 3 下一代互联网的可扩展路由模型和协议的研究 面向下一代互联网的具有可扩展路由模型和协议的研究是下一代互联网研究的核 心内容，这方面的研究在近年来引起了研究人员的广泛注意。新的路由模型分别面对互 联网不同维度可扩展性的情况进行建模，主要可分为如下几类： f 1 ) 在针对网络空间规模可扩展性的路由体系结构研究方面 文献 9 】 1 0 】是单播( u n i c a s t ) 路由方面的代表性研究成果。 文献【1 1 提出了一种新的端到端分层分布式路由算法和相关协议，仅选择一部分域 进行路由信息的扩散，使得该算法在大规模网络中具有极其优秀的扩展性。 文献 1 2 】设计了一种宏路由( m a c r o r o u t i n g ) 模型，使用移动代理( m o b i l ea g e n t ) 的技术 重点针对传统分层模型在路由信息不准确、q o s 信息不敏感方面的问题。 大连理工大学硕士学位论文 在组播路由方面，文献 1 3 在空间尺度设计了新的分层多播路由协议g m r p ，在保 证了组播的灵活性基础上，对路由信息量进行了最小化，优化了组播路由的带宽使用， 取得了较高的空间扩展性和分层路由效率。 文献 1 4 1 与文献 1 3 的研究方向类似，但其工作着重在组播组内的资源利率用和协 议可扩展性方面。由于网络的异构性，面向实用技术的空间维度路由研究多针对不同的 网络类型展开。 近期在a t m 网络方面的代表文献 1 5 在p n n i 路由架构上使用智能计算技术，在获 得高扩展性、低通讯量的同时，还对网络资源的利用率做了最大化设计。 在国际权威刊物发表的文献 1 6 1 ；f n 文献 1 7 1 分别是对m a n e t ( m o b i l ea dh o e n e t w o r k s ) 网络在路由可扩展性和分层模型流量方面主要研究成果的调查和展望，启发 性很高。 还有很多面向其它类型网络的研究成果，如传感器网络方面的文献 1 8 1 1 1 9 1 ，无线 广域网方面的文献 2 0 1 ，卫星网络方面的文献 2 1 】。 ( 2 ) 在网络动态可扩展特性方面的路由研究方面，主要成果集中在大小尺度的动态 时闯模型研究、流量动态行为的建模与预测等几个主要方面。 在面向链路路由量度变化的小尺度动态问题方面，文献【2 2 是时间依赖路由理论的 奠基性论文，o r d a 和r o m 在文章中给出的三类时间依赖网络模型：不受限等待模型、 源等待模型和无等待模型及其理论基础。 文献 2 3 从理论上证明了传统最短路径算法不能有效解决t d n 网络中的路由问题， 并给出了无等待模型和源等待模型的最短路径算法。 文献 2 4 以此为基础设计了混和型的时间依赖路由模型，并仿真实现基于以此模型 为核心的路由协议。 在面向拓扑变化的大尺度动态问题研究方面，文献 2 5 1 及其前期工作设计了能够适 应快速拓扑变化的路由缓冲机制和需求驱动的全新路由模型，并针对t c p 协议在高动 态性网络中的传输失败率和实际吞吐量进行了优化，实验表明新模型大幅度提升了t c p 的这两项性能。 文献【2 6 】使用反向路径转发的思想，设计了拓扑频繁变化的动态网络的路由协议 t b r p f ，实验证明了该协议在路由通讯量方面与传统路由模型相比取得了高达9 8 的 减少。 文献 2 7 针对网络的动态行为采用了预测模型作为解决方案，基于该模型设计了动 态源路由协议并配合使用路由缓冲机制，在对于不同动态性的拓扑场景模拟实验中，该 协议都取得了优秀的性能数据。 韩宁宁：基于动态聚台树模型的网络路由协议研究 ( 3 ) 在服务维度可扩展路由研究方面，具有代表性的文献有： 美国n e w a r c h 项目的研究成果【2 8 设计了面向用户的路由模型n i r a ，为用户提供 在自治域以上的路由级别中自主路由的能力，提高了用户对路由服务的控制。该论文设 计的拓扑信息传播协议t i p p 和分布式名字路由解决方案n r r s 都在仿真实验中取得了 优秀的性能。 文献 2 9 在提供了一种基于预计算方式的服务质量路由模型，为多约束服务质量路 由的n p 完全问题提供了一种切实可行实际解决方案。 文献 3 0 1 设计了针对服务质量路由的分布式缓存探听架构，为服务质量路由提供了 信息敏感度高、可扩展性良好的新模型。 出在贝尔实验室的文献 3 1 代表了无线网络路由服务模型的最新进展，该论文为多 接入服务点的i e e e8 0 2 1 1 无线网的设计了最新的公平服务路由模型，并支持对流量服 务质量的控制。 文献 3 2 】也是典型小区域无线网服务维度的路由研究成果，作者为蓝牙微网 ( b l u e t o o t h p i c o n e t ) 的实时应用设计了能够综合保证带宽和时延的公平轮转路由模型。 另外，一些研究者对服务维度的路由研究现状提出了批评，认为应更多的关注实际 开发技术而非基础理论模型设计，g r e n v i l l ea r m i t a g e 在文献 3 3 q u 对这一现象做了介绍 和探讨。 多维度可扩展路由模型的研究近年来刚剐起步，成熟研究成果并不多见。文献 3 4 3 5 都是综合考虑时间和空间两维路由的研究成果。文献 3 6 】以最小延时作为路由目标为基 础路由设计了时间驱动的分层s t e i n e r 树模型。文献【3 7 】面向m a n e t 设计了称为时间矢 量路由( t i m e - v e c t o r - r o u t i n g ) 的分层模型，该模型在与传统源路由方案的性能对比中占 有明显的优势。 路由模型和协议的研究是互联网理论和技术的重要组成部分，这个领域的研究涉及 到多种网络类型、传输技术和网络不同维度的路由属性p 8 】，相关的研究成果无法在本节 一一列举。以上主要概述了近年来与本文内容相关的研究热点和学术成果。本文的研究 内容分别针对路由模型在空间和时间维度的扩展性方面做了新的探索，选题来自于国家 自然科学基金项目，研究成果获得了发明专利，并且发表在国内外的诸多国际会议以及 国内的核心期刊上。 1 2 本文的主要工作 本文的主要工作分组概括为如下几个部分： ( 1 ) 针对下一代互联网的大规模特性设计了全新的路由模型及协议。 大连理丁大学硕士学位论文 随着网络规模的增大，在空间维度对网络进行可扩展性的分层路由成为互联网继续 发展的必由之路。本文针对大规模网络设计了分层路由模型聚合树路由模型。给出 了聚合树模型的定义、构造过程，以及相关的路径优化定理。为设计与实现具有高效率、 低空间复杂性的最佳路由协议奠定了理论基础，具有非常重要的实际应用意义。 ( 2 ) 针对下一代互联网动态性特点设计了全新的路由模型及协议。 网络的动态特征主要体现在网络的拓扑结构随时间变化方面。根据网络的拓扑结构 有两种变化链路权值随时间变化和拓扑结构随时问变化的研究，提出了面向下一代 互联网的动态路由协议增量路由协议。使用针对网络状态的变化量进行路由计算的 新方法，削减了路由器的计算量，不仅大大地降低了费用，并且具有高水平的q o s 性能。 ( 3 ) 对大规模性和动态性进行了融合，提出了面向下一代互联网的大规模动态路由 模型及协议。 下一代互联网的多维性和动态性路由结构研究为互联网在多维度上提供可扩展性 良好的模型，这些模型具备协作融合的能力，适应多种网络服务和数据流对路由体系的 不同要求。本文将聚合树模型与增量路由模型进行了融合，修改了大量两模型互相冲突 的机制，提出了面向下一代互联网大规模性和动态性的动态聚合树模型及路由协议。 r 4 ) 分别应用在互联网和无线网络中 将面向下一代互联网大规模动态性的动态聚合树模型应用到互联网中，做了最优路 径算法的复杂度、准确度以及处理机的平均吞吐量的模拟仿真试验，得到了预期的效果。 将动态聚合树融合模型应用到无线a dh o c 网络中，做了端到端延迟和端到端吞吐量的 模拟仿真试验，也得出了动态聚合树模型的优势。最后，在仿真模拟的实验基础上分析 了动态聚合树模型的优缺点，并提出了解决的方案。 1 3 论文的组织结构 文章剩余部分组织如下： 第二章针对下一代互联网大规模特性提出聚合树路由协议，对该协议的准确性和合 理性提出了理论保证，并且对通讯复杂度等问题进行了分析。 第三章针对下一代互联网动态特性提出增量路由寻径算法，其中可分为三大部分： 其一，针对链路删除情况提出解决的算法；其二，针对链路增加情况提出解决的算法； 其三，针对链路权值改变的情况提出解决的算法。 第四章为下一代互联网大规模性和动态性的融合研究。修改了大量两种模型互相冲 突的机制，设计出了聚合树路由模型和增量路由协议融合的、面向下一代互联网大规模 性和动态性的动态聚合树模型，以及相关的路由协议实现机制。 韩宁宁：基于动态聚合树模型的网络路由协议研究 第五章为仿真模拟的实验部分。把动态聚合树模型分别模拟应用在传统的互联网和 无线a dh o e 网络中，并且分别与两种网络中的经典网络路由协议做了比较，得出了动 态聚合树模型具有更好的性能效果。 最后对全文进行总结和展望，阐述了动态聚合树模型需要进一步优化的地方。 大连理工大学硕士学位论文 2 面向下一代互联网大规模特性提出的聚合树路由协议 2 1 分层路由问题的提出及其基本思想 随着网络规模的增长，路由器的路由表也成比例地增加。不断增加的路由表不仅消 耗了路由器的内存，而且需要更多的c p u 时间来扫描路由表，需要更多的带宽来发送 有关的路由状态报告。当网络规模的增长接近临界状态时，每个路由器不太可能再为其 它每一个路由器维护一个表项，所以，路由选择过程必须分层进行口”。 分层路由的引入，虽然大大的节省了路由表的存储空间，但也付出了必要的代价。 那就是空间的节省带来了路由平均路径长度的递增和路由准确率的下降。这也正是分层 路由技术研究的难点所在 帅l 。 在分层路由系统中，由一部分路由器组成路由主干。任何一台主机发送出的数据包 首先经过非主干路由器到达主干路由器，然后沿着路由主干传递。当到达目的地的网络 区域时，从主干路由器转入非主干路由器，并最终抵达目标接收方【4 1 】。 在这一分层路由过程中，路由器被划分成区域( r e g i o n ) ，每个路由器知道如何将分组 路由到自己所在的区域内的目标地址，但是对于其他区域的内部结构毫不知情。当不同 的网络被相互连接起来的时候，很自然地就会将每个网络当作一个独立的区域，这样做 的好处在于某个网络中的路由器不必知道其他网络的拓扑结构。 对于当今的互联网络来说，一个两层的分层结构已不能满足它的规模需要 4 2 】。还需 要将区域组织成群( c l u s t e r ) ，将群组织成区( z o n e ) ，将区组织成组( g r o u p ) 等等，依次类推。 为了不造成概念的混淆，本文中“域”一律代表最基本的路由节点集合。 尽管分层路由大大简化了路由表的存储，但是无论基于多少层次固定级别的分层路 由模型设计，都没有在根本上满足网络不断扩大所要求的空间规模的扩展性。针对这一 问题，本节设计了能够根据链路通讯能力的不设分层级别上限的聚合树路由模型。 2 2 解决网络大规模特i 生的聚合树路由协议 2 2 1 聚合树模型的定义 聚合树模型是网络( 图) 和树的精确结合和扩展，提供了高精确度的路由协议。这 种模型根据链路的不同参数( 本文考虑带宽参数) 将大规模网络划分为多个域。每个域 是聚合树的一个节点，我们根据这个理论定义从源节点到本域及其祖先域内的目的节点 的路径。这一模型的主要目标是提供具有高路由准确性的路由算法，并且很大程度上地 将路由过程的搜索空间缩小在很少的子域内，大大减少了算法的执行时间和网络的传输 韩宁宁：基于动态聚合树模型的网络路由协议研究 负载。它是基于网络拓扑中链路的通信能力构造的树型结构。在这种模型下，网络路由 节点只需使用远远少于全局网络的路由信息，就能够找到优化路径。下面给出聚合树模 型的形式化定义。 定义2 1 ( 聚合树模型的定义) ：聚合树模型为at r e e = r zh ) ，其中t 是大规模 网络的域集合；若r 只含一个域，则日= a ，否则日是定义在丁上的二元关系；在r 中存在唯一的称为根的域d ，；若丁一6 a ，则存在，一d r o 中存在一个划分 r l ，疋，瓦( n 0 ) ，其中v j 戽，1 ，k n ，有，nt k = o ，且对v f ，l f h ，存 在唯一域z 巧，满足 h ：对应于丁一h 的划分， h 一 ， ) ，唯一的一个划分q ，珥，其中v j t ，l 蔓工k h ， 有抒，n 嘎= g 。对于v i ，1s i ，q 是z 上的二元关系，( 巧，e ) 是一棵符合本定义 的聚合树，称为根域以的子聚合树。 上述给出了一般化的、抽象的聚合树模型的递归定义，其基本构造思想来源于最短 路径算法研究领域的网络树模型【4 3 。在解决实际路由问题时，如何使用分布式分割算法 将原网络划分为聚合树是聚合树路由模型需要解决的问题。下面给出如何将原网络进行 集中式划分构造成聚合树的过程。 2 2 2 聚合树模型的构造 在网络中，我们首先选择带宽值相对较大的一些链路所链接的路由器集合作为根域 节点。然后，在剩余路径中选择带宽值相对较大的链路，将这些链路所链接的路由器按 照区域组成集合作为第二层的子域节点，分别连接在根域宏节点下。剩余链路以此类推， 分别形成下面层次的节点；连接在下面，这样就形成了聚合树。这种路由协议是基于链 路状态的路由协议开放最短路径优先算法( o s p f ) 在层次拓扑结构中的应用。本域路 由器节点通过带权值的各链路，相互交换状态信息，确保域内每个路由器都能完全掌握 本域的拓扑信息。其他域的路由器信息，分别作为网络中的拓扑节点( 称为拓扑宏节点) ， 被整体处理。在此模型中，各路由器只需保存本域和子域内的路由器节点以及其它拓扑 宏节点的信息，大大缩小了查找空间。使用开放最短路径优先算法，每个路由器就可以 计算出从自身到本域和其予域节点以及其它域的拓扑宏节点问的最短路径，产生最小生 成树( m s t ) 。 下面给出聚合树模型构造过程的形式化定义。 设原有网络拓扑结构为n = ( 矿，a ，缈) ，其中y 是一个非空有限节点集，a n x n 是 有限的链路集形= w ( d ) 1 ae a l ，( 口) 是非负实数，表示链路a 的权值。 大连理工大学硕士学位论文 首先为原网络中的链路定义不同的级别，即在集合4 上建立一个映射函数。映射函 数定义如下： 定义2 2 ( 链路的级别) ：v a a ，3 h 1 ，i = 1 ，2 ，3 ，k ) ，存在一个映射函 数f ：a 斗，使得f ( a ) = h ，h 称为链路d 的级别；h 的值越小，级别越高；并且v h i ， 使得厂1 ( 矗) = a a l f ( a ) = h 不为空。所有级别为h 的链路集合记作4 ，即a h = f 。( ) 。 根据链路的通讯能力对网络进行划分，具有明确的意义。网络中的通讯线路有局域 网、接入网、城域网、国家级主干网、洲级主干网和私有专线等通讯和管理能力不等的 线路等级。这样的划分从模型的构造基础上就清晰的表现了网络配置和管理的基本层 次。为在此模型基础上设计的路由协议的信息管理和计算都提供很大的方便。 在链路级别的基础上，从原网络n = ( v ，a ，) 开始构造聚合树at r e e = r zh j 。设 由级别为4 的链路组成的域为聚合树at r e e 的根域，即匾，4 t 。如果一d l a ， 将4 链路从原图中抽出，剩下的部分n d l 将自然被划分成啊个非空子网络 互1 ，t 1 2 ，王。，其中，对于v p g ，1 p ，q 惕有，互p n 毛= o 。对于v ，1 f 碍， 在王子网中选取级别最高的链路集合，设为4 “。将由a “构成的域和节点集巧，n 碣合 并构成的域作为4 第i 个子域，称为研，有4 ，t ， h 。如果正，一 吐。) o ， 重复上面的过程将a “从写，中抽出，余下的部分互。一 d ，。) 划分为个非空域 丁lb ，r 1 矿，五，其中，都对于v p q ，1 墨p ，q s 惕，有n 正= o 。对于 夥，1 j 强。，在王。子网中选取级别最高的链路集合，设为一”。将由a 1 ”构成的域和节 点f a t , 。nd l ，合并构成的域作为吨第_ ，个子域，称为4 f ，有西fa t ， e h 。 以此类推，递归调用该过程，最后建立基于原网络n = ( v ，a ，矿) 的聚合树模型at r e e = r zh ) 。图2 1 举例演示了这一过程。 定义2 3 ( 关联节点定义) ：在聚合树at r e e = ( t ，h ) 中，任意域d ，t ，如果存 在其父域d p t ， h 。属于集合d 。n d ，的节点为关联节点。集合也n d ，记 为r d 。显然，根域的关联节点集是空的。关联节点其实就是既在上层又在下层，也 就是使上下两个层次通信的联系节点。 根据聚合树的构造过程和定义2 3 ，可以得到以下性质结论： 性质2 1 ( 父域特性) ：硝v ( d 。) ，即父域包含所有子域的关联节点。 性质2 2 ( 节点路由特性) ：设有节点s 和d ，如果它们不在同一域并且各自所在的 域不具各父子关系，则s 和d 的路由路径，一定包含两者共有的祖先域中的节点。 韩宁1 基于动态聚合树模型的网络路由协议研究 ( a ) 原网络 ( a ) t h eo r i g i n a ln e t w o r k ( b ) 域西 ( b ) d o m a i n 吨 - q 一i ( d ) 子域d 1 2 qp 蒴薯 一一j j ! ( c ) 子域五1 ( c ) s u b - d o m a i n 五l 一爹p 、 遗p j ( e ) 子域d l l( f ) 子域吐 ( d ) s u b d o m a i nd 1 2 ( e ) s u b d o m a i nd 1 1 ( f ) s u b d o m a i n d m ) 子域d 。 a ) 聚合树 ( 1 1 ) s u b d o m a i nd 11 2 ( i ) a g g r e g a t i o nt r e e 图2 1 聚合树构造过程示例 f i g 2 1t h ec o n s t r u c t i o no fa g g r e g a t i o n - 订e em o d e l 大连理工大学硕士