王占丰，陈鸣，邢长友，白华利，魏祥麟

（解放军理工大学 指挥自动化学院，江苏 南京 210007）

1 引言

在因特网时延空间中，违反三角形不等式(TIV,triangle inequality violation)的现象已被许多网络测量数据集所证实[1～5]。TIV是指以节点间的往返时延(RTT, round trip time)作为距离测度，则网络中任意3个节点构成的三角形中2边之和不大于第3个边。通常认为 TIV现象是由低效路由策略（routing inefficiency）和网络结构导致的[1～3]。TIV现象使得因特网时延建模变得举步维艰，TIV现象严重的数据集嵌入时误差较大[4]。如何消除或缓解TIV的影响成为当前因特网时延空间建模（或网络坐标系统）研究的热点。

文献[1]利用时延较小时 TIV严重性较轻这一现象，提出了一种基于时延阈值的层次化 Vivaldi因特网时延空间模型。文献[5]进一步分析了时延大小和TIV的关系，发现这种关系并不明显，为减小TIV导致的预测误差，每个节点在选择邻居节点时，选择那些使预测误差最小的节点作为邻居节点，以获得最佳嵌入坐标。文献[6]分析了因特网时延空间的聚簇（cluster）特性，指出TIV在不同的节点簇之间比较严重，而在簇内则比较轻。这种方法虽然保证了坐标系统的稳定性，却限制了该算法的适用范围。文献[7]同样利用因特网时延空间TIV的聚簇特性，提出了一种双层因特网时延空间模型。文献[8]使用一种基于决策树的有监督学习方法来判定TIV是否发生，其原理是将时延系统的预测值与实际测量值的统计量作为输入样本，通过标记的TIV来训练决策树，最后给出一颗TIV判定树。

上述算法尽管表现形式不同，但都是通过将因特网时延空间划分为不同粒度的子空间，以减轻数据集中的TIV严重程度。……