（通信与信息系统专业论文）mpls的服务质量保证技术研究.pdf

北京邮电大学硕士学位论文 m p l s 的服务质量保证技术研究 摘要 随着i n t e m e t 商业化程度的不断加深及其在世界范围的迅猛发 展，人们越来越希望i p 网络不仅能提供单纯的数据传输业务，像 e - m a i l ，f t p 等业务，还要能够提供话音、图像、多媒体等实时业务， 同时i n t e m e t 服务提供商( i s p ) 也希望有更多的手段管理控制网 络，从而可提供更为丰富便捷的服务。服务质量( q u a l i t yo f s e r v i c e ， q o s ) 保证技术正是基于此原因而受到了广泛关注。 m p l s ( m u l f i p r o t o c o ll a b e ls w i t c h ，多协议标签交换) 虽然不是 主要的q o s 机制，但是它是实现q o s 的一个重要工具，m p l s 技术 无缝的集成了i p 路由技术的灵活性和二层交换技术的简捷性，在面 向无连接的邛网络中增加了m p l s 这种面向连接的属性，其显示路 由能力为流量工程和i p 网络快速故障恢复的实现提供了保证。m p l s 作为一种成功的电信网络技术与计算机网络技术的融合，成为目前业 界普遍看好的解决d 骨干网中q o s 问题的基本技术。 本文首先分析了课题的研究背景，并对i pq o s 的两种服务模型 进行了简单介绍，阐述了m p l s 的基本概念、工作原理，以及m p l s 网络提供q o s 保证的技术和优势，在接下来的第三和第四章节中详 细论述了本文完成的主要工作，本文主要就m p l s 服务质量保证技术 中的两个方面进行了较深入的研究，一是流量工程动态路由算法，二 是m p l s 网络的故障恢复机制。 在第三章中首先分析了目前最小干扰路由算法的局限性，在此基 础上提出了一种新的最小干扰路由算法，该算法分为预处理和在线计 算两个过程，从而将复杂的计算在预处理过程中完成，降低了算法复 杂度的影响，同时引入次关键链路的概念，降低网络连接请求的拒绝 率，提高网络吞吐量，仿真结果表明新的最小干扰路由算法的性能得 到了进一步改善。 在第四章中研究了m p l s 网络的故障恢复机制，在深入研究了当 前的保护交换和重路由故障恢复机制的基础上，针对目前重路由故障 恢复机制中的节点计算负担问题，首先给出一种新的备用路径的计算 方法，将图论中的基本回路的概念引入到备用路径的计算中来，从而 北京邮电大学硕士学位论文 将备用路径的计算分为预计算和在线计算两个过程，大大缩短了备用 路径的在线计算时间，减轻了节点的计算负担，然后在此基础上给出 了一种重路由故障恢复机制，分析与仿真结果表明，本机制具有较优 的性能。最后，就本文提出的备用路径的计算方法在其他故障恢复机 制中的应用作了简单分析。 关键词：服务质量多协议标签交换流量工程故障恢复重路由 保护交换 i i 北京邮电大学硕士学位论文 r e s e a r c h o ng u a r a n t e e d q u a l i t yo f s e r c et e c h n o l o g i e so v e rm p l s a b s t r a c t w i t ht h ed e e p e n i n go f 血ee x t e n to fi n t e r a c tc o m m e r c i a l i z a t i o na n d t h er 印i de x p a n di nt h ew h o l ew o r l do fi n t e r a c t , i n t e r n e tw a s e x p e c t e d t o p r o v i d en o to n l yt h es i m p l ec o n n e c t i o ns e r v i c e ss u c ha se - m a i la n df t p b u ta l s om o r ea b u n d a n ts e r v i c e ss u c ha sb r o a db a n da n dm u l t i m e d i a a t t h es a m et i m ei n t e m e ts e r v i c ep r o v i d e r ( i s p ) h o p et h a tt h e r ea r em o r e m e a n st om m a a g ea n dc o n t r o li n t e r a c t ，s ot h a tm o r ek i n d so fs e r v i c e s c o u l db ep r o v i d e de a s i l y u n d e rt h ec i r c u m s t a n c e sg u a r a n t e e dq u a l i t yo f s e r v i c e s ( q o s ) t e c h n o l o g i e sa t t r a c ta t t e n t i o n a l t h o u g hm u l t i p r o t o c l l a b e l s w i t c h ( m p l s ) i s n o ta q o s m e c h a n i s m ，i ti sa ni m p o r t a n tt o o lf o rt h ei m p l e m e n to fq o s m p l s i n t e g r a t et h ef l e x i b i l i t yo fi pr o u t i n ga n dt h es i m p l i c i t yo fs w i t c h i n ga n d a d dc o n n e c t i o nt r a i ti nt h ec o n n e c t i o n l e s si pn e t w o r k t h ec a p a b i l i t yo f e x p l i c i tr o u t i n gg u a r a n t e e st h ei m p l e m e mo ft r a f f i ce n g i n e e r i n ga n df a s t f a u l tr e c o v e r yi ni pn e t w o r k m p l sc o m b i n e st h et e l e c o m m u n i c a t i o n t e c h n o l o g i e sa n dc o m p u t e r n e t w o r k s t e c h n o l o g i e ss u c c e s s f u l l ya n d b e c o m e sab a s i ct e c h n o l o g yf o rt h es o l u t i o no f i pq o s p r o b l e m r e s e a r c hb a c k g r o u n dw a sa n a l y z e da tf i r s ta n di pq o ss e r v i c e m o d e l sw e r ep r e s e n t e d t h e nt h ec o n c e p t sa n dt h e o r i e sa b o u tm p l sw e r e i n t r o d u c e da n da d v a n t a g e so fm p l si np r o v i d i n gg u a r a n t e e dq o sw e r e g a v e m ym a i nw o r kw a sd i s c u s s e da tc h a p t e r3a n dc h a p t e r4 t w o a s p e c t so fg u a r a n t e e dq o st e c h n o l o g i e sw e r es t u d i e d ，o n ei sa b o u tt r a f f i c d y n a m i cr o u t i n ga l g o r i t h ma n dt h eo t h e ri sa b o u tf a u l tr e c o v e r y m e c h a n i s mi n 田l sn e t w o r k a tc h a p t e r3 ，t h el i m i t so fm i n i m u mi n t e r f e r e n c er o u t i n ga l g o r i t h m ( m i r a ) w e r ea n a l y z e da tf i r s ta n dan e wm i n i m u mi n t e r f e r e n c er o u t i n g i i l 北京邮电大学硕士学位论文 a l g o r i t h m ( n - m m a ) w a sp r o p o s e d an e wm e t h o do fc o m p u t i n gl i n k v a l u ew a sg i v e na n di tc o n s i s t so ft w os t a g e s ：p r o p r o c e s s i n ga n do n l i n e c o m p u t i n g t h ec o m p l i c a t e dc o m p u t i n gw a sp e r f o r m e di np r o - p r o c e s s i n g s t a g e ，w h i c hd e c r e a s e st h ee f f e c to fc o m p l i c a t i o n t h en e wa l g o r i t h m d e f i n e ss u b c r i t i c a ll i n k ，w h i c hd e c r e a s et h er e j e c t i o nr a t i oo fc o n n e c t i o n r e q u e s t sa n di n c r e a s et h et h r o u g h o u to fn e t w o r k s i m u l a t i o nr e s u k ss h o w t h ep e r f o r m a n c eo f m i r ai si m p r o v e ds i g n i f i c a n t l y a t c h a p t e r4 ，f a u l tr e c o v e r ys c h e m e i nm p l sn e t w o r kw a s r e s e a r c h e da n daf u n d a m e n t a lc i r c u i tb a s e d r e r o u t i n gs c h e m ew a s p r o p o s e d t h ek e yp r o b l e mf o rr e r o u t i n gf a u l tr e c o v e r yi st h el o a do f n o d ec o m p u t i n g an e wm e t h o do f c o m p u t i n gb a c k u pp a t hw a sg i v e na n d i tc o m p r i s e so ft w os t a g e s ：p r o p r o c e s s i n ga n do n l i n ec o m p u t i n g t h e n e wm e c h o ds h o r t e n st h ec o m p u t i n gt i m eo fb a c k u pp a t ha n dt h e nt h e b u r d e no fn o d ew a sd e c r e a s e d b a s e d0 1 1t h en e wm e t h o d ，af u n d a m e n t a l c i r c u i tb a s e dr e r o u t i n gs c h e m e ( f c r ) w a sp r o p o s e d t h er e s u l t so f s i m u l a t i o na n da n a l y s i ss h o wt h a tf c rh a sm a n ya d v a n t a g e s ，t h e c o m p u t i n gm e t h o do fb a c k u pp a t hc o u l db eu s e di nm a n yo t h e rf ，a u l t r e c o v e r ys c h e m e s k e yw o r d s ：q u a l i t yo fs e r v i c e ( q o s ) ；m u l t i p r o t o c o ll a b e ls w i t c h ( m p l s ) ；t r a f f i ce n g i n e e r i n g ；f a u l tr e c o v e r y ；r e r o u t i n g ； p r o t e c t i o ns w i t c h i n g 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：荔，盘磊日期：纽：! ：! 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定， 即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被 查阅和借阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、 缩印或其它复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此 规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 北京邮电大学硕士研究生学位论文 1 1 引言 第一章绪论 从由于特殊需要而出现的网络互联，到今天互联网已渗透到人们生活、工作的 各个方面，只经历了短短几十年的时间。就在这么短短的几十年间，互联网从最 初的专用网，到少数网络的互通，发展到了覆盖全球的i n t e m e t ，它不再是只供 少数科研者进行交流的平台，而是像其他任何物品一样，一旦进入经济生活，开 始为商业机构所使用，它已经开始作为一种商品，它就需要不断更新，不断提高 自身，才能适应竞争的加剧。人们不再满足其单纯的数据传输业务，需要有语音、 图像、多媒体等实时性要求的业务，不再满足其尽力而为的服务质量，而是希望 物有所值，物超所值，拥有更好的网络服务质量；同样网络运营商为了竞争的需 要，希望能够提供更丰富的业务吸引用户，希望能为付出更高费用的用户提供更 高的服务质量保证，希望互联网能像传统的电信网络一样可管理、可控制。 新业务应用需求的提出，网络运营商对互联网更容易运营的期望的增加，归 根到底，是对互联网技术提出的挑战，是希望互联网可以提供满足各种服务质量 要求的业务应用。因此，对互联网的服务质量保证技术的研究将是实现向下一代 互联网发展的重要步骤。本文选择了基于m p l s 的服务质量技术研究，对其中 的流量工程路由算法和故障恢复机制进行了深入的研究。 1 2 论文的研究背景 1 2 1i n t e r n e t 互联网的现状 i n t e r a c t 是计算机交互网络的简称，又称网间网。它是利用通信设备和线路 将全世界上不同地理位置的功能相对独立的数以千万计的计算机系统互连起来， 以功能完善的网络软件( 网络通信协议、网络操作系统等) 实现网络资源共享和 信息交换的数据通信网。 二十世纪六十年代出于军事需要，由美国国防部高级研究计划署d a r p a ( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 提供经费，联合计算机公司和大 学共同研制而发展起来了a r p a n e t 网络。该网主要是基于这样的指导思想：网 北京邮电大学硕士研究生学位论文 络必须经受得住故障的考验而维持正常的工作，一旦发生战争，当网络的某一部 分因遭受攻击而失去工作能力时，网络的其他部分应能维持正常的通信工作。由 此，a r p a n e t 于1 9 6 9 年投入使用，成为i n t e m e t 的前身，也成为现代计算机网 络诞生的标志。 a r p a n e t 的试验奠定了i n t e r n e t 存在和发展的基础，较好地解决了异种机网 络互联的一系列理论和技术问题。1 9 8 3 年，a r p a n e t 分裂为两部分，a r p a n e t 和纯军事用的m i l n e t 。同时，局域网和广域网的产生和蓬勃发展对i n t e r n e t 的 进一步发展起了重要的作用。其中最引人注日的是美国国家科学基金会a s f ( n a t i o n a ls c i e n c ef o u n d a t i o n ) 建立的n s f n e t 。n s f 在全美国建立了按地区划分 的计算机广域网并将这些地区网络和超级计算机中心互联起来。n f s n e t 于1 9 9 0 年6 月彻底取代了a r p a n e t 而成为i n t e m e t 的主干网。 i n t e m e t 的第二次飞跃归功于i n t e r a c t 的商业化，1 9 9 5 年4 月3 0 日，n s f n e t 正式宣布停止操作，由美国政府指定三家私营企业来经营互联网。1 9 9 8 年6 月5 日美国政府发表白皮书，成立非赢利公司，互联网域名地址分配公司( i n t e r a c t c o r p o r a t i o nf o ra s s i g n e dn a m e sa n dn u m b e r s ，i c a n n ) 负责对互联网进行技术管 理。商业机构一踏入i n t e r a c t 这一陌生世界，很快发现了它在通信、资料检索、- 客户服务等方面的巨大潜力。于是世界各地的无数企业纷纷涌入i n t e r a c t ，带来： 了i n t e r a c t 发展史上的一个新的飞跃。 我国i n t e r a c t 的发展可大致分三个阶段，第一阶段是研究试验阶段，一些科 研部门和高等院校开始研究互联网技术，网络应用仅限于小范围内的电子有点服 务，第二个阶段是起步阶段，1 9 9 0 年l o 月我国正式注册了中国顶级域名c n 。 于1 9 9 4 年由中国科学院、清华和北太三单位共建n c f c ，与互联网实现了全功 能联接，互联网开始进入公众生活，并在中国得到了迅速的发展，到1 9 9 6 年底， 互联网用户达到2 0 万，利用互联网开展的业务与应用逐步增加。从1 9 9 7 年开始， 进入快速增长阶段，互联网用户数基本保持每半年翻一番的增长速度，发展到今 天，在最新的互联网发展统计报告中显示，截至2 0 0 5 年1 2 月3 1 日，我国网民 数量已经达到1 1 1 亿，上网计算机总数为4 9 5 0 万，域名总数约为2 5 9 2 4 1 0 个， 其中c n 域名为1 0 9 6 9 2 4 个，网站总数约为6 9 4 2 0 0 个，国际出口带宽总量达到 1 3 6 1 0 6 m ，互联网也成为人们生活，学习，工作必不可少的工具之一，随着新的 应用的涌现，互联网在社会经济中所发挥的作用也将越来越重要。 1 2 1 1 互联网的技术特点 作为a r p a n e t 的一个重要贡献，t c p i p 协议族的开发，保证了整个网络体 系结构相当灵活，网络不会受到子网硬件故障的影响，也成为了当前互联网的基 北京邮电大学硕士研究生学位论文 本网络模型，该协议族实现了无缝方式实现各种网络之间的互联技术。该协议族 主要包括协议( i n t e m e tp r o t o c 0 1 ) 、t c p 协议( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 ) 和u d p 协议( u s e rd a t a g r a mp r o t o c 0 1 ) 、以及应用层协议，以该协议族为基础的 网络体系结构称为t c p i p 参考模型。t c p i p 模型是一种层次结构，共分为4 层， 分别为应用层、传输层、互联网层和网络接口层。各层实现特定的功能，提供特 定的服务和访问接口，并具有相对的独立性。 互联网层，是网络体系结构的关键部分，使主机可以把分组发往任何网络并 使分组独立的传向目标( 可能经由不同的网络) 。这样的转发操作对用户是透明， 用户并不需了解转发原则和转发的路径，而且该转发操作不能保证分组的转发顺 序和发送顺序一致，如果需要按照顺序发送和接收，则需要上层完成排序。理 协议即位于该层，定义了标准的分组格式和接口参数，只要符合这样的标准，分 组就可以在不同网络间实现漫游。互联网层要实现分组的转发，必须首先要进行 寻径，寻径的操作需依赖于路由协议来实现，不同的路由协议采用不同的路由算 法。 t c p 协议和u d p 协议均位于传输层，即互联网层的上层，这两个协议均是 端到端的协议。t c p 协议是一个面向连接的协议，允许从一个主机发出的字节流 无差错的发往互联网上的其他主机，它把输入的字节流分成报文段传给互联网 层。在接收端，t c p 把收到的报文重组成报文流，另外t c p 还具有流量控制能 力。u d p 协议是一个不可靠的、无连接协议，用于不需要t c p 的排序和流量控 制能力而自己能完成这些功能的应用程序，提供更快速的传输服务。 采用以上体系结构的互联网，决定了其具有以下特点： ( 1 ) 基于无连接的分组交换网络，大大简化了系统管理和系统设备的复杂度， 网络采用尽力而为的方式，无需预先建立连接，只要有可用的资源，就可 进行分组包的转发，避免了采用连接时的空闲时间仍要占用资源所造成的 资源浪费，节省网络资源。采用分组包交换方式，将数据流分解成小数据 包，数据包可以沿很多路径同时传输，尽量避免拥塞，而且，即使数据包 在传输中丢失，只需重传该数据包，降低处理成本。 ( 2 ) 基于最短径的路由算法，内部网关路由协议采用的路由算法，均是基于最 短径算法实现，即根据一定的度量参数，寻找网络中一条最短径，在各个 路由器中存储到达目的地的最短径的下一跳端口，最终实现分组均可按照 最短径到达目的地，节省网络资源，且实现简单。 ( 3 ) 多种传输服务，目前互联网依靠传输层，可以提供可靠和不可靠的两种传 输服务，根据业务的种类，可以自由选择，且屏蔽了下层的口层的转发操 作，使得上层应用无需关心下层的操作，只需选择合适的端口，就可得到 北京邮电大学硕士研究生学位论文 所需的服务。 1 2 1 2 互联网的业务应用 业务总是和技术相关的，技术决定可实旖的业务应用，同时技术也是由应 用不断推动发展的，业务的需求推动了互联网的发展，互联网的技术特点也决定 的应用的种类，当前互联网的大部分业务应用与发展初期的应用大致相同，主要 是非实时数据业务，像电子邮件、w w w 、t e l n e t 和f t p 等，这些业务有个共同 的特点，对实时性要求不高，但对包的丢失较敏感，目前的互联网技术完全能够 满足这些业务需求。 1 2 2 当前互联网面临的挑战 1 2 2 1 应用的发展 ， 如果因特网能够满足现有的需求，则现有的技术就不用改变，但是，公众开 始注意因特网新的应用，希望能够充分支持实时和交互式视频语音的应用，不再 是电子邮件、文件传输等单纯的数据传输服务，而是要求网络中的i p 分组能够 保证其实时性和时序性，这样目前尽力而为的简单婵网络显然已无法满足要求， 必须要求口网络更加智能化，才能提供可预测，可管理的高质量的服务，满足 新业务的需求。 而且随着业务的多样化，用户可选择的业务种类也随之越来越丰富，因此d 网络需要提供服务质量要求不同的多种应用，不再是提供一种尽力而为的服务， 而是针对不同的用户需求需要提供不同的业务质量。 1 2 2 2 服务提供商的需求 随着新应用不断出现，企业的i p i n t r a n e t 和商业瑶骨干网同样面临着许多新 的需求，要求他们的网络在端到端的行为上具有更高的可预测、可控制，满足用 户的不同需求。理网络不同于传统的电信网可以提供可靠的连接服务，且网络 行为可完全控制，随着互联网的商业化程度的不断发展，服务提供商对p 网络 的可管理、可维护、可控制的愿望越来越强烈，希望有基于网络的，端到端的流 量控制机制，满足不同业务应用的服务质量要求。 流量的拥塞在传统口网络中主要依靠t c p 的控制机制，无可避免的造成包 4 北京邮电大学颈士研究生学位论文 的延迟或丢失，这一方面是因为网络资源的短缺，另一方面是因为在传统即网 络中只选用最短路，造成流量分布不均，从而使得某些链路拥塞，而某些链路依 然空闲。针对第一方面，只能通过增加网络带宽，而对于第二种情况希望进行流 量重新分配或选择非最短径实现。而且新的应用大多是高带宽需求的业务，一味 的增加带宽是服务提供商所不希望的，因此采用新的技术避免流量拥塞提高服务 质量是服务提供商最期望的。 1 2 3 课题的提出 业务应用的多样化及实时性要求，服务提供商对互联网的可控制、可管理期 望，归根到底是希望利用互联网提供高质量的满足各种应用的业务。因此，互联 网服务质量( pq o s ) 技术受到人们的关注，成为下一代网络技术的研究热点之 一口 服务质量q o s 指用来表示服务性能之属性的任何组合。为了使其具有价值， 这些属性必须是可提供的、可管理的、可验证和计费的，而且在使用时它们必须 是始终如一的、可预测的、有的属性甚至是起决定性作用的。服务质量的问题可 谓由来已久，从计算机网络诞生之时起，一些有远见的研究者就认识到服务质量 的重要性，已提出了基于客户的性能评价的问题，但因为计算机网络的性能限制， 人们对q o s 的关注只停留在数据流传输中的正确率、吞吐量和延迟等单一服务 质量的评价和控制上。直到2 0 世纪8 0 年代末，随着b i s d n ( b r o a di n t e g r a t e d s e r v i c ed i g i t a ln e t w o r k ) 和a t mfa s y n c h r o n o u st a u s f e rm o d e ) 技术的出现，人们 才开始对q o s 管理和控制进行较为系统的研究。特别是随着互联网商业化的巨 大成功，网络拥塞现象的日益严重，i pq o s 的问题研究更随之深入。i e t f ( i n t e m e t e n g i n e e r i n g t a s k f o r c e ) 于1 9 9 7 年9 月开始正式制定了有关q o s 定义与服务的一 系列r f c 标准，提出了两种i pq o s 服务模型：综合服务( i n t e g r a t e ds e r v i c e s ， i n 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 s ，d i f f s e r v ) 。 q o s 问题是一个涉及用户终端和通信网络的端到端的问题，纵向上包括物理 层到应用层，横向上跨越端到端之间的各个节点设备、各种底层物理技术。q o s 保障技术的研究也包括很多方面，像q o s 体系机构的研究，节点设备的q o s 技 术，网络层面上的路由及流量控制机制等等。本文重点研究了基于m p l s 的服 务质量保证技术。 多协议标签交换( i v i p l s ) 最初并不是作为一个q o s 的解决方案提出的，而 是以一个新的转发机制的角色出现的，来源于思科提出的t a gs w i t c h i n g 结构。 其主要思想是将二层交换和三层路由有机结合，将二层的快速转发引入第三层， 大大提高了路由器的转发性能。但是，随着网络处理器速度的快速增长，m p l s 北京邮电大学硕士研究生学位论文 的快速转发的优势已并不明显。而是其面向连接的特性，良好的流量控制能力以 及v p n 的应用更受到关注，而且，m p l s 可以与q o s 模型实现很好的结合，且 可运行在多种协议之上，m p l s 已成为下一代口网络中保证服务质量的必不可 少的关键技术之一。本文正是在充分理解m p l s 技术的基础上，对其实现服务 质量支持的技术进行了深入研究，包括流量工程目标的路由算法和故障恢复机 制。 1 3 论文的主要工作 本文重点研究m p l s 的流量工程路由算法和故障恢复机制的研究，并取得 以下研究成果： ( 1 ) 在深入研究当前广受关注的流量工程动态路由算法一最小干扰路由算法的 基础上，提出了一种新的最小干扰路由算法，并进行了仿真分析，证明本 算法在性能上得到一定改善。 ( 2 ) 重点研究了m p l s 的重路由故障恢复机制，针对其备用路径的计算负担重 的问题，首先提出一种新的计算备用路径的算法，将图论中的基本回路的 概念引入到备用路径的计算，并在此基础上给出一种基于基本回路的重路 由故障恢复机制，最后对该机制进行了分析仿真，证明该机制有较好的性 能。 1 。4 论文的内容安排 本文后续章节的安排如下： 第二章对i pq o s 体系机构及m p l s 技术进行了简单介绍，并分析了m p l s 支持口q o s 的优势，及目前m p l s 的q o s 热点技术。 第三章重点研究了流量工程动态路由算法。详细介绍了本文提出的新的最小 干扰路由算法的研究背景及实现流程，并给出了仿真结果。 第四章重点研究了m p l s 网络的故障恢复机制。分析比较了各种故障恢复 机制的优缺点及当前的主要研究热点，重点分析了重路由故障恢复机制面临的问 题，对本文提出的新的备用路径的计算方法进行了详细分析与介绍，并在此基础 上给出一种基于基本回路的重路由故障恢复机制，对该机制进行了分析仿真。最 好，简单分析了新的备用路径的计算方法在其他故障恢复机制中的应用。 第五章对本文进行了总结与展望。 北京邮电大学硕士研究生学位论文 2 1 引言 第二章m p l s 与i pq o s 研究 i pq o s 的研究由来已久，并且随着互联网的研究不断深入，各研究组织根 据不同的研究角度，给出了不同的定义，但研究的目标均是有效地为用户提供端 到端的服务质量控制或保证。i e t f 于1 9 9 7 年9 月开始正式制定了有关q o s 定 义与服务的一系列r f c 标准r 1 i 2 3 1 ，并提出了两种i pq o s 服务模型：综合服务 ( i n t e g r a t e ds e r v i c e s ，i n t s e r v ) 4 1 和区分服务( d i f f c r e n t i a t e ds e r v i c e s ，d i l l s e r v ) 5 1 。广大研究者均基于该服务模型之上，对具体的q o s 技术从设备层面，到服务 模型的体系结构方面做了大量的工作。 m p l s 6 1 p 8 1 技术的提出，使得i pq o s 模型的实现更为方便，特别是其自身 具备的一系列优良特性，使其成为实现i pq o s 的必不可少的关键技术之一， m p l s 的服务质量保证技术一直为研究者所关注也就不足为怪。本章首先对p q o s 体系结构进行简单介绍，然后从m p l s 技术的发展过程起，简单分析了该 技术支持q o s 的优点，最后对基于m p l s 的服务质量保证技术进行了简单概括。 2 2i p q o s 的定义 i pq o s 就是i p 网络的q o s ，q o s 指网络单元( 例如，应用程序，主机或路 由器) 能够在一定级别上确保它的业务流和服务要求得到满足。q o s 并没有创造 带宽，只是根据应用程序的需求以及网络状况来管理带宽。i pq o s 有一套性能 参数 2 1 ，主要包括：可用性、吞吐量、时延、时延变化( 包括抖动和漂移) 和丢失， 下面详细叙述。 - 可用性 是当用户需要时网络即能工作的时间百分比。可用性主要是设备可靠性和网 络存活性相结合的结果。对它起作用的还有一些其他因素，包括软件稳定性以及 网络演进或升级时不中断服务的能力。 - 吞吐量 是在一定时间段内对网上流量( 或带宽) 的度量。对i p 网而言可以从帧中继网 借用一些概念。根据应用和服务类型，服务水平协议( s e r v i c el e v e la g r e e m e t s ， s l a ) 可以规定承诺信息速率( c o m m i t t e di n f o r m a t i o nr a t e ，c m ) 、突发信息速率 ( b u r s ti n f o r m a t i o nr a t e ，b m ) 和最大突发信号长度。承诺信息速率是应该予以严 北京邮电大学硕士研究生学位论文 格保证的，对突发信息速率可以有所限定，以在容纳预定长度突发信号的同时容 纳从话音到视像以及一般数据的各种服务。一般讲，吞吐量越大越好。 时延 指一项服务从网络入口到出口的平均经过时间。许多服务，特别是话音和视 像等实时服务都是高度不能容忍时延的。当时延超过2 0 0 2 5 0 毫秒时，交互式会 话是非常麻烦的。为了提供高质量话音和会议电视，网络设备必须能保证低的时 延。产生时延的因素很多，包括分组时延、排队时延、交换时延和传播时延。 传播时延是信息通过铜线、光纤或无线链路所需的时间，它是光速的函数。在任 何系统中，包括同步数字系列( s y n c h r o n o sd i g i t a lh i e r a r c h y , s d h ) 、异步传输模式 ( 删) ，传播时延总是存在的。 时延变化 是指同一业务流中不同分组所呈现的时延不同。高频率的时延变化称作抖 动，而低频率的时延变化称作漂移。抖动主要是由于业务流中相继分组的排队等 候时间不同引起的，是对服务质量影响最大的一个问题。某些业务类型，特别是 话音和视像等实时业务是极不容忍抖动的。分组到达时间的差异将在话音或视像 中造成断续。所有传送系统都有抖动，只要抖动落在规定容差之内就不会影响服 务质量。利用缓存可以克服过量的抖动，但这将增加时延，造成其他问题。漂移 是任何同步传输系统都有的一个问题。在s d h 系统中是通过严格的全网分级定 时来克服漂移的。在异步系统中，漂移一般不是问题。漂移会造成基群失帧，使 服务质量的要求不能满足。 - 丢失 不管是比特丢失还是分组丢失，对分组数据业务的影响比对实时业务的影响 都大。在通话期间，丢失一个比特或一个分组的信息往往用户注意不到。在视像 广播期间，这在屏幕上可能造成瞬间的波形干扰，然后视像很快恢复如初。即便 是用传输控制协议( t c p ) 传送数据也能处理丢失，因为传输控制协议允许丢失的 信息重发。事实上，一种叫做随机早丢( r a n d o me a r l yd e t e c t i o n ，r e d ) 的拥塞控制 机制在故意丢失分组，其目的是在流量达到设定门限时抑制t c p 传输速率，减 少拥塞，同时还使t c p 流失去同步，以防止因速率窗口的闭合引起吞吐量摆动。 但分组丢失多了，会影响传输质量。 2 3i p q o s 服务模型 服务模型，就是指一组端到端的q o s 功能，最基本的服务模型有三种：尽 力而为服务模型：综合服务模型：区分服务模型。尽力而为服务模型是当前互联 网的缺省服务模型，它是一个单一的服务模型，也是最简单的月睫务模型，对时延、 北京邮电大学硕士研究生学位论文 可靠性等性能不提供保证，网络尽最大可能发送报文。后两种服务模型为q o s 服务模型，可提供多种q o s 保证的服务。 2 3 1i n t s e r v 服务模型 i n t s e r v t 4 是一个综合服务模型，它可以满足多种q o s 需求。它以每个流( 单 独或聚集的) 为基础，提供两种端到端的面向实时传输的服务： 一质量保证服务：提供保证的带宽和时延限制来满足应用的需求。 - 负载控制服务：保证即使在网络过载的情况下，能对报文提供近似于网 络未过载类似的服务，即在网络拥塞得情况下，保证某些应用的报文低 时延和高通过。 i n t s e r v 依靠资源预留消息r s v p ( 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 ) 9 1 提供q o s 协商机制，逐节点的建立或拆除每个数据流的路径状态和资源预留软状态，依靠 接纳控制决定链路或网络节点是否有足够的资源满足用户的资源预留请求，依靠 传输机制将p 分组分类成不同的传输流，并根据每个流的状态对分组的传输实 施q o s 路由、传输调度等控制。下面说明一个资源预留过程。 ( 1 ) 发送端在发送报文前，需要向网络申请特定的服务。这个请求通过信令完 成，发送端将确定发送的数据流所需的带宽、延迟和延迟抖动等指标包含 在r s v p 协议的p a t h 分组中发给接受端。 ( 2 ) 当网络的某一路由器接收到p a t h 分组，将p a t h 分组中路径状态消息存 储起来，该信息中描述了p a t h 分组的上一级源地址。 ( 3 ) 当接受端收到p a t h 分组后，沿着和p a t h 分组获取的源路径相反的方向 发送一个r e s v 分组。该r e s v 分组包含为数据流进行资源预留所需要描 述的流量和性能期望等q o s 信息。 ( 4 ) 当某个路由器收到r e s v 分组后，通过接纳控制来决定是否有足够的资源 满足q o s 需求。如果有，进行资源预留，并存储相关信息，将r e s v 分组 转发给下一个路由器；如果没有足够的资源，则拒绝该请求，返回接受端 一个错误信息。 ( 5 ) 如果源端收到r e s v 分组，则表明数据流的资源预留成功，开始发送数据。 ( 6 ) 数据发送完毕后，路由器可以释放先前设置的预留资源。 应用程序开始报文后，要将报文控制在参数描述的范围之内，一旦网络确认 为应用程序的报文分配了资源，则只要应用程序的报文控制在流量描述的范围 内，网络将承诺满足应用程序的q o s 需求。而网络为每个流维护一个状态，并 基于这个状态执行报文的分类、流量监管、排队及其调度，实现对应用程序的承 诺。 北京邮电大学硕士研究生学位论文 2 3 2d i l l s e r v 服务模型 d i f f s e r v q 是一个多服务模型，可以满足不同的q o s 需求。它是在i n t s e r v 模型 的发展遭遇到巨大的障碍时应运而生的，其目标在于简单有效，满足实际应用对 可扩展性的要求，与i n t s e r v 椎l 比，简化了网络内部节点的服务机制和服务对象， 在网络内部节点只进行简单的调度转发，而流状态信息的保存与流监控机制的实 现等只在边界节点进行，内部节点是状态无关的，另外服务对象时流聚集而非单 流，单流信息只在网络边缘保存和处理。 具体而言，边界节点根据用户的流规定和资源预留消息将进入网络的单流分 类、整形、聚合为不同的流聚集，这种流聚集信息存储在每个口包头的d s 标记 域中，称为d s 标记( d i f f e r e n t i a t e ds e r v i c e sc o d e p o i n t ，d s c p ) 0 0 ，内部节点在 调度转发口包时根据包头的d s c p 选择提供特定质量的调度转发服务，其特性称 为逐跳行为( p e r - h o p b e h a v i o r ，p i - i b ) ，这样边界节点和内部节点通过d s c p 协 同起来提供特定服务质量的服务。 i e t f 定义了1 4 个标准的p i - i b 1 1 【1 2 ，包括尽力而为( b e s t e f f o r t ，b e ) p i - i b ， 快速转发( e x p e d i t e df o r w a r d i n g ，e f ) p h b ，以及1 2 个有保证转发( a s s u r e a f o r w a r d i n g ，a f ) 的p h b 。尽力而为的p h b ，即内部节点无需进行特殊的处理； 快速转发的p h b ，用于延迟很小、丢包率低的流量；1 2 个有保证转发( a f ) 的 p h b 按照队列号和丢弃优先级定义，包含4 个队列，每个队列三个优先级，共1 2 个a fp i - i b 。 d s c p 与p h b 的映射关系见表2 1 表2 1d s c p 与p h b 映射关系表 p h bd s c pp h bd s c pp h bd s c p d e 0 0 0 0 0 0 a f l l 0 0 1 0 1 0a f 3 l 0 1 1 0 1 0 e f1 0 1 1 1 0a f l 20 0 1 1