（计算机系统结构专业论文）overlay网络路由算法的研究.pdf

重庆大学硕士学位论文中文摘要 摘要 o v e r l a y 网络是由一系列分布在i n t e r n e t 各个自治系统内部的0 v e r l a y 服务节 点以及连接它们的逻辑链路所组成的虚拟网络，它能有效地利用i n t e m e t 给终端用 户提供更为可靠的服务。o v e r l a y 网络的优劣取决于所提供的q o s 的好坏。 研究o v e r l a y 网络的服务质量，关键取决于o v e r l a y 网络模型的路由算法，在 某一模型下表现为最优的算法在另一模型下可能效果最差，不同的o v e r l a y 网络模 型通常都有自己的路由算法，每种算法的不同具体表现为代价公式不同，选取的 q o s 参数不同等。每一种o v e r l a y 网络模型下的路由算法的目标均为在保证q o s 的同时均衡网络资源，使有限的网络资源能够提供更多的服务。 q u e s t 框架是o v e r l a y 网络模型的一种，由x g | u 等人提出的一种保证组合服 务的架构，该模型可以在服务o v e r l a y 网( s o n ) 中为服务寻求多q o s 约束条件下的 最佳路径，并均衡网络资源，其路由的核心内容是q s c b 算法。q s c b 算法通过 代价公式判断代价值来完成对链路的选择，当其代价值出现相等的情况下，该算 法通常随机选取一条链路，并未考虑到网络均衡的问题，不能有效的平衡网络资 源，违背了最初算法的初衷。参照其它o v e r l a y 系统处理网络均衡性的算法，我们 为q s c b 算法的代价公式引入了平衡系数，使得服务选取一条保证q o s 的路径的 同时可以兼顾网络资源的均衡，提高了算法均衡网络资源的能力。随着网络资源 均衡性的提高，不仅可以使有限的网络资源为更多的用户提供服务，同时网络资 源的利用率以及用户的满意率都会有所提高。 通过仿真试验，随机的选择节点、链路、服务建立一个服务o v e r l a y 网络来模 拟q u e s t 框架来对比引入平衡参数后的算法与原算法，均衡网络资源效果略有提 高，q o s 满意率、链路通信负载、节点计算负载均有不同程度的提高，证明改进 后的算法在原链路代价公式相等的情况下可以更好的处理网络均衡的问题，达到 了预期的效果。 最后我们得出结论，改进后的算法在均衡网络资源方面优于原算法，同时使 得q u e s t 框架在q o s 满意率、节点和链路的利用率方面得到了一定的提高。 关键词：o v e r l a y 网络，q u e s t ，网络负载均衡，q s c b 算法 重庆大学硕士学位论文 英文摘要 a b s t r a c t o v e r l a yn e t w o r ki sv i r t u a ln e t w o r k ，w h i c hc o m p o s e db yal o to fn o d e sa n dl i n k s e v e r yn o d ea n dl i n kb e t w e e nn o d e sa r ei ns o m ea s ( a u t o n o m ys y s t e m s ) w h i c h m a n a g e db yi s p ( i n t e r n e ts e r v i c ep r o v i d e r ) o v e r l a yn e t w o r kc a np r o v i d er e l i a b l e s e r v i c et ou s e r , a n dc a nn o tc h a n g et h ef r a m e w o r ko fi n t e m e t t h ec a p a b i l i t yo fa o v e r l a yn e t w o r ki sd e c i d e db y t h ea b i l i t yt op r o v i d eq o s n er e s e a r c hq o si no v e r l a yn e t w o r k , t h er o u t i n ga l g o r i t h mo fo v e r l a yn e t w o r k m o d e li sv e r yi m p o r t a n t t h es t u d yr o u t i n ga l g o r i t h mi no v e r l a yn e t w o r ki st e s t i f i e dt h a t o n ea l g o r i t h mw h i c hr e p r e s e n t st h eb e s tp e r f o r m a n c ei ns o m e o n eo v e r l a yn e t w o r k f r a m e w o r km a y b ei st h ew o r s tp e r f o r m a n c ei i ia n o t h e ro n e t h ed i f f e r e n to v e r l a y n e t w o r km o d e l sh a v ed i f f e r e n to v e r l a yn e t w o r kr o u t i n ga l g o r i t h m ，w h i c hh a v ed i f f e r e n t c o s tv a l u eo rp a r a m e t e ro fq o s t h eg o a lo fa l lr o u t i n ga l g o r i t h m si no v e r l a yn e t w o r k a r es e a r c has a t i s f yp a t hf o rs e r v i c em e a n w h i l et h ea l g o r i t h mm u s th a v et h ea b i l i t yo f l o a db a l a n c i n gi ns o n ( s e r v i c eo v e r l a yn e t w o r k ) w h i c hc o u l do f f e rm o r es e r v i c ew i t l l t h es a m en e t w o r kr e s o u r c e q u e s ti so n eo fm o d e la b o u to v e r l a yn e t w o r k ，i sf i r s tb r i n gf o r w a r db yx c m q u e s tf r a m e w o r k i saq o s a s s u r e dc o m p o s i t i o ns e r v i c ei n f r a s t r u c t u r e i tc a n s i m u l t a n e o u s l ya c h i e v eq o s a s s u r a n c e sa n dl o a db a l a n c i n gi ns o n t h ec o r eo f r o u t i n g a l g o r i t h m si nq u e s t i sq s c ba l g o r i t h m 1 1 1 ej o bo fq s c ba l g o r i t h mi sc h o o s et h e p a t hf o rt h es e r v i c ew h i c hd e t e r m i n eb yt h ep a t h sc o s tv a l u e ，w h e nt w oo rm o r ep a t h s h a v et h es a m ec o s tv a l u e ，t h eq s c bi sc h o o s eo n e r a n d o m l y a c c o r d i n gt oa n a l y s i sa n d s t u d yt h eq s c b ，w ef o u n dt h ew a yo fq s c bt os o l v et h ep r o b l e mw h i c hm o r ep a t h s h a v et h es a l t l ec o s tv a l u ei sn o tc o n s i d e rt h ea b i l i t yo fl o a db a l a n c i n g ，a n dc a nn o tl o a d b a l a n c i n gi ns o n a ta 1 1 s oi t sn o ta c c o r dw i t ht h eg o a lo f r o u t i n ga l g o r i t h m si no v e r l a y n e t w o r k w ef o l l o wt h ew a yo fo t h e rr o u t i n ga l g o r i t h m si no v e r l a yn e t w o r k , a d da b a l a n c i n gp a r a m e t e rt ot h eq s c b t h ep u r p o s e si sc h a n g et h es ：l q l ec o s tv a l u et o d i f f e r e n t , a n df i n a l l yc h o o s et h eb e s tp a t hw h i c hs a t i s f yt h ep a r a m e t e ro fq o sa n dl o a d b a l a n c i n g i i ls o n b y g e tt h eb e t t e rl o a db a l a n c i n gi ns o n w ec a nn o to n l y o f f e rm o r e s e r v i c ew i t ht h es a m en e t w o r kr e s o u r c e ，b u tc a r li m p r o v et h er a t eo fq o ss a t i s f a c t i o n a n dt h em t eo f n o d ea n dl i n k su s i n g i no u rs i m u l a t ee x p e r i m e n t ，w ec h o o s et h en o d e s ，l i n k s ，s e r v i c er a n d o m l yt ob u i l d am o d e lo f o v e r l a yn e t w o r k t h er e s u l to f c o m p a r i s o no f q s c ba n di m p r o v e di st h a tt h e i l 重庆大学硕士学位论文 英文摘要 i m p r o v e da l g o r i t h mi sb e t t e ri nt h ea s p e c to ft h e r a t eo fq o ss a t i s f a c t i o na n dt h er a t eo f n o d ea n dl i n k su s i n g ，b u ti sn o to b v i o u s l y a c c o r d i n gt oo u ra n a l y s i s ，t h ei m p r o v e d a l g o r i t h mi so n l ys o l v et h ep r o b l e mo fm o r ep a t h sh a v et h es a n l cc o s tv a l u e ，t h em o r e p r o b l e mh a p p e n ，t h eb e t t e re f f e c to f i m p r o v e da l g o r i t h m a n dw es t i l lt r ya n o t h e rt e s tt o t e s t i f yt h ev a l i d i t yo f0 1 1 1 i m p r o v e da l g o r i t h m w ec h o o s es e v e nn o d e sa n dt h r e e s e r v i c e sa n dr e g u l a t et h el i n k sa n dp a r a m e t e ro fq o st os i m u l a t et h ei n s t a n c eh a p p e n i n t h i st e s tw ec a np r o v eo u ri m p r o v ea l g o r i t h mi sv a l i d i t y i nt h ee n d ，w ec a ng e tac o n c l u s i o n t h ei m p r o v e da l g o r i t h mi sb e t t e rt h a nq s c b i nt h ea s p e c to fs o l v i n gt h ep r o b l e mo fm o r ep a t h sh a v et h es a n l ec o s tv a l u e a n di t i m p r o v e dt h er a t eo f q o ss a t i s f a c t i o na n dt h er a t eo f n o d ea n dl i n k su s i n go f q u e s t k e y w o r d s ：o v e r l a yn e t w o r k ，q u e s t , l o a d - b a l a n c i n g ，q s c ba l g o r i t h m 1 1 i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特另j j ) j n 以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废盔堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 徭李萏 签字日期：c 妒7 年，月争日 学位论文版权使用授权书 本学位论文作者完全了解重庞太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重废太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 、) 。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名： 签字日期：。加7 年月4e l 导师签名：劳玉暑 签字日期：- z - o 年多月q - e t 重庆大学硕士学位论文 l 绪论 1 绪论 1 1o v e r l a y 网络的提出 i n t e m c t 是由许多自治系统( a u t o n o m o u ss y s t e m s ，a s ) 组成的，每个a s 一般 由一个独立的实体来控制，大部分是商业化组织，如( i n t e r n e ts e r k , i c ep r o v i d e r , i s p ) 。 a s 之间可以有两种连接方法：t r a n s i t 和p e 耐n g 。 t r a n s i t 的连接关系是在i n t e r a c t 上公开发布的，如果自治系统b 和c 是 t r a n s i t 的连接关系，则任何以c 为目的地的包都可以通过b 路由，反之亦然。 p e e r i n g 的连接关系是秘密的，仅对其内部用户可见，对其它的a s 是不可见的， 如果自治系统是p e e r i n g 的连接关系，则b 和c 的内部用户可以使用它们之间的 连接，而其它a s 的用户则不能利用b 和c 之间的这种连接关系，即不能通过b 把包直接路由到c 或者通过c 把包直接路由到b 。t r a n s i t 的连接信息是由边界网 关协议饵o r d e r g a t e w a y p r o t o c o l ，b g p ) 发布，它允许a s 们相互交换路由信息，但 是它提供的通常不是最佳路由，此外，b g p 协议并不探测路径性能，不能绕过拥 塞连接。新应用的不断涌现，对服务质量要求越来越高，目前的i n t e m e t 已经越来 越不能满足人们的服务要求了。而我们从t r a n s i t 和p e e r i n g 对路由的影响可以看 出，利用应用层上中间结点可以提供一条更加有效的传输路径。 在这种情况下，o v e r l a y 网络诞生了，他并不需要大规模的改变现有网络的架 构就可以提供更为可靠、容错性更好的路由。o v e r l a y 网络是由一系列分布在 i n t e r n e t 各个自治系统内部的o v e r l a y 服务节点以及连接它们的逻辑链路所组成的 虚拟网络，他能有效地利用i n t c r n c t 给终端用户提供更为可靠的服务。o v e r l a y 节 点通常具有路由、数据处理和数据保存的功能，而逻辑链路( 即o v e r l a y 链路) 通常 对应底层的一条或者多条物理路径。 1 20 v e r l a y 网络的应用 1 2 1p 2 p 文件共享 在过去的几年中，如g n u t e l l a 这样的对等( p e e r t o p e e r ，p 2 p ) 文件共享软件 在i n t e m e t 上迅速传播，用户数量急剧增长。这类系统中，数据被保存在终端用户 主机中，而不像传统的集中控制模式( 如c s ，b s ) 那样把数据存放在服务器上。 所有的终端主机都是对等的，这些对等节点组成了一个o v e r l a y 网络。其优点如下： 分散化。网络中的资源和服务分散在所有的节点上，信息的传输和服务的实现 都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了部分瓶颈。 分散化是p 2 p 的基本特点，由此带来了其在可扩展性、健壮性等方面的优势。 重庆大学硕士学位论文1 绪论 可扩展性。传统的c s 架构中，系统能够容纳的用户数量和提供服务的能力主 要受服务器的资源限制。而在p 2 p 网络中，随着用户的加入，不仅服务的需求 增加了，系统整体的资源和服务能力也在同步地扩充，始终能比较容易的满足 用户的需要。 健壮性。传统的集中式服务模式中，集中式服务器成为整个系统的要害所在， 一旦发生异常就会影响到所有用户的使用。而p 2 p 服务是分散在各个节点之间 进行的，部分节点遭到破坏对其他部分影响很小。而且p 2 p 模型一般在部分节 点失效时能够自动调整整体拓扑，保持其它节点的连通性。 高性能。采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将计算 任务或存储资料分布到所有节点上。利用其中闲置的计算能力或存储空间，达 到高性能计算和海量存储的目的。 1 2 2 内容分送网络 一般情况下网站响应速度的快慢和访问者与网站服务器之间的“距离”密切相 关。为了改善网站响应速度，内容分发网络( c o n t e n td e l i v e r y n e t w o r k ，c d n ) 提 出了“让内容离用户更近”的思路。c d n 的技术原理是在遍布世界的主要i n t e m e t 接入点部署内容服务器节点，在这些节点的基础上组成一个o v e r l a y 网络，并利用 一种特殊的路由机制将网站内容发布到离用户最近的网络“边缘”，使用户能以最快 的速度、从最接近的地方获取所需要的信息。目前c d n 在国外已经得到了广泛的 应用，如著名c d n 提供商a k a m a i 早在2 0 0 1 年6 月就已经在全球部署了1 1 6 8 9 台 服务器，覆盖6 2 个国家8 2 0 个网络。国内的c d n 应用也已经起步，如c h i n a c a c h e 公司已经在全国部署了4 0 个c d n 服务节点。 1 2 3 应用层组播 在坤组播中，与组播相关的功能都放在网络层即路由器上实现，路由器负责 记录组播组的存在和组成员的变化，并在组成成员问构造一颗组播发送树。数据 源只需要向组内发送一份组播数据，由路由器在恰当的分支复制数据，就可让所 有组员都收到数据。任何一份数据拷贝只会在每条组播链路上出现一次，这样就 有效的降低了主机服务负载、网络通信负载，因此被认为是解决组内通信的最理 想方式。然而经过1 0 多年的研究，i p 组播技术仍然只是停留在实验平台( 如 m b o n c 2 ，i n t e m e t 2 3 】等) 上的应用阶段，一直没有能够进入商业领域，概括来说 主要由于以下几个原因造成的：组播需要路由器的支持，每个组播路由器需要 为每个组地址甚至十组播业务源保存组状态。由于组地址时动态分配的，不能够 像单播地址那样得到有效的汇聚，需要在路由器内保存大量组状态，这增加了路 由器的开销和实现的复杂性。口组播目前缺乏有效的可靠传输和拥塞控制机制， 可能对正常的单播业务造成伤害，组播的拥塞控制机制非常难解决，在没有可靠 2 重庆大学硕士学位论文1 绪论 的拥塞控制机制之前，i s p 不会在他们的网络上大规模配置组播业务。目前还缺 乏对组播流的合理收费模型。 o v c n a y 网络的提出使得实现组播成为了可能。所谓应用层组播是指将原本在 网络层即路由器上实现的组播相关功能移动到应用层即终端主机上来实现。在应 用层组播中，所有的终端节点组成一个o v e r l a y 网络，每个终端主机都是一个 o v e r l a y 服务节点。为了更好的利用网络资源，应用层组播也需要在组成员之间建 立一颗组播分布树，与口组播不同的是，应用层组播的分叉点必须是终端系统， 也就是说组播数据的复制是在终端系统中实现的，所以有些链路可能由多份数据 拷贝，效率不如口组播。但是在应用层组播有如下优点：它不需要路由器的支 持，m 组播之所以不能在i n t e m c t 上使用就是因为大部分路由器不支持，应用层组 播绕开了这一点。由于任何两个组员之间在发送数据或接受数据时都是单播放 式，所以可以使用单播流量控制和差错控制协议，从而简化了口组播的拥塞控制 机制。 1 3o v e r l a y 网络的研究现状 目前国内对0 v c f l a y 网络的研究主要集中在通用平台、网络拓扑、路由等几个 方面。 1 3 1o v e r l a y 网络通用平台的研究 大部分o v e r l a y 网都是针对特定的网络，如c h o r d l 4 1 、b r o c a d e 5 1 和t a p e s t r y 6 】 等都是为基于良好定义架构( w e l l d e f i n e d ，s t r u c t u r e - b a s e d ) 应用而设计的，其主要 的目标都是在一个大的分布式系统中对内容进行迅速的定位，这些研究仅仅是基 于某种应用的o v e r l a y 网构架，但是随着o v e r l a y 网的增加，有人提出了通用o v e r l a y 网，它能对已有的和将来的o v e r l a y 应用提供支持。当前对此的研究主要有o s n ( o v e r l a y s e r v i c e n e t w o r k ) ，o p u s ( o v e r l a y p e e r u t i l i t y s e r v i c e ) ，o v e r q o s ( o v e r l a y n e t w o r k o f f e r i n g q o s ) ，s o n ( s e r v i c e o v e r l a y n e t w o r k ) 等。 1 3 2o v e r l a y 网络的拓扑研究 设计一个o v e r l a y 网络，第一步就是选择一个连接所有o v e r l a y 服务节点的网 络拓扑结构。不同的拓扑模型对o v e r l a y 网的性能有很大的影响，目前已经有不少 o v e r l a y 网拓扑的研究。 文献【7 】数学上的维数和曲率的概念运用到了o v e r l a y 网的拓扑图的构建上。文 献【8 研究了带宽保证下的o v e r l a y 网络拓扑设计问题，文中提出了一个启发式算法 来设计运行费用最小化的o v e r l a y 网络拓扑。文献【9 】提出了一种利用交叉生成树 ( i n t e r l e a v e ds p a n n i n gt r e e ) 来设计o v e r l a y 网络拓扑的方法，用此方法设计的拓扑 具有如下特征：高性能，多路径，自组织。文献【1 0 】针对p 2 p 系统拓扑的研究，在 3 重庆大学硕士学位论文 1 绪论 p 2 p 系统中节点加入退出频繁，经常导致实际网络拓扑和每个节点保存的拓扑不匹 配，文章提出了一种自适应o v e r l a y 拓扑最优化技术，能有效地减少拓扑不匹配的 问题并带来更高的查询效率。 文献1 1 1 1 把o v e r l a y 网的拓扑模型分为两类，一类是不知道或者不利用物理层 网络拓扑的，如全网格( f u l lm e s h ) 、网格树( m e s h t r e e ) 、最小生成树( m i n i m u m s p a n n i n gt r e e ) 等；另外一类是知道物理层网络拓扑的，如邻近连接( a d j a c e n t c o n n e c t i o n ) 和知道物理层拓扑的最小生成树( t o p o l o g y - a w a r em i n i m u ms p a n n i n g t r e e ) 等。同时文献d 1 还对这些拓扑结构利用不同的路由算法进行仿真试验，通 过对错误修复率、路由耗费等性能指标的对比后得出了以下几个结论：网络拓 扑对o v e r l a y 网的路由服务性能有重大的影响，在一种网络拓扑下表现最好的路由 算法在另外一种拓扑结构下可能最差；下层物理网络拓扑信息对构建一个高效 率的o v e r l a y 网拓扑结构是非常有用的，因为指导物理层网络拓扑的o v e r l a y 网拓 扑模型在各种路由算法下性能表现普遍比其他拓扑模型好。 1 3 3o v e r l a y 网络的路由研究 路由问题是o v e r l a y 网络研究的关键问题之一。目前国内外对o v e r l a y 网络的 路由问题已经进行了大量的研究。 a k a r o u t i n g i l 2 】是内容分送网络系统a k a m a i 的路由解决方案，它包括m a p m a k e r 和g u i d e 两个组件，m a p m a k e r 探测i n t e r n e t 的全局“距离”，并为每个a k a m a i 数据 中心和内容提供商节点之间建议三条较佳路由路径，而g u i d e 则比较这三条路径， 从中选择一条最佳的路径。 文献【1 4 提出了一种基于最大收益的d n s 内容路由算法，该算法采用名字解 析服务器与网关处分别获取内容服务器负载信息和网络路有信息生成网络收益， 根据最大网络收益选取最佳的内容服务器。 文献【1 3 】 1 5 】则是针对o v e r l a y 网络组播路由的研究，提出了均衡度分配 ( b a n l a n c e dd e g r e e a l l o c a t i o n ，b d a ) 的路由方案能够有效地均衡网络负载并减少 端到端时延。文献 3 1 】也是对o v e r l a y 网络组播的路由研究，文中提出了一种启发 式路由算法来解决o v e r l a y 网络组播中的“最小直径、剩余均衡、度数受限的生成 树”问题。 文献 1 8 】研究了如何在o v e r l a y 网络内部节点和外部节点之间实现路由，提出 了n a t r o n 的网络架构并在该架构上设计实现了一种启发式算法来选择路由路 径。 不同的o v e r l a y 框架的路由算法都有其相对于自身的优势，在某一框架下表现 为最优的算法放入另一框架很可能会成为最差，因此，目前鉴于通用的o v e r l a y 框 架同样在研究中，通用的算法的研究相对较少，对于o v e r l a y 网络路由算法的研究 4 重庆大学硕士学位论文 i 绪论 大部分都是针对特定的网络而进行的，每一个服务体系下的路由算法各有利弊。 1 4 0 u e s t 框架 q u e s t 框架是o v e r l a y 网络模型的一种，由x o u 等人提出的一种保证组合服 务的架构，该模型可以在服务o v e r l a y 网( s o n ) 中为服务寻求多q o s 约束条件下的 最佳路径，并均衡网络资源，其路由的核心内容是q s c b 算法。 相对于其它的o v e r l a y 网络模型，q u e s t 具备以下优点：( 1 ) 多q o s 条件下选 路的同时能均衡网络资源；( 2 ) 动态服务组合，当现有服务路径失败时自动使用备 用路径代替现有路径。 由于涉及到收费、管理等诸多问题，该框架同许多o v e r l a y 网络模型一样尚未 被大量应用。q u e s t 模型的路由算法q s c b 算法具有均衡网络资源的功能。 但是经过我们研究分析发现，当多条路径代价值相等时，该算法就失去了均衡网 络资源的能力。为了解决该算法在这种情况下不能调节网络资源的问题，参照其 它路由算法均衡网络资源的方法式，我们为q s c b 算法引入了平衡系数，在一定 程度上解决了上述问题。 1 5 本文的主要工作及篇章结构 本文在对q u e s t 框架下及其路由算法进行了分析的同时，也对现有的q o s 路由、o v e r l a y 网络的q o s 路由策略和算法进行了研究和分析。在此基础上，参照 其它算法，针对q u e s t 框架下的路由算法在链路代价值相等的情况下不能有效的 均衡网络资源的不足提出一些改进。主要目的是当出现上述情况时，改进后的算 法能在找到一条满足q o s 要求的路由路径的同时均衡网络的资源。改进实现的具 体目标为：为服务选出一条满足q o s 的路径的同时均衡网络资源；提高原算 法的q o s 满意率；增加链路通信负载，提高对链路资源利用；增加节点计算 负载，提高对节点资源利用。 我们需要完成以下工作： 引入适当的平衡系数 模拟网络实验环境，验证改进后算法的正确性 对实验结果进行分析，分析改进后算法自身的优劣 总结研究期间的相关工作 首先，我们参照s b s q r 算法均衡网络资源的方式，为q s c b 算法引入平衡系 数，引入的平衡系数为一段时间内网络测量的平均值，平衡系数的引入，理论上 可以将原链路代价值相等的路径重新计算会获取不同的链路代价值，从而找到一 条满足q o s 要求的路由路径的同时达到均衡网络资源的目的。 5 重庆大学硕士学位论文l 绪论 其次，需要通过仿真实验验证改进后的算法在q o s 满意率、链路通信负载、 节点计算负载等方面比原算法是否有所提高，同时证明改进后的算法在原链路代 价公式相等的情况下是否可以处理网络均衡的问题。在仿真实验中，我们选取了 七个节点，三个服务以及若干条链路来对于改进前后的算法进行仿真实验，主要 目的是验证算法的正确性。 再次，对实验结果进行分析，实验结果证明改进后的算法在处理网络资源均 衡方面是有效的，但是，改进的算法仅仅解决了原算法的一种特殊的情况即原算 法链路代价公式相等而无法均衡网络资源。因此，通过分析证明了改进后算法的 优势与原算法链路代价公式相等的频率相关，代价公式相等的次数越多改进后的 算法的优势越明显。 最后，我们对算法的改进进行了全面的总结。改进后的算法仍存在不足，例 如跳数、服务类型的方面尚未考虑，笔者希望可以为后者提供帮助，让后续研究 工作能够更加完善q s c b 算法。 本文篇章结构如下： 第一章介绍了o v e r l a y 网络的相关背景知识以及研究现状。 第二章分析了三种q o s 路由策略的优缺点，介绍了现有的q o s 路由算法，指 出o v e r l a y 网络的q o s 算法和一般的q o s 路由的区别，然后介绍了o v e r l a y 网络 q o s 路由方案。 第三章分析了q u e s t 框架以及其算法的优缺点，详细阐述了如何对现有的算 法进行改进，达到均衡网络资源的目的。 第四章对改进后的算法进行了仿真比较，并分析了仿真结果。 第五章对全文进行了总结，并对q s c b 算法提出新的展望。 6 重庆大学硕士学位论文 2q o s 路由和o v e r l a y 网络的q o s 路由 2q o s 路由和o v e r l a y 网络的q o s 路由 2 1 基本路由算法 在i n t e r n e t 等分组交换网中，由于没有建立连接电路，传送的每个分组都需要 携带传送目的地址以及到达终点的各中间节点的路由信息。构造路由表可以使用 集中式算法或者分布式算法。由于节点或链路时效以及新节点或动态链路加入时， 可能导致网络拓扑的变化，集中式算法不能处理这种情况。分布式算法知道网络 拓扑的改变，根据更新的拓扑信息来计算路由路径，因而更具有动态性。下面介 绍几种路由算法，几乎所有复杂的路由算法都是由这几种算法演化而来的。 2 1 1d i j k s t r a 最短路径算法 通信网络可以模型化为一个图形，其中顶点和边代表网络的节点和链路。同 心链路的代价表示为图形中的相关边的权值。d i j k s t r a 为集中式算法，需要完整的 网络拓扑和链路权值，以此来计算从一个指定源节点到网络中其它节点的最短路 径。图g = g ( v ，目，其中v 和e 分别表示图形的顶点和边的集合。从顶点u 到顶 点v 的边的权值表示为w ( u ，v ) ，须为非负的。一条边的权值尺度包括跳数( 即 “，v ) = 1 ) 、链路带宽、平均传输时延或者它们的组合。算法使用一种权值尺度来 计算最短路径。 d i j k s t r a 算法的步骤如下： 各个节点用从源节点沿已知最佳路径到本节点的距离来标注，标注分为临时性 标注和永久性标注； 初始时，所有节点都为临时性标注，标注为无穷大； 将源节点标注为0 ，且为永久性标注，并令其为工作节点； 检查与工作节点相邻的临时性节点，若该节点到工作节点的距离与工作节点的 标注的和小于该节点的标注，则用新计算得到的和来重新标注该节点； 在整个图中查找具有最小值的临时性标注节点，将其变为永久性节点，并成为 下一轮检查的工作节点。 重复、，直到节点成为工作节点。 2 1 2 距离矢量路由算法 距离矢量路由算法又名b e l l m a n - f o r d 路由算法。该算法要求每个节点内部维 持一张路由表，表中给出到每个目的节点已知的最短距离和下一跳节点。子网中 每个节点在表中都占有一个入口，路由表包括两部分内容：到某目的节点的最佳 下一跳和估计到该墓地节点的“距离”。距离尺度可以为跳数、时延、分组队列长度 或者类似的值。算法假设每个节点知道自己到所有相邻节点的距离，这是完全可 7 重庆大学硕士学位论文2q o s 路由和o v e r l a y 网络的q o s 路由 以做到的：如果是以跳数来计量距离，则相邻节点间的距离等于l ；如果是以时延 来计量距离，则每个节点可定期向相邻节点发送“回声”分组，每个节点收到分组后 在其上记录接受的时间，并以最快的速度发送出去，通过检查分组上的时间戳就 可以推算出延迟时间；如果是以分组队列长度来计量距离，则只需统计一下去往 该节点的分组数即可。 距离矢量路由算法的工作流程如下： 1 路由器启动时，对路由表进行初始化，包含所有与本路由器直接相连的网络 路径，这些网络路径不经过中间节点，初始路由表中各项的路径长度为0 。 2 各路由器周期性地向外广播期路由表报文，与某路由器r i 直接相连的路由 器r i 收到r i 的报文后，逐项检查报文内容，遇到下述表目之一，须对本地路 由表的相应内容进行修改： 路由器r i 列出的表目在路由表r i 中没有，则r i 路由表中增加相应表目， 其信宿是r j 表目中的信宿，距离为玛表目中的距离加1 ，下一跳为r j 。 r i 到某信宿的距离加l 小于r 到该信宿的距离，说明r i 到该信宿若经过 r i ，其路径会更短，则r i 修改本表目，其信宿域保持不变，距离为r i 中相 同信宿表目的距离值加l 。 r i 到某信宿的路径经过r i ，而r j 的路由表中不再包含到该信宿的表目，则 删除r i 路由表中相应的表目。 r i 到某信宿的路径经过r j ，而r j 的路由表中到该信宿的距离发生了变化， 则r i 对中相应的表目距离项进行修改，以r 中距离加1 取代。 距离矢量路由的主要问题是，网络拓扑改变时算法收敛慢以及无穷计算问题。 加强距离矢量收敛的一个常用方法是水平分裂算法，但是该算法不能解决所有的 无穷计算问题。 2 1 3 链路状态路由算法 链路状态路由算法中每条链路都有一系列状态信息。如图2 1 所示，链路状态 是一个包含剩余带宽、时延和代价的三元组。节点也有状态信息，节点的状态信 息可以单独的测量出来或者映射到相邻链路的状态中。 8 重庆大学硕士学位论文 2q o s 路由和o v e r l a y 网络的q o s 路由 ( 1 ，2 ，2 ) 图2 1 网络链路状态 f i g 2 1s t a t eo f l i n ki nn e t w o r k 2 ) 链路状态路由算法的工作流程如下： 每个路由器发现它的邻居节点，并知道其网络地址； 测量到各邻居节点的延迟或者开销； 组装一个分组以后告诉路由器刚知道的所有信息； 将该分组发给所有其它路由器； 计算到其他路由器的最短路径。 现在各式各样的链路状态路由选择算法已经得到了广泛的应用，如开放最短 路径优先( o p e l ls h o r t e s tp a t hf i r s t ，o s p f ) 协议就是使用链路状态算法的一个例子。 2 2 服务质量 路由算法使用不同的q o s 尺度来决定最佳路径，一个完善的路由算法能够综 合多个q o s 尺度进行路由选择。常用的q o s 尺度包括路径长度、带宽、可靠度、 时延、时延抖动和通信费用等。 路径长度是很常用的路由尺度。很多路由协议定义路径长度为跳数( h o p s ) ， 即包从源节点到达目的节点途中经过的网络设备的数目。 可靠度在路由算法中是指网络链路可靠度( 通常以误码率表征) ，若某链路出 故障的概率比其他链路大，则该链路的可靠度低。 9 重庆大学硕士学位论文2 q o s 路由和o v e r l a y 网络的q o s 路由 时延是指包从源节点到目的节点所需要的时间。时延通常包括链路传输时延， 交换节点的队列等待时延，交换节点的处理时延等，时延是一种常用和有效的q o s 尺度。 时延抖动是指同一条链路或路径在不同次传输中时延的变化幅度，v o m 等应 用对时延抖动很敏感。 带宽是指链路的通信容量。尽管带宽表征链路可达到的最大传输能力，但并 不意味着通过高带宽链路的路由一定能比通过较慢链路的路由好。例如业务都去 使用高带宽的链路，则这些链路相对忙碌，则实际传送包所需要的时间可能比低 带宽的链路要长。 通信费用是另一个重要的q o s 尺度。一些公司可能更关心运行开支更甚于关 心性能。有时即使使线路时延更长，他们也会通过自己的线路传送包，而不使用 需要付费的公共线路。 根据路径总q o s 值运算规则的不同，q o s 尺度参数可以分为三类，分别为加 性参数、乘性参数和凹性参别1 9 1 。假设路径p 包含n 条链路 $ - * o9 乙) ，h ) 是链 路的参数值，州p ) 是路径尸的总参数值，各种参数特性定义如下： 加性参数：似即= 以) 乘性参数：以力= 1 7 以) 凹性参数：以p ) = 赢n “) ，江1 ，2 ，玎 上述q o s 参数中，传输时延、跳数、通信费用属于加性参数，链路可靠度、 时延抖动属于乘性参数，带宽属于凹性度量参数。乘性参数可以通过对数变换的 方法转化为加性参数。 2 3o o s 路由 2 3 1q o s 路由概述 传统的i n t e r n e t 网络主要优化的对象是接入率与网络吞吐量，它主要为数据业 务提供尽力而为的服务，并不能提高很高的q o s 保证。随着i n t e r n e t 的发展，出现 了越来越多的数字音视多媒体应用等对服务质量有更多样化、更严格要求的业务。 为了为这些业务提供所需的服务质量保证网络必须进行合理的资源预留并实现对 网络的有效控制。q o s 路由技术就是在这种背景下被提出的。 q o s 路由是在一个或者多个q o s 性能指标约束下的路由，q o s 路由约束通常 可以分为两大类：链路约束和路径约束。链路约束是指一条路径上链路的使用限制， 例如可用的链路容量( 通常为带宽) 必须大于或者等于路由请求的要求容量。路径约 束是指在选定路径上的性能度量标准值的加性或者乘性组合的界限，例如路径提 1 0