（计算机应用技术专业论文）面向ngi大规模动态特征的路由模型和协议研究.pdf

大连理工大学硕士学位论文摘要本文围绕目前下一代互联网发展中急待解决的基础路由问题展开，根据f 一代互联网的发展趋势，其基础路由模型需要具有多维的可扩展性，以期能够满足网络中多服务种类、多数据流类型对网络服务质量、流量调度等方面的需求。本文选择互联网在时间和空间两个维度上的路由模型作为研究的切入点，分别针对下一代互联网在时间维度上的动态性特点和在空间维度上的大规模特点提出了全新路由解决方案，并通过仿真实验与传统路由技术进行了性能对比。下一代互联网动态特性的研究可以分为小尺度动态问题和大尺度动态问题两部分。本文面向小尺度动态问题提出了基于时间依赖理论的路由模型h t d n 及其路径最优化定理。在h t d n 路由模型的基础上，本文设计了路由协议h t d r p ，并在理论上对其使用的路由算法在时间复杂度和通讯复杂度等方面进行了分析。对h t d r p 协议的仿真实验建立在权威网络仿真环境n s 2 平台上，通过仿真，本文给出了h t d r p 协议与传统路由协议r i p 的性能对比分析。在面向大尺度动态问题方面，本文提出了基于增量算法的路由模型，并在增量路由模型的基础设计了路由协议i a r p 。针对网络链路状态的变化量的不同，详细设_ ；t - y 增量路由寻径算法和及其针对多链路状态变化情况的改进，并给出了相关的算法分析。针对下一代互联网大规模的特性，本文提出了基于链路通讯能力的网络树路由模型，给出了网络路由模型的定义、构造过程和路径优化定理，在网络树路由模型的基础上，本文设计了分层路由协议n t r p 。n t r p 协议的理论分析着重在收敛性能、路由准确率和通讯复杂度三个方面进行。仿真实验表明，与传统协议比较，n t r a 在收敛性、准确度和平均吞吐量方面均占有绝对的优势。最后，本文在多维路由模型的融合方面进行了探索，分别设计并评价了两个时空两维的融合模型：n t d n 融合模型和增量融合模型，并总结了路由模型融合过程中出现的难点和可能的解决办法。关键词：路由模型；路由协议；时间依赖；增量算法：网络树大连理工大学硕士学位论文r o u t i n gr e s e a r c hf o rt h el a r g es c a l ea n dd y n a m i cc h a r a c t e r so fn g im o d e l sa n dp r o t o c o l sa b s t r a c ti no r d e rt om e e tr a p i dd e v e l o p m e n to fn e x tg e n e r a t i o ni n t e r t n e t ( n g b ，t h er e v o l u t i o n a r yr o u t i n gs c h e m e sw h i c hc a nf i n i s hr o u t i n gw o r ko nm o r et h a no n ed i m e n s i o n a l i t ya r ei nd i r en e e do f t h i st h e s i si sa b o u tt h er e s e a r c hi nr o u t i n gm o d e l sa n dp r o t o c o l sw h i c hc a ns u p p o r tt h el a r g es c a l ec h a r a c t e ro f n g ii nt i m ed i m e n s i o n a l i t ya n dt h ed y n a m i cc h a r a c t e ro f n g ii ns p a c ed i m e n s i o n a l i t y t h i st h e s i sd e s i g n st h r e en o v e lr o u t i n gm o d e l sa n dt h er o u t i n gp r o t o c o l sb a s e do nt h e m t h ep e r f o r m a n c ee v a l u a i o na r ea c h i e v e db ys i m u l a t i o n s f o rt h ed y n a m i cc h a r a c h e ro f n g i ，t h er o u t i n gp r o b l e mc a nb ed i v i d e di n t ot w op a r t s ：t h em i c r os c a l ed y n a m i cp r o b l e ma n dt h em a c r os c a l ed y n a m i cp r o b l e m t h i st h e s i sp r e s e n t st h eh t d nr o u t i n gm o d e lf o rm i c r os c a l ed y n a m i cp r o b l e mb a s e do nt h et i m ed e p e n d e n tt h e o r yt h er o u t i n gp r o t o c o lh t d r pi sd e s i g n e df o rh t d nm o d e l t h et h e s i sa n a l y s e st h et i m ea n dc o m m u n i c a t i o nc o m p l e x i t yo fh t d r pa n dc o m p a r et h ep e r f o r m a n c eo fh t d r pa n dr i pu s i n gn s 2 t h es o l u t i o nf o rm a c r os c a l ed y n a m i cp r o b l e mi st h ei n c r e m e n t a lr o u t i n gm o d e la n di t sr o u t i n gp r o t o c o li a r pw h i c hc o m p u t et h er o u t et a b l eo n l ya c c o r d i n gt ot h ec h a n g e so f t h en e t w o r k s f o rt h el a r g es c a l ec h a r a c h e ro f n g i ，t h et h e s i sp r e s e n t st h en e t w o r k t r e er 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 i sm o d e li sd e s i g n e di nc o n s i d e r a t i o no ft h ec o m m u n i c a t i o nc a p a b i l i t yo fl i n k s t h er o u t i n gp r o t o c o ln t r pb a s e do nn e t w o r k t r e er o u t i n gm o d e li n c l u d e st h en e t w o r k - t r e ec l u s t e r i n ga l g o r i t h m ，t h en e t w o r k - t r e er o u t i n ga l g o r i t h ma n dt h ea g g r e g a t i o ns c h e m ef o rr o u t i n gc o n t r o li n f o r m a t i o n n t r pa c h i e v e sah i g hr o u t i n ga 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 b ys i m u l a t i o n s ，n t r pg e t sh i g hp e r f o r m a n c ei nc o n v e r g e n c e ，r o u t i n ga c c u r a c ya n da v e r a g et h r o u g h p u t a t1 a s tp a r to ft h et h e s i st r y st ou n i t et h es e p a r a t em o d e l s a sar e s u l t t w oc o m b i n a t i o nm o d e l sa r eg e n e r a t e da n de v a l u a t e dk e yw o r d s ：r o u t i n gm o d e l ；r o u t i n gp r o t o c o l ；t i m ed e p e n d e n t ；i n c r e m e n t a la l g o r i t h m ；n e t w o r k - t r e e一一独创性说明作者郑重声明：本硕士学位论文是我个人在导师指导f 进行的研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理t 大学或者其他单位的学位或证书所使用过的材料。与我一同丁作的同志对本研究所做的贡献均已在论文中做r 明确的说明并表示，谢意。作者签名：坌! 互：日期：心3 ，fj1f大连理工大学硕士学位论文1 绪论1 1 研究背景及意义1 1 1 下一代互联网的现状和发展趋势在人类社会从工业社会向信息社会转变的过程中，以互联网为代表的信息网络平台已逐步成为现代社会的重要基础设施，其影响力已渗入到社会生活的多个领域，是未来信息化社会的基础平台和载体。信息网络平台的建设和升级直接标志着一个国家的综合国力的水平。经典的计算机网络理论与技术于二十世纪六十年代在美国起步，计算机网络领域的著名专家d c l a r k 在论文 1 l o ? 给出i n t e m e t 的主要设计原则，奠定了i n t e r n e t 的发展方向。但该设计并没有为i n t e m e t 日后的大规模扩张打下坚实的理论基础。互联网在信息的收集、处理、分发和共享等方面的优势迎合了2 0 世纪信息技术革命的需求，使得其在短短几十年中已成为了人类社会生活的一个重要组成部分。然而，随着计算机、移动电话等信息终端设备在信息收集、处理和分发能力的不断提高，人们对于更复杂的信息处理技术的需求也在高速增长，研究开发人员不断的将新功能注入网络平台。随着功能的增加，分组括互联网、电信网络在内主流信息网络平台都已不能满足未来信息网络平台的需要，更新换代迫在眉睫。从二十世纪九十年代起，新一代网络平台的基础理论和应用技术方面的研究引起了世界各国和国际专业组织的广泛关注，在世界范围内已有很多针对下一代网络平台的研究和工程项目相继展开。在互联网方面，美国于1 9 9 6 年最早开展大规模的下一代互联网( n e x tg e n e r a t i o ni n t e m e t ，n g i ) 研究计划【2 j 。该计划的目的是研究二十一世纪计算机信息网络的基本理论，构造全新概念的下一代计算机互联网络的体系结构，为美国的教育和科研提供世界最先进的基础设施。目前，i e t f 力推新一代网络层传输协议i p v 6 3 1 作为下一代互联网的网络层基础，i p v 6 彻底解决了v 4 地址空间不足的问题，并同时充分考虑了网络层的安全问题。i p v 6 的出现缓解了目前互联网在发展空间上受限的困境，受到世界各国各地区的广泛支持，多个大型i p v 6 网络已建设完成或正在建设中，其中以美国的a b i l e n e n ，欧盟的g e a n t ”，亚太地区的a p a n 6 1 ，加拿大的c a 3 n e t ，英国的j a n e t 2 目较为典型。我国的i p v 6 实验床始建于1 9 9 8 年。1 9 9 9 年国家自然科学基金联合项目资助的“中国高速互联研究实验网n s f c n e t ”启动。2 0 0 3 年我国筹建的世界上最面向n g i 大规模动态特征的路由模型和协议研究大的i p v 6 商用网络f 一代互联网示范项目c n g i 核心网c e r n e t 2 核心网在北京开通，标准化方面已经进入世界前沿。( c n q i ) 1 9 1 建设全面启动。2 0 0 4 年末，标志着我国在下代互联网的建设方面和在电信网方面，下一代网络( n e x tg e n e r a t i o nn e t w o r k ，n g n ) 的概念已经提出多年，最终由国际电联( i t u ) 于2 0 0 4 年确定了n g n 的定义l l 训，为n g n 的发展铺平了道路。n ( 荆实验网络大部分由电信运营商建设，其中以 = j 本n t t 公司建设的n g n 、韩国k t 公司组建的b c n 、英国b t 公司建设的2 1 c 最为典型。这些网络都采用软交换体系结构，使用毋技术承载数据，表现出了明显的向互联网体系结构演化的趋势。我国在n g n 的实验方面同样走在世界前列，中国电信、移动、铁通、联通等电信运营商相继于2 0 0 0 年左右开展n g n 的实验网络建设，部分商用n g n 网络已投入使用。在n g i 和n g n 的研究和发展中，两者不断体现出在体系结构方面相互融合的趋势。但无论是站在电信网的角度，还是互联网的角度，都可以看到网络迫切需要升级的诉求。从目前的趋势看，下一代信息网络平台必然是互联网和电信网相融合，以p 技术承载的信息软交换平台。原因在于，传统的电信网络很难承担现有的数据业务，其必须改变原有的电路交换理论体系结构，全面使用i p 形式的软交换才有能力进行数据通信业务的服务。而传统的互联网如果继续按照原有的体系结构发展下去，将无法适应用户对服务质量( q o s ) 要求的发展。n g i 实验得出的一个重要结论是，目前在n g i 上实现q o s 十分困难，甚至是高带宽下也无法提供的【l ”。其根本原因在于，目前使用的互联网体系结构建立在“边缘论”基础上，仅提供尽力而为( b e s te f f o r t ) 的服务模式 1 2 1 ，只考虑到网络在联通方面的扩展性。这种模型在下一代互联网的发展中已暴露出诸多的缺陷。i p v 6 虽然在地址空间上彻底解决了网络地址匮乏的情况，但互联网的基础理论方面并没有突破性进展，经典的路由、流量控制、传输技术模型在空间、时间、服务质量、网络管理等多个维度上，依然没有良好的描述能力，基于经典的模型不可能为这些维度上的网络特征提供可扩展性良好的支持。1 1 2 互联网基础理论研究要解决的基本矛盾问题目前，新一一代互联网发展过程中主要应该解决“人类社会对下一代互联网需求的不断增长与网络理论和技术本身发展的不充分性之间的矛盾”l l ”，这是下一代互联网发展中所面临的基础矛盾和发展瓶颈。随着超高速光通信技术、高速无线通信技术、网格计算和新的互联网杀手级应用的研究进展，可以预见，下一代互联网的建设耍更大、更快、更及时、更方便、更安全、更可管理和更有效。其中，更大是指下代互联网应具有巨大的地址空间，能够有效容一2 大连理一 大学硕士学位论文纳网络的高速发展；更快是指与目前的互联网相比，下一代互联网网络的数据传输率要大幅度提高，以适应多媒体数据流的要求，至少达到1 0 0 m b p s 以上；更及时是指下一代互联网在路由结构上必须支持组播和面向服务质量控制的传输机制，只有达到这样的要求才能给更多的用户提供实时的媒体信息；更方便是指下一代互联网需要支持更方便有效的接入方式，需要支持以无线网和移动电话网为主的异构网络融合；更安全指的是下一代互联网需要提高网络服务的可靠性、信息的安全性并且有很强的抗攻击能力；更可管理是指下一代互联网需要一个更加灵活有力的管理机制，对于网络中的端到端的行为、骨干网的流量调整均需提供高效的管理；更有效是指面对多媒体服务的普及，互联网也需提供类似电信网络的精确计费手段，提供合理的互联网运营盈利模式。面对这些发展目标，显然，仅在原有互联网模型的基础上升级i p 协议是远远不够的。要满足下一代网络平台发展的多种需求，就要在互联网体系结构方面研究新模型、新机制，以期能够从统计学、数学等基础学科的角度对网络行为进行建模，创建全新的适合互联网发展的体系结构。目前，互联网基础理论的缺陷主要体现在以下几个方面：首先，互联网传统的体系模型仅考虑到网络在联通方面的扩展性，未能在其它维度上给出可扩展性高的路由模型，主要表现在：随着网络规模的扩大，尽力而为的路由结构将面对越来越大自治域系统和路由表长度，传统路由基础理论在路由表的快速查找、路由信息的聚合等方面已捉襟见肘，面向网络空间维度的路由模型已成为研究的热点领域；随着互联网和以无线网、移动电话网为代表的电信网络的融合，网络动态行为特征已逐步成为下一代互联网的标志性特征。传统路由理论，对于动态的网络行为采取启发式的算法，对网络链路、节点的动态行为规律不予理会，其结果导致路由机制对网络状态的动态变化反映迟缓甚至错误、路由的频繁重新计算消耗了大量的计算和存储资源。面对网络的强动态特性，传统模型及方法己力不从心，建立一种能够准确感知网络状态动态变化并迅速进行路由调度的路由模型成为研究的必由之路：随着网络服务和数据类型的增加，数据对路由的质量要求在提高，用传统路由方法保证服务质量的难度很大。许多基于传统路由模型的q o s 路由算法都只能在特定的条件下对服务质量进行局部的优化，见效甚微。一种清晰的解决方案就是在服务维度新建路由模型，从基础上解决传统路由结构忽视服务质量维度信息的设计缺陷，m p l s 技术 1 4 就是这一方向上成熟的研究成果。其次，互联网基础理论在分组交换网的流量模型方面缺乏深入的研究。流量模型的缺乏，导致互联网管理人员的工作缺乏有力的流量控制和管理理论的指导，只能凭借经3 。面向n g i 大规模动态特征的路由模型和协议研究验完成流量调度、接入控制、服务质量控制等重要的工作，这也远远不能满足下一代互联网更方便、更可管理和更有效的发展目标。再次，互联9 嘲发展至今已经成为一个复杂的巨系统，随着异构网络的融合，下一代互联网平台将更大、更复杂。从规模上看互联网的用户数量巨大且不断增长；从网络协议栈角度看，无论在垂直方向还是从水平方向上，网络协议都呈现出多样化的特点，这大大增加了网络中通讯的复杂程度和难度。转发节点间、网络终端用户间和不同的数据流之间因为协议所产生的沟通困难、资源竞争都使得网络的行为日益复杂难以预测。另外，网络中聚集的大量软硬件都有可能发生足以影响全网性能的破坏性事件。如何从复杂巨系统的角度对网络的复杂性和脆弱性进行描述和保护成为新的基础理论研究关键。最后，用户和服务提供者对服务需求的复杂性和多样性使得互联网运营商在如何构建大规模互联网服务方面缺乏指导。如何根据下一代互联网的体系结构建立可扩展性强的服务模式，如何快速灵活的为用户提供具有良好互操作性和高性能的服务，如何对现有的服务模型做出调整，如何建立清晰合理的盈利模型，如何对服务进行有效的管理都是急需互联网基础理论的研究和创新。il3 路由体系结构在互联网基础理论研究中的重要作用多维可扩展的路由体系结构是下一代互联网的基础理论研究中重要的组成部分。首先，路由体系结构的可扩展性直接影响下一代互联网的空间规模可扩展性、服务规模可扩展性和网络性能可扩展性等多个方面。可咀说路由体系结构的研究是关系到下一代互联刚在多维可扩展性方面成败的关键。d c l a r k 等专家在文献5 j 中指出下一0 e 互联网基础理论在解决新媒体应用需求、异构平台融合，特别是移动节点路由、用户地址与身份访问等问题方面，其核心就是创建新的路由体系结构。其次，网络动态行为的理论研究与基础路由体系结构的研究相辅相成，相互影响。针对网络动态行为的研究需要从统计学的角度进行网络流量行为的分析，从时间序列模型和网络历史流量的资料中，对网络行为的发生进行预测式的建模。这些工作均是以对真实网络流量进行网络测量和行为分析为前提和基础的。虽然研究表明，网络流量的自相似性不会随流量的控制方法而改变【i “，但路由体系结构对于网络流量的局部影响巨大：好的路由算法能够减轻网络拥塞的程度；高效的路由查找算法，能够削减分组的延迟，提高网络的吞吐量；设计公平的缓冲区排队算法能够保证多数应用服务的持续进行；快速灵活的动态路由协议，能够有效提高路由节点对流量的最优路由程度，从而优化全网的路由资源配置。同时，路由体系结构的研究也应建立在对网络流量动态行为特征有清楚认识的基础上。d 一大连理工大学硕士学位论文1 2 国内外的研究现状和发展趋势12 1 下一代互联网基础理论的研究与发展对下一代互联网基础理论的研究，始于美国。作为n g i 项目的补充部分，由美l o o多所大学联合发起的i n t e m e 垃研究计划1 1 7 1 旨在利用i n t e m o t 现有环境探索未来高速互联网的应用技术，在i n t e m e t 2 的研究过程中，研究文献 1 8 】 19 公布现有互联网体系结构理论中的一些缺陷和不适应继续发展的部分，如文献【1 9 提到的现有的互联网无法为数据流分配价值标签、无法通过对流量的监控进行有效结算、无法描述时间维度上高速变化的资源，比如移动设备、无法适应超长距离的传播延迟的路由。随着这些研究成果的出现，世界各地的研究机构于近年纷纷开展互联网基础理论的研究，其中的领导性项目为美国国防部资助的下一代互联网体系结构研究项目- - n e w a r c h 删j ，该项目由美国南加州大学信息科学研究所、麻省理工学院计算机科学实验室和加州伯克利大学国际讨算机科学研究所合作开展，以构建适合下代互联网发展的体系结构为研究目标，已经发表的研究成果分组括 2 1 2 6 ，其中在 2 1 2 4 中，作者对现有的互联网进行了反思，并提出了下一代互联网设计的基本原则：面向变化的设计，可控制的透明性和兴趣冲突的隔离。其中，面向变化的设计就是指进行多维可扩展的网络体系结构的研究，而这方面的研究又是以地址体系结构和路由体系结构为核心的。例如，在文献 2 2 1，作者描述了用于取代i p 地址概念的f a f r 结构，这一新的地址体系结构，用a s s o c i a t i o n s $ 1 1 f o r w a r d i n gd i e i v e 二维地址体系替代了原有的i p 体系，将i p 地址集节点位置功能和路由寻址功能于一身的情况拆分为两个互不干扰的维度上进行，从而增强了网络地址的灵活性，减小了单一地址系统的负担。而文献 2 5 甚至颠覆了传统的网络协议栈分层的概念，使用了角色的概念来定义全新的网络功能模块的构成。各个协议模块之间，不再存在上下的层次概念，而是完全转向了角色之间相互通信、合作完成网络服务的全新体系结构。在路由理论研究方面的主要工作将留待下节详细介绍。我国的互联网基础理论研究起步较晚，由国家9 7 3 项目的“颏一代互联网体系结构理论研究”项目于2 0 0 3 起步，该项目由清华大学、国防科技大学、东南大学、北京邮电大学、中科院网络中心等单位共同承担，吴建平教授任首席科学家。该项目最新的进展分组括文献2 7 3 1 】。国内其它一些重要的研究成果还分组括 3 2 - 3 5 】。一5 面向n g i 大撬模动态特征妁路由搂帮郸挤议研究i 2 2 下一代互联勰的路睦模型和于舟没的碌究面向f 一代互联网的路由模型和乩议的研究是下一代互联网基础理论研究的梭心内容，这方两的研究在近年来引起了研究人员的广泛注意。新的路由模型分嗣强对互联网不同维度的情况进行建模，主要q 分为如f l 类：在务维度路由研究力厦，代表文献分组括：美剿n e w a r c h 项目舱研究成果f ，3 1 设计了面向用户的路由模型n i r a ，为用户提供在自治域咀上的路由级别中自主路由的能力，提麓了用户对路由服务的控制。该论文设计的拓扑信息传插协议t i p p 和分布式名字路由解决方案n r r s 都在仿真实验中取得了优秀的性能；文献 2 9 在提供了一种摹于预计算方式的服务质量路由模型，为多约束服务质量路由的n p 完全问题提供了一种切实可行实际解决方案：文献3 6 】设计了针对服务质量路由的分布式缓存探听架掏，为鞭务质量路由提供了信息敏感度高、町扩展陛辽好的新模型。出在贝尔实验事的文献 3 7 代表了无线网络鼹幽服务模型於最耘进展，该论文为多接人服务点豹i e e e8 0 2 1l 无线网的没训了最新的公平服务路由模型，并支持对流量服务质量的控制。文献 3 8 1c n 是典型小区域无线网服务维度的路出研究成果，作者为蓝牙微网( b l u e t o o t hp i c o n e t ) 的实时应用设计了能够练台保证带宽和时题的公平轮转路由模型。另外，一些研究者对服务维度的路由研究现状提出了批评，认为应更多的关注实际开发技术而非基础理论模型设计，g c e n v i l l ea m _ i i i a g e 在文献 3 9 中对这一现象做了介绍和探讨。在针对网络空间规模的路由体系结构研究方面，文献 4 0 【4 1 是单播( u n i e a s o 路由方面扮 表性研究成莱。f 4 0 1 提出了一种新嚣端到端分层分寿式路由算法和相关洒议，仅选择嘟分域进行路由信息的扩散，使得浚算法在大舰模网络中只有极其优秀的扩展性。【4 1 1 设汁了一释宏路由( m a c r o r o u t i n g ) 模型，使用移动代t 里( m o b i l ea g e n t ) 的技术重点针对传统分层模型在路由信息不准确、q o s 信息不敏感方面的问题。在组播路由方面，f 4 2 1 在空矧尺度设计了新的分层多波路由曲议g m r p ，在保证了组播的灵活性基础上，对路由信息量进行了最小化，优化了组播路由的带宽使用，敢得了较高的空间扩展性和分层路由效率。 4 3 与 4 2 1 的研究方向类似，但其工作着重在组播组内的资源利率用和协议可扩展性方面。由于网络的异掏性，碰囱实胡技术的空间维度辨由研究多针对不同的嘲络类型展开。近期在a t m 网络方面的代表文献f 4 4 在p n n i 路由架构上使用智能训箨技术，在获得毫扩展性、低通讯量的同时，还薅网络资源的利罔率撒了最大化设计。在国际权威刊物发表的文献f 4 5 1 和【4 6 分别是对m a n e t ( m o b i l ea dh o cn e t w o r k s ) 网络在路由可扩展性相分层模型流量方强主要研究成果的调查和展望，启发6 大连理工大学硕士学位论文性很高。还有很多面向其它类型网络的研究成果，如传感器网络方面的 4 7 1 1 4 8 1 ，无线广域网方面的 4 9 】，卫星网络方面的 5 0 】。在网络动态特性方面的路由研究方面，主要成果集中在大小尺度的动态时间模型研究、流量动态行为的建模与预测等几个主要方面。简述如下：在面向链路路由量度变化的小尺度动态问题方面，文献 5 1 是时间依赖路由理论的奠基性论文，o r d a 和r o m 在文章中给出的三类时间依赖网络模型：不受限等待模型、源等待模型和无等待模型及其理论基础。文献【5 2 从理论上证明了传统最短路径算法不能有效解决t d n 网络中的路由问题，并给出了无等待模型和源等待模型的最短路径算法，文献 3 5 以此为基础设计了混和型的时间依赖路由模型，并仿真实现基于以此模型模型为核心的路由协议。在面向拓扑变化的大尺度动态问题研究方面，文献 5 3 及其前期工作设计了能够适应快速拓扑变化的路由缓冲机制和需求驱动的全新路由模型，并针对t c p 协议在高动态性网络中的传输失败率和实际吞吐量进行了优化，实验表明新模型大幅度提升了t c p 的这两项性能。文献f 5 4 使用反向路径转发的思想，设计了拓扑频繁变化的动态网络的路由协议t b r p f ，实验证明该协议在路由通讯量方面与传统路由模型相比取得了高达9 8 的减少。文献 5 5 针对网络的动态行为采用了预测模型作为解决方案，基于该模型设计了动态源路由协议并配合使用路由缓冲机制，在对于不同动态性的拓扑场景模拟实验中，该协议都取得了优秀的性能数据。多维度路由模型的研究近年来n i gr j 起步，成熟研究成果并不多见。文献 5 6 1 1 5 7 1 都是综合考虑时间和空间两维路由的研究成果。【5 6 以最小延时作为路由目标为基础路由设计了时间驱动的分层s t e i n e r 树模型。 5 7 面向m a n e t 设计了称为时间矢量路由( t i m e v e c t o r m u t i n g ) 的分层模型，该模型在与传统源路由方案的性能对比中占优。路由模型和协议的研究是互联网基础理论的重要组成部分，这个领域的研究涉及多种网络类型、传输技术和网络不同维度的路由属性，相关的研究成果无法在本节一列举。以上主要概述了近年来与本文内容相关的研究热点和学术成果。本文的研究内容分别针对路由模型在空间和时间维度的扩展性做了新的探索，部分研究成果 3 5 5 8 1 与发表在通信学报与i c n 0 5 国际会议上。1 3 本文的主要工作本文的主要工作分组括如下几个部分：n 1 针对下一代互联网动态性特点设计了全新的路由模型及相关路由协议。7 面向n g t 大规模动态特征的路由模型和协议研究网络的动态特征主要体现网络的整体和局部状态随时间变化。根据对网络状态观察的尺度的不同将动态性分为大尺度动态性和小尺度动态性两部分，本文在小尺度动态性问题方面，设计了全新的h t d n 路由模型，并以h t d n 模型为基础设计了适用于网络小尺度动态行为的路由协议h t d r p 。在大尺度动态问题方面，本文没计了基于增量算法的增量路由模型，使用针对网络状态的变化量进行路由计算的新方法，削减了路由器的计算量，并在这一模型的基础上设计完成了增量路由协议i a r p 。为了验证新模型和新协议的性能，这部分的工作还分组括对两个路由模型的理论分析和仿真实验。f 2 1 针对下一代互联网的大规模特性设计了全新的路由模型及相关路由协议随着网络规模的增大，在空间维度对网络进行可扩展性高的分层路由成为互联网继续发展的必由之路。本文针对大规模网络设计了分层路由模型网络树路由模型。给出了网络树模型的定义、构造过程和相关的路径优化定理。在网络树模型的基础上设计了分层路由协议n t r p ，并对n t r p 的性能进行了理论分析和仿真实验。( 3 ) 对时空两维路由模型进行了融合，对多维路由模型的融合进行了探索。下一代互联网的多维路由结构研究需要为互联网在多维度上提供可扩展性良好的模型，这些模型应具备协作融合的能力，以便适应多种网络服务和数据流对路由体系的不同要求。本文在将这部分种的主要工作分组括：将h t d n 路由模型与网络树路由模型进行了融合，对新的h t d n 融合模型进行了定义，并针对两模型的不能协同工作的部分做了修改；将增量路由模型与网络树模型进行了融合，修改了大量两模型互相冲突的机制；总结了在进行多维路由模型融合的过程中所遇到的困难和可能的解决办法。1 4 论文的组织结构文章剩余部分组织如下：第二章针对互联网动态特性的时间维度路由模型及协议的设计、理论分析和仿真实验，其中可分为两大部分：其一，针对小尺度动态问题的混合时间依赖模型h t d n 和混合时阃依赖路由协议h t d r p 的设计、理论分析和仿真实验；其二，针对大尺度动态问题的增量路由模型和增量路由协议设计及其理论分析。第三章针对互联网大规模特性的空间维度路由模型及协议的设计、理论分析和仿真实验。主要分组括网络树模型的设计、网络树路由协议n t r p 协议设计及n t r p 的理论分析和仿真实验结果。8 大连理工大学硕士学位论文第四章为时空两维路由模型的融合研究。描述了h t d n 融合模型和增量融合模型并分析了两个融合模型的优缺点。给出了多维路由模型融合的难点分析和可能解决方案。最后对全文进行总结和展望。9 面向n g i 大规模动态特征的路由模型和协议研究2 面向n g i 动态特征的时间维度路由模型及路由协议2 1 问题的提出在下一代互联网的动态行为特征越来越明显，这种动态的行为主要涉及到互联网在时间维度上的状态变化，而传统的路由体系结构并没有在列间维度上给出相应的描述模型。f 一代互联网商、i 卫应用在即，在路由的基础理论方面支持时间维度的路由信息，已成为业界研究的重点。从路由的角度，网络的动态行为特征可以分为两种情况进行认识 5 9 1 ：从链路的角度看，如何对链路的路由量度变化进行建模，确切的反映链路状态变化的特征，并以此为基础进行路由计算是一类问题，简称小尺度动态问题；从整个网络拓扑图的角度看，如何对网络拓扑的变化进行建模，并迅速对其进行路由的更新是一类问题，简称大尺度动态问题。2 2 网络动态路由的基本思想传统路由理论的动态路由算法是以路由缓存表进行路由信息的暂存，并不断通过邻居间交换路由信息而更新路由缓存表，最后以该表为基础使用b e l l m a n - f o r d 和f o r d f u l k e r s o n 路由算法 6 0 】来完成路由表的更新。由于在该路由表( 即一个矢量，v e c t o r ) 中列出了当前已知的到每个目标的最优路由的距离( d i s t a n c e ) 和所使用的下一跳( n e x th o p ) ，这种路由算法称为距离矢量路由算法，而使用该类算法的路由协议称为距离矢量协议。传统距离矢量协议的一个路由信息更新过程如图2 ，1 和图2 _ 2 所示：幽21 距离矢量协议演示拓扑图f i g 21t h et o p o l o g yo f an e t w o r kr u n n i n gd i s t a n c ev e c t o rm u t i n gp r o t o c 0 11 0 大连理工大学硕士学位论文到aamb 卜刊cr _ f ldr 矿leh 1 4if 匮fg 1 8lhf 1 f lir j 2 1 h。田kl2 4il 圆h从j 出发的延迟k下跳8a2 1 3a2 8l2 0h17l3 di1 8h12h1 0106k1 5k建蠢1 为 4 。基蠢霓，。墓蠢粤。建蠢霎。j 到4 个邻居的距离矢量图2 2 节点j 的路由缓存表和路由表f i g2 2t h er o u t i n gc a c h et a b l ea n dt h er o u t i n gt a b l eo f n o d ej图2 1 显示了一个子刚。图2 2 的前四列显示了j 节点从邻居路由器接收到的有关链路延迟的路由信息矢量。其中a 节点称它到达节点b 需1 2 微秒的延迟，到c 需要2 5 微秒的延迟，到d 需要4 0 微秒的延迟等等，假定j 测得它邻居a 、i 、h 和k 的延迟分别为8 、1 0 、1 2 和6 微秒，则j 的路由表如图2 2 的最后两列所示。每当网络链路的状态发生变化，与之相连的节点会重新发布路由信息矢量，而接受到该信息的节点则根据新信息来计算更新路由表。2 。3 解决小尺度动态问题一基于时间依赖理论的路由模型及协议2 3 1 时间依赖的混合型网络路由模型h t d n时间依赖的混合型网络路由模型h t d n ( h e t e r o g e n e o u st i m e - d e p e n d e n tn e t w o k s ) 模型的形式化描述如下：用g ( y ，工，7 、) 表示一个时间依赖的网络，其中v = 1 ，2 ，n 是有限结点集且v = v wk av n ，v 。是允许分组等待的结点集，v 。是不允许分组等待的结点集。l v v 是链路集，t = g 。( f ) | ( i ，j ) 工 是对于每一条链路( f ，- ，) 上，在时间f 【屯，o 】区间上定义的函数集，其值域是有限的实数。0 一f 。= 丁咒( t i m et ol i v e ) 是面向n g i 火规模动态特征的路由模型和协议研究该模掣感兴趣的时间周期( 周期的长度确定为网络允许分组生存的最长时间，例如，在i n t e m e t 中，i p 协议定义了相应的字段来决定分组在网络中的生存时间) 。n 表示结点i 的相邻结点集。对于离散时间情况，h t d n 网络模型为c ( v s ，l ，t 1 ，其中s 是离散化之后的时间间隔，即s = t 0t o + ，气+ 2 a ，t o + ( m 一1 ) a ，是较小的时间间隔，在该间隔内可以认为链路的延时不发生变化。m 是使得 矗，岛十m a 成为感兴趣时间周期( 例如，网络流量高峰期间) 的最大整数。v t s ，g 。( f ) 是非负实数tf + 岛( t ) 总是有定义：对于，乇+ m a ，定义岛( ，) = o 。v x s = ( i ，f 川f e v r t ，e s ) ，表示结点的状态空问，有序对f f ，t ，1 表示结点的一个状态。同一个结点在不同时刻的状态各不相同。在后面的叙述中将用到的一些术语定义如下：定义2 1 ：考虑分组在结点i 产生( 以结点i 为起始结点) 或者到达结点i ( 结点i是分组传输过程的中间结点) 等待转发的时刻称为分组在结点i 准备好的时刻。定义2 2 ：设分组经过的结点序列为( 扎如，) ，分组在相应结点准备好的时刻序列为( ，。，：，) ，定义兀。( ，。) = ( ，) ，( ，。) ，( ，t 3 ) ，( + 一，) ，( ，) 为时刻从结点f ，到结点的一条时间依赖的路径，_ 尸d ( 兀。( f ，) ) = 一 是时间依赖路径1 - i 。( f i ) 的延时值。两结点之间的结点序列不同，或者分组在结点准备好的时刻不同，两结点之间时间依赖的路径也就不同，并且两结点之间可以存在多条时间依赖的路径。定义2 3 ：给定网络g ( y ，l ，t ) 、起始结点、目的结点和分组在结点f 。准备好的时刻“摄优延时路径问题定义为：寻找兀“) = ) ，( “) ，( “) ，( o ，( ，) )使得对于v 兀。( ) = ( f t ，f i ) ，( f 2 ，f 2 ) ，( ，毛) ，( m 一t ) ，( o ，) ，有1 2 ( 2 1 )人近理| _ 人学硕十学位论文p d ( 兀i 。( ) p d ( 丌。( r i ) ) ；( 2 2 )则称路径兀：。( ) 为最优延时路径。定义2 4 ：在h f l d n 模型中，设t 时刻从结点i 通向目的结点d 的某条时问依赖路径的延时值为p d ( n ：( f 。) ) ，则集合：d = d 。( r ) i d 。( r ) = p d ( n ：( r 1 ) ) ，ze y ，de 矿一 z ，r 【，r 。，】( 23 )为从节点i 到节点d 的所有时问依赖路径的延时值集合。定义2 5 ：在h t d n 模型中，令f 。h ， 表示该分组从i 结点发送的任意时刻，对于不允许等待的结点，默认为f = t 。2 3 2 基于洲) n 路由模型的路径最优化理论f d n 网络模型与传统的静态网络模型4 曰比，有本质的不同。由于链路权值的时刚依赖性，传统的d i j k s t r a 最优路径算法和标号设置算法不能正确求解t d n 网络中的最优路径问题 4 。基于h t d n 网络的特点，本文提出了下面的定理2 1 ，浚定理是h t d n网络中最优路径算法的理论基础，h t d n 网络分布式路由协议也是在此基础上设计的。定理2 1 ：口。( f ) 耿最小值的充分必要条件是对于w n ，v t 【f f 。】，均有d 。( ，) f + g ，( f 1 ) + d ( f 1 + 岛( r ) ) 成立。证明：必要性：如果d 集合的每个元素9 。，( ，) 都表示t 时刻在结点i 准备好的分组通向目的结点d 的最优延时路径的延时值，假设可n 。，t ，f 。，】( 对于、允许等待的结点，有f = ，) ，( r ) f + 岛( f _ ) + d + 岛( r ) ) ，那么t 时刻在结点i 准备好的分组等待到，。时刻，再经过j 结点到达目的结点d 的延时值比口。( ，) 还小，这与口。( ，)的性质榭矛盾。所以定理4 1 的必要性成立。充分性：如果剥于d 集合的每个元素d ；a ( f ) ，w n 。，v t 【f ，t ， ( 对于不允许等待的结点，有f = f ) ，口d ( f ) 玉r g 。( f + d s at + 岛( f ) ) 都成立，那么对于路径兀。( f ) = 黔f ) ，( f 。1 ) ，( ，t 2 ) ，( f = ；，屯) ，l ，( 一，) ，( d ，v t le 【r ，o ，v t ；eh ，】，v f ! h l 。 ，l ，v h t 。， 有：1 3 耍塑型鱼! 丛型堡垫查堑堑塑堕虫塑型! l i 塑望堕塑一一哦f ( ，) l - i + g o ) + d ，。，0 。+ g o ) ) = t - r + g 。u ) + d q d o i )口，d ( ，1 ) ，1 。一，l + g 叫，( t l ) + 口2 d ( t l + 蜀止( ) ) = ，l 。一+ g ：( ) 十口，“( f 2 )d ，。“( ，2 ) 2 。- - 1 2 + g 川，( r 2 。) + d l l 。l ( r 2 + g ，( r 2 ) ) = ，2 f 2 + g ，( f 2 ) + p “( f 3 )l口肛一( f 肛i ) i l 1 + g k ，。( 一】) + 三k ( ，。l + g 。n ( f 肛1 ) ) = i n - ij - - i n l + g k d ( t o 】)将以卜所有不等式两边相加得到：d , a ( t ) r - ，+ g h 0 ) ) + ( ，1 一f 1 + g 州：( ) ) + ( t 2 - 1 2 + g 叫；( ，2 ) ) + a + ( f 。一1 一i h + g 。“( f