（无线电物理专业论文）提高网络qos的蚁群路由算法研究.pdf

中山人学颂i ：学位论文 提高网络q o s 的蚁群路由算法研究 专业：无线电物理 硕士生：陈秀英 指导老师：秦家银教授张琳副教授 摘要 网络技术的飞速发展远远不能满足媒体业务发展的需求。网络传输的业务 不仅包括文本数据信息，还包括语音、图形、图像、视频、动画这些类型的多媒 体信息。随着多媒体业务需求的r 益增长，对这些有带宽、延迟、延迟抖动、丢 失率、吞吐量等特殊要求的应用来说，现有的“尽力而为”的服务显然是不够的。 因此需要采用q o s ( q u a l i t yo f s e r v i c e ) 服务质量研究，而q o s 路由算法的研究 是支持q o s 服务研究的重要分支。 蚁群算法能很好地解决组合优化问题，不依赖于具体问题的数学描述，善于 利用不确定信息，具有全局优化能力和本质上的并行性，并且具备较强的鲁棒性、 求解时问短、易于计算机实现等优点。蚁群算法的这些特性使其适用于解决如今 多q u s 要求的网络路由问题。 论文就蚁群算法解决q o s 路由问题进行了研究分析。论文首先阐述了q u s 路由技术和蚁群算法原理及几种常见的改进，并介绍了它们的研究现状。然后提 出了一种具有变异的动态全局信息素更新的蚁群算法改进策略。该算法在a c s ( a n tc o l o n ys y s t e m ) 算法的基础上，增加了一种适用于q o s 路由的变异策略， 采用全局更新和局部更新的同时，还加入了动态局部更新参数，并限制了全局更 新范围。论文用c + + 语言对该蚁群算法进行实验分析，并与其它两种经典蚁群算 法：a c s 算法和最大最小蚁群算法进行了比较，由实验结果分析可知该改进的 蚁群算法具有解的多样性、参数要求低、收敛性好、有效防止了停滞问题等优点， 验证了该算法用于解决q o s 路由问题的有效性。 关键记：q o s ，路由，蚁群算法，变异，动念信息素 中山人学坝i 学位论文 r e s e a r c ho na n tc o l o n yr o u t i n ga l g o r i t h mf o r i m p r o v in gn et w o r kq o s m a j o r ：r a d i op h y s i c s n a m e ：c h e nx i u y i n g s u p e r v i s o r ：p r o f e s s o rq i nj i a y i n a s s o c i a t ep r o f e s s o rz h a n gl i n a b s t r a c t t h er a p i dd e v e l o p m e n to ft h en e t w o r kt e c h n o l o g yi sf a rf r o ms a t i s f y i n gt h e t r e m e n d o u sd e m a n d so f m u l t i m e d i ab u s i n e s s e s n e t w o r kn o to n l yt r a n s m i t sd a t a m e s s a g e s ，b u ta l s o k i n d so fm u l t i m e d i am e s s a g e sl i k es o u n d ，g r a p h i c s ，v i d e o ， a n i m a t i o n t h es e r v i c eo fb e s t e f f o r tc a l ln o ts a t i s f ya l lt h e s er e q u i r e m e n t s t h e r e b y , q o s ( q u a l i t yo fs e r v i c e ) w a sp r o p o s e dt o r e s o l v et h ep r o b l e m n o w a d a y s ，i th a s b e c o m ea ni m p o r t a n ti s s u ei nn e t w o r k a so n eo fi t sb r a n c h e s ，q o sr o u t i n gi s e s p e c i a l l yak e yp r o b l e m a n tc o l o n ya l g o r i t h mh a sb e e np r o v e dt oh a v em a n ya d v a n t a g e s t h em a i n c h a r a c t e r i s t i co ft h i sm o d e la l ep o s i t i v ef e e d b a c k ，d i s t r i b u t e dc o m p u t a t i o n , a n dt h e u s eo f ac o n s t r u c t i v eg r e e d yh e u r i s t i c i ti s9 0 0 da tu t i l i z eu n c e r t a i nm e s s a g e s ，a n dc a n d e a lw i t hc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sp e r f e c t l y t h e s ee x c e l l e n tp r o p e r t i e s j u s tf i tt om u l t i p l eq o sr e q u i r e m e n t si nn e t w o r kr o u t i n g t h e r e b y , t h i st h e s i sf o c u s e so nr e s o l v eq o sr o u t i n gi nn e t w o r ku s i n ga n tc o l o n y a l g o r i t h m f i r s t l y , t h i st h e s i sr e v i e w st h er e l e v a n tp r i n c i p l e so fq o sr o u t i n ga n da n t c o l o n ya l g o r i t h m ，a n dt h e nd i s c u s s e ss e v e r a le f f e c t i v ei m p r o v e m e n t so fa n tc o l o n y a l g o r i t h m ，a sw e l l a st h es t u d ys t a t u sr e c e n t l y t h e n , a ni m p r o v e da n tc o l o n y a l g o r i t h mw i t hm u t a t i o na n dd y n a m i cl o c a lp h e r o m o n eu p d a t i n gi sp r o p o s e d t h e i m p r o v e da l g o r i t h mi s b a s e do nt h ea n tc o l o n ys y s t e m ( a c sa l g o r i t h m ) a m u t a t i o ns t r a t e g yw a sa d d e dt oa c sa l g o r i t h m a n dt h ea l g o r i t h mu s e sb o t hg l o b a l p h e r o m o n eu p d a t i n ga n dl o c a lp h e r o m o n eu p d a t i n g , m e a n w h i l e , r e s t r i c tt h ea c t i v e h i 中山人学硕士学位论文 r a n g eo fg l o b a lp h e r o m o n eu p d a t i n ga n du s ead y n a m i cg l o b a lp h e r o m o n eu p d a t i n g p a r a m e t e r t h et h e s i s n s e sc + + l a n g u a g et o i m p l e m e n t t h ea l g o r i t h m t h e p e r f o r m a n c ec o m p a r i s o nb e t w e e nt w oc l a s s i c a la n tc o l o n ya l g o r i t h m s ( a c sa l g o r i t h m a n dm a x - m i na n tc o l o n ya l g o r i t h m ) ，d e m o n s t r a t et h a tt h ei m p r o v e da n tc o l o n y a l g o r i t h mi so fd i v e r s i t yr e s u l t ，l o wr e q u i r e m e n tf o rp a r a m e t e r s ，q u i c kc o n v e r g e n c e ， a n ds t a g n a t i o nm o v e m e n t t h ep r o p o s e di m p r o v e da l g o r i t h mi sa l s op r o v e dt ob e e f f e c t i v et od e a l i n gw i t hq o s r o u t i n gp r o b l e m s k e yw o r d s ：q o s ，r o u t i n g , a n tc o l o n ya l g o r i t h m ，m u t a t i o n , d y n a m i cp h e r o m o n e 中山大学颂 ：学位论史 第1 章绪论 1 。1q o $ 路由问题及研究现状 在传统的i p 网络中，所有的报文都被无区别的对待。路由器对报文均采用 先入先出( f i f 的策略进行处理，尽最大的努力( b e s t - e f f o r t ) 将报文送到目的地， 即对所有业务请求都会接受，并且只要具有同样的源地址和目的地址就会在同一 路径上传输。这样的设计可能会导致网络负载分配不均匀，业务无法被保证准确、 及时地传输到目的地址，对报文传送的可靠性、延迟等性能不提供任何保证。随 着网络技术的飞速发展，特别是随着多媒体业务的兴起，计算机己经不是单纯的 数据处理工具。带宽的增加、地址空间的扩大、用户数目的激增，带来的是应用 和业务的不断推陈出新和网络吞吐量的急剧增加。当今分布式多媒体应用( 如视 频会议、视频点播、i p 可视电话、远程教育、网络游戏1 ，不仅包括文本数据信 息，还包括语音、图形、图像、视频、动画这些类型的多媒体信息。对这些有带 宽、延迟、延迟抖动、丢失率、吞吐量等特殊要求的应用来况，现有的“尽力而 为”的服务显然是不够的。所以，支持多媒体数据和实时数据传输的需求对新一 代网络提出了新的要求。 据此，i e t f ( i n t e m e t 规划与发展的主要标准化组织) 首先提出了服务质量 ( q u a l i t yo fs e r v i c eq o s ) 保证的概念【l 】。q o s 旨在针对口网络中各种应用业务的 不同需求，为其提供不同的服务质量，例如提供专用带宽、减少报文丢失率、降 低报文传送时延及时延抖动等。而q o s 路由算法的研究是支持q o s 服务研究的 重要分支。在实际的网络中，这种具有q o s 保证的路出算法的性能在很大程度 上要依赖于网络中路由节点和链路的可用资源的信息。但是，这些信息并不是总 能够得至4 及时有效的更新，从而会直接影响网络的服务质量。另一方面，网络全 局状态信息具有不精确性，原因是：1 ) 局部网络状态的改变广播到其他路由节 点需花费不可忽略的传播时延；2 ) 网络状态信息不可能频繁更新，否则会花费 过多的网络资源；3 ) 分层路由方案的使用会增加网络状念非精确的程度。如何 表达和捕捉网络状态的这些不精确性，最终找到一条具有最大可能性满足q o s 约束条件的路由就成了当前实际网络进行q o s 路由选择时所面临的关键问题， 中山大学硕l 学位论文 也成为很多学者研究的热点。 路由算法已有很多种，常见的有b e l l m a n f o r d 算法【2 1 、d i j k s t r a 算法【3 1 等。 b e l l m a n f o r d 算法属于距离向量路由算法，它在小系统中工作的很好，但当a s ( a u t o n o m o u ss y s t c i l l ，自治系统) 变大后，就不行了，而且还受到无限计算问 题的困扰，收敛性慢；d i j k s t r a 算法是典型最短路算法，属于链路状态路由算法， 这种方法具有直观简单、易于推广等优点，但由于遍历计算的节点多，所以效率 低。 蚁群算法是近十几年新兴的一种群智能算法，该算法不依赖于具体问题的数 学描述，具有全局优化能力和本质上的并行性，同时比遗传算法、模拟退火算法 等进化算法具备更强的鲁棒性、求解时间短、易于计算机实现等优点【5 】。蚁群算 法所具有的这些特性，能很好的解决不精确信息的复杂的网络路由问题。因此， 本文拟采用蚁群算法实现o o s 路由。 1 2 蚁群算法的研究现状 蚁群算法是一种启发式算法，它源于对蚂蚁群体搜索行为的研究。它是由意 大利学者m d o r i g o 等人于1 9 9 1 年提出的，该算法模仿蚂蚁觅食的行为，按照 启发式思想，通过信息传媒信息素( p h e r o m o n e ) 的诱导作用，逐步收敛到问题的 全局最优解。接着，m d o r i g o 等人于1 9 9 6 年在i e e e 刊物上又发表了一篇奠 基性论文，文中对蚁群系统的最基本模型和特点进行了综合分析，并通过实例仿 真讨论了该模型的特征和应用【1 5 1 。 自1 9 9 1 年蚁群算法提出后，针对网络的路由优化问题，各国学者都从不同 角度对基本的蚁群算法做了不同改进。文献【6 】差要运用蚁群算法解决网络负载 问题，文献【7 】主要是解决网络路由停滞问题，文献【8 】、【9 】、【1 0 】则主要解决多 播路由问题，文献【l l 】主要是解决移动a dh o e 网络路由的节能问题，文献 1 2 】 解决网络路由的时延问题，文献【1 3 】提出了一种新的路由表更新方法，文献 1 4 】 提出了一种自适应的蚁群算法，等等。 从当酶可以查阅的文献情况来看，研究和应用蚁群算法的学者主要集中在比 利时、意大利、英国、法国、德国等欧洲国家；同本和美国也在算法提出这一两 年内开始了对蚁群算法的研究；国内于1 9 9 8 年木爿丌始有少量的公开报道和研 2 中山人学硕i 学位论文 究成果，而且基本局限于t s p 问题上，但在近几年出现了许多利用蚁群算法求 解各种问题的文章，求解的问题有车辆路径问题1 2 l 】、组播路由问题f 2 2 】、生产调 度问题、组合优化问题【2 3 1 等。 本文拟研究蚁群算法，并对算法进行了改进。本文则提出了一种具有变异的 动态局部更新参数蚁群算法，解决网络路由问题，并证实了它的优越性。 1 3 论文的主要内容和结构安排 本文针对影响网络q o s 的关键问题q o s 路由做了分析研究，提出一种改进 的蚁群算法一具有变异的动态局部更新参数蚁群算法，来解决q o s 路由选择 问题，并用实验比较证明该改进的蚁群算法较其它蚁群算法的优越性。 本文的结构安排如下： 第一章：首先提出论文将要研究的问题q o s 路由问题，指出本文将用 一种改进的蚁群算法解决该问题。接着简单介绍了q o s 路由问题和蚁群算法目 前国内外的研究状况。 第二章：介绍了q o s 路由的相关技术，先分别介绍了q o s 技术和路由技术 的相关知识，然后阐述了q o s 路由的模型及常用的算法。 第三章：介绍了蚁群算法的起源、算法原理和模型、改进思想，以及几种较 优的改进算法，最后提出一种具有变异及动态全局信息素更新的蚁群算法一改 进的a c s 算法。 第四章：分析了改进的a c s 算法的各关键参数的作用，并用c + + 语言实现 算法，分析比较此改进的蚁群算法与a c s 算法和最大最小蚁群算法各自的优劣， 证实了该算法的有效性。 第五章：对论文做了总结。 中山人学硕i ：学位论文 第2 章q o s 路由技术 2 1o o s 概述及其定义 任何服务都需要考虑质量，在通信和计算机网络中，服务质量简称q o s ( q u a l i t yo f s e r v i c e ) 。q o s 的提出始于a t m 交换机。学术界普遍认为q o s 有广 义和狭义之分：狭义q o s 指技术指标( 传输时延、抖动、丢失率、带宽要求、 吞吐量等) ；广义q o s 指资源调配与利用、层与层之问的协商，从而涉及不同层 次的q o s t 。这里的蚁群路由算法主要是研究狭义q o s 。 服务质量保证q o s 的核心思想就是针对不同客户或不同业务特性的要求， 尽可能地提供好的服务质量。服务质量体现的是消费者对服务者所提供服务的满 意程度，是对服务者服务水平的一种度量和评价。现代计算机网络作为计算和信 息等服务的提供者，在当i j 高速网络中按照用户的要求提供q o s 控制是一个普 遍的要求。通过研究网络q o s ，可以提高网络资源利用率，降低网络成本。网络 运营商可以通过提供q o s 机制，根据不同用户对q o s 的不同要求，提供多种有 区别的服务，提高客户满意度，同时提高网络运营商的经营收益。 q o s 的研究包括多个方面：接纳控制( a d m i s s i o nc o n t r 0 1 ) ，拥塞控制 ( c o n g e s t i o nc o n t r 0 1 ) ，流量整形( t r a f f i cs h a p i n g ) 、队列缓冲管理( b u f f e rs h a r i n g ) 、分 组调度( p a c k e ts c h e d u l i n g ) ，q o s 路由( q o sr o u t i n g ) 等。其中，流量整形、队列缓冲 管理、分组调度等是提高q o s 在节点控制方面的途径。q o s 的前期研究，主要 集中在接纳控制、拥塞控制、队列缓冲管理和分组调度策略上。q o s 路由算法是 对整个网络或局部网络控制的途径，它通过对路由与信令的控制，达到对业务流 或业务连接在网络中传输的直接控制。近几年的研究表明它对实现网络保证服务 质量起到了非常关键的作用，同时网络q o s 路由算法也是平衡网络负载和充分 利用网络资源的重要保证。 当前，不同的目际组织对q o s 有不同的定义，但其目的都是为用户提供更 好的服务，同时有效地利用网络资源。q o s 的主要定义如表2 一l 所示，q o s 在i e l 下 中定义为“as e to f s g r v i g er e q u i r e m e n t st ob em e tb yt h en e t w o r kw h i l et r a n s p o r t i n ga f l o w ”，即网络在传输数据流时要满足的一系列服务要求，具体可以量化为传输 5 中山大学硕 学位论文 时延、抖动、丢失率、带宽要求、吞吐量等指标【1 j 。 表2 - 1q o s 在不同标准中的定义【1 】 编号q o s 定义标准 lt h i sa t t r i b u t ei sd e s c r i b e db yag r o u po fs p e c i f i cs u b - a t t r i b u t e s ，f o r l 1 0 4 e x a m p l e ：s e r v i c er e l i a b i l i t y , s e r v i c ea v a i l a b i l i t y t h ev a l u e s a r e u n d e rs t u d y 2t h ec o l l e c t i v ee f f e c to fs e r v i c ep e r f o r m a n c ew h i c hd e t e r m i n e st h ee 8 0 0 2 1 0 1 d e g r e eo f s a t i s f a c t i o no f au s e ro f t h es e r v i c e 3as c to fq u a l i t yr e q u i r e m e n t so nt h ec o l l e c t i v eb e h a v i o ro fo n eo rx 9 0 2 m o r eo b j e c t s q o sm a yb es p e c i f i e di nac o n t r a c ta n dr e p o r t e da r e r t h ee v e n t ，t h eq o sm a yb ep a r a m e t e r i z e d 4t h ec o l l e c t i v ee f f e c to fs e r v i c ep e r f o r m a n c ew h i c hd e t e r m i n e st h ey 1 0 1 5 2 d e g r e eo f s a t i s f a c t i o no f a u s e ro f t h es e r v i c e 5i n f o r m a t i o ns e n ti nt h ef o r w a r dd i r e c t i o nt oi n d i c a t et h eq o sc l a s s q 2 7 6 2 r e q u e s t e db yt h eu s e rf o e ac o n n e c t i o n q o sc l a s s e da r ed e f i n e dt o a l l o wan e t w o r kt oa l l o wan e t w o r kt oo p t i m i z er e s o u r c e si n s u p p o r t i n gv a r i o u s s e r v i c ec l a s s e s 6as c to fv a l u e sa s s o c i a t e dt ot h ef o l l o w i n ga t mp e r f o r m a n c e f 8 1 1 p a r a m e t e r s ：e n d t o e n dc a l ll o s sr a t i o ，e n d t o - e n dc e l lt r a n s f e r d e l a y , e n d - t o e n dc e l ld e l a y v a r i a t i o n 7as e to fq u a l i t i e sr e l a t e dt ot h ec o l l e c t i v eb e h a v i o ro fo n eo rm o r ex 6 4 2 ，3 2 o b j e c t s c o l l e c t i v ee f f e c to fs e r v i c ep e r f o r m a n c e ，w h i c hd e t e r m i n e st h eg 1 0 0 0 8 d e g r e eo f s a t i s f a c t i o no f a u s e r o f t h es e r v i c ee 4 1 6 e 4 1 7 9i su s e dt os p e c i f yt h er e q u i r e dq u a l i t yo fs e r v i c e ss u c ha sb i te r r o r q 1 7 2 0 r a t e 1 0t h ec o l l e c t i v ee f f e c to fs e r v i c ep e r f o r m a n c ew h i c hd e t e r m i n e st h ee 7 2 6 d e g r e eo f s a t i s f a c t i o no f au s e ro f t h es e r v i c e 6 中山大学硕卜学位论文 l l t h eq u a l i t yo ft h es e r v i c et h a ti n d i v i d u a li n f o r m a t i o ns t r e a m sh 2 2 3 r e c e i v ef r o mt h em u l t i p l e x e r , a sm e a s u r e db yp a r a m e t e r ss u c ha sh i t r a t e , d e l a y j i t t e r , l o s s ，e t c 1 2t h ec o l l e c t i v ee f f e c to fs e r v i c ep e r f o r m a n c ew h i c hd e t e r m i n e st h ej 1 4 5 d e g r e eo f s a t i s f a c t i o no f a u s l 目ro f t h es e r v i c e m 6 0 3 0 1 8 1 3 a n yp e r f o r m a n c ev a r i a b l “s u c ha sc o n g e s t i o n , d e l a y , e t c ) w h i c hi s e 6 0 0 p e r c e i v a b l eb ya u s e l - 1 4t h e t o t a l i t yo fc h a r a c t e r i s t i c so fa ne n t i t yt h a tb e a ro ni t sa b i l i t yt o i s 0 9 0 0 0 s a t i s f ys t a t e da n di m p l i e dn e e d s 2 2 路由 2 2 1 路由原理 当i p 子网中的一台主机发送i p 分组给同一m 子网的另一台主机时，将 直接把i p 分组送到网络上，对方就能收到。而要送给不同i p 子网上的主机时， 它要选择一个能到达目的子网上的路由器，把口分组送给该路由器，由路由器 负责把i p 分组送到目的地。如果没有找到这样的路由器，主机就把i p 分组送 给一个称为“缺省网关( d e f a u l tg a t e w a y ) ”的路由器上。“缺省网关”是每台主机 上的一个配置参数，它是接在同一个网络上某个路由器端口的i p 地址。 路由器转发i p 分组时，只根据i p 分组目的i p 、地址的网络号部分选择合 适的端口，把i p 分组送出去。同主机一样，路由器也要判定端口所接的是否是 目的子网，如果是，就直接把分组通过端口送到网络上；否则，就要选择下一个 路由器来传送分组。路由器也有它的缺省网关，用来传送不知道往哪儿送的i p 分组。这样，通过路由器把知道如何传送的i p 分组证确转发出去，不知道的l p 分组送给“缺省网关”路由器，这样一级一级地传送，l p 分组最终将送到目的 地，送不到目的地的l p 分组则被网络丢弃。 目的t c p i p 网络，全部是通过路出器互连起来的，i n t e r n e t 就是成千上万 个l p 子网通过路出器匠连起来的国际性网络。这种网络称为以路由器为基础的 网络( r o u t e r b a s e d n e t w o r k ) ，形成了以路由器为节点的“网阳j 网”。在“网1 日j 网” 7 中山大学硕 ：学位论立 中，路由器不仅负责对i p 分组的转发，还要负责与别的路由器进行联络，共同 确定“网问网”的路由选择和维护路由表。路由动作包括两项基本内容：寻径和 转发。寻径即判定到达目的地的最佳路径，由路由选择算法来实现。由于涉及到 不同的路由选择协议和路由选择算法，要相对复杂一些。为了判定最佳路径，路 由选择算法必须启动并维护包含路由信息的路由表，其中路由信息依赖于所用的 路由选择算法而不尽相同。路由选择算法将收集到的不同信息填入路由表中，根 据路由表可将目的网络与下一站( n e x t h o p ) 的关系告诉路由器。路由器问互通信 息进行路由更新，更新维护路由表使之正确反映网络的拓扑变化，并由路由器根 据量度来决定最佳路径。这就是路由选择协议( r o u t i n gp r o t o c 0 1 ) ，例如路由信息 协议( r i p ) 、开放式最短路径优先协议( o s p f ) 和边界网关协议( b c p ) 等。 转发就是沿寻找好的最佳路径传送信息分组。路由器首先在路由表中查找， 判明是否知道如何将分组发送到下一个站点( 路由器或主机) ，如果路由器不知道 如何发送分组，通常将该分组丢弃；否则就根据路由表的相应表项将分组发送至q 下一个站点，如果目的网络直接与路由器相连，路由器就把分组直接送到相应的 端口上。这就是路由转发协议( r o u t e dp r o t o c 0 1 ) 。 ， 2 2 2 路由协议 根据是否在一个自治域内部使用，动念路由协议分为内部网关协议( 1 g p ) 和 外部网关协议( e g p ) 。这罩的自治域是指一个具有统一管理机构、统一路由策略 ，一 的网络。自治域内部采用的路由选择协议称为内部网关协议，常用的有r i p 、 o s p f ；外部网关协议主要用于多个自治域之白j 的路由选择，常用的是b g p 。下 面分别进行简要介绍。 2 2 2 1 路由信息协议( r i p l 协议最初是为x e r o x 网络系统的通用协议而设计，是i n t e m e t 中常用的路 由协议。r i p 采用距离向量算法，即路由器根据距离选择路由，所以也称为距离 向量协议。路由器收集所有可到达目的地的不同路径，并且保存有关到达每个目 的地的最少站点数的路径信息，除到达目的地的最佳路径外，任何其它信息均予 以丢弃。同时路由器也把所收集的路由信息用r i p 协议通知相邻的其它路由器。 这样，j 下确的路由信息逐渐扩散到了全网。r i p 使用非常广泛，它简单、可靠， 8 中山人学硕i ：学位论文 便于配置，但是r i p 只适用于小型的同构网络，因为它允许的最大站点数为十 五，任何超过十五个站点的目的地均被标记为不可达，而且r i p 每隔三十秒一 次的路由信息广播也是造成网络的广播风暴的重要原因之一。 2 2 2 2 开放式最短路径优先协议( o s p f ) 八十年代中期，r i p 己不能适应大规模异构网络的互连，o s p f 随之产生。 它是由网间工程任务组织的内部网关协议工作组为i p 网络而开发的一种路由协 议。o s p f 是一种基于链路状态的路由协议，需要每个路由器向其同一管理域的 所有其它路由器发送链路状态广播信息。在o s p f 的链路状态广播中包括所有接 口信息、所有的量度和一些其它变量。利用o s p f 的路由器首先必须收集有关的 链路状态信息，并根据一定的算法计算出到每个节点的最短路径。而基于距离向 量的路由协议仅向其邻接路由器发送有关路由更新信息。 与r i p 不同，o s p f 将一个自治域再划分为区，相应的有两种类型的路由 选择方式：当源和目的地在同一区时，采用区内路由选择：当源和目的地在不同 区时，则采用区间路由选择。这就大大减少了网络开销，并增加了网络的稳定性。 在一个区域内的路由器出了故障时并不影响自治域内其它区域路由器的正常工 作，这也给网络的管理维护带来了方便。 2 2 2 3 外部网关协议( b g p l 是为t c p i p 互联网设计的外部网关协议，用于多个自治域之间。它既不是 基于纯粹的链路状态算法，也不是基于纯粹的距离向量算法。它的主要功能是与 其它自治域的b g p 交换网络可达信息。各个自治域可以运行不同的内部网关协 议。b g p 更新信息包括网络号、自治域路径的成对信息。自治域路径包括到达 某个特定网络必须经过的自治域串，这些更新信息通过t c p 传送出去，以保证 传输的可靠性。 2 2 3 路由选择的目的和要求 在通信子网中，网络节点在收到一个分组后，要确定传输的路径，并向下一 个节点转发，这就是路由选择。路出选择的目的和要求有以下几点： 1 ) 能证确、迅速、合理地传送报文信息。 2 ) 能适应网络内节点或链路故障而引起的拓扑变化，使报文在故障条件下 9 中山大学硕i j 学位论文 一般能到达终点。在发生故障时，允许某些线路的通信量过载而增加时延。 3 ) 能适应网络流量的变化，使各条通路的流量均匀，整个网络的通信设备 负荷平衡，充分发挥效率。 4 ) 算法尽量简单，以减少网络开销。 2 2 4 路由选择算法 理想的路由选择算法具有如下特点： 1 ) 正确性算法必须正确。 2 ) 计算简单算法应使用节点上最少的运行资源，这样可以节省开销、减少 时延，而且应该使用节点问链路的带宽，如果为了计算合适的路由必须使用网络 其它节点发来的大量状态信息，额外开销就会较大。 3 ) 自适应性或称健壮性：算法能适应业务量和网络拓扑的变化。当网络中 的业务量发生变化时，算法能自适应地改变路由。当节点、链路出现故障时或修 复后重新工作时，算法能及时找到一条替换的路径。 4 ) 稳定性算法必须收敛，当业务负载和拓扑变化时，没有过多的振荡。振 荡就是算法得出的路由是在一些路由之问来回不停地变化。 5 ) 公平性算法对所有的用户必须是同等的，仅指在分配的优先级范围内。 例如，仅考虑使某一对用户的端到端时延最小，就不符合公平的要求。 6 ) 最优性路由选择算法应该能提供最佳路由，从而使平均分组时延最小而 吞吐量最大。这里“最佳”可以是由多个因素决定的，如链路长度、数据率、链 路容量、传输时延、节点缓冲区被占程度、链路的差错率、分组丢失率等。显然 不存在一种绝对的最佳路由算法，所谓“最佳”只能是相对某一特定要求下得出 的较为合理的选择而已。 实际上没有一个算法能全部满足上述要求，有的还可能是矛盾的，例如，要 使吞吐量最大就有可能增加时延。然而，路由选择算法的效能可能影响时延随吞 吐量增加的快慢，而且一个好的算法可能得到一个较好的吞吐门限，在这个门限 值上时延过大就必须进行控制。 一个理想的路由选择算法应保证所选路径的币确性和简单性，并能适应通信 量和网络拓扑的变化，还应具有稳定性、公平性和最优性的特点。一个实际的路 1 0 中l 【1 大学颂l 学位论史 由选择算法，应尽可能接近于理想的算法。在不同的应用条件下，对以上几个方 面也可有不同的侧重。 路由选择算法有很多种，基本上分为静态路由选择算法和动态路由选择算法 两大类。如今因特网中通常使用的路由算法为动态路由选择算法。下面介绍这两 类中几种常用的路由选择算法。 2 2 4 1 静态路由选择算法 静态路由算法又称为非自适应算法，是按某种固定规则进行的路由选择。其 特点是算法简单、容易实现，但效率和性能较差。属于静态路由算法的有以下几 种： 1 ) 固定路由选择算法( 最短路由法) 这种方法是在每个网络节点上存储一张路由表，表中每一项记录着对每个目 的地址的转发路径，即从表中可以查到转发的下一个节点。这些路由表在整个系 统进行配置时生成，此后相当长一段时问保持固定不变。如果表中对每个目的地 址仅给出一条转发路径( 如最短路径) ，就称为固定单路由选择算法。固定单路由 选择算法易造成全网信息流量的不均衡，应变能力也较差。另一种固定多路由选 择算法除了在表中给出了一条最佳路径，还给出了次佳的多条路径。当信息量过 分集中于最佳路径时，可将分组引导到其它链路。通常在节点中设立一个伪随机 数发生器，按路径的使用率将产生的伪随机数分段，并分别控制多条链路实现负 载分配。 2 ) 扩散式路由选择算法( 洪泛式算法) 扩散式路由选择算法又称为洪泛式算法，是欧洲r a n d 公司提出的军用分 组交换网采用的路由选择方法。其基本思想是，当一个节点收到一个不是发给它 的分组时，就立即将其复制若干份副本分发到所有的相邻节点中去，如洪水泛滥 一样。只要目标节点是可达的，分组总能送至目的地。当网络的通信量很小时， 可使分组的时延为最小，而且在许多条并行发送的路由中，肯定有一条是最佳的。 但是，出于网中分组副本太多，降低了网络资源的利用率，容易导致拥塞现象的 发生，因此需要采用某些方法来限制分组的数目，防止分组的无限循环转发。如 在分组的报头中设置一个计数器，每转发一次，计数器值加1 ，当计数器值超过 规定值时，即将此分组丢弃。另一种方法是在每一个节点建立一张登记表，对经 中山大学硕：仁学位论文 过此节点的分组进行登记，当分组再经过此节点时将其予以丢弃。 可将扩散式算法修改成选择扩散式算法，由节点选择向着靠近目标节点的方 向发送分组，从而降低额外信息量的代价。 扩散式算法十分简单，不需要路由表，且不论网络发生什么故障，它总能自 动找到一条路由到达目的地，可靠性很高。但是，它会造成网络中无效负荷的剧 增，导致网络拥塞。因此这种方法一般只用在可靠性要求特别高的军事网络中。 3 ) 随机走动法( 热土豆法) 热土豆算法( h o tp o t a t o ) 每收到一个分组，不管其目的地址是什么，都将它 放在该节点最短的输出队列中，以使它尽快脱手离开本节点，就像拿到一个烫手 的热土豆一样。虽然选择的不是最佳路由，但减少了分组在各节点的排队等候时 间。 2 ) 最短队列加偏置的方法( s q + b ) 这种方法考虑到最短队列的方向不一定为正确的转发路由，因此在每个队列 长度( s q ) 的基础上再增加一个对于某个目的地址的偏移值( b ) ，以二者之和最小 的队列作为转发的方向，b 由每个节点中的最短路由表获得，这种方法又称为 静态路由选择加热土豆的结合算法。 3 ) 反向学习法( b a c k w a r dl e a r n i n g ) 这种算法是根据进入分组中的路由信息来判断自己已有的路由信息是否要 修改。如果进入分组中指出的路由比原来已有的路由好，则进入的路由代替原来 的路由。这样经过反复的学习比较，就能得到最佳的路由选择表。因此，这种方 法即为利用进入节点分组所经过的路径反复比较学习而获得最佳路由，将分组中 的源节点作为目标节点，把进入分组的入口路由作为出口路由的反向学习过程。 2 2 4 2 动念路由算法 动态路由算法又称为自适应算法，是一种依靠网络的当前状念信息束决定路 由的策略。这种策略能较好地适应网络流量、拓扑结构的变化，有利于改善网络 的性能；但算法复杂，实现丌销大。属于动态路由算法的有以下几种： 1 ) 集中式路由选择算法 采用这种方法必须设立一个路出选择控制中一t j , ( r c c 。r o u t i n gc o n t r o l c e n t e r ) ，每个节点定期地向r c c 发送自己的状态信息，如：当前处于运行状态 1 2 中山大学顾i 学位论文 的相邻节点名、队列长度、上次报告状态信息后每条链路处理的通信信息量等。 r c c 负责收集所有节点报告的状态信息，并根据它对整个网络的了解，采用某 种算法为每个节点计算出新的路由表，然后发送到各个节点，更新节点中已经存 在的路由表。因为r c c 拥有整个网络的全局性信息，所以r c c 一般能做出较 完美的决策，同时也减轻了每个节点各自计算路由的负担。但也存在着较严重的 缺点：离r c c 较近的地方通信信息量过于集中，容易造成拥挤；r c c 计算路 由所花的时问长，负担过重；一旦在r c c 中出现故障，对网络影响太大。 2 ) 分自i 式路由选择算法 分布式路由选择算法的思想是，网络中的每个节点定期地与相邻节点交换信 息，每个节点存储一张路由选择表，并不断根据所获得的信息更新其路由表。最 基本的算法有两个：距离向量路由算法和链路状态算法。 距离向量路由算法：距离向量路由算法是早期的a r p a n e t 曾使用过的一 种算法。每个节点存储的路由表中记录着该节点至网上其它节点的输出路由以及 延迟时问( 或距离等) 。若以延迟时间作为度量标准，每个节点可知道至相邻节点 的延迟时问，再根据其从相邻节点获得的路由信息，可以日j 接地求出到网中各节 点的延迟。 链路状态算法：由于采用距离向量路由算法时路由变化需经相邻节点的多次 传递彳+ 能传播到所有节点，存在着收敛较慢的缺点，1 9 7 9 年后的a r p a n e t 采 用了一种新的链路状态路由算法柬代替它。目前广泛使用的一些路由算法都是它 的变形。该算法的基本思想是：每个节点通过与其它节点之间的信息交换获得关 于全网的拓扑信息，从而得知网中所有节点、各个节点自j 的链路连接和各条链路 的代价( 时延、费用等) 。然后将这些拓扑信息抽象成一张带权无向图，并利用最 短路径算法计算出到各个目的节点的最短路径。其主要步骤为： 曲找出所有可达的相邻节点及它们的网络地址； b 1 确定到这些相邻节点的代价： c 1