Hierarchical Clustering for Network Topology Identification

Project Title: Hierarchical Clustering for Network Topology Identification

PI Involved: Robert D. Nowak
Associate Professor, Electrical & Computer Engineering, University of Wisconsin - Madison

Student: Rui M. Castro
Ph.D. Candidate, Electrical & Computer Engineering, Rice University, Houston, TX

Project Description

We have developed a new method for hierarchical clustering. Unlike other existing clustering schemes, our method is based on a generative, tree-structured model that represents relationships between the objects to be clustered, rather than directly modeling properties of objects themselves. In network topology identification, this generative model naturally captures the physical mechanisms responsible for relationships among end-hosts. The new clustering method provides a means for dealing with errors in the similarity matrix, simultaneously promoting two desirable features in clustering: intra-class similarity and inter-class dissimilarity. Experiments demonstrate that this offers improved topology identification performance compared to existing methods. For more information please see [1] and [2].

Fig.1 : Sandwich probing scheme for topology identification.


(a) Traceroute topology	(b) Topology inferred using ALT

(c) Topology inferred using MCMC techniques

Fig.2 : Comparison between the 'traceroute' topology and the estimated topologies for an Internet experiment: (a) The topology of the network used for Internet experiments, obtained using 'traceroute'. (b) Estimated topology using the ALT algorithm. (c) MPLT obtained using MCMC techniques.

References

1. R. Castro, M. Coates, and R. Nowak, "Likelihood Based Hierarchical Clustering," IEEE Transactions on Signal Processing, August, 2004.

2. M. Coates, R. Castro, R. Nowak, and Y. Tsang, "Maximum Likelihood Network Topology Identification from Edge-Based Unicast Measurements," Proc. of ACM Sigmetrics, Marina Del Ray, California, June, 2002.