Gents, On Tue, Apr 21, 2009 at 5:30 PM, Dave Plonka <plonka@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