（通信与信息系统专业论文）覆盖网络的qos路由研究.pdf

浙江大学硕士学位论文 犷 6 8 9 2 ; 7 摘要 随 着i n t e rn e t 的 迅速普及和发展， 在i n t e rn e t 上涌现了 许多对网 络的 服务质量( 包 括带宽、时延、 可靠性等) 有较高的要求的应用，如v o l e 、网络视频会议、网络音频 / 视频广播、网络多媒体交互协作平台等。 现在商用i n t e m e t 的网络层大都只提供 “ 尽 力而为”的数据传输服务，其容错性较差，不能很好满足这些应用的服务质量要求。 而且随着手机、 p d a等处理能力不高的设备越来越多地连入i n t e rn e t ，人们希望在得 到满意服务的同时， 服务进程中大部分的计算处理 l 作都能在网上完成， 这在现有的 i n t e rn e t卜 是不能实现的。 覆盖网 络正是在现有网 络越来越不能满足不断涌现的各种 应用的情况下诞生的，它是重叠在现有网络上的虚拟网络，由分布在 i n t e r n e t 各自 治 区域的一些覆盖节点和它们之间的逻辑链路组成。 它实现方便， 不用大规模改变现有 网络架构就能提供更高的服务质量。 q o s 路由问 题是覆盖网 络研究的关键问 题之一， 这也 正是本文的 研究重点。 本文e r 较了 q o s 路由 三种策略的 优缺点， 介绍了 现有的一些q o s 路由 算法。 然后引入覆盖网 ip 上的 q o s 路由问 题， 分析了 覆盖网 络_ f . 的 q o s 路由 与 般q o s 路由的区别。 在对己 有1 覆盖网络q o s 路由 算法的 研究和分析的基础上， 提出了 一个通用覆盖网 络架构g o n 和 基于该网 络架构的 q o s 路由 解决方案。 本文采用可扩展性最好的 分层路由 策略， 提出了 一种新的 覆盖 链路带宽 和覆盖 服务 节点 处理能 力 受限 的 q o s 路由 算法一 r b l c p 算法， 该算法能在找到一条满足q o s 要求的 路由 路径的同时 均衡网 络的资源尤其是相对稀缺 的资源。本文最后通过仿真验证了r b l c p 的性能，仿真结果显示与 现有的同类算法相 比 ， r b l c p 算法具 有更好的 q o s 满意 率， 在 对网 络资 源尤其 是稀缺资 源的 均衡上也有 良 好的表现。 关键词:覆盖网 络， q o s 路由，分层路由，g o n r b l c p 浙江大学硕士学位论文 abs tract wi t h t h e r a p i d d e v e l o p m e n t o f i n t e r n e t , a l o t o f n e w a p p l i c a t i o n s w h i c h h a v e s t r i c t d e m a n d s o n q u a l it y o f s e r v i c e h a v e o c c u r r e d i n i n t e rn e t , s u c h a s v o i p , n e t w o r k v i d e o c o n f e r e n c e s , n e t w o r k a u d i o / v i d e o b r o a d c as t e . t . c . wh i l e t h e n e t w o r k l a y e r o f i n t e r n e t o n l y p r o v i d e s b e s t - e ff o rt t r a n s p o r t . i t h a s p o o r e r r o r s u ff e r a n c e , c a n t p r o v i d e s a t i s i f y i n g q o s f o r th e s e a p p l i c a t i o n s . mo r e o v e r , w i t h m o r e a n d m o r e d e v i c e w i t h p o o r c o m p u t a t i o g c a p a c i t y ( s u c h a s mo b i l e p h o n e , p d a ) a r e c o n n e c t e d i n t o i n t e rn e t , p e o p l e h o p e t h a t m o s t c o m p u t a t i o n d o n e i n t h e n e t w o r k , t h e c u r r e n t n e t w o r k s c a n t p r o v i d e t h e s e r v i c e . o v e r l a y n e t w o r k i s i n t r o d u c e d t o s o l v e t h e a b o v e p r o b l e m s . i t i s a v i r t u a l n e t w o r k o v e r l a i d u p o n t h e e x i s t i n g n e t w o r k s , c o n s t r u c t e d w i t h a l o t o f o v e r l a y n o d e s d i s t r i b u t e d i n d i ff e r e n t a s e s i n i n t e rn e t a n d t h e v i r t u a l l i n k s b e t w e e n e a c h o f t h e m . i t c a n e a s i l y b e e m p l o y e d a n d p r o v i d e m u c h b e tt e r q u a l it y o f s e r v i c e w i t h l i t t l e c h a n g e t o t h e c u r r e n t n e t w o r k a r c h i t e c t u r e . q o s r o u t i n g o n w h i c h t h i s t h e s i s f o c u s i s o n e o f t h e k e y i t e m s o f o v e r l a y n e t w o r k s r e s e a r c h . i n t h i s t h e s i s , t h e t h r e e s t r a g e g i e s o f q o s r o u t i n g i s c o m p a r e d w i t h e a c h o t h e r , t h e a d v a n t a g e s a n d d i s a d v a n t a g e s o f e a c h s t r a g e g y a r e d i s c u s s e d . s o m e t y p i c a l q o s r o u t i n g a l g o r i t h m s w i l l b e i n t r o d u c e d b r i e fl y . t h e n t h e d i ff e r e n c e s b e t w e e n i p q o s r o u t i n g a n d q o s r o u t i n g i n o v e r l a y n e t w o r k a r e o u t l i n e d . a ft e r a n i n - d e p t h s t u d y o f t h e e x s i s t i n g o v e r l a y q o s r o u t i n g s o l u t i o n s , w e p r o p o s e a g e n e r i c o v e r l a y n e tw o r k a r c h i t e c t u r e ( g o n ) , b a s e d o n w h i c h a n e w s o l u t i o n f o r q o s r o u t i n g i s i n t r o d u c e d , i n c l u d i n g t o p o l o g y c o n s t r u c t i o n , q o s r o u t i n g a l g o r i t h m a n d m a i n t e n a n c e o f r o u t i n g . h i e r a r c h i c a l r o u t i n g s t r a t e g y i s a d o p tt e d i n t h i s t h e s i s . a n e w q o s r o u t i n g a l g o r i t h m , n a m e d r e s o u r c e - b a l a n c e d l e a s t c o s t p a t h ( r b l c p ) a l g o r i t h m , i s p r o p o s e d f o r g o n . wi t h t h e n e w a l g o r i t h m w e c a n f i n d a fl e a s i b l e r o u t i n g p a t h a s w e l l a s b a l a n c i n g t h e r e s o u r c e in t h e o v e r l a y n e t w o r k . f i n a l l y , t h e re s u l t s o f s i m u l a t i o n s h o w t h a t r b l c p a c h i v e s b e tt e r p e r f o r m a n c e i n t h e f e a t u r e o f q o s s u c c e s s r a t i o t h a n t h e e x s i s t i n g c o r r e s p o n s i v e a l g o r i t h m s . i t c a n a l s o b a l a n c e r e s o u r c e w e l l , e s p e c i a l l y f o r t h e r e s o u r c e t h a t i s s h o r t i n t h e n e t w o r k . k e y wo r d s : o v e r l a y n e t w o r k s , q o s r o u t i n g , h i e r a r c h i c a l r o u t i n g , g o n rblcp 1 1 浙江大学硕士学位论文 第一章 绪论 1 . 1覆盖网络的提出 日 前的i n t e rn e t 是山 许多自 治系统( a u t o n o m o u s s y s t e m s , a s ) 组成的， 每个a s 一 般由 一 个独立的实体来控制，大部分是商业化组织，如i n t e r n e t 服务提供商 ( i n t e rn e t s e r v i c e p r o v id e r , i s p ) . a s 之间的连接通常可以 有两种方法: t r a n s i t 和p e e r i n g . t r a n s i t 连接关系是在 i n t e rn e t 上公开发布的，如果自 治系统 b和 c是 t r a n s i t 的连接 关系， 则任何以c为目 的地的 包可以 通过b路由，反之亦然。 p e e r i n g 连接关系是秘 密的， 仅对其内 部用户可见， 对其它a s 是不可见的， 如果自 治系统b 和c 是p e e r i n g 的关系， 则b和c的的内部用户可以使用它们之间的连接， 而其它a s内的用户则不 能利用b和c之间的这种连接关系，即不能通过b把包直接路由到c或通过c把包 路由直接到b . t r a n s i t 连接信息由 边际网 关协议 ( b o r d e r g a t e w a y p r o t o c o l , b g p i ) 发布， 它允 许a s们相互交换路由信息，凭借 b g p ，当 一 个 a s想发包给另一个与它没有直接 p e e r i n g 或者t r a n s i t 连接关系的a s 时， 它能找到下一跳。 但是b g p 并不保证最佳路 由。 如图1 - 1 所示，图中实线代表t r a n s i t 连接，虚线 代表p e e r i n g 连接，当 一个包需 要从a路由 到b时， 如果采用b g p公布的路由信息， 包需要跨越c , d , e三个a s . 显然这并不是最佳的传输路径， 如果我们在自 治网络c内放置 一 个具有路由功能的中 间节 点，就可以 利用b和c之间的p e e r i n g 连接关系， 包就可以 只跨越c一个a s o 从t r a n s i t 和p e e r i n g 连接对路由的 影响可以 看出， 利用应用层上的中间 节点 可以 提供 一条更加有效的传输路径。 图 1 - 1 t r a n s it 和p e e r i n g 连接对路由的影ii向 浙江大学硕士学位论文 同时，为了提高i n t e rne t 的可扩展性，b g p 协议在不同自治系统之间只是传递必要 的路由信息，它采用 “ 跳数”作为性能度量来挑选最优路由，而这常常并不是实际 - 的最优路由;另外b g p 路由协议并不探测路径性能，所以它不能绕过拥塞的连接。因 此其简单性和可扩展性的提升是以网络容错性的降低为代价的。随着新应用的不断涌 现，对服务质量的要求越来越高，现有的i n t e rn e t 己 经越来越不能满足人们的服务要求 了。 覆 盖网 络( o v e r l a y n e t w o r k ) 正 是 在这 种 情 况 下诞 生的 ， 它 不 需 要 大 规 模 改 变现 有 网络架构就能提供更为可靠、容错性更好的服务。有了覆盖网络，即使网络层出现错 误，应用系统也可以凭借覆盖网络快速找到替代路由，并且可以根据应用服务的不同 服务质量要求寻找相应的最优路径。同时，覆盖网络只是重叠在现有网络之上的虚拟 网络，并不需要改变现有网络架构，实现起来也是很方便的。覆盖网络是由一系列分 布于i n t e r n e t 各自 治系统内部的覆盖服务节点以及连接它们的逻辑链路所组成的虚拟网 络， 它能有效地利用i n t e rn e t 给终端用户提供更为可靠的服务。 覆盖节点通常具有路由、 数据处理和数据保存等功能，而逻辑链路 ( 即覆盖链路)通常对应底层的一条或多条 物理路径。图1 - 2 所示就是 一个覆盖网络的例子。 图1 - 2覆盖网络示意图 浙江大学硕十学位论文 覆盖网络大致可以分为两大类: 基于终端主机的覆盖网络和基于固定节点的覆盖 网络。 在基于终端主机的覆盖网络中，终端主机只是逻辑上相连 ( 在网络层) ，没有得 到 i s p的任何支持。 它要求终端主机同时和其它多个终端相连。 著名的p 2 p 文件共享 系 统g n u t e ll a 3 1 和 基于终端主 机的i n t e r n e t 组播 4 1 都是 属于这 类网 络。 有两个问 题限 制 了 这类网 络的 应用: 终 端节点 的 低接入带宽 和较大的“ 最后 一英里” 传输延 迟5 1 。 大 多数终端主机使用c a b le mo d e m, d s l或者拨号等低带宽的接入力 一 式接入i n t e rne t , 仅有少部分主机有1 0 / 1 0 0 mb / s 的接入带宽 ( 不过随着宽带的普及，这情况正在得 到改善) 。此外，由于终端节点随时可能被打开或者关闭，所以这类覆盖网络是动态 变化的，不能提供非常可靠的服务。 基于固定节点的覆盖网络使用一系列分布于 i n t e r n e t 上的固定节点来实现覆盖服 务， 它通常由 第三方服务提供商来维护， 第三方服务提供商通过和i s p 签订服务等级 协议 ( s e r v i c e l e v e l a g r e e m e n t , s l a ) 使 覆盖 服务节点 之间 的 覆盖链路的q o s 得 到 一定的保证， 内容分送网络就属于这类覆盖网络。 这类覆盖网络的优点是能够提供可 靠的服务， 缺点是由于覆盖服务节点在搭建覆盖网的时候就己经固定下来了， 增加或 减少服务节点比较麻烦，所以网络灵活性比较差。 1 . 2覆盖网络的应用 基于覆盖网技术的应用有很多，我们简单介绍几种典型的应用:内容分送网络、 应用层组播、p 2 p 文件共享等。 1 .2 . 1 内容分送网络 一般情况下网站响应速度的快慢和访问者与网站服务器之间的“ 距离” 密切相关。 为了改善网站响应速度， 内 容分发网络( c o n t e n t d e l i v e r y n e t w o r k , c d n ) 提出了“ 让 内 容离用户更近” 的思路。 c d n的技术原理是在遍布世界的主要i n t e rn e t 接入点部署 内容服务器节点， 在这些节点的基础上组成一个覆盖网络， 并利用一种特殊的路由机 制将网站内容发布到离用户最近的网络 “ 边缘” ，使用户能以最快的速度、从最接近 的地方获取所需的信息，例如，当w e b 用户点击一个支持内容分送服务的u r l时， 内容分送网络实时的根据网络流量和各节点的连接、 负载状况以及到用户的距离和相 应时间等信息， 将用户请求重定向到离用户最近的内容服务器， 大大提高了网络的访 问速度。由于这种技术极大的缓解了拥塞情况， 所以网站有能力提供更多类似视频节 目 、歌曲点播等数据流量大的内 容服务。目前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 个网络16 1国内的c d n应用也己经起步， 如c h i n a c a c h e 公司已经 在全国部署了4 0 个c d n服务节点7 1 1 . 2 . 2 应用层组播 在 i p组播中，与组播相关的功能都放在网络层即路由器上实现，路由器负责记 录组播组的存在和组成员的变化，并在组成员间构造一颗组播发送树。 数据源只需要 向组内发送一份组播数据，由路由器在恰当的分支复制数据， 就可让所有组员都收到 数据。 任何一份数据拷贝只会在每条组播链路上出现一次， 这样就有效的降低了主机 服务负载、网络通信负载，因此它被认为是解决组内通信的最理想方式。然而，经过 了 十多 年的 研 究， i p 组 播技 术至 今 仍 只 停留 在实 验 平台( 如m b o n e 8 , i n t e rn e t 2 l9 1等) 上的应用阶段， 一直没有能够进入商业领域， 概括来说主要由于一 卜 几个原因造成的: 第一， i p 组播需要路由 器的支持， 每个组播路由 器需要为每个组地址甚至是组播业务 源保存组状态。由于组地址是动态分配的，不能够像单播地址那样得到有效汇聚，需 要在路由器内保存大量组状态， 这增加了路由器的开销和实现的复杂性。 第二， i p 组 播目 前缺乏有效的可靠传输和拥塞控制机制， 可能对正常的单播业务造成伤害， 组播 的拥塞控制机制非常难解决，在没有可靠的拥塞控制机制前，i s p不会在他们的网络 上大规模配置组播业务。第三，目 前还缺乏对组播流的合理收费模型。 覆盖网技术的提出使在应用层实现组播成为可能。 所谓应用层组播是指将原本在 网络层即路由器上实现的组播相关功能移到应用层即终端主机上来实现。 在应用层组 播中， 所有的终端节点组成 一 个覆盖网络， 每个终端主机都是一个覆盖服务节点。 为 了更好的利用网络资源，应用层组播也需要在组成员间建立一颗组播分布树，与 i p 组播不同的是， 应用层组播的分叉点必须是终端系统， 也就是说组播数据的复制是在 终端系统中实现的，所以有些链路可能由多份数据拷贝， 效率不如 i p组播。 但是应 用层组播有如下的优点:( 1 )它不需要路由器的支持，i p组播之所以不能在 i n t e rn e t 上使用就是因为大部分路由器不支持， 应用层组播绕开了这一点。( 2 )由于仟何两个 组员之间在发送或接收数据时都是单播方式的， 所以可以使用单播流量控制和差错控 制协议，从而简化了 i p组播繁杂的拥塞控制机制。因此应用层组播更有可能成为 i n t e rn e t 上 组播的实现方式。 1 . 2 . 3 p 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 rn e t 上迅速传播，用户数量急剧增长。 在这类系统中， 数据被保存在终端用户主 机中，而不象传统的集中控制模式 如c l ie n t / s e r v e r . b r o w s e r / s e r v e r ) 那样把数据存 放在控制中心的服务器上。所有的终端主机都是对等的，称为对等结点 ( p e e r ) ，这 些对等节点连接在一起就组成了一个覆盖网络。 通过覆盖网络组织起来的 p 2 p文件共享与传统的集中式模式文件共享相比有如 f 的优势: 1 、分散化:网络中的资源和服务分散在所有节点上， 信息的传输和服务的实现都直 接在节点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。分 散化是p 2 p的基本特点，由此带来了其在可扩展性、健壮性等方面的优势。 2 . 3 、 可扩展性:传统的 c / s架构中，系统能够容纳的用户数量和提供服务的能力主要 受服务器的资源限制。而在p 2 p网络中，随着用户的加入，不仅服务的需求增加 了，系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需 要。 健壮性:传统的集中式服务模式中，集中式服务器成为整个系统的要害所在，一 旦发生异常就会影响到所有用户的使用。而p 2 p服务是分散在各个节点之间进行 的，部分节点或网络遭到破坏对其它部分的影响很小。而且p 2 p 模型一般在部分 节点失效时能够自 动调整整体拓扑，保持其它节点的连通性。 高性能:采用 p 2 p架构可以有效地利用互联网中散布的大量普通节点，将计算任 务或存储资料分布到所有节点上。利用其中闲置的计算能力或存储空间，达到高 性能计算和海量存储的目的。 1 . 3覆盖网络的研究现状 国内外学术界已经对覆盖网络做了大量的 研究， 主要集中在通用平台、 网络拓扑、 安全、底层网络支持、路由等几个方面。 1 .3 . 1覆盖网络通用平台 研究 日 前， 大部分对覆盖网的研究都是针对特定应用的，比 如 c h o r d , b r o c a d e l t o t a p e s t r y l i等都是为 基于良 好定义 架构的( 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 ) 应用而设 计 的， 它们主要目 标都是在一个大的分布式系统中 对内 容进行迅速的定位， 而文【 5 1 3 则是针对基于覆盖网的应用层组播的研究。 这些研究者都提出了基于某种应用的覆盖 浙江大学硕十学位论文 网架构， 然而随着覆盖网络应用的增多， 为各种不同的应用建立不同的重叠网络就显 得多余了。 于是有人提出了通用覆盖服务网的概念， 它能对己有的和将来的覆盖应用 提 供 支持。 当 前 对 此的 研究 主 要有 覆盖 服 务网 络( o v e r la y s e r v ic e n e t w o r k , o s n ) ( , 覆盖 应用服务网 络( o v e r l a y u t i l i t y s e r v i c e , o p u s ) 5 j , 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 , o v e r q o s ) i 以 及服务覆盖网 络 ( s e r v i c e o v e r l a y n e t w o r k , s o n) 0 8 ,9 等。 o s n可以为各种覆盖服务提供资源分配和协商、路由、拓扑发现等服务支持。 o s n特别适用于对q o s 敏感的覆盖应用服务， 文献 1 4 3 为o s n设计了 两种路由 选择 算法， 可以 为覆盖服务应用提供满意的q o s ， 并均衡覆盖链路的通信流量及节点计算 负荷。 o p u s 是 一个提供q o s 保 证的 大范围 覆盖 应用服务网 络平台， 它是能同 时 为多 个 分布式 应用 提供必 要的 服务。 在o p u s 模型中， 大范围的 资 源映 射是由 应用的 性能 要 求决定的。 o p u s 能同时满足应用的性能和可靠性要求， 并且具有很好的 扩展性，能 够扩展到数千个参与节点。 o v e r q o s 是一个利用覆盖网为i n t e r n e t 提供服务质量保证的架构。 o v e r q o s 提出 了丢包控制虚拟链路 ( c o n t r o l l e d l o s s v i r t u a l l i n k , c l v l ) 的概念， 通过在数据流中加 入冗余数据包来实现丢包控制。 使用c l v l , o v e r q o s 能提供比 传统i n t e r n e t 的“ 尽 力而为”更好的 服务。 o v e r q o s 将不同的q o s 要求的 服务数据流分 类， 将相同q o s 要求的服务数据流汇聚成一 “ 束” ，资源是以“ 束”为基本单位进行分配调度的。 第 二方服务提供商可以 利用o v e r q o s 技术来给其客户提供不同q o s 保证的 服务。 s o n利用覆盖网技术来在i n t e rne t 上提供附加值服务，与o s n类似，s o n提供 商可以从不同的i s p 那里购买具有一定q o s 保证的 带宽 ( 这个q o s 保证是相对较低 的) ， 在此基础上建立一个覆盖网络来给用户提供更高q o s 保证的服务。 s o n主要关 注的是在满足q o s 和流量要求的基础上如何尽量减少带宽花费。 1 . 3 .2覆盖网络的拓扑研究 设计一个覆盖网，第一步就是选择一个连接所有覆盖服务节点的网络拓扑结构 不同的拓扑模型对覆盖网的性能有很大的影响，目 前己 经有不少覆盖网拓扑的研究 文献 g a 把数学上的 维 数和曲 率的 概念运用到了 覆盖网的 拓扑图 的 构建 上。文 献 2 1 研究了带宽保证下的 覆盖网络拓扑设计问 题， 文中提出了一个启发式算法来设计 运行费用最小化的覆盖网 络拓扑。文献 2 2 提出了一种利用交叉生成树 ( i n t e r l e a v e d 浙江大学硕士学位论文 s p a n n i n g t r e e ) 来设计覆盖网 络拓扑的 方法， 用此方法设计的拓扑具有如下特性:高 性能 如低时延，高带宽，低丢包率等) ，多路径 ( 即两个节点间有多条路径，保证 在一条路径失效时 可以换另一条路径) ，自 组织( 即拓扑能 够应付节点随时加入， 退出 和其它不 确定因素 ) 。 文献 2 3 是针对p 2 p 系统拓扑的 研究， 在p 2 p 系统中i i 点加入 退 出频繁， 经常导致实际网络拓扑和每个节点保存的拓扑不匹配， 文章提出了一种自 适 应覆盖拓扑最优化技术，它能有效减少拓扑小匹配的问题并带来更高的查询效率。 文献 2 4 把覆盖网的拓扑模型分为两类，一类是不知道或者不利用物理层网 络拓 扑的， 如全网 格( f u l l m e s h ) 、 网 格树( m e s h t r e e ) , 最小生成树( m i n i m u m s p a n n in g f 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 e m i n i m u m s p a n n i n g t r e e ) 等。 然后对这些 拓扑结构 l 利用不同的路由算法进行了仿真实验， 通过对错误修复率、 路由耗费等性 能指标的对比后得出了以下几个结论: ( 1 )网络拓扑对覆盖网的路由服务性能有重大的影响，在一种网络拓扑下表现 最好的路由算法在另外一种拓扑结构下可能最差: ( 2 )网格树模型在覆盖服务网中并不是一个好的选择，因为仿真实验中所有的 路由算法在这个拓扑模型下的性能表现都很差; ( 3 ) 下层物理网络拓扑信息对构建一 个高效率的覆盖网拓扑结构是非常有用的， 因为知道物理层网络拓扑的覆盖网拓扑模型在各种路由算法下性能表现普遍比其它 拓扑模型好。 1 .3 . 3覆盖网络的安全研究 和传统的 i n t e r n e t 一样，覆盖网络也容易受到各种恶意攻击，所以安全问题也是覆 盖网络所需要关注的问题之一。 文献 2 5 认为拒绝服务 ( d e n i a l o f s e r v i c e , d o s ) 攻击是覆盖网络安全的 主要威胁。 以前防止d o s 攻击的方法是被动的， 即等有攻击产生了网络才会启动保护机制， 这难以 防止使用复杂伪装技术的 攻击。 文中提出了 一个安全 覆盖服务( s e c u r e o v e r l a y s e r v i c e s , s o s )网络架构可以主动预防d o s 攻击。s o s 架构采用了安全覆盖隧道、相容哈希和过 滤等技术。 它在 “ 边缘”网络使用高强度的过滤保护， 将d o s 攻击推向核心网络， 核心 网络的高速路由 器可以处理大量攻击流量使得攻击难以成功。另外它还引入了匿名机 制和随 机机制， 使 攻击者难以 针对某个特定的目 标进行 攻击。 文 献 2 6 改 进了 s o s 架 构， 提出了更为灵活的g s o s 架构，该架构可以更好地抵御d o s 攻击。 文献【 2 7 1 研究了 应用层组播安全密钥管理的问题。 由于在应用层组播中， 每次出现 浙江人学硕士学位论文 成员变动 ( 如加入或退出)，所有成员都需要更新其会话密钥，如果组播组的规模很 大，成员变动频繁，则更新密钥将是一笔很大的开销。 文章提出了 一 个安全覆盖树 ( s e c u r e o v e r l a y t r e e ) 的 概念， 将组播组分为很多簇， 侮个簇内 使用相同的密钥， 不同 簇使用不同的密钥，这样某簇的成员变化时，只需该簇的成员更新密钥，其它簇的成 员不需要更新密钥，大大减少了密钥更新的开销。 1 . 3 . 4覆盖网络的底层网络支持研究 虽然覆盖网络尽量避免对底层网络做太大的改动。但是如果在底层网络中加入 些支持功能，那么由此建立起来的重叠网络将会更为高效。 文献 6 2 介绍了 一种叫 包p a c k e t r e fl e c t i o n 的网 络层支持覆盖网的 技术， 使用这种技 术可以使内容的发布更为有效，降低网络带宽的消耗，在其支持下，用户可以给邻近 路由器发送请求，把数据的复制转发交给邻近的路由器完成，使得内容发布占用的带 宽最小化。这种技术并不需要全部路由器支持，只需在适当路由器中加入此技术就可 以达到目的，所以并没违反避免对底层网络做太大改动的初衷。 在覆盖网络中，节点通过连接它们的覆盖链路进行单播通信。在应用层组播中， 数据复制转发在终端主机实现，这样使得相同的数据包在一些链路上需要传输好几 次。如图1 - 3 ( a ) 所示的应用层组播树，在数据从源s ， 通过r ) , 凡、凡发送到目 的 地e l ，再由e ， 转发给e 2 , e : 的过程中，链路r 3 凡和r 4 e i 被重复使用了三次，而链 路r 3 r 5 被重复使用了两次。而如果r 4 支持p a c k e t r e fl e c t i o n 功能，则终端主机e ， 可 以 给凡发送r e fl e c t i o n 请求， 要求当有数据从s , 发送给e 1 时， 路由 器r 4 要把数据同 时转发给e 2 , e 3 ，这样数据在r 4 e , 上就只需传递一次， 得到了优化，如图1 - 3 ( b ) 所示。 凡除了 对数据r e fl e c t i o n 以 外， 继续正常数据的路由， 所以e i 能收到以它为目 的地址所有数据。如果路由 器之间也能实现p a c k e t r e fl e c t i o n 请求，那么内容的发送 将得到最大的优化。 在图1 - 3 ( c ) 中， 凡利用p a c k e t r e fl e c t i o n 请求r 3 实现数据转发， 这样数据在链路r 3 r 4 也传递一次就够了， 减轻了链路r 3 r 4 负担。 当然了， 当r 3 已经 完成数据转发后r 4 就不再需要进行数据转发了。 这可以通过标志位来，如果从r 3 发 送来的数据己 经有转发标准，则r 4 将不再转发。 采用p a c k e t r e fl e c t i o n 技术所带来的好处是显而易见的。即使只有 一个路由器支 持此种技术，也能马上就能提高带宽利用率， 有效提升响应时间。 所以说，并不需要 升级所有路由器， 而只需在特定路由器上采用此技术就能大大提升系统整体性能。 此 外， 它还减轻了路由器的负担。 在应用层组播系统中， 某些路由器需要接收相同的数 据包若干次， 再查找若干次路由表， 再将其发送出去。 然而， 如果有p a c k e t r e fl e c t i o n 浙江大学硕士学位论文 的支持，路由器只需查找一次，并将多份拷贝发送出去即可。 r- r石 =e 只 -r e , s 称 r r i t 一 、 e 5发厂 3 a 5.卜朽入叹 n ! 七一七 235 / kz , 图1 - 3 p a c k e t r e fl e c t i o n 技术的 应用 1 . 3 . 5覆盖网络的路由研究 路由问题是覆盖网络研究的关键问题之一。 日前国内外对覆盖网的路由问 题己经 进行了大量的研究，其中大部分研究都是针对特定应用的。 a k a r o u t i n 酬是内 容分送网 络系 统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 rn e t 的 全局“ 距离” ， 并 为每 个a k a m a i 数 据中 心 和内容提供商节点之间建议三条较佳路由路径， 而g u i d e 则比较这三条路径， 从中选 择一条最佳的 路径。 文献 2 9 提出了 一种基于最大收益的d n s 内 容路由 算法， 该算法 采用名字解析服务器与网关处分别获取内容服务器负载信息和网络路由信息生成网 络收益， 根据最大网 络收益算法选取最佳的内容服务器。文献 1 3 3 0 侧是针对覆盖 组播网 络的 路由 研究， 提出 了 均 衡度 分配 ( b a l a n c e d d e g r e e a l l o c a t i o n , b d a ) 的 路 由 方案能 够有效 均衡网 络负 载并 减小 端到 端时 延。 文 献 3 1 也 是 对覆盖网 络组 播的 路 由 研究，文中提出了一种启发式路由算法来解决覆盖网络组播中的“ 最小直径、 剩余 均 衡、 度数 受 ir 的 生 成 树( m in i m u m d i a m e t e r , r e s id u a l- b a la n c e d , d e g r e e - lim it e d s p a n n in g t r e e , m d r b d l ) 问 题。 文 献 l 0 3 2 3 3 是 对p 2 p 文 件共享系 统的 路由 研究， 文献 1 0 利用相容哈希表来完成文件的查找和路由 ，文献 3 2 侧进一步将数据分类以 减少路由 查询的消息量， 文献 3 3 研究了 如何利用路由 表中的 冗余信息来获得更高的路由 效率。 文献 3 4 研究了 如何在覆盖网 络内 部节点 和外部节点 之间 实现路由 ， 提出了n a t r o n 的网络架构并在该架构上设计了一种启发式算法来选择路由路径。 覆盖网 络的 q o s路由 是覆盖网 络路由的 一个重要分支， 也是本文的 研究重点， 我们将在第二章详细介绍。 浙江大学硕士学位论文 1 .4本文的主要工作及篇章结构 本文的研究重点是覆盖网 络的q o s 路由问 题。 本文在对现有的q o s 路由 、覆盖 网络的 q o s路由策略和算法进行了 研究和分析的基础土，提出一个通用覆盖网 络 ( g e n e r i c o v e r l a y n e t w o r k , g o n ) 架构， 并研究了 在此架构上的q o s 路由 解决方案， 提出了 一种新的q o s 路由 算法一 r b l c p 算法， 该算法能 在找到一条满足q o s 要求的 路由路径的同时均衡网络的资源尤其是相对稀缺的资源。本文最后通过仿真验证了 r b l c p的性能。 本文篇章结构如下: 第一章介绍了覆盖网络的相关背景知识以及研究现状。 第二章比 较分析了 三种q o s 路由 策略的 优缺点， 介绍了 现有的q o s 路由 算法， 指出 覆盖网 络的q o s 路由 和一般q o s 路由 的区 别， 然后着重介绍了q u e s t , s b q s r , o s p t / l p t , q r o n , t b p 等几种典型的 覆盖网 络q o s 路由 方案。 第三章提出 通用覆盖网 络架构， 研究了 在该架构上的q o s路由 解决方案，详细 阐述了网络拓扑建立，r b l c p 路由算法以及路由维护。 第四章将r b l c p 路由 算法与现有的一些算法进行了仿真比 较，并分析了仿真结 果。 第五章对全文进行了总结，并对覆盖网络 q o s 路由的未来发展提出展望。 浙江大学硕十学位论文 第二章 q o s 路由和覆盖网络的q o s 路由 2 . 1基本路由算法 在i n t e rn e t 等分组交换网中，由于没有建立连接电 路，传送的每个分组都需要携带 传送目的地址以及到达终点的各中间节点的路由表信息。构造路由 表可以使用集中式 算法( 最典型的 是d ij k s t r a 算法) 或者分布式算法( 如距离矢量算法和链路状态算法) 。 由于节点或链路失效以及新节点或动态链路加入时，可能导致网络拓扑的变化，集中 式算法不能处理这种情况。分布式算法知道网络拓扑的改变，根据更新的拓扑信息来 计算路由路径，因而更具有动态性。下面介绍三种最基本的路由 算法，几乎其它所有 复杂的路由算法都是由这几种算法演化而来的。 2 . 1 . 1 驹k s t r a 最短路径算法 通信网络可以模型化为一个图形，其中顶点和边代表网络的节点和链路。司 心链 路的 代价表示为图 形中的 相关 边的 权值。 d ij k s t r a 为 集中 式 算 法， 需 要完 整的网 络拓扑 和链路权值，以此来计算从一个指定源节点到网 络中 其它节点的最短路径。图 g = g ( v , e ) ， 其中v 和e 分别表示图 形的顶点 和边的 集合。 从顶点。 到顶点， 的边的 权值表示为w ( u , v ) ，须为非负的。一条边的 权值尺度包括跳数 即w ( u , v ) = 1 )、 链路 带宽、平均传输时延、链路排队时延或者它们的组合。算法使用一种权值尺度来计 算 最短路径。 d ij k s t r a 算法的步骤如下: ( 1 )各个节点用从源节点沿己知最佳路径到本节点的距离来标注， 标注分为临 时性标注和永久性标注; ( 2 )初始时，所有节点都为临时性标注，标注为无穷大; ( 3 )将源节点标注为0 ，且为永久性标注，并令其为工作节点; ( 4 )检查与工作节点相邻的临时性节点， 若该节点到工作节点的距离与工作节 点的标注的和小于该节点的标注，则用新计算得到的和来重新标注该节 占 . 5 )在整个图中查找具有最小值的临时性标注节点， 将其变为永久性节点， 并 成为下一轮检查的工作节点; ( 6 )重复 ( 4 )、 ( 5 )，直到日 的节点成为工作节点。 i n 浙江大学硕士学位论文 2 . 1 . 2 距离矢量路由算法 距离矢量路由 算法又名b e l l m a n - f o r d 路由 算法。 该算法要求每个节点内 部维持一 张路由表， 表中给出到侮个目的节点已知的最短距