（管理科学与工程专业论文）基于Overlay网络的QoS问题研究.pdf

山东师范人学硕i j 学位论文 基于o v e r l a y 网络的q o s 问题研究 摘要 o v e r l a y 网络即覆盖网络，它是建立在现有网络上的一层虚拟网络，由分布 在i n t e r n e t 各自治域上的一些覆盖节点和节点之间的逻辑链路组成。覆盖网络 建立在底层的i p 网络上，不需要对底层网络做大规模的修改，具有很好的灵活 性和容错性能。随着i n t e r n e t 的迅猛发展，在i n t e r n e t 上涌现了许多对网络的 服务质量( 包括带宽、时延、抖动等) 有较高要求的应用，如v o i p 、网络直播等， 而现有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 算法，在o s n 覆盖网络架构的基础上， 提出了一种新的拓扑解决方案g o s n ，并在此方案的基础上提出了一种多q o s 尺 度路由算法m s r o n 。 g o s n 拓扑方案简单而且具有较高的效率，避免了过多分层带来的网络状态信 息聚合时的不精确性。在中小规模的覆盖网络中，该方案既克服了原始拓扑结构 中服务节点所要保存的节点的状态信息的数量变得庞大和服务节点的数量将会 因此受到限制的缺点，又具备了分层结构的良好的可扩展性。m s r o n 算法，采用 d i j k s t r a 最短路径算法，把对网络传输非常重要带宽、时延、时延抖动、丢失 率等多个q o s 值作为尺度，为覆盖服务的路由请求选择一条最佳路径。由于m s r o n 算法中综合考虑到多个q o s 因素，因此能够更好的满足覆盖服务所提出的要求， 特别是对时延、抖动非常敏感的音频和视频数据路由传输。同时，m s r o n 算法还 能很好均衡网络资源，包括服务节点的处理能力和链路带宽。仿真实验结果表明 m s r o n 算法相对其它同类算法有较高的q o s 满意率，并能很好的均衡网络相对稀 缺的资源。 山东师范人学硕i j 学位论义 关键词：覆盖网络，服务质量，q o s 路由，g o s n ，m s r o n 分类号：t p 3 9 3 u 山东师范人学顺i ：学位论文 s t u d yo nq o s p r o b l e m sb a s e do no v e r l a yn e t w o r k a bs t r a c t o v 甜a yn e t 、v o r ki sav i n u a ln e 觚o r kw h i c hb a s e do ne x i s t i n gn e t 、o r k s i ti s c o m p o s e do fs o m el o 百c a ll i n k sb e t w e e ns e r ，i c en o d e sa n dn o d e sd i s t r i b u t i n go nt h e a u t o n o m yd o m a i n so ft h ei n t e m e t o v 刚a yn e t w o r kw i t hm eu p p e rc h a r a c t 嘶s t i co f n e x i b i l i t ya n df a u l t t o l e r a n c ei sb a s e do nm eu n d e d 姐n gi pl a y e r ，s on ol a r g e - s c a l e m o d i f i e so fu n d e r l y i n gn e 似o r k si sr e q u i r e d w i t hm er a p i d l yd e v e l o p m e n to ft h e i n t e m e t ，l o t so fa p p l i c a t i o n sw i t hs p e c i a lq o s ( b a j l d w i d t h ，d e l a y ，d e l a yj i t t e r ，e t c ) n e e d sh a v ee m e r g e d ，s u c ha sv o i p 锄d 口t v h o w e v e r ，t h ei n h e r e n td i s a b i l i t i e so f t h ee x i s t i n gi n t e m e tm a k ei tc a nn o ts a t i s 矽t h e s ea p p l i c a t i o n s r e q u e s to fq o s t h e o v 盯l a yn e t w o r ke n l e r g e sa sr e q u i r e d c o m p a r e dw i m m ee x i t i n gn e t 、) l ，o r k ，m eo v e r l a yn e 附o r kw i l l h a v eah u g e a d v a m a g e u s i n gt h eo v 甜a yn e t w o r k ，w ew i l lb ea b l et op r o v i d em o r er e l i a b l ea n d f a u l t t o l e r a i l c ea n db e t t e rn e t 、o r ks e i c e sw i t hn ol a 唱e s c a l ec h a n g et om ee x i s t i n g a r c h i t e c t l l r eo ft h ei n t e n l e t a tt h es a m et i m e ，s o m en e w 印p l i c a t i o n sc a j lb ed 印l o y e d o nt h eg e n 鲥co v e r l a yn e 唧o r ka n ds p e c i f i co v e r l a yn e 铆o r kw h i c hi sd e s i 印e df o r t h es p e c m c 印p l i c a t i o n u s i n gt h eo v e r l a yn e t w o r k ，e v e l li ft h en e 锕o r kl a y e rr o u t i n g e 1 1 r o r so c c u r i tc a nf i n dan e wr o u t i n t gp a m a n di tc a na n dc a nb ej e i n dt h e c o 玎e s p o n d i n go p t i m a lr o u t i n gp a ma c c o r d i n gt od i 仃e r e n tq o s m o r e o v e r ，t h eo v 甜a y n e 觚o r ki sav i l t u a ln e 帆o r ko v e rm ee x i s t i n gn e t w o r k ，s oi td o n tn e e dt oc h a n g et h e c u r r e n tw i d e l yd 印1 0 y e dne t w o r ka r c h i t e c t u r e ，b u ta l s oe a s i e rt oi m p l e l i l e n tr e l a t i v e l y mt l l er e s e a r c ho fo v e r l a yn e t w o r k ，q o sr o u t i n gi sm o s ti m p o r t a n tp o i n t ，a 1 1 di ti s a l s ot h ef o c a lp o i n to f “sp a p e r f i r s t l yk i n d l yo fq o sr o u t i n ga i l dc o r r e c t i v e a t h m e t i ca r ei n t m d u c e da 1 1 dc o m p r i s e dw i t he a c ho m e ri nm i sp a p c r s e c o n d l y ，q o s 撕t h m e t i ci sd i s c u s s e da n da n a l y z e d b a s e do no s n o v e r l a yn e 觚o r ki n 仔a s t r u c n e ，a n e wr o u t i n gt o p o l o g ys 0 1 u t i o ni s p r o p o s e d ，a n dan e wm u l t i p l eq o ss c a l er o u t i n g a r i t h m e t i cm s r o ni sp r o p o s e d 如r t h e r g o s nt o p o l o g ys c h e i n ei ss i m p l eb u tl l i g h e 伍c i e i l t na v o i d sn e 铆o r ks t a t u si m p r e c i s i o nw h 吼t o om a j l yl a y sa g g r e g a t e i ns m a l l a 1 1 dm i d d l er a n g eo v e r l a yn e 帆o r k ，t h i ss c h e m en o to n l yo v e r c o m en o d es t a t u s i n f o n n a t i o nb e c o m i n gt r e m e n d o u sa i l dt h em l m b e ro fn o d e si sl i m i t e dt h e r e b yi n o r i 西n a ln e 帆o r kt o p o l o g ) r ，b u t a l s oh 嬲t h ee x p a l l d a b i l i 哆a d v a n t a g eo fl a y e r e d s 仃u c t u _ r e m s r o na r i t h m e t i c 、h i c ha d a p td i j k s t r ar o u t i n gm e t h o d ，c o n s i i i 舒n gm e i m p o r t a n tn e 研o r k 仃a i l s m i tf a c t o rb a i l d w i d t h ，l a t e n c y 觚dj i t t e 巧，p r o v i d eab e s tr o u t f o ro v e d a ys e i c er e q u e s t m s r o n ，c 0 幽d 甜n gn m l t i p l eq o sf a c t o r sh a sm e a b i l i t i e st op r o v i d es a t i s 研n gs e r v i c ef o ro v e r l a yn e t w o r kr e q u e s t s ，s p e c i f i c a l l yf o rm e a u d i oa 1 1 dv i d e od a t at r a n s m i s s i o n 讹c ha r es e i l s i t i v et od e l a ya n dd e l a yj i t t e r a tm e i i i 山东帅范人学硕l j 学位论文 s 锄et i m e ，m s r o na t h m e t i ca l s oc a nb a l a n c en e t w o r kr e s o u r c e s ，i n c l u d i n gt h e n o d e s c a p a b i l i t ya n dl i n k s b a n d w i d t h t h es i m u l a t i o nr e s u l t sp r o v e t h a tt h em s r o n 撕t h m e t i cc a np r o v i d em o r ee f e i c i e n tq o ss a t i s f a c t i o nc o m p “s e dt oo t h e rs i m i l a r r o u t i n g 撕t h m e t i ca n d b e t t e ra b i l i t i e st ob a l a j l c et h ev “u a b l en e 眦o r kr e s o u r c e s k e y w o r d s ：o v e r l a yn e t w o r k ，q o s ，q o sr o u t i n g ，g o s n ，m s r o n c l a s s i f i c a t i o n ：t p 3 9 3 i v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如没 有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示谢意。 学位论文作者虢参c 降邀， 导师酶 学位论文版权使用授权书 却吲冬 本学位论文作者完全了解兰邀有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人 授权兰邀可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用 影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后 适用本授权书) 学位论文作者签名： 纠荐恝 i 签字同期2 0 。c 年f 月岁同 导师签字： 却谰 签字噍2 。少多月r 山东师范人学顾 ：学位论文 1 1 研究背景 第一章绪论 近年来，一些非传统的应用例如i p 语音传输及网络视频会议的出现，使得传统的 提供尽力而为型服务的i n t e r n e t 无法同时支持即有的和当前出现的新型应用，为此提 出了i p 服务质量( i pq u a l i t yo fs e r v i c e ，i p q o s ) 机制。自1 9 9 3 年提出至今，i e t f 、 i s 0 等国际标准化组织已经提出了i p 网的q o s 参数及其相关协议和模型。目前有关q o s 问题的主要解决方案有综合服务( i n t e r s e r v r s v p ) 模型、区分服务( d i f f s e r v ) 模 型、m p l s 模型等，这些模型都对路由器、交换机等网络设备有一定要求，因此这几种 方案都有很大的局限性，并没有真正得到实施。 目前的i n t 锄e t 是由许多自治系统a s ( a u t o n o m o u ss y s t e m s ) 组成，每个 a s 一般由一个i s p ( i n t e n l e ts e i c ep r o v i d e r ) 来运营管理。a s 之间的连接方式 通常有两种：t r a l l s i t 和p e 鲥n 誊。t r a n s i t 连接关系是在i n t e m e t 上公开发布的， 如果自治域a sb 和c 是t r a n 8 i t 关系，则任何以c 为目的地的包都可以通过b 路由，反之亦然。而p e e r i n g 关系是不公开的，仅对a s 内部用户可见，对其它 a s 是不可见的。如果自治系统b 和c 是p e e n n g 关系，则b 和c 的内部用户可 以使用这种连接关系，其它a s 内的用户则不能使用这种关系，即不能通过b 把 包直接路由到c ，也不能通过c 把包直接路由到b 。如图1 1 所示，实线代表 t r a n s i t 连接关系，虚线代表p e e r i n g 连接关系，当一个包要从a 路由到b 时，如 果采用边际网关协议b g p 公布的路由信息，包需要跨越c 、d 、e 三个自治域。 但显然这不是最佳的路由路径。但如果在自治域c 中设置一个具有路由功能的 中间结点，就可以利用b 和c 之间的p e 嘶n g 关系，数据包就可以只穿越一个自 治域c 。由此我们可以看出，应用层中间节点可以提供更加高效的路由路径。 图1 1t r 柚s i t 和p e e r i n g 连接示意图 为了提高网络的可扩展性，b g p 路由协议在不同自治域之间进行路由时，只 山东师范人学颂i ：学位论文 简单采用“跳数 作为性能度量来选择最佳路径，而实际上这并不一定是最佳路 径，而且b g p 协议也不能探测路径的性能，所不能有效地绕过产生拥塞的连接。 所以随着应用的发展，特别是多媒体业务的迅速发展，网络应用对服务质量的要 求越来越高，而现有i n t e r n e t 已经越来越不能满足人对服务质量的要求了。 覆盖网络( o v e r l a yn e t w o r k s ) 就是在这种情况下产生的。它是覆盖在现有 网络之上的一层虚拟网络，实现方便，不需要大规模改变现有网络架构就能提供 服务质量更好、更可靠的应用服务，并可以方便地通过针对特定应用的覆盖网络 提供现有网络层基础结构难以提供的新业务。 1 2 覆盖网络概述 1 2 1 覆盖网络的概念 覆盖网络( o v e r l a yn e t w o r k s ) ，如图卜2 所示，就是覆盖在现有网络上的一 层虚拟网络，它由覆盖网络节点和节点的逻辑链路组成。覆盖网络的节点可以是 终端、服务器，也可是路由器等网络节点。节点间的逻辑链路实际上是一个虚拟 链路，它对应着底层的一条或多条物理路径。它能利用i n t e n e t 给用户提供更加 可靠的服务。覆盖节点通常具有数据保存与处理、路由等功能。逻辑链路则在各 个节点问对数据进行传输。 与现有网络相比，覆盖网络将有很大的优势。利用覆盖网络，不需要大规模 改变现有的i n t e r n e t 网络架构就能提供更为可靠、容错性更好的网络服务。可以 在通用覆盖网络架构上部署新应用，也可以在为特定应用设计的覆盖网上提供现 有网络难以提供的新型应用。借助覆盖网络，即使网络层出现路由错误，也可以 通过覆盖网络在覆盖层上找到新的路由。并且可以根据不同应用服务的服务质量 要求寻找相应的最优的路由路径。而且，覆盖网络只是覆盖在现有网络之上的一 层虚拟网络，不需要改变现已广泛部署网络架构，也更加易于实现。 2 山东师范人学坝i ：学位论文 1 2 2 覆盖网络的分类 a vn e t o r k d 图1 2 覆盖网络示意图 覆盖网络按节点是否固定主要可以分为两大类，基于终端主机的覆盖网络和 基于固定节点的覆盖网络。 基于终端主机的覆盖网络中，终端主机即覆盖网结点之间只是在网络层进行 逻辑连接，而且得不到i s p 的支持。它要求一个终端主机必须同时和其它多个终 端相连。例如，p 2 p 文件共享系统和基于终端主机的i n t e r n e t 的应用层多播都这 类基于主机的覆盖网络的典型应用。但有两个问题限制了这类网络的应用，即终 端的带宽接入限制和终端接入的“最后一公里 的传输延迟。此种网络的动态性 也比较强，这是因为终端主机随时有可能加入或者离丌网络，所以此种网络难以 提供持续稳定的网络服务。 在基于固定节点的覆盖网络中，它使用一系列分布在i n t e r n e t 上的固定节点 来实现覆盖服务，它通常由第三方服务提供商( 这里我们称之为o s p ，即o v e r l a y s e r v i c ep r o v i d e r ) 来维护，o s p 通过和i s p 签订服务等级协议( s e r v i c el e v e l a g r e e m e n t ，s l a ) 使覆盖服务节点之间的覆盖链路的q o s 得到保证，内容分发网络 就属于这类覆盖网络。该类覆盖网络的优点就是能够提供可靠的服务，但由于覆 盖服务节点在覆盖网搭建时就已经固定下来了，服务节点的加入或者离开就比较 麻烦，所以网络的灵活性较差。 1 2 3 覆盖网络的应用 覆盖网络是为了解决i n t e r n e t 存在的诸多问题而提出的，目的是为了是使 3 山东师地人学颂i j 学位论文 i n t e r n e t 能够支持更多的业务和应用。覆盖网络的应用有很多，主要在内容分 发网络、p 2 p 、应用层组播等方面 1 内容分发网络 内容分发网络( c o n t e n td e l i v e r yn e t w o r k ，c d n ) 【2 】的是由遍布在世界上主要 i n t e r n e t r 接入点的内容服务器节点组成的覆盖网络，并利用一种特殊的路由机 制将网站内容发布到离用户最近的网络“边缘”，使用户能以最快的速度、从最 为接近的地方获取所需的信息。 c d n 代表了一种基于质量与秩序的网络服务模式。简单地说，c d n 是一个经 过预先策略性部署的整体系统，包括分布式存储、负载均衡、网络请求的重定向 和内容管理4 个要件，而内容管理和全局的网络流量管理( t r a f f i cm a n a g e m e n t ) 是c d n 的核心所在。通过用户就近性和服务器负载的判断，c d n 确保内容以一种 极为高效的方式为用户的请求提供服务。 2 p 2 p 在n p a s t e r ，g n u t e l l a 等文件共享模型中，一群高性能的中央服务器保存着 网络中所有活动对等计算机共享资源的目录信息。当需要查询某个文件时，对等 机会向一台中央服务器发出文件查询请求。中央服务器进行相应的检索和查询 后，会返回符合查询要求的对等机地址信息列表。查询发起对等机接收到应答后， 会根据网络流量和延迟等信息进行选择，与合适的对等机建立连接，并开始文件 传输。但是这种对等网络模型存在很多问题，首先，中央服务器的瘫痪容易导致 整个网络的崩溃，可靠性和安全性较低；再者，随着网络规模的扩大，对中央索 引服务器进行维护和更新的费用将急剧增加，所需成本过高：而且，中央服务器 的存在经常引起共享资源在版权问题上的纠纷，并因此被攻击为非纯粹意义上的 p 2 p 网络模型。对小型网络而言，集中目录式模型在管理和控制方面占一定优势。 但鉴于其存在的种种缺陷，该模型并不适合大型网络应用。正是这样，人们提出 了利用覆盖网络实现p 2 p 文件共享机制。 p 2 p 文件共享与传统的集中式模式文件共享相比有如下的优势： ( 1 ) 非中心化：网络中的资源和服务分散在所有结点上，信息的传输和服 务的实现都直接在结点之间进行，可以无需中间环节和服务器的介入，避免了可 能的瓶颈。p 2 p 的非中心化基本特点，带来了其在可扩展性、健壮性等方面的优 势。 ( 2 ) 可扩展性：在基于覆盖网络的p 2 p 网络中，随着用户的加入，不仅服务 的需求增加了，系统整体的资源和服务能力也在同步地扩充，始终能较容易地满 足用户的需要。整个体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以 认为是无限的。 ( 3 ) 健壮性：由于服务是分散在各个结点之间进行的，部分结点或网络遭 到破坏对其它部分的影响很小。在部分结点失效时能够自动调整整体拓扑，保持 4 山东师范人学硕i ：学位论文 其它结点的连通性。p 2 p 网络通常都是以自组织的方式建立起来的，并允许结点 自由地加入和离丌。还能够根据网络带宽、结点数、负载等变化不断地做自适应 式的调整。 ( 4 ) 高性价比：可以有效地利用互联网中散布的大量普通结点，将计算任 务或存储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到高 性能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成 本提供更高的计算和存储能力。 ( 5 ) 负载均衡：由于每个节点既是服务器又是客户机，减少了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，所以能 更好的实现整个网络的负载均衡。 3 应用层组播 随着网络的发展，许多基于网络的应用被开发出来。这其中很多应用需要用 到组播，例如网络视频会议、大规模网络游戏等。而它们对组播的运用与当初设 计i p 组播的初衷有很大不同。首先，这些应用的组播规模较小，而i p 组播是设 计用来进行大规模组播应用的；其次，在i p 组播中，与组播相关的功能都放在 网络层即路由器上实现，随着组播数目的增大，路由器需要保存和更新的路由表 的数量也会相继增大，这样会增加路由器的负担。所以，虽然经过了十多年的研 究，i p 组播技术至今仍只停留在实验平台( 如m b o n e 【3 1 ，i n t e n r e t 2 【4 】等) 上的应用 阶段，一直没有能够进入商业领域。 覆盖网络技术的提出使在应用层实现组播成为可能。所谓应用层组播足指将 原本在网络层即路由器上实现的组播相关功能移到应用层即终端主机上来实现。 在应用层组播中，所有的终端节点组成一个覆盖网络，每个终端主机都是一个覆 盖服务节点。为了更好的利用网络资源，应用层组播也需要在组成员间建立一颗 组播分布树，与i p 组播不同的是，应用层组播的分叉点必须是终端系统，也就 是说组播数据的复制是在终端系统中实现的，所以有些链路可能由多份数据拷 贝，效率不如i p 组播。但是应用层组播有如下的优点：首先，它不需要路由器 的支持，护组播之所以不能在i n t e r n 6 t 上使用就是因为大部分路由器不支持， 应用层组播绕开了这一点。其次，由于任何两个组员之间在发送或接收数据时都 是单播方式的，所以可以使用单播流量控制和差错控制协议，从而简化了i p 组 播拥塞控制机制。因此应用层组播更有可能成为i n t e r n e t 上组播的实现方式。 1 3 覆盖网络研究现状 随着最近几年覆盖网络技术的发展，国内外科技工作者对覆盖网络做了大量 的研究，也取得了一定的进展，主要集中在网络平台、拓扑结构、q o s 路由、虚 拟链路技术、安全问题等方面。 5 山东帅范人学硕i j 学位论文 1 3 1 覆盖网络平台研究 覆盖网络平台主要可以分为两类，一类为是特定应用设计的，另一类则是通 用覆盖网络。人们根据不同的应用要求提出了许多覆盖网络的模型，并且对它们 进行了研究、部署和测试，并取得了一定的成果。 目前，大部分对覆盖网络的研究都是针对特定应用的，比如 c h o r d 【5 】，b r o c a d e 6 】，和t a p e s t r y 【7 】等等都是属于这一类的，它们的目标都是在一 个大的分布式系统中对内容进行迅速的定位，而还有一些则针对基于覆盖网络的 应用层组播进行研究。这一类的研究都提出了基于某种特定应用的覆盖网络构 架，但是随着应用的增多，为每一种特定应用都建立不同的覆盖网络则显得多余 了。于是，人们提出了通用覆盖网络的概念，它对对已有的和将来的一些应用提 供支持。当前，对通用平台的研究主要有0 p u s ( o v e r l a yu t i l i t ys e r v i c e ，0 p u s ) 【8 】，r o n ( r e s i l i e n to v e r l a yn e t w o r k s ，r o n ) 【9 】，o v e r q o s ( 0 v e r l a yn e t w o r k o f f e r i n gq o s ，o v e r q o s ) 【1 0 】【1 1 】，s o n ( s e r v i c eo v e r l a yn e t w o r k s ，s o n ) 【1 2 】【1 3 】，o s n ( o v e r l a ys e r v i c en e t w o r k s ，o s n ) 【1 4 1 等。 o p u s 是一个提供q o s 保证的大范围覆盖应用服务的网络平台，它能够同时为 多个分布式应用提供必要的服务。在o p u s 模型中，大范围的资源映射是由应用的 性能要求决定的，它能同时满足应用的性能和可靠要求，并且具有很的扩展性能， 能够扩展到数千个扩展结点。 r o n ，即弹性覆盖网，是一个在现存的i n t e r n e t 底层路由之上的应用层覆盖 网络。它在各个结点之间建立虚拟连接，并控制它们之间的连通性，一旦网络层 出现路由故障时就通过覆盖层结点重新路由。覆盖层结点检测链路的各项性能指 标，并根据所得到的各项性能信息决定是直接传输数据还是通过其它的r o n 节点。 r o n 可以在几秒钟内发现路径故障和周期性的性能下降并能将其恢复正常，可以 减少丢包率，降低时延，提高吞吐量，在很大程度上提高了路由性能。 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 dl o s sv i r t u a ll i n k ，c l v l ) 的概念，通过 在数据流中加入冗余数据包来实现丢包率的控制。使用c l v l ，0 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 要求的服务数据流汇聚成一个“束 ，资源是以“束” 为单位进行路由分配调度的。 s o n 利用覆盖网技术在i n t e r n e t 上提供增值服务，s o n 的原理是s o n 服务提 供商可以从不同的i s p 那里购买有一定q o s 保证的带宽( 但这个带宽相对来说是 较低的) ，在这个基础上建立一个覆盖网络来给用户提供更高q o s 保证的服务。 它重点研究了s o n 带宽提供的数学模型，在管道s l a 模型基础上，通过降低s o n 成本并向用户提供灵活的动态的带宽，使s o n 利益最大化，其数学模型可以作为 6 山东师范人学硕f ：学位论文。 定价策略的依据，但它没有涉及端到端q o s 保证的实现问题。 o s n 可以为各种覆盖服务提供资源分配和协商、路由、拓扑发现等服务进行 支持。o s n 适应于对q o s 特别敏感的覆盖应用服务，文献 1 4 设计了两种路由选 择算法，可以为覆盖服务提供满意的q o s ，并且该算法还均衡了链路的流量和节 点的计算能力。 1 3 2 覆盖网络拓扑结构研究 由于覆盖网络是建立在应用层之上的，所以覆盖网络的拓扑结构对其性能影 响很大。一个良好的拓扑结构能够有效发挥覆盖网络的特点和优势，提高整个网 络的资源利用率。 文献 1 5 介绍并分析了覆盖网络拓扑模型，并把它们分为两类，一类是不知 道或者不利用物理层网络拓扑构建的网络拓扑，如全网格( f u l lm e s h ) 、网格 树( m e s ht r e e ) 、最小生成树( m i n n u m ss p a n n i n gt r e e ) 等；另外一类是利用 物理层拓扑结构而构建的覆盖网络结构，如邻近连接( a d j a c e n tc 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 gt r e e ) 等。 然后在这些拓扑结构上利用不同的路由算法进行了仿真，通过对错误修复率、路 由耗费等性能指标进行对比，得出了以下三个结论： ( 1 ) 网络拓扑对覆盖网络的路由服务性能有很大影响，在一种网络拓扑下 表现很好的算法在另外一种拓扑结构下可能表现很差。 ( 2 ) 下层物理网络拓扑信息对构建一个高效的覆盖网络拓扑结构是非常有 用的，这是因为知道物理层网络拓扑的覆盖网络拓扑模型在各种路由算法下表现 比其它拓扑模型普遍要好。 一 ( 3 ) 网格树模型在在覆盖服务网中并不是一个好的拓扑模型选择，在性能 仿真实验中，所有的路由算法在这个拓扑结构下的性能表现都很差。 对于拓扑结构的选择，我们一般要根据实际的需要来进行选择。文献 1 6 提出了一种利用交叉生成树来设计覆盖网络拓扑结构的方法，用此方法设计的拓 扑具有高性能、多路径、自组织的特征。文献 1 7 把数学上的维数和曲率的概念 用到的覆盖网络的拓扑的构建上。文献 1 8 则对带宽保证下的覆盖网络拓扑进行 了研究，提出了一种启发式算法来设计运行费用最小化的覆盖网络拓扑。 1 3 3 覆盖网络虚拟链路研究 覆盖网络虚拟链路是覆盖网络两个节点之间的可靠链路，为消息传输提供端 到端的可靠性，是覆盖网络研究中的重要组成部分。 文献 1 9 主要讲述了通过多路径来弥补标准i p 单路径的缺陷。在i p 网络上 7 山东师池人学顾l j 学化论文 构筑一个覆盖网络，通过不同的覆盖路径传输不同的部分，多路径可以避开瓶颈 问题。文章中提出的m p o t 方案为文件和实时媒体在i p 单一路径中存在瓶颈链路 时极大的提高性能，i p 路径中的最小链路带宽严重限制了有效传输层带宽。这 种方法主要是当直接i p 传输路径具有瓶颈时在两个主机之间提供受控的间接路 径。覆盖成员使用获得拓扑消息决定路径节点和虚拟链路的选择。通过在传输中 插入中间主机，路径被局部控制，可以帮助数据不通过瓶颈区域。 文献 2 0 将传统的端到端控制协议转换成逐跳控制协议，并在链路上实施实 时恢复协议，降低了包的丢失率可传输的抖动性能，保证了传输的可靠性。 文献 2 1 从延时的三个主要因素( 传输延时、带宽延时、主机和中间节点等 原因造成的其他延时) ，提出了基于测量的计算路径方法，使消息延时最大概率 接近最优，降低端到端的延时，保证了服务质量。文章中采用m e a s u r e m e n td a e m o n 用来收集延时测量，p a t h d a e m o n 用来为消息计算路径，r o u t i n g d a e m o n 用来路由 其他d a e m o n 的路由信息。同时因为带宽等链路指标也是链路研究的一个部分， 文献 2 2 ，2 3 中提出了对链路和路径带宽的测量方法，文献 2 4 对可获得带宽进 行了研究。 1 3 4 覆盖网络路由研究 路由是覆盖网络研究的关键问题之一。目前，国内外的研究者对覆盖网的路 由问题进行了大量的研究，但其中大部分的研究工作都是针对特定应用的。 文献 2 5 提出了一种基于最大收益的d n s 内容路由算法，该算法采用名字解 析服务器与网关处分别获取内容服务器负载信息和路由信息生成网络收益，根据 最大网络收益来选取最佳的内容服务器。 a k a r o u t i n g 【2 6 】是内容分送网络系统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 则比 较这三条路径，从中选取一条最佳的路径。 覆盖网络的q o s 路由是覆盖网络路由研究的一个重要方向，是本文研究的重 点，我们将在以后章节中作详细介绍。 1 4q o s 概述 从计算机网络诞生开始，人们就一直致力于提高系统的服务性能和服务质 量，所以q o s 问题由来已久。目前在高速网络中按照用户的要求提供q o s 控制是 一个普通的要求，也是i n t e r n e t 发展的重要挑战。计算机网络的q o s 问题已经 成为当今网络研究最重要的研究领域之，对未来网络技术的研究、应用和发展 山东师范人学硕i ：学位论文 具有举足轻重的意义。 随着高速网络技术和多媒体技术的飞速发展，人们越来越多的提出了包括多 媒体通信在内的综合服务要求。传统的分组交换网络，如i n t e r n e t 是面向非实 时的数据通信( 如f t p 、e m a i l 等) 而设计的，采用的t c p i p 协议主要是为了 优化整个网络的数据吞吐量并保证数据通信的可靠性。而当今的分布式多媒体应 用( 如视频会议、视频点播、i p 可视电话、远程教育) 不仅包括文本数据信息， 还包括语音、图形图像、视频、动画这些类型的多媒体信息。这些不同应用需有 不同的q o s 要求，而且对q o s 的要求也越来越高。 1 4 1q o s 的概念 q o s 是指发送和接收信息的用户之间以及用户和传输信息的综合服务网络之 间关于信息传输的质量约定。该约定可以被理解为服务提供者与用户之间的一份 服务契约，即服务提供者承担支持给定的服务质量，当且仅当用户按照约定的信 息流特征产生数据。换句话说，服务质量包括用户的要求和网络服务提供者的行 为两个方面，是用户和服务提供者两方面主客观标准的统一。用户的要求是指用 户在i n e t e r n e t 上进行多媒体通信时所要求的服务类型以及相应的传输性质及 相应的传输性能和质量等；网络服务提供者的行为则指i n t e r n e t 针对某一类服 务所能提供和达到的性能与质量。 q o s 控制的目标是为i n t e r n e t 应用提供服务区分和性能保证：服务区分是根 据不同的应用需求为其不同的服务；性能保证则要解决诸如带宽、丢失率、延迟f 延迟抖动等性能指标的保证问题。 1 4 2q o s 控制和管理 所谓q o s 的控制和管理，是指计算机网络系统采用一定的方法接受用户应用 的服务请求，并保证其q o s 的过程。在这一过程中，网络系统将用户的请求映射 成一些预先定义的q o s 参数，进而与系统的有效资源对应起来，通过资源分配和 调度，完成用户的应用。这一过程也称为q o s 协商。q o s 协商有时可能不成功， 其原因是系统无法完全满足应用的网络带宽、延迟等要求，这时通常就要进行 q o s 重协商，以确定应用是否容忍降低的服务。 q o s 控制和管理机制( 也称为算法) ，是由用户的q o s 描述、资源能力以及 资源管理策略所驱动的。在对资源的管理上，q o s 机制可以分为静态和动态两种； 静态的资源管理是处理信息流的建立和端到端的q o s 的重协商阶段，动态的资源 管理是处理媒体传输阶段。前者通过对系统资源的协商和预留，使系统接受用户 的q o s 请求，而后者是在系统接受应用的q o s 请求之后，通过资源调度和流控制 9 山东帅范人学硕i j 学位论文 等机制来保证和维护用户所获得的q o s 。 当用户应用与网络系统达成q o s 约定之后，网络系统就必须提供基于q o s 的 信息流实时拥塞控制。这种控制是能q o s 控制机制来实现的。 为了保证应用的端到端的q o s ，网络系统只分配资源是不够的，还需经常维 护已经担保的q o s ，这是由q o s 管理机制来完成的。 1 4 3q o s 的体系结构 q o s 研究的目标是提供有效的端到端的服务质量控制或保证。近年来，i e t f 在此方面作了很多工作，先后提出了两种不同的i n t e r n e t q o s 体系结构：综合服 务( i n t e g r a t e ds e r v i c e s ，i n t s e r v )和区分服务 ( d if f e r e n ti a t e d s e r v i c e s d i f f s e r v ) 1 综合服务( i n t e g r a t e ds e r v i c e s ，i n t s e r v ) 为了满足i n t e r n e t 多媒体应用的实时传输需求，i e t f 定义了综合服务模型 i n t s e r v 。r f c l 6 3 3 给出了i n t s e r v 的框架，并将其划分为综合服务模型和参考 实现框架两大部分。 在服务层次上，除了原来的尽力而为型的服务以外，i n t s e r v 还为每个流( 单 独的或聚焦的) 为基础，提供了两种端到端的面向实时传输的服务：质量保证服 务( g u a r a n t e e ds e r v i c e ) 和可控负载型服务( c o n t r 0 1 1 e d l o a ds e r v i c e ) 在实现在的层次上，i n t s e r v 服务方案需要所有的路由器在控制路径上处理 每个流的信令消息并维护每个流的路径状态和资源预留状态，并且在数据路径上 执行基于流的分类、调度和缓冲区管理。 在技术层次上，i n t s e r v 依靠资源预留协议r s v p 提供q o s 协商机制，逐节点 ( h o p _ b y 柏o p