（计算机系统结构专业论文）具有分类服务功能的路由选择算法研究.pdf

中文摘要 基于肝l s 流量工程的路由算法研究有很多，但是一般都只考虑了有带宽要 求的业务。传统的流量工程路由算法，如p b r 、d b r 、m i r a 等，都是针对有带 宽保证业务的路由选择算法，即都只能处理有确定带宽要求的q o s 业务，没有涉 及b e s te f f o r t 业务。而实际上，网络中占大多数的业务是b e s t - e f f o r t 业务。 基于d i f f s e r v 的流量工程方案( d s - t e ) 提供了多服务功能，但要求首先由系统 管理员在每条链路上手工为不同服务类划分链路带宽，然后使用基于约束的最短 路( c s p f ) 算法为不同类的业务请求选择路由；划分带宽的依据或是管理员的经 验，或是根据每条的服务要求；这往往会导致不合适的带宽分配，而且忽略了网 络整体性能。因此，本文提出了一种具有分类服务功能的路由选择算法。该算法 从流量工程优化目标出发离线计算可供源目的节点之间传输业务使用的路径集 合；当网络业务到来时，在线路由算法采用不同的选路策略分别为q o s 业务和 b e s t - e f f o r t 业务选路，即为q o s 业务请求选择跳数少( 最短) 且可用带宽与q o s 带宽要求最为接近的路径，或称为最窄的路径，以满足其带宽和延迟性能要求， 同时避免了使用最宽的路径时，因带宽要求不均匀而导致不能满足未来的较大的 带宽需求的问题；为b e s te f f o r t 业务选择剩余带宽较大的路径，以达到负载平衡 和最小化拥塞的效果。 利用n s 一2 仿真结果表明，与c s p f ( c o n s t r a i n e ds h o r t e s tp a t hf i r s t ，基于约束 的最短路优先) 相比，使用本文提出的流量工程框架，在首先保h 正q o s 业务传输 带宽和网络接受比要求的同时，大幅度的提高了b e s t - e f f o r t 业务的吞吐量。同时 采用预留带宽机制，实现不“莽撞”拒绝请求。 关键词l 衄l s 流量工程在线路由离线优化计算q o s a b s t r a c t t h e s ea r em a n yr o u t i n ga l g o r i t h m sb a s e do nm p l st r a f e ce n g i n e e r i n g , al a r g e n u m b e ro fw h i c ha r eo n l ys e l e c tp a t h sf o rt h eu a m cw i t ht h eb a n d w i d t hr e q u e s t t r a d i t i o n a lt t a 伍ce n g i n e e r i n ga l g o r i t h m s , e g p b r , d b l lm i r a , a r ea l lr o u t i n g s e l e c t i o na l g o r i t h m sw i 也b a n d w i d t hg u a r a n t e e v i z t h e yc a l lo n l ym a n a g et h eq o s o p e r a t i o nw i t ht h eb a n d w i d t hr e q u e s t , a n dn o td e a lw i t ht h eb e s t - e f f o r to p e r a t i o n a c t u a l l y , ag r e a tn u m b e ro fo p e r a t i o n sa r eb e s t - e f f o r to p e r a t i o ni nn e t w o r k s 1 1 舱 f r a n ce n g i n e e r i n gs o l u t i o n ( d s t e ) b a s e do nd i f f s e r vp r o v i d e sd i f f e r e n t s e r v i c e sf u n c t i o n , b u ti tn e 2 d ss y s t e ma d m i n i s t a t o rt os e l e c tb a n d w i t hf o re a c hs e r v i c e f i r s t , t h e ni i sc s p fa l g o r i t h mt 0s e l e c tr o u t i n gp a t hf o rs e r v i c e s ；h o wt om a k et h e p a t hi sb a s e do nt h es y s t e ma d m i n l s t a t o r se x p e r i e n c eo rt h ed e m a n do fe a c hs e r v i c e t m sm e t h o dc a nn o tb a l a n c et h ew h o l eb a n d w i d t ho f t h en e t w o r kt oe a c hs e r v i c ea n d l o s es i g h to ft h ep e r f o r m a n c eo ft h en e t w o r k a ne x t e n s i o nt or o u t i n gs e l e c t i o n a l g o r i t h m c a l l e d r o u t i n g s e l e c t i o na l g o r i t h mw i t hs e r v i c e sd i f f e r e n t i a t i o n c o n s c i o u s n e s si sp r o p o s e di nt h i sp a p e r o f f - l i n em u l t i p a t ha n a l y s i si st h ee s s e m i a l p a r to f t h ea l g o r i t h m ，i tc r e a t e ds o m eu s e a b l el a b e l s w i t c h - p a t h sf o re a c hs o u r c e - n o d e 幻d e s t i n a t i o n - n o d e ；w h e nt h eo p e r a t i o n ss e ti n , t h eo n - l i n er o u t i n ga l g o r i t h mw i l l c r e a t et h el s pf o re a c ht h eq o sa n db e s t - e f f o r to p e r a t i o n su s i n gd i f f e r e n ts t r a t e g y , v i z s e l e c tt h es h o r tp a t hw h i c hi sc l o s et ot h eb a n d w i d t hr e q u e s to f t h e 台瓶cf o rq o s ， t os a t i s f yt h er e q u e s t so fd e m a n da n d ，l o wd e l a y , a n da l s ot oa v o i dr e f u s i n gt h e p o s t e r i o rq o st r a 街cw h i c hd e m a n di sh i g hi n t ot h en e t w o r k ；f o rb e s t - e f f o r tt r a f f i c s e l e c tt h ep a t hw h i c hr e s i d u a lb a n d w i d t hi sa b u n d a n c e ，t oa v o i dc o n g e s t i o na n di o a d b a l a n c e u s i n gn s - 2 ，t h es i m u l a t i o nr e s u l ts h o w st h a tt h en e w o n l i n er o u t i n ga l g o r i t h m s i g n i f i c a n t l yo u t p e r f o r m st h ec s p f ( c o n s t r a i n e ds h o r t e s tp a t hf i r s t ) ，w h i c hg r e a t l y i n c r e a s e st h et h r o u g h p u to f t h eb e s t - e f f o r tt r a 伍c s ，a n ds i m u l t a n e o u s l yg u m a n t o e st h e b a n d w i d t ha n da c e e p t a b l e - m t i oo ft h eq o st r a 街c s o f f - l i n ea l g o r i t h ma l s or e s e r v e s s o m eb a n d w i d t hf o rq o st r a 伍c ，r e s u l t si nn o tr e j e c t i n gt h er e q u e s ti na l li r r e s p o n s i b l e w a y k e yw o r d s ：t r a 伍ce n g i n e e r i n g , m p l s ，o n - l i n em u t i n g , o f f - l i n eo p t i m a l ，q o s 独创性声明 本人声明所里交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得叁壅盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：降锍玩签字日期：堋年蝴7 日 学位论文版权使用授权书 本学位论文作者完全了解：叁鲞盘堂有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 厉 签字日期：年月矽日。 翮签名：多删 签字日期：即缉2 月矽日 天津大学硕士学位论文具有分类服务功能的路由选择算法研究 第一章绪论 目前网络传输中的业务可以分为两类：实时业务和b e s t - e f f o r t 业务。实时业 务在我们的生活中，例如语音、在线视频、在线会议等，需要有一定的带宽保证， 在网络传输中需要保持其数据的完整性和低延迟性，即我们通常所说的q o s 业 务；b e s t - e f f o r t 业务是一种尽力而为的业务，例如文件传输、e m a i l 服务等，不 需要严格的带宽和延迟的约束，但是需要我们给予这种业务一定的吞吐率保证。 现有的流量工程算法存在的主要问题是只能处理有带宽要求的业务，对 b e s t e f f o r t 业务没有做任何的考虑，这对现在的网络来说，是不可接受的，因为 现在网络业务中，b e s t - e f f o r t 业务占的比率更大。因此，本文提出一种具有分类 服务功能的路由选择算法，用以平衡两类业务的传输。 1 1 论文背景与研究动机 1 1 1i p 网络中的q o s 业务服务 q o s ( q u a l i t y - o f - s e r v i c e ) ，从概念上说，可以看作是为一项或一类网络业务 定义的一组性能参数，其性能目标就是有效的提供一定的端端性能保证。例如， 话音业务延迟不得超过2 0 0 m s ，延迟抖动，丢包率等；另外实时业务有其固有的 数据率要求，例如话音业务为6 4 k b p s 等等，这就要求网络必须为此类业务提供 一定的带宽。其性能参数【1 1 主要包括： 可连接性( c o n n e c t i o n ) 保证传输节点之间连接的稳定性。 延迟保证( l o w _ d e l a y ) ：数据包传送时间的保证。 延迟抖动保证( d e l a y ) ：数据包之间的传输时间差异。 接受比( a c c e p tr a t i o ) ：最大化能接受的q o s 请求数日。 吞吐率( t h r o u g h p u t ) ：网络中发送数据包的速率。 1 1 2i p 网络中的b e s t - e f f o r t 业务服务 b e s t - e f f o r t 业务一尽力而为的服务业务，标准的因特网服务模式。应用程 序可以在任何时候，发出任意数量的报文，而且不需要事先获得批准，也不需要 通知网络。对b e s t - e f f o r t 服务，网络尽最大的可能性来发送报文，但对时延、可 第一章绪论 靠性等性能不提供任何保证。在网络接口发生拥塞时，不顾及用户或应用，马上 丢弃数据包，直到业务量有所减少为止。例如最普遍的f t p 和e l e c 心o n i cm a i l ， 可以允许任意的延迟、丢包，它通过先入先出( f i f o ) 队列来实现。 1 1 3m p l 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 ，多协议标记交换) 是i e t f 制定的集 成式i po v e ra t m 技术，即在f r a m er e l a y 及a t ms w i t c h 上结合路由功能的技 术规范，它结合了目前坤与a t m 的技术优势。m p l s 可适用于任何网络层协议， 目前主要致力于传输口业务。 图1 1m p l s = i p - 4 - a t m 2 流量工程( t r a f f i c e n g i n e e r i n g ) 的概念是合理安排业务流量在网络中的流向 以避免造成网络资源的不均衡使用f 3 】。在r f c 3 2 7 2 1 4 中，给出了流量工程的明确 定义，就是与i n t e m e t 网络工程进行性能评价及如何操作p 网络使网络性能优化 这两个问题相关的所有知识。一般来说，它包含了技术的应用、测量的科学准则、 模型化、归纳和因特网流量的控制，以及如何将这些知识和技术应用到实践中来 获取一些特定的性能指标。流量工程的主要问题是路由，路由算法决定网络资源 的使用。良好的实施流量工程可以减小网络拥塞、减小资源消耗、最大化网络接 受比、最大化业务吞吐率。 近年来，对流量工程框架和算法的研究主要集中在o s p f 5 1 、i s i s 【6 1 和m p l s 【7 】这三个协议上。o s p f 和i s - i s 是现在网络中使用最广泛的两种内部网关协议， 而且能在o s p f 上实现的流量工程算法也能同样在i s i s 上实现。匝t f 已给出了 流量工程在o s p f 和i s i s 上扩展的标准f 8 】 9 1 。针对o s p f b s i s 协议研究的重点 2 天津大学硕士学位论文具有分类服务功能的路由选择算法研究 是如何将优化计算得到的结果转化成链路权值，以达到网络效益的最大化【1o 】【n 】。 1 1 4 背景与动机 本文是在天津市自然科学基金资助项目( 项目编号：0 4 3 6 0 0 3 1 1 ) 课题背景 下展开的。研究的主要内容是在m p l s 流量工程基础上，分析适合i p 网络传输的 路由选择算法和框架。 目前的m 网络路由选择算法主要研究q o s 业务类的正常传输，对于占网络 业务主流的b e s t - e f f o r t 业务类没有过多的涉及。这样的算法往往导致为 b e s t - e f f o r t 业务提供的带宽不足，造成b e s t - e f f o r t 业务拥塞甚至s t a r v a t i o n 1 2 。 本文所提出的算法是在文献【1 3 】所提出算法的基础上，进一步研究的结果。 文献 1 3 】提出一种在线路由算法，来提高尽力而为业务( b e s t e f f o r t ) 的吞吐率， 同时保证有服务质量保证业务( q o s ) 传输的低延迟性。由于 1 3 】提出的框架首 先针对如何提高b e s t - e f f o r t 业务类性能，对q o s 服务选路性能并没有过多的涉 及( 目前的网络毕竟是以q o s 保证优先) ；此外，文献【1 3 】中采用的是静态业务， 并不能完全代表现在的网络动态性。因此本文算法在其基础上优化了离线计算路 径集合，并且将在线选路算法改变为优先为q o s 类选路的算法，其次保证 b e s t e f f o r t 业务传输性能。在仿真实验中增加离线资源预留实验、在线动态业务 吞吐率实验、网络q o s 类可接受比测量实验等等。 1 2 论文的主要研究工作 本文主要的研究工作是： 1 离线预处理阶段，优化文献【1 3 】中线性规划产生的路径集合，提出q o s 动态资源预留系数。 2 在线阶段，提出一种全新的分类服务功能路由选择算法，在优先提供有 服务质量保证业务的性能要求的同时，为尽力而为业务选路。 3 利用n s2 0 工具在l i n u x 中进行了大量的网络仿真实验，分析算法的可 行性。 1 3 论文整体结构 本文共分六章，第一章是绪论部分；第二章介绍了m p l s 技术原理，核心部 分是基于m p l s 的流量工程的基本概念和基本原理：第三章是经典的路由选择算 第一章绪论 法综述，在此章主要介绍目前比较常用的，如p b r l l 4 、d b r 【l 习、m i r a 0 6 等路 由选择算法。第四章首先给出了本文流量工程框架中，离线预处理计算的公式， 然后提出了一种将离线计算得到的链路带宽分配结果转化为路径集合的算法，并 介绍了本文提出的分类服务功能的在线路由算法，该算法兼顾了q o s 业务和 b e s t - e f f o r t 业务的特点，为q o s 业务提供有带宽保证的服务，并提高了b e g - e f f o r t 业务能够使用的最大带宽。第五章是仿真实验部分，本文的仿真实验主要利用 n s2 0 和l i n d ot 具。第六章，本文结论与未来展望。 4 天津大学硕士学位论文具有分类服务功能的路由选择算法研究 第二章肝l s 网络技术 在过去的二十多年中，传统的以i p 包转发为基础的机制以其良好的统一性、 兼容性已确立了无可撼动的地位。但是随着因特网的飞速发展，各种新业务以及 迎合其需求的专有网络也在不断发展，但是原先针对不同业务、同时处理多种网 络连接的运营方式已经束缚了企业的发展，它们希望利用一种单一的网络来支持 多种业务。传统的i p 技术存在两个主要的缺陷，一是尽力传输( b e m e f r o r t ) 无 法保证像视频、语音等多媒体等业务对传输质量的要求；二是最短路优先( s p f ) 算法无法平衡网络负载，导致某些网络资源过载，造成某些链路拥塞，而另外一 些网络资源却没有充分利用的现象。针对当前网络存在的问题，人们希望利用多 协议标记交换( m p l s ) 和流量工程( t e ) 1 7 来解决相应的问题。 m p l s 是近几年发展起来的新型的网络交换技术。它主要是在传统的口网络 中增加了面向连接的特性，从而使得在传统m 网络中实施流量工程成为可能。 m p l s 所提供的最关键的优点是能够将口分组路由到一条标记交换路径l s p ( l a b e ls w i t c h e dp a t h s ) 上，l s p 实质上是建立了一条穿越网络的虚电路。一对 源目的地址之间可以建立多条( 包括一条) 不同的l s p ，每条l s p 的路由可以 独立指定。 流量工程就是一种能将业务流映射到实际物理通路上，同时又可以自动优化 网络资源以实现特定应用程序服务性能要求的、具有宏观调节和微观控制能力的 网络工程技术。流量工程的目标是避免拥塞问题以及由此引起的q o s 服务等级 下降问题；另外它还要实现网络工程自动化。从网络流量的观点来看，流量工程 的功能可以看作是网络中业务流量分布的优化。 因此利用基于m p l s 的流量工程技术，就可以将一些负载严重的链路上业务 平衡到其他一些空闲的链路中，实现网络资源的合理利用，达到平衡网络负载的 目的。 2 1m p l s 的基本概念 m p l s 即m u l t i - p r o t o c o ll a b e ls u b s t i t u t i o n ，多协议标记交换。 1 ) 协议 m p l s 位于传统的二、三层协议之间，其上层协议与下层协议可以是当前网 第二章m p l s 网络技术 络中的任何协议。如：可以是i p x ，a p p l e t a l k 等等。 2 ) 标记 m p e s 的标记( l a b e l ) 是一个长度固定，作用范围在本地的标志。标记封 装在m p l s 的分组头之中，m p l s 分组头总共包含3 2 b i t s 的数据，如图4 1 所示， 其中l a b e l 字段占2 0 b i t s ，就是我们通常所说的标记值：用于实验的e x p 字段占 3 b i t s ，用于表示服务等级c o s ( c l a s so f s e r v i c e ) ，影响分组在网络中传输时排队 和丢弃算法；堆栈指示字段p s 占l b i t ，用于支持标记栈的结构，在标记栈最后 一个实体中设置为l ，其他标记实体置为0 ；t 1 l ( t t m et ol i v e ) 字段占8 b i 乜， 与传统i i l 网中1 r l 字段的含义相同。 i l 2 h e a d e rl 唧l ss h i mh e a d e r i ph e a d e r u s e t d a m 、 l a b e l ( 2 0 b i t s )e x o b i t s )p s ( i b i t s )t t l ( s b i l s ) 图2 - 1m p l s 网络中的分组头格式 在a t m 或x 2 5 的网络中，标记可以直接使用v p i v c i 或l c n 来表示。 3 ) 交换 通常我们所说的交换包括三种( 以从x 走到y 这一过程中的交换为例) ： a 广播式路由 从x 出发，不考虑方向问题，任意发送数据分组，直到走到y 为止 b h o p j b y - h 叩路由( 逐跳) 从x 出发，不断的寻找哪个节点离y 比较近，然后向该节点发送数据分组， 依次类推，直到走到y 点停止 c 源路由 预先建立一个列表，存储从x 走到y 的路径，依据表中的路径走蓟y 。 m p l s 中的标签交换主要采用b 或者c 的方法。通过图2 - 2 我们可以比较直 观的看出m p l s 中的标签交换方法。 2 2m p l s 网络中的常用术语 1 ) 标签交换路径【1 8 1 ( l s p ) ，l a b e ls w i t c h i n gp a t h 。使用m p l s 协议建立起 来的分组转发路径，由表示源到目的节点一系列l s r 的标记以及它们之间的链 6 天津大学硕士学位论文 具有分类服务功能的路由选择算法研究 路组成。 2 ) 标签边缘路由器( l e r ) ，l a b e ls w i t c h i n ge d g er o u t e r 。m p l s 网络同其 它网络的边缘设备。 3 ) 标签交换路由器( l s r ) ，l a b e ls w i t c h i n gr o u t e r 。m p l s 网络的核心交 换机，它提供标记交换、标记分发功能。 4 ) 标签分配协议( l d p ) ，l a b e ld i s t r i b u t i o np r o t o c o l 。标记分发协议，相当 于传统网络中的信令协议，负责标记的分发与维护。 5 ) 标签信息库( l m ) ，l a b e li n f o r m a t i o nb a s e 。作用类似于路由表，其中包 含各个标记所对应的各种转发信息，每个入口标记对应一个条目，包括出口标记、 出口接口等信息。 6 ) 转发信息库( f i b ) ，f o r w a r d i n gi n f o m m f i o nt a b l e 。存储标签绑定信息和 相应的标签转发信息的数据库。 7 ) 用户边缘路由器( c e ) ，c u s t o m e re d g e 。将一个用户站点接入服务提供 者网络。 8 ) 运营商边缘路由器( p e ) ，p r o v i d e re d g e 。与用户c e 路由器相连的、服 务提供者的边缘路由器。 9 ) 运营商骨干路由器( p ) ，p r o v i d e r 。连接服务提供者的骨干路由器。 1 0 ) 基于约束的标签分发协议( c r - l d p ) ，c o n s t r a i n t - b a s e dl a b e ld i s t r i b u t i o n p r o t o c o l 。基于约束的标签分发协议，在标记的分发与维护过程中，可以采用某 些方法实现q o s 业务的保证。 1 1 ) 类型长度值( n ) ：t y p e l e n g t h v a l u e 。m p l s 消息中的子结构，类似 于其它协议中各种消息内的对象。 1 2 ) 转发等价类( f e c ) ，f o r w a r d i n ge q u i v a l e n c ec l a s s 。m p l s 实际上是一 种分类转发的技术，它将具有相同转发处理方式( 目的地相同、使用的转发路径 相同、具有相同的服务等级等) 的分组归为一类，这种类别就称为转发等价类。 属于相同转发等价类的分组在m p l s 网络中将获得完全相同的处理。在l d p 过 程中，各种等价类对应于不用的标记，在m p l s 网络中，各个节点将通过分组的 标记类识别分组的转发等价类。 2 3m p l s 的工作原理 m p l s 的工作原理简单说就是利用h o p - b ) 州o p ( 逐跳寻径) 的方法建立标 记( l a b e l ) ，在从源节点到目的节点的l s p 路径中，m p l s 通过在每一个节点的 标记交换来实现包的转发。 第二章m p l s 网络技术 2 3 1 标记的封装 第三层封装驴p a c k e t m p l s 封装s h i ml a b e l 第二层封装 ：i mf rp p pe n l e r r l e t 图2 - 2 标记的封装 标记的封装可以分为四个部分：l a b e l ( 标记值，2 0 b i t s ) 、e x p ( 实验使用， 目前作为i pq o s 的映射，3 b i 忸) 、s ( 堆栈指示，1 b i t ) 以及r r l ( 生存时间， 8 b i t s ) 。 由于m p l s 技术尝试运行在不同结构的数据链路层，因此在第2 层链路层 m p l s 标记封装格式也是有针对性的。 目前最常用的标记格式包括： a t m ：标记包含在a t m 头的v c u v p i 域。 f r a m e r e l a y ：标记包含在f r 头的d l c i 域。- p p p l a n ：使用”s h i m ，插入在2 层和3 层报头之间。 m p l s 的标记栈封装可以定义在多种不同的媒质上，栈顶的标记仍然可以沿 用现有的格式，如在a r m 媒质上，就可以沿用v p i 、v c i 作为栈顶的标记；低 一些级别的标记可以使用“夹层”或者叫“垫层”( s h i m ) 标记，以消除不同媒质之 间的差异。m p l s 在各种媒质上的封装如图2 3 所示 图2 3m p l $ 对于多种媒质类型有独特的标记封装 2 1 ：a t m 和f r 链路层的标记可以 利用已经存在的标记格式，e t h e m e t 、p p p 的标记类型利用s h i m1 1 9 l 标记。 3 天津大学硕士学位论文具有分类服务功能的路由选择算法研究 2 3 2 标记分配协议 标记分配协议( l d p ) 是在m p l s 网络中定义的、专用于标记交换路由器( l s r ) 之间交换“标记转发等价类( f e c ) ”绑定信息以便建立和维护标记交换路经( l s p ) 的控制信令。 目前应用最广泛的三种标记分配协议包括：基本标记分配协议( l d p ) 2 0 l 、 基于约束的l d p ( c r - l d p ) 【2 l 】和扩展r s v p ( r s v p - t e ) 瞄】。 l d p 是基本的m p l s 信令与控制协议，它规定了各种消息格式以及操作规 程，u ) p 与传统路由算法相结合，通过在t c p 连接上传送各种消息，分配标记、 发布 映射，建立维护标记转发表和标记交换路径。但如果需要支持 显式路由、流量工程和q o s 等业务时，就必须使用后两种标记分配协议。 c r l d p 是l d p 协议的扩展，它仍然采用标准的l d p 消息，与l d p 共享 t c p 连接，c r - l d p 的特征在于通过网管制定或是在路由计算中引入约束参数的 方法建立显式路由，从而实现流量工程等功能。 r s v p 本来就是为了解决t c p m 网络服务质量问题而设计的协议，将该协 议进行扩展得到的r s v p t e 也能够实现各种所需功能，在协议实现中将r s v p 作用对象从流转变为f e c ，降低了颗粒度，也就提高了网络的扩展性f 2 】。 2 3 3m p l s 工作流程 m p l s 的工作流程主要包括网络边缘行为、网络中心行为以及标记交换路径 的建立： 1 ) 网络边缘行为：当i p 数据包到达一个l e r 时，m p l s 第一次应用标记。 首先，l e r 要分析p 包头的信息，并且按照它的目的地址和业务等级加以区分。 在l e r 中，m p l s 使用了f e c 的概念，将输入的数据流映射到一条l s p 上。 简单地说，f e c 就是定义了一组沿着同一条路径、有相同处理过程的数据包。这 就意味着所有f e c 相同的包都可以映射到同一个标记中。 对于每一个f e c ，l e r 都建立一条独立的l s p ，穿过网络，到达目的地。数 据包分配到一个f e c 后，l e r 就可以根据l i b 来为其生成一个标记。标记信息 库将每一个f e c 都映射到l s p 下一跳的标记上。如果下一跳的链路是a t m ，则 m p l s 将使用a t m v c c 里的v c i 作为标记转发数据包，l e r 检查标记信息库中 的f e c ，然后将数据包用l s p 的标记封装，从标记信息库所规定的下一个接口发 送出去。 2 ) 网络的核心行为 当一个带有标记的包到达l s r 的时候，l s r 提取入口标记，同时以它作为索 第二章m p l s 网络技术 引在标记信息库中查找。当l s r 找到相关信息后，取出出口标记，并由出口标 记代替入口标记，从标记信息库中所描述的下一跳接口送出数据包。 最后，数据包到达了m p l s 域的另一端，在这一点，l e r 剥去封装的标记， 仍然按照p 包的路由方式将数据包继续传送到目的地。 3 ) 标记交换路径的建立 ( f b c a( f b c )b l s r ll s r 2l s r 3 荪签映射消息席签映射消息 图2 4 标记交换路径的建立，通道建立时序：a + b c d 如图2 - 4 ，标签交换路由器l s r i 建立一个显示路由对象，该路由对象包含 一条显示路由( l s r 2 ，l s r 3 ) ，l s r l 将沿此路由建立一条l s p ；每个l s r 是由 3 2 b i t s 长度的m 地址来表示：l s r l 构造一个标签请求消息并发送给l s r 2 ( 时 序a ) ，该标签请求包含显示路由对象e r o ( l s r 2 ，l s r 3 ) ，l s r 2 在收到l s r l 发来的标签请求消息时( 时序b ) ，会发现自己就是e r o 的第一个节点，然后 l s r 2 会继续查找下一个节点，即( l s r 3 ) ，l s r 2 把当前e r o 中的自己删除， 并向l s r 3 发送一个新的标签请求消息，此时e r o 变为( l s r 3 ) 。l s r 3 发现自 己是e r o 中的最后一个节点，那么l s r 3 就在其输入端口产生一个本地绑定 ( f e c ，l 2 ) ，l s r 3 向l s r 2 发送标签映射消息( 时序c ) ，l s r 2 接收到该消息 后，在输出端口生成一个远程绑定，即用l s r 3 传来的标签来填写自己标签转发 表的输出端口部分，同时建立输入端口的本地绑定 f e c ，l 1 ) ，并将标签映射 消息( 时序d ) 发送到l s r l ，l s r l 收到来自l s r 2 的标签映射消息后在输出端 口建立远程绑定 o ) ，d f 表示从源节点s r 到目的节点t r 的聚集业务带宽需求。y i j 表 示链路( i ，i ) 分配给源目的节点对s 的带宽值。因为在本文中，源一目的节点 对和业务带宽有一对一关系，所以业务矩阵也可以表示源一目的节点对集合，只 要忽略了d r 这个参数即可。 业务矩阵的测量也有很多人在研究【2 7 】网【2 9 】，在文【2 7 】中，比较t - - - 种业务矩 阵测量技术，并提出了p o p p o p 业务矩阵测量的新方法。文 2 8 1 q a ，给出了估 计源目的节点对间的业务矩阵参数的一种算法。在文 2 9 1 中，给出了动态环境下， 估计业务矩阵的方法。由此可知，业务矩阵是可以得到的。在本文中，假设业务 矩阵r 是已知的，且业务矩阵是非随机的。 4 3 分类服务一离线阶段 离线阶段的主要工作是利用离线预处理计算，优化网络的整体性能，并在有 业务传输要求的源一目的对之间建立近似优化的路径集。 4 3 1 算法概述 为了离线( o f f - l i n e ) 计算业务可使用的路径集合，算法必须要明确网络拓扑 中各条链路可以分配给当前业务的可使用带宽，然后我们才能依据带宽分配结果 为相应的业务建立适合它的路径集合。 通常离线优化的方法包括最小化拥塞和最小化资源消耗两种方法。文 3 0 1 给 出了以最小化拥塞为优化目标的形式化公式。最小拥塞优化以最小化最大链路利 用率为目标，往往导致较长的路径。为避免这一缺点，本文在离线计算中以最小 化网络中各条链路负载之和为优化目标，并转化为运筹学线性规划求解问题，最 后将计算结果采用链路状态协议发送到各个边缘节点，获得各条链路给当前业务 的可使用带宽。 第四章分类服务路由选择算法 最小化资源消耗的线型规划( 4 1 ) 表示为， 目标函数：r a i n 巧 ( 4 一1 ) ( f ，) e r e r 1 4 i fi = s r , r r 约束条件：j ，；一巧= 一d r i ff = d ，r ( 4 - 2 ) ，i ，7 ) e e，和j ) e e 10d t h e ，w i s e y ； + 5 c i j ) m i n b w = y ； e n o d e2 j ； i f ( m i n b w2 = o o ) 返回路径集p f ，算法结束。 b 肚) = m i n b w ； 将节点c n o d e 加入路径p 中； 3 ) 在当前节点的所有邻居节点中， w h i l e ( c n o d e ! = d e s t ) m i n b w2 - l o t ) ； w h i l e ( c n o d e ，j ) e e i f ( m i n b w j ) m i n b w = y r o d c j c n o d e = j ； ) 查找带宽分配最小的链路 第四章分类服务路由选择算法 i f ( m i n b w = = 0 0 ) 分配结果有误，退出算法。 b m = m i n c o 肚) ，m i n b w ) ； 将节点c n o d e 加入到路径p r o 【) 中； 得到容量为b 歌) 路径p r ( k ) ，并加入到路径集p r ； 对路径p i o 【) 上的每条链路( i ，j ) ，将死减去b d ； 4 ) 回到2 ) ，继续运行算法。 4 4 分类服务一在线阶段 在线阶段是基于带限定条件的路由选择，传统的路由选择主要是以最短路径 优先( s p f ) 为基础的，即起点与目的节点之间最少的跳数或最小的路径指标的 路径为最优路径。带限定条件的路由选择应用在有性能保证的q o s 业务，它是 延时、丢包率与网络连接上的可用带宽之间的综合考虑。现有的很多算法都假设 网络中只有q o s 业务，例如前面提到的p b r 、d b r 、m i r a 等等。一方面，这 些算法对b e g - e f f o r t 业务没有做任何的考虑，这对现在的网络来说，是不可接受 的。另一方面，即便是s p f 方法可以对单一q o s 请求提供最短路径，但随着网 络资源使用增加，会导致很高的请求拒绝率和很低的网络资源使用率( 参考一种 m p l s 流量工程中的动态路由算法) 。 针对这些问题，本文提出了一种具有分类服务功能的在线路由选择算法，该 算法用于m p l s 网络，特别是该算法试图在基于m p l s 的流量工程背景下，可 以为不同的业务提供不同的服务。算法基于4 3 中离线预处理阶段计算的路径集， 根据不同业务类的特点分别选择适合的路径。 4 4 1 算法概述 很多启发式q o s 算法在线便用最短最宽或最宽最短策略，本文算法为q o s 业务在满足它带宽的基础上，选择跳数少、路径可用带宽最接近业务需求值( 较 窄) 的路径；为b e s t - e f f o r t 业务选择路径负载较低( 较宽) 的路径传输，以尽 量避免两种不同的业务共享路径和在路径级别上平衡它们的带宽使用。为o o s 选 择比较窄的路径主要是考虑以后要满足可能出现的带宽需求较大的q o s 业务，防 止需求小的q o s 业务占用比较大的链路，使得后面到来的需求大的o o s 业务无法 天津大学硕士学位论文具有分类服务功能的路由选择算法研究 正常传输。 在线路由选择部分的主要参数有路径剩余带宽、路径利用率下限b ，上限y 。 b 的值设的比较小，目的是防止负载较轻的时候，所有的b e s t e f f o r t 业务都集 中到一条路上，而别的路径闲置，造成带宽的浪费。路径利用率上限y 用来限制 q o s 业务占用过多的路径集上的资源，使得b e s t e f f o r t 业务的进入造成负载较 重的路径拥塞，或者使拥塞的路径情况更加严重。 算法主要包括以下几个步骤： 1 路径集合排序，将离线计算得到的路径集合中的路径按照路径剩余带宽 从小到大，长度( 跳数) 从短到长的顺序排序，这样最窄最短的路径就 排在了前面，最宽最长的路径就排在了集合的后面； 2 为q o s 业务选路，从路径集合中的第一条路径，即最窄最短的路径开始 查找，如果某条路径剩余带宽满足业务带宽需求，就输出找到的路径， 如果路径集合中的所有路径都不满足q o s 业务的要求，启动基于约束的 最短路算法为q o s 业务选路。这样即使业务矩阵的预测出现较大的失误 ( 很多预测的业务没有到来，很多到来的业务是没有预测到的业务) ， 算法的性能也只会和约束最短路算法一样，而不会出现像p b r l l 4 】那样拒 绝所有的业务请求，使网络的利用率为0 的情况。 3 为b e s t e f f o r t 业务选路，从路径集合中的从剩余带宽最大的那条路径 开始为b e s t e f f o r t 业务查找负载较轻的路径，对剩余带宽相同的路径， 选择较长的。如果某条路径的利用率低于b ，那么就直接采用这条路径， 否则就选择低于上限y 的路径中链路利用率最小的那条路径。 4 4 2 算法伪代码 算法4 2 在线分类选路算法 输入：1 网络图g ( v ，e ) 2 算法4 1 输出的可使用路径集合p 3 在线q o s 业务的带宽需求b i 输出