CCIPCA-OPCSC: An online method for detecting shared congestion paths

摘要

It is very useful to detect network paths sharing the same bottleneck for improving efficiency and fairness of network resource usage. Existing techniques have been designed to detect shared congestion between a pair of paths with a common source or destination point. And they are poor in scalability and not applicable to online detection. To cope with these problems, a novel method called CCIPCA-based Online Path Clustering by Shared Congestion (CCIPCA-OPCSC) is proposed to detect shared congestion paths, whose essence lies in the use of a novel eigenvector projection analysis (EPA). First, the delay measurement data of each path are mapped into a point in a new, low-dimensional space based on the correlation among paths reflected by the eigenvectors and eigenvalues in the process of PCA. In this new space, points are close to each other if the corresponding paths share congestion. CCIPCA is also introduced to compute the eigenvectors and eigenvalues incrementally. Second, the clustering analysis is applied on these points so as to identify shared congestion paths accurately. CCIPCA-OPCSC has low computational complexity and can fulfill the requirement of online detection. This method is evaluated by NS2 simulations and experiments on the PlanetLab testbed over the Internet. The results demonstrate that this novel method is feasible and effective.