（计算机应用技术专业论文）qos选播路由算法研究.pdf

硕十学位论文 摘要 随着网络规模的日益扩大，网络服务需求已超过了网络服务容量，对具有q o s 服务的应用产生了严重的影响。为了增强服务的可用性和改善网络流量分布，通 常的方法是在网络中复制服务器。选播是一种支持分布式服务器复制的新的服务 模型。由于越来越多的应用需要选播服务，因此选播服务在i p v 6 中已被定义为一 种标准服务模型。本文主要研究o o s 选播路由算法及其相关技术。 本文首先分析了q o s 选播服务的一般模型和基本的q o s 选播路由算法。在此 基础上，从网络负载平衡的观点出发，提出了一种基于网络链路空闲率的q o s 选 播路由算法。本算法结合网络的总负载和请求带宽，以寻找选播路径。实验结果 表明：新的算法能较好地平衡网络和服务器负载，并具有较高的请求接受率：考 虑到网络状态信息的非精确性，本文提出了一种基于安全度的q o s 选播路由算法， 本算法利用网络非精确信息，结合更新策略，赋予每条链路一个安全度函数，并 利用它来寻找选播路径。对不同网络参数下的模拟结果表明，新的算法能较好地 平衡网络负载并具有较高的请求接收率；针对传统q o s 路由算法忽视了网络负载 平衡和整体性能，本文提出一种随机q o s 路由算法。算法利用网络平均空闲率作 为算法的性能评价指标，结合提出的安全度计算公式，寻找传输路径。实验结果 表明：此算法能有效提高网络负载能力和优化网络的熬体性能。本文依据网络模 拟器设计思想，实现了基于事件的网络路由模拟器，并利用此模拟器对本文所提 算法进行了性能评价。 关键词：非精确信息；服务质量；路由算法；选播 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e t n e t w o r ks e r v i c er e q u i r e m e n t se x c e e d t h e c a p a b i l i t i e so ft h e n e t w o r k ，w h ic hc a u s e sa g r e a t i n f l u e n c et o a p p l ic a t i o no fq u a l i t yo fs e r v i c e ( q o s ) i no r d e rt oe n h a n c et h es e r v ic e a b i l i t ya n di m p r o v en e t w o r kf l o wd i s t r i b u t i o r ，w eu s u a l l yd u p l i c a t es e r v e r s int h e n e t w o r k a n y c a s t s e r v i c ei san e ws e r v ic em o d e l s u p p o r t i n g d i s t r i b u t e dd u p l i c a t i o n m o r ea n dm o r ea p p l i c a t i o n sa r er e l a t e dt oa n y c a s t ， s o a n y c a s t i sas t a n d a r ds e r v i c em o d e ld e f i n e d b y i p v 6 t h i st h e s is c o f l c e n t r a t e so nt h es t u d yo fq o sa n y c a s tr o u t i n ga l g o r i t h m sa n dr e l a t e d t e c h n o l o g i e s t h et h e s i ss t a r t sw i t ha na n a l y s i so nt h eg e n e r a lm o d e li no o sa n y c a s t s e r v i c ea n db a s i co o sa n y c a s tr o u t i n ga l g o r i t h m s w i t ht h es t a n d p o i n to f l o a d b a l a n c e d ，t h i st h e s i sp r e s e n t saq o sa n y c a s tr o u t i n ga l g o r i t h mb a s e d o nn e t w o r kl i n ki d l e n e s sp r o b a b i t i t y t h i sa l g o r i t h mc o m b i n e st h en e t w o r k t o t a l1 0 a d sw i t hr e q u e s tb a n d w i d t h ，a n ds e a r c h e sf o raq o sa n y c a s tr o u t i n g p a t h t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wa l g o r i t h i nc a nb a l a n c e1 0 a d s o fn e t w o r ka n ds e r v e r e f f i c i e n t l y ，a n d h a s h i g h e ra c c e p t a n c e r a t eo f r e q u e s t s b e c a u s et h en e t w o r ks t a t ei n f o r m a t i o ni s n o ta l w a y sa c c u r a t e ， t h i st h e s i sb r i n g sf o r w a r daq o sa n y c a s tr o u t i n ga l g o r i t h mb a s e do ns a f e t y r a t e u t i l i z i n g i n a c c u r a t en e t w o r ki n f o r m a t i o na n dc o n s i d e r i n gu p d a t e p o l i c y ，t h i sa l g o r i t h mg i v e sas a f e t yf u n c t i o nt oe v e r y1 i n k i nn e t w o r k ， a n dh u n t sf o ra na n y c a s tr o u t i n gp a t ht h r o u g hi t t h ee x p e r i m e n t a lr e s u l t s s h o wt h a tt h e p r o p o s e da l g o r i t h m h a s g o o d 1 0 a d b a l a n c e dw i t h h i g h l y a c c e p t a n c er a t eu n d e rd i f f e r e n tn e t w o r kp a r a m e t e r s b e c a u s et r a d i t i o n a l o o sr o u t i n ga l g o r i t h m si g n o r et h et r a d e o f fa n dt o t a lp e r f o r m a n c e s ，t h i s t h e s i sp r o p o s e saq o sr a n d o m i z e dr o u t i n ga l g o r i t h m t h i sa l g o r i t h mu s e s t h en e t w o r ka v e r a g ei d l e n e s sr a t ea sa ne v a l u a t i o np a r a m e t e r ，a n ds e a r c h e s f o rat r a n s m i s s i o np a t h a c c o r d i n g t oa p r e s e n t e ds a f e t y f o r m u l a t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wa l g o r i t h mc a ni m p r o v ec a b i l i t yo f n e t w o r kl o a d sa n do p t i m i z ep e r f o r m a n c eo ft h ew h o l en e t w o r k a c c o r d i n gt o i d e o l o g y o f d e s i g n i n g an e t w o r k s i m u l a t o r ，w ed e s i g n a ne v e n t b a s e d s i m u l a t o r t h ep e r f o r 皿a n c e so fa l la l g o r i t h m si nt h et h e s i sa r ee v a l u a t e d t h r o u g ht h e s i m u l a t o r i i 硕士学位论文 k e yw or d s ：a n y c a s t ：r o u t in ga i g o ri t h m ：q u a ii t yo f s er v ic e ：in a c c ur a t e in f or m a t io n ： 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 刑秀莼 日期：矿，眸年月。日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ”) 作者签名： 导师签名： 互螺琵 勘荔 i 日期：矿一悻午月己日 日期：伊学f 噜月。日 硕士学位沦文 1 1o o s 选播路由概述 第1 章绪论 随着更多的网络主机相连，网络服务需求已超过了网络的服务容量。虽然其 不影响一些经典的网络应用，比如电子邮件、文件传输等，但是对需要实时服务 的应用产生了严重的影响，如视频点播、i p 电话等。为了提供足够的网络服务， 必须增加一些定量或定性的确定性i p 服务。服务质量( q u a l i t yo fs e r v i c e ，q o s ) 通过管理网络资源来改善网络服务和满足更多不同需求的网络应用“。 q o s 的概念已经用于定量和定性地描述服务的提供者和服务的接受者之间协 商的服务性能。服务质量可以由些特定的参数来描述，服务的提供者允许服务 的使用者在建立连接时对各种服务参数指定希望的、可接受的最低限度值，有些 参数还可以用于无连接的传输服务。服务台的提供者根据网络服务的种类或它能 够获得的服务来检查这些参数，决定能否提供所要求的服务。一些典型参数如下； 网络带宽、传输延时、延时抖动、差错率等。在i n t e r n e t 上对网络服务质量的要 求也越来越高，例如：视频会议、网络电话的实时和带宽要求，大数据量数据备 份的完成时间要求等。如何在网络中实现多种服务质量是全世界通信领域竞相研 究的重点课题。1 。q o s 的研究有多个方面，包括流量整形( t r a f f i cs h a p i n g ) “ ，包调度算法( p a c k e ts c h e d u l i n g ) i s - s 、路由算法( q o sr o u t i n g ) 。1 “、资源 预留( r e s o u r c er e s e r v a t i o n ) “t 3 、接入控制( c a l la d m i s s i o nc o n t r 0 1 ) “。 等的研究。 为了增强服务的可用性和改善网络的流量分布，通常的方法是在网络中复制 服务器，例如：在i n t e r n e t 中的w w w 镜像服务器、视频点播、股票服务器、计算 服务器和代理服务器。复制服务器技术主要有本地复制和分布式复制两类“”。本 地复制主要采用服务器组群技术，这些服务器都在同一个子网内。分布式复制是 将服务器放置在不同的地理位置，通过i n t e r n e t 连接提供服务。如果客户端需要 定位合适的服务器，就必须扩充和增强客户端功能去完成定位工作。 在i n t e r n e t 上，可以采用一种新的服务模型选播( a n y c a s t i n g ) 来支持分布 式服务器复制。选播服务是指从一台主机向一组目的主机中的任何一台传输数据 “，一组目的主机的地址是由一个选播地址表示，提供相同服务的不同服务器拥 有相同的选播地址。例如：多个w w w 镜像服务器可以共享一个选播地址，为得到 所需要的信息( 例如：天气情况、股票数据等) ，用户可以简单的采用选播地址所 对应的虚拟主机名访问若干个主机中的一个。图1 1 给出了选播服务的示意图， 服务器l 、服务器2 和服务器3 具有相同的选播地址，客户机1 和客户机2 要确定 用服务器l 、2 、3 中的哪个服务器提供服务。在该事例中采用最少跳数的策略， 客户机1 选择服务器1 提供服务，而客户机2 选择服务器2 提供服务。 图1 1选播服务示意图 1 9 9 3 年文献 1 8 首次提出选播服务的概念，并通过客户定位最近服务器的事 例阐述了需要选播地址的主要动机。在文献 1 8 中，选播服务的概念定义为：采 用无状态的“尽力而为”的方式，将选播报文至少传输到一个具有选播地址的主 机，最好仅仅传输到一个主机。由于越来越多的应用需要选播服务，因此选播服 务在i p v 6 中已被定义为一种标准服务模型“。目前的i n t e r n e t 网络中，一个会 话的数据分组可以通过不同的传输路径到达目的节点，而且不同任务分组公平地 共享网络资源，例如：链路带宽、交换缓冲区等。这种结构不能支持多媒体数据 和实时数据传输“3 。多媒体业务需求的日益增长推动了现有多媒体应用的进一步发 展，这也对新一代网络提出了新的要求”1 。 选播路由选择包含两个基本任务：收集状态信息并更新和基于收集的信息为 新的请求寻找一可行的传输路径。任何一个路由选择算法的性能直接依赖于前 任务解决的好坏。网络状态信息可以是局部、全局和汇聚状态信息。局部状态信 息：假定每一节点保持其更新的局部状态，包括排队和传送延迟、输出链路的剩 余带宽、以及其它资源的可利用性。全局状态信息是所有节点局部状态信息的组 合，每个节点通过链路状态协议”或距离矢量协议能够保持全局状态o “，它们定 2 硕士学位论文 = = = = = ! = = = = = = = ! ! = = = 2 = ! = = ! = = = = = = = ! = ! = = = = = = = = = = = = = = = ! ! ! ! ! ! ! ! ：= ：= = 期地在节点间交换局部状态。汇聚状态信息：通过根据大型网络的层次结构汇聚 信息实现”1 ，每个节点保存一个汇聚的网络映象。汇聚状态信息大大减少了状态 数目，但也引入了汇聚信息的不精确性。选播路由计算可以是集中计算，即整个 路由的计算在一个节点内进行，也可以是分布计算，即计算开销由沿着路由的各 个节点分担。q o s 选播路由策略通常分为以下3 种”“：源端路由。”2 “、分布式路 由”。”1 和层次路由( 分级路由) 。3 “。 1 2 研究现状 目前，研究选播服务模型主要从两个方面着手：基于网络层的选播服务和基 于应用层的选播服务。文献 3 4 提出了一种基于应用层的支持服务器复制的选播 通信方法，并且提出了基于使用选播裁决器的选播域名到多个i p 地址映射的实现 方法。文献 3 5 提出了一种映射客户端选播请求至“最佳”分布复制服务器的优 化算法，其是基于经济模型和排队理论的应用层选播算法。文献 1 7 研究了如何 在对当前使用的路由算法和协议处理策略影响不大的情况下在i n t e r n e t 中实现选 播路由服务，并设计和实现了用于在i n t e r n e t 的i b mo l y m p i cw e b 站点的负载分 布的基于网络层的选播服务。文献 3 6 提出和分析了一种分布式选播路由协议， 该协议包含路由表建立和数据包转发两个子协议。路由表建立协议增强了路径选 择过程中路由器的有序性，从而避免路由环的出现。数据转发协议为了平衡网络 流，采用一种用于多路选择的加权随机选择方法。文献 3 7 提出了集成路由选播 算法，该算法通过合理选择网络路由器集来执行多路径路由选搔算法，充分利用 了单路径路由和多路径路由选播算法的优点。文献 3 8 3 考虑到路由器上的负载处 理和计算机网络上的处理单元，提出了负载平衡的路由选播算法，但对最短延迟 路由只提出了近似的解决方法。 基于非精确网络状态下的q o s 选播路由算法是研究q o s 选播服务模型的热点 问题之一。造成网络状态信息非精确的主要原因有口”：网络状态信息的传播延 时、网络状态更新策略和网络的分层结构。1 9 9 7 年，g u e r i l q 和o r d a 等人在网络 研究中最著名的i n f o c o m 国际会议上首次提出了网络状态信息非精确的概念和基 本研究模型“。他们继续研究了在非精确网络状态信息下的带宽受限和时延受限 的路由问题，提出了基于概率分布的非精确信息模型和路由算法。文献 4 1 总结 了关于该模型的进一步研究结果，提出了一个新的启发式时延受限路由算法。文 献 4 2 ，4 3 研究了在仅具有非精确信息的动态环境下的源端和分布式q o s 路由算 法，并提出了一个更为简单的非精确模型。在文献 4 5 3 中，为了补偿网络节点链 路状态信息的不精确性，提出了一个计算从源节点到目的节点若干条传输路径的 q o s 路由算法。由于网络状态信息的非精确和全局网络状态信息交换的额外开销， 文献e 4 6 提出了两个全新的基于局部状态信息的q o s 路由算法。除了对非精确网 3 络状态信息f 模型和路算法的研究外，人们已经开始注意到评价非精确网络状态 信息对嘲络路由算法的影响。文献 4 7 研究了当链路状态信息是非精确时采用链 路安全信息( 满足要求的概率) 来提高路由算法性能相关的一些问题。文献 3 9 研究了在q o s 源端路由算法中网络开销和路由算法性能之间的本质关系，分析了 路由算法的性能和额外开销与链路更新策略、潜在的流量负载、网络拓扑和链路 代价尺度等关系。国内关于非精确网络状态信息的研究刚刚起步，己引起了许多 专家学者的注意。文献 4 8 指出研究在链路状态不精确情况下的多路径q o s 路由 是未来的重要工作之一。文献 2 3 在总结宽带i p 网络的q o s 路由领域研究时指出 需要面对不精确网络状态信息的现实。在实施不确定信息选路时，可以考虑将端一 到一端时延限制分解为局部限制，以便建立有效、可行的算法，然后结合链路状态 值的概率分布来考虑选路的综合优化问题。 新一代计算机网络必然支持各种服务质量的传输业务，而网络状态信息的非 精确是客观存在的，因而研究非精确网络状态信息下的q o s 选播路由算法是十分 必要的。非精确网络状态信息下的q o s 选播路由算法的研究在国内外刚刚起步， 以前有关非精确网络状态信息下q o s 选播路由算法的研究主要集中在寻找最大概 率的传输路径，而忽视了网络负载平衡和整体网络性能。本文提出的非精确网络 状态信息下的q o $ 选播路由算法，能有效的提高网络的负载能力，优化网络性能。 1 3q o s 选播路由的一般模型和算法 令网络图占= ，e 抄，其中肛 r e , “) 是g 的节点集合，占= ( e 。，如，b ) 是g 的链路集合，用鼠。， 朝表示每条链路e j 当前可用带宽；用a ( a ) 表示选播目的 节点集：c ( a ) = 历，如，蹦，且g 似) c v 。具有q o s 条件约束的选播请求斤= ( 配。丘向戌) ，其中“表示源节点，a 为选播地址，b 表示传输带宽需求，龙为传 输延迟需求。选播q o s 传输路径p 是指在网络g 中从源节点至g ( a ) 中任何一个 节点的通路，且满足以下两个条件： 尻。r e j 6 ；e ，( k p ( 1 1 ) ip | s 虬 ( 1 2 ) 式( 1 2 ) 中旧为路径p 包含的链路数。 该问题的数学描述为： f i n dap a t hp ，s u b j e c tt o ： 。磊。，是工矿o 菇”1茹。0 f o re a c hi u oa n di 硅g ( a ) ： 4 ：一一一! ：尘圭耋垡坠： = = ：一一：一： 。，毳驴【磊“ 。薹嘞引 f o ra l l e d g e i ，j ： x , je o ，1 。, 1 薹x v 。 m i n b , i i ii 【i ，j e e a n d x i j 0 2 b 其中x ，。= o ，表示节点i 不是节点j 的邻接点，x ，= 1 ，表示节点i 是节点 j 的邻接点。 寻找q o s 选播路径一般采用最短路径算法( s h o r t e s tp a 幼，简称s p ) “”，包 括静态最短路径算法( s t a t l cs h o r t e s t 心t h ，简称妒) 和动态最短路径算法 ( d y n a m i cs h o r t e s tp a 砌简称n 。静态最短路径算法不改变网络的拓扑结构和 网络信息，动态最短路径算法在寻找路径时，网络结构与信息是变化的。最短路 径算法简单，找路迅速，但由于它没有考虑全局资源使用情况，不能有效平衡网 络和服务器负载，因此请求接受率不高。至于随机策略算法、负载平衡算法、单 路径路由与多路径路由算法、集成路由算法等，由于只从局部或单条链路考虑， 不能很好的平衡网络负载和服务器负载，请求的接受率也不理想。本文将从整个 网络的信息出发，去研究选播路由，从而有效提高请求的接受率，节约存储单元， 更好的平衡网络和服务器负载。 1 4 本文所做的主要工作 使新一代i n t e r n e t 网络能够提供有服务质量保证的传输业务是目前计算机 网络研究的主要课题之一，本文主要研究q o s 选播路由算法及有关技术，分析网 络状态的非精确性对路由算法性能的影响。主要工作归纳如下： 1 分析了q o s 选播服务的一般模型和基本的q o s 选播路由算法。 2 从网络负载平衡的观点出发，本文提出了一种基于网络链路空闲率的q o s 选播 路由算法。该算法结合网络的总负载和请求带宽，来寻找选播路径。实验结果 表明，新的算法能较好地平衡网络和服务器负载，并具有较高的请求接受率。 3 针对网络状态信息的非精确性，本文提出了一种基于安全度的q o s 选播路由算 法，该算法利用网络非精确信息，结合更新策略，赋予每条链路一个安全度函 数，并利用它来寻找选播路径。对不同网络参数下的模拟结果表明，新的算法 能较好地平衡网络负载并具有较高的请求接收率。 4 考虑到传统q o s 路由算法忽视了网络负载平衡和整体性能，提出了一种随机 q o s 路由算法。该算法利用网络平均空闲率作为算法的性能评价指标，结合提出 5 的安全度计算公式，来寻找传输路径。实验结果表明，此算法能有效提高 c ) 9 络 负载能力和优化网络的整体性能。 5 依据网络模拟器设计思想，本文设计了基于事件的网络路由模拟器，并利用此 模拟器对本文所提算法进行了测试和性能评价。 全文主要包括以下五个章节：第一章绪论介绍q o s 路由算法研究背景和意 义，并对当前课题的研究现状和研究内容以及本文的主要工作进行了论述；第二 章网络模拟器的设讨与实现介绍了网络模拟器设计的思想和设计思路，详细描 述了基于事件网络路由模拟器r n s 的设计与实现；第三章基于随机策略的q o s 路由算法研究包括单播路由算法研究的模型、基于随机策略的q o s 路由算法及实 验；第四章基于网络链路空闲率的q o s 选播路由算法研究包括主要思想及算法 描述，实验结果及分析；第五章基于安全度的q o s 选播路由算法研究包括算法 的主要思想及描述，实验结果与分析；最后是总结全文。 6 硕士学位论文 第2 章网络模拟器的设计与实现 由于在实际网络中进行q o s 选播路由算法模拟的难度很高，目前通用的网络 模拟器中网络状态信息都是精确的，若要利用这些网络模拟器进行非精确状念信 息下的q o s 选播路由算法进行测试，必须修改模拟器的底层系统。本章依据网络 模拟器设计思想，设计了基于事件的网络路由模拟器，并利用此模拟器对本文所 提算法进行了性能评价。 2 1 概述 近几年来，全球的i n t e r n e t 在快速发展，这不仅仅体现在网络服务机构、网 络设备和网络服务接受者的增加，而且体现在i n t e r n e t 所提供的网络服务类型的 增多。i n t e r n e t 已逐步由单一的数据传送网向数据、语音、图象、视频等多媒体 信息的综合传输网发展。随着i n t e r n e t 网上多媒体信息传输的出现，各种传输请 求对传输质量有不同的要求，例如：传输速度、传输延迟、延迟的均匀性等。这 就对网络能支持的服务提出了新的要求。人们希望网络应能适应各种不同质量要 求的服务请求，即网络应能支持多种服务质量请求。基于q o s 的路由是网络支持 q o s 请求的一个研究方面，其主要目的是在网络中选择一条满足q o s 请求的网络路 径，一个q o s 请求包括网络上的发送点和接受点，以及对网络延迟、网络带宽等 要求。q o s 路由算法的优劣直接影响网络服务质量，因此，研究如何评价q o s 路由 算法性能是至关重要的问题。 近年来，i n t e r n e t 在大小和规模上都显著增长。因此，新的协议和算法正在 不断地被设计出来用于满足i n t e r n e t 上不断变化的运行要求。为进行新路由算法 的性能评估涉及许多问题。虽然在实验室中的小规模评估，在实验台上的大规模 测试以及传统的模拟器都是非常有价值的，但是它们每一种都有严重的不足。这 些方法经常缺乏将现实网络中的通信和拓扑结合起来的能力，它们需要大量的经 费，同时在控制条件下重复实验也是很困难的。建立网络实验室来测试网络的性 能十分重要，但这种方法有一些缺点h ：建立大规模网络实验环境需要巨额资金， 同时难以更改配置和共享，甚至有些新的思想和方法在现实网络环境下无法测试。 采用建立网络测试模拟系统的方法虽然会丢失一些细节信息，但其具备更好的灵 活性和共享性 s o l 。多协议的网络模拟器能够以低费用来提供丰富的实验环境。在 不同的研究领域使用共同的模拟环境能够给网络社区带来许多好处。这些好处包 括对现有协议行为检验的改进，开发新协议所需的丰富的基础结构，在控制环境 下研究大规模的协议交互，以及更容易的对研究结果进行比较。 许多模拟器定位于某个特殊领域，例如atm 、pim 组播等特定的网络类 7 型和协议。而其它的包括n s 一2 “、r e a l 、opnet es2 、i nsan e 等模拟器 定位于更为广泛的协议，这些模拟器都提供了一种带有网络协议库的模拟语言， 例如：m a is i e 和opnet 。 在这些通用的网络模拟器中网络状态信息都是精确的，若要利用这些网络模 拟器进行非精确状态信息下的q o s 选播路由算法进行测试，必须修改模拟器的底 层系统。我们在掌握了解这些模拟器系统的设计方法和信息流的处理方法的基础 上，设计了基于非精确网络状态信息的事件触发机制的网络模拟系统，t j f 于评价 q o s 选播路由算法。 2 2 基本思想 模拟器应用蒙特卡罗方法 5 33 用一个数值模型来模拟一个真实网络的运作情 况。蒙特卡罗法又名统计试验法，是计算数学的一个分支，其基本思想是根据已 有资料或者设计好的分布预先决定统计分布，再由分布来产生随机数，以此来输 入模型求其结果。蒙特卡罗法能够模拟实际的物理过程，解决问题与实际非常符 合，只要产生的随机实验数据足够多，就可以得到较准确的结果。 根据实际运行网络中的统计数据，网络节点上请求的到达是一个简单流，即 请求的到达服从泊松分布，请求的持续时问服从指数分布。因此可以随机地产生 这些请求，并使网络中每个节点请求到达的时间间隔服从泊松分布，请求的需求 带宽在一定范围内均匀分布，请求的持续时间服从指数分布，请求节点与目标节 点在网络拓扑中依据概率分布随机取值，请求的其它服务质量要求同样也在一定 范围内均匀或按某种概率分布。然后将这些请求数据输入网络模型中，模拟其进 行路由选择以及占用链路带宽并进行传输和释放带宽的过程。根据现实网络拓扑 以及链路有效带宽信息来判断路由的正确性。这样通过改变网络拓扑参数、产生 随机请求的参数就可以构建各种负荷的网络环境，通过模拟就可以得到路由算法 的性能参数，并可以对一些算法进行比较。 2 3 路由算法性能评价指标 目前，评价路算法的性能主要是采用用户请求接受率和网络带宽利用率两项指 标。为了更加准确地评价和比较q o s 选播路由算法的性能，提出了五种测量路由 算法有效性的参数。这些参数都是根据网络模拟器所测得的六个统计数字计算而 来的。依据不同的网络拓扑、不同的配置参数、不同的路由算法，通过网络模拟 测试器可以得到在整个模拟期间以下六个统计数据： 1 r e q u e s t s 表示所到达的q o s 数目； 2 s u c a e s s e s 表示所能满足的q o s 请求数目； 8 坝士学位论文 3 f a j r o u t e s 表示路出算法找到一条无效的路径，且实际网络中没有能满足 的q o s 的路径的情况数目； 4 w r o n g r o u t e s 表示路出算法找到一条无效的路径，且实际网络中有能满足的 q o s 的路径的情况数目；f a i i r o u t e s 和w r o n g r o u t e s 反映了由于网络路由算法的 缺陷或网络状态信息更新策略的影响而无法准确寻找到路径的情况。 5 w r o n g r e j e c t s 表示路由算法没有找到一条合适的路径，且实际网络中有能 满足的q o s 的路径的情况数目； 6 r i g h t r e j e c t s 表示路由算法没有找到一条合适的路径，且实际网络中也的 确没有有能满足的q o s 的路径的情况数目； 为了描述以上数据之间的关系，可以假设s e t # x 表示某类数据的集合，其相 互之间的关系可以表示为： s e t # r e q u e s t s ) - x lx 路由算法接受的q o s 请求) + y i y 路由算法拒绝的 q o s 请求) s e t # s u c c e s s e s + s e t # f a i l r o u t e s ) + s e t # w r o n g r o u t e s = f x i x e 路由算法接 受的q o s 请求) s e t # w r o n g r e j e c t s ) + s e t # r i g h t r e j e c t s ) = y iy 路由算法拒绝的q o s 请求) 从模拟测试系统中可以获取以上六个统计数据，用下面五个参数来反映网络 路由算法的性能： 成功接受率：s r r = # s u c c e s s e s # r e q u e s t s 寻径失败率：f r r = # f a i1 r o u t e s # r e q u e s t s 寻径错误率：w r r = 棹w r o n g r o u t e s # r e q u e s t s 错误拒绝率：w j r = w r o n g r e j e c t s # r e q u e s t s 正确拒绝率：r j r = # r i g h t r e j e c t s # r e q u e s t s 很明显可知：s r r + f r r + w r r + w j r + r j r = l 。这些参数反映了q o s 路由算法的有效 性、网络负载、网络状态更新策略的有效性等网络性能指标。例如：当网络负载 很重时，无论采用什么路由算法，w j r + r j r 必然较高。在以前的研究中，采用s r r 作为唯一的评价指标。s r r 的确在某种程度上反映了路由算法的优劣，但是其他四 个指标在评价路由算法性能方面的作用不可忽视。 在支持q o s 的网络体系中，目前大量采用资源预留协议r s v p ( r e s o u r c e r e s e r v a t i o np r o t o c 0 1 ) 。对于某个实时应用，其工作可以分为三个阶段： 第一阶段：利用q o s 路由算法在发送者和接受者之间寻找一条满足应用程序服 务质量要求的路径。 第二阶段：应用程序采用r s v p 在所找到路径上的路由器中保留所需的资源。 第三阶段：应用程序利用这些保留的资源通过同样的路径发送实时业务流量。 如果第一阶段中的路由算法所确定的路径，在第二阶段中某一路由器没有足 9 够的资源支持所需的服务质量，这必将造成网络资源的浪费。在评价指标中， f r r + w r r 就反映了这一情况。一个的效的q o s 系统应具备以下特点：s r r 高，f r r + w r r 比较低，而r j r 在r j r + f r r 中所占比例应高。 2 4 网络模拟器r n s 的设计 网络模拟器在研究和测试新的网络技术方面有巨大作用，并且避免了建立网 络测试平台的高成本和复杂性。模拟器能够评价在不同网络条件下的网络性能， 为网络新技术研究提供可靠的实验依据。一个好的模拟系统应具有以下特性： 能够支持大规模数据的测试。由于模拟系统主要通过统计特性反映网络性能， 因此需要测试大量数据来分析其统计特性。 狈0 试数据易于修改。网络的性能与许多测试数据参数存在直接的关系，在模 拟期间，经常需要调整网络参数，因此模拟器中应提供测试参数易于修改的途径。 可扩充。网络模拟器需不断补充新的功能模块，添加新的测试算法，因此必 须提供良好的扩充编程接口。 可视化界面。网络模拟器应能为研究者提供可视化界面，方便研究者分析实 验结果，并能动态跟踪模拟的整个过程。 一一一一一一- r 一一一一一一一一一一 网络拓扑生成器：! 网络负载生成器 圈圈匝 图2 1 网络模拟器r _ n s 模型 网络模拟器r _ n s 的设计主要是为了测试不同q o s 路由算法在不同网络参数下 的性能指标。主要网络参数包括网络的拓扑、网络链路状态更新策略、网络流的 特性及分布、性能评价指标、路由选择算法、网络调度算法、网络接入控制策略 = = = = = = = = ：= 。：堕兰兰笪塞墼窒三一：一! ：= 一：一 等。r n s 的模型如图2 1 所示。 网络模拟器r n s 主要包括网络拓扑生成器、网络负载生成器、网络模拟处理 器和模拟结果收集统计分析器。 网络拓扑生成器主要功能为：产生网络拓扑结构，并构造初始网络链路状态 信息。主要包括两种产生方式：人工产生拓扑和实际网络的拓扑结构。实际网络 拓扑结构主要包括i n t e r n e t 主干网、m b o n e 、a t m 测试网、一些企事业单位的专用 网络等，网络拓扑信息库保存这些网络拓扑结构，在模拟过程中使用。人工产生 拓扑主要是根据某种需要构造网络拓扑结构或随机产生，其目的主要为评价网络 拓扑对网络性能的影响。 网络负载生成器负责产生整个模拟期间的网络请求。每个结点上的请求到达 服从泊松分布，平均到达间隔为t 1 秒( 其中热点平均到达时间间隔是t 2 秒， t 2 7 m 则触发链路状态 更新。 基于均匀分类的更新方法。对于某一固定的常数毋将链路中可得到的带宽分 成大小相等的区域，即( 0 ，占) 、( b ，2 b ) 、( 2 b , 骝) ，如果链路j 的实际值 与其他路由器中该链路的建议值。不在同一区域内，则触发链路状态更新。 基于指数分类的更新方法。对于固定的常数b 和f ，将链路中可得到的带宽分 大小不相等的区域，即( 0 ，占) 、( 夙( 一j ) 占) 、( ( 一) 及( ，十一j ) 劫，如果链 路的实际值三。7 与其他路由器中该链路的建议值。7 不在同一区域内，则触发链 路状态更新。 模拟结果收集统计分析器的主要功能是收集在不同网络参数条件下 # s u c c e s s e s 、# r e q u e s t s 、# f a i l r o u t e s 、# w r o n g r o u t e s 、# w r o n g r e j e c t s 和 # r i g h t r e j e c t s 的值，分析不同条件下的网络性能，为优化网络性能提供实验依据。 2 5 网络模拟器r n s 的实现 网络模拟器r n s 采用v c + + 6 0 在w i n d o w s 2 0 0 0 环境下开发实现。网络模拟器 r n s 的工作流程如图2 2 所示。 网络拓扑一般可以用邻接矩阵和邻接链表来表示，一般来说，使用邻接链表 占用存储空间较少，而且处理邻接关系也较方便。因此模拟系统中采用邻接表来 保存网络拓扑以及链路有效带宽信息。网络中的每一个节点均维护一个这样的邻 接链表。为了有效地评价路由算法的性能，需要在不同网络拓扑结构下进行测试。 建立网络拓扑图库，保存一些经典的网络拓扑结构，如：a r a p n e t ，m c i ，i s p 等。 同时设计网络拓扑产生器，用于产生一些随机网络拓扑结构和特殊的网络拓扑， 例如：m e s h ，c u b e 等。 l 从拓扑信息库中提取网- 络拓t b n g n 网络链路初始状态信息 l i产生o 。s 请求呼叫序列，并对请求呼叫序列进行处理 l f 对请求序列中每个呼叫计算路由、判断能否被路由算法所接 l l进行网络资源预留：网络状态更新的处理 l i收集统计网络状态信息，使用m s c h a r t _ 显示统计分析结果 图2 2 网络模拟器r n s 的工作流程 在模拟过程中，网络中产生的请求总数是由用户指定的。请求数目越大，实 验受随机因素影响越小，实验结果也越精确。但是实验模拟所需的存储器资源和 处理器资源也会随之增大，运行的时间也会加长。对于实际网络中的每个节点， 请求的到达以及处理都是并行的，但网络模拟器在处理的时候，把它们看成是有 时序的，按照请求的到达时刻来对他们进行串行的处理。 硕士学位论文 2 6 小结 本章首先介绍了网络模拟器设计的基本思想和设计思路，提出了网络路由评 价模拟器的模型和性能评价指标体系，并且论述了网络模拟器的具体实现过程。 网络模拟器r n s 的设计主要是为了测试不同q o s 路由算法在不同网络参数下的性 能指标。主要参数包括网络的拓扑、网络链路状态更新策略、网络流的特性及分 布、性能评价指标、路由选择算法、网络调度算法、网络接入控制策略等。网络 模拟器r n s 主要包括网络拓扑生成器、网络负载生成器、网络模拟处理器和模拟 结果收集统计分析器四个部分。模拟器的设计与实现对网络路由算法的研究提供 了很好的支撑环境。本文所提算法用此模拟器进行测试和性能评价。 ：一 = 堡：圭兰堡堡三一： ：一：一! 一= 一： 第3 章基于随机策略的q o s 路由算法 本章针对传统q o s 路由算法忽视了网络负载平衡和整体性能的问题，提出了 一种随机q o s 路由算法。该算法利用网络平均空闲率作为算法的性能评价指标， 结合新提出的安全度计算公式，来寻找传输路径。实验结果表明，此算法能较好 地提高网络负载能力和优化网络的整体性能。 3 1 概述 及时传输有服务质量q o s 要求的多媒体信息对于集成服务的宽带网络发展提 出了新的挑战。q o s 路由为不同q o s 请求寻找满足要求的传输路径，是实现网络支 持q o s 的关键问题之一。q o s 路由的研究目标是：最大限度的满足各种不同的q o s 要求和保证全局网络资源的有效利用率“”。”1 。 路由的研究包括两个内容：收集、更新网络状态信息和根据网络状态信息计 算出合适的传输路径。网络路由的确定需要各条链路状态的精确信息，由于网络 状态信息是不断变化的，如果要保持网络状态信息的准确性，需要随时更新网络 状态信息，这将导致庞大的网络额外开销，会使网络整体性能下降。另外，网络 规模的扩展、分层结构的引入使得网络高层在做出决断时，缺乏底层具体物理网 络状态信息的支持，高层主要是依据高层次逻辑结构来做决断的。因此网络链路 状态信息一般是不精确的。“”1 。 q o s 路由策略通常分为：源端路由、分布式路由和层次路由3 种。源端路由每 个节点都维护完整的全局信息，源端节点根据全局信息计算一条可行路径，然后