（通信与信息系统专业论文）基于虚拟坐标的ip网络定位技术研究.pdf

重庆邮电大学硕士论文 摘要 摘要 对于许多大规模的分布式网络应用如应用层组播、最近服务器选择等，如果能 够方便快捷地获取主机之间的网络距离，将对提高它们的性能有很大的帮助。度量 网络距离的网络性能参数时延、带宽以及丢包率等虽然可以按需求进行精确测量， 但是大量的大区域端到端路径却使按需测量由于其昂贵的开销、时间花费以及带来 的网络负担而变得不实际。为了协调性能优化和可扩展性之间的冲突，网络定位技 术通过预测主机之间的网络距离来近似真实的测量值，并成为目前研究的热点之一。 其中基于虚拟坐标的网络定位技术由于其简单有效的特点，更是得到了广泛的研究。 本文首先对口网络定位技术进行了介绍，描述了网络定位的目的及其现状。接 着详细介绍了基于虚拟坐标的口网络定位技术，分析了其基本思想，介绍了网络坐 标系统设计过程及其面i 晦的挑战。对于基于固定锚节点的网络坐标系统，讨论了锚 节点的个数以及它们在网络中的位置对系统性能的影响。关于锚节点的分布，当其 数量较小时，目前的选取方法容易使其形成网络瓶颈，针对此问题提出了一种新的 锚节点选取机制。然后分析了网络坐标系统对锚节点数量的需求，在现有工作的基 础上提出了一种最小化锚节点的网络坐标系统c - l a n d m a r k s ，并利用所提出的机制 选取锚节点。最后进行了仿真验证。仿真结果表明：1 ) c l a n d m a r k s 系统能够在准 确预测网络距离的情况下减小系统的测量开销。2 ) 在锚节点失效的情况下， c 1 a n d m a r k s 系统仍能有效地预测网络距离，该系统能够具有很好的稳定性。3 ) 所 提出的锚节点选取机制能够使锚节点具有较好的分布，从而提高网络坐标系统的性 能。 总体来说，本文的主要贡献如下： 1 ) 提出了一种锚节点选取机制。当采用较大数量的锚节点时，进行随机选取， 简单有效；当采用较小数量的锚节点时( 5 1 0 个) ，所提出的基于聚类的选取方式 能够使锚节点具有较好的分布，同时也可以提高系统的稳定性。 2 ) 在现有网络坐标系统的基础上，提出最小化锚节点的个数以减小系统的测 量开销，并利用上述机制选取锚节点( c l a n d m a r k s ) 。c - l a n d m a r k s 系统减小了普 通主机的测量次数，降低了测量开销；而所选锚节点的分布则保证了系统距离预测 的准确度，同时也使c - l a n d m a r k s 具有较好的稳定性。 关键词：网络距离，坐标，锚节点，c - l a n d m a r k s 系统，聚类 重庆邮电大学硕士论文摘要 a b s t r a c t m a n yl a r g e s c a l ed i s t r i b u t e dn e t w o r ka p p l i c a t i o n ss u c h a l sa p p l i c a t i o nl a y e rm u l t i c a s t a n dn e a r e s ts e v e rs e l e c t i o nc a nb e n e f i tf r o mo b t a i n i n gn e t w o r kd i s t a n c e sb e t w e e nh o s t s c o n v e n i e n t l y a l t h o u g ht h ed i s t a n c em e t r i c ss u c ha sl a t e n c y ，b a n d w i d t ha n dp a c k e tl o s s r a t ec a nb ea c c u r a t e l ym e a s u r e do nd e m a n d ，t h eh u g en u m b e ro f 淅d e - a r e a - s p a n n i n g e n d - t o - e n dp a t h sm a k e sp e r f o r m i n go n d e m a n dn e t w o r km e a s u r e m e n t si m p r a c t i c a l b e c a u s ei ti st o oc o s t l ya n dt i m e - c o n s u m i n g t ob r i d g et h eg a pb e t w e e nt h ec o n t r a d i c t i n g g o a l so fp e r f o r m a n c eo p t i m i z a t i o na n ds c a l a b i l i t y , t h en e t w o r kp o s i t i o n i n gt e c h n o l o g y a t t e m p tt op r e d i c tt h en e t w o r kd i s t a n c eb e t w e e nh o s t s ，a n di th a sb e c o m ea l li m p o r t a n t r e s e a r c hf i e l d t l l en e t w o r kp o s i t i o n i n gt e c h n o l o g yb a s e do nv i r t u a lc o o r d i n a t e s e s p e c i a l l yg a i n sm u c hm o r ec o n c e r n sb e c a u s eo fi t ss i m p l i c i t ya n de f f i c i e n c y i nt h i sp a p e r , t h et e c h n o l o g yo fl pn e t w o r kp o s i t i o n i n gi si n t r o d u c e df i r s t l y , i n c l u d i n g t h ep u r p o s eo fn e t w o r kp o s i t i o n i n ga n dt h ec u r r e n td e v e l o p m e n t t h e nw ec o n c e n t r a t eo n t h ei pn e t w o r kp o s i t i o n i n gt e c h n o l o g yb a s e do nv i r t u a lc o o r d i n a t e s ，w h e r et h ek e yi d e ai s s t u d i e da sw e l la st h eg e n e r a la p p r o a c ha n dc h a l l e n g et oc o n s t r u c tan e t w o r kc o o r d i n a t e s y s t e m f o rt h en e t w o r kc o o r d i n a t es y s t e mb a s e do nf i x e dl a n d m a r k s ，h o wt h el o c a t i o n s a n dt h en u m b e ro fl a n d m a r k sw i l la f f e c tt h ep e r f o r m a n c eo ft h es y s t e mi sd i s c u s s e dh e r e w h e ni tc o m e st ot h ed i s t r i b u t i o no ft h el a n d m a r k s ，i ft h en u m b e ro ft h el a n d m a r k si s s m a l l ，i tm a yb e c o m et h ec o m m u n i c a t i o nb o t t l e n e c k sa c c o r d i n gt ot h ec u r r e n ts e l e c t i o n m e t h o d s t h e r e f o r e ，an o v e ll a n d m a r k ss e l e c t i o nm e c h a n i s mi sp r o p o s e di nt h i sp a p e r m e a n w h i l e ，a r e ra n a l y z i n gt h er e q u i r e m e n to ft h en u m b e ro fl a n d m a r k sf o ran e t w o r k c o o r d i n a t es y s t e m ，t h es y s t e mo fc l a n d m a r k si sp r o p o s e dt om i n i m i z et h en u m b e ro f l a n d n m r k s ，w h i c hu s i n gt h e s e l e c t i o nm e c h a n i s mm e n t i o n e da b o v et oc h o o s et h e l a n d m a r k s t h es i m u l a t i o nr e s u l t ss h o wt h a t ：1 ) c l a n d m a r k sc a l lm a k et h em e a s u r e m e n t o v e r h e a dg r e a t l yr e d u c e dw h i l ep r e d i c t i n gn e t w o r kd i s t a n c ea c c u r a t e l y 2 ) c l a n d m a r k s w i l lb ee f f i c i e n ti nn e t w o r kd i s t a n c ep r e d i c t i o nw h e ns o m eo ft h el a n d m a r k sa r e u n a v a i l a b l e ，a n dt h e r e f o r eh a sg o o ds t a b i l i t y 3 ) ml a n d m a r k ss e l e c t i o nm e c h a n i s m p r o p o s e de i a s u r e s ag o o dd i s t r i b u t i o no ft h e l a n d m a r k s ，w h i c h c a l li m p r o v et h e p e r f o r m a n c eo f t h es y s t e m t os u mu p ，t h em a i nc o n t r i b u t i o n so ft h i sp a p e ra r ea sf o l l o w s ： 1 ) a n o v e ll a n d m a r ks e l e c t i o nm e c h a n i s mi sp r o p o s e d w h e nu s i n gal a r g e rn u m b e r n 重庆邮电大学硕士论文 摘要 o fl a n d m a r k s ，t h er a n d o ms e l e c t i o ni se f f e c t i v e ；w h e nu s i n gas m a l ln u m b e ro fl a n d m a r k s ( 5 10 ) ，t h es e l e c t i o nm e t h o d sb a s e do nc l u s t e r i n gc a nm a k et h el a n d m a r k sh a v eag o o d d i s t r i b u t i o n ，a n da l s oi m p r o v et h es t a b i l i t yo ft h es y s t e m ， 2 ) t h en e t w o r kc o o r d i n a t es y s t e mo ft l a n d m a r k si sp r o p o s e db a s e do nc u r r e n tw o r k ， w h i c hm i n i m i z e st h en u m b e ro fl a n d m a r k st or e d u c et h em e a s u r e m e n to v e r h e a d ，a n du s e s t h el a n d m a r ks e l e c t i o nm e c h a n i s mm e n t i o n e da b o v e c 1 a n d m a r k sm i n i m i z e st h e m e a s u r e m e n t so fa j lt h eo r d i n a r yh o s t s ，w h i c hc a nr e d u c et h em e a s u r e m e n to v e r h e a do f t h es y s t e m ；a tt h es a n l et i m e ，t h ed i s t r i b u t i o no ft h es e l e c t e dl a n d m a r k sc a ni m p r o v et h e a c c u r a c yo fd i s t a n c ep r e d i c t i o n , a n da l s om a k et h es y s t e mh a v eg o o ds t a b i l i t y k e yw o r d s ：n e t w o r kd i s t a n c e ，c o o r d i n a t e s ，l a n d m a r k s ，c l a n d m a r k ss y s t e m ， c l u s t e r i n g h i 重庆邮电大学硕士论文 第一章绪论 第一章绪论 1 1 研究背景及意义 近年来随着口网络的快速发展，出现了许多大规模的全球分布式网络服务和应 用，如内容寻址网络( c a n ) n 1 、o v e r l a y 组播晗1 、以及p 2 p 文件共享( 如n a p s t e r 和g n u t e l l a ) 等。这些应用的共同特征就是它们在选择通信路径上有很大的灵活性， 包含了系统中节点相对位置的拓扑信息将会有助于提高此类应用的性能。 内容寻址网络( c a n ) 中，有效的路由机制对系统的性能将起着至关重要的作 用。在执行一个查询任务时，c a n 节点到邻居节点的距离信息将有助于选择合适的 转发路径，从而降低查询时延。在p 2 p 文件共享系统( 如n a p s t e r 和g n u t e l l a ) 中， 用户在下载所需的共享文件时，如果能够获得相对的拓扑信息，则可以选择从距离 自己较近的节点处下载。另外如w e b 镜像服务器的选择，对应一个w e b 站点( 如 y a h o o ) 有多个镜像服务器( s ，最) 可以为w r e b 客户提供服务。当一台主机h 要连接到该w e b 站点时，希望能够连接距离该主机最近的一个镜像服务器，以保证 w e b 页面传输速度，同时提高h t t p 请求的响应速度。这时，就需要知道网络中该主 机h 与各个镜像服务器之间的距离，从而使该主机能够选择距离其最近的一个镜像 服务器。 与这些应用紧密相关的网络性能参数有时延、带宽以及丢包率等，它们可以从 不同角度衡量主机间的网络距离。虽然此类网络性能参数可以按需求进行精确测量， 但是在这些分布式系统中必须考虑大量的大区域跨越的端到端路径，这将使按需网 络测量由于其昂贵的开销、时间花费以及沉重的网络负担而使变得不实际。 为了协调性能优化和可扩展性之间的冲突，目前有前景的方法是要尝试预测主 机间的网络距离( 如往返时延和发送延时等) ，用预测得到的距离来近似真实的网络 测量距离，从而尽可能地减少按需网络测量。有效的网络距离预测方法能够在大量 节省测量开销和时间花费的情况下，获得大致的网络拓扑信息，满足大规模分布式 网络应用如c a n 、应用层组播等的需求。因此，网络距离预测方法已成为目前研究 的热点之一。 我们在本篇文章中所研究的p 网络定位技术，即是研究p 网络中主机之间的 网络距离预测机制。此处，关键的问题是如何设计出能够准确地、可扩展地、及时 地预测网络距离的方法。 重庆邮电大学硕士论文第一章绪论 1 2 网络计算模式 1 2 1 客户端服务器模式 在传统的互联网计算模式中，客户端服务器( c l i e n t s e w e r ，c s ) 模式占据了 主流。当时，客户端的带宽和计算资源较弱，通过c s 模式可以降低对客户终端能 力的要求，而将处理集中在服务器端。客户端发送请求给服务器，等待服务器的响 应，并返回自己所请求的服务。图1 1 描述了一个典型的c s 模式的网络结构。 服务器 咨尸 图1 ic s 模式网络结构 近年来，不同网络资源的发展速度出现了新的特点：即网络流量和网络带宽都 在快速增长，而计算资源和存储能力相比起来却发展缓慢，尤其是存储能力每年仅 提升百分之几。因此在诸多资源中，计算和存储资源可能逐渐变为“瓶颈”。相应 地，在c s 模式中，处于体系架构的中心服务器也成为性能的“瓶颈 ，一旦中心 服务器崩溃将造成整个服务系统崩溃。 1 2 2 对等网络模式 对等网络( p e e r - t o p e e r ) 是一种全新的计算模式。在该种计算模式中，网络中 的计算机对等直接地交换共享计算机资源，其中每个结点的地位都是对等的，兼有 客户机和服务器的功能。这一点不同于传统的客户端朋& 务器模式( c s ) 。对等节点 之间通过直接互连实现信息、处理器、存储甚至高速缓存等资源的全面共享，无需 2 重庆邮电大学硕士论文 第一章绪论 依赖集中式服务器支持。对等网络系统具有自组织、容错性好、可扩展性强等特性， 这使它特别适合与广域网范围内的各种应用。 与传统的基于客户服务器的方案相比，p 2 p 系统在可扩展性上具有潜在的优 势。由于没有共享服务器的需求，故潜在的性能瓶颈可被消除，尤其当系统规模增 大的时候，由于没有与远端服务器通信时的延时，性能也有可能得到改善。 图1 2 p 2 p 模式网络结构 目前，互联网系统的计算模式正在发生从客户端服务器模式到对等计算模式的 转变。随着p c 技术、移动终端技术以及i n t e m e t 的发展，如何更好地利用所有节点 搭建更好的分布式系统自然而然地成为人们关注的问题。因此，在学术界，对等网 络成为分布式系统方向最活跃的研究领域之一。 1 3i p 网络定位技术研究现状 目前，考虑到许多大规模分布式网络应用对节点相对位置信息的需求，口网络 定位技术已逐步得到深入的研究。近年来已经提出了许多不同方案用于预测主机之 间的网络距离。 1 3 1 基于距离数据空间的网络定位方法 在f r a n c i s e t a l 的初期工作中，作者从拓扑的角度详细分析了网络距离预测中的 问题，并提出了第一个完整的解决方案，称为i d m a p s 3 1 。它是一种基础设施服务， 基于c s 网络模型。其中特殊的h o p s 服务器维护一个虚拟的因特网拓扑图，该拓 扑图包括了终端主机和一些特殊主机( 被称为追踪器t r a c e r s ) 。主机a 和主机b 之 间的距离通过以下方式来估算，即：虚拟拓扑上a 和距其最近的追踪器t 1 之间的 重庆邮电大学硕士论文第一章绪论 距离，加上b 和距其最近的追踪器t 2 之间的距离，再加上t l 和t 2 之间最短路径 的距离。随着追踪器数目的增加，i d m a p s 的距离预测准确性将会得到提高。由于 它被设计成客户朋艮务器结构的解决方案，从而终端主机可以通过询问h o p s 服务器 来得到网络距离的预测值。目前已经有部署的实验性的i d m a p s 系统。 在【4 】中，h o t z 提出基于三角剖分的启发式算法，定义系统中主机a 的距离向量 为元= 【吃l ，一，屯r ，其中，吮为主机a 到系统中信标节点的测量距离，m 是信标 节点的个数。从而主机a 与主机b 之间的网络距离l 可以表示为： m a xi 丸一吃ji 上m i n ( d 。, + 吃) 为了提取拓扑信息，r a m a s a m y 等人【5 】提出了一种b i n n i n g 机制。定义一个主机 的b i n 为系统中信标节点的序列，其中信标节点将根据到该主机的时延由小到大进 行排序。因此，一个主机的b i n 表示该主机到系统信标节点的相对距离。r a t n a s a m y 等人把这种机制应用于o v e r l a y 网络的构建和服务器选择的问题上。当一个主机要 加入当前o v e r l a y 网络或要选择某个服务器时，它会选择和自己有最相似b i n 的主机 节点。 1 3 2 基于虚拟坐标的网络定位方法 n g 和z h a n g 最早提出了基于网络坐标系统的网络定位机制，称为g n p ( g l o b a l n e t w o r kp o s i t i o n i n g ) 6 1 。它以p 2 p 网络模型为基础，讨论网络应用中的节点定位问 题。g n p 不再使用原始的网络距离空间，而是把每台主机映射到一个d 维的笛卡尔 坐标系统中，让主机节点维护一组描述它们在网络中位置的坐标( 如一组数字 集) 。这样网络距离可以通过对主机坐标进行距离函数的运算来估计。g n p 把网络 中的节点分为锚节点( 1 a n d m a r k s ) 和普通主机节点两部分。锚节点首先通过相互之 间的全测量构造初始的坐标系统，然后普通主机节点通过测量到锚节点的距离确定 自己的相对位置。g n p 具有较高的网络距离预测准确度，然而指定锚节点容易造成 固定节点上的负担过重，从而形成网络通信瓶颈。另外系统的距离预测准确度也受 到锚节点的数量和位置的影响。 n g 和z h a n g 提出g n p 算法证明了基于坐标方案的可行性，同时基于坐标的方 法简单有效，因此基于坐标系统的网络距离预测机制引起了广泛的关注和研究，从 而设计出了一系列的网络坐标系统方案。后来的研究工作主要从可扩展性和分布性 等方面考虑，提出了一些具有代表性的基于坐标系统的网络距离预测方法。 在基于锚节点结构的方案中，l i g h t h o u s e s 7 1 ，m i t h o s 引，和n p s 9 分别从采用多 个局部坐标系统、优先测量较近的邻居节点以及采用分层结构等方面对g n p 机制 4 重庆邮电大学硕士论文第一章绪论 进行了拓展。c o s t a 等人提出p i c ( p r a c t i c a li n t e m e tc o o r d i n a t e s ) i l o j ，系统中的任何 已经获得坐标的节点都可以作为锚节点，并为新加入的节点提供参考信息。因此， p i c 可以把通信和计算开销平均分布在系统的所有节点上。另外，考虑到p 2 p 网络 中可能存在的恶意节点，p i c 提出了基于三角不等式的恶意节点对抗方法，从而使 得该系统即使在恶意环境下也能维持一定的可靠性。 c o x 最初提出的网络坐标系统v i v a l d i 1 1 】【1 2 】，稍后由d a b e k 等人进行改进【1 3 】，通 过采用一个包括h e i g h t 向量的二维几何模型提高了系统的距离预测准确度。v i v a l d i 是一种完全分布式的坐标系统，通过模拟一个弹簧系统的伸缩来最优化主机节点的 坐标。它能够扩展至有大量主机参与的大规模网络应用中去，而且其网络距离预测 的准确度可与g n p 相匹敌。另外s h a v i t t 和t a n k e l 的b i g b a n g 模拟系绀川，采用 了类似于v i v a l d i 的弹簧系统，从物理的角度模拟一种势能场。但是b i g - b a n g 系统 相对于v 址d i 较为复杂，而且难以转换为分布式的。 l l e h m a n 等人首先在【i5 】中提出了一种分布式坐标系统p c o o r d ，并在【1 6 】中进一 步改进，提出了三种稳定机制，促进系统平稳地收敛至较低的网络距离预测误差。 该系统能够较好地适应主机节点动态加入以及离开的情况。 文献【1 7 1 1 8 】提出的网络坐标系统则采用了不同的嵌入空间。网络中的主机节点首 先把直接测量锚节点得到的距离作为自己的坐标，然后则采用l i p s c h i t z 嵌入，利用 主元分析法( p c a ) 降低系统维数，从而获得一个较低维数的坐标空间。 1 3 3 其他网络定位方法 b e r n a r dw 等人提出m e r i d i a n t 拶j 通过查询和测量相结合的方式进行网络定位，描 述了一种在p 2 po v e r l a y 网络中进行节点位置查询和选择的情况。每一个m e r i d i a n 节点跟踪一组固定的邻居节点，并根据到它们之间的网络距离把它们组织在按指数 增长的圆环内，以便将来对目标节点进行查询。m e r i d i a n 查询过程中的每一步路由 都仅依赖于当前的测量值，从而不会引入时延误差。但是，对应于每一次客户查询， 都会引发大量的测量开销；而且如果处于m e r i d i a n 节点所维护的圆环内成员节点变 动时刻，所得到的结果便有可能是不准确的。 c h r i s t o p h e rk 等人提出b e a c o n i n g 算法用于寻找i n t e m e t 主机的邻居节点【2 0 j ；另 外，d a v i d & k a r g e r 等人在解决寻找最近邻居节点问题时，考虑到目前越来越多的 应用不再局限于欧氏度量，从而提出了一种增长受限的测量空间等【2 1 】圆。 5 重庆邮电大学硕士论文 第一章绪论 1 4 论文结构安排 本文共分五章，各章的内容安排如下： 第一章：首先描述了本文的选题背景及意义，指出了本文的主要研究内容。然 后介绍了网络模型的发展。最后概述了p 网络定位技术的研究现状。 第二章：描述了基于虚拟坐标的m 网络定位技术的基本思想，给出了网络距离 的概念及其度量参数。然后讨论了设计网络坐标系统需要面临的挑战及其一般步骤， 并描述了几种体现系统性能的参数。详细介绍了两种具有代表性的网络坐标系统。 最后分析了网络坐标系统的优点及其应用前景。 第三章：提出了一种新的锚节点选取机制。分析了锚节点分布对网络定位的影 响，提出了针对不同锚节点数量的选取方法。当我们选取较少锚节点时，选取机制 分为了两个过程，利用了聚类方法从预选的1 s t l a n d m a r k s 中再次选取实际所需的2 n d l a n d m a r k s 作为系统的锚节点。介绍了聚类的基本概念以及常用的聚类算法。然后介 绍了著名的统计软件s p s s ，并利用它实现对1 s tl a n d m a r k s 的层次聚类。最后针对聚 类后的结果，提出了两种策略从中选取2 n dl a n d m a r k s ，并对所提出的锚节点选取机 制进行了分析和总结。 第四章：分析了锚节点数量对网络坐标系统性能的影响，并在现有工作的基础 上提出一种最小化锚节点的网络坐标系统c 1 a n d m a r k s 。为了使锚节点能有一个较好 的分布，采用了第三章提出的锚节点选取机制。然后讨论了c 1 a n d m a r k s 算法的实 现过程。最后通过m a t l a b 仿真，分别从准确性、鲁棒性、稳定性以及测量开销等方 面对c 1 a n d m a r k s 系统进行了分析，并验证了所提出的锚节点选取机制的性能。 第五章：总结了全文的内容，并提出了未来的工作。 6 重庆邮电大学硕士论文第二章基于虚拟坐标的i p 网络定位技术 第二章基于虚拟坐标的口网络定位技术 2 1 基本思想 如图2 1 所示，基于虚拟坐标的网络距离预测机制实质上就是把i p 网络中的主 机节点嵌入到某个几何空间中，并寻找一种映射关系口：h v ，使得两个主机在 该几何空间中的距离可以近似它们在网络中的真实距离。即有下列式子成立： d ( 红，1 ) d o , ，v j ) ( 2 1 ) 其中日表示口网络环境，y 为欲嵌入的k 维几何空间。d ( a ，h ，) 为网络中两个 主机根据测量得到的真实距离，d ( v ，1 ，) 为它们在几何空间中由计算得到的估计距 离。如图2 1 所示，网络中的主机啊，红，h = 矗，缟，红) ，分别对应于二维几 何空间中的节az , ，匕，巧，v = k ，k ，巧) ，从而能够得到：d ( 红，鸣) d ( h ， 9 2 ) 。 h l i p 网络 h 3 图2 1 基于虚拟坐标的网络距离预测模型 因此，构建网络坐标系统的目的就是把网络中的主机映射为几何空间中的某些 点，使主机节点可以利用它们在几何空间中计算得到的距离来近似它们在网络中的 真实距离，从而在避免大量端到端测量的情况下获得主机之间的网络距离信息。 2 2 网络距离概述 2 2 1 网络距离参数 根据不同的用途，可以对网络的多种参数进行测量，包括时延、丢包率、链路 7 重庆邮电大学硕士论文 第二章基于虚拟坐标的i p 网络定位技术 的容量和带宽、流量、连接的平均持续时间、网络拓扑等等。在我们所研究的i p 网 络定位系统中，主机间的网络距离参数通常体现为时延和带宽等。 网络的传输时延分成单向( o n e w a y ) 时延和往返( r o u n d - t r i p ) 时延。影响网 络传输时延的因素很多，主要分为三大类：1 ) 网络本身的性能，即完全独立于网络 测量方法而仅与网络本身的硬件特性相关的部分，包括网络的物理层介质、传输所 需的路由转发等分组处理的次数和速度、网络的数据链路层协议的不同实现方式等； 2 ) 测量数据包的特定性能，这与网络具体的测量方式密切相关，主要包括承载测量 报文的协议类型、报文长度、发送频率等；3 ) 当前的网络流量，网络负载比较重时， 其传输和处理速度会大大下降，此时测量的网络传输时延结果将比较大。 网络传输时延的测量主要是利用i c m p 协议实现，最典型的应用就是p i n g 。由 于i c m p 安全性不高，因此现在许多主机和防火墙过滤i c m p 分组，在这种情况下 则可以使用u d p 报文，采用类似的方法实现往返时延的测量。如果要测量网络的 单向时延，则首先需要保证发送端和目的端的时钟同步，然后根据发送端的发送时 刻和目的端的接收时刻计算单向时延。 带宽是网络的重要资源，准确、广泛地测量网络带宽对于有效利用网络、提高 网络服务质量非常重要。然而网络环境的复杂性，如链路的异构性、通信量的异构 性、路由和链路改变等，使精确测量网络带宽面临巨大困难。 带宽的概念包括链路带宽( l i n kb a n d w i d t h ) 和有效带宽( a v a i l a b l eb a n d w i d t h ) 。 链路带宽是链路自身的容量，不因链路中其他流量的存在而改变。有效带宽是某一 时刻在给定链路上发送数据可用的最大带宽，会随该链路中背景流量的变化而变化。 有效带宽是动态的，因此对它进行测量会比较困难。 2 2 2 网络距离定义 时延是最一种简单有效的距离参数，它能够很好地体现出网络的性能，并可以 用于描述许多网络应用( 如路由选择等) 所需的拓扑信息。另外时延参数也比较容 易获取，原因在于：1 ) 易于测量。发送少量的探测包即可获得很好的时延估计。2 ) 由于主机间两条不同的路径可能会有相同的时延，因此，尽管我们发送的探测包所 走的路径有可能和用户数据包实际所选的路径不同，但测量得到的时延值将仍然是 有用的。相对来说，带宽测量起来就比较困难，其花费较高，而且带宽对于路径的 选择也比较敏感单个低带宽的链路就限定了整个路径的带宽。 因此，在讨论p 网络定位技术的时候，主机间的距离通常采用时延作为参数。 在本篇论文中，我们用往返时延( r o u n d - t r i pt i m e ) ) 表示主机之间的网络距离。 在一个网络坐标系统中，距离的普遍度量 2 3 1 定义如下： 8 重庆邮电大学硕士论文 第二章基于虚拟坐标的i p 网络定位技术 当p 取不同的值时，我们就可以得到不同的距离函数。其中，一些重要的距离 函数如：曼哈顿距离厶( p ；l 时) 、欧几里德距离岛( p ；2 时) 以及切比雪夫距离l ( p = o o 时) 。切比雪夫距离l 又可以表示如下： l ( 4 ，d ，) = l i ml p ( 吐，d f ) = 如瞪i 丸，d 鹰i ( 2 3 ) 口o r卫 2 3 网络坐标系统的设计分析 2 3 1 面临的挑战 通常情况下，设计一个应用于大规模分布式网络应用的网络坐标系统，需要面 临以下的挑战： 1 ) 寻找一种测量空间使i p 网络的嵌入误差尽可能的小。一个合适的测量空间必 须能够应付i p 网络路由、传输时延以及查询等所引入的问题。 2 ) 能够扩展到有大量主机参与的场合。网络坐标系统的优势在大规模的应用中 才会发挥的更为明显；如果只是少量主机参与的场合，我们可以直接地测量主机之 间的距离。 3 ) 算法的执行尽可能是分布式的。许多应用，如基于p 2 p 的应用，都是分布式 的，而且节点的地位是平等的。通常情况下没有固有的可信赖节点专门供我们选为 参考节点。 4 ) 最小化网络探测流量。理想的网络坐标系统不应该引入任何额外的网络流量， 而是能够从应用中已有的通信活动中获取自己所需的所有信息。 5 ) 能够适应变动的网络环境。由于网络拥塞或重构等原因，主机在网络中的相 对位置可能发生变动。所设计的网络坐标系统应该能够依据这些变动周期性地更新 主机节点的坐标。 目前所提出的网络坐标系统，从不同方面满足了以上所述的部分需求，但是都 没有完全解决所有的需求问题。 2 3 2 构建网络坐标系统的一般方法 通常情况下，建立一个网络坐标系统的一般步骤为： 9 、，2q ，一p 勺 靠 一 九 。胤 ，l i i 、j 以 或 ，l 0 重庆邮电大学硕士论文第二章基于虚拟坐标的i p 网络定位技术 1 ) 选择网络中的一部分主机作为参考节点，构建初始的坐标系统； 2 ) 测量参考节点之间的往返时延( r 1 广r ) ； 3 ) 计算所有参考节点的坐标； 4 ) 普通主机测量它到参考节点的往返时延( r 1 盯) ； 5 ) 计算普通主机的坐标。 目前所提出的基于虚拟坐标的网络定位机制的不同之处主要就体现在1 ，3 ，5 步，也即参考节点的选取和坐标计算方法有所不同。最初用于预测网络距离的网络 坐标系统选择一小部分主机作为其他主机的参考节点，在后来的研究工作中逐步往 分布式方向发展，逐步淡化或放弃固定参考节点的思想，产生了许多分布式的网络 坐标系统。另外，采用什么算法计算主机节点的坐标也是设计一个网络坐标系统需 要研究的内容。 2 3 3 系统性能参数 目前所提出的网络定位系统，一般通过以下参数来衡量其性能： 1 ) 准确性： 准确性是在体现系统性能时最常用的参数，通常用节点间测量得到的距离和根 据坐标计算得到的距离之间的误差来度量，有时也可以参考系统中的节点收敛至准 确坐标所用的时间。 2 ) 鲁棒性 鲁棒性体现了系统在巨大外界压力的情况下系统的性能。人们通常较为关注的 是在极大网络流量或有恶意节点的情况下的系统性能，因为这对于p 2 p 应用来说也 是最为常见的问题文件传输可能引起突发流量，黑客也可能会趁此攻击该网络 坐标系统，影响距离预测的准确性。 3 ) 稳定性 集中式系统如g n p 的配置需要一组可信赖的节点锚节点，需要考虑锚节 点失效时对系统可能的影响；当网络发生变化时，v i v a l d i 类似弹簧系统的性能也将 受到破坏。另外网络节点的加入和离开也是经常发生的现象。因此有必要研究分析 在这些变动情况下系统的性能。 对于一个新提出的网络坐标系统，则通常选择与其他网络坐标机制进行准确性 的比较。 1 0 重庆邮电大学硕士论文 第二章基于虚拟坐标的i p 网络定位技术 2 4 网络坐标系统 基于网络坐标系统的方法由于在预测网络距离方面表现出来的优势而得到了广 泛的研究，目前已经提出了许多网络坐标系统。这些基于网络坐标系统的网络距离 预测机制大致可以分为两种类型：1 ) 基于锚节点的网络坐标系统，如g n p 6 1 、n p s l 9 1 、 p i c 1 0 】等：2 ) 基于模拟( s i m u l a t i o n ) 的网络坐标系统，如v i v a l d i 1 3 1 以及b i g - b a n g 系统【1 4 】等。下面我们将分别介绍两种比较具有代表性的网络坐标系统：g n p 和 v i v a l d i 。 2 4 1 全局网络定位系统( q 岬) g n p 6 ( g l o b a l n e t w o r kp o s i t i o n i n g ) 作为最早提出的网络坐标系统，其主要思 想在于将i n t e m e t 建模成一个几何空间( 如三维欧氏空间) ，并用此几何空间中的 一个节点来表示i n t e m e t 中任何一台主机的位置。从而任何两台主机之间的网络距 离都可以通过它们之间计算得到的几何距离来预测。如图2 2 所示。 y 。l 天2 ，y 2 , 2 ， ( x l ty “z 1 ) 奢。 皆 万 、 忒么 蹦7 ，镌 ( x 3 ，y 3 z 3 ) ( x 4 , y 4 ，7 - 4 ) l 堕兰塑些堡窒塑i 图2 2 将i n t e m e t 映射为几何空间模型 g n p 把网络中的主机分为两部分。第一部分为网络中的少量节点，称为锚节点 ( 1 a n d m a r k s ) 。它们首先在选定的几何空间中计算自己的坐标。锚节点的坐标将作 为其它节点的参考，并散布给任何想参与进来的主机节点。第二部分为系统中的普 通主机。由于能够获得锚节点的坐标，任何普通主机都可以参考锚节点而计算出自 己的坐标。 假定将i n t e m e t 映射为一个几何空间s 。主机h 在s 中的坐标表示为c ：，对 这些坐标执行运算的距离函数表示为厂s ( ) ，主机q 和致之间由计算得到的距离表 示为d s ( 通过厂s ( 四。，嚷) 得到) 。下面将详细介绍这两部分： 重庆邮电大学硕士论文 第二章基于虚拟坐标的i p 网络定位技术 1 ) 锚节点的坐标确定 这部分主要是选择网络中的一小组主机作为特殊节点，即锚节点，用于为s 中 的其它主机提供一组必需的参考坐标。如何最优地选择锚节点的位置和数量仍然是 一个开放性的问题。 假设有个锚节点，厶，“。锚节点使用i c m p 的p i n g 消息很容易测量得到 相互之间的往返时延( r t t ) ，从而构造出一个n 的时延矩阵( 沿对角线对称) 。 用如 表示主机q 和吼之间测量得到的距离a 使用之前所测量得到的距离叱l ，( f ，) ，某个主机或者个锚节点中的一员将计算所有锚节点在几何空间s 中的坐标。 目的是为n 个锚节点寻找一组坐标罐，吃，使测量得到的距离与在s 中计算得 到的距离之间的整体误差最小。用数学表示为最小化下面的目标函数厶。( ) ： 厶。( q ，咙) =占( 吒妒霞。，) ( 2 4 ) 上，山售 上1 如 l i j 其中占( ) 是误差度量函数，可以为简单的平方误差函数： 占( 吒以，旌以) = ( 吒以一露。也) 2 ( 2 5 ) 也可以为其它更为复杂的误差度量函数。误差度量的方式将会影响到最终的距离预 测准确性。 根据公式( 2 4 ) ，节点坐标的计算可以被视为多维全局最小化问题，可以由许 多已有的方法近似解决，如s i m p l e xd o w n h i l l 方法 2 4 j 。图2 3 描述了在一个2 维欧 几里德空间中有3 个锚节点时的情况。 y 。 国 ：) ( 1 - xy 1 ) 时 | | ； 、，- 、 图2 3 锚节点的坐标确定 里德空间 一旦计算出了锚节点的坐标，这些坐标连同采用的几何空间s 的标识、相应的 距离函数厂s ( ) 将被发送到任何想参与到g n p 的普通主机。 2 ) 普通主机的坐标确定 1 2 重庆邮电大学硕士论文第二章基于虚拟坐标的i p 网络定位技术 在体系结构的第二部分，普通主机根据几何空间中已经确定了的锚节点坐标， 来计算自己的坐标。为了达到这一目的，普通主机利用i c m p 的p i n g 消息测量它到 个锚节点的往返时延r 1 厂r ，并选择每条路径上的最小测量值作为节点之间的距离。 在这个阶段，锚节点只用简单地应答到来的p i n g 消息即可。普通主机利用到个锚 节点的距离测量值计算自己的坐标c 著，该坐标值使该主机到所有锚节点的距离计算 值和预测值之间的整体误差最小。表示为最小化下面的目标函数厶：( ) ： f o b , ：( 露) = 占( ，) 厶6 ，“ ( 2 6 ) 图2 4 说