MRTG in Fourier Space

Anton Kapela tkapela at gmail.com
Thu Apr 23 21:48:54 UTC 2009


Gents,

On Tue, Apr 21, 2009 at 5:30 PM, Dave Plonka <plonka at doit.wisc.edu> wrote:
>
> Hi Crist,
>
> On Tue, Apr 21, 2009 at 05:12:04PM -0700, Crist Clark wrote:
>>
>> Has anyone found any value in examining network utilization
>> numbers with Fourier analyses? After staring at pretty

In short, yup!

>> there are some interesting periodic characteristics in the
>> data that could be easily teased out beyond, "Well, the

Indeed, there are. Interesting things emerge in frequency (or phase)
space - bits/sec, packets/sec, and ave size, etc. - all have new
meaning, often revealing subtle details otherwise missed. The UW paper
[Barford/Plonka et. al] is one of my favories and often referenced in
other publications.

Along similar lines, I presented a lightning talk at nanog that
demonstrates using windowed Ft's (mostly Gaussian or Hamming) in
three-axis graphs (i.e. 'waterfalls') available in common tools
(buadline, sigview, labview, etc) for characterizing round trip times
through various network queues and queue states. Unexpectedly,
interesting details regarding host IP stacks and OS scheduler behavior
became visible.

Find the talk slides and video here (look for 'kapela'):

http://www.nanog.org/meetings/nanog37/agenda.php

>> A quick Google search turned up nothing at all.

Signal analysis, sadly, isn't as fun as going shopping or posting to
webhosting talk, etc. so you won't likely find much there.

> Such techniques are used in the are of network anomaly detection.
> For instance, a search for "network anomaly detection" at
> scholar.google.com will yield very many results.

I would also mention citeseer (http://citeseer.ist.psu.edu/) and ieee
explore (http://ieeexplore.ieee.org) - there's lots of related
application of Ft's and wavelet/fir filters in various disciplines,
all of which can apply to the analysis of time-series data.

> is one such work.  We mention that we use wavelet analysis rather
> than Fourier analysis because wavelet/framelet analysis is able
> to localize events both in the frequency and time domains, whereas
> Fourier analysis would localize the events only in frequency, so an
> iterative approach (with varying intervals of time) would be necessary.
> In general, this is the reason why Fourier analysis has not been a
> common technique used in network anomaly detection.

I want to suggest that time windowed Ft might be a reasonable middle
ground, certainly for Crist's case. Naturally, the trade-offs will be
in frequency accuracy (ie. longer window) vs. temporal accuracy (ie.
short window). Another solution for your needs might be cascaded FIR
"bandpass" filters, but again, you're subject to time/frequency error
trade-offs as related a filter's bandwidth.

While you're at it, consider processing your time series data into
histogram stacks, or nested histograms. I haven't specifically seen a
paper covering this, but another UW gent (DW, are you reading this?)
used to process their 30 second ifmib data into a raw .ps file, and
printed this out weekly/daily. The trends visible here were quite
interesting, but I don't think much further work was done to see if
anything super-interesting was more/less visible in this form than
traditional ones.

-Tk




More information about the NANOG mailing list