（计算机软件与理论专业论文）基于承载网的服务放置与服务选择问题的研究.pdf

摘要 摘要 随着各种覆盖网系统规模和数量的剧增，它们独立探测底层网络性能对网络 资源造成的浪费，以及独自选路导致的路由抖动和不公平性等问题日渐受到人们 的重视。 承载网( u n d e r l a y ) 是为解决此问题而提出的一种新的网络架构，服务的放置 和选择是其支撑覆盖网服务的两个关键问题，本文基于u n d e r l a y 环境，围绕这两 个问题展开了一些工作，主要有： ( 1 ) 首次在u n d e r l a y 中引入了服务放置与服务选择问题。 对两个问题的已有研究工作进行了较全面的介绍，并首次对u n d e r l a y 引入 了服务放置与服务选择问题，分析了两个问题的联系。 ( 2 ) 设计了u n d e r l a y 中服务放置的最大流算法。 为u n d e r l a y 中的服务放置问题引入了流量效应这一概念，围绕此概念设计 了增量式部署服务器的贪婪算法，即最大流算法。 ( 3 ) 设计了u n d e r l a y 中服务选择的集中式和分布式方案。 结合u n d e r l a y 中的o o s 选路机制设计了与o o s 路由集成的服务选择方案， 给出了适合不同场景的集中和分布式管理的设计。 ( 4 ) 对以上研究进行了仿真实验。 设计并完成了最大流算法的仿真实验，根据实验结果对算法进行了比较评 价。 关键词；覆盖网承载网服务放置服务选择最大流 l a b s t r a c t a b s t r a c t a st h es c a l ea n dq u a n t i t yo fv a r i o u so v e r l a ys y s t e m sb e c o m el a r g e r , t h ew a s t eo f n e t w o r kr e s o u r c ec a u s e db yt h e i rs e p a r a t e l yt r a c i n gt h ep e r f o r m a n c eo fu n d e r l a y n e t w o r k , a sw e l la sr o l l t ef l a p p i n ga n du n f a i r n e s sc a u s e db yt h d rs e p a r a t e l yr o u t i n g a r cg i v e nm o r ea n dm o r ea t t e n t i o n u n d e r l a yn e t w o r ki san e wi n f r a s t r u c t u r et os o l v et h ea b o v ep r o b l e m s s e r v i c e d e p l o y m e n ta n ds e l e c t i o na r ec r u c i a lf o ru n d e r l a yt os u p p o r to v e r l a ya p p l i c a t i o n s t h e p a p e r c e l l t e r 5o nt h e s et w op r o b l e m s t h em a i n w o r ki sa sf o l l o w s ： ( 1 ) i n t r o d u c et h ep r o b l e mo f r v e fp l a c e m e n ta n ds e r v i c es e l e c t i o nt o u n d e r l a yn e t w o r kf o rt h ef i r s tt i m e t h ep a p e rp r e s e n t e dt h es u r v e yf o rt h e s et w op r o b l e m si nd e t a i l b e s i d e s ，t h e a u t h o ra n a l y z e dt h er e l a t i o n s h i pb e t w e e nt w op r o b l e m sa n di n t r o d u c e dt h e s ep r o b l e m s t ou n d e r l a yn e t w o r kf o rt h ef i r s tt i m e ( 2 ) d e s i g nt h em a x - f l o ws e w e rp l a c e m e n ta l g o r i t h m b a s e do nu n d e r l a y n e t w o r k t h ep a p e ri n t r o d u c e dt h ec o n c e p to ft r a f f i ce f f e c tf o rt h es e r v e rp l a c e m e n t p r o b l e m , b a s e do nw h i c h ，w ed e s i g n e dg r e e d ya l g o r i t h m ，i e m a x f l o wa l g o r i t h m , w h i c hc 觚i n c m e n t a i l yd e p i o ys e r v e r s ( 3 ) s t u d ya n dd e s i g nc e n t r a l i z e da n dd e c e n t r a l i z e ds e r v i c el o c a t i o ns c h e m e w ed e s i g n e das e r v i c es e l e c t i o nm e c h a n i s mw h i c hi ni n t e g r a t e dw i t hq o sr o u t i n g i n u n d e r l a yn e t w o r lt h em e c h a m s mc a nb e u s e di ne i t h e rc e n t r a l i z e do r d e c e n t r a l i z e dw a y , d e p e n d i n go nt h ec h a r a c t e r i s t i co fs e r v i c e sa n dt h en e t w o r k ( 4 ) s i m u l a t i o na n de x p e r i m e n t i no r d e rt oe v a l u a t eo u ra l g o r i t h m s ，w ed e s i g n e de x p e r i m e n t st oe m u l a t et h e a l g o r i t h m s p r o c e d u r e t h ep a p e ra l s op r e s e n t e dt h ed e s i g na n dt h er e s u l to fa l lt h e e x p e r i m e n t s k e y w o r d s ： o v e r l a yn e t w o r ku n d e r l a yn e t w o r k s e r v i c e s e r v e rp l a c e m e n t s e r v i c e s e r v e rs e l e c t i o nm a xf l o w 原创性声明 本人郑重声明：本人所呈交的学位论文，是在导师的指导下独立 进行研究所取得的成果。学位论文中凡引用他人已经发表或未发 表的成果、数据、观点等，均已明确注明出处。除文中已经注明 引用的内容外，不包含任何其他个人或集体已经发表或撰写过的科研 成果。对本文的研究成果做出重要贡献的个人和集体，均已在文中以 明确方式标明。 本声明的法律责任由本人承担。 论文作者签名：羔播 日 靼 关于学位论文使用授权的声明 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属兰州大学。本人完全了解兰州大学有关保存、使用学位论文的规定， 同意学校保存或向国家有关部门或机构送交论文的纸质版和电子版， 允许论文被查阅和借阅；本人授权兰州大学可以将本学位论文的全部 或部分内容编入有关数据库进行检索，可以采用任何复制手段保存和 汇编本学位论文。本人离校后发表、使用学位论文或与该论文直接相 关的学术论文或成果时，第一署名单位仍然为兰州大学。 保密论文在解密后应遵守此规定。 论文作者签名：滥导师签名：丝臣兰堡日 期： 第1 章引言 1 1 选题意义和背景 第1 章引言 当前越来越多的复杂应用对i n t e m e t 的传输服务提出了越来越高的要求，这些 要求对于以提供尽力发送( b e s te f f o a ) 的单播传输服务为主的i n t e m e t 来说，也 越来越难以满足。覆盖网络( o 、，c r l a v n e t w o r k ，简称o v e r l a y ) 是人们为了解决 传统的i n t e m e t 难以在网络层提供的服务质量支持、资源共享和组播等服务而提出 的一种新思路，包括路由覆盖网络【1 】【2 1 、内容传送网络【3 】【4 1 、应用层组播【5 h 1 5 1 、 p 2 p 等各种覆盖网络系统。由于o v e r l a y 网络不需要对现有的i p 传输网络进行任何 修改，因此能够针对具体的服务需求迅速部署。c a c h e l o g i c 在2 0 0 4 年上半年对全 球i n t e r a c t 的测量数据i l o j 表明，p 2 p 应用所占有的网络带宽已经超过了任何其它一 种应用。 为数不多的覆盖网络系统对i n t e m e t 的影响不大，但随着各种覆盖网络系统的 规模和数量的剧增，它们各自独立探测底层网络性能对网络资源的浪费l l “，以 及独自选路造成的路由抖动和不公平性l l 叫等问题日渐受到人们的重视。 承载网( u n d e r l a yn e t w o r k ，简称u n d e r l a y ) 就是为解决上述问题而提出的 一种新的网络架构，它位于物理传输网络和覆盖网络之间。向下和底层网络融合， 通过对其底层的拓扑发现和虚链路测量，作为u n d e r l a y 路由选择的依据；向上可 以为各种应用提供支持服务质量路由、流量负载均衡等服务的接口，供应用层网 络( 覆盖网络) 使用。u n d e r l a y 是为整合和更好的服务于各种具有专门应用的覆 盖网络而提出的一种通用的网络架构，因而在传统网络中基于特定服务的服务放 置及服务选择等问题对当前的网络架构又提出了新的需求。 传统网络中对服务放置问题和服务选择问题的研究比较广泛。对于服务放置 问题很多是形式化描述为k - 中点( k - m e d i a n ) 或设施放置( f a c i l i t vl o c a t i o n ) 问题， 或者两种问题的变形，以最小化部署开销为目标，利用线性规划的拉格朗日松弛 来解决。因为这些问题本身是n p 难的，而且上述方法也没有较好的近似算法， 最重要的是已有方案和u n d e r l a y d 0 流量分配和负载平衡等目标难以统一。此外， u n d e r l a y 为支持覆盏网的灵活性和高适应性，需要在承载层实现q o s 路由，并在 服务选择的同时完成o o s 路径的选择，这对传统服务选择又提出了新的需求。 综上，以更灵活和优化的方式承载各类服务是u n d e r l a y 提出的初衷，服务的 放置和选择作为这其中的主要环节，对服务的性能和网络的性能的优化都有重要 的意义。本文正是在u n d e r l a y 的环境下解决此类问题的一次尝试。 第1 章引言 1 2 论文的主要工作 这篇论文基于u n d e r l a y 两络，对服务放置问题和服务选择问题进行了研究， 主要工作有： ( 1 ) 首次将服务放置与服务选择问题引入到u n d e r l a y 环境中。 全面介绍了静态、动态服务放置问题和服务选择闯题的已有研究工作，分析 了两者之间的联系，并首次将它们引入u n d e r l a y 。 ( 2 ) 提出了服务放置的最大流算法。 根据u n d e r l a y 承载服务的特点，为u n d e r l a y 中的服务放置问题引入了流量 效应的概念，围绕这一概念设计了增量式部署服务器的贪婪算法，即最大流算法。 论文对算法思想和算法步骤进行了详细的阐述和介绍，并给出了考虑用户请求动 态性的初步方案。 ( 3 ) 设计了u n d e r l a y 中的服务选择方案。 结合u n d e r l a y 中的q o s 选路机制，设计了与o o s 路由集成的服务选择方案， 给出了适合不同场景下的集中式和分布式方案。其中，对集中式方案详细论述了 其设计思想和工作流程，对分布式方案重点介绍了其多集中节点的选择和交互机 制。 ( 4 ) 对以上研究进行了仿真实验。 描述了最大流算法仿真实验的设计，根据实验结果对提出的算法进行了评 价。还比较了不同的选择算法对服务性能的影响。 1 3 论文的组织结构 论文共分6 个章节： 第1 章为引言，介绍了课题意义和背景，阐述了论文的主要工作。 第2 章概述了覆盖网络的相关研究现状，介绍了和本文工作相关的o o s 路 由、任意播等内容。 第3 章对服务放置问题的已有研究( 包括静态和动态的情形) 和服务选择问 题进行了综述，引入了u n d e r l a y 需要承载服务的两个重要问题：即服务放置服 务选择问题。 第4 章提出了在u n d e r l a y 中放置服务的最大流算法，详细描述了算法思想、 过程和仿真方法，并对所提出的算法与已有的类似算法进行了性能比较。最后就 动态情形下的放置问题提出了初步解决方案。 第5 章提出了在u n d e r l a y 中与q o s 路由集成的服务选择方案，给出了适合 2 第1 章引言 不同场景的集中与分布式管理的设计。 第6 章对论文工作进行总结，并列出了下一步的工作。 3 第2 章相关工作 第2 章相关工作 本章介绍了与论文内容相关的国内外的研究现状。其中：o 、r e r l a y 网络和 u n d e r l a y 网络的已有研究成果是本论文研究的起点；u n d e r l a y 网络为了更好地提 供数据传输服务，需要以o o s 路由的已有研究工作为基础；而任意播在应用层 的推广与o v e r l a y 网络中的服务选择有很相似的特点。以下三节分别对上述三部 分内容进行了概述。 2 1 o v e r l a y 网络概述 应用层网络又称覆盖网络，它的基本含义是在现有的i n t e r n e t 传输网络之上构 建一个完全位于应用层的网络系统。利用覆盖网络，可以在不需修改已存在的软 件协议和网络的底层结构基础上而快速地添加新的网络功能。 o s i 模型和i n t e r a e t 模型都是具有层次结构的，应用层位于层次结构的最高 层，它利用传输层提供的服务完成相应的应用功能。但随着应用的模式越来越复 杂，这种只依赖于传输层的应用层已经不能满足需要了。例如，目前出现的对等 网络( p e e r - t o p e e r ，p 2 p ) 体系结构，在一个对等网络中，往往有数千台计算机 既是服务器又是客户机。此时，对等网络本身就构成了一个覆盖网络，对等体需 要自己去进行服务器发现，选择到其他对等体的路由等，因为这些功能是和对等 网络提供的服务模式相关的，因此不能放到传输层完成。 又例如，由于目前的i n t e r n e t 的传输网络还不能完全支持组播，参加组播的计 算机可以自己构成一个覆盖网络，然后在应用层维护组播树的结构并由应用节点 参与进行组播转发。 目前发展比较迅速和应用比较广泛的应用层网络系统有路由覆盖网络、对等 网络、应用层组播和内容传送网络( 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 ) 等。 2 1 1 路由覆盖网络 路由覆盖网络中比较有代表性的有弹性覆盖网络和服务覆盖网络。 弹性覆盖网络r o n 1 9 】是一种分布式o v e r l a y 网络体系结构，它可以便分布 式应用检测到路径的失效和周期性的性能降低现象并能够迅速从中恢复( 恢复时 问少于2 0 秒) 。r o n 节点可以位于i n t e r a c t 的任意位置，它们形成了一个应用层 的o v e r l a y 网络并且相互协作完成分组转发。每个r o n 节点都监控它和其它节 4 第2 章相关工作 点之间的i n t e r n e t 路径的质量并使用该信息进行路由选择。 服务覆盖网络s o n 2 0 i 也是一种位于应用层的o v e r l a y 网络。s o n 通过双向 的服务级别合约( s e r v i c el e v e l a g r e e m e n t ，s l a ) 从各个i s p 处购买带宽( 需要 满足某些服务质量要求) ，并以这种方式在现有的i n t e m e t 上构造一个端到端的应 用层网络并提供增值服务。s o n 引入了一种新的级别的流量聚集一服务聚集 ( s e r v i c e a g g r e g a t e ) 。低层传输网络只需要根据所属s o n 的不同把同一个s o n 的流量聚集在一起并根据和s o n 达成的s l a 对该聚集流量进行控制，而具体的 端到端的服务质量控制则由s o n 自己完成，这样s o n 可以根据不同的应用采用 不同的服务质量管理方法。 2 1 2 对等网络 在目前的i n t e r n e t 中，p 2 p 文件共享的应用越来越多，用户数量急剧增长， 其代表有b i t t o r r e n t 2 、e d o n k e y 2 2 1 、f a s t t r a c k 2 3 1 、g n u t e l l a 2 4 1 等。在这样的系统 中，数据保存在用户的计算机( 称之为对等节点) 中，而不像以往的客户服务 器模式那样把数据存放在集中的服务器上。在f 2 p 网络中，数据在对等节点之间 直接传递。随着p 2 p 网络系统规模的增长，系统的可扩展性成为迫切需要解决的 问题也成为了研究的热点。研究人员已经提出了多种具有良好可扩展性的分布式 哈希查找系统并基于这些系统构造了新一代的文件共享软件。 c h o r d l 2 5 1 实现了这样一种操作：给定一个关键字，将关键字映射到某个节点。 如果给f 2 p 网络应用的每个数据都分配一个关键字，那么p 2 p 网络中的数据查 找问题就可以用c h o r d 很容易地解决。c h o r d 用相容哈希函数为每个节点和关键 字分配标识符，每个关键字保存在它的后继节点中，而相容哈希的一个特点就是 当节点加入或者离开网络时对网络带来的冲击可以达到最小。c h o r d 的路由查找 过程是向目的地不断逼近的过程，每个节点将查询请求转发到自己的邻居表中距 离目的地最近的那个节点。在由个节点组成的网络中，每个节点只需维护其它 d ( l o g ) 个节点的信息，每次查找只需要d ( 1 0 9 ) 条消息。当节点加入或者离 开网络时，c h o r d 需要更新路由信息，每次加入或者离开需要传递d l 0 9 2 n ) 条 信息。 内容访问网络c a n 【2 6 可以在i n t e m e t 规模的大型p 2 p 网络上提供类似哈希 表的功能，具有可扩展、容错和完全自组织等特点。c a n 基于虚拟的d 维笛卡 儿坐标空间实现其数据组织和查找功能。整个坐标空间动态地分配给系统中的所 有节点，每个节点都拥有独立的互补相交的一块区域，因而c a n 类似于一张大 的哈希表。在d 维坐标空间中，当两个区域在d 一1 维上都覆盖相同的跨度而在另 一维上相互邻接，则称这两个区域邻接。c a n 在进行路由时，计算目的点在d 第2 章相关工作 维笛卡儿坐标空间的坐标，然后寻找从发起请求的点到目的点的一条路径。每个 节点朝着目标节点的方向把请求转发给自己的相邻节点。 在p a s t r y i 韧网络中，当给定一条消息和一个关键字时，p a s t r y 节点会把这条 消息路由到在当前所有的p a s t r y 节点中节点号和关键字最接近的那个节点。 p a s t r y 考虑了网络的位置信息，其目标是使消息传递的距离最短，而距离采用的 是类似口路由的跳数的标量度量。p a s t r y 在路由时，每个节点把消息发送给节 点号和关键字之间的共同前缀至少比现在节点长一个数位的节点。在某些情况 下，会出现路由表对应表项为空，或者路由表表项对应的节点不可达。这时候消 息会被转发给共同前缀一样长的节点，但是该节点和当前节点相比，其节点号从 数值上将更接近关键字。由于路由的每一步和上一步相比都向目标节点前进了一 步，因此路由过程是收敛的。对于个节点构成的p a s t r y 网络，路由过程的复 杂度是d ( k g n ) 。 2 1 3 应用层组播 早在1 9 8 8 年d e e r i n g 就提出了口组播机制，其主要通过在i n t e m e t 单播框架 下进行扩展，通过路由器实现主要的功能。但由于在具体实施过程中口组播面 临很多问题，促使人们重新考虑组播的有效解决方案，应用层组播便应运而生了。 应用层组播的基本思想是屏蔽底层物理网络的拓扑细节，将组成员节点直接自组 织成一个逻辑上的覆盖网络，在应用层提供组播路由协议来构建和维护该组播网 络，为数据传输提供高效可靠的服务。按不同的构造策略可将应用层组播分为以 下几类：基于m e s h 网的应用层组播、基于树的应用层组播和基于隐含组播拓扑 结构的应用层组播。 a ) 缸播( b ) 口轩l 籀( c ) 橙晶纨插 图2 1 单播、口组擂、覆盖组播示意图 在基于m e s h 网的策略中组成员首先组成一个应用层的覆盖网络。每个成员 都要参加分布式的路由协议，计算自己到其他节点的转发路径。可以采用被许多 m 组播路由协议采用的反向路径转发机制创建面向源的组播树，如n 孤a d a 【5 】、 6 第2 章相关工作 s c a t t c r c a s t e 等，适应于小组播组的应用时效率很高，但可扩展性较差。 在基于树的策略中直接采用分布式算法构造数据转发树。然后，每个组成员 都主动发现一些并不是自己邻居节点的组播树中的其他节点并和这些节点保持 控制连接。在基于树的策略中，数据转发树加上这些额外的连接就构成了控制拓 扑。代表有y o i d l 7 】，h o s tm u l t i c a s t 8 1 ，a 瑚l 【伽，s w i t c h - - t r e e s 1 0 l 等。基于树的协 议不适合对延迟要求高的实时应用，但是可以用于实现高带宽需求的数据传输。 当使用面向大规模对等网络的路由机制创建带有某些特殊属性的控制拓扑 时，在控制拓扑中就隐含定义了数据转发路径。此时可以采用基于隐含组播转发 拓扑结构的策略。如层次化控制拓扑结构的n i c e 1 1 j ，c a n 向组播应用的扩展 c a n - - m u l t i c a s t 1 2 1 ，基于哈希路e h 和查找机制p a s t r y 的应用层组播协议s c r i b c t 3 l ， 基于t a p e s t r y 路由机制的应用层组播协议b a y e u x p 4 | ，以及d e l a u n a y t r i a n g u l a t i o n s 1 5 l 等等。基于隐含组播拓扑结构的协议可以用于规模非常大的组播 应用，而且同时适应延迟敏感和高带宽的应用。 2 1 4 内容传送网络 内容传送是当前比较热门的话题之一，内容传送网络提供了一种传输内容的 新型体系结构。因为传统的缓存技术只针对静态的h t m l 文件和图片等较小的 文件，而随着多媒体技术的不断发展，图像、音频、视频服务所占的比重越来越 大，如果采用传统得中央网站式内容传送，必然导致主干网带宽浪费和响应时间 过长等问题。c d n 就是这样一种将内容和服务动态地，分布式地缓存在网络不 同地理位置上去的覆盖网络体系结构。c d n 的基本思想是引导用户就近访问， 全局流量负载均衡。 c d n 与缓存技术不同的是，i s p 用缓存代理来存储最近或者最经常被访问的 内容，是作为一种本地策略而实施的；而w e b 服务器通过c d n 技术来存储网络 管理员指定的内容，特别的，c d n 可专门用在一些涉及安全的内容，流媒体， 动态内容等一些不可以被缓存的存储和访问。 c d n 的功能主要有以下几个方面： 请求重定向和内容传送服务：将用户请求定位到较合适的最近的服务器副本 上去，通过避免拥塞的机制克服突发流量或s l a s h d o t 效应。 内容外购和分发服务：将内容复制或者缓存到分散的副本服务器上去，利用 代理服务器代替原始服务器。 内容协商服务：以满足具有特定需求的个体或群体用户。 管理服务：管理网络部件，对内容的使用计价，监测以及报告。 通过缓存和将内容复制到按一定策略放置的各个备份服务器上去等方法， 7 第2 章相关工作 c d n 可提供性能更高的服务来解决w e b 内容访问时出现的突发流量或 s l a s h d o t 效应，将用户的请求重定向到距离他们最近的服务器副本上去，从而减 少请求的响应时间。 c d n 的体系结构包括以下三个组成部分：内容提供商，c d n 服务提供商， 端用户。内容分发网络服务商可以和网络服务提供商p ) 合作，在i s p 的设施中 配置它们基于软件的内容分发服务器。目前较为常见的商业性c d n 网络有 a k 锄a i 【3 1 、d 蝤t a li s l a n d 4 1 、i n k t o m i 等公司。 2 1 5o v e r l a y 与u n d e r l a y 网络 o v e r l a y 越来越多的被用来部署一些难以直接在底层物理网络上难以实现直 接部署的服务，上面所述的各类0 e r l a y 网络均被用来实现某一种特定的路由功 能，o v c l l a y 提出的初衷就是在一个i n t e r n e t 上的小规模范围内，通过构建一个专 用的网络来提供性能更高的服务，因此所有的这些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 v e r l a y 的普通应用 造成影响，此外还需考虑这些o v e r l a y 之间的自私路由问题【1 8 】导致网络的整体的 性能下降和路由不公平现象。 【1 7 提出了在o v e r l a y 网络和底层i n t e m e t 间插入一个u n d e r l a y 路由层， o v e r l a y 通过请求u n d e r l a y 做出特定应用的路由决策，而由u n d e r l a y 层负责对底 层i n t e m e t 的网络状态探测和信息聚集。各类o v e r l a y 系统都需要有拓扑发现和 维护之类的机制，如果这些o v e r l a y 通用的需求可以通过共享一个u n d e r l a y 网络 来实现，在u n d e r l a y 层实现底层网络状态探测，为上层o 、，c r l a y 提供拓扑发现和 路由选择服务就能很好的解决以上问题，也使得o v e r l a y 网络更具可扩展性。 2 2o o s 路由 2 2 。1q o s 路由概述 当前的i n t e r n e t 主要提供尽力发送服务，网络层不区分用户业务的种类，而 将网络资源( 包括链路带宽、交换节点c i u 资源、队列等) 公平的提供给各类 业务，以最大速度尽力转发数据分组作为单一目标，在分组丢失概率、延迟等方 8 第2 章相关工作 面公平的对待各类业务。这种基于尽力发送体系结构的传统网络是无连接、与状 态无关的，既不能支持资源预留，也不能预测传输参数，甚至还可能产生多媒体 实时业务所不希望的乱序现象等，因此面向服务质量保证的网络体系结构也应运 而生。 定义2 1服务质量( q o s ) 服务质量( q u a l i t yo fs e r v i c e ，o o s ) 是网络传输业务流时，业务流对网络服 务的需求集合，其中业务流是指与特定q o s 相关的从源到目的地的分组流l 勰l 。 也就是说，q o s 是应用业务对网络传输服务所提出的一组可度量的要求，主 要包括带宽、端到端延迟、分组丢失率、抖动、花费的代价等，网络传输相应的 数据业务时，必须满足这组要求。 o o s 需求可以通过一个限制集来描述，其中的限制可以是链路限制、路径限 制或树限制【2 9 1 。链路限制定义了从源到目的地的每一条链路的限制，如带宽限制； 路径限制定义了从源到目的地的一条路径上端到端o o s 需求，如延迟；树限制 定义了对组播中使用的整个组播树的限制，例如对组播树延迟的限制是对树中从 源到所有目的地的路径中最大延迟的限制。 定义2 2可行路径( 可行树) 可行路径( 可行树) 是网络中从源到( 所有) 目标节点的一条路径( 组播树) ， 并且该路径( 树) 具有足够的尚未分配的资源，能够提供特定连接的q o s 需求。 定义2 3服务质量路由( q o s r ) q o s r 是一种基于数据流q o s 请求和网络可用资源进行路由的机制网。或 者 q o s r 是一种动态路由协议，并且在其路径选择标准里可能包含可用带宽、链路 和端到端路径利用率、资源消费量、延迟、跳数以及抖动等q u s 参数【卿。 当前i n t e m e t 的主要路由协议包括域内路由协议o s p f ( o p e ns h o r t e s tp a t h f i r s t ) 、r i p ( r o u t i n gi n f o r m a t i o np r o t o c 0 1 ) 和域间路由协议b g p ( b o r d e rg a t e w a y p r o t o c 0 1 ) 等。这些都是“尽力发送”的路由协议，选择路由时通常只使用单一优 化目标( 如跳数或花费) ，因此在某种意义上所有的业务都是基于“最短路径” 的。即便源节点到目的节点之间存在更好的“路径”，只要不是最短路径也不会 投入使用，这样这种路由机制就会导致在某些链路空闲的情况下而另外在一些链 路上造成拥塞。q o s r 路由就是将传统的最短路径变为一条更好的路径，其主要 目标包括以下两点【冽： 为每一个接纳的o o s 业务连接请求，找到满足其q o s 要求的可行路径( 组 播树) ；优化全局资源利用率，平衡网络负载，从而最大化网络接受其他q o s 请 求的能力。 9 第2 章相关工作 根据计算可行路径的时刻，o o s r 可以分为预计算和在线计算两种。预计算 ( p r e - c o m p u t a t i o n ) 是一个后台进程根据网络状态信息构造路由表，而在o o s 请求时，通过快速查找路由表确定可行路径的方式f 3 1 j 。在线计算是o o s 请求到 达时，根据状态信息计算可行路径的方式，因而不需要事先构造路由表。 o v e r l a y 网络以其灵活性和高适应性提供了将q o s 机制融入到现有i n t e m e t 网络的一种方法。通过在i n t e m e t 中部署一定数量的o v e r l a y 路由节点，路由节 点之间构成o v e r l a y 路由网络，然后在该路由网络中进行服务质量路由，这样既 能为端用户提供q o s 路由服务，又不需要对已有的i n t e m e t 路由器进行任何的修 改 为完成q o s r 的两个目标，q o s r 的主要内容包括两方面：( 1 ) 测量、收集并 维护网络状态信息；( 2 ) 根据维护的网络状态信息计算优化的可行路径( 树) 。 第一个内容涉及到本地状态的获取和状态信息传播的问题；后一方面主要是 q o s r 算法，而各种算法往往需要依据节点所维护的状态信息。 2 2 2 状态信息交互 在不同节点之间采用链路状态协议或距离向量协议交互，使每个节点获取 ( 聚集的) 全局状态。链路状态协议直接将本地的链路状态( 或其改变量) 发送 给所有的邻居，同时将收到的这类信息扩散给其他节点，从而实现每个节点都能 获取( 聚集的) 全局状态，并据此用d i j k s t r a 算法计算最短路径。与链路状态协 议不同，距离向量协议接收到这类信息后，首先使用距离向量算法( 即 b e l l m a n - f o r d 算法) ，为每一个可能的目的网络形成一个距离向量，然后将这些 距离向量发送给所有的邻居。距离向量的计算过程实际上就是对全局状态的压 缩，从而在一定程度上减小了计算可行路径的复杂程度。与链路状态的聚集过程 类似，计算距离向量也带来了信息丢失的问题，尤其是链路具有多种约束条件时， 这个问题更为突出 按照状态的交互间隔，协议交互可以分为以下几个方式：( 1 ) 周期方式：协 议周期性广播网络状态信息的方式。基于这种方式的路由协议设计和实现较为简 单；但是周期取值过大会造成每个节点所维护的信息过于陈旧，而周期过j , l t j 重 复传送大量相同信息造成通信开销大，浪费带宽。因此周期广播的方式只在面向 小型的路由协议中使用，例如r i p 2 规定，每个节点每3 0 秒广播一次该节点维护 的全局状态。( 2 ) 触发方式：由网络状态的变化而触发协议广播网络状态信息的 方式。这种方式通常采用一个门限值，例如与上次广播时相比，链路带宽的变化 超过2 0 时，触发新的一次广播。为了防止网络状态变化剧烈而引发的路由抖动， 通常需要设置最小保持时间间隔，以保证连续两次广播的时间间隔不能过小。( 3 ) 1 0 第2 章相关工作 触发和周期结合的方式。 2 2 3 三类路由策略 通过路由协议交互，每个节点收集到适当的网络状态信息后，需要据此采用 一种相应的路由策略实现路由。根据网络中每个节点所维护的信息种类和进行路 由的具体位置，路由策略可以分为源路由、分布式路由和层次化路由三类。 定义2 4 源路由 每个源节点收集和维护完整的全局状态，只在发送数据的源节点计算从源节 点到目标节点的完整的可行路径。为建立连接，源节点通过控制信息通知这条路 径上的其他节点如何进行路由。这种路由策略称为源路由。 源路由的概念和算法非常简单，易于实现和评价。源节点的集中式计算能 够避免分布式的各种缺点，如网络状态数据不一致所造成的死锁和回路等问题。 但由于每个可能的源节点都需要收集和维护完整的全局状态，也带来了以下几个 问题：( 1 ) 由于源路由需要通过链路状态交互，因而维护全局状态的开销很大； ( 2 ) 源节点根据全局状态计算可行路径，时间和空间开销很大；( 3 ) 源节点所 维护的全局状态，其陈旧性对路由的性能影响很大。随着网络规模扩大，以上三 个问题越发突出。考虑到可扩展性，在支持o o s 的大型网络中直接使用这种源 路由的策略是不可行的。 定义2 5 分布式路由 每个节点收集和维护一定的网络状态信息，网络中的多个不同节点基于这些 信息进行独立的分布式计算，从而获得可行路径的路由策略称为分布式路由。 分布式路由中，每个节点并不知道完整的可行路径，甚至只知道可行路径 中的下一跳( n e x t h o p ) 节点，至于下一跳节点再往后的路径则由下一跳节点计 算和决定。当前i n t e r a c t 的路由策略就是这种分布式路由。分布式路由将计算分 散在各个中间节点，减小了计算复杂程度，甚至有的算法只要求节点具有本地状 态，因而具有较好的可扩展性。但是分布式处理较为复杂，尤其是在o o s 多约 束时很难设计良好的启发式算法。此外，由于各个节点依靠本地维护的全局信息 独立计算可行路径，因此由于信息不一致可能造成回路，这就需要额外的回路检 测算法。 定义2 6 层次化路由 网络中的节点通过聚集形成多层次的拓扑结构，每个物理节点保存聚集状 态。为建立连接，源节点沿着可行路径发送控制信息，当一个组的边界节点作为 代表这个组的逻辑节点而收到控制信息时，使用源路由的方式将可行路径扩展， 直到通过这个组。这种路由策略称为层次化路由。 1 1 第2 章相关工作 层次化路由是为解决源路由可扩展性问题而提出的。o s f f 协议通过区域 ( a r e a ) 实现了两层的路由结构，在区域内部交互链路状态，区域之间交互距离 向量。p n n i 通过任意多层的状态聚集，实现了层次化路由。与源路由相比，层 次化路由以对数缩减了节点之间交互的信息和每个节点的计算复杂度，具有良好 的可扩展性。但由于聚集状态导致信息丢失，给q o s r 带来了巨大的反面作用。 目前，如何聚集状态信息还是一个有待进一步研究的问题。 2 3 任意播概述 a n y c a s t ( 任意播) 一词最早出现在1 9 9 3 年的r f c l 5 4 6 1 3 2 1 中，最初定义 a n y e a s t 地址来标识一组提供某种服务的主机，是一个目的地址的集合。与我们 熟知的单播和组播地址一样，a n y c a s t 也是口的一种通信模式，发送到一个 a n y c a s t 地址的数据报将会被投递到这组主机中的任意一台去，在传统意义上， 是一种无状态的、尽力而为的网络层投递方式。i p v 6 协议正式接纳了a n y c a s t 服务，定义了a n y c a s t 地址。 现在我们提起a n y c a s t 已不仅限于作为一种m 地址的定义，a n y e a s t 作为一 种可以解决在一组成员中选择一个成员的通信方式已经广泛地应用到很多领域 中了。如“最优”服务器的选择，主机自动配置等等，随着网络中各种新应用的 不断涌现，对a n y c a s t 也会提出更多的需求。当前对a n y e a s t 的研究主要集中在 图2 2 网络层a n y c a s t 示意图 体系结构、路由算法、服务选择策略等方面。其中应用层a n y c a s t 在体系结构的 研究中是一个热点，而服务选择可以很自然的与应用层a n y c a s t 联系起来。 第3 章服务放置与服务选择 第3 章服务放置与服务选择 作为支撑覆盖网服务的一个网络体系结构，u n d e r l a y 除了提供更灵活的路由 外，另一个主要职能是为各类应用部署和选择服务。本章首先对已有服务放置与 服务选择问题的研究进展进行了综述性的介绍，然后提出了u n d e r l a y 环境下需 要解决的这两个实际问题及它们之间的联系。 3 1 服务放置问题 3 1 1 静态服务放置问题 设施放置问题( 选址问题) 作为一个古老的问题，在城市规划，物流问题以 及c d n 中都有涉及。如考虑城市中某些公共服务设施如何部署，才能使得用户更 快捷便利的使用，此问题可以定义为最小化距离最远的用户到服务设施的延迟问 题；又如物流问题中，需要对多个售货点配货，配货中心如何选址，才使得到所 有售货点的路径距离之和最短。类似的问题也存在于计算机网络领域，在c d n 中， 服务器的放置策略直接影响了用户请求的响应速率和系统的负载均衡状况。 此类问题常用到的图论模型有以下两种： ( 1 ) k - 中位问题： 给定图g = ( g e ) 以及，；y 的节点v ，对某服务的需求s 以) ，求解集合y 的一个子集矿，满足iv l = k ，矿中的元素作为放置设施的中位点，目标是使得 服务的开销c ( gs 七) = s “y n ，珊 ) ) 最小化。 艚 其中假定每个客户端选择距离自己最近的服务器，用册o ；) 表示y 中距离节 点u 最近的中位点，d ，小“) ) 表示u 距离其选择的中位点之间的距离( 可以是 延迟，跳数等) 。 ( 2 ) 设旌选址问题： 与k _ 中位问题类似，不同的是：设旅选址问题中没有服务器个数k 的限制， 即不考虑部署服务器的个数上限，但是对特定位置处部署一个服务器需引入一个 部署开销。简言之，设施选址问题不仅仅考虑客户到服务器的路径开销，也考虑 在特定位置处部署一个服务器本身所带来的开销。 形式化的描述为：给定图g = ( 髓) 以及v 吩e v 的节点咋对某服务的需求 第3 章服务放置与服务选择 s ( v ；) 和在v ；处部署设旌的开销，【u ) ，求解集合矿的一个子集， 矿中的元素 作为放置设施地点，目标是使得部署和服务的总体开销c ( gs 力： 罗，以) + 罗， 弦“，m ( v a ) t 4 、化。 v 分v 穆 其中同样假定每个客户端选择距离自己最近的服务器，用m ( v ，) 表示矿中距 离节点坼最近的中位点，d ( v l ，m ( v ；) ) 表示i ；i 距离其选择的中位点之间的距离( 可 以是延迟，跳数等) 。 以上问题的描述是设施选址问题的通用描述，通常采用基于线性规划的( 拉 格朗日松弛) 算法来解决，因为此类问题都属于h p 难的，其他有效的近似算法 常常采用贪婪法和迭代法求解，此外还有基于特殊拓扑( 如树型结构) 的算法1 3 3 】 等。【3 4 为服务放置问题引入了一套统一的评价框架，根据计算开销的函数将问 题分成了三类：不考虑访问速率的情况；仅考虑读访问速率的情况；以及同时考 虑用户访问的读速率和写速率的情况，后两种情况又根据请求数据是一个还是多 个，服务器是否具有