Abstract: The problem of the Internet monitor placement is turned to that of the network topology cluster. The hierarchical clustering method set is selected to cluster the network nodes for the hierarchical characteristic of the network. An algorithm is put forward based on the difference between the network nodes, which recursively eliminates one out-degree exceptional node. Under the conditions of keeping the basics of the network topology, the proposed algorithm decreases the effect of exceptional nodes on the cluster result. We regard the maximum out-degree nodes in each cluster as the cluster centers, which are chosen as the monitors. Our simulation results show that the complete linkage method of the hierarchical clustering method set can better cluster the network nodes and the proposed algorithm can further improve the cluster result. The proposed algorithm effectively solves the problem of the Internet monitor placement.

Key words: network delay, monitor, hierarchical clustering, exceptional node