algorithm - 检测网络流周期性的有效方法

Question

我有很多 netflow 数据(i.e src_ip, dest_ip, beg_time, end_time, data_size, etc)，其中一些是定期发生的，我想找出来。

考虑我有n 个netflow（可能在 10^6 左右），其中m个是周期性的。我怎样才能找到哪些是周期性的？

我可以写一个代码，但它至少会是 O(n^3 logn)，这在 10^4 个 netflow 之后将永远需要。

我已经搜索过它，但找不到任何东西。

注意：可以考虑数据是按照开始时间排序的，开始时间是32位无符号整数（c++中的uint32）

更正：src_ip是唯一的，dest_ip不是唯一的，time for periodicity是未知的。可能是 5 分钟，也可能是 5 天。您可以忘记src_ip, dest_ip, end_time, data_size流的其他属性。我只是在寻找开始时间是周期性的事件，你可以考虑，我已经排除了不相关的事件，比如不同的 src_ip，等等......

任何帮助将不胜感激，

谢谢

Answer 1

我会尝试在与您的数据相对应的信号上计算 FFT。

例如，我会将块beg_time=1、end_time=5、data_size=100 转换为幅度为 100 的 1 到 5 个时间单位的方脉冲。

如果你想一起分析所有东西，你可以叠加你得到的所有脉冲。

如果将所有内容放在一起没有意义，则仅叠加来自相同src_ip或来自同一对的脉冲src_ip和dst_ip。

然后对通过叠加获得的信号进行 FFT，看看频域中是否有明显的峰值，或者看起来都是随机的，没有突出的峰值。

FFT 在 O(n*log(n)) 时间内运行，其中n是信号样本的数量。

我确信必须有更好的方法来做到这一点，但它可能值得一试。