一种层次化网络距离预测机制.pdf.pdf

《计算机学报》 2010 年第 2 期, 2010 , 33 ( 2)
一种层次化网络距离预测机制1
邢长友, 陈鸣
(解放军理工大学指挥自动化学院,江苏南京 210007)
摘摘摘摘要要要要: 网络坐标系统向分布式应用提供了一种高效的网络距离信息获取机制,但现有
基于单一度量空间嵌入的距离预测机制难以精确描述因特网复杂的层次结构特征,进而
导致较大的距离预测误差。提出了一种分域的 Pharos ,该
机制根据因特网结构以及性能特征将其划分为相互独立的核心预测域和边缘预测域,通
过相关边缘预测域和核心预测域内预测值迭加获取节点间距离信息。理论分析和仿真实
验显示, NetPharos 能够有效解决预测过程中短距离和长距离的相互干扰问题,提高预
测精度。
关键词关键词:网络坐标系统;距离预测;层次化结构;预测域;空间嵌入
中图法分类号中图法分类号: TP393

1 引言
因特网服务被定义为尽力而为的分组交付服务,它并不向上层应用提供不同路径的性能
信息。然而当前许多大型分布式应用都需要依赖于该信息进行性能优化,导致上述设计理念
不能适应这些新型网络应用的需求。例如,结构化 P2P 应用基于性能信息可以构造更加高
效的分布式哈希表结构[1];在多播系统中,性能信息可以协助构造更加优化的多播树[2];基于
CDN 的流媒体服务,可以根据网络性能状况选择最优服务器为用户提供服务[3];在 Skype
等需要使用中继节点桥接位于 NAT/ 防火墙后主机节点的 VoIP 系统中,性能信息能够帮助选
择具有最优性能的节点作为桥接节点,从而为用户提供最佳通话质量[4]。最后, ISP 本身也
可以通过性能信息分析因特网可达性、选路不稳定性以及检测 DDoS 攻击等。
为了获取所需性能信息,目前不少应用都设计了相应的测量机制。然而,这种解决方案
会造成诸多问题:一方面测量需要花费一定的时间,导致系统无法及时响应用户的性能信息
查询请求;另一方面如果大量用户都采用该方式将会严重侵扰网络。在各种网络性能指标中,
网络距离(往返时延)是一个非常重要而又相对容易获取的参数,因此,设计一个合适模型实
现对网络距离的有效预测具有重要的现实意义。根据网络坐标系统的基本理念,本文中我们

收稿日期: xxxx-xx-xx; 修改稿收到日期: xxxx-xx-xx. 本课题得到国家自然科学基金重大研究计划资助项目(No. 90304016) 和国家
863 高技术研究发展计划项目基金计划(No. 2007AA01Z418)资助. 邢长友, 男, 1982 年生, 博士, 讲师, 主要研究方向包括网络测
量、分布式系统等. E-mail: ******@plaust.. 陈鸣, 男, 1956 年生, 博士, 教授, 博士生导师, 主要研究领域为网络测量、网络
管理、分布式系统和网络体系结构等.
1
《计算机学报》 2010 年第 2 期, 2010 , 33 ( 2)
Pharos ,从而能够基于部分距离测量信息,通过
坐标空间嵌入机制实现网络中任意两个节点之间时延预测,为向因特网中各种应用提供网络
距离信息给出了一种解决思路。
文章按如下方式组织:首先第 2 节概述了网络距离预测相关研究工作,然后第 3 节总结
了网络坐标系统的基本概念,分析了因特网的层次结构,提出并详细描述了层次化的距离预
Pharos ;随后第 4 节基于多个性能指标 Pharos 进行了理论和仿真分析;最
后第 5 节总结了全文。
2 相关研究工作
Ng 最先提出了一种通过虚拟坐标嵌入实现网络距离预测的机制 GNP (work
Positioning) [5]。在该机制中,将因特网建模为一个欧氏空间,根据测量得到的距离关系为网
络中每个节点分配一个坐标值,不同节点间距离基于坐标值采用欧氏空间距离公式计算得
出。 BBS(Big-Bang Simulation) 将网络节点建模为势能作用下根据牛顿力学在欧氏空间中运
动的粒子,并且其势能由节点间全部的嵌入误差组成, 算法最终在总嵌入误差降到最低时终
止, BBS 克服了 GNP 算法收敛速度慢等问题[6]。 PIC 允许在构建节点坐标值的过程中动态
选择基准节点,相对于使用固定基准节点的 GNP 而言扩展性更好[7]。 Vivaldi 通过完全分布
式的结构实现坐标嵌入, 简化了网络坐标系统的部署[8]。 Shavitt 等研究了因特网距离空间的
曲率特征,提出负曲率度量空间更适合描述因特网距离,并据此构造了一种基于双曲空间的
距离预测机制[9]。 ICS( Coordinate System) [10]虽然