支持反三角嵌入的松弛度量空间网络坐标算法

A TIV Preserved Network Coordination Algorithm in Relaxed Metric Space

网络坐标是根据网络测量时延将节点嵌入虚拟度量空间,根据坐标位置预测节点时延的模型和算法.然而通过网络测量发现互联网中广泛存在非对称和反三角(Triangle Inequality Violation,TIV)时延,度量空间固有的对称性和三角形不等性在本质上无法体现互联网时延的真实特征.特别是对利用反三角属性建立优化中继路由的应用,传统的网络坐标算法无法支持.为此,该文提出一种基于松弛度量空间的网络坐标模型,利用KL散度距离替代欧式距离定义节点时延,并设计了分布式网络坐标算法KL_vivaldi.通过理论分析与仿真表明:算法支持非对称时延和TIV的预测,提高了时延的预测精度,拓展了网络坐标算法的应用领域.

Network coordination is a general model to embed internet nodes into metric space in order to predict the delay between node pairs.However,the nature property of symmetry and triangle inequality of metric space cannot preserve the asymmetry delay and Triangle Inequality Violation（TIV）phenomena which are widely discovered by network measurement.Therefore the usability and prediction accuracy of network coordination are limited especially in the scenarios to explore the shorter relay path based on TIV.To preserve the TIV and asymmetry delay property,a network coordination model in relaxed metric space generated by KL divergence distance is proposed,and a distributed algorithm named KL_vivaldi is designed.Theory analysis and simulations show that the KL_vivaldi provide the capability of TIV predication as well as promotion of prediction accuracy,therefore the application scale of network coordination is expanded.