（计算机应用技术专业论文）基于tcpip的qos路由算法的研究.pdf

博上论文基于t c p i p 的q o s 路由算法的研究 摘要 a t m 网络是既能支持传统数据业务，又能支持实时多媒体业务的网络。然 而转向a t m 网络意味着或者构造第二层网络基础设施、或者用a t m 网络替代 已存在的网络，但这两种方法在费用上都是惊人的。如何在t c p i p 体系结构中 支持有多种服务质量要求的业务? 一种方法是研究开发新的网络协议，如i p v 6 、 r s v p ( 资源预留协议) 、r t p ( 实时传送协议) ；然而最根本的方法还是改造路由 器，使其具有处理q o s 请求的功能。 因此，新开发的路由技术不再仅仅是为数据传输找到一条通道就行，还需要 考虑所选路径的传输容量和服务质量，即具有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 o s 路由算法必须同时满足三个目标：一是为每个接受的q o s 、悭务流提供 服务质量保证，二是达到网络全局资源的最佳利用，第三是对性能影响尽可能小。 前者要求在多约束条件下计算可行路径，后者则要求在多条可行路径中进一步优 化。优化的方式通常是首先设计费用( c o s t ) 函数，然后求解函数值最优的可行路 径。而多约束下求解f 优化的1 可行路径属于n p 完全问题。 本文主要研究如何通过重新设计遗传算子，构建一个综合评价函数，以多目 标遗传算法解决q o s 路由问题。具体地由三部分组成：第一部分由第1 、2 章构 成，主要对经典路由算法及协议、q o s 路由算法的研究进行综述，阐述本文的主 要工作；第二部分由第3 、4 、5 、6 、7 章构成，它是全文的核心，针对q o s 路 由问题，研究并设计了几种q o s 路由算法；第三部分由第8 章构成，对本文的 研究工作进行小结。 关键字：网络安全，q o s 路由算法，多目标遗传算法，d i j k s t r a 算法，f a l l b a c k 算法，t c p i p 协议，a t m 网络，负载均衡 摘要博士论文 a b s t r a c t t h ea t mn e t w o r ki st h eo n l yn e t w o r kt h a tc a ns u p p o r tt r a d i t i o n a ld a t ab u s i n e s s a n dr e a l t i m e m u l t i - m e d i ab u s i n e s sa tp r e s e n t w h e nw eu s et h ea t mn e t w o r k ，i t m e a n st h a tw es h o u l db u i l dt h es e c o n dl a y e ro f n e t w o r k sb a s i ce q u i p m e n to rr e p l a c e t h ee x i s t e dn e t w o r kw i t ht h ea t mn e t w o r k ，w h i c hc o s th i g h h o wc a ni t s u p p o r t m u l t i m e d i ab u s i n e s so f q o s ( q u a l i t y o f s e r v i c e ：q o s ) i nt c p i pa r c h i t e c t u r e ? o n ei s t o d e v e l o pa n e wn e t w o r kp r o t o c o ls u c ha si p v 6 、r s v p ( r e s o u r c er e s e r v a t i o n p r o t o c 0 1 ) 、r t p ( r e a l t i m et r a n s p o r tp r o t o c 0 1 ) a c t u a l l yt h e b a s i cm e t h o di si m p r o v i n g t h er o u t e rt of i tt h ed e m a n d so f q o s t h en e w r o u t i n gt e c h n o l o g yi sn o to n l yt of i n da na c c e s sf o rd a t at r a n s p o r tb u t a l s ot of u l f i l lt h e t r a n s p o r tc a p a c i t ya n ds e r v i n gq u a l i f i e s i tm e a n s a r o u t i n ga l g o r i t h m t h a th a st h ea b i l i t yo f q o s w h e ni t a n a l y s e sa n da f f o r d st h eb a l a n c eo f t h eq u a l i t yo f d a t at r a n s p o r ti na l la c c e s s e st ot h en e t w o r k t h er o u t i n go fu n c i a l s 、m u l t i c a s to ri n d o m a i n 、b e t w e e nd o m a i n ，r o u t i n ga l g o r i t h m sa l lh a v ei n q u i r et e c h n o l o g yt h a ta s k s f o r q u i c kc o n v e r g e n c ea n dh i g h e f f i c i e n t r o u t i n g l i s t w i t ht h e d e v e l o p m e n to f n e t w o r ka n da p p l i c a t i o nb u s i n e s s ，q o s b a s e dr o u t i n gb e c o m e so n eo ft h en u c l e a r n e t w o r k p r o b l e m s q o s - b a s e dr o u t i n ga l g o r i t h mm u s tg e tt h r e ep u r p o s e s ：1 ) o f f e r i n gt h eg u a r a n t e e o fs e r v i c eq u a l i t yf o re a c ha c c e p t e db u s i n e s s s t r e a mo fq o s ；2 ) m a k i n gt h eo p t i m u m u s eo fa l ln e t w o r kr e s o u r c e s ；3 、i n f l u e n c i n gt h el e a s tp r o p e r t i e s t h ef o r m e rd e m a n d s t oc a l c u l a t et h e p o s s i b l ea c c e s s e s o nc o n d i t i o no fm u l t i c o n t r o l ，a n dt h el a t t e rd e m a n d s f u r t h e r o p t i m i z ea m o n g t h e m u l t i p l ep o s s i b l ea c c e s s e s o p t i m i z a t i o n i s u s u a l l y d e s i g n i n gt h ec o s tf u n c t i o n ，w o r k i n go u t t h eo p t i m u mp o s s i b l ea c c e s s ，w h i c hb e l o n g s t on p c o m p l e t ep r o b l e m t h em a i n p u r p o s e o ft h i sp a p e ri st oc o n d u c tac o m p r e h e n s i v e e v a l u a t i n gf u n c t i o n t os o l v eq o sr o u t ep r o b l e mt h r o t i g hr e - d e s i g n i n gg e n ea r i t h m e t i co p e r a t o r s t h r e e p a r t sc o m p o s e t h ep a p e r t h ef i r s tp a r ti n v o l v e st h ec h a p t e r1a n d c h a p t e r2 t h e m a i n a i mi st os t u d yt h ec l a s s i cr o u t ea r i t h m e t i c ，p r o t o c o l sa n dq o sr o u t ea r i t h m e t i c t h e s e c o n dp a r ti n v o l v e st h ec h a p t e r3 - c h a p t e r7 i ti st h ec o r ei nt h i sp a p e r a c c o r d i n gt o t h eq o sr o u t ep r o b l e m ，s e v e r a lq o sr o u t ea r i t h m e t i ci sd e s i g n e d t h et h i r dp a r t i n v o l v e st h ec h a p t e r8 t h es t u d yi s s u e sa r es u m m a r i z e di nt h i sp a r t k e yw o r d s ：n e t w o r ks e c u r i t y , q o sr o u t i n ga l g o r i t h m ，m u l t i - o b j e c t g e n e t i c a l g o r i t h m ，d i j k s t r aa l g o r i t h m ，f a l l b a e k + a l g o r i t h m ，t c p i pp r o t o c o l ，a t mn e t w o r k ， l o a d b a l a n c i n g i i 博士论文基于t c p i p 的q o s 路由算法的研究 1绪论 1 1 论文的背景和意义 当前i n t e m e t 只提供尽力发送( b e s t e f f o r t ) 服务，网络层不区分业务，尽管i p 分组头包含指明优先级及服务类型的字段，但在路由器选择路由和处理分组时往 往被忽略了，根本不予处理。而将网络资源公平地提供给各类业务，在分组丢失、 时延等方面公平地对待各类业务。这种尽力发送的机制使网络层无法保证传输的 参数，然而丢失率、带宽、端到端时延、时延抖动等对于应用业务往往是至关重 要的。文件传输业务要求分组的丢失率尽可能低，而传输时延不是关键因素；实 时多媒体业务则更注重时延和时延抖动。这就要求网络能够区别对待各种业务， 并对它们提供不同的服务质量。由于i p 是无连接的协议，不要求像a t m 网络那 样在数据传输前从源节点到目的节点建立连接。这种尽力发送的体系结构是无连 接、与状态无关的，它既不能支持资源预留，也不能预测传输参数，甚至还可能 产生多媒体实时业务不希望的乱序等。由此，面向服务质量的网络体系结构应运 而生。 目前唯一既能支持传统数据业务，又能支持实时多媒体业务的网络是a t m 网络。然而转向a t m 网络意味着或者构造第二层网络基础设施，或者用a t m 网络替代已存在的网络，但这两种方法在费用上都是惊人的。如何在t c p i p 体 系结构中支持有多神q o s 要求的业务? 一种方法是研究开发新的网络协议，如 i p v 6 、r s v p ( 资源预留协议) 、r t p ( 实时传送协议) ；然而最根本的方法还是改 造路由器，使其具有处理q o s 请求的功能。 新丌发的路由技术不再仅仅是为数据传输找到一条通道就行，还需要考虑所 选路径的传输容量和服务质量，即具有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 o s 路由算法必须同时满足三个目标：一是为每个接受的q o s 业务流提供 服务质量保证，二是达到网络全局资源的最佳利用，第三是对性能影响尽可能小。 前者要求在多约束条件下计算可行路径，后者则要求在多条可行路径中进一步优 化。优化的方式通常是首先设计费用( c o s t ) 函数，然后求解函数值最优的可行路 径。而多约束下求解( 优化的) 可行路径属于n p 完全问题。 由于q o s 路由问题具有n p 的性质，而遗传算法是一种先进的优化算法，对 于n p 问题是一种有效的工具。本文试图从基于负载均衡和遗传策略的角度，研 博士论文 究q o s 路由的遗传算法。 q o s 路由算法的复杂性主要表现在以下几方面。 1 1 1 路由算法的复杂性 路由算法的复杂性通常表现在： ( 1 ) 路由算法要求子网中所有节点相互协调，而不像数据链路层和高层那样 仅涉及一对对等模块之间的协调； ( 2 ) 路由算法必须处理链路和节点的故障，要求对业务进行重新定向的对系 统维持的数据库进行更新； ( 3 ) 必须达到高性能，当网络部分区域拥塞时，路由算法必须能够修正路由。 一个路由算法通常应当在高的业务负荷的情况下，在保证相同的成本条件 下，可以增加网络的通过量；在轻负荷和中等负荷的情况下，可以减少每一个分 组的平均成本。 路由算法通常是与流量控制算法一起相互作用，共同确定网络的通过量和时 延，如图1 1 1 - 1 所示。路由算法应当将网络中分组时延维持在很低的水平上。 辩聊 ( a ) 路由选择与流量控制的相互作用于( b ) 路由选择对网络性能的影响 图1 1 卜1 路由算法与流控算法的相互作用 由于时延的存在，流控算法通过平衡通过量的时延的关系，采取必要措施来 拒绝一些可能会引起网络阻塞的业务。好的流控算法应当允许更多的业务流进入 网络。时延和通过量之间的严格平衡将同流控算法决定，而路由算法将决定不同 的通过量一时延曲线。 1 1 2i n t e r n e t 的应用范围广泛 根据对q o s 要求的不同，i n t e r n e t 业务可分为两大类：弹性( e l a s t i c ) 业务和 非弹性( i n e l a s t i c ) 业务。从用户的角度出发，可以将i n t e r a c t 上的多媒体应用划分 为5 类叽要求最小时延、最小时延抖动、最d 、丢包率以及固定带宽保证的高保 真音频视频系统；要求最小时延、最小时延抖动及最小丢包率，但应用信息流的 生成和发送具有随机性和突发特性的实时音频视频系统；具有突发数据特性且允 许一定程度传送时延的非实时音频视频系统：无时延和抖动要求，但要求数据无 差错传送的数据类；信息流的传送速率允许在较大范围内变化的可控制信息流量 博论文 基于l | 1 c p i p 的q o s 路由算泣的研究 的应用类。另外，多媒体应用的数据流中往往包含有不同的媒体信息，不同媒体 信息之间存在着特定的同步关系，该关系若遭到破坏将严重影响应用的性能。如 图1 1 2 - 1 所示。 j d k儿u w腿c k i 图1 1 2 - 1 各种流的复用 11 3in t e r n e t 业务流要求提供的服务质量不一样 i n t e r n e t 上的业务各种各样，有语音、图像、数据业务。各种业务对网络的 q o s 要求不同。i n t e m e t 中的业务q o s 参数主要包括：带宽要求( 传输速率) 、时 延和抖动上限、误码率和丢包率、同步等。弹性业务在网中时延及吞吐量变化时 仍能满足相应的应用要求。t c p f l p 网络支持这种传统业务类型。这类业务的应 用包括通用的i m e m e t 应用，如：文件传输、电孑邮件、远程登录、网络管理、 w e b 页访问。但这些应用在需求方面也是有区别的，如表1 1 3 - 1 所示。 表1 1 3 1 对应于各种应用和0 0 s 要求 应用时琏镶醛度带宜要求 口电话 高小 电视鸯议幕统高大 音乐 由由 皤象 由 大 w e b 页请问 由由 e - 蛐i l 低小 因此即使对传统的弹性业务，也应考虑q o s 要求。非弹性业务不容易适应 或根本不能适应网络中时延或吞吐量的变化。这种业务应用的代表是语音或图像 传输。这类应用要求保证： ( 1 ) 吞吐量：要求最小的吞吐量的保证。不像弹性业务可以在服务降级时仍 能传送数据，许多非弹性业务不能做到这一点。 ( 2 ) 时延：时延敏感的典型例子是股票交易，接受的服务延时越长，操作者 的行动就越慢。 ( 3 ) 时延抖动：允许的时延越大，传送数据的真正时延就越长，接收端所需 的延时缓冲区就越大。实时交互应用，如：电视会议，可能要求一个时延变化的 1 绪论博士论文 合理上限。 ( 4 ) 分组丢失：不同实时应用所能承受的分组丢失率不同。 另外非弹性业务还提出两项新的要求： ( 1 ) 优先级：应用可以在传送之前用某种业务请求功能提前提出它们的q o s 要求，或者在传送过程中用i p 分组头的适当字段指明它们的要求。前一种方法 较可取，它可以使提出要求的过程更方便和灵活，同时使网络能预测到要求，并 在不能满足要求时拒绝它。这种方法使用了某种资源预留协议，如r s v p 等。 ( 2 ) 支持弹性业务。非弹性业务在网络阻塞时不会撤回或减少业务需求。因 此在阻塞时，弹性业务会被挤出网络。所以需要一种策略防止这种情况发生。当 种业务请求申请了太多的资源面留下的资源不足以处理当前的弹性业务时，网 络就拒绝请求。 1 1 4q 0 8 路由选择目标之间的可公度性 与单目标路由不同，多目标路由最显著的特点是目标之间的不可公度性和目 标产生的矛盾性。所谓目标之间的不可公度性是指各个目标之间没有统一的度量 标准。在0 0 s 路由的选择目标中，通常希望端到端有时延最小、丢包率最小、 瓶颈带宽最大、所占用的网络资源最少、若各种服务所需的费用不同，用户还希 望使用网络的费用最小。在上述5 个目标中，时延的度量单位是时问( s 或m s 、 掣s ) ，费用是用钱的单位( 元) ，路径的度量单位是长度( m 或t 聊) ，丢包率的度 量单位是b i t ，带宽是用b p s 或b ，s ，路径的跳数骰可以用占用的网络资源来表 示，而占用的网络资源目前还没有一定的度量标准。因此，从物理意义上讲，不 能把多个目标简单归并为单个目标，而目标之间的矛盾性使得强调改善某个目 标，可能使另一个目标变差。所以，在多目标规划中，一般不存在所有目标函数 共同的极大值点。 1 2 ( 1 0 s 路由研究现状 为了满足i n t e m e t 上各种网络应用的传输服务质量的需求，i n t e r a c t _ 1 ：程任务 组( i e t e ) 先后提出了集成服务资源预留模型( i n t s e r v r s v p ：i n t e g r a t e d s e r v i c e r e s o u r c er e s e r v a t i o np r o t o c 0 1 ) 、区分服务模型( d i f t s e r v ：d i f f e r e n t i a t e ds e r v i c e ) 多协议标记交换( m p l s ：m u l t ip r o t o c o l l a b e l s w i t c h i n g ) 以及q o s 路由( q o s r ： q o s b a s e dr o u t i n g ) a 1 2 1i n t s e r v r s v p 【2 】 i n t s e r v 可对单个的应用会话提供服务质量的保证，主要特点有两个：一是 资源预留。一个路由器需要知道不断出现的会话已经预留了多少资源：二是呼叫 建立。一个需要服务质量保证的会话必须首先在源节点到目标节点的路径之间的 每一个路由器预留足够的资源，以保证其端到端的服务质量的要求。因此在一个 4 博士论文 基于t c p i p 的q o s 路由算法的研究 会话之前必须有一个呼叫建立过程，它需要在其分组传输路径中的每一个路由器 都参加。每一个路由器都要确定该会话所需的本地资源是否够用，同时还不要影 响到已经建立的会话的服务质量。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 dp r o t o c 0 1 ) ，可以使应用程序得到比通常的“尽力而为”更加可靠 的服务。 i n t s e r v 共有4 个部分组成：资源预留协议r s v p ，在传送数据之前应先建 立会话路径和预留所需的资源。接纳控$ | i ( a d m i s s i o nc o n t r 0 1 ) 程序，用来决定是 否同意对某一资源的请求。分类程序( c l a s s i f i e r ) ，用来将进入路由器的分组进 行分类，并根据分类的结果将不同类别的分组放入特定的队列。调度程序 ( s c h e d u l e r l ，根据服务质量要求决定分组发送的前后顺序。 1 2 2d i f f s e r v d i f f s e r v 的基本思想是对网络层和传输层只做相对较小的改变，但在网络的 边缘( e p 在用户和i n t e m e t 服务提供者i s p 之间的接口) 加上计费和管制功能。这 种思想是引入较少量的服务类别，而针对每一个数据报指派一种服务类别。在路 由器的队列中对不同的服务类别给予不同的服务。d i f f s e r v 简单有效，可以满足 实际应用对可扩展性的要求。d i f f s e r v 可用于公用广域网。其实现途径是： ( 1 ) 简化网络，内部节点的服务机制。在内部节点只进行简单的高度传发， 而流状态信息的保存与流监控机制的实现等只在边界节点进行，内部节点是状态 无关的。 ( 2 ) 简化网络内部节点的服务对象。采用聚集传输控制，服务对象是流聚集 ( s t r e a ma g g r e g a t e ) 而非单流，单流信息只在网络边界保存。 具体而言，边界节点根据用户的流规定( p r o f i l e ) a n 资源预留信息将进入网络 的单流分类、整形、聚合为不同的流聚集，这种聚集信息存储在每个i p 包头的 d s ( d i f f e r e n t i a t e ds e r v i c e s ) 标记域( f i e l d l 3 ，4 1 ) 中，称为d s 标记( d s c p ：d i f f e r e n t i a t e d s e r v i c e sc o d e p o i m ) 。内部节点在调度传发i p 包时根据包头的d s c p 选择提供特 定质量的调度传发服务，其外部特性称为逐跳行为( p h b ：p e r h o p b e h a v i o r ) 。网 络边界对单流做分类聚合与网络内部对聚集流提供特定质量的调度传发服务。这 两个过程是通过i p 包头内的d s c p 协同起来的。 1 2 3l t l p k s m p l s 多协议标记交换是i e t f 制定的第三层交换规范，它是对第二层a t m 标记交换和第三层i p 路由协议的有机结合。既实现了a t m 的面向连接、简单高 速交换、q o s 保证、流量管理、流量工程等优点，又实现了i p 的灵活性、有效 性和可扩展性等优点。 i 绪论博士论文 m p l s 采用面连接的第二层交换支持无连接的第三层i p 包转发，以实现i p q o s 和流量工程。它采用第三层( i p ) 的控制协议( 如沿用已有的i p 路由协议，新 定义标记分配协议( l d p ) 代替a t m 信令) 来控制第二层( a t m ) 的数据交换。在用 户数据通信之前，通过l d p 协议建立类似a t mp v c s v c 的标记交换通道 ( l s p ) 。与a t mv p i v c i 一样，标记只在本地有意义，多个标记可以嵌套构成 标记栈，可以实现显式路由和层次化路由。 m p l s 域的出入口处设备称为边缘路由器( l e r ) ，核心设备称为标旧交换路 由器( l s r ) 。只在入口的l e r 进行一次根据i p 包头的相关信息将不同q o s 要求 的i p 数据流划分成不同的转发等效类( f e c ) ，并作相应的标记映射。具有相同 标记的数据流都属于相同的f e c 。沿事先建好的l s p ，内部的l s r 只根据标记 进行简单高速交换，不再作f e c 处理。m p l s 实现了网络核心处理简单，智能 在边缘接入层实现的原则，这符合i p 的精髓思想。 m p l s 是对i p 现有组网模式的革新，包括路由和转发体系结构。m p l s 提供 了传统路由器与i p 现有组网模式不具备的解决方案，如：显式路由、流量工程、 v p n 、保护现有电信网的投资( 通过a t mm p l s 支持) ，使网络运营商能在业务 量快速增长和q o s 要求的外部因素、网络资源优化的内部因素间找到较优的平 衡点。 1 2 4q o s r q o s r 是保证网络和业务q o s 的优化路由。这种路由是以资源预留( r s v p ) 为前提1 5 , 6 。依据网络的资源状态决定是否接纳该业务的连接请求，若接纳，则 为该连接在保证端到端时延要求的路径上各节点预留带宽，实现对业务的接入控 制。在尽量减少资源消耗的基础上，合理分配网络的流量负荷，减少拥塞概率， 同时有利系统在建立此连接之后，能接入更多的业务。一般有两种方案：一种是 负载平衡( 1 0 a d b a l a n c i n g ) ”，即将负载均匀地分布在各个链路上。另一种是称为 l o a d p a c k i n g 的方法【8 】，即将带宽需求窄的呼叫全并到某些链路上，使其它链路 剩下足够的带宽以接入带宽需求大的连接，这样保证网络对带宽连接和窄带连接 接入的公平性。在第2 章，我们将对有关q o s r 作进一步论述。 1 3 0 0 s 路由研究面临的问题 随着网络和应用业务的快速发展，目前有关q o s r 日益成为网络研究的核心 问题之一。目前在研究成果表明，在一定区域内部通过合理地配置基于链路状态 的q o s r 协议，为支持q o s 所引入的开销是完全可能接受的【9 】，然而q o s r 领域 在以下几方面还有待进一步研究。 ( i ) 并不是所有的路由器都支持r s v p 协议 如果用户会话之间存在着不支持r s v p 的路由器，那么对于那些支持r s v p 协议的路由器，它能确保用户需要的q o s ，而对于不支持r s v p 协议的路由器来 6 博l 论文 基于t c p i p 的q o s 路由算法的研究 讲，就只能依靠它们提供的尽量传送来达到一定的q o s ，这时就不能确保网络中 的各个部分都能给用户会话提供特定的q o s 。 ( 2 ) l o a d b a l a n c in g 和l o a d - p a c k i n g 方法的局限性 l o a d - b a l a n c i n g 方法可能导致链路带宽碎片( f r a g me n t a t i o n ) 过【l ，造成宽带 连接的被阻塞。如何对应用流量进行划分、如何计算满足所划区间的带宽请求的 可行路径以及窄带业务合并到某些链路上，l o a d p a c k i n g 方法并未给出具体的算 法。事实上，两种连接接入的公平性是难以实现的，这也造成某些链路的阻塞， 从而导致整个系统不可用，并且降低网络效益。 ( 3 ) 可扩展性 通过网络状态聚集能够以对数缩减信息量，相应的分层路由可以通过限制每 层内节点的数量使用源路由方式，从而很好地解决可扩展性问题。但这同时又引 入了新的问题：如何聚集状态信息、如何基于聚集状态设计良好的启发式算法。 目前所设计的状态信息聚集方法往往会丢失大量的可用信息，严重影响了q o s r 算法的性能：同时，所设计的启发式算法也往往是基于全局状态源路由策略的。 此外，由于很多q o s r i n 题的精确求解复杂度都是n p c 的，因此需要设计快速、 有效的启发式算法。 ( 4 ) 信息陈旧性 状态信息的陈旧性是实际网络中不可避免的，并且会对q o s r 算法的性能和 有效性造成显著影响。然而对这种陈旧性的分析涉及到复杂的随机数学模型，相 关的讨论往往基于模拟试验数据，而缺少定量的理论分析。此外，通常的算法只 是停留在理论设计和分析上，缺乏对信息陈旧情况下算法实际性能的考虑。因此， 可以考虑基于概率模型求解，寻找以最大概率满足q o s 约束的可行路径，从而有 效地减少建连失败对网络造成的额外负担。 ( 5 ) 多路路由与重路由 在多条可能的路径上同时探测可行路径的方法中，如何与资源预留相结合尚 无定论【】。此外，网络提供多条从源到目的的路径，并将这些路径并行复用起来 ( 如增加带宽) 而对用户业务透明，这是一种多路复用的路由方式。然而，其主要 问题是多条路径之间如何同步，以及如何避免分组的延迟抖动、乱序等 j “。由于 网络资源和可行路径分配的不合理，因而在某些情况下需要重新路由。重路由可 在网络资源不足时进行，能够有效地重新分配网络资源，但由于存在状态保存、 同步和开销等问题，使重路由变得很困难。 ( 6 ) 网络模型 不同的网络拓扑结构和o o s 业务流往往对q o s r 算法的性能造成很大的影响 包括网络直径、节点互联粒度、网络资源分布、路径长度分布、连接持续时间分 布、q o s 需求分布等参数。因此，q o s r 需要在以下两个方面与网络模型结合起来： 7 1 绪论博士论文 ( 1 ) 评价q o s r 算法和协议的性能、有效性；( 2 ) 针对实际网络设计高效的q o s r 算 法和协议，如对持续时间短的连接使用静态路由1 1 3 1 。由于i n t e m e t 缺乏“典型的” 网络拓扑结构和业务流，因此，如何使用适当的网络模型来指导q o s r 的研究， 将是进一步的研究方向。 ( 7 ) 与其他网络组件结合 今后的网络应该是q o s r 和尽力发送相结合的【1 4 】。网络的路由目标是最大化 资源效用，这包括尽可能地接纳更多的q o s 连接请求，同时最大化尽力发送业务 的吞吐量和相应速度。由于这两者是矛盾的，因此二者融入的过程会产生很多问 题。倒如，在有资源预留的链路空闲时，没有资源预留的链路却可能由于尽力发 送业务而造成拥塞。这种拥塞的链路仍然有可能因为尚未预留资源而接受q o s 请 求。此外，q o s r 算法必须与其他网络组件结合才能提供q o s 保证，包括状态收集、 资源预留、分组调度等，因此可以考虑这种结合过程对q o s r 算法和其他网络组件 的简化。 ( 8 ) 基于遗传策略的q o s r 的研究 目前基于遗传策略的q o s r 的研究，主要有两个问题：一是所使用的遗传算 法是“简单遗传算法”或称为“经典遗传算法”。而用简单遗传算法所求取的解 往往是“局部解”，而不是总体最优解，因而所求得的路径并不是最佳路径。二 是评价函数的设计缺乏代表性和科学性。而评价函数的优劣直接影响到对所选路 径的评价，有可能造成所选择的路径实际上并不是最优的，而被评价评为“最优 的”。另外所设计的评价函数只能解决一个特殊的问题，而不能解决一类问题。 1 4 本文主要工作 1 4 1 研究的问题 文章主要研究： ( 1 ) 为了解决简单遗传算法易收敛于局部解问题，应如何设计遗传算子才能 提高解的效率； ( 2 ) 如何将遗传算法应用到最短路径的求取中； ( 3 ) 在确保网络资源有效利用的条件下，如何利用f a l l b a c k 算法，设计q o s 路由算法； ( 4 ) 如何将d i j k s t r a 算法用于解决q o s 路由选择选择问题i ( 5 ) 在负载均衡条件下，如何应用遗传算法解决q o s 路由选择问题； 1 4 2 解决思路 ( 1 ) 以简单遗传算法为基础，对交叉算子进行重新设计，采用连续解探索的 方法，连续地反复利用简单g a 顺次得到的高适应度解的信息，在全局范围内探 索多个解( 候补) 。这样可以改善“个体的未成熟期出现收敛现象”，对解的探索 可以连续地进行，使得探索全局范围内的最佳解成为可能。 ( 2 ) 基于简单遗传算法，对遗传算子( 选择算法、交叉算法和变异算法) 进行 了重新设计，采用启发式策略。它能够根据种群进化情况，动态地调整遗传算子， 8 博士论文基于t c p i p 的q o s 路由算法的研究 维持种群的多样性，克服过早收敛及加快搜索速度。 ( 3 ) 基于f a l l b a c k 算法，在f a l l b a c k 算法中增加栈操作生成最佳路径，这样 每当更新路径时，从源节点到目的节点之间的所有可能路径不再废弃，而是暂时 保存在栈( s t a c k ) 中，将其用于多q o s 控制路径选择。 ( 4 ) d i j k s t r a 算法的复杂度是o ( n 2 ) ，如果能构造出一个评价指标，它能同时 满足多q o s 需求和网络负载分布均衡，将此指标定义为“距离”，使用d i j k s t r a 算法求取路径，则所求取的路径一定是最佳路径。 ( 5 ) 由于q o s 路由选择问题可以转化多目标决策问题，而将多目标遗传算法 用于解决多目标决策问题的关键是建立一个综合评价指标。因此，首先根据网络 拓扑模型生成一个搜索树，然后对该搜索树的根，枝和叶进行编码，基于网络负 载平衡及q o s 要求，建立综合评价指标。以此指标作为适应度函数，用多目标 遗传算法求取最佳路径。 1 4 3 主要工作与创新性 ( 1 ) 提出一种连续探索型遗传算法( g a w i t hr e l a ys e a r c hm e t h o d ，r s g a ) 。 简单g a 存在着许多局部解的“多峰性问题”。采用g a 解法进行标准遗传 操作时，有时会在个体的未成熟期出现收敛现象，或出现多目标最佳化的区域性 问题。而采用r s g a 算法，可以有效地扼制“个体的未成熟期出现收敛现象”， 解决“多峰性问题”，使得到的解为“全局最优解”。 ( 2 1 提出一种启发式遗传算法( g a w i t hi l l u m i n a t i o n ：i g a ) 简单g a 的遗传算子即：选择算子、交叉算予和变异算予的操作，都必须事 先确定选择策略、交叉率和变异率，自适应性较差，同时在解决复杂问题或解空 问很庞大时，会发生收敛速度慢或收敛于局部解情况。而采用i g a ，它能够根据 种群的进化情况，动态地调整遗传算子，维持种群的多样性，克服过早收敛并加 快了搜索速度，得到高品质解。 ( 3 ) 提出一种多q o s 路由最短路径算法f a l l b a c k + f a l l b a c k 算法中，路径选择是按照算法设计者根据经验排序的多q o s 来确定， 因此路径选择是经验性，所做的选择难以保证是最佳路径。另外f a l l b a c k 算法主 要以满足多q o s 路径选择为目的，并未考虑网络资源的有效利用。f a l l b a c k _ 中， 基于网络负载均衡，增加栈的操作，每当更新路径时，从源节点到目的节点之问 的所有可能路径不再废弃，而是暂时保存在栈( s t a c k ) 中，将其用于多q o s 控制 路径选择。 ( 4 ) 提出一种基于d i j k s t r a 策略的q o s 路由算法 为了能将d i j k s t r a 算法用于q o s 路由选择，构造出个综合评价指标，它能 同时满足多q o s 需求和网络负载分布均衡，将此指标定义为“距离”，使用d i j k s t r a 算法求取路径，则所求取的路径一定是最佳路径。 9 1 绪论l 埠士论文 ( 5 ) 提出一种q o s 路由多目标遗传算法 将q o s 路由选择问题转化多目标决策问题，通过设计一个综合评价指标，以 此指标作为适应度函数，采用多目标遗传算法解决多目标决策问题。 1 5 本文的主要结构 本文的具体内容安排如下： 第l 章，论述本文的研究背景，阐述现有的q o s 路由算法研究及其问题，并 对全文的研究内容作了前瞻性的介绍。 第2 章，它是全文的理论基础。分析了路由算法的特点、作用、分类，介绍 了经典路由算法，阐述了路由协议的演进及其发展，指出了经典路由协议的局限 性，并对q o s 路由算法的研究中的几个问题进行了讨论。 第3 章，通过对简单遗传算法g a 的结构和遗传算子的分析，指出其存在的 不足，给出了一种连续探索型遗传算法( g a w i t hr e l a ys e a r c hm e t h o d ，r s g a ) o 它以简单遗传算法为基础，对交叉算子进行重新设计，采用连续解探索的方法， 使得探索全局范围内的最佳解成为可能。通过对“多峰值问题”的仿真，说明了 算法的有效性。 第4 章，在进行一步分析连续探索型遗传算法r s g a 的基础上，对选择算 子、交叉算子和变异算法等遗传算予进行改进，基于启发式策略，提出了一种启 发式遗传算法。它能够根据种群进化情况，动态地调整遗传算子，维持种群的多 样性，克服过早收敛及加快搜索速度。通过对遗传子型进行特殊设计，可以解决 求取“多次通过同一个节点”或“必须通过指定节点”的最短路径问题。 第5 章，针对f a l l b a c k 算法的不足，通过在f a l l b a c k 算法中增加栈操作，提 出了种多q o s 路由选择算法f a l l b a c k + ，它可以满足多q o s 路由选择要求和网 络资源的有效利用。 第6 章，由于d i j k s t r a 算法不能直接用于q o s 路由选择。通过构造一个综合 评价函数，采用启发式策略，提出了一种基于d i j k s t r a 策略的q o s 路由多目标算 法。本章主要介绍这种算法及其仿真结果。 第7 章，对网络拓扑结构的进行形式化分析，给出了一般网络拓扑结构的数 学模型，建立了q o s 度量指标。通过将q o s 问题转化为多目标决策问题，以一 神综合评价指标作为评价函数，采用遗传算法解决q o s 路由选择问题。 第8 章，对全文进行小结。 l o 博l + 论文 基于t c p i p 的q o s 路由算法的研究 2 路由算法和协议 2 1 绪论 自从1 9 9 1 年美国参议院通过了建设信息高速公路的法案后，因特网进入了 迅猛发展的时期，并成为世界上最著名、最成功、连接范围最广的网际网。它由 大量的不同类型的网络通过网络互连设备连接而成。因特网采用自由、开放式的 网络组织方式，用统一的网络互连协议( t c p i p ) 和通用的地址体系保证网络的互 通。按入i n t e r a c t 的每个用户均可利用网络上的资源，也可以将自己的资源加入 i n t e r a c t 供所有用户享用。整个i n t e r a c t 自上丽下可分为三级网络结构：广域网、 城域网、局域网；可以将其称之为：一级主干网、二级主干网和三级用户网，其 示意图如图2 1 所示。 图2 1 in t e r n e t 的组织结构示意图 现有的i n t e r a c t 路由算法是基于矢量距离或链路状态 2 “。基于矢量距离的路 由是满足最小跳数的路由，而基于链路状态的路由实际上就是满足一定业务质量 的路由，其典型代表是开放最短路径优先算法( o s p f ) 。 i n t e m e t 中采用的路由选择协议属于自适应的( 即动态的) 、分布式路由选择协 议。i n t e m e t 采用分层次的路由选择协议，它将互连网划分为许多较小的自治系统 ( a u t o n o m o u ss y s t e m ：a s ) 。一个自治系统是一个互连网络，它自主地决定在本 系统内应采用何种路由选择协议。i n t c m e t 把路由选择协议划分为两大类：内部网 关协议i g p s ( i n t e r i o rg a t e w a yp r o t o c 0 1 ) 和外部网关协议e g p s ( e x