（计算机应用技术专业论文）融合蚁群优化算法与遗传算法的qos路由选择研究.pdf

融合蚁群优化算法与遗传算法的o o s 路由选择研究 摘要 保证服务质量的q o s 路由( q u a l i t yo f s e r v i c er o u t i n g ) 是网络中 解决q o s 问题的一项关键技术。q o s 路由的主要目标是为接入的业 务选择满足服务质量要求的传输路径，同时保证整个网络资源的有效 利用。受多个q o s 约束的路由问题是n p 完全问题。目前已经有许多 方案将蚁群算法和遗传算法分别用来解决o o s 路由问题，但是如何将 两者融合在一起用于解决o o s 路由问题是一个崭新的课题。 本文提出了一种将蚁群优化算法与遗传算法融合的新算法。采用 蚁群优化算法进行寻径生成初始群体，利用遗传算法对路径进行优 化。仿真结果表明此算法是可行的、有效的。 关键词：蚁群优化；遗传算法；o o s 路由；单播路由 r e s e a r c ho fu s i n gt h ec o m b i n a t i o no fa n t c o l o n yo p t i m i z a t i o n a n dg e n e t i ca l g o r i t h mt os o l v eq o s r o u t i n gs e l e c t i o n a b s t r a c t q o sr o u t i n gi so n eo ft h ek e yt e c h n o l o g i e st op r o v i d eq u a l i t yo fs e r v i c ei n f u t u r en e t w o r k s t h eg o a l so fq o sr o u t i n ga r et os e l e c tf e a s i b l ep a t h st h a tm e e tq o s c o n s t r a i n t sa n dt om a k ee f f i c i e n tu t i l i z a t i o no ft h en e t w o r kr e s o u r c e t h er o u t i n g p r o b l e mw i t hm u l t i c o n s t r a i n ti sn p - c o m p l e t e n o wt h e r ea r em a n ym e t h o d sh a v e a p p l i e da n tc o l o n ya l g o r i t h ma n dg e n e t i ca l g o r i t h mr e s p e c t i v e l yo nt h eq o sm u t i n g p r o b l e m b u ti ti san e wt a s kt h a tr e s e a r c h i n gh o wt om i n g l et h et w oa l g o r i t h m st o s o l v et h ep r o b l e m i nt h i sp a p e r , t h ea l g o r i t h mi sb a s e do nt h ec o m b i n a t i o no fa n tc o l o n y o p t i m i z a t i o na l g o r i t h ma n d g e n e t i c a l g o r i t h m f i r s t ，i ta d o p t sa n tc o l o n y o p t i m i z a t i o na l g o r i t h mt og e tan e wp o p u l a t i o nb yr o u t i n g ，s e c o n d ，i tm a k e su s eo f t h eg e n e t i ca l g o r i t h mt oo p t i m i z et h ep a t h a f t e rs i m u l a t i o n ，r e s u l ts h o wt h a tt h e a l g o r i t h m i sf e a s i b l ea n de f f e c t i c e k e yw o r d s ： a n tc o l o n yo p t i m i z a t i o n ； g e n e t i ca l g o r i t h m ； q o sr o u t i n g ； u n i c a s tr o u t i n g i l 缩略语表 a sa n ts y s t e m 蚂蚁系统 a c s a n tc o l o n ys y s t e m )蚁群系统 a c oa n tc o l o n yo p t i m i z a t i o n 蚁群优化 a c o g aa n tc o l o n yo p t i m i z a t i o ng e n e t i ca l g o r i t h m 蚁群优化算法与遗传算法 a sa u t o n o m o u ss y s t e m 自治系统 b g pb o r d e rg a t e w a yp r o t o c o l 边界网关协议 d i f f s e r vd i f f e r e n t i a t e ds e r v i c e区分服务 g a g e n e t i ca l g o d t h m遗传算法 i pi n t e m e tp r o t o c o l 因特网协议 i e t fi u t e m e te n g i n e e r i n gt a s kf o r e因特网工程研究组 i u t s e r v i n t e g r a t e ds e r v i c e集成服务 m m a sm a x m i na n ts y s t e m最大最小蚂蚁系统 m p l sm u l t i - p r o t o c o ll a b e ls w i t c h i n g多协议标记交换 m f cm i c r o s o f tf o u n d a t i o nc l a s s微软基础类 n p c n o n d e t e r m i n i s t i cp o l y n i m i a lc o m p l e t en p 完全 p h b p e r - h o p b e h a v i o r每跳行为 q o sq u a l i t yo fs e r v i c e服务质量 q o s rq u a l i t yo fs e r v i c er o u t i n g服务质量路由 r s v pr e s o u r c er e s e r v a t i o np r o t o c o l 资源预留协议 r i p r o u t i n g i n f o r m a t i o n p r o t o c o l路由信息协议 s g a s i m p l eg e n e t i ca l g o r i t h m s基本遗传算法 t s p t r a v e l i n gs a l e s m a np r o b l e m旅行商问题 南京邮电学院学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：垃日期：堕型 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电学院研究生部办理。 躲避名：蝉吼d 南京邮电学院硕士学位论文 刖舌 随着i n t e m e t 的迅猛发展，多媒体应用的种类和数量的增加，网上电子商务活 动的开展，对服务质量( q u a l i t yo fs e r v i c e ，简称q 0 s ) 提出了更高的要求：当前 的i n t e m e t ( i p v 4 标准) 只提供“尽力而为( b e s t e f f o r t ) ”服务，不能保证服务质量， 如何满足q o s 的需求，已成为i n t e m e t 相关技术的研究热点。 q o s 是网络在传输业务流时，业务流对网络服务的需求的集合，其中业务流是指 与特定q o s 相关的从源到目的地的分组流。也就是说o o s 是应用业务对网络传输服 务提出的一组可度量的要求，主要包括带宽、端到端延迟、分组丢失率、抖动、花费 等网络在传输相应的数据业务时，必须满足这组要求。i e t e 已经提出了多种服务模 型和机制来满足各种q o s 的需求，其中比较典型的有以下几种：集成服务资源预留 协议( i n t e r s e r v r s v p ) 模型、区分服务( d i f f e r e n t i a t e ds e r v i c e s ) 、多协议标 签交换协议( m p l s ，m u l t i - p r o t o c o ll a b e ls w i t c h i n g ) 、流量工程( t r a f f i c e n g i n e e r i n g ) 和o o s 路由( q o sr o u t i n g ) 目前许多有关支持q o s 的研究主要着眼 于调度、拥塞控制和资源预留，而研究q o s 路由的较少。1 。因此有关此领域的工作 比较新颖。 服务质量路由( o o sr o u t i n g ) 是一种动态路由协议，并且在其路径选择标准里可 能包含可用带宽、链路和端到端路径利用率、资源消费量、延迟、跳数咀及抖动等 o o s 参数。1 。当前i n t e r n e t 的主要路由协议包括域内路由协议o s p f 、r i p 和域间路由 协议b g p 等。都是“尽力发送”的路由协议，选择路由时通常只基于单一度量( m e t r i c ) 优化，因此通常所有的业务都是基于“最短路径”，难以满足多样的q o s 需求，即便 源到目的节点之间存在“更好的”路径，只要不是最短路径就不会投入使用，因此可 能导致某些链路空闲时另外一些链路的拥塞。o o s 路由就是将传统的最短路径变为一 条更好的路径。1 。 实时应用往往会对延时，延时抖动，带宽，丢失率，业务代价等多个参数同时提出 性能要求。例如，实时多媒体业务会对延时和延时抖动同时提出要求。这些参数相 互独立时，选择满足多个参数限制的路由就成为n p 完全问题“1 。近年来，国内外许 多学者利用神经网络“帅”、蚁群算法。“、遗传算法”矧等智能算法来解决n p 完全问 南京邮电学院硕士学位论文 题，并且取得了一定的成果；各算法都有各自的优缺点，如何实现优势互补，得到更 好的效果，不少学者进行了深入的研究并且取得了较好的效果汹掣。目前已经有许 多国内外学者提出方案用蚂蚁算法和遗传算法分别用来解决q o s 路由问题”“”， 但是如何将两者融合在一起，实现两种算法的优势互补用于解决o o s 路由问题是一 个崭新的课题。 本论文主要研究将蚁群优化算法与遗传算法进行融合来解决q o s 单播路由问题 基本思想是汲取两种算法的优点，克服各自的缺点，优势互补；算法先运用i 岫i a s 陆删 改进传统蚁群算法的寻径行为，实现对搜索空间的高效、快速的全面寻优，然后用遗 传算法对蚂蚁算法得到的有效路由路径，通过选择、交叉、变异等优化过程，产生性 能更优的下一代群体，以防止过早收敛于非全局最优解以及计算时间过长，不断重 复，直到满足相应的条件。本论文以文献 3 3 中的q o s 单播路由选择实例为例；对 本论文提出的用蚁群优化算法与遗传算法进行融合后的新算法，进行了计算机仿真 实验，并与基本遗传算法、a c s 算法等已有算法的仿真实验结果进行比较分析。 本论文算法的原理大致如下： 首先为了提高算法的效率，对q o s 单播路由问题进行了两点简化： ( a ) 在算法迭代中不考虑抖动而是在之前进行处理；因为抖动可通过目的节点 的缓冲进行平滑，故为简化问题，只考虑目的节点的抖动汹1 。 ( b ) 对于带宽限制，之前先对网络拓扑进行过滤，通过删除带宽小于需求带宽 的链路，把网络滤成一个新的简单网络。 本算法进：f ? q o s 单播路由的步骤如下： ( 1 ) o h 果目的节点的抖动不满足q o s 路由需求，则退出，路由选择失败：否则进入 ( 2 ) 。 ( 2 ) 遍历拓扑图中的所有链路如果某链路不满足q o s 路由需求，则去除该链路， 从而产生过滤后的新拓扑图。转( 3 ) ( 3 ) 初始化网络中各链路上的信息素强度以及蚂蚁的控制参数，迭代次数，遗传算 法的交叉、变异概率等。转( 4 ) ( 4 ) 将m 只蚂蚁置于源结点，根据蚁群算法的寻径规则，每只蚂蚁选择转移的下一 结点：每只蚂蚁遍历结束后，都找到一条路径。对满足q o s 的路径，对其链路上的信 南京邮电学院硕士学位论文 息素进行局部更新。转( 5 ) ( 5 ) 保留最优的一条路径，然后利用赌轮选择法从其余的路径集中，遗传形成新的 一代群体( 路径集) 。转( 6 ) ( 6 ) 按一定的交叉概率先对新的群体进行配对，然后用双点交叉法对路径进行交 叉操作，形成新的群体( 路径集) 。转( 7 ) ( 7 ) 对第( 6 ) 步形成的群体( 路径集) ，按一定的变异概率，采用基本位变异法对群 体( 路径集) 进行变异操作。转( 8 ) ( 8 ) 对群体( 路径集) 用遗传算法优化后；先对所有链路上的信息素进行更新，然 后对全局最优路径上的信息素进行更新加强。如果迭代的次数没有超过规定的迭代 次数，则转( 4 ) ，否则转( 9 ) ( 9 ) 输出最优解。 本文提出的算法对蚁群算法与遗传算法进行了融合，结合文献 3 3 3 中的实例， 通过计算机模拟仿真，并与基本遗传算法、a c s 算法等已有算法的仿真实验结果进行 比较可以看出，经过较少的迭代就可以找到全局最优路径，由此可见，本文提出的 融合后的算法具有较好的收敛性和自适应性。 本文共五章。第一章0 0 s 、q o s 路由及q o s 单播路由的基本原理；第二章介绍了蚁 群优化算法的基本原理；第三章介绍了遗传算法的基本原理；第四章介绍了本文提 出的对蚁群优化算法与遗传算法进行了融合的算法的原理及设计：第五章介绍了对 实例的仿真实现及结果分析：最后展望了将来进一步的研究工作。 南京邮电学院硕士学位论文 第一章q o s 原理 当前i n t e r n e t 只提供尽力发送( b e s t e f f o r t ) 服务，网络层不区分用户业务的种 类，而将网络资源公平地提供给各类业务，在分组丢失、延迟等方面公平地对待各类 业务。这种尽力发送的机制使网络层无法保证传输的质量，然而丢失奉、带宽、端到 端延迟、延迟抖动等对于应用业务往往是至关重要的。例如，文件传输业务要求分组 的丢失率尽可能低，而传输延迟不是关键因素：实时多媒体业务则更看重延迟和抖动 这就要求网络能够区别对待各种业务，并对它们提供不同的服务质量( o u a l i t yo f s e r v i c e ，简称q o s ) 由于i p 是无连接的协议，不要求像a t m 网络那样在数据传输 前从源到目标节点建立连接这种尽力发送的体系结构是无连接、与状态无关的，它 既不能支持资源预留，也不能预测传输参数，甚至还可能产生多媒体实时业务不希望 的乱序等。由此，面向服务质量的网络体系结构应运而生，如何满足q o s 的需求，已 成为i n t e m e t 相关技术的研究热点“”。 1 1i pq o s 问题删0 1 q o s 是应用业务对网络传输服务所提出的一组可度量的要求，主要包括带宽、 端到端延迟、分组丢失率、抖动、花费的代价等：网络传输相应的数据业务时，必 须满足这组要求。i e t f 已经提出了多种服务模型和机制来满足各种q o s 的需求，其 中比较典型的有以下几种： 1 1 1 集成服务模型( i n t s e r v r s v p ) 为了满足i n t e r n e t 多媒体应用实时传输的需求，i e t f 定义了i n t s e r v 模型在服 务定义层次上，i n t s e r v 提供端到端的质量保证型服务( g u a r a n t e e ds e r v i c e ) 或可控 负载型服务( c o n t r o l l e d l o a ds e r v i c e ) ，典型的应用如远程教学、视频点播等交 换式音频和视频应用：在实现层次上，现有的i n t s e r v 方案需要所有路由器在控制路 径上处理每个流的信令消息并维护每个流的路径状态和预约状态，在数据路径上执 行基于流的分类、调度和缓冲区管理具体而言，i n t s e r v 通过资源预留协议r s v p 为单 个实时应用流提供服务。在应用传送数据前须先通过r s v p 信令协议建立路径和预留 资源。 南京邮电学院硕士学位论文 i n t s e r v 尽管提供q o s 保证但其扩展性差，因为其扩展性差。因为其工作方式是 基于每个流的，这就需要保存大量的与分组队列数成正比的状态信息。此步f r s v p 的 有效实施必须依赖于分组所经过路径上的每个路由器。在骨干网上，业务流的数目 可能很大，因此要求路由器的转发速率很高，这使得i n t s e r v 难以在骨干网上得到实 施。 1 1 2 区分服务模型( d i f f s e r v ) 为了解决i n t s e r v 的一些缺点，i e t f 提出了d i f f s e r v 体系结构，d i f f s e r v 的目标 在于简单有效，以满足实际应用对可扩展性的要求，实现的途径是： ( 1 ) 简化网络内部节点的服务机制在内部节点只进行简单的调度转发，而流状 态信息的保存与流监控机制的实现等只在边界节点进行，内部节点是状态无关的。 ( 2 ) 简化网络内部节点的服务对象采用聚集传输控制，服务对象是流聚集而非 单流，单流信息只在网络边界保存和处理。 边界节点根据用户的流规定( p r o f i l e ) 和资源预留信息将进入网络的单流分类、 整形、聚合为不同的流聚集，这种聚集信息存储在每个i p 包头的d s ( d i f f e r e n t i a t e d s e r v i c e s ) 标记域( f i e l d ) 中，称为d s 标记( d i f f e r e n t i a t e ds e r v i c e s c o d e p o i n t ，d s c p ) ：内部节点在调度转发i p 包对根据包头的d s c p 选择提供特定质量的 调度转发服务，其外特性称为每跳行为( p e r h o p b e h a v i o r ，p h b ) 。网络边界对单流做 分类聚合与网络内部对聚集流提供特定质量的调度转发服务，这两个过程是通过i p 包头内的d s c p 协同起来的。 由于d i f f s e r v 采用对数据流分类聚集后提供差别服务的方法实现对数据流的 可预测性传输，所以对q o s 的支持力度取决于传输服务的分级层次，各网络节点中存 储的状态信息数量仅正比于服务级别的数量而不是数据流的数量，由此d i f f s e r v 获 得了良好的扩展性。 1 1 3 多协议标记交换( m u l t i p r o t o c o ll a b e ls w i t c h i n g ，m p l s ) 多协议标记交换( m p l s ) 是时下最热门的技术之一，它将灵活的三层i p 选路和 高速的二层交换技术完美地结合起来，从而弥补了传统i p 网络的许多缺陷。它引入 了新的标签结构，对i p 网络的改变较大，m p l s 可以克服d i f f s e r v 不能解决的一个问 南京邮电学院硕士学位论文 题：即将流量从网络拥塞的部分分流。在现有的网络中，路由是由路由选择协议决 定的，网络管理员不能控制它，当网络拥塞时，以上所述的服务体系没有重新选路 的能力。而m p l s 提供了由源建立到目的地显式路由的机制，它可以和路由协议的选 路不同。所以如果两个节点之间拥塞，网络管理员可以建立显式路由来分流流量， 对q o s 提供了更为可靠的保证。 1 1 4 流量工程( t r a f f i ce n g i n e e r i n g ) 网络资源不足或流量的不均匀分布都会导致拥塞的产生。前者只能通过增加网 络资源解决；在后者，网络的一部分过负荷，而另一部分轻负荷，这种情况通常由 现有的以找到最短路径为目的路由协议引起。流量工程主要是运行网络的性能优化， 研究的主要内容是如何通过平衡负载来降低业务流通过网络时拥塞的概率。一般来 说，它包含了技术的应用、测量、模型化、归纳的科学准则和i n t e r n e t 流量的控制， 以及如何将这些知识和技术应用到实践中来获得一些特定的性能指标。m p l s 中关心 的流量工程的方面是测量和控制。 流量工程的一个主要目的就是在促进有效、可靠的网络操作的同时，优化网络 资源的利用率和流量的性能。由于网络资源的昂贵和因特网激烈的商业竞争的本质， 流量工程已经为大型自治系统中一个不可缺少的功能。 1 1 5q o s 路由( q u a l i t yo fs e r v i c er o u t i n g ，q o s r ) 服务质量路由( q o sr o u t i n g ) 是一种基于数据流q o s 请求和网络可用资源进行路 由的机制。或者，q o s 路由是一种动态路由协议，并且在其路径选择标准里可能包含可 用带宽、链路和端到端路径利用率、资源消费量、延迟、跳数以及抖动等q o s 参数。 1 、2q o s 路由问题阳胁鄙1 钔 目前的网络研究主要通过两个途径提高q o s 个途径是节点控制：另一个途 径是整网或局部网络控制。节点控制在单节点或单链路完成，主要控制业务对单节 点共享资源的占用，包括共享的链路、缓存区、处理器资源节点控制主要的策略包 括：业务流整形、业务调度、节点缓冲区管理。整网或局部网络控制通常通过对路 由与信令的控制达到对业务流或业务连接在网络中传输的直接控制。因为路由直接 关系到网络性能，所以q o s 路由成为解决q o s 问题的项关键技术。 6 南京邮电学院硕士学位论文 目前许多有关支持q o s 的研究主要着眼于调度、拥塞控制和资源预留，而研究 q o s 路由的较少。因此有关此领域的工作比较新颖，本文主要讨论o o s 路由问题。 从应用背景看，目前q o s 路由的研究可以分为三个方面：单播路由( u n i c a s t r o u t i n g ) ，多播路由( m u l i t c a s tr o u t i n g ) 和a d h o c 路由；本文主要讨论单播路由问 题。 1 2 1i n t e r n e t 路由结构 i n t e r n e t 是一个基于路由器的通信网络，所有末端节点( 主机) 都必须通过网 络节点( 路由器) 才能与其他末端节点进行通信；路由器将主机从繁重的路由负担 中解放出来，决定i p 分组转发方向的关键因素是路由表( 表项的内容为主机的网络 地址) ，而路由表的查找、建立、维护和更新工作是由路由器完成的。这一部分的 功能在路由器中占有很重要的地位，它直接涉及n 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 2 路由算法类型 路由选择算法根据是否随当前网络状况( 信息流量和拓扑结构) 的变化而动态 调整分为两大类：非自适应( 静态) 、自适应( 动态) 非自适应算法不能根据网络 当前实际传输量和拓扑变化来做路由选择，而是按原先设计好的路径传送，路径的设 定和修改是静态的。自适应算法是根据当前网络流量和拓扑等条件来改变路由选择 是动态路由选择算法：现代计算机网络通常使用动态路由选择算法，目前常用的动态 路由选择算法有以下两种，即距离矢量路由选择算法和链路状态路由选择算法。 南京邮电学院硕士学位论文 1 、距离矢量路由选择( d i s t a n c ev e c t o rr o u t i n g ) 算法 距离矢量路由选择算法是让每一个路由器维护一张表，表中给出了每个目的地 已知的最佳距离和线路。通过与相邻路由器交换信息来更新表中的数据。距离矢量 路由选择算法在理论上能有效地工作，但实际上却有很大的缺陷，一是它没有考虑线 路的带宽：二是算法本身要消耗过多的时间用于记录信息：三是它的运算时间有可能 较长，特别是它对好消息的反应迅速，但对坏消息却反应迟钝。 2 、链路状态路由选择算法 链路状态路由选择算法其实现的思想非常简单，可以分为五个部分加以描述：发 现它的邻近节点，并获知其网络地址：测量到其各邻近节点的延迟或开销：组装一个 分组以告之它刚知道的所有信息：将这个分组发送给所有其他路由器：计算到每个其 他路由器的最短路径。事实上，完整的拓扑结构和所有的延迟都已被测量并发布到各 个路由器中随后，各个路由器都可咀用d i j k s t r a 算法来找出最短路径。 距离矢量路由选择算法和链路状态路由选择算法各有特点，距离矢量路由选择 算法原理清楚，实现简单，并且对路由器处理能力要求不高，在规模较小和拓扑变化 不快的网络中获得了广泛的应用，而且由于成形较早，比较成熟。链路状态路由选择 算法性能优越，适应于规模较大及拓扑变化比较快的网络，但每一网络节点( 包括主 机和路由器) 均需要实时形成全网的拓扑图及以自己为根节点的树，因此对c p u 的处 理能力提出较高的要求，同时由于路由信息是以广播的方式传播的，比较占网络带 宽。由于两种算法各有优点，为适应组网的需要，路由器中就应当同时配置两种类型 的路由协议以实现距离矢量路由选择算法和链路状态路由选择算法。 1 2 3 单播路由协议 单播是i n t e r n e t 中最基本的功能，是点对点的通信。单播时在源主机和目标主机 之间需要有单独的数据通道，源主机所发出的分组中必须包括能够标识源_ 丰机和目 标主机的唯一的i p 地址。另外，从源主机发出的每一个分组只能传送给一个目标丰机 并由路由器或交换机来实现分组的转发。在数据转发路径上的每一个路由器都要维 护由单播路由协议构成的路由表，并根据分组中目的地址查找路由表来确定转发路 径。随着因特网规模的急速增长，使用单一协议实现网络互联已不可能实现，所以将 南京邮电学院硕士学位论文 网络划分为多个自治系统( a u t o n o m o u ss y s t e m ，a s ) 根据路由器在自治系统中的位 置，可将路由协议分为内部网关协议和外部网关协议。以下介绍几种常用的路由协 议。 1 、路由信息协议r i p r i p 协议采用距离矢量路由选择算法，该算法早在i n t e r n e t 的前身a r p a n e t 网络 中就已经被广泛采用，它综合了实际应用中许多现实版本的特点，同时为版本的兼容 互通性提供了可靠的依据。随着网络技术的发展，随后r i p 又扩展为r i p 2 ：该协议使 r i p 消息能够携带更多的信息，并允许使用一个简单的认证机制保护路由表更新，更 重要的是增加了对可变长予网掩码( v a r i a b l el e n g t hs u b n e tm a s k ，v l s m ) 的支 持r i p 使用距离( 一般用跳数) 作为度量来决定最佳路径。该协议是一个成熟、稳定 的单播路由协议，被路由器厂商广泛支持，由于具有易于配置的特点，在没有多重 路径的网络中，r i p 被广泛使用。但是，r i p 收敛时间长，适用网络规模小，在具有多重 路径的网络中可能导致无穷计算的问题，另外使用距离作为唯一标准选择的路径不 一定是”最佳”路径。 2 、最短路径优先协议o s p f o s p f 协议采用链路状态路由选择算法。最初的因特网主要采用r i p 协议，该协议 在小系统中工作得很好，但当a s 变大后就不再那么好了。因此i e t f 着手开发了o s p f 协议。后来o s p f 扩展到i p v 6 ，被称为o s p f v 3 。o s p f 路由选择是基于网络中物理链路 的状态的变化，并且该变化被立即广播到网络中的每一个路由器。o s p f 能够实现快 速适应网络拓扑变化的功能，所以o s p f 更加适合于大型的互联网络。但是o s p f 依然存 在路由计算量大、交互信息多的缺陷。 3 、边界网关协议b g p 在a s 内部，因特网上推荐使用的路由协议是o s p f ( 虽然它肯定不是唯一使用的 协议) ，在a s 之间，使用的是另一个协议，即边界网关协议b g p 。b g p 是一个用于自 治系统之间的、复杂的分布式动态路由协议，是最重要、最常用的路由协议之一， 是中高档路由器应当支持的路由协议。b g p 是目前唯一在i n t e r n e t 上使用的域间路由 协议，综合了距离矢量路由选择算法和链路状态路由选择算法。b g p 通过在路由信息 中增加自治系统的路径属性，来构造拓扑图并用于选择路由，从而消除路由环路并 南京邮电学院硕士学位论文 实施用户配置的策略。b g p 必须保存已经发送的路由信息，以便发送一条新路由前确 认其是否真的应该发送，所以增加了协议的复杂程度。b g p 支持域间路由( c l a s s l e s s i n t e rd o m a i nr o u t i n g ，c i d r ) 来减小路由表的体积和发送路由的通信量。 1 2 4n p 完全( n o n d e t e r m i n i s t i cp o l y n i m i a lc o m p l e t e ) 问题 当前i n t e r n e t 的主要路由协议包括域内路由协议o s p f 、r i p 和域问路由协议b g p 等。都是“尽力发送”的路由协议，选择路由时通常只基于单一度量优化，因此通 常所有的业务都是基于“最短路径”，难以满足多样的q o s 需求，选择路由时即便源 到目的节点之间存在“更好的”路径，只要不是最短路径就不会投入使用，因此可能 导致某些链路空闲时另外一些链路的拥塞。q o s r 路由就是将传统的最短路径变为一 条更好的路径，其主要目标包括以下两点： ( 1 ) 为每一个接纳的q o s 业务连接请求，找到满足其q o s 要求的可行路径( 组播树) ： ( 2 ) 优化全局资源利用率，平衡网络负载，从而最大化网络接受其他q o s 请求的能 力。为了提供q o s 保证，数据传输前通常需要沿着计算好的路径，从源到目的地传播 一个消息，用来通知路径上的所有节点为这个o o s 业务保留相应的资源( 如带宽、缓存 等) ，而后续的数据传输则沿着这条已经预留了资源的路径。因此，q o s r 具有面向连接 的特性。根据计算可行路径的时刻，q o s r 可以分为预计算和在线计算两种。预计算 ( p r e c o m p u t a t i o n ) 采用一个后台进程，根据网络状态信息来构造路由表，当q o s 请求 时，只需通过查找路由表就能确定可行路径。在典型网络设置中，q o s 连接请求的到达 速率远大于网络的变化速度，因此可以使用预计算模式。由于q o s 业务的多样性，路由 表为了包含每个可能的q o s 业务，其规模会相当庞大因而降低了可扩展性。在线计算 则是当q o s 请求到达时，再根据状态信息计算可行路径。这种方式虽然不需要事先构 造路由表，但每次路由计算延迟较大，并且路由器负担很重。q o s r 问题很难完全解决 的原因包括：( 1 ) 寻找同时满足两个以上路径约束( 优化) 的可行路径，具有n p 完全的 计算复杂度：( 2 ) 为了提高可扩展性所使用的层次化模型，产生了多种参数如何聚集 的问题：( 3 ) 网络状态信息的陈旧性极大地影响t q o s r 算法的性能：( 4 ) 将q o s r 融入 到当前这种尽力发送的路由体系结构中，原有的尽力发送业务将受到巨大的冲击。 n p 完全问题：同时对两个以上相互独立的参数提出要求时，这个问题就是一个n p 南京邮电学院硕士学位论文 完全的问题。实时应用往往会对延时，延时抖动，带宽，丢失率，业务代价等多个参数 同时提出性能要求。例如，实时多媒体业务会对延时和延时抖动同时提出要求。这 些参数相互独立时，选择满足多个参数限制的路由就成为n p 完全问题。n p 完全问题 直接关系到路由算法的可实现性。 q o s 路由问题是n p 完全问题，其解决方法一般有两种： ( 1 ) 求出具有指数复杂度的精确解。这种方法虽然能求出问题的精确解，但计 算具有n p 难度，只有理论意义，不能实际应用； ( 2 ) 通过启发式算法找出最优解。启发式路由算法用于解决多限制条件下的0 0 s 路 由问题。该算法可以降低算法的时间复杂度，但不能保证在即使存在传输路径的条件 下发现一条可行的传输路径。近年来，各国学者也提出了一些快速有效的方法。虽 然启发式算法能够保证在多项式时间内找到合适解，但启发式算法有个明显缺点， 即缺乏全局观点。启发式算法的基本原理是对于搜索过程中遇到的每个新状态( 或 者说每个新节点) ，按估价函数计算出它的最佳代价估计值，然后选出当时估计值的 最小状态，并从该节点开始继续搜索。可以看出每个新节点的选择是以当时节点 与新节点之间最小估计值为标准，而不是基于整个问题的最小估计值。因此，一般 只能找到局部最优解，难以找到全局最优解。 近年来，启发式智能优化方法愈来愈引起人们的关注。如：模拟退火、遗传算 法、蚁群算法、d n a 计算等，它们是解决n p 问题的有效工具。 本文主要针对单播路由选择，提出将蚁群算法与遗传算法进行融合，确定q o s 路由选择策略。 1 、3q o s 单播路由选择喵“1 ”心刚口踟 1 3 1 问题描述 通常将o o s 路由选择问题描述为一个有向图口( ，)，其中，有向图的顶点 表示网络结点( 交换机、路由器、集线器等网络节点设备) ；有向图的边表示网络 链路具有多个属性，可以是带宽、链路传输延迟、花费等参数：是网络结点集， 是网络链路集n 是网络中单播情况下( 源结点，目的结点) 的集合，元素 吩l e 为l ( 疗，吩) 或lu = n i n j ，q o s 路由选择即为在有向图g ( ，) 中，为特定的u 南京邮电学院硕士学位论文 u 找出代价( c o s t ) 最小，同时满足单播服务所需求q o s 的路由。 在图占中，如果对卢l ，2 ，卜1 有n i ，h h l e l ，则仁( n l r ”2 ，m ) 为图g 的一 条从_ - 7 i 到珊的路径，也记作卢f 如* iji = i ，2 ，k - i ) 。 q o s r 的目标就是选择一条从源节点n l 到目标节点的可行路径只使其满足 服务q o s 要求。 o o s 请求需要通过可测量的o o s 度量来实现，常用的几种o o s 度量主要包括可用带 宽、延迟、分组丢失率、抖动、花费等，不同的度量具有不同的性质按照这些性质， q o s 度量可以分为：可加性度量、可乘性度量和最小性度量。 对于图占中的路径p = 印l ，舵，h 0 ，若b 1 尸( 其中i = 1 ，2 ，1 ) ，将b l 的第j 个属性记为“。或w l ( 1 i 1 ) ，整个路径尸的第j 个属性记为以。 以上3 类度量的定义如下： j 一 1 若路径尸的第j 个属性为可加性度量，则：，一2 善“+ 可加性度量包括延迟、抖动、花费、转发跳数等。例如：一条路径p 的延迟为从 源到目的地的所有节点、链路延迟的总和。 ( 2 ) 若路径尸的第个属性为可乘性度量，则：“ 例如，分组丢失率属于可乘度量。 ( 3 ) 若路径尸的第个属性为最小性度量，则：w ：2m i n 。 仁h p i 例如，带宽为最小性度量，即路径带宽为路径上瓶颈链路的带宽。 o o s 度量以及多个q o s 度量的组合，其计算的代价是不同的。例如，求解多重最 小性度量的组合可以在多项式时间内完成，而多重可加性度量的组合通常不能在多 项式时间内完成。 一个单播请求。由( “= ( 只d ) ) u 表示，它由源结点s 、目的结点d 以及 q o s 请求构成。o o s 请求包括带宽需求b 。、延迟d 。、丢失率三。和抖动j 。等， 由应用用户提供。如果路由算法能找到满足下列条件的代价最小的路由，路由请求u 将被接受： 南京邮电学院硕士学位论文 可用带宽限制：a b ( z ) b 。，对路由u 上的每一链路而言。 。端到端延迟限制：d n ( n ) + d l ( t ) d 。，在路由u 中m e n if e 朋 端到端丢失率限制：f i ( 1 一上晨( h ) ) ( 卜l 。) ，在路由u 中。这里我们假设分组 n e n l 丢失的原因主要是结点的缓冲溢出。 端到端抖动限制：n ，( d ) j 。，在目的结点通常，抖动可通过目的结点的缓 冲进行平滑，故为简化问题，只考虑目的结点。 上述条件中，a b ( j ) 表示链路j 的可用带宽a b ：一曰+ ：觑v 是结点处理延 迟，p n ：一疗+ ：说是链路延迟，d l ：一斤+ ：n l 是路由u 上的结点集：l 是 路由u 上的链路集：三斤是结点丢失率，斤：n 一斤+ ，肜是目的结点d 的抖动， 矿： 一斤+ ，曰+ 表示正实数集。 1 3 2q o s 路由策略 通过路由协议交互，每个节点收集到适当的网络状态信息后，需要据此采用一 种相应的路由策略实现路由。按照网络状态信息维护的方式和路径的搜索方式分类， 可把路由策略分为源路由( 集中式路由) 、分布式路由和层次化路由。 源路由中，每一个节点维护着完整的全局信息，包括网络拓扑结构和每一个链路 的状态信息，最优路径的计算基于这些全局信息在源节点进行：分布式路由机制中， 每一个节点无须维护全局信息，一般只要知道相邻节点的信息，路径通过在各个节点 之间进行分布式计算获得，控制信息在节点之间交换，综合使用每个节点保存的状态 信息来搜索路径，大部分分布式路由算法都需要一个距离矢量协议( 或者链路状态协 议) 在每一个节点处以距离矢量的形式维护和路由计算相关的信息，基于这些距离 矢量，路由过程一跳一跳地完成：层次化路主要是为了解决可扩展性问题，把网络中 的一部分节点聚合成一个逻辑节点，然后把一部分这样的逻辑节点聚合成再上一层 的逻辑节点，形成一个树结构，路由过程先从最上层的逻辑节点开始计算。 i 、源路由 源路由的算法非常简单，易于实现和评价。源节点的集中式计算能够避免分布 式的各种缺点：如网络状态数据不一致所造成的死锁和回路等问题。但由于每个可 南京邮电学院硕士学位论文 能的源节点都需要收集和维护完整的全局状态，因此源路由带来了以下几个问题： ( 1 ) 由于源路由需要通过链路状态交互，因此维护全局状态的开销很大。 ( 2 ) 源节点根据全局状态计算可行路径，时间和空间开销很大。 ( 3 ) 源节点所维护的全局状态，其陈旧性对路由的性能影响很大。 随着网络规模扩大，以上三个问题越发突出。考虑到可扩展性，在支持q o s 的大 型网络中直接使用这种源路由的策略是不可行的。 2 、分布式路由 分布式路由中，每个节点并不知道完整的可行路径，甚至只知道可行路径中的 下一跳节点，至于下一跳节点再往后的路径则由下一跳节点计算和决定。当前 i n t e r n e t 的路由策略就是这种分布式路由。分布式路由将计算分散在各个中间节点， 减少了计算复杂程度，甚至有的计算只要求节点具有本地状态，因而具有很好的可 扩展性。但是分布式处理较为复杂，尤其是在q o s 多约束时很难设计良好的启发式算 法。此外，由于各个节点依靠本地维护的全局信息独立计算可行路径，因此由于信 息不一致可能造成回路，这就需要额外的回路检测算法。 3 、层次化路由 网络中的节点通过聚集形成多层次的拓扑结构，每个物理节点保存聚集状态。 为建立连接，源节点沿着可行路径发送控制信息，当一个组的边界节点作为代表这 个组的逻辑节点而收到控制信息时，使用源路由的方式将可行路径扩展，直到通过 这个组。层次化路由直被用来解决大规模网络路由计算中的可扩展性问题。层次 化路由计算的过程通常都要结合源路由策略和分布式路由策略，因为每一个节点只 维护聚合后的一部分网络状态信息。一般来说，在同一层内可以直接应用己有的源路 由策略，分布在不同逻辑层之间的计算结果结合起来得到最终的路径。所以层次化路 由同时具有源路由和分布式路由