johnh: research teaching PAPERS software other contact about

Remote Detection of Bottleneck Links Using Spectral and Statistical Methods

Xinming He, Christos Papadopoulos, John Heidemann, Urbashi Mitra, and Usman Riaz
USC/Information Sciences Institute

Abstract

Persistently saturated links are abnormal conditions that indicate bottlenecks in Internet traffic. Network operators are interested in detecting such links for troubleshooting, to improve capacity planning and traffic estimation, and to detect denial-of-service attacks. Currently bottleneck links can be detected either locally, through SNMP information, or remotely, through active probing or passive flow-based analysis. However, local SNMP information may not be available due to administrative restrictions, and existing remote approaches are not used systematically because of their network or computation overhead. This paper proposes a new approach to remotely detect the presence of bottleneck links using spectral and statistical analysis of traffic. Our approach is passive, operates on aggregate traffic without flow separation, and supports remote detection of bottlenecks, addressing some of the major limitations of existing approaches. Our technique assumes that traffic through the bottleneck is dominated by packets with a common size (typically the maximum transfer unit, for reasons discussed in Section \refsec:spectral_testbed). With this assumption, we observe that bottlenecks imprint periodicities on packet transmissions based on the packet size and link bandwidth. Such periodicities manifest themselves as strong frequencies in the spectral representation of the aggregate traffic observed at a downstream monitoring point. We propose a detection algorithm based on rigorous statistical methods to detect the presence of bottleneck links by examining strong frequencies in aggregate traffic. We use data from live Internet traces to evaluate the performance of our algorithm under various network conditions. Results show that with proper parameters our algorithm can provide excellent accuracy (up to 95%) even if the traffic through the bottleneck link accounts for less than 10% of the aggregate traffic.

Availability

This paper is available in several formats: abstract web page with pointers and cites, PDF, paper copies can be obtained by mail to the authors. Copyright terms for this paper appear below.

Reference

He09a: Xinming He, Christos Papadopoulos, John Heidemann, Urbashi Mitra, and Usman Riaz. Remote Detection of Bottleneck Links Using Spectral and Statistical Methods. Computer Networks, 53 (3 ), pp. 279-298, February, 2009. <doi: 10.1016/j.comnet.2008.10.001>, <http://www.isi.edu/~johnh/PAPERS/He09a.html>.

@article{He09a,
	author = "Xinming He and Christos Papadopoulos and John
 Heidemann and Urbashi Mitra and Usman Riaz",
	title = "Remote Detection of Bottleneck Links Using Spectral and Statistical Methods",
	journal = "Computer Networks",
	year = "2009",
	publisher = "Elsevier Science Publishing Co., Inc.",
	volume = "53",
	number = "3",
	pages = "279--298",
	month = "February",
	doi = "	10.1016/j.comnet.2008.10.001",
	keywords = "spectral analysis, bottleneck detection",
	copyrightholder = "Elsevier Science Publishing Co., Inc.",
	url = "http://www.isi.edu/~johnh/PAPERS/He09a.html",
	pdfurl = "http://www.isi.edu/~johnh/PAPERS/He09a.pdf",
	myorganization = "USC/Information Sciences Institute",
}

Copyright

This paper is copyright © 2009 by Elsevier Science Publishing Co., Inc.. Single photocopies of single articles may be made for personal use as allowed by national copyright laws. Permission of the Publisher and payment of a fee is required for all other photocopying, including multiple or systematic copying, copying for advertising or promotional purposes, resale, and all forms of document delivery. Special rates are available for educational institutions that wish to make photocopies for non-profit educational classroom use. Permissions may be sought directly from: Elsevier Global Rights Department / P.O. Box 800 / Oxford OX5 1DX, UK / phone: (+44) 1865 843830 / fax: (+44) 1865 853333 / e-mail: permissions@elsevier.co.uk