（计算机应用技术专业论文）基于核心路由器的蚂蚁算法研究与应用.pdf

摘要 随着i n t e r n c t 日益广泛的应用，其规模也越来越大，通信流量也迅速增 长，这就迫使其传输平台向更高的通信带宽方向发展。因此，建设高速度，高 宽带的骨干网就显得十分必要。 合理高效的路由选择方式不仅可以保障全网的正常运行，还能够提高网 络的接通率，而将i n t e r n c t 网的接通率提高，既可以尽量避免交换机不堪重负 甚至崩溃的情况，又能降低网络的运营成本。提高网络的接通率相当大的程 度上依赖于路由选择策略的改变。因此，t c p i p 网的动态路由选择问题变得 越来越重要。蚂蚁算法能够有效地选择一条最优路径，但忽视了实际网络中 的另外一个问题：最优路径一旦形成，所有的数据都从最优路径传输，这样 一来，处于该路径上的路由器，尤其是在骨干网络中心节点( 即多条路径交 汇处) 的路由器将承受巨大的数据传输量，因而很容易造成“瓶颈”现象。 目前采用的一个办法是在骨干网络中心节点处设置交换容量达到或超过干兆 比特级的。具有高密度高速端口的核心路由器来扩展带宽和提高数据传送速度 以达到解决骨干网络中心节点处的数据拥塞的目的。但这样大大提高了网络 成本，并且无法解决最优路径上非核心路由器( 又名接入路由器) 上的数据 拥塞问题。 根据上述问题，本文提出一种对蚂蚁算法的改进方法一基于核心路由器 的蚂蚁算法：在骨干网络的各核心路由器上相互发送蚂蚁寻找各核心路由器 之间的最优路径，这样可比传统蚂蚁算法通过让“蚂蚁”周游整个网络后来 寻找最优路径要快很多。另一方面，该算法通过对最优路径上，在各个核心 路由器之间的非核心路由器设置上下限两个阈值。当某个非核心路由器a 上 的数据流量达到上限阈值时表明该路由器即将处于拥塞。这时，它邻近的核 心路由器将a 看成是一个“障碍物”，利用蚂蚁算法能够绕过障碍物寻找最优 路径的特点，可以在这两个核心路由器之间重新寻找一条不包括路由器a 在 内的“次优”路径。这样后续的数据将从“次优”路径传输以达到对a 路由 器进行分流。经过一段时间分流后，当数据流量下降到下限阈值时，就可以 重新启动原最优路径，从而达到了既分流又采用最优路径传输的目的。 关键词：t o p i p ；路由：蚂蚁算法；服务质量 a b s t r a c t w i t ht h ew i d e l ya p p l i c a t i o ni ni n t e r n e t ，i t ss c a l eh a sb e c o m el a r g e ra n dl a r g e r , a n di t sf l o wi n c r e a s e dq u i c k l yt o o ，i ti sf o r c e dt od e v e l o pi t st r a n s m i s s i o nt oh i g h b a n d w i d t h s ot h ec o n s t r u c t i o no fn e t w o r kw i t hh i g hs p e e da n dw i d eb a n d w i d t h b e c o m e se s s e n t i a l t h er e a s o n a b i l i t ya n dh i g he f f i c i e n c yi nr o u t i n gc a nn o to n l yg u a r a n t e e st h en e t w o r k sw e l l ，b u ta l s oc a ni n c r e a s et h er a t eo fc o n n e c t i o n i nt h i sw a y ，i tc a na v o i d c o l l a p s i n gb e c a u s eo fu n b e a r a b l eh e a v yb u r d e ni ns w i c h e sb u ta l s oc a nd e c r e a s et h e c o s to ft h en e t w o r k i n c r e a s i n gt h er a t eo fc o n n e c t i o ni nn e t w o r kl a r g e l yd e p e n do n t h em e t h o d so fr o u t i n g t h e r e f o r e ，t h ed y n a m i cr o u t i n gm e t h o di nt c p i pn e t w o r k i sb e c o m i n gm o r ea n dm o r ei m p o r t a n t t h ea n ta l g o r i t h mc a nc h o o s eas u p e r i o rp a t h a v a i l a b l y ，b u ta n o t h e rp r o b l e mt h a tn e g l e c t e di na c t u a ln e t w o r ki st h a t ，o n c et h e s u p e r i o rp a t hi sf o r m e d ，a l ld a t e sw i l lb ed e l i v e r e df r o mt h i sp a t h ，i nt h i sc a s e ，t h e r o u t e ro nt h i sp a t h ，e s p e c i a l l yt h er o u t e ri nc e n t e rn o d eo ft h en e t w o r k ( s e v e r a lp a t h s h a n d so v e rl or e m i tap l a c e ) w i l lb e a rt h ee n o r m o u sd a t ad e l i v e r i n g a sar e s u l t ，t h e ”b o t t l e - n e c k ”p h e n o m e n o nf o r m e de a s i l y c u r r e n t l y ，am e t h o dt os o l v et h i sp r o b l e m i st oe s t a b l i s h e sac o r er o u t e ri nc e n t e rn o d eo ft h en e t w o r k ，w h i c hh a st h e c o m m u t a t i o nc a p a c i t ya t t a i n so ro v e rt h o u s a n dm b i t sa n dh a ss u p e r s p e e d p o r t w h i l ei ti sl a r g e ri n c r e a s i n gt h en e t w o r kc o s t s ，a n dc a n tr e s o l v et h ed a t aj a mo fn o n c o r er o u t e ri ns u p e r i o rp a t h i nt h i sc a s e ，t h i sp a p e rp r e s e n t sa ni m p r o v e m e n ta n ta l g o r i t h mw h i c hb a s e do nt h e c o r er o u t e r s ：o ne a c hc o r er o u t e r ，s e n d i n ga n t st ol o o kf o rt h es u p e r i o rp a t hm u t u a l l y b e t w e e ne a c ho t h e r ，i tw i l lb em u c hq u i c k e rt h a nt h et r a d i t i o n a la n ta l g o r i t h mw h i c h i sl o o k i n gf o rt h es u p e r i o rp a t hb yp a s st h ew h o l en e t w o r k o nt h eo t h e rh a n d ，i nt h e s u p e r i o rp a t h ，t h ea l g o r i t h ms ct w ov a l u e so nn o n - c o r er o u t e r st oa v o i dj a mo fd a t a w h e nt h en o n - c o r er o u t e rai sb e c o m i n gj a m ，t h en e a rc o r e r o u t e rt r e a taa sa ” s t u m b l i n gb l o c k ”，s o i tw i l lc h o o s ea n o t h e rs e c o n ds u p e r i o rp a t hw h i c hi sn o t i n c l u d i n ga ，i nt h i sw a y ，t h ed a t ai ss h a r eb yt h es e c o n ds u p e r i o rp a t h w h e nt h e v a l u er e d u c e d ，i tw i l lc h o o s et h ef i r s ts u p e r i o rp a t ha g a i n a sar e s u l t ，t h i sa l g o r i t h m c a nn o to n l yf i n dt h es u p e r i o rp a t h ，b u ta l s oa v o i dj a mo ff l o w k e y w o r d s ：t c p i p ；r o u t i n g ；a n ta l g o r i t h m ；q o s 、l i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：豫志向日期：少年夕月爿日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1 、保密口，在 一年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 蔚、志向 叶研 日期：如辟 ，月纠日 日期：文叼睁歹月，阳 第一章绪论 1 1 问题的提出 当今时代，i n t e r n e t 已经成为人们生活中不可缺少的一部份，它提供给人们 巨大的功能和方便，借助于i n t e r n c t ，人们可以通过计算机将数据很方便地发送 到千里之外的地方，目前i n t e r n e t 上进行数据传输所用的协议有很多，而t c p i p 协议是使用最广泛的协议。如果我们用协议对网络进行分类，那么我们可以把基 础协议是t c p i p 的网络归为单独一类一t c p i p 网，i n t e r n e t 就是一种t c p i p 网。现在的i n t e r n e t 网规模非常庞大，庞大到谁也无法精确知道某一时刻全世 界究竟有多少台计算机在网上。而计算机输入输出速度以及信息传输速度已经达 到若干千兆位每秒。在网上传输的不仅有字符、文字，而且还有声音、图像、动 画、电视等多媒体信息，在这种情况下，i n t e r n e t 的路由选择就面临许多新的挑 战。例如视频点播要求数据吞吐达到某一个传输速率，而语音传输则要求时延不 能超过某一个值。现在的i n t e r n e t ，一个会话的不同数据包可能通过不同路径到 达目的节点；同一网络资源，如缓冲及带宽，可能被不同会话所分享。所以，网 络的路由选择既要满足用户不同应用的要求，又要能尽量提高网络整体资源的利 用率。由于网络特别庞大，拓扑结构及流量不断动态变化，所以显得特别杂乱。 所以，网络的路由选择是一个既重要又困难的任务。将i n t e r n e t 网的接通率提 高，既可尽量避免交换机不堪重负甚至崩溃的情况，又能降低网络的成本。提高 网络的接通率相当程度依赖于路由选择策略的改变【”。所以，研究网络的路由和 提高网络服务质量问题变得越来越重要，对它的研究，既有重要的经济效益，又 有深刻的理论价值。 1 2 国内外研究状况 蚂蚁算法( a n ta l g o r i t h m ) 是由意大利科学家m a r c od o r i g 在2 0 世纪9 0 年代 初提出来的。它是继模拟退火算法、遗传算法、禁忌搜索( t a b us e a r c h ) 算法、人 工神经网络算法等以后，出现的又一种应用于组合优化问题的启发式搜索算法。 蚂蚁算法是一种仿生类算法，它吸收了生物世界中蚂蚁群的行为特征，用蚂蚁这 种昆虫在搜索食物源的过程中所体现出来的路径寻优能力来解决一些优化问题。 尽管一些思想尚处于萌芽时期，但人们己隐隐约约认识到，人类诞生于大自然， 这种由欧洲学者提出并加以改进的新颖系统思想，正在受到越来越多人的注意和 研究，应用范围也开始遍及许多领域。该方法求解旅行商问题、指派问题、调度 问题，取得了一系列较好的实验结果。 从当前可以查阅的文献【2 巧】情况来看，研究和应用蚂蚁算法的学者主要集中 在比利时、意大利、英国、法国、德国等欧洲国家，日本和美国在这一两年内也 开始启动对蚂蚁算法的研究。国内于1 9 9 8 年末才开始有少量公开报道和研究成 果，而且基本局限于t s p 问题上。但在近两年出现了许多利用蚂蚁算法求解各 种问题的文章。求解的问题有组播路由、度限制树、二次规划、生产调度、组合 优化等等。在文献【6 l 中是采用的是遗传算法求解q o s 组播路由问题的，此问题 也属于一种最优化问题。利用遗传算法解最优化问题一般采用如下方法：首先应 对可行域中的点进行编码( 一般采用二进制编码) ，然后在可行域中随机挑选一些 编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编 码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作 为繁殖过程前的编码样本。选择机制应保证适应度较高的解并且能够保留较多的 样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程 中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交 换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某 一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁 殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传 算法解最优化问题所得到的最终结果。可以看出遗传算法使用的是群体搜索技 术，是通过对当前群体旅加选择、交叉、变异等一系列遗传操作，从而产生出新 一代群体，并逐渐使群体进化到包含或接近最优解的状态，即在产生一个新解时 只能参考其上一代的解，而不能利用原来产生的所有的解集信息，这样就容易导 致局部最优解。在文献【7 】和文献【8 】中都采用的是蚂蚁算法分别求解的a t m 网上 的v c 路由问题和话网路由问题，在以上三个问题中，原算法都只是对静态网络 进行路由的选择，都没有对动态网进行分析、求解，即没有考虑网络的扩展性。 但在网络日益扩大的今天，对动态网络进行优化路由己经成为人们应该认真考虑 的问题了。 总之，蚂蚁算法还是一种新型的模拟进化算法，其研究刚刚开始，虽然蚂蚁 算法思想在启发式方法范畴内逐步成为一个独立分支，在有关国际会议上多次作 为专题加以讨论。但远未像g a ，s a 等算法那样形成系统的分析方法和坚实的数 学基础，有许多问题有待进一步研究，如算法的收敛性、理论依据等。但可以想 象，随着研究的深入，蚂蚁算法也将同其它模拟进化算法一样，获得越来越多的 应用。 1 3t c p i p 网络简介 t c p i p 是一种网络通信协议，它规范了网络上的所有通信设备，尤其是一 个主机与另一个主机之间的数据往来格式以及传送方式。t c p f l p 又是一种电脑 数据打包和寻址的标准方法。在数据传送中，可以形象地理解为有两个信封， t c p 和i p 就像是信封，要传递的信息被划分成若干段，每一段塞入一个t c p 信封，并在该信封面上记录有分段号的信息，再将t c p 信封塞入i p 大信封， 发送上网。在接受端，一个t c p 软件包收集信封，抽出数据，按发送前的顺序 还原，并加以校验，但t c p i p 网络并不能保证数据传输的高安全性和服务质 量，它所能保证的只是尽力投递。 随着交互式实时多媒体业务及i p 电话的出现，为了提高网络效率，降低网络 成本，提高用户的满意度和网络运营商的收益，必须提高网络的服务质量。而q o s 路由( q u a l i t y o fs e r v i c e r o u t i n g ) $ , l j 是保证服务质量的关键技术q o s 路由的 主要目标是为接入的业务选择满足其服务质量要求的传输路径，同时保证网络资 源的有效利用。一般路由选择过程由两个部分组成：一是为到达业务选择路径并 发送数据包，即寻路过程；二是节点问路由信息的交互过程q o s 的选择对q o s 路 由的实现起到决定性作用。 1 4 路由选择 路由选择是网络最复杂同时也是最重要的功能。路由选择的概念实际上可追 溯到2 0 世纪5 0 年代，当时计算技术仍是一门处于研究阶段，极少有组织拥有 一台单独的计算机，更不用说连在一起的多台计算机了。网络互联更多的仍是关 于未来的幻想而非现实，这一幻想预测到了那一天的到来：计算机将被广泛使用 并通过一个无所不在的全球互联网络- - i n t e r n e t 来进行互联。 建立并使用全球互联网的挑战正在改进发现、访问并与远程主机通信的手 段。表面上，全球互联网会提供冗余；换句话说，穿过某一网络、在任意给定的 一对主机之间会有许多不同的物理路径。需要这样一种机制，它能够发现远程的 网络和主机并通过网络探测到达那些网络和主机的不同的可能路由。 最后，需 要应用数学的方法。逻辑上讲，如果存在许多不同的到达某个特定目的的路径， 它们不可能完全相同。某些路由可能会比其它路由提供总距离较短或者性能较好 的路径。因此，比较所有可能的路由然后选择最好的一条或几条路由是符合逻辑 的。这些机制就被称为路由器。发现、计算并比较到达远程网络和主机的过程即 是路由选择。 1 4 1 路由选择的方式 路由器能以两种基本方式进行路由选择。它们可以使用预先设置好的静态路 由，或使用一种动态路由选择协议来动态地计算路由。路由器使用动态路由选择 协议来发现路由，然后机械地把分组( 或数据报) 转发到那些路由上。 静态设置的路由器不能发现路由，它们缺乏与其他路由器交换路由选择信息 的机制。静态设置的路由器只能使用由网络管理员定义好的路由来转发分组。除 了静态规划路由，有三种广义上的动态路由选择协议1 9 j ： 距离矢量路由选择 链路状态路由选择 混合路由选择 静态路由选择协议在网络出现问题或其他原因引起拓扑变化时，不能发现其 他路由并利用它。需要网络管理员手工调整这些变化。与静态路由选择协议相 比，在任何具有冗余路由的互联网中使用距离矢量路由选择协议更好。这是因为 距离矢量路由选择协议能自动检测到网络中的失效并更正它。但是，距离矢量路 由选择协议在会聚过程中，网络面对不协调一致的路由选择会很脆弱，甚至会无 限地循环下去。而且会聚的过程很慢，不适合大型、复杂的w a n 网。 如果使用了链路状态路由选择协议，距离矢量路由选择的危险就可以避免。 根据实际使用的协议和选择的度量，路由选择协议很可能识别所有的可行路径， 并试图应用最好的一个。一些链路状态协议甚至可以对这些路由进行性能上的估 价，然后倾向于性能最好的一个。如果那条性能最好的路径，正处于某一类运行 上的困难之中( 包括会聚或组件失效) ，链路状态路由选择协议将检测出这个变 化，并转向另一个较好的路径。 1 4 2 路由选择的目的和要求 在通信子网中，网络节点在收到一个分组后，要确定传输的路径，并向下一 个节点转发。路由选择的目的和要求有以下几点： ( 1 ) 能正确、迅速、合理地传送报文信息。 ( 2 ) 能适应网络内节点或链路故障而引起的拓扑变化，使报文在故障条件下 一般能到达终点。在发生故障时，允许某些线路的通信量过载而增加时延。 ( 3 ) 能适应网络流量的变化，使各条通路的流量均匀，整个网络的通信设备 负荷平衡，充分发挥效率。 ( 4 ) 算法尽量简单，以减少网络开销。 1 5 路由协议 根据是否在一个自治域内部使用，动态路由协议分为内部网关协议( i g p ) 和 外部网关协议( e g p ) 。这里的自治域是指一个具有统一管理机构、统一路由策略 的网络。自治域内部采用的路由选择协议称为内部网关协议，常用的有r i p 、 o s p f ：外部网关协议主要用于多个自治域之间的路由选择，常用的是b g p 。下 面分别进行简要介绍。 1 5 1 路由信息协议( r i p ) r i p 协议最初是为x e r o x 网络系统的通用协议而设计，是i n t c r n e t 中常用 的路由协议。r i p 采用距离向量算法，即：路由器根据距离选择路由，所以也 称为距离向量协议。路由器收集所有可到达目的地的不同路径，并且保存有关到 达每个目的地的最少站点数的路径信息，除到达目的地的最佳路径外，任何其它 信息均予以丢弃。同时路由器也把所收集的路由信息用r i p 协议通知相邻的其 它路由器。这样，正确的路由信息逐渐扩散到了全网。 r i p 使用非常广泛，它简单、可靠，便于配置，但是r i p 只适用于小型的 同构网络，因为它允许的最大站点数为1 5 ，任何超过1 5 个站点的目的地均被 标记为不可达，而且r i p 每隔3 0s 一次的路由信息广播也是造成网络的广播 风暴的重要原因之一。 1 5 2 开放式最短路径优先协议( o s p f ) 8 0 年代中期，r i p 已不能适应大规模异构网络的互连，o s p f 随之产生。 它是由网间工程任务组织0 e a f ) 的内部网关协议工作组为l p 网络而开发的一种 路由协议。o s p f 是一种基于链路状态的路由协议，需要每个路由器向其同一管 理域的所有其它路由器发送链路状态广播信息。在o s p f 的链路状态广播中包 括所有接口信息、所有的量度和一些其它变量。利用o s p f 的路由器首先必须 收集有关的链路状态信息，并根据一定的算法计算出到每个节点的最短路径。而 基于距离向量的路由协议仅向其邻接路由器发送有关路由更新信息。与r i p 不 同，o s p f 将一个自治域再划分为区，相应的有两种类型的路由选择方式：当源 和目的地在同一区时，采用区内路由选择；当源和目的地在不同区时，则采用区 间路由选择。这就大大减少了网络开销，并增加了网络的稳定性。在一个区域内 的路由器出了故障时并不影响自治域内其它区域路由器的正常工作，这也给网络 的管理、维护带来了方便。 1 5 3 外部网关协议( b g p l b g p 是为t c p i p 互联网设计的外部网关协议，用于多个自治域之间。它 既不是基于纯粹的链路状态算法，也不是基于纯粹的距离向量算法。它的主要功 能是与其它自治域的b g p 交换网络可达信息。各个自治域可以运行不同的内部 网关协议。b g p 更新信息包括网络号，自治域路径的成对信息。自治域路径包括 到达某个特定网络必须经过的自治域串，这些更新信息通过t c p 传送出去，以 保证传输的可靠性。 1 6q o s 路由 q o s 路由是指根据网络上可利用的资源和流( f l o w ) 的q o s 需求决定流的路由 机制。路由有两方面的基本内容：收集网络状态信息并不断更新信息根据已有信 息来为新的连接请求选择一条合适的路由。它是对各流的包基于q o s 要求选择 可用路径的过程。它面向连接，带资源预留，以满足各流的连接要求，减少呼叫阻 塞。因此，它着重在满足约束，希望连接的数据传输不受其它连接的动态流量的影 响。基于q o s 路由的约束包括链路约束、路径约束、树约束、时延约束等【”。 由于网络永远是动态的，节点对全局网络q o s 状态的了解不精确、不实时，对路由 的确定与预计就未见得完全正确。q o s 路由的代价主要包括两方面：一方面是计 算开销，另一方面则是协议开销。因为前者需要更加复杂和频繁的路由计算，后者 要分布式地提供和刷新与路由选择有关的网络资源状态信息。各种刷新方案各有 优劣。刷新越及时，路由需要的网络状态信息就越精确，但刷新太频繁，增加网络负 担。要在两个极端中折衷。q o s 路由按通信方式分，可以分为单播路由( 即端到端 的路由) 、多播路由( 即端到目的节点集中的每一个节点的路由) 及a n y c a s t 路由 ( 即端到目的节点集中的任一个节点的路由) 1 0 l 。其中，单播路由和多播路由是密 切相关的。在很多情况下，多播路由可以作为单播路由的推广。 随着多媒体的急剧发展，网络带宽资源短缺情况已经越来越明显，特别是网 络很难同时满足大数据量传输和实时要求，这就要求网络系统能够更加合理地利 用有限的网络带宽资源，尽量满足客户应用的各种需求。针对这个问题提出了服 务质量( o o s ，q u a l i t yo fs e r v i c e ) 。 1 6 1q o s 路由网络模型 q o s 路由选择问题可以描述为一个无向赋权图g = ( v ，e ) ，其中：图的顶点 表示网络节点，图的边表示网络链路，v 为网络中所有交换节点集，e 为网络 链路集( 对于有向图可以通过变换解决) 。e vx v 表示网络中单点投递情况 下( 源节点，目的节点) 的集合。q o s 路由选择即为在无向赋权图中，为特定的 e 找出代价( c o s t ) 最小，同时满足单点投递服务q o s 要求的路由 n - i s 】。 1 6 2q o s 路由度量参数的选择标准及基本性质 目前i p 网络的路由协议，如o s p f 、r i p ，仅基于一个路由度量参数，如 路由跳数、链路代价等，计算最短路由路径。实际的网络业务通常会对网络的多 个q o s 指标提出要求，这就需要同时考虑对多个路由度量参数的优化。q o s 选路过程需要根据度量参数给出的网络状态和业务对网络q o s 质量要求，在某 种优化目标之下得到一个满足用户要求的最优的或至少是可用的传输路径，因此 找到合适的描述网络路由代价的路由度量参数是基于q o s 保证的的核心问题之 一a 网络应用产生的业务流通常对网络传输提出多样的q o s 质量保证要求。 q o s 路由的选择方法应能根据业务提出的要求进行路径选择，一条传输路径的 度量参数由组成该路径的各传输链路的状态决定，网络各链路的度量参数取值是 对网络状态的表达，它们很大程度上决定了路由策略可以支持的q o s 服务要 求。因此选择合理的度量参数是进行q o s 路由设计的第一步，而选择度量参数 时通常应考虑一些主要因素： 对于选取的度量参数，应该存在能以有限复杂度实现的路由算法，这样得到 的才可以适应像i n t e r n e t 这样的大规模网络。该度量参数应该能够有效地反映 网络的基本链路特征，所携带的信息应该足以支持目前业务需要的基本的o o s 质量要求。由于网络业务提出的任何q o s 要求都会最终映射为度量参数对路由 算法提出的约束条件，所以度量参数在一定程度上决定了网络可以支持q o s 要 求，例如不将传输延迟作为参数的很难提供对实时业务的延迟保证。 选择的度量参数应该是尽可能相互独立的，以避免多个参数间存在冗余信 息。在多个参数相互关联的情况下将难以对每个度量参数的性质进行独立的讨 论，同时对冗余信息的多次迭代评价将加大路由算法的复杂度。选择的度量参数 应该在整个网络中有合理一致的编码表示，特别对于跨越多个自治域的网络系 统，只有当各链路的q o s 度量参数得到一致的定义时才可以有意义地合成全路 径度量参数。基于以上的选择要求，度量参数通常选用链路可用传输带宽、链路 传输延时( 通常指链路固有的物理传输延时) 、传输成功( 失败) 率、路径跳数等。 基于各种度量的性质不同，这些度量参数有多种合成形式，即加性参数、乘性参 数与凹性参数( 最小性参数) 。传输延时和跳数是常见的加性参数，其合成规律为 整个传输路径的度量参数值即各个组成链路的度量参数值之和，如式( 2 1 ) 所 示。式中m ( 1 i ) 是链路l i 上的度量参数取值，m ( p ) 是由从l i 到l n 的n 条链路组成 的传输路径的总度量参数值。 三 r e ( p ) = 1m ( 1 i )( 2 - 1 ) 镐 传输成功率是常用的乘性参数，其合成规律为各链路度量参数值之积，如式( 2 2 ) 所示。 r e ( p ) = n m ( 1 i ) ( 2 2 ) 可用带宽、路由器缓冲区剩余容量等则是常用的凹性参数，其合成规律为路 径的度量参数值为各链路度量参数中最小的，如式( 2 3 ) 所示。 m ( p ) = m i n m ( 1 i ) 】 ( 2 - 3 ) 也有一些度量参数不能直接归结为以上3 类，如丢包率也即传输差错率，其合 成规律较为复杂，在式( 2 4 ) 中给出，m ( p ) 和m o o 分别为全路径和链路i i 的传输 失败率。 m ( p ) = 1 一 1 - n m ( 1 i ) 】 ( 2 _ 4 ) 由于丢包率的合成规律复杂使其不易与其它度量参数同时使用，于是我们将其表 示为式( 2 5 ) 。 l g 【1 - m ( p ) 】= l g ( 丌m ( 1 i ) 一罗l g ( 1 - m ( 1 i ) ) ( 2 5 ) a 对于度量参数进行如上的分类有利于从理论上对度量参数性质的分析，同时 为多个参数组合为单混合参数提供了指导标准。 1 6 3q o s 度量参数的常用选择方法 按照业务对度量参数的约束要求，可以把基于度量参数的选择问题分为：参 数受限和参数最优两种类型。参数受限是指业务某度量参数必须达到某个数值要 求，如链路延时不得大于1 0 0m s 等；参数最优是指业务并不对度量参数提出某 种最小、最大数值要求，而是期望得到目前网络能够提供的一条基于某度量的最 好性能的路径，如要求该路径具有最大带宽或最小延时等。 多个度量参数的选择问题可以分为如下四个基本类型：凹性参数受限、凹性 参数最优、路径参数受限、路径参数最优( 对于加性和乘性度量参数，路径总的 度量数为各组成链路参数的和或积，因此统称为路径参数、。大部分的q o s 度 量参数选择考虑2 个度量参数选择路径。对于路径参数选路问题，文献【1 4 i 中 已经证明，对任意m 个加性度量参数和n 个乘性度量参数，当m + n 2 时 求解最优路由的选路算法是n p c o m p l e t e 的。因此度量参数的选择应在满足业 务q o s 要求和所需的复杂度间采取一些折衷，使得到的q o s 路由方法有足够 的扩展性能以应用于大规模网络。 n ) 单混合度量参数 基于单个度量参数的路由算法已经广泛应用，在常用的o s p f 、r i p 等路由 协议中使用延时或网络带宽的倒数值等作为一个单一的链路代价，并利用d i j k s t r a 或b e l l m a n f o r d 算法进行最短路径寻路，表现出了很好的性能。 单混合参数可以定义为多个q o s 度量参数的函数。例如，根据式( 2 6 ) 的 函数计算得到的参数值正比于可用带宽b ( p ) ，反比于延时d ( p ) 和丢失率 l ( p ) 、成本c o s t ( p ) 。一条具有较大的m ( p ) 的路径通常表现出更好的q o s 性 质，如具有较大的带宽和较低的延时和丢失率及成本。 m ( p ) ：些型一 ( 2 6 ) d ( p ) l ( p ) c o s t ( p ) 、 这样一个简单的单混合参数显然具有很低的运算复杂度。具有算法简单，可在现 有的基础方便地实现等优点。另一个主要优点在于它可以利用得到的单混合度量 参数值作为链路代价而对现有的某一最短选路协议( 如o s p f ) 进行改进得到新 q o s 路由协议。 但) 多度量参数 多度量的选路问题是根据业务的q o s 选路请求对多个度量参数的取值提出 独立的要求。多个度量参数对选路的同时约束，可以明显改进单一度量参数或单 混合度量参数对路由q o s 状态描述不充分的缺陷，为网络业务提供更为严格的 q o s 保证。因为多个加性与乘性度量参数的最优问题是n p c o m p l e t e 的，所以 多度量参数选择中避免同时优化2 个或2 个以上加性乘性度量参数，而利用链 路可以用带宽w 的凹性性质，结合另一加性或乘性度量参数构成多度量参数问 题，常可以取得多项式运算复杂度的寻路算法的一个特别的要求就是需要在满足 用户需要的情况下，尽可能降低算法复杂度。过于复杂的虽然可以更精细地满足 各种q o s 需求，但是其过大的路由开销使其无法用于大规模网络。当链路可用 带宽与另外的度量参数联合构成多度量参数约束问题时，为了保证选路算法的简 单可行性，采用参数受限的选路算法通常不试图求解一个多约束的全局最优选路 问题而是使用合适的启发式算法简化寻路过程，这样得到的q o s 路径通常不是 全局最优的，但是能够在可以承受的算法复杂度下找到满足业务o o s 要求的路 由。 ( 3 ) 度量参数的离散量化 对于单度量或多度量参数问题，为了减小路由协议的开销，同时由于度量参 数在网络中发布必然引入信息的老化，通常不需要直接将度量参数的精确数值向 网络各节点发布。将带宽、延时等连续取值的度量参数值进行合理的量化，利用 离散的量化数值进行选路计算，可以降低选路算法复杂度和协议开销，节省路由 器的存储空间，还可以避免过于精细的参数取值的波动引起网络路由不必要的过 于频繁的摆动。在多度量参数问题中，量化的方法甚至使算法复杂度大为降低。 例如，对2 个加性度量参数的双约束问题中的一个度量参数进行离散量化后可 以利用改进的d i j k s t r a 或b f 算法在多项式级时间内找到满足约束的路径。量 化参数选路的另一益处在于增加了选路算法取得等价路径的概率，有利于引入负 载均衡等机制进一步改善网络服务质量。但离散量化的代价是使得一些在原有连 续参数约束条件下存在的可行路径可能不满足约束参数量化之后的网络。 q o s 路由度量参数选择一方面需要考虑满足q o s 请求业务，同时由于的 可扩展性要求，参数选择时如何降低算法的复杂度成为需要考虑的另一重要因 素。 1 7 本文结构及创新点 1 7 1 本文结构 本文主要的介绍了以下四个方面： ( 1 ) 分析了当前i n t e r n e t 上应用晟广泛的t c p i p 传输方式、原理和优缺点， 并针对i n t e r n e t 上要求越来越高的服务质量所必需q o s 及其它路由算法作了简 要介绍。 ( 2 ) 介绍了路由器技术及其功能，分析路由的原理，介绍了开放式最短路径 优先协议、q o s 路由及其网络模型，分析了q o s 路由度量参数的选择标准及基 本性质并介绍了理想路由算法的特点以及重点介绍了当前常用路由算法的优缺 点。 ( 3 ) 在介绍了蚂蚁算法的基本原理、蚂蚁算法参数选取的基本理论、蚂蚁算 法的研究近况及蚂蚁算法的优缺点后，针对蚂蚁算法存在计算时间长、易陷入局 部最优的缺陷，提出了一种改进算法一基于核心路由器的蚂蚁算法。 ( 4 ) 针对常用的路由算法只能有效的计算某个路由参数最小的路由，不能计 算出对多个路由参数进行限制的q o s 路由的缺点，在本文提出的基于核心路由 器的蚂蚁算法中进行相关研究，将该算法设计成一种对时延、带宽、丢包率及时 延抖动进行限制，并保证费用最小的q o s 路由算法。 1 7 2 本文创新点 针对当前i n t e r n e t 新业务发展迫切需要保证网络服务质量q o s 的状况，本 文通过分析了当前所使用的路由算法以及蚂蚁算法的优缺点后提出了一种基于核 心路由器的蚂蚁算法来改进基本蚂蚁算法的不足，其主要创新点如下： ( 1 ) 针对基本蚂蚁算法在大型网络中收敛速度慢，搜索时间较长缺点，在基 于核心路由器的蚂蚁算法中提出先将网络以核心路由器为中心逻辑上划分成若干 个子网，然后从各核心路由器出发，同时向临近的核心路由器发送“蚂蚁”寻找 最优路径来减小算法搜索的范围，并且由于该算法具有并行寻路的功能，所以比 基本蚂蚁算法的收敛速度快，算法复杂性小。 ( 2 ) 该算法另一个创新之处在于能够预防最优路径上的数据拥塞。 由于蚂蚁算法是一种正反馈算法，当运用该算法在网络中找到了一条最优路 径后，使得这条最优路径上的信息素浓度比其他路径上的要高很多，因此后续的 数据一般都会将选择这条最优路径进行传输，这样就很容易造成该路径上的数据 流量突增，对于那些非核心路由器很难承受这样大流量的数据传送，从而很容易 造成“瓶颈”。基于核心路由器的蚂蚁算法通过设置上下两个阈值来监控通过最 优路径数据流量，能够根据最优路径上各路由器通过的数据流量来判断该路由器 是否将出现数据拥塞，如果有拥塞迹象( 当测得的流量大于路由器设置的上限阈 值) 时，会动态地在该路由器临近的核心路由器上重新选择一条“次优”路径来 对该路由器分流；经过一段时间以后，随着数据流量的下降，原来处于拥塞状态 的路由器逐步恢复正常。当处于正常状态( 即测量该路由器上数据流量值小于先 前设定的下限阈值) 时，就可以恢复原来的最优路径。这样一来既可以保证所选 择的路径在当前状态下是最优的，又能够有效地预防和避免拥塞。 第二章路由器技术及路由算法 2 1 路由器技术及功能介绍 2 1 1 路由器技术简介 路由器技术的发展经历了几个阶段，早先的路由器由软件集中进行i p 包的转 发，吞吐量比较低；例如思科的2 5 0 0 、3 6 0 0 等中低端路由器，其转发能力约为几 十k b p s 。第二代路由器是基于软件的分布式转发，每个接1 ：3 板上都有c p u ，主控 板生成的路由表被下发到各接口板形成转发表，每块接口板根据转发表独立进行 转发工作；例如思科的7 5 0 0 系列路由器，转发能力超过1 m b p s 。第三代路由器基 于硬件进行i p 包的转发，转发引擎可以是a s i c ( 专用集成电路) ，也可以是专门为 i p 转发而设计的网络处理器。 2 1 2 路由器的功能 路由器是一种典型的网络层设备，用于连接多个逻辑上分开的网络，从事不 同网络之间数据的存储转发功能。它可以根据不同的帧来传输数据，完成网络层 中继任务。它掩盖了下层网络的细节，使各类网络都在i p 层上达到统一。路由 器的主要任务就是接收来自网络接口的数据包，根据其中所含的目的地址，寻找 一条最佳传输路径，并将该数据包有效地传送到目的站点。为了完成这项工作， 在路由器中保存着各种传输路径的相关数据一路由表( r o u t i n gt a b l e ) ，路由选择 时，要按照某种路由协议查找路由表。路由表中列出网络中包含的各个节点，以 及节点间的路径情况和与它们相联系的传输费用。如果到特定的节点有一条以上 路径，则应基于预先确定的准则选择最优( 对于不同数据服务需求有不同的含义) 的路径。由于各种网络段和其相互连接情况可能发生变化，因此路由情况的信息 需要及时更新。按照所使用的路由协议的规定，路由表应定时更新或者按变化情 况更新，以便保持有效的路由信息。此外，路由表还可以由系统管理员固定配 置。 路由器通常实现下列基本功能： 将i p 数据包封装到链路层帧或从链路层帧中取出i p 数据包； 将i p 地址与相应网络的链路层地址相互转换： 按照路由表信息，为每个i p 数据包选择下一跳目的地； 按照该网络所支持的最大数据包大小发送或接收i p 数据报； 必要时将数据包分段； 实现网络支持的流量控制和差错指示； 在收发数据包过程中实现缓冲区管理、拥塞控制以及公平性处理； 出现差错时辨认差错并产生i c m p 报文及必要的差错消息： 支持至少一种内部网关协议，与同一自治系统中的其它路由器交换路由信息及 可达性信息；支持外部网关协议，与其他自治系统交换网络拓扑信息： 提供网络管理和系统支持机制，包括配置、诊断、升级、状态报告、异常情况 报告等。 2 1 3 核心路由器介绍 核心路由器是指在l p 骨干网络中心使用的，交换容量达到或超过千兆比特级 的，具有高密度高速端口的路由器产品。该类产品的可扩展性、高速接口、互操 作性、q o s 能力、高可靠性，为骨干网提供了良好的升级、服务质量和故障恢复 能力，并且为网络向下一代基于i p 的高速骨干网发展奠定了良好的基础。未来l p 骨干网的三个关键组成部分是光纤、d w d m ( 密集波分多路复用) 和核心路由 器。目前的光网络层运行在o c 一4 8 和o c 1 9 2 速率，传统路由器无法提供相应的 接口速率和端口密度，不能有效利用巨大的原始带宽，造成了骨干网的潜在瓶颈。 核心路由器是未来骨干网的关键节点，采用核心路由器能够把大量的原带宽转换 成可用带宽，解决骨干网瓶颈问题。 2 2 路由器工作原理 2 2 1 路由器工作原理 当i p 子网中的一台主机发送i p 分组给同一i p 子网的另一台主机时，它 将直接把i p 分组送到网络