The large size and complexity of today’s networks present many scalability challenges for various tasks such as network monitoring, fault localization, distance estimation, etc. A subset of these problems can be addressed by the divide and conquer approach of dividing the network into smaller manageable networks and building an overall solution over these smaller networks. In this paper we present algorithms to intelligently divide the network into smaller sub-networks. We systematically define the problem of finding minimal number of small-size clusters, and present a reduction of this problem to the Minimum Vertex Cover problem. We then use this reduction to present two algorithms that vary in their optimality and execution time. We present extensive experimental evaluation to evaluate the proposed algorithms on different network topologies. We have introduced the proposed approach in [10]. This paper presents a more detailed explanation of the proposed approach with more illustrations and examples. This paper also extends the approach multiple clustering criteria.

1. Cooperative association for Internet data analysis (CAIDA). the skitter project. Technical report, http://www.caida.org/tools/measurement/skitter/index.html, 2001.
2. P. Barham, R. Isaacs, R. Mortier, and D. Narayanan. Magpie: Online modeling and performance-aware systems. In 9th conference on Hot Topics in Operating Systems, Berkeley, CA, USA, HOTOS’03, 2003.
3. A. Bouloutas and P. Gopal. Clustering schemes for network management. In INFOCOM, pages 111–120, 1991.
4. S. Jamin, C. Jin, A. R. Kurc, D. Raz, and Y. Shavitt. Constrained mirror placement on the Internet. In INFOCOM, pages 31–40, 2001.
5. D. Jeswani, N. Korde, D. Patil, M. Natu, and J. Augustine. Probe station selection for robust network monitoring. In Student Research Symposium, International Conference on High-Performance Computing, Kochi, India, Dec. 2009.
6. R. Kumar and J. Kaur. Efficient beacon placement for network tomography. In Internet Measurement Conference, IMC, 2004.
7. M. Natu and A. S. Sethi. Probe station placement for robust monitoring of networks. Journal of Network and Systems Management, 2007.
8. M. Steinder and A. S. Sethi. Multidomain diagnosis of end-to-end service failures in hierarchically routed networks. IEEE Transactions on Parallel and Distributed Systems, 8(3), Mar. 2007.
9. W. Theilman and K. Rothermel. Dynamic distance maps of the Internet. In IEEE INFOCOM’2000, Mar 2000.
10. S. Krishnan, R. Maheshwari, P. Birla, M. Natu, Network Clustering for Managing Large Scale Networks, In proceedings of ICTSM, Mumbai, 2011.
11. A. Medina, A. Lakhina, I. Matta, and John Byers. Brite: An approach to universal topology generation. In International Workshop on Modeling, Analysis and Simulation of Computer and Telecommunications Systems -MASCOTS’01, Cincinnati, Ohio, Aug. 2001.
12. H. C. Ozmutlu, N. Gautam, and R. Barton. Managing end-to-end network performance via optimized monitoring strategies. Journal of Network and System Management, 10(1), 2002
13. I. Rish, M. Brodie, S. Ma, N. Odintsova, A. Beygelzimer, G. Grabarnik, and K. Hernandez. Adaptive diagnosis in distributed systems. IEEE Transactions on Neural Networks, 6(5):1088–1109, Sep. 2005.

Network clustering Network management Scalable networks