（计算机应用技术专业论文）主动网络中按需服务质量确保路由的研究与实现.pdf

东南大学硕上论文 主动删络中按需服务质量确保路由的研究与实现 摘要 在传统i p 网络中，o o s 路由算法面临的问题有：对两个以上相互独立的参数提出要求 时，容易导致n p 一完全问题；现有的o o s 路由算法往往只是针对某些特定类型的网络应用； i p 网络不能同时承载多种0 0 s 要求不同的网络应用等等。这些问题有待在主动网络中解决， 原因是主动网络为用户提供了更加灵活的网络平台，加速了网络更新的速度，对各种新型网 络应用提供灵活有效的支持。主动网技术的实质是在传统网络功能( 存储一转发) 的基础上 增加了计算能力( 存储一计算一转发) ，使得主动网络节点不仅具有传统路由的转发功能， 而且可以分析用户定制的策略( 主动代码) ，以控制数据的传输。 本论文主要研究了i p 网络中q o s 路由算法以及在主动网络中如何按用户制定的q o s 需 求选择路由的问题，提出了按需0 0 s 路由算法，并基于主动网络设计并实现了相应的原型 系统。本论文的研究和实践工作主要包括以下儿个方面： ( 1 ) 分析了当前i n c e m e 上的基本路由算法和q o s 路由问题，重点对多约束路由算法进 行了探讨。指出应用的多样化和快速增氏对网络提出了各自不同的q o s 服务保证要求，在 传统网络中各种q o s 路由算法又难以灵活部署和共存实现。 f 2 1 对主动网络技术进行了研究分析，包括主动网络的体系结构、实现方法以及主动网 络封装协议a n e p 。对国内外主动网络方向的研究成果进行了细致分析，探讨了主动网络的 灵活的定制服务方法。 ( 3 ) 描述了q o s 路由网络模型，并基于主动网络环境，提出了两种路由计算模式的q o s 路由算法：请求计算方式的q c a r 算法和预计算方式的d a q r 算法。设计了主动路山器的 结构框架，包括路由计算模块和基本q o s 策略库，并对主动报文( c a p s u i e ) 的格式进行了 扩展以支持算法实现。 ( 4 ) 深入研究了主动网络中的执行环境a n t s ，分析了其中的c a p s u l e 编程模型、主动 节点机制、代码分发机制，以及路由和安全问题。以此为基础实现了q c a r 算法验证原型 系统。原型系统实现了依据应用定制的q o s 保障需求和策略进行主动路由选择。 本论文研究内容米源于江苏省自然科学基金重点项目( b k 2 0 0 1 2 0 5 ) “高性能网络路由 器交换系统的算法与协议研究”中关于服务质量可定制主动路由子课题。2 0 0 4 年l o 月，项 目已进行验收和鉴定。 关键词：q o s 路由，主动网络，按需q o s 路由算法，a n t s 东南大学硕士论文 主动涮络中按需艨势质量确保路由的研究与实现 a 1 6 i s 鼍r 建e 量 k 妇嚣a d 主畦程蠢重pn e 黯。嫩，也。即b l 鼬瓤e d 撼q o sr 。h 涵ga l g o 瞧翻i sa s 南l l o w s ，赫垃y w h i l ec o n s i d e r i n gm ed e m a n do ft w oo rm o r es e p a r a t eq o sp a r a m e t e r s ，i ti sa p tt oc a u s e n p c o m p l e t ep r o b l e 肌s e c o n d l me x i s i t l n gq o sr o u t i i l ga l g o t h m sa r ej u s ta d a p tt o 踯e c i n c n 文w o 矗 p l i c a 矗o n sw h 雏sm o f e ，pn # t w o r kc 黼ts i m u l t 8 n e 硅ys e r v e 盎e 蠢j 舞矗e n tn e t w o 浓 a p p l l c a d o n sw i t he a g hd i 行b r e n tq o sr e q u i r c m e n t s _ r h e s ep r o b l e m sr e m a i nt os 0 1 v ei nt h ea c t l v e n e t w 破，也e e a s o ni st h a 主a c t i v en e t w o r kh a so 丘皓r e da 埘o e 丑e x i b l en e t w o r k 势l a 蛭b r m 蜘u s e l a c c e l e r a t et s p e e dt h a tt h en e t w o r ku p g r a d e s ，o 船rg e x 谗l ea i l de 腧c t i v es u p p o r tt 。v a f i o u s k i n d so fn e w t y p en e t w o r ka p p l i c a t i o n t h ee s s e n c eo fa c t i v en e t w o r kt e c h n o l o g yi s 山砒i t i n 瓣d 。c o 臻p h i n g h n e t i 。ni n 辩氇e 秘e l w o 虫，a 珏ds e r v 。m o d # a r ee 魏8 n g e df b 臻s 姆f 。一f 嘶瓤畦耙 s t o r e c o m p u t e f o n v a r d a c d v en e t w o r k sn o d e sn o t 靠t i yh a 8t h ef l l n c n o no fa 订旨d i t i o n a lr o u t c s ， a n dc a na n a l v s eu s e ，sc u s t o 埘z e dt a c n c s ( a c t i v ec o d e ) 、i no l d e rt 0c o n t r o lt h e 虹a n s m i s s i o no f 也e d a t a t h l st h e s i ss t u d i o ss o m eq o sr o u t i n ga l g o r i t i l m si ni pn e t w o r k ，a n dt h ep r o b l e mo fh o wt o c o 鞲攀u 捃sr o u 持f o fa p p l 渤矗锄s b a s 晓姐如e i fq o sd e m a n d s 毓n dp 。1 i d e si n8 c t i n e t w o 出。b a s e d o na c t i v en e w o r kt e c h n o l o g i e s ，w ep f o p o s oaq o s e u s t o m i z e da c t i v er o u t i n ga l g o r i 血mw h i c hi s c a l l e dq c a r ，a i i dc o “亡s p o n d i n g l yi m p l e m e n tap m t o t y p ei na c t i v en e t w o r ko n v i r o n m o n t t h e f e s c 鑫h 踩dp 豫e 斑f ew o r ko f 也至s 氇。矗s 泌e l 疆如疆毽魁l l o w 撼g 辩v 豇a l 辩s 辩l ： ( 1 ) h a v ea n a l y s e db a s i cr o u t ca i g o “c h ma n dq o sr o u t ep r o b l e mi ni n t e m e t ，a n dd i s c u s s e d 珈o r ea b o u tm u l t i - c o n s t r a i 聃dr o u t ca l g o r i t h 娃lm a k op o i n to u tt h a tw j t ht h ed i v e r s i 矗c a d o na n df a s t d c v e l o p m e n to fn e t w o 瓜a p p l i c 鑫t l 。n s ，n e t w o 矗s h o u l dp i v 瓣ean 。wa 畦嚣o x i b l ea p p 圭o a c ht 。 m e e ta p p l i c a “o n s q o sd e m a n d s 2 ) h 靠v er e s e a 辩h e d a ! l d a n a l y s e dt b e 娃v en e t w 删( t e c 弧o l o g y ，i n c l u d i n g8 y s 妇n a i c h i t e c t l 旺o ，i 瑚p l e m e n t a t i o nm e t h o da n da c 矗v en e t w o r ko n c a p s u l 8 t i o np r o t o c o i ( a n e p ) ，a i l d a n a l y s e dt h ea c h i e v e m e m si nt h ed o m e s n ca r i dj m e r n a t i o 眦l 嚣c h v en e t w o r kr e s e a r c hf l e l d s ( 壬毛a v ed e s c r 主b 醚囊en o t w o 糸翔o d e lo f q o s 船“鞋醒b a s e d 雒a c 量h 津n w o 基鞠v i 辩瓣l e 珏t ， w op r o p o s e dt 、v oq o sr o u t i n ga l g o r i t t l m s ，o n ei sq c a r ( a s kf o rc o m p u t ep a t l l ) a r i da n o t h e ri s d a q r ( c o m p u t ep a 血i na d v a n c e ) 。w ed e s i g n e dt h ea r c h i 姆c t mo ft h ea c r 。u t 盯戚n g u t ec o l l l p 撒em o d h 耗a n db a s i cq o sp o l i c yl i h 酣y ，a n d 。x p a n dt h ec a p s u l ef o 册a t of 研t b e i m p l e m e n to f t h ea l g o r i t h m 4 ) h 8 s t n d 主越沁眦i 增e x e c u 士如ne n 证r o 巍联蜷嫩a n t s ，诬e l h d i 鹋c a p s u l e 咿g m 【舯i n g m o d u l e ，a c t i v en o d em e c h a n i s m ，c o d ed i s 缸b u t i o na n dr o u t es e c u r i t yp r o b l e m 、b a s e do na b o v e r e s e a r c hr e s u l t s ，w eb u i l dap r o t o t y p e ，w h i c hc 鲫c o l p u t e sr o u t ef 研a p p l i c a t i o n sa c c o r d l n ga s 壤e 拓q o s 如糯毫魏出基聪p o l i e 溉囊v e l ya 莪d 叠e x 谗 m t h l s 出e s i s sr e s e a 托h n t e n t ss t e m 如m 也en a m m ls c i e n c e 灿dp 画e c t ( b k 2 0 0 1 2 0 5 ) i i l 嚣鞘g s up r o v 讯c e ，b a 礅e d 吼e 搽g 嘶她l sa n dp r o t o c o l su 酬妯b 主馥p 。舶n n a n c 。n e t w o r kr o u 矗g 8 y s t e m ”，w h j c hh a sb e e nc h e c b d 姐da c c e p t e d0 no c t o b e r2 0 0 4 k e yw o r d s ：q o sr o u t m 岛a c t j v en e t w o r k ，q o s - c u s t o r i l i z e dr o u n n ga l g o r i t h m ，a n t s i i 东南大学硕士学位论文 东南大学学位论文 独创性声明及使用授权说明 一学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人己经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用的材料。与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示谢意。 签名孝觞、日期：丝出生 二关于学位论文使用授权说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电 子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 签名 夺骗、 导师签名f 1 期 缈o 心 t s 东南大学硕士论文主动网络中按需服务质量确保路由的研究与实现 1 1 研究背景 第一章引言 j n t e m e t 自2 0 世纪6 0 年代末出现以来，一直在以惊人的速度增长。同时，伴随着多媒 体技术的飞速发展，工n t e m e t 已逐步由单一的数据传送网向数据、语音、图像、视频等多媒 体信息的综合传输网演化。 多媒体与网络技术结合的应用，如视频点播( v i d e o o n d e m a n d ，v o d ) ，i p 电话( v 0 i c e o v e fi p v o l p ) 、远程教学的不断涌现，使得传统的公平对待每一业务的】_ p 网络服务质量 ( o u a l i t yo f s e r v i c e ，q o s ) 机制再也不能满足应用的需求。 以i p 技术为基础的1 1 1 t e m c t 网络所支持的基本服务模型只有种：即“尽力而为( b e s t e 肋r t ) ”模型，在这个模型中，网络平等地处理所有数据包，尽最大努力转发数据包。网络 的接入率与网络吞吐量是其主要的优化对象，然而对应用却不能提供诸如报文丢失率、网络 带宽、延迟、延迟抖动等服务保证。实时多媒体应用要求网络提供低延迟、低延迟抖动及高 带宽。这就需要网络能够根据应用的要求进行资源的分配和路由的选择。 网络服务质量o o s 被用来说明网络服务的“良好”程度。目前的网络研究主要通过两 个途径提高o o s ：一个途径是节点控制：另一个途径是整网或局部网络控制。节点控制在单 节点或单链路完成，主要控制业务对单节点共享资源的占j j ，包括共享的链路、缓冲区、处 理器资源。节点控制主要的策略包括：业务流整形、业务调度、节点缓冲区管理。整网或局 部网络控制通常通过对路由与信令的控制达到对业务流或业务连接在网络中的传输的直接 控制。因为路由直接关系到网络性能，所以q o s 路由成为解决q o s 问题的一项关键技术。 1 1 1o o s 路由问题 服务质量问题是目前网络的热点问题，关于如何在路由解决方案中融入服务质量保证的 研究正在进行中。 为了满足用户对不同o o s 的需求，i i l t e m e t1 二程任务组( i e t f ) 先后提出了集成服务 资源预留模型( i i l t s e r v 瓜s v p ) 、区分服务模型( d i f r s e r v ) 以及从流量工程角度提出的多协 议标记交换( m p l s ) 。这些服务模型都需要一个与之相适应的q o s 路由机制和算法，为不 同的服务质量请求分配不同的路由。 0 0 s 路由是指根据网络上可利用的资源和流( n o w ) 的q o s 需求决定流的路由机制。 o o s 路由的提出是为了获取在服务提供者和用户应用之间的质量与数量上的行为保证。在 o o s 路由下，报文流的路径将被网络中的资源可用性和流的q o s 需求所决定，当前q o s 路 由问题研究的主要目标是： ( 1 ) 动态决定合理的路径。q o s 路由能动态地从所有可能的选择中挑选一一条满足流的 东南大学硕十论文主动网络中按需服务质量确保路由的研究与实现 o o s 需求的路径，这个路径是由一些度量值( m e t r i c s ) 决定的。 ( 2 ) 优化资源的利用率。如果一个网络的状态由q o s 路由机制所决定的话，能从整体 上来提高网络的有效利用率，这是网络工程中基本的因素。 ( 3 ) 支持资源预留。对报文流提供端到端的确保( 延迟、抖动、错误率等) ；对单点投 递，寻找一条路径满足两终端用户间连接的资源需求；对多点投递，建立一棵树，顶点是数 据的发送方，分支是满足顶点与各叶结点( 数据的接收方) 间用户连接q o s 需求的路径。 在确定了报文流的q o s 路径后，要对该路径上所需要的资源进行预留。 o o s 路由中研究重点有三个方面：度量参数的选择问题、寻路问题和路由信息不准确问 题。目前，0 0 s 路由研究中需要解决的主要难点包括： 1 )n p c o r n p l e t e 问题。同时对两个以上相互独立的参数提出要求时，这个问题就是一个 n p c o m p l e t e 问题。实时应用往往会对延迟，延迟抖动，带宽，丢失率，业务代价等多 个参数同时提出性能要求，例如，实时多媒体业务会对延迟和延迟抖动同时提出要求。 这些参数相互独立时选择满足多个参数限制的路由就成为n p c o i n p l e t e 问题。 n p c o m p l e t e 问题直接关系到路由算法的可实现性。 2 )多业务并存。同时承载多种q o s 要求不同的业务时，网络性能优化困难，扩展困难， 尤其是o o s 和尽力而为业务共存时，很难确定最优的操作点。 3 )节点状态信息的存储量大。q o s 路由中，节点需要记录的状态参量将增多，如果状态信 息的存储随网络节点个数的增加而指数性增加，将限制网络的扩展。 4 )信息不准确。传输负荷的抖动、新连接的加入取消等都可能导致网络状态变化。这些 变化因素直接影响全网状态信息的准确性，同时也直接影响算法的性能。 这几点中，第1 ) ，2 ) 点是参数选择所面临的，第3 ) 点在寻路过程中需要考虑，第4 ) 点是路由信息不准确中主要解决的问题。 1 1 2 主动网技术及其解决q o s 路由问题的优势 主动网( a c t i v e n e t w o r k ，a n ) 是美国国防部高级研究计划署( d a r p a ) 于1 9 9 4 1 9 9 5 年在关于未来网络系统发展方向的讨论中提出的。主动网络方案是：使网络节点不仅能转发 报文而且可以通过执行附加程序来对报文进行处理。整个网络上的节点也都是可以编程，可 以执行用户定义的报文处理程序。主动网络是相对于现有网络而言的，现有的网络由于不对 报文进行处理或计算，原封不动地转发用户数据是它们的宗旨，因此称之为被动网络( p a s s i v e n e t w o 出) 。相比之下，在主动网络中的路由器和交换机可以对网络报文进行用户自定义的计 算。概括起来主动网络具有如f 一些特点： 可编程性：主动网络在传统网络功能( 存储一转发) 的基础上增加了汁算功能( 存储， 计算转发) ，网络节点不仅具有传统路由的转发功能，而目允许用户向网络节点插入定 制的程序，以便修改、存储或重定向网络中的数据流，为分组的转发或分组的进一步处 理提出建议，这种计算功能可以通过编程定制。 可移动性：在网络中传输的主动式数据包可以携带执行代码，在流经的节点执行。 东南大学硕士论文主动网络中按需服务质量确保路由的研究与实现 可扩展性：主动网络为用户提供更加灵活的网络平台，从而加速网络更新的速度，对各 种新型业务提供灵活有效的支持。 1 2 研究现状 从应用背景看，目前的q o s 路由的研究可以分为三个方面：单播路由( u n i c a s tr o u t i n g ) ， 多播路由( m u l t i c a s t r o u t i n g ) 和a d h o c 路由。在这三个方面的研究中，度量参数选择问题、 寻路问题和路由信息不准确问题，是首要解决的基本问题，也是o o s 路由中的研究重点。 国内外关于主动网技术的研究很多，主要集中于主动网络的体系结构、主动网的执行环 境、主动多播、主动拥塞控制、网络管理、主动路由及安全等方面的研究。主动网中实现 q o s 路由研究涉及不多。英国索尔福德大学的m o h a m e d t a s l r 在“如p ，垤m f 4 c “w r 。“f 加g 扣r 仰。“f 馏q d sd 口月出”【i 文中通过研究目前各种动态路由技术，提出了一个基于主动网 的智能主动路由系统结构，该体系结构支持o o s 需求。因斯布鲁克大学的m i c h a e lw e l z l 等 在“爿n 却m 口曲f 。凡蹦西kq o sr d “f 加gw 泐4 c 盯v e p 舢。出”文中指出，主动网在q o s 支持上显得特别有效，并提出了一种主动q o s 路由算法a r q ，仿真试验表明在各种网络条 件和流量特性下都有良好表现。国内在此方面没有具体研究。 随着人工智能的发展，许多相关的技术也开始应用在网络路由算法上：如应用退火 h o p f i e l d 神经网络算法，采用新的冷却机制进行m o s p f 中的最短路径计算”j ；用遗传算法 解扶q o s 单播和组播路由问题【4 】：用h 0 p 6 e l d 神经网络计算可以满足多种约束条件的q o s 路径【5 】o 在主动网络中实现q o s 路由，相比传统的i p 网络有以r 一些优势： 主动网络使主动节点具有计算能力，用户具有定制能力，这使得个体用户、网络管理者 或网络所有者可以很方便地控制它们的数据穿越网络的路径。 用户可以灵活地定义q o s 参数及体现用户q o s 需求的路由选择计算公式。 用户对于o o s 的要求在网络难以完全满足的情况下，可以通过用户定义的折中策略来 实现折中方案( 仃a d eo f f ) ，从而避免无效的选路过程，提高o o s 路由算法的有效性。 根据用户对q o s 要求的不同实现在主动网络中多个o o s 路由算法的共存。 更适合实现分布式的路由算法。 新的路由机制可以快速部署。 1 3 论文内容及章节概述 本论文的研究内容与章节安排如下： 第一章对论文的研究背景、国内外研究现状和全文的内容和安排进行了综述。 第二章分析了当前i n t e m e t 上的基本路由算法和o o s 路由问题，重点对多约束路由算法 进行了探讨。 3 东南大学硕士论文主动唰络中按需服务质量确保路由的研究与实现 第三章主要介绍了主动网络技术，包括主动网络体系结构、主动网络的实现方法以及用 于封装主动厩i 络数据包的a n e p 协议，摄后对国内外主动网络领域的研究成果进行了细致 分析，探讨了主动网络的灵活的定制服务方法。 第四章描述了o o s 路由网络模型，并基于主动网络环境，提出了两种路由计算模式的 0 0 s 路由算法：请求计算方式的q c a r 算法和预计算方式的d a q r 算法。 第五章在主动网络环境中，基于主动网络执行环境a n t s2 o 实现了按需q o s 选路原型 系统。原型系统主要实现了对系统定义的5 种固定数据类型以及自定义数据类型的q o s 策 略选路。 第六章对原型系统进行测试，测试包括：( 1 ) 主动报文在传输路径上的总延迟( 以0 s p f 算法作为对照) ：( 2 ) 主动报文是否严格按照用户策略进行路由选择，选路结果是否符合用 户o o s 要求。 第七章对全文进行总结，并对f 一步工作进行了展望。 4 东南大学硕士论文主动网络中按需服务质量确保路由的研究与实现 第二章q o s 路由问题研究 目前，在高速网络中按用户的需求提供o o s 控制是一个普遍的要求，也是i i l t e m e t 发展 的重要挑战。网络研究主要通过两个途径提高o o s ，一个是节点控制；另一个是整网或局部 网络控制。节点控制在单节点或单链路完成，主要控制应用对单节点共享资源的占用，包括 共享的链路、缓存区、处理器资源。整网或局部网络控制通常通过对路由与信令的控制达到 对应用数据流在网络中传输的直接控制因为路由直接关系到网络性能，所以q o s 路由成 为解决o o s 问题的一项关键技术。 2 1 基本路由算法 2 1 1 路由算法分类 2 1 - 1 1 静态路由与动态路由 静态路由是在路由器中设置的固定路由表。除非网络管理员干预，否则静态路由不会发 生变化。静态路由般用于网络规模不火、拓扑结构固定的网络中。其优点是简单、高效、 可靠。在所有的路由中，静态路由优先级最高。当动态路由与静态路由发生冲突时，以静态 路由为准。静态路由的缺点是不适用于现在的大型、易变的网络。 动态路由是指网络中的路由器之间相互通信，传递路由信息，利用收到的路由信息更新 路由器表的过程。它能实时地适应网络结构的变化。如果路由更新信息表明发生了网络变化， 路由选择软件就会重新计算路由，并发出新的路由更新信息。这些信息通过各个网络，引起 各路由器重新启动其路由算法，并更新各自的路由表以动态地反映网络拓扑变化。动态路由 适用于网络规模大、网络拓扑复杂的网络。 静态路由和动态路由有各自的特点和适用范围，动态路由算法可以在适当的地方以静态 路由作为补充。 2 1 1 2 单路路由和多路路由 一些复杂的路由协议支持到相同目的地的多条路径，这些多路算法允许可多路复用，单 路算法只选择一条路由。多路算法的优点是能够提供较好的网络负载均衡，合理地使用网络 资源。 2 1 1 3 平坦的路由和分级的路由 一些路由协议在平坦的空间里运作，其它的则有路由的层次。在平坦的路由系统中，每 个路由器与其它所有路由器是对等的。在分层次的路由系统中，一些路由器构成了路由主干， 5 东南大学硕士论文土动网络中按需服务质量确保路由的研究与实现 数据从非主干路由器流向主干路由器，然后在主干上传输直到它们到达目标所在区域，在这 里，它们从最后的主干路由器通过一个或多个非主干路由器到达终点。 路由系统通常设计有逻辑= 肯点组，称为域、自治系统或区间。在分层的系统中，一些路 由器可以与其它域中的路由器通信，其它的则只能与域内的路由器通信。在很大的网络中， 可能还存在其它级别，最高级的路由器构成了路由主干。 分层路由的主要优点是它模拟了多数公司的结构，从而能很好地支持其通信。多数的网 络通信发生在小组中( 域) 。因为域内路由器只需要知道本域内的其它路由器，它们的路由 算法可以简化，根据所使用的路由算法，路由更新的通信量可以相应地减少。 2 1 1 4 主机智能路由和路由器智能路由 一些路由算法假定源结点米决定整个路径，这通常称为源路由。后来把源节点路由器决 定整个路径的方法，也称为源路由。其它路由算法假定主机对路径一无所知，在这些算法中， 路由器基于自己的计算决定通过网络的路径。前一种系统中，主机具有决定路由的智能，后 者j l j j j 为路由器具有此能力。 主机智能和路由器智能的折衷实际是晟佳路由与额外开销的平衡。主机智能系统通常能 选择更佳的路径，因为它们在发送数据前探索了所有可能的路径，然后基于特定系统对“优 化”的定义来选择最佳路径。然而确定所有路径的行为通常需要很多的探索通信量和很民的 时间。 2 1 _ 1 5 域内路由或域间路由 一些路由算法只在域内工作，其它的则既在域内也在域间工作。这两种算法的本质是不 同的。其遵循的理由是优化的域内路由算法没有必要也成为优化的域问路由算法。 2 1 1 6 链路状态或距离矢量路由 链路状态算法( 也称短路径优先算法) 是把路由信息散布到网络的每个节点，不过每个 路由器只发送路由表中描述其自己链接状态的部分。距离向量算法( 也叫做b e l l m a l l f o r d 算法) 中每个路由器发送路由表的全部或部分，但只发给其邻居。也就是说，链接状态算法 到处发送较少的更新信息而距离向量算法只向相邻的路由器发送较多的更新信息。 2 1 2d i j k s t r a 最短路径算法 我们用加权图g = 缈，e ) 来表示研究的网络，其中矿表示图g 中所有节点( 网络中交 换机、路由器或主机) 的集合，e 表示途中所有的边界( 链路) 的集合。从顶点“到顶点v 的边的权值表示为w 0 ，v ) 。一条边的权值度量方法可以包括跳数、链路带宽、平均传输延 迟或者它们的组合。d k s t r a 算法使用一种权值度量方式米计算最短的路径，算法流稃如下。 6 东南大学硕士论文主动网络中按需服务质量确保路由的研究与实现 d q k s t r a ( g ，w ，j ) g ：图形，w ：边的权值，5 ：源节点 6 昭觑 d v 】表示到目前为止从s 到v 的最短路径的权值 p n 圳p 怯示在最短路径中v 的前一节点 v v 矿，d 【v = m ，p 口如【v 】= n 玎； d b = o ；s = a ；丁= 矿； 鼢f 把仃o ) 如 取d b 】为最小值的“为t 中的一个顶点。 丁= 丁一函ks = s u “ ； 对于“相邻的每个节点v ： 矿0 v 】 d l 】+ w 0 ，v ” d 卜】= d 【“】+ w ( “，v l p 砌【v = “； p n j 通过跟踪p a 胁卜 ，可以获得从s 到v 的最短路径的顶点序列。d 【v 】最终值即为从s 到 v 的最短路径的权值。 2 1 3 距离矢量路由算法 距离矢量路由也称为“b e l l i l l a l l f o r d 路由”，它让每个路由器维护一张表( 即矢量) ，表 中给出了到每个目的地己知的最佳距离和路线。在此类路由算法中，每个路由器维持有一张 子网中每一个以其它路由器为索引的路由选择表，表中的每一项对应丁- 子网中的每个路由 器。距离度量标准可为跳数、延迟、路径排队长度或者类似的值。 距离矢量路由算法的工作流程如下： ( 1 ) 路由器启动时，对路由表进行初始化，包含所有去往与本路由器直接相连的网络路 径，这些网络路径不经过中间节点，初始路由表中各项的路径氏度为o 。 ( 2 ) 各路由器周期性地向外广播其路由表报文，遇到下述情况之一，对本地路由表的相 应内容进行修改： a )路由器r ，列出的表目在r 。路由表中没有则月，路由表中增加相应表目，其信 宿是毋表目中的信宿，距离为母表明中的距离加l ，下一跳为吩。 b ) r ，去往某信宿的距离+ l ，去往某信宿的距离，说明r 。去往该信宿若经过马， 其路径会更短，则r ，修改本表目，其信宿域不变，距离为r ，中相同信宿表目 的距离值+ l 。 c ) 置去往某信宿的路径经过马，而弓去往该信宿的路径发生如下变化： ( i )r ，的路由表中不再含有去往该信宿的表目，则删除r 。路由表中相应的 表目； 7 东南大学硕士论文 主动网络中按需服务质量确保路由的研究与实现 ( i 1 )r ，的路由表中去往某信宿的距离发生变化，则对足中相应表目的距离 项进行修改，以r ，中距离+ l 取代。 距离矢量路由的主要问题是，网络拓扑改变时算法的收敛慢以及无穷汁算问题，所谓无 穷计算是指节点强迫其它节点单调地增加它们的距离矢量。加速距离矢量收敛的一个流行方 法是水平分裂( s p i i th o r i z o n ) 算法，但水平分裂算法不能解决所有的无穷计算问题。 2 1 4 链路状态路由算法 每条链路具有一套有关q o s 度量准则的被测量状态。如图2 1 所示，链路状态是一个包 含剩余带宽、延迟、和代价的三元组。节点也有状态信息，节点的状态信息可以单独地测量 出米，或者像图2 1 那样合并到相邻链路的状态中。 链路状态= ( 带宽，延迟，代价) 图2 1 网络链路状态 链路状态路由算法的工作流程如f ： ( 1 ) 每个路由器发现它的邻居节点，并知道其网络地址： ( 2 ) 测量到各邻居节点的延迟或者开销； ( 3 ) 组装一个分组以告知路由器刚知道的所有信息； ( 4 ) 将该分组发送给所有其他路由器； ( 5 ) 计算到每个其他路由器的最短路径。 现在各种各样的链路状态路由选择算法得到了广泛的应用，例如在i n t e i m e t 上越来越多 地使用开放最短路径优先( o p e ns h o n e s tp a t h 缶s t ，o s p f ) 协议就是使用链路状态算法的一个 例子。 2 2q o s 路由问题 2 2 1q o s 路由概述 i e t f 已经提出了许多服务模型和机制来满足q o s 需求6 ”，其中比较典型的有：集成服 东南大学硕二 论文 主动网络中按需服务质量确保路由的研究与实现 务资源预留协议( r s v p ) 模型【8 - 9 】、区分服务( d i 踮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 a ll a b e ls w i t c h i n g ) 、流量工程( t r a m ce n g i n e e r i n g ) 和q o s 路由( q o s _ b a s e d r o u n 2 ) 旧“】，其目的都是为了满足应_ h j 的0 0 s 需求，同时有效的利用网络资源。 o o s 路由是近十几年来网络研究的热点问题。i e t f 在r f c 2 3 8 6 【l ”中定义了i n t e m e t 的q o s 路由框架，并在r f c 2 6 7 6 f “1 中对o s p f 协议进行了扩展，以支持q o s 路由。目前国内、外有 众多的研究人员在从事这方面的研究。 r f c 2 3 8 6 对o o s 路由的定义是：“在网络可用资源信息和数据流q o s 要求的基础上确定 数据流路径的路由机制”。q o s 路由不同于“尽力而为”( b e s t e f f b r t ) 路由，q o s 路由通常是 而向连接的，并使用资源预留机制为业务的服务质量提供保证。而“尽力而为”路由可能灶 面向连接的，也可能是无连接的。根据当前网络可用资源的不同，“尽力而为”路由为业务 提供的服务质量会有很大的差别。 o o s 路由的主要目标是：为网络应用选择满足其服务质量要求的传输路径，同时保证网 络资源的有效利用。一般路由选择过程由两个部分组成：寻路过程和节点问路由信息的交互 过程。与传统的尽力而为的路由过程相比，q o s 寻路过程涉及两个方面的问题：一是依据哪 些度量参数作为寻路标准，这里简称为度量参数选择问题；另一个是在寻路标准设定后，如 何找到满足业务需求的路径，并保证数据经由选定路径传输到目的节点，我 j 称之为寻路问 题。路由信息交互过程中，由于链路传输延迟的存在，每个节点获得的其他节点的状态信息 总是具有一定的不准确性，这些不准确性将在一定程度上影响q o s 路由算法的有效性，因 此，路由信息不准确的问题，也是q o s 路由中的一个主要问题。度量参数选择问题、寻路 问题和路由信息不准确问题是首要解决的基本问题，也是q o s 路由中的研究重点。 2 2 2q o s 路由的分类 2 2 2 1 按照路由策略分类 根据网络状态信息的保存方式和路由搜寻方式的不同，路由策略可分为三种：源路由、 分布式路由和层次路由。 源路由 在源路由中，每个节点保存全局的网络状态信息，包括网络拓扑结构信息和每条链路的 状态信息。根据此全局信息，源节点在本地计算出一条合适的路由。然后，在选择的路由上 传送一个控制包通知节点路由上的每个节点，说明其前继者和后继者为谁。每个节点的信 息更新由链路信息协议完成。 分布式路由 路由选择的计算是由分布计算完成的。其路径上的各个节点通过交互控制信息，来完成 路由选择的计算。大多数分布式路由算法需要用距离向量协议或链路状态协议来保持其全局 信息，在每个节点上此信息是以距离向量的形式保存。根据距离向量，路由以接力的形式完 成。 9 东南大学硕士论文主动网络中按需服务质量确保路由的研究与实现 层次路由 物理节点聚合为“组”，而“组”又反复不断地进一步聚合为更高一层的组，从而形成 一种多层次结构。每个物理节点保存了经过聚合的全局信息，此信息包括此物理节点所在组 的详细状态信息和其它组的聚合信息。使用源路由算法来进行路由选择，然后，沿计算得到 的路径传输控制消息来建立连接。当代表逻辑组的物理节点收到此消息时，它将把对应于其 组的链路部分进行扩展，即用物理链路代替其对应的逻辑链路。 三种路由策略的比较和有待解决的问题如表2l 所示： 表2 1 三种路由策略比较 路由簸略优点缺点待解决的问题 集中处理，简单，不产保存全局信息。在大型网可扩容性、信息不确定性 源路由生环路。 络中有很大的传输开销， 对选择路径的影响的研究。 计算开销较大。 可扩容性好。须引入环路控制机制和解多度量约束路由算法的研 分布式路由 决分布计算的终止问题。究：降低通信开销。 可扩容性好抑制环路聚合q o s 参数的实用、有效各种q o s 度量参数的聚台问 层次路由 产生。算法还有待研究。题。 由于以下原因，使源路由不具有良好的可扩容性：通信开销和存储开销随网络规模增加 而增丈；通信开销与本地信息广播频率成正比；计算开销为网络规模的多项式时间，且与连 接清求的频率成正比：全局信息的准确度与网络规模( 或网络半径) 和广播频率成反比。当网 络规模扩大时，其对应的通信开销、存储开销利计算开销都相应的增长。降低网络信息更新 频率并不能解决此问题，因为全局信息的准确度也会随之下降。 分布式算法可以部分解决扩容性问题。例如，基于选择性探测的分布式路由算法可以克 服信息的不精确性问题，从而可以降低网络的通信开销。目前还缺少高效率分布式q o s 路由 算法，特别是在组播( 多播) 传送问题方面。这主要是由于没有详细的拓扑信息和链路信息 可供使用。如果在不同节点的全局信息不一致的话，就有可能产生环路。环路可以通过控制 包到达同一节点两次来检测，但环路将导致路由失败，因为距离向量信息往往不能给出足够 的信息来确定替代路由。 层次路由对扩容性提供了清晰的解决方案。由于每个节点仅保存经聚合的全局信息，远 端网络节点的信息用经过聚合的逻辑节点信息代替，这种聚合信息的规模仅是全局信息规模 的对数函数( 大大缩减) ，因而其具有良好的可扩容性。另外，由于计算是分布式进行的， 因此也具有分布式路由的优点。然而，由于信息聚合会产生附加的不确定性，其算法性能会 随网络规模而急剧降低。因为q o s 路由对网络状态的不确定性比较敏感，故而研究能适应网 络不确定性的路由算法就变得十分重要。另外，由于层次路由是把有复杂拓扑结构的组用一 个逻辑节点代替，因而在做本地计算时，远端节点的具体信息是不可见的，从而不可能精确 计算本地物理节点到远端物理节点的q o s 度量参数值。此问题在涉及多q o s 度量参数约束 】0 东南大学硕士论文主动网络中按需服务质量确保路由的研究与实现 时，将更加复杂。由此，如何对状态信息进行聚合目前还是一个待解决的问题。 2 2 2 2 按照路由服务的节点范围分类 按照路由服务的节点范围区分，路由可以分为两大类：单播和多播。这两类路由问题是 密切相关的。在很多情况下，多播路由可以视为单播路由的推广。 o o s 单播路由 q o s 单播路由的研究，首先涉及4 种基本的q o s 路由问题：( 1 ) 链路约束问题；( 2 ) 链路最优化问题；( 3 ) 路径约束问题以及( 4 ) 路径最优化问题。 以上4 种问题都可以通过改进d i j k s 仃a 算法或b e l l m a nf o r d 算法来实现。而许多q o s 路由问题都可以分解成这四个基本问题”】。q o s 单播组合路由问题可以归纳为以下几类： a ) 链路约束一链路最优化问题( l c l o ) ； b ) 链路多约束问题( m l c ) ； c ) 链路约束一路径约束问题( l c p c ) ； d ) 路径约束一链路最优化问题( p c l o ) ： e ) 路径约束一路径最优化问题( p c p o ) ； f )多路径约束问题( m p c ) 。 其中，前四类问题可用改进的最短路径算法在多项式时间内求解，而后两类问题则是 n p 一完全问题。这两类n p 一完全问题是基于两个假设：q o s 尺度是独立的，并且允许它们 是实数或无界定的整数。假如所有0 0 s 尺度可以取有限的整数值，或这些尺度是与某个公 共尺度相关的，则此类n p 一完全问题就有可能找到多项式解。 o o s 多播路由 q o s 多播路由问题的处理与q o s 单播路由相似，其区别仅在于，在单播路由中对路径 的优化或约束，变为在多播路由中对路由树的操作。 o o s 多播路由问题，基本上可分为：( 1 ) 单链路约束问题：( 2 ) 多链路约束问题；( 3 ) 单树约束问题；( 4 ) 多树约束问题；( 5 ) 链路最优化问题：( 6 ) 树最优化问题。 对于第( 1 ) ( 2 ) 类问题可通过从网络拓扑图中删去不台约束要求的链路的方法来解决。 第( 3 ) ( 5 ) 类问题可在多项式时问内求解。第( 4 ) ( 6 ) 类问题是n p 完全的。 2 2 3 基