上海公共研发服务平台
         登录 | 注册会员中心  | 设为首页 | 联系我们
 
软件首页 > 行业动向
网络距离预测机制的兴起
上海市浦东科技信息中心   石习    2010-09-30
关键字:网络距离预测, 网络距离 浏览量:

         近年来,随着网络技术的发展,新的网络应用不断涌现,其中具有代表性的包括P2P 文件传输、网格、CDN(内容分发网络)和在线网络游戏等。在这些应用中,由于能够提供相同服务的服务器不止一个,用户在请求某项服务时可以从中选择一个具有更好性能的服务器。因此,快速、准确地获得底层IP 网络的时延、丢包率和可用带宽等状态信息,就可以采用相应措施提高这些网络应用的性能。例如,在P2P 应用中,当资源发现机制发现多个对等实体拥有所请求的内容资源时,网络性能信息可以帮助它决定访问哪个对等实体的资源效率最高。

         正是因为网络性能信息的重要性,许多应用系统在实现中自行设计了测量机制,独立测量所需的网络性能信息。然而,测量需要花费一定的时间,造成系统无法及时响应用户的性能信息查询请求;另一方面,如果大量用户都采用这种方式将会严重侵扰网络。比较好的做法是设计实现一种高效的网络性能测量预测机制,统一获取网络性能信息并发布为公众所用。在各种指标中,RTT(往返时延)是一个重要而又相对容易获取的参数。为此,人们提出了多种网络距离预测技术,基于有限的测量信息预测网络中任意两个节点之间的时延信息,从而降低获取网络距离信息的复杂性,为向因特网中各种应用提供网络距离信息给出了一种解决思路。

          一、 网络距离预测基本概念及分类

          1. 网络距离值预测和网络邻近度估计

          根据获取节点间距离方式的不同,网络距离预测可以分为网络距离值预测和网络临近度估计两大类。前者目标是给定网络中任意两个节点,系统均通过预测方式尽可能精确地计算出它们之间的距离值;后者并不预测节点间确切的距离值,而是采用一定的算法,根据用户请求寻找出满足某些条件的一个或者一组近距离邻居节点,进而通过直接测量方式获取到该节点或节点集的距离。两种技术各有优缺点,网络距离值预测技术获取节点间距离比较简单,且测量负载较小,但其预测精度相对较低;而网络临近度估计技术通过一定算法估计出可能的临近节点,最终到目标节点的距离由直接测量获得,因此其精度较高,但测量负载相对较大。

网络邻近度估计

          2. 基于虚拟坐标预测和基于网络拓扑结构预测

         基于虚拟坐标的预测技术又被称为网络坐标系统,它采用空间嵌入的方式将因特网距离空间嵌入到一个几何空间中,每个网络节点在该几何空间中分配一个坐标,不同节点间的距离利用其坐标值通过空间距离公式计算得出。基于网络拓扑结构的预测技术则认为网络拓扑对距离预测有重要影响,它首先通过AS 连接关系或者测量数据构建因特网拓扑地图,然后基于该拓扑地图预测节点间路径,并根据路径预测结果估计其距离。

基于虚拟坐标的网络距离预测技术

          3. 基于基准节点预测和基于物理模拟预测

         根据距离预测机制采用的坐标优化思想不同,可以将基于虚拟坐标的距离预测技术进一步划分为基于基准节点(landmark-based)和基于物理模拟(simulation-based)两大类。在基于基准节点的距离预测机制中,新节点加入系统后,首先测量到基准节点的距离,然后采用优化算法基于该距离和基准节点坐标获取自身在系统中的坐标;而基于物理模拟的距离预测机制则将网络建模为一种特定的物理系统,网络节点在该物理系统中受到某种力的作用产生运动,最终达到一种平衡状态。此时,节点位置即反映了其在网络中的位置关系。

基于基准节点的虚拟坐标空间嵌入

          二、 网络距离预测技术的应用

         1. 基于传感器的分布式网络距离预测

         针对Internet 环境中基于网络坐标估计节点间网络距离的问题,利用任意播机制分布式的网络坐标预测算法Cocast :所有用户节点均加入一个结构化Peer2to2Peer 对等网;对等网中任意的节点均可以发送网络坐标任意播查询消息,该消息被转发到多个负责坐标计算的用户节点,这些用户节点分布式地预测消息发起节点坐标,最终消息发起节点获得一个综合的坐标位置。Cocast 基于网络坐标任意播选择提供位置估计的用户节点,利用层次化网络嵌入预测坐标位置,借助位置融合传感器机制过滤恶意节点的影响。实验表明Cocast 具有可扩展、快速收敛、渐增精度、抗恶意节点破坏等优点。

          Cocast 的主要部件包括基于DHT 的分布式ASN 查找子图,基于ASN 排序启发式的网络坐标任意播服务,层次化网络嵌入和位置融合机制四部分。

         ASN 查找子图作为Cocast 网络坐标任意播查询的基础设施,主要提供为请求者定位一组优化的ASN 节点联系信息功能。ASN 查找子图每个节点具有一个本地缓存Cache,以存放一组ASN 节点联系信息。ASN 查找子图通过ASN 发布P响应过程构建。我们选一个特定标识符Root 作为ASN 查找子图标识符,记“维护”该Root 标识符的节点为根节点。任意播查询消息包括:用户当前联系信息( IP 地址,端口,当前坐标位置,坐标差错程度等) ,请求的ASN 节点总数K,当前已存入消息中的ASN 联系信息。Cocast 利用层次化网络嵌入来解决坐标位置更新,主要包括ASN2ASN 网络嵌入和SN2ASN 网络嵌入两个过程,均采用基于“推力”模拟的CoPush 算法,以“推”的方式预测坐标位置。Cocast 采用位置融合传感器来提高网络嵌入过程的容错性和稳定性。每个ASN 节点i 位置估计的响应消息包括:ASN 节点当前坐标posi,用户的新坐标nposi,当前坐标距离与网络距离的偏差度diff i

          不同传感器的网络坐标预测精度对比:

          考察三类位置融合传感器(Median Sensor ,Min Sensor , Average Sensor) 在没有恶意节点情况下的性能。每个节点平均进行10 次探测。不同传感器的相对差错CDF(Cumulative Distribution Function ,累积分布函数) 分布如图所示。

         结果说明: (1)Min Sensor 和Median Sensor 相对差错均低于Average Sensor ,平均低20 %以上; (2) 采用CoLandmark 计算ASN 节点初始坐标可以有效降低节点的相对差错程度,图(b) 中每类传感器相对于图(a) 中的该类传感器平均相对差错降低约30 %。

          2. 因特网层次化距离预测机制NetPharos

          因特网的层次化结构导致网络性能分区域的不均匀,进而影响其时延分布模式。 在核心网络中,高速路由器通过专用高速链路相连,所以网络时延状况相对稳定;而在边缘网络,由于节点数量很多,网络带宽往往受限,因此网络时延变化范围较大、变化速率较快。 例如,目前广泛使用的DSL 以及Cable因特网接入方式性能特征与核心网络性能特征有很大区别,其中由于排队等因素使得网络节点间时延变化范围具有近4 个数量级的差别。 并且这种层次化网络结构也导致因特网选路的层次性,例如,当前存在不同的域间以及域内选路协议,使得因特网端到端路径并非时延意义上的最优路径,因此节点间距离会违反三角形不等式的约束,导致无法通过任何一种度量空间对其进行精确描述。

          在Net Pharos 中,根据因特网的结构以及性能特征,将整个因特网划分为边缘网络与核心网络两部分,核心网络作为一个整体构建坐标嵌入空间,边缘网络按照网络距离、所属关系等限制分区域构建独立的坐标空间,不同空间内网络节点坐标值之间相互独立。 同时,可以根据网络距离特征,独立地为每个预测域选择最佳嵌入空间以及预测结果更新频率等。 例如,由于核心网络距离相对稳定,同时节点距离违反三角形不等式等情况很少见,因此欧氏空间就能够很好地实现嵌入。 而考虑到边缘网络通常具有的类树型拓扑,树型空间可能更加适合边缘网络等。 在距离预测过程中,通过“边缘2核心2边缘”度量空间内距离迭加获得网络节点间距离。

基于网络层次结构的预测域划分

         三、 网络距离预测技术未来研究方向

         未来,网络距离技术还需要解决下列问题:

          (1) 网络距离特征及其对嵌入空间选择的影响

          严格来说,由于违反对称性以及三角不等式约束,因特网距离空间不满足测度空间的定义。因此,任何一种基于虚拟坐标的距离预测机制都是对网络距离的一种近似,选择合适的嵌入空间对预测精度有重要影响。与传统PCA 分析结论不同,网络距离空间具有非常低的维度[32]。也有研究指出,Internet 选路空间具有指数扩张速度,因此,多项式扩张速度的欧氏空间难以对其进行精确描述等。如何利用这些特性选择更好的嵌入空间实现距离预测仍需要进一步探讨。

不同距离预测机制研究对比

          (2) 距离预测新机制的研究

          现有的各种距离预测机制的内在缺陷限制了预测精度的提高和在因特网中的大规模应用,因此需要探讨新的距离预测机制和解决方案。例如:考虑到因特网层次化结构对网络性能的重要影响,一个可行的研究方向就是在预测过程中充分利用因特网边缘-核心-边缘的网络结构信息将网络划分为多个预测域,通过分域的方式独立为每个预测域构造距离预测模型,避免多个域间时延分布的相互干扰;其次,因特网节点间距离呈现典型的分簇特性,同时,簇内节点间的距离违反三角不等式约束情况更加严重。因此,可以考虑如何利用这种特性构建新的距离预测机制,提高预测精度;再次,因特网选路对节点间距离有重要影响,可以考虑利用选路信息提高预测的精度。另外,网络层析成像(network tomography)[34,35]能够通过端到端测量推断链路级的时延、丢包率等性能参数,它广泛应用于网络故障诊断、拓扑发现等研究中,如何将这一技术与距离预测结合也值得进一步探索。

          (3) 多种网络性能参数的测量预测

         当前,大多数距离预测机制仅仅能够针对网络往返时延进行预测。然而,往返时延只是影响网络应用性能诸多因素中的一个,广义的网络距离应当包括诸如可用带宽、丢包率、时延抖动等多种性能参数。与往返时延是一种加性参数不同,可用带宽为凹性参数,丢包率为乘性参数,简单利用空间嵌入技术将这些参数映射到诸如欧氏空间这样的几何空间中会导致较大的预测误差。因此,如何基于不同性能测度的特性设计合适的模型实现相应性能参数的预测仍需要进一步研究。

          (4) 距离预测系统的安全性

          目前,大多数的预测机制都假设参与节点是可以信任的,如果网络中出现恶意节点提供虚假的距离信息,将严重降低距离预测精度甚至导致整个预测系统的失效。在基于固定基准节点以及集中式结构提供距离预测服务的系统中,相应基准节点或中心服务器又会面临各种攻击的威胁。能否有效防范这些问题,直接影响距离预测服务在网络中的部署。目前,有关这方面的研究刚刚起步,在进一步的研究中可以借鉴分布式系统设计中的概念,构建实用的安全性距离预测系统。

          (5) 构建完善的因特网性能服务体系结构

          随着网络技术的发展,越来越多的网络应用需要依赖因特网性能信息提高自身性能。设计一种标准化的性能服务模型,以通用的方式向因特网端用户和各种网络应用提供性能服务变得日益重要。网络距离预测为实现这样一种服务提供了部分解决方案,从本质上讲,距离预测的最终目标是协助优化分布式应用的性能。目前,围绕如何优化P2P 等应用的性能出现了一些探讨,其中典型机制包括P4P[37]、基于指导的ISP-P2P 协作机制等,进一步的研究应当结合网络架构和应用结构两方面综合考虑。设计一个精确、可靠的因特网性能服务体系结构是下一步的重要研究方向,也是网络距离预测研究的根本目的所在。

参考文献:

[1]网络距离预测技术研究 王意洁 李小勇 软件学报 2009

[2]网络距离预测技术 邢长友 陈鸣 中国科学技术 软件学报 2009

[3]一种层次化网络距离预测机制 邢长友等 计算机学报 2010

[4] Cocast:一种基于传感器的分布式网络距离预测任意播算法 王意洁等

国防科技大学学报 2007


 评论加载中...
  返回上一页】【 】【关闭
上一篇:XML技术的应用与发展
下一篇:中国长城计算机集团公司下属公司专利情况
首页 * 软件首页 * 行业动向
Rss种子地址:
在线阅读器
直接订阅:
订阅到鲜果 订阅到抓虾 netvibes google reader my yahoo Rojo Newsgator bloglines 订阅到有道 订阅到QQ邮箱
注册用户才能使用该功能,请您登录!
请您选择要放入情报购物车的内容!
3秒后,自动关闭此窗口

查看您已经收藏的文章>>

3秒后,自动关闭此窗口

查看您已经收藏的栏目>>
关于我们  |  网站地图  |  问题咨询  |  用户协议  |  法律声明  |  服务机构
版权所有 © 2009-2015 上海图书馆上海科学技术情报研究所
沪ICP备05017201号-6