（通信与信息系统专业论文）基于aco路由算法的研究(1).pdf

哈尔滨工业大学工学项士学位论文 摘要 路由器是工作在网络层上，可以连接不同类型的网络，能够选择数据传 送路径并对数据进行转发的网络设备。为了帮助路由器进行路径判定，应使 用路由算法对路由表进行初始化和维护，路由表中应含有路由信息。路由算 法的设计目标是：寻找最佳的路由；开销最低，需求带宽最小，对路由器的 处理和存储资源利用最小：有良好的适应性、健壮性和稳定性；能够快速收 敛；避免路由的环路等等。 蚂蚁算法是2 0 世纪9 0 年代初开始研究的一种启发式寻优算法，自从它 在旅行推销商问题和二次分配问题上取得了良好的解决效果以来，已开始渗 透到各个领域。本文在对r o t h k r a n t z 等人提出的a b c b a c k w a r d 等基于蚂蚁 算法的路由算法进行研究之后，对其进行改进，在其基础上提出新的算法。 本文包含有以下的内容：第一，对路由算法相关理论进行了研究，介绍 了路由协议的类型，路由算法所要实现的目标以及现有两种路由算法的优缺 点。第二，介绍了蚂蚁算法的原理以及用蚂蚁算法解决问题的思想。第三， 介绍了国内外基于蚂蚁算法的路由算法系列的原理。第四，在这些算法的基 础上，修改了算法的路由表存储结构和路由更新方程以增加其正反馈特性， 实现快速收敛，增加了直选规则和避选规则来避免路由的回路。 经过仿真，该算法与传统路由算法比较发现，将蚂蚁算法应用到路由算 法上可以节省网络带宽、减小路由器存储和处理资源的利用率、具有良好的 可扩展性，对实现大规模网络来说是个很好的选择。 关键词路由算法；蚂蚁算法；蚂蚁群系统 哈尔滨y - k 大学工学硕士学位论文 a b s t r a c t t h er o u t e ri san e t w o r ke q u i p m e n tt h a tw o r k so nn e t w o r k l a y e r ， i sa b l e t ol i n kd i f f e r e n tk i n do fn e t ，a n di sa b l et oc h o o s ep a t ha n dt r a n s m i td a t a s t o h e l pr o u t e rd e t e r m i n ep a t h ，t h er o u t i n ga l g o r i t h mi n i t i a l i z e sa n dm a i n t a i n s r o u tt a b l e ，w h i c hc o n t a i n sr o u t ei n f o r m a t i o n t h e t a r g e t o ft h ed e s i g no f r o u t i n ga l g o r i t h m i st o ：f i n dt h eb e s t p a t h ， c o s tl e a s t ， r e q u i r e t h el e a s t b a n d w i d t h ，u s et h el e a s tr e s o u r c eo ft h er o u t e r s p r o c e s s o ra n dm e m o r y ， h a v eg o o df e a t u r eo f a d a p t i v e ， r o b u s ta n ds t a b i l i z a t i o n ， c o n v e r g e n c ef a s t ， a v o i d p a t h so nc y c l ea n ds oo n t h ea n tc o l o n ya l g o r i t h mi sah e u r i s t i co p t i m i z a t i o na l g o r i t h mr e s e a r c h e d f r o m1 9 9 0 s a f t e rr e s o l v i n gw e l lt h e t r a v e l i n gs a l e s m a np r o b l e m ( t s p ) a n d q u a d r a t i ca s s i g n m e n tp r o b l e m ( q a p ) ， i ti su s e d g r a d u a l l yi nm a n yf i e l d s t h i s p a p e r r e s e a r c h e st h ea b c b a c k w a r d a l g o r i t h mp r o p o s e db yr o t h k r a n t z ， i m p r o v e si ta n dp r o p o s e dan e wa l g o r i t h m t h i sp a p e rd e s c r i b e st h ec o n t e n ta s f o l l o w s ：f i r s t ， s t u d y t h er e l e v a n t t h e o r yo fr o u t i a ga l g o r i t h m ，i n t r o d u c et h ep a t t e r no fr o u t i n gp r o t o c o l ，t h e t a r g e tt h a tt h ed e s i g no fr o u t i n ga l g o r i t h mn e e dt or e a l i z ea n dt h ea d v a n t a g ea n d d i s a d v a n t a g eo ft h er e c e n tt w ok i n do fr o u t i n ga l g o r i t h m s e c o n d ，i n t r o d u c e t h e p r i n c i p l e o fa n tc o l o n y a l g o r i t h ma n dt h eg e n e r a la p p r o a c ho fr e s o l v i n g p r o b l e m w i t hi t t h i r d ，i n t r o d u c et h e p r i n c i p l e o ft h eo v e r s e l l s r o u t i n g a l g o r i t h mf a m i l yb a s e do na n tc o l o n yo p t i m i z a t i o n f o r t h ，o nt h eb a s eo ft h e s e a l g o r i t h m ， a l t e r st h es t r u c t u r eo ft h e r o u t i n g t a b l ea n dt h er o u t e u p d a t i n g e q u a t i o nt or e i n f o r c ei t sp o s i t i v ef e e d b a c kf e a t u r es ot h a tc o n v e r g e n c ef a s t ， a d d sd i r e c t c h o o s er u l ea n da v o i d c h o o s er u l et oa v o i dt h e p a t ho nc y c l e t h r o u 曲t h es i i n u l a t i o na n dc o m p a r i n gw i t ht r a d i t i o n a lr o u t i n ga l g o r i t h m ，w e c a nf i n do u tt h a t ，u s i n ga n tc o l o n ya l g o r i t h mi nr o u t i n ga l g o r i t h mc a ns a v et h e b a n d w i d t h ，r e d u c et h eu s eo fr o u t e r s p r o c e s s o ra n dm e m o r y ，h a v eg o o d e x p a n d i n g f e a t u r e f o rb i gn e t ， i ti sag o o dc h o i c e k e y w o r d s r o u t i n ga l g o r i t h m ，a c o ，a c s 1 i 竺查兰三兰盔兰三耋堡圭兰竺丝塞一。一 1 1 研究意义及课题来源 第1 章绪论 1 9 5 7 年，前苏联发射了一颗人造卫星，使美国人感到震惊。于是美国决定 建立高级研究计划署( a d v a n c e d r e s e a r c hp r o j e c t sa g e n c y ，简称a r p a ) ，来保证 美国的技术跟得上苏联，并于2 0 世纪6 0 年代后期，构造了一个实验性的计算 机网络，叫做a r p a n e t 。后来由于技术与政治上的原因，a r p a 网络计划没 能成功。 1 9 9 2 年，在美国国家计算机应用中心( n c s a ) 工作的m a r ca n d r e e s s e n 和 他的同胞创建了第一个强大的网络浏览器，叫做m o s a i c 。m o s a i e 可以看图 片，播放声音，使用g o p h e r ， f t p ，电子邮件和新闻组。它是一个集成的使 用i n t e m e t 的方案，通过漂亮的图片使它完善。从此，i n t e r a c t 进入了迅速增长 并普及的时代。 现在i n t e r a c t 已经从早期的研究原型成长为覆盖世界上所有国家的全球通 信系统。但是，高速的增长比单纯的规模更令人感到惊讶。i n t e r a c t 在过去的 几年中经历了指数增长，也就是说，i n t e m e t 的规模每过9 个月到1 2 个月就增 长一倍。 1 9 9 8 年，我国在8 6 3 计划中开始对下一代i n t e m e t 技术( n e x tg e n e r a t i o n i n t e r a c t ，n g i ) 的i p 交换设备进行研究，1 9 9 9 年国家自然科学基金会立项在 北京市内几所大学和研究所之间开展n g i 试验性研究。同年，中国科学院、 中国广电总局、铁道部、网通公司等，在中国东部地区1 7 个城市范围进行 n g i 应用性试验。这些试验的主要目标在于寻求新技术，解决目前i n t e m e t 网 上拥挤问题及实时服务的质量问题【1 】。 路由就是基于网络层的选择传送数据包路径的过程。路由器则是执行路由 功能的设备，路由器是在o s i 七层网络模型中的第三层网络层操作的。它的工 作原理是，在网络中收到任何一个数据包( 包括广播包在内) ，都将该数据包第 二层( 数据链路层) 的信息去掉( 称为“拆包”) ，并查看第三层信息( i p 地址) 。然 后，再根据路由表来确定数据包的路由，然后检查安全访问表：如果能够通 过，则进行第二层信息的封装( 又称为“打包”) ，最后才将该数据包转发。此 时，如果在路自表中不能查到对应m a c 地址的网络地址，则路由器将向源地 哈尔滨工业大学工学硕士学位论文 址的站点返回一个信息，然后将这个数据包丢弃。 如果从路口器的工作原理来看，路由器的作用与交换机、网桥非常相似。 但是与工作在网络物理层，从物理上划分网段的交换机不同，路由器则是使用 专门的软件协议从逻辑上对整个网络进行划分。例如，一台支持i p 协议的路 由器可以把网络划分成多个子网段，只有指向特殊i p 地址的网络流量才被允 许通过路由器。路由器对每一个接收到的数据包，都会重新计算其校验值，最 后写入新的物理地址。因此，在网络中使用路由器来转发和过滤数据的速度往 往要比只查看数据包物理地址的交换机慢些。但是，对于那些结构较复杂的网 络，采用路由器来连接网络却可以提高网络的整体效率。路由器的另外一个明 显的优势就是可以自动过滤网络广播。为了帮助路由器进行路径判定，应使用 路由算法对路由表进行初始化和维护，路由表中应含有路由信息。 随着通信与计算机技术的发展，现在人们进入了以i n t e r n e t 发展为主导的 信息时代。综观这些大量使用的i p 网络，实质上是一种低速的网络，它们的 数据传输通常是以某种子网技术为基础的。通常，数据交换是发生在网络的第 l 层或第2 层。作为下一代的高速i p 技术，应该主要体现在第3 层i p 交换路 由技术等方面。而对路由技术的转发的研究就是对路由算法的研究1 2 。 1 2 国内外研究现状 路由协议可以分为静态路由协议和动态路由协议，静态路由协议适合应用 于固定拓扑结构的网络，且不考虑通信中一切动态的信息：动态路由协议中， 路由器可以通过网络来学习网络的拓扑结构，也可以根据网络实时通信状态来 决定数据报的转发策略。所以在研究路由协议时，都是指动态路由协议。 路由信息协议( r o u t i n gi n f o r m a t i o np r o t o c o l ，融p ) 是由x e r o x 公司p a l o a l t o 研究中一t j , f p a r c ) 设计的基于距离向量算法的协议。该协议目前已经在许 多w a n 网络中得到应用，但它原来的设计目标却是针对l a n 网络的。虽然 r i p 有很长的历史，但它还是有自身的限制。它非常适合于为早期的网络互联 计算路由：然而，技术进步已极大地改变了互联网络建造和使用的方式。因 此，r i p 很快被今天的互联网络所淘汰。r i p 协议的局限性包括：( 1 ) 不能支持 长于1 5 条的路径：( 2 ) 依赖于固定路由的度量来计算路由；( 3 ) 路由表更新占用 的网络资源多；( 4 ) 收敛速度相对的慢：( 5 ) 缺乏动态负载均衡支持。 开放最短路径优先( o p e ns h o r t e s tp a t hf i r s t ，o s p f ) 协议是针对r i p 协议 存在的问题而设计的一种基于链路状态算法的路由协议，并已得到广泛应用。 哈尔滨工业大学工学硕士学位论文 = = j = = 自 = ! 一j ! ! ! e ! = ! ! ! ! = = = = # = = = = 目= 自e j d _ t = = # = 目_ 日= j - $ 自_ 目目目$ j o s p f 协议在o s i 协议栈中的等效协议是i s i s ( 中间系统一中问系统) 协议。 边界网关协议( b o r d e rg a t e w a yp r o t o c o l ，b o p ) 主要实现i n t e m e t 中不同路 由域间的路由通告，它克服了原有e g p 协议中的许多问题。b g p 已经成为 i n t e m e t 的一个主流协议，并主要用于各i s p 路由域间的路由处理。 内部网管路由协议( i g r p ) 和增强型i g r f 协议( e i g r p ) 是c i s c o 公司推出的 两个专有路由协议。在许多系统中，e i g r p 协议已经替代了i g r p 协议。这两 个协议与r i p 协议很有类似，但它带有些强化的特性。 蚂蚁算法是2 0 世纪9 0 年代初意大利学者d o r i g o ，m a n i e z z o 提出的一种 源于大自然中生物世界的新的仿生类算法。作为通用型随机优化方法，它吸收 了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制，在一系列困难的组合 优化问题求解中取得了成效。虽然目前没有理论证明蚂蚁算法的实用性，但自 从蚂蚁算法在著名的旅行推销员问题( t s p ) 和二次分配问题( q a p ) 上取得成效以 来，已陆续渗透到其他问题领域中，如工件排序问题、图着色问题、车辆调度 问题、大规模集成电路设计、通信网络中的负载平衡问题等等。1 9 9 6 年 d o r i g o 和s c h o o n d e r w o e r d 等人开始将蚂蚁算法应用到路由算法中，并以英国 电信网为原型进行仿真，取得了令人鼓舞的结果，但是，将蚂蚁算法与路由算 法的结合还在研究中，并有待改善【3 】。 1 3 本文研究内容 蚂蚁算法是一种新型的启发式有自组织能力的优化算法。单个蚂蚁的行为 是极其简单的，但是蚂蚁群能利用蚂蚁群体中个体之间相互作用的正反馈特性 加速系统整体优化的过程，这种算法无需进行大量的概率计算或建立复杂的数 学模型来进行系统预测等，它并不给网络信令系统增加很多负担，所以，很容 易实现。尤其是当网络的规模很大、系统运行动态多变的情况下，人们很难为 系统建立一个较准确的数学模型，来进行集中控制。而且，蚂蚁算法对网络拓 扑结构也无特殊要求。蚂蚁算法的这些特点，决定了将它和路由算法结合起来 将是一个很好的选择。本文在已有的研究基础上，对蚂蚁算法进行进一步了解 和探究，经过理论推导和仿真，分析了已有算法的缺点，并在改进这些算法的 基础上提出新的解决方法。 ：尘童三兰查兰三兰至圭兰竺耋耋 1 4 本文结构 本文的第2 章介绍了路由技术的相关知识，并介绍了已有的路由算法及其 特点；第3 章介绍了蚂蚁算法的相关知识，并以t s p 问题解决算法为例，介绍 了蚂蚁算法应用的一般步骤；第4 章先介绍目前国际上基于蚂蚁算法的路由算 法的研究现状，并对其中的主流算法作了简单介绍，然后分析了这些算法的不 足，并在这些算法的基础上作了改进，提出改进后的路由算法；第5 章介绍了 利用s u a l c + + 对所提的改进后的路由算法进行仿真；最后给出了本文的结 论。 哈尔滨工业太学工学硕士学位论文 第2 章路由技术 路由是指这样一组动作，选择一条从源站到目的站的路径，然后通过这条 路径传送分组，路由设备( 路由器) 通过物理连接连到局域网( l a n ) 或广域网 ( w a n ) j ：来提供网络之间的连接。路由包括两个基本的动作：确定最佳路径和 转发分组。 路径确定，是基于在所有到达目的站的有效路径中确定最佳路由的各种准 则。用软件方法来实现路由算法，为每一条有效( 己知) 路径计算出适当的权值 以确定到达目的站的最佳路由。路由算法创建并维护路由表，表中含有路由信 息，以帮助确定路径。路由信息根据所使用的路由算法不同而不同。路径确定 可能会是一个复杂的处理过程。路径确定功能可能含有一个或多个路由协议。 这些协议实现路由器之问路由信息的交换以及提供路由器将这些信息转换成为 路由表所遵循的处理过程( 算法) 。 分组转发，大体上说，在检查分组的目的协议地址时，路由器确定如和将 分组转发到下一跳。在路由器不知道怎样转发该分组的情况下，该分组通常会 被丢弃。而在前一种情况下，路由器把该分组的物理地址改为下一跳的物理地 址，再把该分组发送到下一跳。下一跳可能是最终的目的地主机，也可能不 是；如果不是，这个节点通常也是一个路由器，执行相同的转发策略。分组在 网间传输时，它的物理地址会改变而协议地址却保持不变。分组转发相对来说 是比较简明直接的。 转发功能包含有一组处理过程( 算法) ，这些处理过程被路由器用来对一个 分组作出转发决策。这组算法对分组的信息进行定义，路由器通过它们查找对 应的路由( 转发) 表的待定项来确定下一步如何转发 5 1 。 2 1 静态路由和动态路由 现代路由理论基本上划分为以下两种路由策略：静态和动态路由f 4 】f 关于它 们详细对比见表2 - 1 1 。 静态路由：需要网络管理者判断并手工配置到达目的网络的路由，并由此 创建一张静态路由表。一旦配置完毕，网络路径就不会自动改变。路由器将 直使用预先确定的路由，不管该路由器是否发生故障( 路径中的一个链路或者 另外一个路由器失效) ，因为它不具有自动再配置路由表来为失效链路中的通 竺查童三兰垄兰三兰堡圭兰竺竺耋 信分组重定向路径( 如果存在的话) 的机制。在那种情况下，所有的分组都会被 发送到一个网络黑洞里去。除非失效的链路被路由器( 如：一个直接附加的链 路) 探测出来，这样分组不会被路由器发送到原来的静态路由上去。当网络中 只存在唯一的一条路径而没有别的替代路径时，使用静态路由策略比较合适。 在那种情形下，动态路由不会带来任何附加效果，反而会因为路由更新和周期 性的计算动态路由表而增加相应网络和附加路由器的负担。 表2 - 1 静态路由和动态路由的对比 特征静态路由动态路由 对互联网变化的自动反应没有是 配置对管理者的依赖高低 可用路径的监视 高低 路由信息交换没有需要 路由器处理能力的影响低高 内存消耗低中等到高 网络路由开销没有 中等( 常规操作) 到高( 突发性) 动态路由；与静态路由相反，当网络拓扑结构的改变被探知时，将自动 更新路由表和重新计算最佳路径。路由器和相关的路由器相互交换有关网络拓 扑变换的信息。起始时路由器只能观察到网络中非常有限的范围，因为它只能 从网络管理员那里得到和它直接相连的网段有关信息。剩余的部分留给路由协 议：一个关于路由信息交换、更新周期、路由表的建立和修改、最佳路由的选 择，和当这条路由失效时用条存在的( 次最佳) 备用路由来取代它的机制。动 态路由可以适应互联网络条件的改变( 链路的建立和释放、新的链路和路由器 的加入) 而不需要管理人员的干预( 假设互联网中路由器的协议配置是正确的) 。 2 0 世纪7 0 年代的路由理论认识到，当网络主干的负载适中时动态路由策 略可以提高吞吐量，然而当负荷不均匀的时候，主干重负载时吞吐量会降低。 所以主要的问题是决定应该何时和隔多长时间周期交换路由信息，因为这里引 起了一个冲突：间隔周期应该是足够短，路由策略才是基于最新状态信息做出 的；然而，间隔周期应该足够长以使由于信息更新的开销最小化。 ( 1 ) 链路和系统故障静态和动态路由策略的最大不同是他们对于故障的反 应。 动态路由允许对相关路由中的链路和路由器进行故障检查，如丢失呼叫、 生存期消息，或者纯粹是路由更新消息丢失，然后寻找另外一条路由。 静态路由，由于它并不需要路由器之间进行信息交换，也不具有解决路由 丢失问题的机制，甚至在很多情况下连对链路或系统故障的检查能力都没有。 竺查童三兰查兰三耋罂圭兰竺竺圭 如主机x ( 见图2 - 1 ) 要向主机y 发送分组，这些分组将首先到达路由器a 。在 a 的路由表中已经配置了一条经由路由器b 到达子网1 0 的静态路由。当连接 a 与b 只见的网段发生故障时，这个点到点的链路故障使得那条静态路由失 效。在这种情况下将要产生黑洞，即分组会被发送到一个不可检测的死端：a 所转发的分组j f 会被b 所接收，而这意味着没有路由器会发出“目的不可到 达”的i c m p 报文，因此分组将被意外地丢失了。 子网1 0 图2 - 1 系统和链路故障 ( 2 ) 收敛收敛是指所有的路由器达成关于网络拓扑结构( 实际上是最佳路 由) 的一致性的协商过程。当一个网络事故造成路由停止运作或者失效时，路 由器将发布路由更新信息。路由更新信息向全网散布，引起最佳路由的重新计 算，最终使得所有的路由器都接受这条信息路由。收敛缓慢的路由算法会引起 路由环路或网络停机。 对于所有路由器共享的网络拓扑结构的一致解析是路由协议的一个主要基 准。路由器或者链路状态的改变会引起收敛损耗，而这又会带来网络失效时 间。当网络拓扑结构发生变化时，在实现收敛时可能需要重新配置路由表。因 此在其他路由器由于错误的信息而将分组误传到死端之前，路由器必须很快的 完成收敛过程。 决定协议收敛的因素有：网络规模；跳跃计数的极限值；网络的对等体部 署( 边缘、核心) ；拓扑结构的设计；路由状态信息的兼容性：端口和交换器的 寻址；路径选择。 ( 3 ) 多播路由路由理论同样研究了具有多目的站而非单目的站的情形。起 先这个问题叫做多目的站路由( m d r ) ，现在叫做多播路由。现代多播技术的应 甩包括视频会议、企业通信、远程教学、分布式软件、股票行情和新闻行业。 多播与单擂路由有一个内在的区别是：通用路由规则，即对每个分组进行 独立路由。在一个组里发布大量相同的分组是需要对独立路由的分组进行大量 哈尔滨工业大学工学硕士学位论文 的复制。显然，这会给网络和路由器带来不必要的处理负荷。 相反，对予要发送到一组站点( 多播地址) 中去的相应分组，多播路由只发 送一个它的复制体。通过每一条网络链路到达目的站，在更显著的情况下，仅 仅通过这样一条链路，就可以多播到路由器或终端站点上，这些路由器或终端 站点是特定的被寻址的组成员。多播通信是基于组的概念的。任意地接收组只 希望接收相应的数据流。这些组没有物理上或地理上的边界，主机可以放在可 路由网络的任何地方。 图2 - 2 和图2 - 3 提供了在一个典型的多播技术应用中( 如视频会议) ，单播 和多播路由的对比。 多播技术是一种可以节约带宽的技术。通过同时将一个信息流传送到数以 千计的企业和冢庭而降低了网络业务量。多播技术使用最少的网络带宽，将源 主机业务流分组传送给多个接收主机而不会给源主机或目的主机带来任何的额 外负担。 图2 - 2 单播路由示意图 竺查耋三兰态兰三竺罂圭耋竺竺耋 一 图2 - 3 多播路由示意图 2 2 被路由协议、可路由协议和路由协议 被路由协议是指那些能在互联网上路由器确定路由的协议，一般是网络协 议。这类协议的例子有网际协议f i p ) 、a p p l e t a l k 的d d p 、n e t w a r e 的i p x 、 o s i 的c l n p 或是b a n y a nv i n e s 和施乐网络系统( x n s ) 的v i p 。被路由协议就 是指可路由协议，即它们都实现了网络层和网络寻址这两个实现路由的先决条 件1 0 1 。 可以通过静态或动态的方法为网络协议进行路由。动态路由是基于那些实 现路由算法的路由协议。简单的说，路由协议帮助路由器在互联网上为被路由 协议确定路由。路由协议不是真正的为被路由协议确定路由；他们主要是实现 路由更新信息的发布和路由表的收敛。路由器根据路由表为被路由协议确定路 由，而不断地对路由表进行更新的工作则由路由协议来完成。 路由协议的例子包括路由信息协议( p i p ) 、优先开放最短路径协议 ( o s p f ) 、外部网关协议( e g p ) 、边界网关协议( b g p ) 、o s l 路由协议和中间系统 到中间系统的路由选择协议( i s i s ) 。 因此，一个被路由网络就是一个使用路由器作为互连设备的互联网。另 兰篓耋三兰垄兰三兰矍圭耋：鎏耋 外，它也不能对自己路由。因为它不是一个路由网络。相反，它的业务分组的 路由是在作为互连设备的路由器和静态动态路由进程的支持下被确定的。 2 3 动态路由 动态路由基于路由协议以支持路由协议的路由用户数据，也提供一个路径 判定功能。无论是对于网际协议( i p ) 或网间分组交换协议( r e x ) ，每个路由协议 的主要特征都是用来交换路由信息、建立和维持路由表的基本路由算法阱l 。 如前面所述，路由协议的一个特征就是衡量每一条可能的( 可选择的) 到达 目的网络的路由质量的方法。这样的一个或组准则通常就叫做度量。 度量是测量的一个标准，例如路径长度，它被路由算法用来判定到达目的 地的最佳路径( 路由器比较度量制来确定最佳路由) 。为了帮助路径判定，应使 用路由算法对路由表进行初始化和维护，路由表中应含有包括路径度量在内的 路由信息。当时使用的路由算法不同时，路由信息和度量也会各异。 路由算法曾使过很多不同的度量来判定最佳路由。复杂路由算法将多个度 量合并为一个( 混合的) 度量来选择路由。以下都是被使用过的度量： ( 1 ) 路径长度( 跳跃计数) 。协议使用的最老的度量，它由到达目的地的路 由上的跳( 路由器) 数来表示。 ( 2 ) 延迟。将分组通过互联网从源机发送到目的机所需要的时间长度。延 迟取决于中间网络链路，链路上各个路由器的端口队列，以及所有中间链路上 的网络拥塞。( 在一种简单的情况下，延迟是由于网络拓扑结构没有监视网络 运行而静态的引起的) 。依据延迟度量确定的最佳路由意味着累积的路径延迟 最短。 ( 3 ) 带宽。链路的有效通信容量，也就是链路能达到的最大吞吐量，相当 于相应路由的最小带宽。路径依据它们的最小吞吐量( “最薄链路”) 进行比 较，整个路径的最小吞吐量的值就是最佳路由。 ( 4 ) 负载。到达目的地的路由上的网络资源的繁忙程度( 链路吞吐量和路由 器c p u 的利用率) 。负载需要通过连续的网络监控来度量。依据负载度量确定 的最佳路由意味着路径上的负载最低。 ( 5 ) 稳定性。通常用组成路由的各个链路的误码率表示，且受到连续的监 控。依据这种度量确定的最佳路由拥有最高的稳定性。 ( 6 ) 代价。分配给每一个网段( 路由器的接口) 的一个任意值( 但通常来自其 它“固定”的准则，如带宽) 。依据这个度量确定的最佳路由意味着路径上遍 竺尘耋三兰奎兰三兰丝圭兰竺耋圭一，。；。， 历的每一个链路的开销综合最小。 上述这些度量都各有优缺点。有些度量可以轻易由网络拓扑结构和物理结 构得到，这类度量用于路由协议而不需要额外的开销。有些度量反映了( 类似 于1 网络的瞬时状态，像负载，需要额外的可靠监视资源。目前的“黄金中间 法”可以选取像延迟、带宽或代价这些反映状态值的度量。在当今混合了多种 媒介的大型互联网上跳跃计数度量和需要某些监控任务的度量并没有得到广泛 的应用。然而，一些协议不是使用单一准则而是一个复合的准则。这样的结果 是得到了一个更合适的度量，但是也带来了更高的计算开销和更多需要交换的 路由信息。 2 4 路由算法 为了帮助路径判定，应使用路由算法对路由表进行初始化和维护，路由表 中应含有路由信息。路由信息根据所使用的路由算法不同而各异。路由算法将 各种路由信息写入路由表中。例如表2 - 2 中所示的目的站下一跳之间的关联表 告诉路由器，将分组发送到一个特定的路由器可以通过这个表找到一条到相应 目的站的最佳路由，这个路由器代表了到达最终站点的路由上的“下一跳”。 表2 - 2 目的站下一条关联路由表 到达网络的网络号下一跳发送到的节点号 2 7 节点a 5 4 节点b 3 4 节点c 1 3 节点b 2 5 节点a 路由器接收到一个输入的分组时，要对分组的目的地址进行检查并试图将 这个地址和下一跳联系起来。下一跳可能是最终目的主机，或者是另外一个路 由器。该路由器执行相同的路径并确定进程。 路由表也可以含有其他的信息，比如关于路径期望值的数据。路由器比较 各个度量以决定最佳路由，这些度量因为所使用的路由算法的设计不同而有所 差别。 路由器和另外一个路由器之间相互通信，通过传输各种消息来建立和维持 它们各自的路由表。路由更新消息就是一种这样的消息。它通常组成了路由表 的全部或一部分。通过分析所有路由器的路由更新消息，一个路由器可以建立 ：尘釜三兰奎耋三兰塑圭兰竺耋塞 起一个详细的网络拓扑结构图。链路状态通告消息是路由器之间传输消息的另 外一个例子。它将发送端的链路状态报告给其他路由器。链路信息同样可以用 来建立完整的拓扑结构图以帮助路由器决定最佳路由。 一些路由算法将f 1 的站i 下一跳关联表填写到路由表中( 见表2 2 ) 。关联表 告诉路由器，通过将分组发送到一个标识为“下一跳”的节点可以找到一条到 相应目的站( 通常是一个相应的网络或予网，但也可以是一组网络或站点) 的最 佳路由。其他些路由算法则提供目的站下一跳度量关联表。它告诉路由器 每一个特定的目的站都表示成某个相应的度量( 有时叫做距离) 。路由器比较各 个度量值以决定最佳路由。所使用的路由算法不同，所使用的度量也会不同。 其它路由算法同时也提供目的站路径关联表。这个表将目的站和到达该 目的站的路径联系起来。路由器只是简单地沿着这条路径转发分组直到到达目 的站。以上这些都是路由器之间交换路径信息的方法。当拥有了其它路由器的 路径信息，路由器就可以决定最佳路径了。路由更新信息可以在常规情况下发 送，也可以在路由拓扑结构的变化影响到路由路径时发送，或者两种情况下同 时发送。 路由算法可以根据几个关键的特征来区别。首先，算法设计者的特定目标 会影响到所使用的路由协议的操作。其次，存在着各种类型的路由算法。每一 个路由算法对网络和路由器资源产生的影响都是不同的。最后，路由算法使用 了各种不同的度量，这些度量会影响到最佳路由的计算【5 1 。 2 4 1 路由算法的设计目标 路由算法通常拥有以下的一个或多个设计目标f 5 1 。 ( 1 ) 最佳性为了选择“最佳”路由，也就是说它必须使用合适的准则来评 价每一条可能到达目的网络的路由的质量( 用来计算的度量准则和度量加权) 。 ( 2 ) 简明性开销低，需求带宽最小，对路由器的处理和存储资源的影响 最小。 ( 3 ) 适应性健壮性和稳定性，在通常或者不可预知的环境下也能很好的 运行，例如硬件故障、高负载条件，甚至不正确的操作；快速和准确地适应各 种网络环境的能力。 ( 4 ) 快速收敛所有的路由器根据快速传播的最新而正确的路由信息，在 最佳路由以及路由表的重新生成和计算上达成一致的快速过程( 收敛缓慢的路 由算法会导致路由环路) 。 窒尘兰三兰苎兰三兰璺：兰竺耋圭。，。 ( 5 ) 路由环路的避免通过设置使得路由信息只发送给相关的路由器，同 时不能引起对网络环境的错误理解。 2 4 2 路由算法的类型 现在有两种主流算法，它们都用于事实标准和法定标准的路由协议里例： ( 1 ) 距离向量，用于r i p ( i p 、i p x 和x n s ) 、i g r p ( 用于i p 的非标准c i s c o 系统 协议) 、r t p ( b a n y a nv i n e s ) 和r t m p ( a p p l e t a l k ) 等协议；( 2 ) 链路状态，用于 o s p f ( w ) 和i s - i s ( o s i ) 协议。 ( 1 ) 距离向量算法。距离向量算法要求路由器维持一个描述它与目的网络 之间的路由的简单路由表。这个路由表将路由度量和转发路径( 由路由器的输 出接口以及或相邻节点的输入接口的地址来决定) 联系起来。这种算法的原理 是将一个路由器所知的一切信息通知给所有和它直接相连的相邻节点，然后根 据最佳度量确定路径。对距离向量法的一个更深层次的观察见图2 4 。 图2 - 4 距离向量操作 在距离向量路由协议里，每一个节点将它所知道的所有目的站的信息通知 给( 通常使用广播的方式) 和它直接相连的各个相邻节点。目标可达性信息可使 用两种形式来通知，一种为距离，指到达某个特定目的站的开销；另一种为向 量，指分组到达该目的站所依据的方向。 路由器在开始( 启动时) 只有管理员提供的信息，也就是关于和它直接相连 的网段的信息。因此最初的路由表只是反映了外界( 只有最少的关于连接链路 的度量) 有限的信息。一旦路由协议开始工作，这个新的路由器的最初的路由 信息就会被广播给它的相邻节点。同时相邻节点广播的路由信息也会被该路由 器接收。这个路由器将收到的路由信息和它的路由表进行对比并进行相应的更 新；将最新了解到的路由信息添加到路由表中( 将从相邻节点接收到的度量值 加上它到相邻2 声点的距离，或者将跳数加一) ；忽略具有相同或更差度量值的 路由。这个过程要不断地处理所有接收到的路由信息。 兰尘童三兰苎兰三耋堡圭兰竺丝耋 。，。一 距离向量协议的特征有：实现简单而且在互联网历史上得到了很好的证 实；度量简单( 通常是具有某种限制的路径长度准则) ；对路由信息( 路由表) 采 用广播方式，这会造成带宽的浪费；很容易受路由环路的影响；在大型网络拓 扑中收敛得很慢。 ( 2 1 链路状态算法。路由器通过泛洪法( f l o o d i n g ) 将链路状态信息在网络中 扩散出去以了解互联网络的拓扑结构。链路状态数据只包含了那些直接连接到 每个路由器的网络的开销和标识信息。路由器将链路状态数据发送给一个局域 网内的所有路由器，这些路由器使用这些数据建立起一个完整的描述路由器和 网络连接的表。因此，建立拓扑数据库首先要收集链路状态信息。这个算法使 用复制的分布式数据库。 此时路由器有了一个完整的网络拓扑结构概貌。它可以利用这些信息来运 行最短路径优先( s p f ) 算法以建立一棵树，这棵树的根就是该本地路由器，它 的分枝则映射了所有可达的网络( 节点是其他各个路由器的抽象) 。s p f 算法计 算出网络的可达性并决定到达每个可达网络的最短路径。然后路由器根据树所 提供的信息将所有的最佳( 最短) 路径都列入它的路由表中。 运行链路状态路由协议的路由器只将它们本地的信息( 关于直接连接到它 们上面的链路状态) 通告给网络中所有的路由器( 以多播的形式) 。更新信息是不 断增加的，且潜在地周期性刷新，这些信息在网络中通过泛洪方式扩散出去。 链路状态协议有以下特征：当发生改变时立即将链路状态信息扩散出去以 保证快速收敛；没有或很少周期更新发送：通过对路由信息进行多播实现了低 路由开销( 但在路由的探索过程中互联网会有很大的负载) ；路由器c p u 的资 源占用( s p f 算法循环) 和内存需求( 数据库) 很紧张；适合于实现基于规则的路 由，安全性、支持类型服务( t o s ) 和服务质量( q o s ) 功能；防止形成路由环路： 路由器到路由器的认证。 o ) 距离向量和链路状态路由算法之间的比较。这两种算法之间的比较总 结于表2 3 。 表2 - 3 距离向量和链路状态算法的比较 距离向量链路状态 传向谁邻居所有路由器 什么时候周期性改变后立即 如何传通过广播通过多播 基于什么信息 ( 几乎完全) 路由表有关改变的连接链路信息 变化范围 与网络内被路由的网络地址( 聚类)与拓扑的改变成比例 数据成比例 ：尘耋三兰垄兰三兰塑圭耋竺耋圭 2 5 本章小结 本章主要介绍了路由技术的基本概念，描述了静态路由和动态路由的区别 和优缺点；说明了路由算法的设计目标，描述了两种主流路由算法，并比较了 两种主流路由算法的优缺点。 窒查童三兰奎兰三兰罂圭兰竺丝圭。，。；。一 第3 章蚂蚁算法 3 1 蚂蚁觅食的生态现象 蚂蚁算法( a n tc o l o n ya l g o r i t h m ) 是人们对自然界中真实的蚂蚁群集体行为 进行研究受到启发而提出的一种基于种群的模拟进化算法，这一行为指的就是 蚁群搜索食物的过程。因此。这里首先介绍一下蚂蚁的觅食方式【2 。 蚂蚁作为生态系统中重要的组分之一，它的取食行为与生态系统有着密切 的关系，觅食方式主要有三种：简单合作觅食、小组觅食和集体觅食。 ( 1 ) 简单合作觅食。简单合作觅食是单个工蚁独自完成觅食过程的觅食方 式。箭蚁属c a t a g l y p h s i s 的c b i c o l o r 的觅食行为属于此种觅食方式。c b i c o l o r 生活在干旱地区，每一觅食工蚁都有自己固有的觅食路线。晴天，他们靠太阳 和其他可见线索来定位运动方向。一般以此方式猎取小块猎物。但在发现一些 大块猎物时，他们几乎没法和同巢蚂蚁取得联系。美国沙漠中盘腹蚁 a p h a e n o g a s t e r 蚂蚁也是单独觅食，但能通过释放一种化学激素而与l m 以内的 同伴保持联系。 ( 2 ) 小组觅食。小组觅食是当某一觅食者发现食物后，做好标志，然后返 回巢并带领一小组蚂蚁搬回所发现的食物。弓背蚁属的c a m p o n o t u ss o c i u s 主 要用这种觅食方式觅食。当一只工蚁发现食物时，它在食物周围释放一种分泌 物做标记，然后回巢并一路释放一种分泌物作为示踪标记。在巢内，它做“摇 摆表演”来召集同伴。随后，同巢部分工蚁在它的带领下沿着分泌物的气味找 到食物源。一般情况下，一只工蚁能召集5 3 0 个同伴。但是，当首先发现食 物的工蚁中途消失后，其同伴只能沿着示踪气味继续前进1 0 m 左右，因而通 常很难找到所标记的食物。 ( 3 ) 集体觅食。集体觅食是当某一头工蚁发现食物后回巢告知同伴，大批 的工蚁将一起涌向食物。火蚁属的s o l e n o p s i si n v i c t a 和小家蚁属的 m o n o m o r i c u mp h a r a o n i s 就采用这种觅食方式。当一只工蚁发现食物后，释放 出一种挥发性激素作为示踪标记，然后回巢告知同伴，它在巢内来回迅速跑动 并用前腿和触角轻拍同伴，当同伴得到消息后，成百上千的工蚁涌向食物直至 食物被取食完为止。 ( 4 ) 其它觅食方式。有些种类的蚂蚁自己不去觅食，而靠抢劫其他蚂蚁的 塞当釜三兰查兰三兰丝圭兰竺耋耋。；。，；。一 食物，或者偷食其它种类蚂蚁的卵和幼虫，或者寄生在其它种类的巢内，有的 甚至役使其它种类的工蚁替它觅食。 蚂蚁算法就是模拟上述觅食方式中的第三种，即集体觅食方式。为了与真 实蚁群相区别，我们称蚂蚁算法中的蚁群为人工蚁群。下面一节将介绍它们之 间的联系与区别。 3 2 人工蚁群与真实蚁群的联系 蚂蚁算法中绝大多数的观点来源于真实的蚂蚁。因此它们都包括以下几 项：( 1 ) 一个个体间能相互协作的群体，( 2 ) 进行当前信息交流的( 人- r ) 信息索 迹，( 3 ) 为找到最短路径纪录的当前移动队列，以及( 4 ) 利用当前信息而没有未 来信息的随机选择策略例。 ( 1 ) 一个个体间能相互协作的群体。作为真实的蚁群，蚂蚁算法是利用一 个种群( 或群体) 找到所考虑问题的最优解，这个种群可以同步也可以非同步的 全局协作。虽然每个人工蚂蚁都可以找到一个可行解( 1 i p 任何一个真实蚂蚁都 可以找到一条从蚁巢到食物源的路径) ，但是只有依靠整个蚁群中个体间的相 互协作才能找到最优解。 2 ) 进行当前信息交流的( 人工) 信息素迹。人工蚂蚁与真实蚂蚁都改变了 他们所处环境的一些方面。真实蚂蚁在他们经过的路径上留下了一种化学物