（通信与信息系统专业论文）tiv感知的ip网络坐标系统及其性能研究.pdf

， q 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：却睁 日期：纠。年j 2 月z 1 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：坐导师签名： 日期：2o lo ， 摘要 摘要 目前，许多大规模分布式网络服务和应用需要有效地获知主机间的网络距离， 而网络的大规模、自组织、高度动态等复杂特征使得要准确、完全地测量节点间 的距离信息面临着极大的困难。因此，研究者们提出各种预测技术。 使用虚拟坐标来预测网络时延距离是一种简化而高效的时延测量方法，可以很 大程度降低实际测量带来的网络开销。它将网络空间嵌入到一定的测度空间，用 空间中的坐标来表示网络节点，这样网络时延的测量就转化为空间中点与点之间 距离的计算。但实际网络节点之间的时延距离会产生不满足三角不等式关系的现 象，常称之为三角不等式违例( 即t r i a n g l ei n e q u a l i t y v i o l a t i o n st ) 。违例现象会 使坐标系统产生误差，降低坐标系统的预测准确度。这种误差是不可避免的，但 却是可以抑制的。如何抑制违例对坐标系统预测准确度的影响是当前的研究重点 之一。 本文对已有的研究思路、方法和效果作了细致的分析和归纳，并发现：现有的 网络坐标系统较少考虑三角不等式违例带来的不利影响，致使系统的精确度降低。 由此以抑制三角不等式违例( t i v ) 的影响为目的，提出了一种对违例进行检测和抑 制的机制，即在对违例边进行检测的同时以参数来量化违例程度，并用该参数来 控制坐标的更新，从而达到抑制违例所带来的不利影响的效果。 同时，本文将该机制与分布式的坐标系统v i v a l d i 相结合，建立了对三角不等 式违例感知的网络坐标系统。并通过计算机仿真证明了机制的有效性。 然后，本文分析了违例的影响在坐标系统中的扩散现象，并从节点的更新度出 发，提出了一种基于邻居选择来抑制违例的机制，仿真证明，这种机制在抑制违 例的影响时，起到了较好的效果。 最后，论文对本文工作进行总结，并对未来工作的方向进行了展望。 关键词。网络距离，三角不等式违例，检测与抑制 a b s t r a c t a b s t r a c t t h ed i s t a n c ei n f o r m a t i o nb e t w e e nn o d e si nn e t w o r ki st h eb a s i sf o ra c h i e v i n g t o p o l o g y a w a r e n e s s h o w e v e r , i ts e 既t i si n f e a s i b l et oa c c u r a t e l ya n dc o m p l e t e l ym e a s u r e t h ed i s t a n c e sb e t w e e nn o d e sd u et ot h ec h a r a c t c r i s t i c so fn e t w o r k , s u c ha sb e i n g l a r g e s c a l e ，s e l f - o r g a n i z e d ，h i g hd y n a m i ca n ds oo n c o n s e q u e n t l y ，r e s e a r c h e r sh a v ep u t f o r w a r dv a r i o u sp r e d i c t i o nm e t h o d s u s i n gn e t w o r kc o o r d i n a t e st op r e d i c tn e t w o r kd i s t a n c ei sas i m p l ea n de f f i c i e n t n e t w o r kd e l a ym e a s u r e m e n tm e t h o dw h i c hc a ng r e a t l yr e d u c et h eo v e r h e a do fa c t u a l m e a s u r e m e n t t h en e t w o r kl a t e n c i e sa r ee m b e d d e di n t oag e o m e t r i cs p a c ea n dn e t w o r k n o d e sa r ed e n o t e db yc o o r d i n a t e s ，t h e nt h eg e o m e t r i cd i s t a n c ec a nb eu s e dt op r e d i c t n e t w o r kl a t e n c y b u tt h et r i a n g l ei n e q u a l i t yv i o l a t i o n s ( t r y ) b e t w e e nn e t w o r kn o d e s w i l lc a u s ei n a c c u r a c y s u c hi n a c c u r a c yi si n e v i t a b l e ，b u tg a sb em i t i g a t e d h o wt o r e s t r a i nt si m p a c ti sn o war e s e a r c hp o i n t t h i st h e s i s f i r s t l ya n a l y z et h ep r e s e n tr e s e a r c hm e t h o d sa n dt l l e i r e f f e c t a p h e n o m e n o ni sf o u n dt h a tt h ep r e s e n tn e t w o r kc o o r d i n a t e ss y s t e m su s u a l l yd o n t t h i l l l 【 a b o u tt ，s ot h ep r e d i c t i n ga c c u r a c yi sd e p r e s s e d i no r d e rt or e s t r a i n 刑si m p a c t , t h et h e s i sp r o p o s e sam e c h a n i s mw h i c hc a nd e t e c tt h et a n du s eap a r a m e t e rt od e f i n e t h ed e g r e eo fi ta n du s et h ep a r a m e t e rt oc o n t r o lt h eu p d a t eo fn o d c sc o o r d i n a t e sf o rt h e p u r p o s eo fr e s t r a i n i n gt h ei m p a c to ft w t h e n 也em e c h a n i s ma n dad e c e n t r a l i z e dc o o r d i n a r e ss y s t e mv i v a i d ia r e c o m b i n e dt ob u i l dat a w a r ec o o r d i n a t e ss y s t e m a n di t sv a l i d i t yi sp r o v e dt h r o u g h c o m p u t e rs i m u l a t i o n a l s o ，t h et h e s i sp r o p o s e sam e c h a n i s mw h i c hc a n r e s t r i c tt t h r o u g hc h o o s i n g n e i g h b o r sa n dp r o v ei t se f f i c i e n c yt h r o u g hc o m p u t e rs i m u l a t i o n a tl a s t t h et h e s i si sc o n c l u d e da n dt h ef u t u r ew o r k sa r ei n d i c a t e d k e y w o r d s ：n e t w o r kd i s t a n c e ，t r i a n g l ei n e q u a l i t yv i o l a t i o n ，d e t e c t i n ga n dr e s t r i c t i n g i i 目录 第一章绪论 目录 1 1 1 弓i 言：1 1 2 网络距离预测基本概念及分类1 1 3 网络虚拟坐标系统。4 1 3 1 测度空间嵌入理论5 1 3 2 目前比较完善的网络坐标系统5 1 3 2 1g n p 7 1 3 2 2p i c 9 1 3 2 3v i v a l d i 系统9 1 4 本文的主要工作及结构安排1 1 第二章三角不等式违例及其相关处理 1 2 2 1 三角不等式违例的基本情况。1 2 2 1 1 三角不等式违例的基本概念1 2 2 1 2 产生三角不等式违例的原因1 3 2 2 对三角不等式违例的研究和相关处理。1 6 2 2 1 三角不等式违例的相关特性16 2 2 2 对三角不等式违例问题的相关处理1 8 2 3 本章小结。2 2 第三章三角不等式违例感知的坐标系统 2 3 3 1 三角不等式违例的分析。2 3 3 1 1 违例的普遍性分析2 3 3 1 2 违例与时延大小的关系。2 5 3 1 3 违例对坐标系统准确度的影响2 6 3 2 三角不等式违例的检测和抑制机制2 8 3 2 1 违例系数的引入2 8 3 2 2 参考节点的选取方案2 9 3 3 对三角不等式感知的坐标系统3 0 3 4 对t - v i v a l d i 仿真分析3 4 m 目录 3 4 1p l a n e t l a b 基本介绍3 4 3 4 2 时延数据的处理3 6 3 4 3 仿真环境和参数设置3 7 3 4 4 仿真结果与分析3 9 3 5 本章小结一4 5 第四章基于邻居选择来抑制违例的机制 4 1 三角不等式违例对坐标系统的具体影响和相关处理4 6 4 1 1 v a l d i 系统中t 的影响4 6 4 1 2 三角不等式违例的抑制4 7 4 1 3 预警机制在抑制t 上的应用4 8 4 2 三角不等式违例与坐标的更新程度的关系4 9 4 3 基于邻居选取抑制违例的机制一5 0 4 3 1 违例影响在节点中的扩散。5 0 4 3 2 邻居节点的选取机制5 2 4 4 对邻居选择机制的仿真分析5 4 4 5 本章小结。5 6 第五章结论 5 7 5 1 全文总结5 7 5 2 下一步工作5 8 致谢 参考文献 个人简历 i v 5 9 6 0 6 3 图目录 图目录 图1 1i d m a p s 拓扑结构3 图1 2 实际网络空间。- 6 图1 3 虚拟坐标空间6 图1 _ 4 锚节点的坐标计算7 图1 5 普通节点的坐标计算8 图2 1 三角不等式违例的一般形式1 2 图2 2 自治域之间的三角不等式违例1 3 图2 3 专用链路产生的三角不等式违例1 4 图2 _ 4 使用b g p 协议时产生三角不等式违例1 4 图2 5 自治域内的三角不等式违例产生新的违例1 5 图2 - 6 邻近节点和违例的关系。1 7 图2 7 违例比例与时延大小的关系2 1 图3 1 寻找不违例节点集合2 4 图3 2 不违例节点集合扩大2 4 图3 3 时延大小与违例次数的关系2 6 图3 _ 4 不同违例比例下的相对误差累积分布2 7 图3 5 违例边的检测2 9 图3 6t v a l d i 中违例边的检测3 2 图3 7 节点坐标更新流程3 3 图3 8t - v a i d 伪代码3 4 图3 - 9p l a n e t l a b 在全球的节点分布。3 5 图3 1o 时延大小的分布情况3 7 图3 1 1t - v i v a l d i 的命令参数3 8 图3 1 2 违例比例为2 2 4 7 时相对误差的比较3 9 图3 1 3 违例比例3 1 8 3 时相对误差的比较4 0 图3 1 4 违例比例4 4 5 8 时相对误差的比较4 0 图3 1 5 使用p l a n e t l a b 全部时延数据时相对误差的比较4 l 图3 1 6 不同链路长度下的预测误差比较4 2 v 图目录 图3 1 7 玎l 的比较4 3 图3 18 每个节点的r r l 对比一4 4 图3 1 9t v a l d i 与l a t 的相对误差比较4 4 图3 2 0t - v i v a l d i 与l a t 的r r l 比较4 5 图4 _ l 链路伸缩变化与链路长度的关系4 9 图4 _ 2 节点更新度与违例的关系5 0 图禾3 违例影响的扩散5 1 图4 _ 4 邻居节点选取一5 2 图4 _ 5 邻居节点的选取更新5 3 图4 6 选取机制伪代码5 3 图禾7 相对误差累积分布对比5 4 图4 8r r l 累积分布对比5 5 图4 9 每个节点的仃1 值对比5 5 v l 第一章绪论 第一章绪论 1 1 引言 近年来，随着口网络规模的指数式增长、网络结构呈现高度的异构性与复杂 性，口网络性能的可知性就变得愈加复杂化、困难化。同时又随着新的网络应用的 不断涌现、用户对网络服务质量要求的不断上升，不管是网络运营者，还是网络 使用者，它们都迫切需要能快速、及时地获得反映网络运行性能和行为特征的第 一手资料，准确掌握口网络性能及状态参数，以最大程度地优化网络应用、提高网 络效率。在实际m 网络中，所涉及的性能及状态参数很多，例如：带宽、时延、 吞吐量等，而节点间时延是其中关键参数之一。在目前很多网络拓扑优化设计以 及网络应用性能优化和改善中，它发挥着非常重要的作用。例如：在内容分发网 络( c d n ：c o n t e n td i s t r i b u t i o nn e t w o r k ) 1 】【2 】中，w e b 客户机可利用时延信息，可以 从多个镜像服务器中，选择其中最邻近的一个服务器，快速地获得所请求的页面 对象。这样的例子还有很多，如p 2 p ( p e e r - t o p e e r ) 网络d h t ( d y n a m i eh a s ht a b l e ) 构 造、o v d a y 路由、组播树构建等，它们都可以利用该信息对其性能进行不同程度 的优化和提高。因此时延测量方法和技术一直是口网络研究领域的一个重要主题。 在目前很多研究中，把节点间时延称之为“网络距离”( n e t w o r kd i s t a n c e ) 通常是 指r t t 。获得这些信息的一种最直接的方法是在两节点之间发起主动测量，如p i n g 方式。它的最大优点就是简单直观，但是它效率低、开销大、可扩展性差。因为 随着网络规模的不断扩大，对网络中的所有节点进行完全的距离测量在现实中面临 着极大的困难：网络节点数量庞大，使得完全距离测量极易造成严重的带宽消耗 和网络拥塞，同时测量的通信开销巨大；网络中的节点存在高度动态性、不可达 性等问题，使得直接测量有时根本无法进行。因此，越来越多的研究者们提出采 用网络距离预测技术，以减少测量开销并且使得预测精度足以满足实际应用所需。 1 2 网络距离预测基本概念及分类 网络距离预测的主要任务是，根据有限的测量信息对实际网络中任意两个节点 间的时延值进行推测，进而向用户提供相关距离信息。根据获取节点间距离方式 电子科技大学硕士学位论文 的不同，网络距离预测可以分为网络距离值预测和网络临近度估计两大类。前者 目标是给定网络中任意两个节点，系统均通过预测方式尽可能精确地计算出它们 之间的距离值，后者并不预测节点间确切的距离值，而是采用一定的算法，根据用 户请求寻找出满足某些条件的一个或者一组近距离邻居节点，进而通过直接测量 方式获取到该节点或节点集的距离。两种技术各有优缺点，网络距离值预测技术 获取节点间距离比较简单，且测量负载较小，但其预测精度相对较低；而网络临 近度估计技术通过一定算法估计出可能的临近节点，最终到目标节点的距离由直 接测量获得，因此其精度较高，但测量负载相对较大。 目前网络距离预测技术划分为两类：非坐标距离预测方法和网络坐标计算方 法。 非坐标距离预测方法 非坐标距离预测方法通常是指通过直接测量( d i r e c tm e a s u r e m e n t ) 的方式测量网 络中部分节点的距离，然后根据这些部分测得的距离信息来直接预测所有节点之 间的距离信息，并不使用任何坐标计算的形式来预测。此类方法通常需要在网络 中部署一些特殊的节点来辅助完成预测过程，这些特殊节点可以是一些代理节点 或者服务器节点。根据特殊节点的类型，可将其分为基于代理节点组合方法、基 于d n s 服务器方法以及未利用代理节点和服务器等的其他方法。 基于代理节点组合方法通常在现实i n t e m e t 环境中部署一些代理节点来辅助完 成所有节点间的距离预测。不同的预测方法往往采用不同的代理节点，有的采用 跟踪节点( t r a c 拼) ，有的则采用监控节点( m o n i t o r ) 等。基于代理节点组合的预测方法 ：l = 要- ；f i i d m a p s 6 】等，基于d n s 服务器方法不像基于代理节点组合方法那样需要部 署额外的代理节点，而是直接利用i n t e r n e ；t 中广泛分布的d n s 服务器来完成距离预 测。 i d m a p s 是最早提出的一种大规模网络距离预测机制，通过集中式服务为网络 节点提供距离预测服务。该机制中包括两个核心内容：地址前缀块( a d d r e s sw e f i x , 简称a p ) 以及t r a c e r 节点。每个a p 代表一个具有相同口地址前缀的节点集合， t r a c e ：r 节点则是在网络中部署的测量节点，并保证每个地址块至少有一个t r a c e r 与其接近，不同t r a c e r 节点周期性地互相测量相互之间距离，同时，每个t r a c e r 节 点周期性地测量到与其临近a p 的距离。所有这些测量信息都被收集到某个集中式 服务器中，这样，任意两台主机间的距离就等于两台主机所在a p 到达各自t r a c e r 节点间距离与两个相关t r a c e r 节点间距离之和。 i d m a p s 拓扑结构如图1 - 1 所示： 2 第一章绪论 图1 - 1i d m a p s 拓扑结构 各种基于代理节点方法的特点如下：第一，方法一般采取相关的分簇方式，如 i d m a p s 通过口地址前缀分簇。第二，通过代理节点维护相关的拓扑结构，如 i d m a p s 维护局部a s 图、利用h o p s 服务器维护全局i n t e r n e t 虚拟拓扑图。第三， 适当增加代理节点的数目，能够提高距离预测的精度，但同时会增加维护和管理 的开销；第四，此类方法一般采取局部集中、全局对等的方式来预测距离，容易 导致单点失效、无法预测等问题。 网络坐标计算方法 对网络坐标计算方法的研究是网络距离预测技术研究的主体，其基本思想是通 过某种网络嵌入的方式，将整个网络嵌入到一定的几何空间中，网络中的节点对 应于所嵌入空间中的点，空间中节点之间的距离对应于网络中节点之间的距离， 并以一定的坐标形式计算节点的网络坐标。网络坐标计算方法很多，目前尚无严 格的分类标准。根据不同的研究层面，可以采用不同的分类标准。根据预测方法 中锚节点( 1 a n d m a r k s ) 的分布性，可以分为集中式锚节点和分布式锚节点方法；根据 所使用的坐标类型，可以分为绝对坐标方法和相对坐标方法；根据网络所嵌入的 空间模型，可以分为欧氏嵌入和非欧氏嵌入方法两类；根据坐标的计算过程，还 3 电子科技大学硕士学位论文 可以分为模拟物理过程方法和普通数学计算方法等。 在集中式锚节点方法中，锚节点通常是集中固定的预先选取好的少数节点，节 点的性能相对较高，并且锚节点节点的分布性一般较好。此类方法有其固有的优 势：一方面，新加入的节点可以直接访问已部署的锚节点节点，从而减少了新加 入节点查询地标的开销；另一方面，由于固定锚节点的性能以及分布性较好，坐 标计算的精度较高。然而集中式的方法也具有致命的缺点：集中式的锚节点易成 为通信、负载瓶颈，造成单点失效问题，扩展性明显受到限制，而且易成为恶意 攻击的对象，安全性难以得到保证。集中式锚节点方法多为网络坐标计算研究早 期提出的方法，此方法与非坐标距离预测方法相比效率更高，精确性更好。由于集 中式锚节点的缘故，使得方法的可扩展性和安全性较差，因此后来的研究大多是 针对分布式锚节点方式。 分布式锚节点方法力图避免集中式锚节点的缺陷，通常，系统中已计算出坐标 的任意节点均可作为锚节点，而非使用固定的节点作为锚节点。所有的节点都可 以作为锚节点，并且锚节点的选择是随机的，坐标的计算由节点自身计算而并非 由集中的节点计算，增强了系统的可扩展性。 同时，有学者研究了锚节点选择策略问题，通过对比随机、最近、混合3 种锚 节点选择策略，并且最先发现了远距离和近距离节点的坐标计算不能达到同时精 确的精度不一致性问题。同时指出混合锚节点策略的综合性能最好。针对这种现 象，相关研究采用一种层次式方法利用多个锚节点集合计算多个坐标集，每一个 坐标和锚节点集合对应不同的距离范围。例如，一个节点使用一个坐标来估计到 远节点的距离，而用另一个坐标来估计到近节点的距离如若发现一组坐标对近距 离预测精确，而另一组对远距离是精确的，则根据感兴趣的范围，综合选择合适 的坐标集合以最高的整体预测精度。 一般地，模拟物理过程的分布式地标方法通过增加网络坐标的更新调整过程， 主动适应网络动态变化环境，坐标的适应性、鲁棒性、精确度通常较高，然而此 类方法的问题在于收敛性与稳定性问题，以及为优化收敛性、稳定性所带来的计 算开销和通信开销等问题，在性能与代价方面往往需要折衷考虑。 1 3 网络虚拟坐标系统 简化而高效的时延测量方法，成为了近年来网络测量领域的研究重点之一。近 来，一些研究者将计算几何学和测度论的理论和方法，运用到了m 网络时延测量 4 第一章绪论 的研究中，提出了基于虚拟坐标的间接测量方法。它将口网络距离嵌入到某一测 度空间，建立起网络节点与该空间点的映射关系，即为网络节点赋予一组相应的 空间坐标。由此网络中节点间的时延与空间内两点之间的测度距离就有一定对应 关系，时延测量任务就转为空间内两点之间的测度距离计算任务。 使用虚拟坐标系统来测量时延可以大大减轻实际测量带来的网络负担。在网 络虚拟坐标系统中，每个网络节点需要计算自己在测度空间中的坐标，当坐标确 定以后，节点之间的时延可以用测度空间中点与点之间的距离来预测。这个时候， 网络中任意两点之间的时延就可以根据它们的坐标来求出，而不用单独对每对节 点做出测量。 1 3 1 测度空间嵌入理论 测度空间嵌入理论可以简单描述如下：假设有两个测度空间膨。和鸠，分别 记为m = ( 五，西) 和m ，= ( x ：，吐) 。这里x 为集合，距离函数为击石_ r + ( 满足对 称性、正定性、以及三角不等式关系) 。若存在从五到置的映射西? 墨_ 五， 则在咖作用下，将得到新的测度空间咖f ，m ，) = p f ，五夕，破j ，其中西f ，m 。j 即是m 。在 m ，中的嵌入。在实际问题中，我们常常是找寻恰当的映射西，以便能在一个简单 的低维的测度空间对原始问题求解。在口网络中，网络节点时延的测量和分析也 可采用类似思路。将网络距离嵌入到某一测度空间，建立起网络节点与该空间 点的映射关系，即为网络节点赋予一组相应的空间坐标。由此网络中节点间的时 延与空间内两点之间的测度距离就有一定对应关系，时延测量任务就转为空间内 两点之间的测度距离计算任务。 1 3 2 目前比较完善的网络坐标系统 使用虚拟坐标系统来预测节点之间的时延时，需要解决以下问题： 1 网络节点的几何映射空间构造( 其中包含空间距离函数的定义) 。 2 空间映射点的虚拟坐标计算。 简言之，即如何利用部分测量数据( 即节点时延矩阵) ，为其他所有节点计算 出相应的坐标向量。许多文献都将该问题抽象为一测度空间到另一测度空间的映 射，即嵌入( e m b e d d i n g ) 。目前最主要的嵌入是欧式嵌入，即用欧式测度空间来模 拟网络空间，使用欧式空间中的点的坐标表示每个网络节点。图1 和图2 是嵌入前 和嵌入后的一个简单例子。 电子科技大学硕士学位论文 图1 - 2 实际网络空间 图卜3 虚拟坐标空同 图卜1 中的数值是网络节点之间实际的时延值，这个值通常是用节点之间的往返 时延( r t r ) 表示，图卜2 是将时延嵌入到欧式空间以后，使用空间中的坐标和距 离函数预测出的结果。 目前的虚拟坐标系统所使用的空间嵌入方法主要分为两大类：一是基于锚节点 ( l a n d m a r k n o d e ) 的方法；二是采用物理学上“弹簧伸缩效应一和“力场作用下的 粒子运动模式一等一些类似机理来模拟网络中的节点。 6 也分为两步。分别为锚节点的坐标计算和普通节点的坐标计算。如果使用的欧式 空间的维数为d ，那么计算锚节点的坐标时，需要的锚节点的个数为d + 1 ，当锚节 点的坐标计算出来以后，普通节点就可以测量自己到锚节点的的时延，再结合锚 节点的坐标来计算自己的坐标。 下面我们用l l ，k ，l n 表示n 个锚节点( n 捆，锚节点的计算过程如下： 首先，锚节点测量相互的r 1 阿值，用d z , 工，表示h 与b 的测量距离，d t , l j 表示计算 出的距离。 然后，使用优化算法找出n 个坐标，用石，否岛，否“表示，使得测量距离与 计算距离的误差总合最小，即最小化目标函数： 工坷( 石厶，否岛弓“) = 胁，( d 句，d 厶- ) ( 1 1 ) 厶句t l 上1 “l 盼， 其中： e r r o r ( d i 。zd 厶句) = ( 叱工，一 2 ( 1 2 ) j , d z ，l j ) 这样就得到所有锚节点的坐标。注意在这里，每个锚节点都要测量自己到其他所 有锚节点的距离，并使用这个距离来计算自己的坐标。这个过程如图1 _ 4 所示。 实际测量距离 计算的距离 锚节点 仅2 j 怒。 涮 t 一 阻n ； 叫龠( x 3 ，1 ，y 1 ) 图1 - 4 锚节点的坐标计算 7 y 3 ) 电子科技大学硕士学位论文 l t ，l 2 ，l 。表示锚节点，虚线表示他们之间的实际测量，右图中的( x ，y ，) ， ( x 幻y 2 ) ，( x 。，y 3 ) 是他们在测度空间中的表示。 锚节点的坐标计算出来以后，当有普通节点加入到系统时，用h 表示它，它首 先测量自己到每个锚节点的距离，用d 舭表示，用孑胃表示计算出的距离，那么该 节点的坐标，用e 表示，就可以通过最小化目标函数： 厶( c 胃) = 西柳( 略，如) ( 1 3 ) 与e ，上 来求出。其中( 1 3 ) 中的e r r o r ( ) 同( 1 2 ) 。这个过程如图1 - 5 所示。 兮。：二乒 9 。吾( x 2 ， 一，实际测量距离 天 计算的距离 i) 锚节点 翟 普通节点 、i j ，工， 吣 ，、 刍人 网 旷 唯茏 ( x i ：y 4 ) ，v 。) 图卜5 譬通节点的坐标计算 右图中( x ，y 1 ) 就是普通节点加入系统后计算出的自己的坐标。 图卜3 和1 - 4 只是g n p 系统的一个简单示例，实际使用的测度空间维数要求更 高。 该g n p 方案实现简单，它仅需两个步骤就可完成原始测度空间到一个欧氏空 间的嵌入。总体上讲，g n p 能比较准确地估计网络距离。例如在网络时延的嵌入 空间是7 维欧氏空间情况下，5 0 的距离预测，误差小于1 0 ；9 0 的距离预测，其 误差小于5 0 9 6 。但是，该方案在空间嵌入时，常通过求解非线性多维最优化闯题( 即 曩小化实际网络距离与空闻度量距离闻的相对误差之和) 来构造映射空间，其求解 亨法为单纯形下降法( s i m p l e xd o w n h i l lm e t h o d ) 。然两该方法的最大缺陷在于：不 ：收敛速度很慢，而且对初始值的选取敏感，即初始值对最后求解结果影响很大。 8 第一章绪论 1 3 2 2p i c 为了避免过多依赖锚节点的情况，p i c t 7 】在g n p 的基础上，改进了锚节点的选 取方案。在普通节点加入到系统，并且计算出了自己的坐标以后，新加入的其他 节点也可以用该节点作为锚节点。这样就减轻了初始锚节点的负担，同样也避免 了因为个别锚节点的失效造成的计算误差。 在p i c 中，新加入的节点可以选择任何一个坐标已知的节点作为自己的锚节 点。同时也提出了3 种选取锚节点的策略。 第一种，随机选取策略。即从已有坐标的节点中随机选取n 政壤示坐标维数) 个作为自己的锚节点。 第二种，最近选取策略。即从已有坐标的节点中选取距离自己最近的n 个作为 自己的锚节点。 第三种，复合选取策略，即一部分锚节点随机选取，一部分采取最近选取。 在最近选取策略中，为了找到离自己最近的锚节点，p i c 提出了两种方案。 方案一：先从已知节点中随机选取一个节点暂时做为目标节点，然后测量到 这个节点的所有邻居节点的距离，如果有邻居节点离自己更近，就将这个邻居节 点视为目标节点，接着重复上述过程，直到找不到更近的节点为止。 由于方案一的反复测量可能会带来更多的网络负担，p i c 提出了方案- - ：不直 接测量，使用坐标来计算距离从而判断是否离自己更近。这种方法可以减轻直接 测量带来的过多开销，但如果新加入节点还没有坐标的话，就会失去效果。因此 p i c 提出先用随机策略求出该节点的坐标，然后使用坐标来寻找最近锚节点。 不同的选取策略对坐标的精确度也会有不同的影响，p i c 3 通过实验表明：使 用复合选取策略时，系统的整体相关误差最低，使用随机选取策略时，对长距离 的预测精确度更高，而使用最近选取策略时，对短距离的预测精确度更高。 而与g n p 另外一个不同点就是，p i c 所使用的用来最小化的目标函数为： 乞 厶( 石以) ：兰( 鱼乒堕) ： ( 1 4 ) j z l u h h i l 3 2 3v i v a l d i 系统 v i v a l d i 8 】系统与前面提到的g n p 和p i c 不同，它是一种完全分布式的坐标系 统，系统中所有的节点都是没有差别的，地位平等。它用弹簧的伸缩效应来模拟 网络节点之间的距离的变化，用最小化弹簧的能量来模拟最小化误差从而达到提 9 电子科技大学硕士学位论文 高坐标的精确度的目的。 每个v i v a l d i 系统中的节点使用自己到一部分邻居节点的距离来计算和更新坐 标。它的基本思想是将节点之间的距离模拟为弹簧的长度，弹簧的静止长度对应 于节点之间的测量距离l 玎t ，弹簧的实际长度对应于节点之间的计算距离。如果 弹簧的实际长度大于静止长度，即意味着两节点在测度空间中的距离相对于实际 位置被拉伸了，那么根据弹簧的伸缩效应，会迫使两节点靠拢；如果弹簧的实际 长度小于静止长度，即意味着两节点在测度空间中的距离相对于实际位置被压缩 了，弹簧就会迫使两节点分开。v i v a l d i 系统中的节点就根据这个原则来不断更新 自己的坐标。 用l ；，表示实际测量距离，x ；和x 。表示节点i 和节点j 的坐标，那么根据胡克 定律，最小化r t t 测量值和计算值之间的误差( 采用平方误差函数) 就相当于最 小化弹簧系统的势能。即最小化： e = ( 厶，- i l x , 一_ l i y f ， ( 1 5 ) 这就可以模拟节点在弹力作用下的移动，逐步调整节点坐标实现整个弹簧系统 的稳定，从而达到节点坐标的最优化。 下面是v i v a l d i 系统中每个节点更新自己的坐标的过程。 假设点i 的坐标是x 。，用参数e 。表示该点对自己的坐标的确信程度。它的一个 邻居节点为j ，要更新i 的坐标，i 测量自己到j 的距离( r t l i ) ，同时引入可变参数 c 。和c 。，单位向量t l0 。使用下面的公式来逐步完成更新： 公式( 1 6 ) 计算本地坐标与其他坐标的误差权重： 国= b ( 岛+ 巳) ( 1 6 ) 公式( 1 7 ) 计算此时两点之间距离的相对误差( 计算值与实测值之间的相对误 差) ： 乞爿l lx , 一i i - r ni 膨 ( 1 7 ) 公式( 1 8 ) 计算本地误差的变化： q = 乞x c , 国+ 岛x ( 1 一乞国) ( 1 8 ) 公式( 1 9 ) 、( 1 1 0 ) 更新本地坐标： 万= 巳0 9 毛= + 万( 川一0 玉一1 1 ) “( 毛一) 同时，v i v a l d i 还使用高度向量来弥补欧式空间的不足。 1 0 ( 1 9 ) ( 1 1 0 ) 欧式空间中的距离 第一章绪论 对应于主干网的时延，而高度向量模拟数据包通过接入网进入主干网的时延。高 度向量的大小依赖于询问响应延时和链路质量。 加入高度向量以后，高度向量的性质如下： x ，x l - y ，y h 】= 【( x y ) ，x h + y h 】 i i 【x ，】i l = l i x i | + 口 ，x h xx h = 口工，口x h 】口。【，j 2 【口工，口j 实际上v i v a l d i 系统更新坐标的过程一直在进行，刚开始时， 精确度较低，随着更新的逐步进行，坐标的准确度也逐步提高。 1 4 本文的主要工作及结构安排 ( 1 1 1 ) ( 1 1 2 ) ( 1 1 3 ) 节点的坐标的 本文主要研究提高网络虚拟坐标系统精确度的方法实现，文章所做的主要工 作及相应的结构安排如下： 第一章阐述论文的研究背景、现状及意义，主要包括：网络虚拟坐标系统的 概述。 第二章分析三角不等式违例产生的原因和它对网络虚拟坐标系统的不利影 响，并介绍相关的处理方案。 第三章从三方面分析了违例的影响，针对违例边提出了检测与抑制机制，建 立了基于三角不等式感知的网络坐标系统，同时对其性能进行了全面的仿真，结 果表明该系统在解决三角不等式违例问题时起到了较好的效果。 第四章分析了v i v a l d i 系统中t i v 造成的影响，并基于此提出了根据节点更新 度选择邻居的机制，同时通过仿真验证了该机制抑制违例的有效性。 第五章是全文总结。 电子科技大学硕士学位论文 第二章三角不等式违例及其相关处理 2 1 三角不等式违例的基本情况 在实际网络中，网络节点之间的时延r 1 r t 是很重要的参数，常常被用来寻找 最短路径和寻找最近邻居节点。影响r t t 的因素有很多，链路质量，链路长度， 链路中的通信负担以及接入网技术等等。随着网络情况的变化，r t t 值也会发生 相应的变化。因此少数节点之间的r 1 r t 值并不能完全反应整个网络的时延特征， 例如节点a 到节点b 的时延很小，节点b 又靠近节点c ，a 却并不一定离c 很近。 许多研究【9 】【1 3 】【1 4 】表明网络时延空间中的节点之间会产生三角不等式违例t r i a n g l e i n e q u a l i t yv i o l a t i o n s ( t ) 的情况。这种违例会影响许多分布式系统的性能，因为 这些系统默认三角不等式是严格遵守的。 2 1 1 三角不等式违例的基本概念 网络坐标系统是将网络节点之间的时延距离嵌入到测度空间中，使用空间中的 坐标来表示每个节点。而测度空间中的点之间必须满足三角不等式关系：即空间 中任意三个点a b ，c ，它f f 碇问的距离试a 固域a ，c 咖固要同h 寸j i 盖恩读a 王垆 d 9 ， 鼬射邸。魂0 ，媳咿棚 i 。根据文献【9 】，由于路由策略的影响，实际 网络节点之间的时延并不是严格满足三角不等式，这个时候就产生了三角不等式 违例现象，如图2 1 ，八b ，c 是网络中的三个节点，如果在螂三个节点之间的 距离中，吠邮) + 硪旧 吠2 ，1 ) 坝1 ，3 ) ，三角不等式违例就产生了。 专用链路也是产生三角不等式违例的原因之一。 1 3 到每个路由器之间的路径信息是无法判断的。这个时候也很有可能产生三角不等 式违例。如图2 _ 4 所示。 图2 - 4 使用b g p 协议时产生三角不等式违例 1 4 l 。1 。 节点a 到节点b 的通信，如果使用自治域之间的路径，b g p 协议会选择经过自 治域4 来实现，这时烈a ，