基于测量聚类的网络拓扑推断算法

为了减少基于端到端时延的拓扑推断算法中产生的测量流量,根据网络中端到端时延的特点,提出了一种测量聚类算法和两阶段拓扑推断算法.测量聚类算法在测量时首先粗略测量网络节点的端到端时延,根据时延对节点进行聚类,然后根据节点的聚类测量节点对的端到端时延并计算节点相关性,最后通过两阶段拓扑推断算法推断网络拓扑结构.理论证明了测量聚类算法能够有效减少测量产生的测量流量并通过NS2进行了仿真,仿真结果表明测量聚类算法和两阶段拓扑推断算法在有效减少测量流量的情况下能够正确地推断网络的拓扑结构.

Network topology inference algorithm based on cluster measurement

In order to reduce the measurement traffic in network topology inference algorithms based on end to end delay,a cluster measurement method and two step topology inference algorithm are proposed.The cluster measurement method first clusters the network nodes by simple measurement and then measures end to end delay of node pairs,finally the correlation between nodes is calculated and network topology is inferred by two step topology inference algorithm.The cluster measurement method can reduce the measurement traffic greatly,which is validated theoretically.At last the effectiveness of cluster measurement method and two step topology inference algorithm are validated through simulations by NS2.The results of simulation illustrate that the cluster measurement method and two step topology inference algorithm can infer network topology correctly and reduce the measurement traffic greatly.