（应用数学专业论文）计算机网络中基于服务质量的路由算法研究.pdf

摘要摘要i n t e r n e t 高速网络中实时和多媒体应用业务的迅速发展，要求通信网络能提供高效的服务质量( q o s ) 支持，但是传统的“尽力而为”网络机制并不能满足q o s 通信的要求近几年的研究表明网络路由算法对实现网络质量服务具有非常重要的作用，因此q o s 路由算法日益成为网络研究的核心问题之一。本文首先介绍了q o s 路由算法的发展背景和研究现状，随后对目前可用于解决q o s 路由算法问题的思想方法做了较详细的分析和归纳；对传统d i j k s t r a 最短路算法编程实现之后，从三个方面对传统算法加以改进最后建立了一种q o s 路由数学模型和综合评价指标，并给出了适合该模型和综合评价指标的q o s 路由i ) i j k s t r a 最短路改进算法具体研究工作如下：( 1 ) 分析当前q o s 路由算法的发展现状和需求，讨论其网络模型和算法机制；然后从思想、具体步骤、示例和优缺点等方面较详细地分析和归纳了目前可用于解决o o s 路由问题的八种思想方法：( 2 ) 从最短路生成树和最小生成树两个方面对传统d i j k s t r a 最短路算法进行编程；从数据结构、搜索方向和路由信息的数据存储三个方面提出了改进思想，并比较其优缺点；( 3 ) 建立了一种q o s 路由数学模型和综合评价指标，基于该模型和综合评价指标，给出了针对带宽、时延、丢包率、成本和时延抖动及负载分布的q o s 路由d i i k s 衄最短路改进算法：关键词：计算机网络q o s 路由d i j k s t r a 最短路算法综合评价指标a b s t r a c tn la b s t r a c tw i t ht h ef a s td e v e l o p m e n to fr e a l - t i m ea n dm u l t i m e d i aa p p l i c a t i o n si nh i g h - s p e e di n t e r n e t , t h eh i g h - e f f i c i e n tq u a l i t y - o f - s e r v i c es u p p o r ti sr e q u i r e di nt h ec o m m u n i c a t i o nn e t w o r k b u tt h et r a d i t i o n a l ”b e s t - e f f o r t ”n e t w o r km e c h a n i s mc a nn o tg u a r a n t e et h eq o sc o m m u n i c a t i o n r e c e n tr e s e a r c hs h o w st h a tt h ea l g o r i t h mo fn e t w o r km u t i n gp l a y sa ni m p o r t a n tp a r ti np r o v i d i n gq u a l i t y - o f - s e r v i c eg u a r a n t e e s s ot h eq o s - b a s e dm u t i n ga l g o r i t h mb e c o m e so n eo ft h en u c l e a rn e t w o r kp r o b l e m s f i r s t ，t h i sd i s s e r t a t i o ni n t r o d u c e st h eb a c k g r o u n do ft h eo o s m u t i n gt e c h n o l o g ya n di t sp r e s e n tr e s e a r c hc o n d i t i o n ；t h em e t h o d st h a t 啪b eu s e dt os o l v et h ep r o b l e m so fq o s r o u t i n ga l g o r i t h ma r ea n a l y s e da n dc o n c l u d e di nd e t a i l ；t h e nt h et h e o r yf o u n d a t i o ni se s t a b l i s h e df o r t h en e t w o r kr o u t i n ga l g o r i t h m sw i t hq o sc o n s t r a i n t s ，t h et r a d i t i o n a ld i j k s t r a ss h o r t e s tp a t ha l g o r i t h mi sr e a l i z e df m mt w od i f f e r e n ta s p e c t s ；a n dt h r e ei m p r o v e dm e t h o d sa r ep r o p o s e df o r t h ed i j k s t r aa l g o r i t h m ；a tl a s t , t h em o d e la n ds y n t h e t i c a le v a l u a t i o ns y s t e mo fq o s r o u t n ga r ee s t a b l i s h e d ，a n dt h ei m p r o v e dm e t h o d so fr i j k s w a ss h o r t e s tp a t ha l g o r i t h mf o rm e e t i n gt h er e q u i r e m e n t sa r eg i v e na n dv a l j d a t c d t h em a i nw o r k sa r ef i s t e da sf o l l o w ：( 1 ) a n a l y z i n gt h ec u r r e n td e v e l o p m e n ta c t u a l i t ya n dr e q u i r e m e n to f0 0 s - r o u t i n g ；d i s c u s s i n gi t sn e t w o r km o d e la n dq o s r o u t i n ga l g o r i t h mm e c h a n i s m ；r e s p e c t i n gt h e i ri d e a s ，d e t a i l e ds t e p s , d e m o n s t r a t i o n sa n dr e l a t i v em e r i t s , t h ee x i s t i n gq o s r o u t i n gr e s e a r c hm e t h o d sb i ec l a s s i f i e da n ds u m m a r i z e d ；( 2 ) t h ed i j k s t r a ss h o r t e s tp a t ha l g o r i t h ma r er e a l i z e d 丘咖t w oa s p e c t s ；a c c o r d i n gt ot h ed a t as l r u c t u r e , s e a r c hd i r e c t i o n sa n dd a t as t o r a g eo fr o u t i n gi n f o r m a t i o n , t h r e ei m p r o v e dd i j k s t r aa l g o r i t h m sa r eg i v e n ；( 3 ) p u tf o r w a r dao o sr o u t i n ga l g o r i t h mm o d e la n dt h es y n t h e t i c a le v a l u a t i o ns y s t e md o t ；b a s e do nt h em o d e la n dt h es y s t e m ，t h ei m p r o v e dd i j k s t r aa l g o r i t h mi sp r o p o s e dr e g a r d i n gt ob a n d w i d t h , t i m e ，r a t i oo fl o s s p a c k e t ，c o s t , t i m ed i t h e r i n ga n dl o e dd i s t r i b u t i n g k e yw o r d s ：c o m p u t e rn e t w o r kq o s - r o u t i n gd i j k s t r a s h o r t e s tp t ha l g o r i t h ms y n t h e t i c a le v a l u a t i o ns y s t e m创新性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意申请学位论文与资料若有不实之处，本人承担一切相关责任本人签名：互轧日期：堂掣正关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其他复制手段保存论文( 保密的论文在解密后遵守此规定)本人签名：，丕i导师签名：鼗受日期：塑2 ：兰：鱼日期：! z ：! ：!第一章绪论第一章绪论本章首先衙要介绍了路由算法的基础知识，包括算法的决定因素，分类及度量。对。尽力而为。机制分析后，引出q o s 路由问题并阐述其研究现状，要求和实现难点第三节对q o s 路由模型展开讨论，介绍了q o s 网络模型的建立、路由过程，限制表度量以及算法分类，在算法分类中，重点针对q o s 单播路由问题，根据所解决的问题，对q o s 单播路由问题进行详细分类。重点讨论两类阳完全问题的经典算法最后列出了本文的内容提要和章节安排1 1 路由算法1 1 1 路由算法的决定因素路由1 1 】是把信息从源穿过网络传递到目地的行为路由技术由两项最基本的活动组成，即确定最优路径和传输信息单元( 数据包) 其中，数据包的传输和交换相对较为筒单和直接，而路由的确定则更加复杂一些路由算法【2 】的决定因素如下：( 1 ) 最优化：指路由算法选择最佳路径的能力( 2 ) 简洁性：算法设计简洁，利用最少的软件和开销，提供最有效的功能一( 3 ) 坚固性：路由算法处于非正常或不可预料的环境时，如硬件故障、负载过高或操作失误时，都能正确运行由于路由器分布在网络联接点上，所以在它们出故障时会产生严重后果最好的路由器算法通常能经受时间的考验，并在各种网络环境下被证实是可靠的( 4 ) 快速收敛：收敛是在最佳路径的判断上所有路由器达到一致的过程当某个网络事件引起路由可用或不可用时，路由器就发出更新信息路由更新信息遍及整个网络，引发重新计算最佳路径，最终达到所有路由器一致公认的最佳路径收敛慢的路由算法会造成路径循环或网络中断( 5 ) 灵活性：路由算法可以快速、准确地适应各种网络环境例如，某个网段发生故障，算法要能很快发现故障，并为使用该网段的所有路由选择另一最佳路径1 1 2 路由算法的分类( 1 ) 静态与动态静态路由是开始路由前由网管建立的表映射这些映射自身并不改变，除非网2计算机网络中基于服务质量的路由算法研究管去改动，所以只适于网络传输状态比较简单的环境使用静态路由的算法较容易设计，在网络通信可预测及简单的网络中工作得很好九十年代以来主要的路由算法都是动态路由算法，通过分析收到的路由更新信息来适应网络环境的改变若信息表示网络发生变化，路由软件就重新计算路由并发出新的路由更新信息这些信息渗入网络，促使路由器重新计算并对路由表做相应的改变动态路由算法可在适当的地方以静态路由作为补充例如，最后可选路由，作为所有不可路由分组的去路，保证了所有的数据至少有方法处理( 2 ) 单路径与多路径一些复杂的路由协议支持到同一目的的多条路径与单路径算法不同，这些多路径算法允许数据在多条线路上复用多路径算法的优点是可以提供更好的吞吐量和可靠性( 3 ) 平坦与分层在平坦的路由系统中，每个路由器与其它所有路由器是对等的；在分层次的路由系统中，一些路由器构成了路由主干，数据从非主干路由器流向主干路由器，然后在主干上传输直到它们到达目标所在区域路由系统通常设计有逻辑节点组，称为域、自治系统或区间在分层的系统中，一些路由器可与其它域中的路由器通信，其它的则只能与域内的路由器通信在很大的网络中，可能还存在其它级别，最高级的路由器构成了路由主干分层路由的优点是它模拟了多数公司的结构，从而能很好地支持其通信多数的网络通信发生在小组中( 域) 因为域内路由器只需要知道本域内的其它路由器，它们的路由算法可以简化，根据所使用的路由算法，路由更新的通信量可以相应地减少( 4 ) 主机智能与路由器智能源路由系统中，路由器只作为存贮转发设备，无意识地把分组发向下一跳其它路由算法假定主机对路径一无所知，这里的路由器基于自己的计算决定通过网络的路径前一种系统中，主机具有决定路由的智能，后者则为路由器具有此能力主机智能和路由器智能的折衷实际是最佳路由与额外开销的平衡主机智能系统通常能选择更佳的路径，因为它们在发送数据前探索了所有可能的路径，然后基于特定系统对“优化”的定义来选择最佳路径然而确定所有路径的行为通常需要很多的探索通信量和很长的时问( 5 ) 域内与域问一些路由算法只在域内工作，其它的则既在域内也在域间工作这两种算法的本质是不同的，其遵循的理由是优化的域内路由算法没有必要也成为优化的域间路由算法( 6 ) 链接状态与距离向量链路状态算法( 也称最短路径算法) 发送路由信息到互联网上所有的节点，然第一章绪论而对于每个路由器，仅发送它的路由表中描述了其自身链路状态的那一部分距离向量算法( 也称b e l l m a n - f o f d 算法) 则要求每个路由器发送其路由表全部或部分信息，但仅发送到邻近节点上从本质上说，链路状态算法将少量更新信息发送至网络各处，而距离向量算法发送大量更新信息至邻接路由器由于链路状态算法收敛更快。因此它在一定程度上比距离向量算法更不易产生路由循环，但另一方面，链路状态算法要求比距离向量算法有更强的c p u 能力和更多的内存空间，因此链路状态算法将会在实现时显得更昂贵一些除了这些区别，两种算法在大多数环境下都能很好地运行两种算法的差别归结为表1 1 ，以此作为选择路由协议的技术依据表1 1 距离向量算法与链路状态算法的比较距离向量算法链路状态算法不知道整个网络的拓扑结构知道整个网络的拓扑结构在相邻路由器路由信息的基根据网络拓扑结构寻找和计础上计算路由的向量距离算最短路径收敛速度慢收敛速度快路由器路由表只发送相邻的路由嚣篚i l s p 发送给制定的一路由器个或多个( 或所有) 路由器( 1 ) 路径长度( 最常用) ：一些路由协议允许网管给每个网络链接人工赋以代价值，这时的路由长度是所经过各链接的代价总和其它路由协议定义了跳数，即分组从源到目的的路途中必须经过的网络产品，如路由器的个数( 2 ) 可靠性：在路由算法中指网络链接的可依赖性( 以位误率描述) 有些网络链接可能比其它的失效更多，网路失效后，一些网络链接可能比其它的更易或更快修复任何可靠性因素都可在给可靠率赋值时计算，通常由网管给网络链接赋值( 3 ) 路由延迟：指分组从源通过网络到达目的所花时间很多因素影响延迟，包括中间的网络链接的带宽、经过的每个路由器的端口队列、所有中间网络链接的拥塞程度以及物理距离延迟是多个重要变量的混合体，是较常用且有效的( 4 ) 带宽：指链接可用的流通容量在其它所有条件都相等时，1 0 m b p s 的以太网链接比6 4 k b p s 的专线更可取虽然带宽是链接可获得的最大吞吐量，但是通过具有较大带宽的链接做路由不一定比经过较慢链接路由更好例如，如果一条快速链路很忙，分组到达目的所花时间可能要更长( 5 ) 负载：指网络资源，如路由器的繁忙程度它可用很多方面计算，包括c p u 使用情况和每秒处理分组数持续监视这些参数本身也很耗费资源4计算机网络中基于服务质量的路由算法研究( 6 ) 通信代价：重要的m e t r i c ，尤其是有些公司可能关心运作费用甚于性能即使线路延迟可能较长，也宁愿通过自己的线路发送数据而不采用昂贵的公用线路1 2q o s 路由的提出1 2 1 尽力而为的口网络在以往的实际应用中网络服务提供商和企业一般建造并维护适合各自应用的网络，但是，现在越来越趋向于将这些网络融合为单一的基于分组的i p 网络当前，应用最广的i p 网络就是i n t e r a c t ，其技术基础是分组交换( 或包交换) ，即通过多个网络结点逐段转发数据分组如果通路存在。分组就可以从源端传送到耳的端j p 网络不能保证任何发送的分组最终都能到达其目的地但是，终端的主机可通过一定的协议对这种情况进行处理( 如重发丢失包机制) 这就是“尽力而为 ( b e s te f f o r t ) 网络“尽力而为”服务不加区别地为每个应用提供数据传输服务，缺乏对网络资源有效的分配和管理当网络负载较轻时，各个应用能得到足够的资源，传输服务质量尚可；但随着负载增加，各种应用的行为将表现为无序地竞争网络资源，造成网络资源的不合理占用，导致服务质量不断恶化；另外，“尽力而为”服务对传输质量没有严格的保证，表现为端到端延迟、数据包丢失率等性能随着网络负载的变化而波动随着网络服务不断的增加和网络应用的多元化，传统寻找路由的概念已经开始向满足服务质量路由转化嘲新的路由器不仅起到寻径和转发的功能，多种控制策略、传输管理都是要为保证服务质量来设计和运行的速度更快、服务质量更好、管理更加容易的新路由器体系及其上的协议系统才是路由领域今后发展的方向1 2 2 服务质量问题所谓的服务质量i 卅( q u a l 埘o fs e r v i c e ) 是指发送和接收信息的用户间，以及用户和传输信息的服务网络之间关于信息传输的质量约定它用于定义网络给不同形式的流量提供不同级别的服务保障的能力在传统网络中，服务提供方会因为很多的原因无法为用户提供他们所承诺的信息，这就构成了q o s 问题q o s 问题主要分为两类：网络相关和网络无关引起网络无关q o s 问题的原因主要是用户所需要的服务的负载数据和人为的错误；引起网络相关q o s f a 题的主要原因是设备错误、接入能力不够以及不平衡流量导致的拥塞可见q o s 并不是网络中某一个设备或者某一方面能力的体现，而是网络服务的综合能力q o s 路由其主要目标包括以下两点：( 1 ) 为每一个接纳i 筝j q o s ) l k 务连接请求，找到满足其q o s 宝；求的可行路径( 组播树) ；( 2 ) 优化全局资源利用率，平衡网络负载，从而最大化网络接受其他q o s 请求的能力【5 1 图1 i 和第一章绪论51 2 分别表示了q o s 问题的组成和路由流程图1 1o o s 问题的组成图1 2 , 3 研究现状图1 2o o s 路由流程目前网络研究主要通过两个途径提高q o s ：一个是节点控制；另一个是整网或局部网络控制前者在单节点或单链路完成，主要控制业务对单节点共享资源的占用。包括共享的链路、缓存区、处理器资源它的主要策略包括：业务流整形、业务调度、节点缓冲区管理，整网或局部网络控制，通过对路由与信令的控制达到对业务流或业务连接在网络中传输的直接控制，因路由直接关系到网络性能，故0 0 $ 路由成为解决q o s 问题的一项关键技术与传统的尽力而为的路由过程相比，q o s 寻路过程涉及两个方面的问题：一是依据哪些m c 耐c 作为寻路标准，简称度量参数选择问题：另一个是在寻路标准设定后，如何找到满足业务需求的路径，并保证数据经由选定路径传输到目的节点，简称寻路问题路由信息交互过程中，由于链路传输延时的存在，每个节点获得的其他节点状态信息总具有一定的不准确性，这些不准确性将会影响q o s 路由算法的有效性，因此，路由信息不准确的问题是o o s 路由中的一个主要问题度量参数选择、寻路和路由信息不准确问题是q o s 路由中的研究重点1 2 4q o s 路由的实现难点嘲( 1 ) n p - c o m p l e t e l n l 题：同时对两个以上相互独立的参数提出要求时，这个问题就是一个n p 完全的问题，实时应用往往会对延时、延时抖动、带宽、丢失率、业务代价等多个参数同时提出性能要求，例如，实时多媒体业务会对延时和延时抖动同时提出要求，这些参数相互独立时，选择满足多个参数限制的路由就成为n p 完全问题，n p 完全问题直接关系到路由算法的可实现性6计算机网络中基于服务质量的路由算法研究( 2 ) 多业务并存：同时承载多种q o s 要求不同的业务时，网络性能优化困难、扩展困难，尤其是q o s 和尽力而为b e s t e f f o r t 业务独立共存时，很难确定最优操作点( 3 ) 节点状态信息的存储量大：o o s 路由中，节点需记录的状态参量将增多，如状态信息的存储量随网络节点个数的增加而指数性增加，将限制网络的扩展( 4 ) 信息不准确1 7 ：传输负荷的抖动、新连接的加入等都可能导致网络状态变化，这些变化因素直接影响全网状态信息的准确性，同时也直接影响算法韵性能1 3 1q o s 路由问题的网络模型1 0 q o s 路由q o s 网络的拓扑结构和资源容量可以抽象为一个加权图( y ，e ) ，其中y 代表网络中的交换设备，即网络节点集，e 代表传输线路，即双向链路集对于任意的网络节点h ，p ，如果存在到v 的链路p 一n ， ，) ，一定存在另一条v t i j u 的链路e ，- ( y , u ) 按照链路的对称性，网络可以分为对称网络和非对称网络定义1 1 对称网络在网络( y ，e ) 中取任意链路( u , 1 2 ) ，对于所有的q o s 度量，存在所( u , p ) 一小( y ，) ，则称该网络为对称网络定义1 2 非对称网络在网络( y ，e ) 中，如果存在一条链路( u , p 1 满足，l 醅， ，) ，m ( 1 ，h ) ，则称该网络为非对称网络上述的m ( ) 表示任何q o s 度量，如：代价s f ( ) 、时延如幻，( ) 等，下文将介绍由网络模型【”j 知，网络由节点和链路两要素组成，对其的分析也应包括这两大要素为突出问题本质，本论文对网络模型进行合理简化：假设存在一种分配策略，它能将网络节点的o o s 度量合理分配到对其相邻链路的度量上，则研究可以只考虑网络链路特性而省略网络节点特性大多数实时多媒体网络非对称，所以网络链路应由两条有向边表示但为了便于理解，常常使用对称网络模型以减少链路的数量1 3 2q o s 路由的限制和度量q o s 路由中算法复杂度【1 6 】关系到算法的可实现性度量参数选择【8 】直接关系到算法复杂度问题另外，网络支持的度量参数反映并影响路由选择算法的性能支持的度量参数越多，越能有效保证提供给接入业务的服务质量，但是路由选择算法复杂度增大。存在完全满足参数限制的路由的概率减小，业务接入率降低q o s 是应用业务对网络传输服务提出的组可度量的要求，主要包括代价、带宽、端到端时延、包丢失率、时延抖动等网络在传输相应的数据业务时，必须满足这组要求o o s 需求可以通过一个约束集t 9 1 来描述，包括链路约束、路径约束或树约束第一章绪论7链路约束：从源节点到目的节点的每条链路的约束，是对路由选择所使用链路的一种限制例如，带宽约束要求链路上的带宽必须大于或等于某个预定义的值注意。链路限制一般是凹性或凸性限制条件路径约束：一条路径上的端到端q o s 要求树约束：对组播中整个组播树的约束，分为两种：1 ) 对组播树中从源节点到目的节点的每条路径上性能度量组合值的约束例如，对组播树时延的约束就是对树中从源节点到目的节点路径中最大时延的约束2 1 对从同一源节点到任意两个目的节点路径上的性能度量的不同组合值的约束例如，目的节点之间的时延抖动约束定义为从相同源节点到任意两个不同目的节点路径上的端到端时延差异定义1 3 度量( m e t r i c ) 在网络n ( v ，e ) 中，令链路p e 具有一组有序数列( 啦，m ) 作为e 的属性，则( m ，吃，) 称为链路e 的度量，也称权值( w e i g h t ) 设n ( v ，e ) ：网络，疋：正实数集，r + ：非负实数集，e e e ：任意一条链路，则：代价s f ( e ) ：e _ r时延d e a y ( e ) ：e - 足带宽b a n d w i d t h ( e ) ：e r +时延抖动如匆j i t t e r ( e ) ：- 彤丢包率p a c k e t l o s s i e l ：e f“j 多样的度量值可以更精确地描述一个网络在路由方面的特性，然而在多个限制条件下找到一条合适的路径本身就存在很大的难度由于各种网络应用对资源需求的不同而使这个问题在q o s 路由中显得更加复杂路径计算的复杂性主要由这些度量值的合成规则所决定。应用最广的是下面3 种合成规则：对于路径弓( “，) - ( m ，i ，j ，k ，1 ，) ，用m ( i ，) 表示对应链路f 到j 的性能量度，则o ) s 路由约束可以按性质分为以下三类：1 可加性：若m ( u ，y ) - m ( “，f ) + 小( f ，) + j ，l ( ，f ) + + m ( 七，v )( 1 1 )则称约束值m 具有可加性，则度量由传输通道中所有链路的特性共同决定，如时延、时延抖动、代价和转发跳数等2 ) 乘积性：若臃( “，y ) - m ( u ，f ) 小( f ，j ) x m ( j ，f ) x m ( k ，v )( 1 2 )则称约束值m 具有乘积性，即度量为所有链路对应度量的乘积，如丢包率等3 )极值性：若小( “，y ) 一m i n 胁( “，f ) ，脚( f ，) ，m ( j ，f ) ，m ( k ，v ) ( 1 3 )则称约束值m 具有极值性。也称为凹性若约束值m 具有凸性，则一毡砷一n 戤 一玛f ) ，叫珐碱五班一积南订 度量由传输通道中的瓶颈决定，即此度量仅与路径上的某个瓶颈链路的o o s 度量有关，如剩余带宽、剩余缓存空间、链路速率等等前面说提到的路径约束和树约束典型为加性或乘性代价1 3 3q o s 算法的分类1 3 3 1 按网络状态信息保存方式及路由搜寻方式区分8计算机网络中基于服务质量的路由算法研究1 1 集中式源路由源路由采用集中处理的方式发出路由请求时可立即获取预先存在的路由信息，无需在各网络节点间进行信息交换但它需要网络中每个节点上都维持一张有关网络全局链路状态的图另外，经过计算的路径是不含回路的总之，这是一种简单明了、易于实施评估检查和升级维护的路由计算方法与解决属于n p - 完全问题的分布路由启发试探算法相比，它很容易实施但也存在一些问题即：( 1 ) 为维持整个网络通信链路的状态信息必须进行高频率的状态刷新，给网络造成了负载；( 2 )由于不可避免地存在着刷新延迟，因此存在着状态信息滞后的问题2 ) 分布式路由分布路由的路径计算是激励式的，即当有路由请求时，它不会马上获取到路由信息，需要一个路径搜索延迟但该类路由选择和优化都是基于局部状态信息的，不需要像源路由那样为网络所有节点都维持一张链路状态表因此它能够更好地适应网络规模，但计算复杂度较高，还存在着收敛和相邻节点间状态刷新通信开销的问题同时，在多个方向上并行搜索多个可行路径，增加了搜索的成功率当链路状态信息由于广播延迟而造成不同节点的有关链路状态不一致时，回路将发生，从而增加了网络带宽的消耗。另外，分布路由不同于源路由，由源节点独自完成路由的计算工作，而是由多个节点共同完成路由的计算，减轻了源节点的计算开销3 1 层次路由引入层次路由的目的是为了适应两络规模在层次路由中。它把一组网络节点浓缩成一个逻辑节点，这样每个网络节点所维持的状态表大大简化，减少了对存储容量的需求，因此基于简化了的节点状态表就可对逻辑节点进行源路由操作，同时它也兼顾了分布路由的一些优点然而，由于对网络节点状态进行了简化，存在着逻辑节点状态并不能够精确地表达被浓缩的网络节点的状态信息，从而导致负面效应在有多个q o s 服务品质要求的情况下，这种情况会变得更加复杂1 3 3 2 路由服务的节点范围区分1 ) 单播路由对于网络( k 冒) ，指定路由源节点s e v ，路由目的节点t e v ，o o s 约束集c 以及优化目标，q o s 单播路由就是找出满足给定q o s 约束条件c 的j 到f 的最佳可行路径p ( s ，f ) 对诸如剩余带宽、剩余缓存空间等服务质量的度量，路径的状态取决于瓶颈链路的状态由此定义两类基本的路由选择问题：链路优化路由选择，如：带宽优化路由选择，是寻找在瓶颈链路上具有最大带宽的一条路径；链路约束路由选择，如：带宽给路由选择，是寻找瓶颈带宽高于要求值的一条路径链路可将d i j k s t r a 算法或t h 函r m f o r d 算法稍作修改来解决可减化为对其它服务质量的度量。如延迟差、代价等，路径状态取决于路径上所有链路的组合状态同样由此可定义两类基本第一章绪论9的路由选择问题：路径优化路由选择，如：最小代价路由选择，是寻找总代价最小的一条路径 路径约束路由选择，如：延迟约束路由选择，它是寻找延迟局限于一个要求的值之内的一条路径。 和可由d i j k s t r a 或b e l l m a n f o r d 算法直接解决单播路由：寻找最佳可行路径基本o o s 路由问题组合o o s 路由问题链路优化路由( 例如。带宽优化路由)p 问题链路约束路由( 例如。带宽约束路由)p 问题路径优化路由( 例如。最小代价路由)p 问题路径约束路由( 例如，时延约束路由)p 问题r 。_ - - 。_ 。_ 、；i 链路约束一链路优化路由( 倒i如。带宽约束缓冲优化路由)p 问题链路约柬一路径优化路由( 例如，带宽约束最小时延路由)p 问题多链路约束路由( 例如，带宽及缓冲约束路由)p 问题链路约束一路径约束路由( 例如带宽、时延约柬路由)p 问题路径约束一链路优化路由( 例如时延约束带宽优化路由)p 完全问题路径约束一路径优化路由( 例如。时延约束最小代价路由)n p 完全问题多路径约束路由( 例如。时延及时延抖动约束路由)n p 完全问题p 问题：多项式问题( p o l y n o m i a l )n p 完全问题：非确定多项式完全问题f n o n d e t e r m i n i s t i cp o l y n o m i a lc o m p l e 旧图1 3q o s 单播路由问题由此，q o s 单播路由首先涉及上述四种基本的q o s 路由问题 有关q o s1 0计算机网络中基于服务质量的路由算法研究单播的组合路由问题均由上面四种基本问题演化而来，如图1 3 所示由图可知，在o o s 单播路由中存在两类n p 完全的路由问题：路径约束路径优化路由问题和多路径约束路由问题这两种问题是基于以下两个基本假设：1 ) q o s 度量相互独立；2 ) q o s度量值是实数或极大整数若玎个q o s 度量中n 一1 个是有界整数，则n p 完全问题可通过扩展的d i j k s t r a 或b e l l m a n f o r d 算法转化为p 问题目前的研究结果也能证明，若所有的o o s 度量与其中任何一个相关，算法也可以在多项式时间内求解例如，在使用加权公平排队w f q 调度的函数中，最差情况的时延和时延抖动是网络带宽的函数，因此，时延及时延抖动约束路由问题可在多项式时间内求解表1 2 列举了近几年提出的一些典型的q o s 单播路由算法( 均用作者姓名表示)同时也列举了算法解决的路由问题、路由策略及计算的时问复杂度和状态信息表1 2q o s 单播路由算法算法解决的问题路由策略时间复杂度状态信息c h e n - n a n h r s t e d l带宽、代价约束源路由o ( x n e )全局带宽约束源路由o ( n l o g n + e 1全局m a - s t e e n k l s t e多链路约束源路由d ( b l e )全局w a n g - c r o w c r o f l带宽、时延约束源路由o ( n l o g n + e )全局全局带宽约束源路由o ( n l o g n + e 1( 不精确)g u e r i n - o r d a全局时延约束源路由多项式( 不精确)j u t t n e r时延约束最小代价源路由o ( e 2 l 0 9 4 e 1全局k o t k m a z多路径约束路径优化源路由多项式全局h e r e多约束路径源路由o ( 砌l o g ( 肠+ k ) )全局崔勇多约束路径源路由o ( k ( e + n l o g n ) )全局王颖时延约束最小代价源路由o ( n 2 + p n 2 )全局w a n g - c r o w c r o f t带宽优化分布式o ( n e )全局s a l a m a时延约束最小代价分布式d ( 雄3 )全局s u n时延约束最小代价分布式o ( n )全局0 r d a多约束路径优化分布式多项式全局全局o r d a时延约束最小代价分布式多项式吕国英时延、带宽约束分布式d ( 订3 )全局其中，拜表示网络节点数，e 表示链路数，k 为多约束路径的约束个数，k 为第k条最短路径算法中的参数。p 为路径的个数第一章绪论1 1b 组播路由算法给定带权图g 一( 矿，) ，源节点s ，目的节点集m ，q o s 约束集c 以及优化目标函数0 q o s 组播路由就是以网络拓扑结构和网络状态为基础，构建一棵组播树z ，包含源节点和所有的目的节点，并满足给定的约束条件c 以及优化目标函数d 根据树约束链路约束和目标函数，组播路由问题可分为以下十二大类：链路约束问题：规定一个链路约束来构造可行组播树例如。带宽约束路由多链路约束问题：规定两个或多个链路约束来构造可行树例如。带宽和缓冲约束路由树约束问题：规定一个树约束来构造可行的组播树例如，时延约束路由多个树约束问题：规定两个或多个树约束来构造可行的组播树例如，时延和时延抖动约束路由链路及树约束问题：规定一个链路约束和一个树约束来构造可行的组播树例如，时延和带宽约束路由链路优化问题：使用一个链路优化函数来构造一个优化的组播树例如，组播树中树链路上的带宽最大树优化闯题：使用一个树优化函数来构造一个优化的组播树例如，组播树的总代价最小这就是著名的s t e i n e r 稠i 问题 链路约束链路优化问题：规定一个链路约束并使用一个链路优化函数来构造一个优化的组播树并实现约束例如，带宽约束缓冲优化问题链路约束树优化问题：规定一个链路约束并使用一个树优化函数来构造一个优化的组播树并实现约束例如，带宽约束s t e i n e z 树问题树约束链路优化问题：使用一个树约束和链路优化函数来构造一个优化的组播树例如，时延约束带宽优化问题 树约束树优化问题：使用一个树约束和树优化函数来构造一个优化的组播树例如。时延约束s t e i n e r 树问题 链路约束及树约束树优化问题：使用链路和树约束和树优化函数来构造一个优化的组播树例如，带宽和时延约束的树优化问题问题和容易处理：可通过从网络拓扑中删除不合要求的链路来满足链路约束w a n g 和c l r o w c r o f i i 己证明寻找一条路径使之满足两个或多个相互独立的可加性或可乘性的约束条件以及它们的任意组合是n p 完全问题只有凹性约束和其它可加性、可乘性约束的组合问题是容易处理的故问题和在多项式时间内可解，而问题是n p 完全问题s h a c h a m 提出了解决问题的一个多项式时间复杂度的算法若从网络拓扑中删除不满足约束条件的链路，则问题和可转化为问题，故它们在多项式时间内也可解问题和问题， 以及 已被证明是n p 完全闯题1 2计算机网络中基于服务质量的路由算法研究1 4 本文主要工作本文是作者攻读硕士学位期间在刘三阳教授的指导下完成的部分工作，主要是关于o o s 路由算法方面的研究具体内容如下：本论文在介绍了q o s 路由算法研究背景和基本概念后，对当今已有的可用于q o s 路由研究的思想进行系统总结，把解决路由问题的方法划分成七类，除了叙述每种策略的具体工作过程及其优缺点，还进行了详尽的分析比较并举例说明，弥补了当前诸多文献中只将注意力集中在某一个路由策略内的不足在对基于d i j k s t r a 算法的q o s 路由分析时，从最短路生成树和最小生成树两方面编程实现了经典d i j k s t r a 算法，并提出一种综合评价体系，得到了基于d i j k s t r a 的q o s 路由算法m o q r a d 最后提出了该领域进一步研究的有关方向本论文共分三章，具体章节如下安排：第一章，概述了路由算法的基础知识，从尽力而为服务中引出o o s 研究，对q o s 的网络模型，限制和度量以及算法分类进行介绍：第二章，详细分析并系统总结了q o s 路由目前八种的研究方法，并着重介绍了基于图论的q o s 研究所需要的相关基础知识；第三章，在对传统的d i j k s t r a 算法深入分析的基础上，对已有算法进行改进，最后从q o s 路由算法的综合评价指标入手，给出一种基于d i j k s t r a 最短路改进的q o s 路由算法m o q r a d ，并进行了详细分析最后为结束语概言之，针对q 0 s 路由算法，本文的研究工作有以下几点：( 1 ) 分析当前q o s 路由算法的发展现状和需求，讨论其网络模型和算法机制；然后从思想、具体步骤、示例和优缺点等方面较详细地分析和归纳了目前可用于解决q o s 路由问题的八种思想方法：( 2 ) 从最短路生成树和最小生成树两个方面对传统d i j k s t r a 最短路算法进行编程；从数据结构、搜索方向和路由信息的数据存储三个方面提出了改进思想，并比较其优缺点：( 3 ) 建立了一种q o s 路由数学模型和综合评价指标，基于该模型和综合评价指标，给出了针对带宽、时延、丢包率、成本和时延抖动及负载分布的o o s 路f h d i j k s b a最短路改进算法第一二章o o s 路由问题解决方法第二章q o s 路由问题解决方法本章是在大量阅读相关文献的基础上，对已有的路由研究方法遂一进行分析首先给出路由算法复杂度理论中有关多项式时间、p 类问题以及n p 一完全问题的概念，而后对各种路由策略从宏观上鸟瞰综述，给出其具体工作过程及优缺点，并与相应类似的路由策略进行较详尽的分析比较，弥补了当前诸多文献中只将注意力集中在某一个路由策略内的不足，据了解，这是以往文献未曾进行的工作最后，对基于图论知识的路由策略展开讨论，为下章研究做好理论准备2 1 基本概念2 1 1 多项式时问不同的算法具有不同的时问复杂度函数，计算机界公认的一种简单的区别就是多项式时间算法和非多项式时间算法所谓多项式算法时间可以如下定义【堋：定义2 1 只要存在一个常数c 使得对所有的弗急。都有i ，( 以) i s f l g ( 厅x ，那么称函数，( 押) 是d ( g ( n ) ) 的多项式时间算法定义为时间复杂性函数是d ( p ( 一) ) 的算法，其中p 是一个多项式函数，n 用来表示输入长度-，由定义2 1 可知，给定组合优化闯题c o p ( c o m b i n a t o r i a lo p l i m i z a t i o np r o b l 锄) 二进制编码的长度n ，如果解决长度为n 的任意一个实例所需的最大计算时间受约束于开的某个多项式，那么我们就可以得出结论，即此类c o p 问题是多项式可解的，而其对应的算法就是多项式算法如果七是所有上述实例中最大的指数项。那么我们称上述c o p 问题是d f 矿l 时间可解的 2 0 1 相反，不具有上述约束性质的算法称为非多项式时间算法( 如指数时间算法) 2 1 2p 问题与n p 一完全问题假定存在一个有待解决的问题q ，那么它的每一个解s 都可以看作是问题q 的一个实例( h 略t 卸c c ) p 表示一类可以在多项式时间进行求解的问题，即有p q ，在该类问题的求解中存在着一个算法，该算法针对q 中的每个实例。用多项式时间判定问题的解是否存在而n p 则表示不能够用多项式时间进行求解的一类问题，在该类问题的求解过程中存在着一个算法，该算法针对q 中的每个实例，用多项式时间可以核实问题的解存在是正确的在复杂性理论中，术语n p 一完全问题是指用任何已知的多1 4计算机网络中基于服务质量的路由算法研究项式时间算法都无法解决的问题2 2 解决q o s 路由问题采用的方法本节基于相关文献，弥补当前诸多文献中只将注意力集中在某一个路由策略内的不足，从具体工作过程着手，对已有的可用于q o s 路由研究的思想方法进行了系统总结，对其性能做了比较分析2 2 1 人工神经网络a n n ( a r t i f i c i a ln e u r a ln e t w o r k )用神经网络【矧解决优化组合问题，即寻找问题的最优解，是神经网络应用的一个重要方面1 2 1 趋2 3 1 通过对神经网络能量函数的分析，可以得到这样的启发：既然网络的能量函数在网络的状态按一定规则变化时，可以自动地朝着其稳定的平衡点即极小点运动，并将最终收敛于极值点如果把一个需要求解问题的目标函数转换为网络能量函数，把问题的变量对应于网络的状态，这样当网络的能量函数收敛于极小值时