Remote Detection of Bottleneck Links Using Spectral and Statistical Methods

Remote Detection of Bottleneck Links Using Spectral and Statistical Methods

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

Xinming He, Christos Papadopoulos, John Heidemann, Urbashi Mitra and Usman Riaz 2009. Remote Detection of Bottleneck Links Using Spectral and Statistical Methods. Computer Networks. 53, 3 (Feb. 2009), 279–298.

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 \emphpassive, operates on \emphaggregate traffic without flow separation, and supports \emphremote 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 5.1. 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.

Reference

@article{He09a,
  author = {He, Xinming and Papadopoulos, Christos and Heidemann, John and Mitra, Urbashi and Riaz, Usman},
  title = {Remote Detection of Bottleneck Links Using Spectral and Statistical Methods},
  journal = {Computer Networks},
  year = {2009},
  sortdate = {2009-02-01},
  project = {ant, madcat, nocredit},
  jsubject = {spectral_network},
  publisher = {Elsevier Science Publishing Co., Inc.},
  volume = {53},
  number = {3},
  pages = {279--298},
  month = feb,
  location = {johnh: pafile},
  doi = {	10.1016/j.comnet.2008.10.001},
  keywords = {spectral analysis, bottleneck detection},
  copyrightholder = {Elsevier Science Publishing Co., Inc.},
  copyrightterms = {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
  },
  url = {http://www.isi.edu/%7ejohnh/PAPERS/He09a.html},
  pdfurl = {http://www.isi.edu/%7ejohnh/PAPERS/He09a.pdf},
  myorganization = {USC/Information Sciences Institute}
}

Copyright

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