Scalable clustering of Internet paths by shared congestion

Min Sik Kim, Taekhyun Kim, Yong June Shin, Simon S. Lam, Edward J. Powers

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)


Internet paths sharing the same bottleneck can be identified using several shared congestion detection techniques. However, all of these techniques have been designed to detect shared congestion between a pair of paths. To cluster N paths by shared congestion, a straightforward approach of using pairwise tests would require O(N2) time complexity. In this paper, we present a scalable approach to cluster Internet paths based on DCW (Delay Correlation with Wavelet denoising) which does not require a common end point between paths. We present a function to map each path's measurement data into a point in a multidimensional space such that points are close to each other if and only if the corresponding paths share congestion. Because points in the space are indexed using a tree-like structure, the computational complexity of clustering N paths can be reduced to O(N log N). The indexing overhead can be further improved by reducing dimensionality of the space through wavelet transform. Computation cost is kept low by reusing for dimensionality reduction the same wavelet coefficients obtained in DCW. Our approach is evaluated by simulations and found to be effective for a large N. The tradeoff between dimensionality and clustering accuracy is shown empirically.

Original languageEnglish
Title of host publicationProceedings - INFOCOM 2006
Subtitle of host publication25th IEEE International Conference on Computer Communications
Publication statusPublished - 2006
EventINFOCOM 2006: 25th IEEE International Conference on Computer Communications - Barcelona, Spain
Duration: 2006 Apr 232006 Apr 29

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


OtherINFOCOM 2006: 25th IEEE International Conference on Computer Communications

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Electrical and Electronic Engineering


Dive into the research topics of 'Scalable clustering of Internet paths by shared congestion'. Together they form a unique fingerprint.

Cite this