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

浙江大学硕士学位论文 摘要 通过配置自治系统中一系列智能节点，以i p 层作为底层的，建立起了服务于多媒 体通信的覆盖层网络。覆盖网中的智能节点能够提供应用多媒体服务，进行媒体数据 的传输、网络资源分析和网络宏观调配资源。用户通过多媒体通信终端，连接到覆盖 网中来，通过一系列的智能节点的发送，转发，满足用户对组合多媒体服务的需求。 - 本文主要研究覆盖网q o s 路由问题。通过覆盖网中一系列的智能节点及其提供的 多媒体服务，把两个客户终端连接在一起，满足客户的网络需求。本文的覆盖层路曰 区别于风络层的q o s 路由，也区尉于应用层的单播多播，在现存的各种解决方案都不 能很好的解决这种覆盖网q o s 路由问题，我们的解决方案包括智能连接i l 方案和 q s r o n 算法。i l 拓扑结构通过创建隐性节点和显性节点的机制，在不增加各节点探 测带宽的情况下，最大限度提高网络节点的连通性。在这个拓扑方案的基础上，q s r o n 算法方案，采用d i ) k s t r a 算法，把对网络传输非常重要的带宽、时延、时延抖动、丢失 率等q o s 值作为尺度建立度量权重，分别对单个服务区段进行最佳路径选择和对整个 组合服务进行最佳路径选择，搜索最佳服务路径。获得较好的q o s 满意率。 关键词；覆盖网路由，q o s ，d i j k s t r a 算法，拓扑结构几方案，q s r o n 算法 i i 浙江大学硕士学位论文 a b s t r a c t w i t ht h ea u m n o m o u ss y s t e m s ，a l lo v e r l a ym e d i as e r v i c ep r o x yn e t w o r ki sf o r m e db yas e t o f i n t e l l i g e n tp r o x i e sd e p l o y e da ts t r a t e g i cl o c a t i o n si nt h eu n d e r l y i n gn e t w o r kl a y e r p r o x i e s i nt h i so v e r l a yn e t w o r ka r ea b l et op r o v i d em u l t i m e d i as e r v i c e s ，s u c ha sm e d i ad a t a t r a n s e o d i n ga n da n a l y s i s c l i e n tp o i n t so f m u l t i m e d i ac o m m u n i c a t i o nc a l lt h e nc o n n e c tt o t h i sn e t w o r k 、a n dr e q u e s tac o m b i n a t i o no f m e d i as e r v i c e sd e l i v e r e db yo n eo rm 蕊p r o x i e s i n i t i nt h i sp a p e r ，w es t u d yt h ep r o b l e mo fq o ss e r v i c er o u t i n g 加o v e r l a yn e t w o r k as e r v i c e p a t hc o n n e c t sap a i ro f c o m m u n i c a t i n g e n dp o i n t sv i aac h a i no f m e d i as e r v i c ep r o x i e s w e s h o wt h a ts e r v i c ep a t hf i n d i n gi sd i f f e r e n tf r o mb o t hn e t w o r k - l e v e lq o sm u t i n ga n d a p p l i c a t i o n - l e v e lm u l t i c a s t ；a n dt h a te x i s t i n gs o l u t i o n sa r en o tm a d i l ya p p l i c a b l e o u r s o l u t i o ni n c l u d e st h ei n t e l l i g e n tl i i l km e t h o da n dq o ss e r v i c er o u t i n gi no v e r l a yn e t w o r k b yu s i n gt h er e c e s s i v ep o i n t s ，t h ei lm e t h o dc r e a t e sah i g h l yc o n n e c t e dm e s hw i t h i nt h e o v e r l a yn e t w o r k ，w i t h o mi n c r e a s i n gb a n d w i d t hp r o b i n go v e r h e a d b a s e do nt h em e s h ，t h e q s r o na l g o r i t h mu s e sd i j k s t ma l g o r i t h ma n dc o m p u t e st h e s a f e s t s e r v i c ep a t h sw i m r e s p e c t t oe n d t o - e n dr e s o u r c ea v m l a b i l i t y ，t h u sa c h i e v i n gh i 出o v e r a l ls e r v i c ep a t hs u c c e s s r a t e b o t hs i m u l a t i o na n da n a l y t i c a lr e s u l t sd e m o n s t r a t et h es o u n d n e s so f o u rs o l u t i o n k e y w o r d s ：o v e r l a yn e t w o r kr o u t i n g ，q o s ，d i j k s t r aa l g o r i t h m ，i n t e l l i g e n tl i n km e t h o d ， q s r o na l g o r i t h m 1 i i 浙江大学硕士学位论文 第一章绪论 1 1 o v e r l a yn e t w o r k 及其现状 1 1 1 覆盖网的出现 1 、覆盖网的提出 当今世界，互联网应用的发展取决于三个方面：计算机的处理能力，网络的连 通性和客户的个人偏好。这三个方面的综合发展，不断提高网络通信的性能，让宽 带数据流传输成为可能。并随着各地多媒体代理服务器的出现，各种各样新服务不 断涌现，包括多媒体服务，共享服务等都越来越多，特别是由多种服务组合起来形 成的复杂服务。随着多媒体通信传输的发展，端对端数据服务质量的不断提高，让 随时随地把数据从源节点到目的节点进行传送的端对端服务成为可能。由于互联网 上各种应用服务需求的不同，目前的趋势不是采用发展大规模集成电路的形式来满 足各种特定的服务需求，而是通过软件工程的方法，实现在同一路径上由多个服务 组合而成的应用，这种应用称之为组合服务( c o m p o s a b l es e r v i c e s ) 。基于这种情况， 各个代理服务器广泛分布予互联网中，应用服务的服务质量要求存在着一层中间层 网络，它能够支撑各种组合服务的多媒体路由，满足客户的各种个性化需要。而现 实中，无论是目前的网络层还是p 2 p 都不能满足这种日益发展的网络需求，就在这 样的环境下，出现了架设在以网络层为基础的覆盖网络( o v e r l a y n e t w o r k ) 。 2 、覆盖网络的演进 覆盖网络( o v e r l a y n e t w o r k ) 就是建立在鼹络层上面，服务于应用层的一层虚 拟网络。从某种意义上说，h t e m e t 就是一个覆盖网络。i n t e m e t 能够互连各种网络 和目标；其底层网络可以是以太网、令牌网等等：在基于这些底层网络之上，就可 以把i p 层看作为i n t e m e t 的覆盖层。 覆盖网分为“无组织的覆盖网”和“有组织的覆盖网”两大类。目前，在互联网上 广泛使用的大多是无组织的覆盖网，当今宽带用户流量中一半以上正是这种。 无组织的覆盖网已经演进了4 代：第一代网络采用中央控制网络体系结构，如 早期的n a p s t e r ；第二代采用分散分布网络体系结构，适合在自组织( a dh o c ) 网上应 用，如即时通信等：第三代综合了第一代和第二代的优点，采用混合网络体系结构， 浙江大学硕士学位论文 用分布的超级结点取代中央检索服务器；第四代目前尚处于开始发展中。有组织的 覆盖网目前还处于学术界研究的阶段，如t a p e s l r y 、c h o r d 嘲、p a s l a - y 3 1 和c a n 4 等， 而正在研究的新代的应用包括多播、网络存储等，也都将运行在有组织的覆盖网 1 1 2 覆盖网概述 如今以及在可以预见的未来，分布式应用互联网系统只能建立在一种单播的尽 力而为的数据包传输体系上面。但是，许多的应用对于这样一种服务感到远远不够。 比方说涉及机密的应用系统需要有能控制数据包传输经过的路径这样一种功能；视 频会议系统以及i n t e m e t 广播系统希望能够有效的进行群组的交流；股票应用系统 可能希望在众多的路径中找出一条具有最短延迟的路径，而这是正常路由所办不到 的；而内容分发网络希望在网络中有效的发布和存储数据。 为了解决目前的这种状况，一种办法就是在路由器中实现我们所需要的网络服 务。但是这样做有两个缺点。首先，由于这些网络服务本身需要尽可能简单快速， 把它们放到路由器中可能并不是很恰当；其次，一般一些重要的网络服务只有在设 计初把它集成到路由器中，这样实现和维护起来才是最简单和有效的。现在的互联 网的规模已经非常庞大，又分别为不同运营商和机构拥有和管理。要想同步改变体 系结构几乎是不可能的，而等待各个子网逐步改变又太慢，所以解决这些问题的方 法是在保持现有互联网继续工作的同时实现无缝的演进。 那么，只有覆盖网络能很好地解决这些问题，可以很好地绕开上面的问题，而 给应用系统提供很好的网络服务。在覆盖网络中，分布在网络中的相互协作的服务 器作为节点组成了一个虚拟的网络。利用底层网络层提供的服务，数据包在这些虚 拟的路由器之间交换数据，但是对于特定的应用，这些节点可以任意的调整它们的 功能来为特定应用服务。比方说，基于覆盖网络的多播系统可以在节点处复制和分 发数据；内容分发随络可以存贮数据；r o n ( r e s i l i e n t o v e d a y n e t w o r k s ) 5 】通过不断地对 网络进行性能探测可以提供更有效的数据交换服务。 覆盖网络( o v e r l a yn e t w o r k ) 不需要大规模改变现有网络架构就能提供更为可 靠、容错性更好的服务。有了覆盖网络，即使网络层出现错误，应用系统也可以凭 借覆盖网络快速找到替代路由，并且可以根据应用服务的不同服务质量要求寻找相 应的最优路径。同时，覆盖网络只是覆盖在现有网络之上的虚拟网络，并不需要改 变现有网络架构，实现起来也是很方便的。覆盖网络是由一系列分布于i n t e r n e t 各自 治系统内部的覆盖服务节点以及连接它们的逻辑链路所组成的虚拟网络，它能有效 地利用i n t e m e t 给终端用户提供更为可靠的服务。覆盖节点通常具有路由、数据处理 2 浙 工大学硕士学位论文 和数据保存等功能，而逻辑链路( 即覆盖链路) 通常对应底层的一条或多条物理路 径。图1 - 1 所示是个覆盖网络。 图1 - 1 覆盖网络示意图 覆盖网络( o v e r l a yn e t w o r k ) 是在物理拓扑结构上构建的一层虚拟结构，例如： 内容寻址网络( c a n ) 4 1 ，c h o r d t 2 1 ，p a s t r y t 3 】和v i c e r o y l 6 1 等都属于覆盖网。覆盏网系 统由一组业务结点构成，这些结点分布在i n t e m e t 上，并由业务链路连接起来，从 而在现有的i p 网络上形成一个虚拟的传输覆盖网。它的最大特点在于，它不需要对 现有的网络层协议做任何修改。为了能够为每条业务数据流提供所需的服务质量保 证，实时业务覆盖网系统( r s o n ) 中每个业务结点都参与一个分布式覆盖网业务 路由协议( o s r p ) 以协同工作，它包括业务链路状态的测量、链路状态信息的分 发、业务路径的选择和建立，以及相应的数据包交换模块。与电信业发展的具有集 中控制的下一代网n g n 的思路不同，这是一种分布式的控制管理，保持了互联网 分布自治的特性，称之为无所不在的n g i 。这方面研究工作最突出有代表性的是： 弹性覆盖网( r e s i l i e n to v e r l a yn e t w o r k s ) 、t a p e s t r y ”和p l a n e t l a b t t j 。 至于详细的覆盖网络拓扑，因各应用实现的不同而有历区别。我们将在介绍路 由技术的时候给与说明( 在2 3 3 节将介绍覆盖网络拓扑结构的最新研究) 。 浙江大学硕士学位论文 下面将介绍几种典型覆盖网络。 1 1 3 弹性覆盖网 弹性覆盖网( 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 ) 被作为应用层覆盖在现有的互联网 选路层上口1 。r o n 的结点监视互联网路径的机能和质量，并根据这些信息决定是直 接传输数据还是通过其他r o n 的结点。用r o n 可以减少丢包率，降低时延，提高 吞吐量，可以在几秒钟内发现路径损耗和周期性性能下降并且使之恢复正常，而目 前使用的广域路由协议b g p 等为此要耗费几分钟。 r o n 的结点被放置在不同的选路域中，它们之间可以协同工作并互相转发数 据。因为接入服务器( a s ) 是独立行政管理、配置和选路的，属于不同的运营商，很 少有共享的内部链路，所以a s 发生的故障彼此之间是相互独立的。 r o n 通过主动探测和监视结点之间的链路来发现问题：如果接下来的互联网路 径是最好的，就使用这路径，不需要其他结点介入；如果接下来的互联网路径不是 最好的，r o n 就将数据转发到其他结点，用以建立最佳路径。每一个r o n 的结点 通过综合主动( 探针) 探测和被动观察运行的数据传输，建立包括丢包率、时延和吞 吐量等参数在内的路径质量表，与其他结点之间相互交换这些质量信息，并进一步 在此基础上通过路由协议建立转发表。 r o n 的第二个目标是将路径选择与分布应用综合起来，使之具有根据应用特性 来选择路径的能力。在多媒体会议业务中，用户可以直接使用r o n 的数据库来透 明地构成包括所有参会成员的覆盖网，从而实现低丢包率、低时延抖动和高吞吐量。 网络管理员可以利用r o n 路由器在若干个局域网之间构成覆盖网，成为“覆盖虚拟 专用网( v p n ) ”。这个概念进一步发展成为“覆盖互联网业务提供商( i s p ) ”，即向传统 运营商购买带宽，通过r o n 连接不同的传统i s p 的汇聚接入点( p o p ) ，利用r o n 的选路机制，为用户提供更有弹性和容错能力的互联网业务。 r o n 的第三个目标是提供框架，以实现管制路径选择的显式路由策略，用来管 理网络中路径的选择。r o n 很容易对数据包进行识别分类，这样就能够实现可接受 的使用方式，或能够强制性地控制转发速率。 t a p e s t r y 是一种有组织的覆盖网，是可扩展的基础设施。分布式的目标定位和 选路( d o l r ) 机制使其具有高性能，并可扩展与位置无关的选路，利用局部资源将消 4 浙江大学硕士学位论文 下面将介绍几种典型覆盖网络。 1 1 。3 弹性覆盖网 弹性覆盖犀j ( 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 ) 被作为应用层覆盖在现有的互鞋网 选路层上目。r o n 的结点监视互联网路径的机能和质量，并根据这些信息决定是直 接传输数据还是通过其他r o n 的结点。用r o n 可以减少丢包率，降低时延，提高 吞吐量，可以在几秒钟内发现路径损耗和周期性性能下降并且使之恢复正常，而目 前使用的广域路由协议b g p 等为此要耗费几分钟。 r o n 的结点被放置在不同的选路域中，它们之问可以协同工作并互相转发数 据。因为接入服务器( a s ) 是独立行政管理、配置和选路的，属于不同的运营商，很 少有共享的内部链路，所以a s 发生的故障彼此之间是相互独立的。 r o n 通过主动探测和监视结点之间的链路来发现问题：如果接下来的互联网路 径是最好的，就使用这路径，不需要其他结点介入；如果接下来的互联网路径不是 最好的，r o n 就将数据转发到其他结点，用咀建立最佳路径。每一个r o n 的结点 通过综合主动f 探针) 探测和被动观察运行的数据传输，建立包括丢包率、时延和吞 吐量等参数在内的路径质量表，与其他结点之问相互交换这些质量信息，并进一步 在此基础上通过路由协议建立转发表。 r o n 的第二个目标是将路径选择与分布应用综合起来，使之具有根据应用特性 来选择路径的能力。在多媒体会议业务中，用户可以直接使用r o n 的数据库来透 明地构成包括所有参会成员的覆盖网，从而实现低丢包率、低对延抖动和高吞吐量。 网络管理员可以利用r o n 路由器在若干个局域网之间构成覆盖网，成为“覆盖虚拟 专用网( v p n ) ”。这个概念进一步发展成为“覆盖互联网业务提供商0 s p ) ，印向传统 运营商购买带宽，通过r o n 连接不同的传统 s p 的汇聚接入点( p o p ) ，利用r o n 的选路机划，为用户提供更有弹性和容错能力的互联网业务。 r o n 的第i 个目标是提供框架，以实现管制路径选择的显式路由策略，用柬管 理网络中路径的选择。r o n 很容易对数据包进行识别分类，这样就能够实现可接受 的使用方式，或能够强制性地控制转发速率。 1 1 4 t a p e s t r y t a p e s t r y 是一种有组织的覆盖网川，是可扩展的基础设施。分布式的目标定位和 选路( d o i 固机制使其具有高性能，并可扩展与位置无关的选路，利用局部资源将消 选路( d o l r ) 机制使其具有高性能，并可扩展与位置无关的选路，利用局部资源将消 浙江大学硕士学位论文 息送到最靠近的终点。这样可以提高效率、减少消息时延并提高吞吐量。 1 1 5h a n e t l a b p l a n e t l a b 是一种计算服务“覆盖网络”( o v e r l a y ) ，也是开发全新互联网技术的开 放式全球性测试平台【7 】。这是一个全球性的民间研究计划，旨在用类似于发展l i n u x 开放源代码时的开放合作精神，建立全球分布的研究实验床，连接各处的智能节点， 建立t a p e s t r y 分布式的目标定位和选路( d o l r ) 网络。目前已有1 5 0 所世界一流大学 和行业研究实验室成为p l a n e t l a b 计划的联盟成员，其中包括a t & t 实验室、剑桥 大学、法国电信、l i p 、n e c 实验室、普林斯顿大学和加州大学伯克利分校，连同 巴西、加拿大和中国的国家研究教育网、以及h l 钯m 吐2 机构。 p l a n e t l a b 在全球互联网的主要地区设置了智能节点( 初期10 0 0 个) ，连接骨干 网，构成了分布的虚拟计算环境。这些智能节点可以实现诸如异常检测、鲁棒选路、 储存内容分发( 尽量接近数据源) 、数据融合、提供分散在多个独立域的高生存性存 储等功能。而连接这些智能节点的覆盖网是覆盖在现有的互联网上的，敌便于扩展 演化。 p l a n e t l a b 还将带来诸多新的特性，如永久存储( 即为互联网创建一个“内存”) 。 例如，使数据自现在起到1 0 0 年以后仍然可以完好无损地重新找到，即使当初发布 该数据的计算机已不复存在。此外，这一研究还将影响到未来服务器、路由器和网 络处理器的设计工作。 1 1 6 覆盖层的其它研究 1 内容分发网络 内容分发网络( c o n t e n td i s t r i b u t i o nn e t w o r kc d n ) ，有时也被称作内容传递网 络( c o n t e n td e l i v e r yn e r o ) 【3 】。内容分发和传递一方面可以看作是c d n 的两个 阶段，分发是内容从源分布到c d n 边界节点的过程，传递是用户通过c d n 获取内 容的过程；另一方面，分发和传递可以看作是c d n 的两种不同的实现方式，分发 强调c d n 作为透明的内容承载平台，传递强调c d n 作为内容的提供和服务平台。 c d n 的核心思想是将内容从中心推到边缘靠近用户的地方，这样，不但有效提高了 用户访问内容的性能，而且有效减轻了中心设备和骨干网络的压力。通过c d n ，可 以将内容服务从原来的单中心结构变为分布式的结构。 2 p e e rt op e e r 浙江大学硕士学位论文 对等计算( p e e rt op e e r ，简称p 2 p ) 是一种分布式网络i 9 ，网络的参与者共享他 们所拥有的一部分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ， 这些共享资源需要由网络提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无 需经过中间实体。在此网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ， 又是资源( 服务和内容) 获取者( c l i e n t ) 。 p 2 p 技术的特点体现在以下几个方面：非中心化( d e c e n t r a l i z a t i o n ) ，胃扩展性， 健壮性，高性能价格比，隐私保护和负载均衡。 p 2 p 实际的应用主要体现在以下几个方面：p 2 p 分布式存储，计算能力的共享， p 2 p 应用层组播，i n t e r n e t 间接访问基础结构( i n t e m e ti n d i r e e t i o ni n f r a s t r u c t u r e ) 。 3 应用层组播 端系统组播又称为应用层组播( a p p l i c a t i o n l a y e r m u l t i c a s t ) 。应用层组播网的节点 是组播成员主机，数据路由、复制、转发功能都由成员主机完成，成员主机之间建 立一个叠加在i p 网络之上的、实现组播业务逻辑的功能性网络，称为覆盖i 稠( o v e r l a y n a t w o r k ) ，主机基于自组织算法建立和维护覆盖网。i p 组播的数据沿着物理链路复 制和转发，而应用层组播的数据则在主机实现复制和转发，数据报沿着逻辑链路转 发，多跳逻辑链路可能经过同一条物理链路。 应用层组播思想提出后的短短几年内，多个研究机构开展了应用层组播体系结 构的研究项目，如：e s m ( e n ds y s t e mm u l t i c a s t ) t ”】、y o i d t ”】、s c a t t e r c a s t “、o v e r c a s t ”1 、 a l m i f “】、h m ( h o s tm u l t i c a s t ) 15 1 等。 ( 1 ) e s m e s m 是c m u ( 卡耐基梅隆大学) 开展的一个端系统组播研究项目，是目前为止 最成功的一个项目。2 0 0 0 年，e s m 的研究表明，在端系统中实现组播功能的体系 结构是可行的，它可以支持各组成员在几百范围内、分布稀疏的、较小规模的多方 通信。2 0 0 1 年，通过在因特网中实际运行基于e s m 的视频会议，验证了e s m 采用 的自组织协议可以在动态的、异构的因特网中支持较小规模的视频应用。 ( 2 ) y o i d y o i d 是a c i r i ( a t & tc e n t e rf o ri n t e m e tr e s e a r c ha ti c s o 研究中心在2 0 0 0 年 提出的，基于应用层组播的一整套内容分发的解决方案，包括了应用层组播之上的 可靠、安全、拥塞控制等机制。y m t p ( y o i dm u s c a t t r e ep r o t o c 0 1 ) 是y o i d 体系的 核心，是一种自组织的拓扑管理协议，将主机组织成网状网和共享的组播转发树。 ( 3 ) s c a t t e r c a s t 6 浙江大学硕士学位论文 2 0 0 0 年，b e r k e l e y 大学的e c h a w a e h e 在其博士论文中提出了s c a r e r c a s t 的体 系结构。这是一种基于应用层组播实现因特网大规模广播业务的体系结构。其思想 是在因特网中部署支持广播业务的服务器，称为s c a a e r e a s tp r o x y 节点，应用层组 播将这些服务器组织成一个因特网广播业务的支撑网，支持用户规模巨大的i n t e m e t 广播和软件分发应用。s c a a e r c a s t 体系结构包括应用层组播机制、应用层组播之上 的传输机制以及内容请求的实现机制。g o s s a m e r 是s c a a e r c a s t 体系结构的自组织组 网协议。 1 2 q o s 的研究现状 1 2 1引言 互联网发展的速度和规模，远远出乎二十多年前互联网的先驱们制定t c p ，m 协议时的意料之外，他们从未想过互联网会发展到如此的规模，并且仍在飞速增长。 除了众所周知的弹地址匮乏外，另外一个严重问题就是缺乏服务质量( q u a l i t yo f s e r v i c e ，q o s ) 保障。 目前的i n t e m e t 仅提供尽力而为( b e s t - e f f o as e r v i c e ) 的传送服务，业务量尽快传 送，没有明确的时间和可靠性保障。随着网络多媒体技术的飞速发展，i n t e m e t 上的 多媒体应用层出不穷，如p 电话、视频会议、视频点播f v 0 d ) 、远程教育等多媒体 实时业务、电子商务在i n t e m e t 上传送等。i n t e m e t 己逐步从单一的数据传送网向数 据、语音、图像等多媒体信息的综合传输网演化。这些不同的应用需要有不同的 q o s 要求，q o s 通常用带宽、时延、时延抖动和分组丢失率来衡量。各种应用对服 务质量的需求在迅速增长。 表1 - 1 一些主要应用的业务特性及其q o s 需求 应用 业务特征0 0 s 需求 电子邮件文件 数据量小、批文件的传输容许时延，带宽需求低；尽力而为传送 传输远程终端 h t m l 网页浏览序列小的、突发的文件传输容许适当的延时：带宽需求；变化的；尽 力而为传送 客户服务器 许多小的双向传输对时延、丢失率敏感；带宽需求适当；必 电子商务须可靠传送 基于i p 协议的连续或变化的传送对时延、抖动非常敏感；带宽需求低；需 语音实时音频 要可预计的时延和丢失率 流媒体变化的位置 对时延、抖动非常敏感：带宽需求高：需 要可预计的时延和丢失率 7 浙江大学硕士学位论文 i n t e r n e t 上一些主要应用的业务特征及其q o s 需求如上表1 1 所示 显然，现有的尽力传送服务己无法满足各种应用对网络传输质量的不同要求， 需要i n t e m e t 提供多种服务质量类型的业务。而尽力而为的服务仍将提供给那些只 需要连通性的应用。 服务质量q o s 系指用来表示服务性能之属性的任何组合。为了使其具有价值， 这些属性必须是可提供的、可管理的、可验证和可计费的，而且在使用时它们必须 是始终如一的、可预测的、有的属性甚至是起决定性作用的。为了满足各种用户应 用的需要，构建对i p 最优并具备各种服务质量机制的网络是完全必要的。专线服务、 语音、文件传递、存储转发、交互式视频和广播视频是现有应用的一些例子。 所有这些都需要我们努力去提高网络的服务质量，建立适应现实需要的q o s 模 型。 1 2 2 q o s 的概念 q o s ( q u a l i t yo f s e r v i c e ) 即服务质量，指发送和接收信息的用户之间，以及用 户与传输信息的集成服务网络之间关于信息传输的质量约定。该约定可被解释为服 务提供者与服务用户之间的一份服务契约，即服务提供者承担支持给定的服务质量 层次的义务当且仅当服务用户按照约定的信息流量特征产生数据时。换句话说，服 务质量包括用户要求( u s e rr e q u i r e m e n t ) 和网络集成服务提供者的行为( a c t i v 时) 两个方面。用户要求指用户在因特网上进行多媒体通信时所要求的服务类型以及相 应的传输性能和质量等。集成服务提供者的行为则指因特网针对某一类服务所能提 供和达到的性能与质量。 1 o o s 控制的目标 q o s 控制的目标是为了i n t e m e t 应用提供服务区分和性能保证； 服务区分：是根据不同应用的需求为其提供不同的服务。 性能要求：要解决诸如带宽、丢失、延迟、抖动等性能指标的保证问题。 2 o o s 控制和管理 q o s 控制和管理：是指计算机网络系统采用一定的方法接受用户应用的服务请 求，并保证其q o s 的过程。 q o s 协商：网络系统将用户应用的服务请求映射成一些预先定义的q o s 参数， 8 浙江大学硕士学位论文 进而与系统的有效资源对应起来，通过资源分配和调度，完成用户的应用。 3 q o s 提供机制 q o s 协商分前向和后向两个阶段。前向阶段：一端发起，逐级向下层映射比较， 发送给网络另一端，在另一端，逆向映射到应用层并显示给另一端用户；后向阶段， 发送端根据所得到的q o s 参数和协商情况决定q o s 参数的级别。 1 2 3 o o s 的体系结构 1 综合服务体系结构in t s e r v 在服务层次上，h a t s e r v 分为：尽力而为型服务，质量保证型服务( g u a r a n t e e d s e r v e ) 1 1 6 ，可控负载型服务( c o n t r o l l e d - l o a ds e r v e ) 【1 7 】。 技术层次上，i n t s e r v 依靠资源预留协议r s v p 1 ”提供q o s 协商机制，逐节点 ( h o p b y - h o p ) 地建立或拆除每个数据流的路径状态和资源预留软状态( s o f ts t a t e ) ； 依靠接纳控制( a d m i s s i o nc o n t r 0 1 ) 决定链路或网络节点是否有足够的资源满足用户 的资源预留请求；依靠传输控制( t r a f f i cc o n t r 0 1 ) 将i p 分组分类成不同的传输流， 并根据每个流的状态对分组的传输实施q o s 路由( r o u t i n g ) 传输调度( s c h e d u l i n g ) 等控制。 事实上，资源预留，接纳控制和传输控制是i n t s e r v 的重要基石。 n 综合服务分类 在n t e m e t 的综合服务模型中，将延迟分为两大部分：传输延迟和等待延迟。 网络元素的资源共享可以分为三个层次：链路的共享、协议的共享和服务的共 享。 2 ) 资源预留协议( r s v p ) r s v p 的主要构成元素是控制分组，控制分组参数及其有关格式，控制状态和 预留格式。r s v p 包括两类最基本的控制分组：p a t h ( 控制) 类分组和r s v p ( 预 留) 类分组。r s v p 协议从接收端开始向发送端请求预留资源。 2 区分服务体系结构d if f s e r v d i f f s e r v 的目标在于简单有效，以满足实际应用对可扩展性的要求，其实现途 径是： 9 浙江大学硕士学位论文 1 、简化网络内部节点的服务机制，在内部节点只进行简单的调度转发，而流 状态信息的保存与流监控机制的实现等只在边界节点进行，内部节点是状 态无关的 2 、简化网络内部节点的服务对象，用聚集传输控制，服务对象是流聚集而非 单流，单流信息只在网络边界保存和处理 边界节点根据用户的流规定( p r o f i l e ) 和资源预留信息将进入网络的单流分类、 整形、聚合为不同的流聚集，这种聚集信息存储在每个m 包头的d s 标记域中，内 部节点在调度转发i p 包时根据包头的d s 标记( i ) s c p ) 选择提供特定质量的调度 转发服务，其外特性称为逐点行为。网络边界对单流作分类聚合与网络内部对聚集 流提供特定质量的调度转发服务，这两个过程通过i p 包头内的d s c p 协同起来。 3 多协议标签交换m p l s m p l s 协议的关键是引入了标签( l a b e l ) 的概念【1 9 2 0 1 。一对标记交换路由器 ( l s r ) 必须在标签的数值和意义上一致。m ：p l s 可以支持添加到现有的帧或分组 结构( 如以太网、p p p ) 的标签，也可以利用包含在数据链路层( 如帧中继和删) 中的标签结构。 标签的格式取决于分组封装所在的介质。当一个数据包进入m p l s 网络时，它 首先在标记边缘路由器( l e r ) 处被分配一个标签。报文沿着动态标记交换路径 ( l s p ) 进行转发，路径中的每个l s r 仅仅根据标签内容来做出转发决定。在每一 跳中，l s r 剥离现有的标签，将一个新的标签应用于该报文，并告诉下一跳如何转 发该报文。 1 。2 4 q o s 研究现状 至今为止，人们对q o s 的研究已经取得了很大进展，提出了许多很好的算法和 协议，并且设计和实现了些实验性系统。但是，大部分系统对提供q o s 担保的研 究是将重点主要放在了面向传输模型的网络和服务调度机制上。这些担保实际上并 不是端到端的。他们只是提供端系统访问的网络接口间的q o s 担保。当前的q o s 研究存在的主要问题有以下几个方面： ( 1 ) 已经建立起必要的q o s 概念，但是对q o s 的描述和定义还很不统一，对 集成服务网络的q o s 仍然缺乏全面和严格的定义： ( 2 ) 多媒体q o s 的控制和管理机制还很不一致，不完全，缺乏q o s 保证机制。 1 0 浙江大学硕士学位论文 ( 3 ) 缺乏对集成服务网络q o s 控制框架的研究。 直到目前为止，i n t e r n e t 上所提供的大部分依然是“尽力而为”服务，在这种服 务模型中，所有的数据流公平地竞争网络资源。随着各种着新型网络应用的兴起， 迫切需要在i n t e m e t 中加入q o s 能力。对于我们所研究的q o s 将具有很强的使用价 值。本文研究覆盖层q o s 路由，是属于研究集成服务网络q o s 方面。 1 3 本文主要工作 本文的研究重点是覆盖网络网络拓扑及其覆盖网q o s 路由算法。 本文在对现有q o s 路由、覆盖网路由进行研究的基础上，提出了网络拓扑智能 连接i l 方案和q s r o n 算法。 文章结构如下： 第一章重点介绍了覆盖网络概念、出现原因、发展及其研究现状，并陈述了 覆盖网络最新发展的几个方面。其次介绍了q o s 的概念、分类、体系结构和最新 q o s 相关研究的情况； 第二章首先介绍覆盖网络的作用和覆盖网节点的设置形式。着重描述q o s 路 由算法、设计中的重点难点和评价指标，对经典的几种q o s 路由基础算法进行了介 绍。作为本章重点的覆盖网路由算法，文章首先把它同q o s 路由算法进行了对比， 在这个基础上详细描述了几种典型的覆盖网q o s 路由最新研究算法和覆盖网拓扑 结构；在相关研究中，对与本文核心方案和路由算法相关的各种服务路径研究、拓 扑结构研究和路由算法研究进行了介绍和分析； 第三章主要介绍了两个方面：网络拓扑智能连接i l 方案和q s r o n 算法。 首先介绍覆盖网网络的层次架构和覆盖网的服务模型。通过在分析覆盖网网络 拓扑的过程当中，详细分析已有的r b l c p 路由算法拓扑方案和b m m m 方案的优 缺点，并在改进优缺点的基础上，增进了显性节点和隐性节点的机制，提出了i l 方案。 在综合分析i l 拓扑方案功能机制的基础上，采用d i j k s t r a 算法，把对网络传 输非常重要的带宽、时延、时延抖动、丢失率等q o s 值作为尺度，分别对单个服务 区段进行最佳路径选择和对整个组合服务进行最佳路径选择，提出q s r o n 算法机 制。在算法的最后，把智能连接i l 方案和q s r o n 算法结合起来使用，让服务路由 的效果达到最好。 浙江大学硕士学位论文 第四章第一部分主要是介绍仿真中的拓扑生成，节点生成，服务生成，网络 信息的更新与控制方面的内容；第二部分重点对比了四种方案( q s r o n ，i l ) ， ( q s r o n ，b m m m ) 、( r b l c p ，分层结构) 和( s h o r t e s tw i d e s t ，b m m m ) 。首先 对比三种拓扑方案在运行时间开销方面的优劣，其次对比四种总体方案分别在节点 服务到达率增加的情况下，覆盖路由q o s 满意率、增加动态干扰流、单个服务经过 的智能节点数目h p 1 ，和智能节点间带宽的资源满意度函数f b ( p ，m ) 四种情况 下仿真的曲线图。 第五章对全文进行了总结，并对覆盖网络q o s 路由的未来发展提出展望。 浙江大学硕士学位论文 2 1 覆盖网络 第二章覆盖层q o s 路由 2 1 1 覆盖网络的作用 覆盖网络( o v e r l a yn e t w o r k ，o n ) 采用分布管理模式，在网络上的关键部位 设置智能节点( i n t e l l i g e n t p r o x y ) 。 对于底层网络，用以监视周围网络上的资源分布、带宽利用率、传输延时、路 由走向、流量模式和分布、网络拥塞、中断和故障以及病毒感染流行等情况。智能 节点之间相互交换这些信息，并进一步实现监视和控制，即时做出响应措施，如提 供路由探测选择、消灭病毒以及内容的检索、分类和管理等等。 对于应用层，智能节点的另外一个用途就是支持各种应用服务，例如支持应用 层出现的大规模多媒体服务，各种组合引用服务，提供分层检索能力，进行内容分 发等。智能节点拥有较强的计算能力，它向网络核心注入大量的计算资源。与当今 的互联网不同，覆盖网智能节点不是静态地将应用和数据分配到指定位置的具体设 备中，而是动态分配计算和存储能力，能从整体调控网络资源，这样就可以让网络 性能达到最佳的效果。 2 1 2 覆盖网节点 覆盖服务网络是有一系列专门的覆盖网节点组成，这些节点由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 n t e m e t 服务提供商( i s p ) 的任何支持。它要求终端主机同时和其它多个终端 相连。著名的p 2 p 文件共享系统g n u t e l l a 和基于终端主机的i n t e m e t 组播都是 属于这类网络。有两个问题限制了这类网络的应用：终端节点的低接入带宽和较大 的“最后一英里”传输延迟。大多数终端主机使用c a b l em o d e m 、d s l 或者拨号 浙扛大学硕士学位论文 等低带宽的接入方式接入i n t e m e t ，仅有少部分主机有1 0 10 0m b s 的接入带宽( 不 过随着宽带的普及，这一情况正在得到改善) 。此外，由于终端节点随时可能被打 开或者关闭，所以这类覆盖网络是动态变化的，不能提供非常可靠的服务。 基于固定节点的覆盖网络使用一系列分布于i n t e m e t 上的固定节点来实现覆盖 服务，它通常由第三方服务提供商来维护，第三方服务提供商通过和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 得到一定的保证，内容分送网络就属于这类覆盖网络。这类覆盖网络的优点是能够 提供可靠的服务，缺点是由于覆盖服务节点在搭建覆盖网的时候就已经固定下来 了，增加或减少服务节点比较麻烦，所以网络灵活性比较差。本文采用的覆盖网节 点就是基于固定节点的覆盖网节点。 2 2 q o s 路由 2 2 1 q o s 路由概述 目前网络研究主要通过两个途径提高q o s ，一个是节点控制：另一个是整网或 局部网络控制。节点控制在单节点或单链路完成，主要控制业务对单节点共享资源 的占用，包括共享的链路、缓存区、处理器资源。节点控制主要的策略包括：业务 流整形、业务调度、节点缓冲区管理，整网或局部网络控制通常通过对路由与信令 的控制达到对业务流或业务连接在网络中传输的直接控制，因路由直接关系到网络 性能，所以q o s 路由成为解决q o s 问题的一项关键技术。 q o s 路由的