（计算机应用技术专业论文）具有不精确状态信息的qos单播路由算法研究.pdf

南京邮电大学硕士研究生学位论文 摘要 具有不精确状态信息的q o s 单播路由算法研究 摘要 传统的服务质量( q u a l i t yo fs e r v i c e ，q o s ) 路由都假设网络结点的状态信息可以 被准确地获知，但实际网络存在许多因素使得链路状态信息不精确。这些不精确的状态信 息将导致网络性能的恶化，如丢包率和阻塞率的上升。因此，我们必须为q o s 路由算法 引入适当的机制，使其可以在链路状态信息不精确的情况下，做出有效且可靠的路由选择， 均衡网络负载，提高网络整体的保障服务性能。 本文通过证明得出结论：若某一条路径上的各条链路的延迟均服从均匀分布，则通过 o p - m p 算法眩1 求得的端到端延迟绑定的概率将随着该路径上的所有链路延迟下限之和的减 小而增大，随着所有链路延迟变化值之积的减小而增大。 文 3 3 的改进算法只考虑了链路延迟下限这一个参数，且在调用k 优路径算法h 3 时所选 取的k 是一个固定值，因此该改进算法所获得的路径就不能始终保持一些良好的性能。本 文在文 3 的改进算法的基础上，运用上述证明得到的结论，设计了两种改进算法：d y n a m i c ki m p r o v e da l g o r i t h m 和f i x e dki m p r o v e da l g o r i t h m 。这两种算法都同时考虑了延迟下 限和延迟变化值这两个参数，其差别在于：d y n a m i cki m p r o v e da l g o r it h m 中所求得的k 优路径中的k 值是通过动态确定的，f i x e dki m p r o v e da l g o r i t h m 中所求得的k 优路径中的 k 是固定值。这两种算法都能够有效地降低丢包率，提高端到端延迟绑定的概率，运用网 络仿真器o p n e t 进行仿真分析，仿真结果表明了这两种改进算法的有效性。 关键词：q o s 路由，不精确状态，单播，仿真 南京邮电大学硕士研究生学位论文absnmct r e s e a r c ho nq o su n i c a s tr o u t i n g a l g o r i t h mw i t h u n c e r t a i ni n f o r ma t i o n a b s t r a c t t r a d i t i o n a lq o sr o u t i n ga s s u m e st h a tt h e r ee x i s t sp r e c i s es t a t ei n f o r m a t i o ni na n yn o d e w i t h i nn e t w o r k s ，b u ti nap r a c t i c a ln e t w o r k ，t h es t a t ei n f o r m a t i o ni sa l m o s tu n c e r t a i n t h e u n c e r t a i ni n f o r m a t i o nw i l ll e a dt od e p r a v a t i o no fn e t w o r kp e r f o r m a n c es u c ha si n c r e a s i n gp a c k e t l o s sr a t ea n db l o c k i n gr a t e t h e r e f o r e ，w em u s ti n t r o d u c es o m em e c h a n i s mi no r d e rt op r o v i d e e f f i c i e n ta n dr e l i a b l er o u t i n g ，b a l a n c et h en e t w o r kl o a da n di m p r o v et h es e r v i c ep e r f o r m a n c eo f t h ew h o l e n e t w o r kw i t hu n c e r t a i ni n f o r m a t i o n t h i sp a p e rh a sp r o v e dt h a ti fe v e r yl i n k sd e l a yi st h eu n i f o r md i s t r i b u t i o ni nap a t h ，t h e p r o b a b i l i t yo fab o u n do nt h e i re n d t o - e n dd e l a yw i l li n c r e a s ea st h es u mo fa l ll i n k s t h el o w e r d e l a yd e c r e a s i n gi nt h ep a t h ，a n da st h ep r o d u c to fa l ll i n k s t h er a n g eo fd e l a yd e c r e a s i n gi nt h e t h ei m p r o v e da l g o r i t h mi nt h er e f e r e n c e 【3 】o n l yc o n s i d e r st h ep a r a m e t e ro ft h el o w e ro f d e l a ya n dt h eki saf i x e dv a l u ew h e nc a l l i n gk s h o r t e s ta l g o r i t h m s ot h ei m p r o v e da l g o r i t h m c a l ln o ta l w a y sk e e pt h eb e t t e rp e r f o r m a n c e u s i n gt h ec o n c l u s i o nh a sb e e np r o v e da b o v e ，t w o i m p r o v e da l g o r i t h m sb a s e do nd e l a yc o n s t r a i n ta r ep r o p o s e du p o nt h ei m p r o v e da l g o r i t h mi nt h e r e f e r e n c e 3 】t h e ya r ed y n a m i cki m p r o v e da l g o r i t h ma n df i x e dki m p r o v e da l g o r i t h m t h e t w oi m p r o v e da l g o r i t h m sc o n s i d e rt h ep a r a m e t e ro ft h el o w e ro fd e l a ya n dt h er a n g eo fd e l a y t h ed i f f e r e n c eo ft h e mi st h a tt h ev a l u eo fki nd y n a m i ck i m p r o v e da l g o r i t h mi sd y n a m i c ，a n d t h ev a l u eo fki nf i x e dk i m p r o v e da l g o r i t h mi saf i x e dv a l u e 。t h et w oi m p r o v e da l g o r i t h m sc a n e f f e c t i v e l yg u a r a n t e et h ed e f i n i t es u c c e s ss u c ha sp a c k e tl o s sr a t ea n dp r o b a b i l i t ye n d - t o - e n d d e l a yc o n s t r a i n to nau n i c a s tr o u t i n gp a t h a n dt h es i m u l a t i o nr e s u l t sf r o ms i m u l a t i o nt o o l o p n e ts h o wt h a tt h et w oi m p r o v e da l g o r i t h m sa r ee f f e c t i v e k e y w o r d s ：q o sr o u t i n g ，u n c e r t a i ni n f o r m a t i o n ，u n i c a s t ，s i m u l a t i o n l i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：4 魉丝日期：之2 ：丝2 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理o ，- ， 研究生签名：么绥噍弧 导师签名：日期：诩酿 南京邮电大学硕士研究生学位论文 前言 1 上j - 刚吾 目前的i n t e r n e t 网络中，个会话的数据分组可以通过不同的传输路径到达目的结 点，而且不同任务分组公平地共享网络资源，例如：链路带宽、交换缓冲区等。这种结构 不能支持多媒体数据和实时数据传输。多媒体业务需求日益增长推动了现有多媒体应用的 进一步发展，这也对新一代网络提出了新的要求。 服务质量( q u a l i t yo fs e r v i c e ，q o s ) 的概念已经用于定量和定性地描述服务的提 供者和接受者之间协商的服务性能。如何提供不同的服务质量是互联网络面临的一个重要 问题，而服务质量路由( q u a l i t yo fs e r v i c er o u t i n g ，q o s r ) 则是其中的核心技术和热 点问题。q o s 路由是指一种基于数据流q o s 请求和网络可用资源进行路由的机制，或者说 q o s 路由是一种动态路由协议，在其路径选择标准中可以包含可用带宽、延迟、跳数以及 延迟抖动等q o s 参数。q o s 路由的主要目标是为接入的业务选择满足其服务质量要求的传 输路径，同时保证网络资源的有效利用。 传统的q o s 单播路由问题都假设网络状态协议获得并保持网络全局状态信息的精确值， 并由此确立了基本的算法准则。但在实际的动态网络环境中，网络结点所能获得的网络中 各链路状态和全局状态并不是精确的蚴。这些不精确的状态信息将导致网络性能的恶化， 如丢包率和阻塞率的上升。因此，我们必须为q o s 单播路由算法引入适当的机制，使其可 以在链路状态信息不精确的情况下，做出有效且可靠的路由选择，从而可以均衡网络负载， 防止因过分拥挤而造成网络性能下降，有利于提高网络整体服务性能一3 。目前关于此类 问题的主要研究思路可归结为：通过对网络业务流模型的分析，借助于相应的网络检测机 制和数学统计分析方法，得到各链路上度量参数的概率分布函数，然后对q o s 路由算法进 行改进，由此实现在不精确状态信息下的路径选择。 本文借助链路状态信息的概率模型来近似描述当前的网络状态，这些概率分布可以通 过网络流量模型和基于测量的统计分析方法得到，本文对此不着重讨论，而是假定各链路 的延迟服从均匀分布且相互独立。 本文证明了端到端延迟绑定( d e l a yb o u n d ) 的概率与链路延迟下限和延迟变化值这两 个参数都有关，而在文 3 的改进算法( 记为：h ui m p r o v e da l g o r i t h m ) 只考虑了延迟下 限这一个参数，且在调用k 优路径算法口1 时，所取的k 是一个固定值，因此该改进算法所获 得的路径就不能始终保持一些良好的性能。本文在h ui m p r o v e da l g o r it h m 算法的基础上， 运用上述通过证明得到的结论，设计了两种改进算法：d y n a m i cki m p r o v e da l g o r i t h m 和 南京邮电大学硕士研究生学位论文 前言 f i x e dki m p r o v e da l g o r i t h m 。这两种算法都同时考虑了链路延迟下限和延迟变化值这两 个参数，其差别在于：d y n a m i cki m p r o v e da l g o r i t h m 中所求得的k 优路径中的k 值是通过 动态确定的，f i x e dki m p r o v e da l g o r i t h m 中所求得的k 优路径中的k 是固定值。最后再运 用网络仿真器o p n e t 进行仿真分析，仿真结果表明了这两种改进算法的有效性。 本文共分为五章。第一章介绍t q o s 路由问题的基础知识，包括q o s 路由的定义、分类、 路由选择方法、q o s 路由研究的主要困难点、q o s 度量参数及q o s 路由策略。 第二章介绍了不精确状态信息产生的原因、问题和模型，并综述了具有不精确状态信 息的q o s 单播路由算法。 第三章先通过证明得出结论：若某一条路径p 上的各条链路的延迟均服从均匀分布，则 通过o p - m p 乜1 算法求得的端到端延迟绑定为d 的概率将随着该路径上的所有链路延迟下限之 和的减小而增大，随着所有链路延迟变化值之积的减小而增大。然后在h ui m p r o v e d a l g o r i t h m 算法的基础上，运用上述结论，设计了两种改进算法：d y n a m i cki m p r o v e d a l g o r i t h m 和f i x e dki m p r o v e da l g o r i t h m 。 第四章先介绍了o p n e t 网络仿真软件，然后分别构建结点数为2 0 和5 0 两种网络模型，对 第三章所提出的两种改进算法及a ui m p r o v e da l g o r i t h m 3 和s 1a l g o r i t h m 跚这四种算法进 行了仿真比较与性能分析。 第五章对本文进行了总结，并对未来的研究方向进行了展望。 2 南京邮电大学硕士研究生学位论文 第章q o s 路由问题 第一章q o s 路由问题 保证服务质量的o o s 路由是网络中解决q o s 问题的一项关键技术。q o s 路由的主要目标 是为接入的业务选择满足其服务质量要求的传输路径，同时保证网络资源的有效利用。q o s 路由研究的主要内容包括：q o s 度量参数问题、q o s 路由策略问题和路由信息的不精确问题。 本文简单介绍一下q o s 度量参数问题和q o s 路由策略问题，重点讨论路由信息的不精确问 题。 1 1 q o s 路由的基本概念和原理 1 1 1o o s 路由的定义 q o s 是网络传输业务流时，业务流对网络服务的需求集合( 主要包括带宽、端到端延迟、 分组丢失率、抖动、花费代价等) ，其中业务流是指与特定q o s 卡f l 关的从源到目的地的分组 流。q o s 是用于定量和定性地描述服务的提供者和服务的接受者之间协商的服务性能。 q o s 路由是指一种基于数据流q o s 请求和网络可用资源进行路由的机制，或者说q o s 路 由是一种动态路由协议，在其路径选择标准中可以包含可用带宽、链路和端到端路径利用 率、资源消费量、延迟、跳数以及抖动等q o s 参数。 1 1 2o o s 路由的分类 q o s 路由按通信方式分，可以分为单播( u n i c a s t ) 、多播( m u l t i c a s t ) 、广播 ( b r o a d c a s t ) 、和选播( a n y c a s t ) 。 ( 1 ) 单播。单播路由选择问题定义如下：给定一源节点s ，一目的节点t ，一组服务 质量约束c ，和一个可能的最佳化目标，寻找从s n t 满足c 的最可行路径。 ( 2 ) 多播。多播路由选择问题定义如下：给定一源节点s ，一组目的节点集r ，一组 约束c ，以及可能的最佳化目标，寻找从s 出发覆盖r 中所有目标节点且满足c 的最可行的树。 ( 3 ) 广播。广播路由选择问题定义如下：给定一源节点s ，一组约束c ，以及可能的 最佳化目标，寻找从s 出发覆盖网络中所有其它节点且满足c 的最可行的传播树。 ( 4 ) 选播。选播路由选择问题定义如下：给定一源节点s ，一组目的节点集a ，一组 约束c ，以及可能的最佳化目标，寻找从s 出发到目的节点集a 中任意一个节点且满足c 的最 可行传播路径。 南京邮电大学碗i 研究生学位论文第一章q o s 路自目艇 11 3 路由选择方法 q o s 路由选择方法很多，它们之间的差别在于几个关键特性的不同。首先，方法设计 者的特殊目的会影响路由协议的操作结果：其次，路由选择方法使用的不同度量方式( 如 最短路径、最小时廷等) 也会影响最佳路径的计算结果，评判个路由选择方法的优劣比 要从以下几个方面进行： 晟优性，就是指路由选择方法具有选择最佳路径的能力： 正确性和简单性，这便于方法的高效实现： 健壮性和稳定性，使网络能适应环境的变化： 快速收敛性，这是所有路由器在最佳路径上取得一致的保证。 路由器通过网络分发路由更新信息，促使最佳路径的蕈新计算，最终使所有路由器达 成一致。收敛很慢的路由算法可能会产生路由环或网路中断。 在图i 一1 中的路由环中，某分组在时间t l 到达路由器1 ，路由器l 已经更新并知道到 达目的的晟佳路径是以路由器2 为下一跳，于是就把该分组转发给路由器2 ，但是路由器 2 还没有更新，它认为虽佳的下跳是路由器1 ，于是把谊分组发回给路山器l ，结果分组 在两个路由器间来回传递直到路由器2 收到路由更新信息或分组超过了生存期。 a b e a d yu 咖a t e d n “”lu 删a l 图1 - 1 产生路由环的情况 路由算法还应该是灵活的，即它们应该迅速、准确地适应各种网络环境。 例直【】，假定某网段断掉了，当知道问题后，很多路由算法对通常使用该网段的路径将 迅速选择次佳的路径。路由算法可以设计得可适应网络带宽、路由器队列大小和网络延迟。 1 14q o s 路由研究的主要困难点 q o s 路由研究中需要衅决的主要难点包括”1 ： ( 1 ) n p 完全( n o tp o l y n o m i a l c o m p l e t e ， c o m p e r e ) 问题同时对两个及两 个以一h 相互独立的参数提出要求时，这个问题就是一个n p 完全的问题。1 。实时应用往往会 南京邮电大学硕士研究生学位论文 第一罩q o s 路由问题 对延迟、延迟抖动、带宽、丢失率、业务代价等多个参数同时提出性能要求。例如实时多 媒体业务会对延迟和延迟抖动同时提出要求，这些参数相互独立时，选择满足多个参数限 制的路由就成为n p 完全问题n 。n p 完全问题直接关系到路由算法的可实现性。 ( 2 ) 多业务并存：同时承载多种q o s 要求不同的业务时，网络性能优化困难，扩展困 难，尤其是q o s 和尽力而为( b e s t - e f f o r t ) 业务独立共存时，很难确定最优的操作点1 1 2 1 。 ( 3 ) 结点状态信息的存储量大：q o s 路由中，结点需要记录的状态参数将增多。如果 状态信息的存储量随网络结点个数的增加而指数性增加，将限制网络的扩展n 1 1 3 1 。 ( 4 ) 路由信息的不精确：传输负荷的抖动、新连接的加入取消等都可能导致网络状 态变化。这些变化因素直接影响全网状态信息的准确性，同时也直接影响算法的性能阳1 。 这四点中，第( 1 ) 、( 2 ) 点是度量参数选择所面临的，第( 3 ) 点在寻路过程中需要 考虑，第( 4 ) 是路由信息不精确中主要解决的问题。 1 2q o s 度量参数 q o s 路由中算法复杂度关系到q o s 路由算法的可实现性，度量参数的选择直接关系到 算法复杂度问题，合理解决多参数问题，在设计低复杂度的o o s 路由算法中占有重要地位。 路由选择算法中的度量值表现了选择路由的标准，它通常需要把端到端的约束分解到每个 链路上，网络度量值的选择通常应该满足以下3 个标准： ( 1 ) 必须存在计算路径的有效算法； ( 2 ) 必须反映网络的基本特征和q o s 对网络元素( 结点、链路) 的约束； ( 3 ) 度量之间应该尽量互为正交并能用实数或整数表示。 目前q o s 路由算法涉及的度量参数包括：带宽、延迟、延迟抖动、丢失率和跳数等。根 据运算规则，这些度量参数可以分为加性q o s 度量、乘，i 生q o s 度量、凹性q o s 度量。假设路 径p 包含n 条链路 ，乞，乙) ，( 以) 是链路上的度量参数值，i = l ，2 ，1 1 ，f ( p ) 是路 径p 的总度量参数值，则以上3 类度量的定义如下n 4 3 ： ( 1 ) 加性q o s 度量 如果f ( 尸) = 芝f ( 1 ，) ，那么度量由传输通道中所有链路的特性共同决定，如时延、 时延抖动、费用等。 ( 2 ) 乘性q o s 度量 如果f ( p ) = 兀f ( 1 j ) ，即度量为所有链路对应度量的乘积，如连接可靠性等。对乘性度 = l 量。 ( 3 ) 凹性q o s 度量 如果f ( p ) = r a i n ( 厂( z ，) ) ，那么度量由传输链路中的瓶颈决定，即此度量仅与路径上 j ；- ，h 的某个瓶颈链路的q o s 度量有关，如剩余带宽、剩余缓存区、链路速率等。 对前述的q o s 度量可以定义为两种基本路由问题：最优化问题和性能界约束问题。最优 化问题就是寻找对应q o s 度量的最优路径：而性能界约束问题就是寻找大于对应q o s 度量 ( 如带宽) 或小于对应q o s 度量( 如延迟) 的一条路径，即在满足性能界要求的集合中选择 一个解。优化问题要求最优解，而约束问题则要求次优解就可满足需求n 5 1 。 对于凹性q o s 度量，可以定义两种基本的路由问题：链路优化路由例如带宽优化 路由问题，就是寻找一个路由使其瓶颈链路带宽最大；和链路约束路由例如带宽约束 路由，就是寻找一条路由使其瓶颈带宽大于一个给定值。链路优化问题可由改进的 d i j k s t r a 算法或b e l l m a n - f o r d 算法来实现，而链路约束问题可以比较容易地转化为链路 优化路由问题。 对于加性q o s 度量，可以定义另外两种基本路由问题：路径优化路由例如最小费 用路由，就是寻找一条路由使其所通过的所有链路的费用的和为最小；和路径约束路由 嘲l 如时延约束路由，就是寻找一条路由使其传输时延小于给定的值。这两类路由问题 都可以直接使用d i j k s t r a 或者b e l l m a n - f o r d 算法来解决。 很多组合路由问题都可以从上面的四种基本问题演化而来。如带宽约束最小延迟路由 就属于链路约束路径优化问题，要寻找满足带宽需求的最小延迟路由，此问题可以通过把 不符合带宽需求的链路删除后，用最短路径算法来解决。另外，用最短路径算法可以在多 项式时间内求解的路由问题有以下四类：链路约束一链路优化问题、链路多约束问题，链 路约束一路径约束问题，以及路径约束一链路优化问题。而涉及到两个或两个以上加性q o s 度量的优化或约束问题则属于n p - c o m p l e t e 问题。如路径约束一路径优化问题、路径多约 束问题等。其属于n p - c o m p l e t e 问题是基于以下两个假设：( 1 ) o o s 度量间相互独立，( 2 ) 其值可取实数或无界整数。如果度量中只有一个取无界整数，而其他度量的取值空间为有 界整数，则此类问题不属n p - c o m p l e t e 问题。可以用扩展的d ij k s t r a 或b e l l m a n f o r d 算 法在多项式时间内求解d 引。如果所有度量都与一个共同的度量相关( 即度量间是相关的) ， 则这也不是n p - c o m p l e t e 问题，求解时间为多项式时间。例如，在使用加权公平排队调度 6 问一性型川s 一茭型舶羔鼾 磊 一八一姒 一脚 一八 一兀仲 忑竖肋瓮 慕电一锗篡 南京邮电大学硕士研究生学位论文 第一章q o s 路由问题 的网络中，最差情况的延迟和延迟抖动是网络带宽的函数，因此，约束延迟约束延迟抖动 路由属路径多约束问题，可以在多项式时间内求解n 引。 1 3q o s 路由策略 路由选择包含两个基本任务：收集状态信息并更新之和基于收集的信息为一新的请求 寻找一可行的路径。根据网络状态信息的保存方式和路由搜寻方式的不同，路由策略可分 为三种：源路由、分布式路由和层次路由。 1 3 1 源路由策略 源路由策略n 力( s o u r c er o u t i n g ) 的路由选择由业务接入结点( 即源结点) 完成。一 般在源路由策略中，每个结点都需要保留全网状态信息，包括网络拓扑，到达其他结点的 路径的度量参数值等。业务请求到达时，源结点根据状态信息的业务度量参数要求计算路 径，如果存在合适的路径，则由源结点沿所选路径发送资源预约信令建立路径。 源路由策略优点：以集中方式计算路由，可以避免分布计算面临的一些问题，如死锁 检测和预防等。还能确保没有循环( l o o pf r e e ) 的路径，并且易于实现、评估、调试和升 级。另外，为解决某些n p 完全的路由计算问题，集中方式下的启发式算法比分布方式更 容易设计。 源路由策略缺点： 1 、扩展性极差，为与不断变化的网络参数( 如带宽和时延) 保持一致，结点的全 局状态必须频繁更新，这对大型网络来说开销很大。 2 、为减少开销而降低更新频率以及更新消息本身一定的传播时延，使得结点只能 提供不太精确的状态信息，结果q o s 路由可能发现不了实际存在的一条可行路径。 3 、 源端结点的计算负荷较重，尤其是在组播和多约束条件的q o s 路由情况下更是 如此。 1 3 2 分布式路由策略 在分布式路由策略n 8 1 ( d i s t r i b u t e dr o u t i n g ) 中，路由选择由多个结点协同完成。每 个结点存有到所有目的结点的下一跳列表，当收到一个数据包时，路由结点仅查表确定下 一跳节点，然后发送数据包。这样，数据包经由每一个节点一跳接一跳前向传送。分布式 路由的寻路一般是通过分布式地传送信令过程实现的，每个节点通过信令，了解本节点相 应于到达某个目的节点的某种业务的前一级节点和后继节点。 7 南京邮电大学硕士研究生学位论文第一章q o s 路由问题 在分布式路由选择中，路径计算分布在从源端到目的端之间的节点上。因此，路由选 择响应时间被缩短，算法更易扩展。为找到一可行路径，并行地搜索多条路径成为可能， 提高了成功机率。它的路由计算和信令发送过程一般是在业务到达前预先进行的，因此路 由建立的响应比源路由快。 然而，目前大多数存在的路由选择算法要求每一个节点保持全局的网络状态( 距离矢 量) ，基于此，分段地作出路由选择的决定。一些扩散式算法不要求保持任何全局状态， 路由选择的决定和最优化完全基于局部( 本地) 状态而进行。依赖于全局状态分布式路由 选择算法或多或少会遇到与源端路由选择算法一样的问题。不需要任何全局状态的分布式 路由选择问题设计有效的分布式启发搜索，尤其在多点传送路由选择情况下更是如此，这 主要是因为没有详细的拓扑结构和链路状态信息。此外，当在不同节点的全局状态不一致 时，循环可能发生。当路由选择消息被一个节点第二次收到时，循环能轻易地检测到。然 而，循环通常使路由选择失败，因为距离矢量不能提供足够信息来改变路径。 1 3 3 层次路由策略 层次路由策略n 钆嘲的原理是把物理节点聚合成组而组又反复不断地进一步聚合为更 高一层的组，从而形成一种多层次结构。每一物理节点保持一聚集的全局状态。这个状态 中包含同组中的节点的详细状态。源端路由选择用来在那些作为逻辑节点表示组的节点 上，寻找一可行路径，随后沿该路径发送控制消息以建立连接。当由逻辑节点代表的组边 界节点收到消息后，它使用源端路由选择扩展路径至整个组。每个最底层的节点( 实际的 网络节点) 都维护一个汇聚的全局状态信息。汇聚的全局状态信息也是分层的，每一层的 信息包括本层中同属一个组的逻辑节点和逻辑链路的详细和其他组的汇聚信息。在最上层 的逻辑节点间采用源端路由找到一条可行逻辑路径，然后一个控制消息沿着这条逻辑路径 发送以建立真实的连接。当路径上逻辑节点所代表的组边界节点( 即下层的逻辑节点) 收 到消息后，则它在这个组内仍采用源端路由扩展路径到该组的出口边界节点，递归这样的 过程，直到真实的连接建立。 层次路由的可扩展性很好，因为每个节点只需维护部分的全局信息，大小是网络详尽 全局信息大小的对数。在每层，逻辑节点依据汇聚信息直接采用源端路由，因而层次路 由继承了源端路由的优点，同时路由计算还是由路径上的许多节点共同分担，因而还继承 了分布计算的优点。层次路由是对大型网络而言最有前途的路由策略。 然而，由于汇聚信息引入了不精确性，层次路由在一些情况下可能导致选路失败。这 通常是由于逻辑节点通告的其自身的多个q o s 能力可能对应的不是通过该逻辑节点的同 8 南京邮电大学硕士研究生学位论文第一章q o s 路由问题 一条路径。 1 3 4 三种路由策略的比较和有待解决的问题 综上所述，三种路由策略的比较和有待解决的问题如表卜1 所示。 表1 - 1 ：三种路由策略的比较 路由策略优点缺点待解决的问题 源路由集中处理，保存全局信息，在大型网络可扩展性、信息不精确 简单，不产中有很大的传输开销，计算性、对选择路径的影响因 生环路开销较大素的研究 分布式路由可扩展性好须引入环路控制机制和解多度量约束路由算法的 决分布计算的终止问题研究，降低通信开销 层次路由可扩展性 聚合q o s 参数的实用、有效各种q o s 度量参数的聚 好，抑制环算法还有待研究合问题 路的产生 必须注意q o s 数据和尽力而为 ( b e s te f f o r t ) 数据的融合问题。在实际的网络中 q o s 数据和尽力而为数据是共存的，路由的作用在于最大地提高网络资源的利用率，这包 含两个目的：一是使网络能够接收的q o s 连接数最大化，这等同于使阻塞率最小化。二 是让尽力而为数据的吞吐量和网络响应最优化。这两个目的是互斥的。因为前一问题仅考 虑了q o s 数据，后一问题仅考虑了尽力而为数据，但此两者数据的分布和性质是完全不 同的。总体来说，q o s 数据由于受资源预留的保护，因此不受尽力而为数据的影响。然而， 如果对数据流动情况的判断失误，尽力而为数据的吞吐量会极大地受q o s 数据的影响。 9 南京邮电大学硕士研究生学位论文 第二章具有不精确状态信息的q o s 单播路由算法综姿 第二章具有不精确状态信息的q o s 单播路由算法综述 2 1 不精确状态信息产生的原因 q o s 路由的选择取决于网络节点和链路的可利用资源的状态信息，这些不精确状态信 息产生的原因大致可以归纳为以下几种口3 ： 。( 1 ) 网络的动态性 许多与延迟约束相关的参数受网络或链路的临时状况的影响，如网络拥塞等。目前采 用的链路状态更新策略是周期性更新策略，但广播的参数基本上是平均行为或最坏行为， 且局部状态的改变广播到其它结点需花费不可忽略的传播延时，因此用于路由计算的只是 更新周期前的值。当网络状态频繁变动时，这些参数是不精确的。 ( 2 ) 大型网络的状态聚集 随着网络规模的增长，网络中每个网络设备不可能保持所有结点和链路状态信息的精 确值。a t m 的专用网间接口( p r i v a t en e t w o r k - t o - n e t w o r ki n t e r f a c e ，p n n i ) 引入了一种层 次化的处理过程，可以将多个网络结点合成一个结点。然而这使得网络高层在做出决断时， 缺乏底层具体物理网络状态信息的支持，高层主要是依据高层次逻辑结构来做决断的，从 而也无法避免信息的不精确乜卜2 引。 ( 3 ) 不精确的测量 在现有的路由广播协议中，如开放最短路径优先( o p e ns h o r t e s tp a t hf i r s t ，o s p f ) ， 结点并不广播所有与路由决策有关的参数 2 4 , 2 5 o 用于路由决策的参数是通过网络管理系统在 特定的链路上进行主动或被动的测量而获得的。然而，这些机制只能提供部分且不精确的 值，由此将造成路由信息的不准确。 ( 4 ) 近似的计算 所谓“精确 的结点和链路参数实际上也只是实际参数的近似值。它们通常是用理想 化的模型来计算的，可这并不能完全表达设备的复杂性，所计算出的参数值通常是上限或 混合了一些不精确的假设，这也将导致网络状态信息的不精确。 ( 5 ) 被隐藏的信息 当所有的路由设备都在同一个网络监控下进行操作时，路由信息在结点之间进行正常 的交换。但互连的网络可能包括一些私有网络，这些网络出于保密的需要或是出于自由的 考虑，它们会隐藏部分或全部的网络资源信息。 l o 南京邮电大学硕士研究生学位论文第二章具有不精确状态信息的q o s 单播路由算法综述 2 2 问题和模型 我们用一个有向图g = ( 矿，e ) 来表示一个网络，其中，矿= v l ，v 2 ， 表示网络中结 点的集合，e = 弛，e 2 ，) 表示网络中链路的集合，lyl 和ie1 分别表示网络总的结点数和 链路数，i p l 表示路径p 上链路数。如果各传输线路是对称的，即每条传输线路的两个方 向上的数据都有同样的特性，则称此网络是对称的，此时各条边为无向边；反之，则称网 络是不对称的，对应的边为有向边。对于大多数实际的网络而言，其链路一般都是非对称 的，因而其每一条链路对应于模型中两条有向的加权边，但在研究中为了简便起见，常常 使用对称网络模型以减少弧的数量3 。 o o s 单播路由问题，就是要寻找一条从源结点j 到目的结点f 的满足q o s 约束且代价最 小的路径。我们用d l 表示链路f 上的延迟，z ( d ) 表示链路z 满足延迟绑定为d 的概率， ( 尸) 表示路径尸满足端到端延迟绑定为d 的概率。常见的问题定义如下： ( 1 ) m p ( m o s tp r o b a b l ep a t h ) 问题 指在给定的端到端延迟约束d ，找到一条路径p ，使得对于任何路径p ，有 7 d ( 尸+ ) 万d ( 尸) 。 假设 彳( d ) ) 脚是已知的，对于严格绑定的端到端延迟，需要在选定的最优路径上分解 端到端延迟为本地约束，从而预留相应的结点和链路资源，d 分解成( 尸) = 口) 舯， ，口= d 。 则在这条路径上的划分品( 竹= 口) ，尸， 有： 万( 日) 舯) = p a 4 口，v lep = i - i 石( 口) 。 l e p ( 2 ) o p ( o p t i m a lp a r t i t i o n ) 问题 指在一条给定的路径上的结点之间划分端到端延迟需求。其形式化描述如下：给定一 条路径p 以及延迟约束d ，找到一个划分品( 尸) = 巧) 肿，使得万( ( 尸) ) 万( & ( 尸) ) 。 ( 3 ) o p m p ( o p t i m a l l yp a r t i t i o nm p ) 问题 在将端到端延迟分解到本地延迟约束时，确定一条最有可能满足端到端延迟需求的路 径。其形式化描述如下：给定一个延迟d ，找到一条路径尸和一个划分岛( 尸) = 巧) 舯， 使得对于任何p 而言都有：万( s ：( p 。) ) 万( 醛( p ) ) 。 ( 4 ) r s p 问题( r e s t r i c t e ds h o r t e s tp a t h ) ： 南京邮电大学硕士研究生学位论文第二章具有不精确状态信息的q o s 单播路由算法综述 给定一个网络g = ( 矿，d ，对于网络中每条链路| 有 名，q l 以，其中刃表示链路? 上的延 迟，c i 表示链路z 上的代价，给定端到端延迟保证为d ，找到条路径p ，使得啦d ， ，e ， 且对于其他满足珥d 的路径p 而言，有q c ，。该问题属于n p 难问题，证明略， | e pl e p i e p 请参见文献 7 。 0 p 问题、m p 问题、0 p m p 问题以及r s p 问题都是n p 难问题口1 。而0 p i p 问题与r s p 问题的最主要差别在于：对于o p - m p 中的链路z 而言，其。并非是一个静态值，而是关于d 的函数，我们可以用c f ( d ) = 一l o g ( f ( d ) ) 来表示这个函数。不过从文 7 中，我们可以证明， o p - m p 问题的求解可以简化为对r s p 问题的求解，因此，我们可以从r s p 的解决方案中获 得启发，以求获得对o p - m p 问题的求解。 标准最短路径问题有一个优化子结构特征，即如果p = ( s ，“，v ，z ) 是s - - z 的最短 路径，则( 甜，y ) 是“- - - 9 , 1 ，的最短路径，故最短路径的选择可以利用这样一种“传递性 来 构造，同时将时间复杂度降到多项式。0 p - m p 问题具有优化子结构特征，而m p 问题不具有 这个特征，证明请参见文献 7 。 为了便于理解，我们举例说明。网络拓扑如图2 - 1 所示： 3 图2 - 1 一个简单网络拓扑 v = a ，b ，c ) ，e = 1 ，2 ，3 ，4 ，各链路的延迟概率分布如下： 石= 彳( d = 1 ) = 0 5 ，石( d = 5 ) = 0 5 ) ； 石= 五( d = 2 ) = 1 ) ： 石= 石( d = 1 ) = o 4 5 ，a ( d = 2 ) = 0 4 5 ，a ( d = 9 ) = o 1 ) ； 丘= 工( d = 1 ) = 0 2 ，f 4 ( d = 2 ) = 0 8 ) ； 1 2 0 4 i 塑室墼皇奎堂堡主堡壅竺堂垡丝奎 茎三童墨查至塑塑鉴查堕星箜g ! ! 璺塑堕虫簦鲨箜垄 -_。-o_-_-_-_-_-_-_i-io-_-_o_-ooo_o_i_-_o-_oooo_。oo。oo。一一假设给定端到端延迟约束为3 ，求从a 到c 的m p 和0 p m p 。 设日= 1 ，4 ，昱= 2 ，4 ，忍= 3 , 4 。 置满足端到端延迟约束为3 的概率为乃( 只) = 石( d = 1 ) 幸( 厶( d = 1 ) + 五( d = 2 ) ) = o 5 ，同 理求得 3 ( 最) = 0 2 ，乃( 忍) = 0 5 4 。故m p 为罡。 如果延迟必须划分成本地约束，则必须解决最优划分问题。则丑的最优划分为 g ( 鼻) = 1 ，2 ) ，则万( g ( 暑) ) = o 5 ；最的最优划分为g ( 罡) = 2 ，1 ) ，则万( g ( 最) ) = 0 2 ，只的 最优划分为g ( b ) = 1 ，2 ) ，则万( g ( 与) ) = 0 4 5 。故o p m p 为曰。 从图2 - 1 可见，b 是a 到c 的必经之路，考虑所有可能的划分，a 到c 的m p 是b ，但 a 到b 的m p 是弓，所以它不具有优化子结构特性。需观察0 p m p 结果，在最优划分下，a 到c 的o p m p 和a 到b 的o p - m p 经过相同的链路，且划分也相同，这就是说，o p m p 具有 优化子结构特性。 2 3 具有不精确状态信息的o o s 单播路由算法 目前，具有不精确状态信息的o o s 单播路由算法可分为两大类：容忍不精确状态信息 的q o s 单播路由算法和基于状态信息概率分布的q o s 单播路由算法n 酗。 2 3 1 容忍不精确状态信息的o o s 单播路由算法 为了减少网络的动态性所产生的不精确状态信息对网络性能的影响，可以采用状态信 息的刷新使得网络结点拥有的信息一致。目前常用的刷新机制有基于时间的刷新机制 ( t i m e rb a s e dp o l i c y ) 和基于阀值的刷新机制( t h r e s h o l db a s e dp o l i c y ) 两种。根据刷新 机制的不同可将不精确状态信息分为两类。对应于基于时间的刷新机制的一类不精确状态 信息属于随机的不精确信息( r a n d o mi m p r e c i s i o n ) ，对应于基于阀值的刷新机制的另一类 不精确信息属于确定的不精确信息( d e t e r m i n i s t i ci m p r e c i s i o n ) 。通常容忍不精确状态 信息的q o s 单播路由算法可分为下面5 个小类： ( 1 ) 基于安全的路由(