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

citation

Xinming He, Christos Papadopoulos, John Heidemann, Urbashi Mitra and Usman Riaz 2008. Remote Detection of Bottleneck Links Using Spectral and Statistical Methods. [PDF]

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.

reference

@unpublished{He08a,
  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},
  note = {to appear, Computer Networks},
  year = {2008},
  sortdate = {2008-09-01},
  project = {ant},
  jsubject = {chronological},
  month = sep,
  jlocation = {johnh: pafile},
  keywords = {spectral analysis, bottleneck detection},
  url = {https://ant.isi.edu/%7ejohnh/PAPERS/He08a.html},
  pdfurl = {https://ant.isi.edu/%7ejohnh/PAPERS/He08a.pdf},
  myorganization = {USC/Information Sciences Institute}
}