Detecting periodic patterns in internet traffic with spectral and statistical methods

Unrestricted Internet traffic contains a rich set of periodic patterns. Examples include regular packet transmissions along bottleneck links, periodic routing information exchange, and periodicities inside Denial-of-Service attack streams. Analyzing such periodic patterns has wide applications, including a better understanding of network traffic dynamics, diagnosis of network anomalies, and detection of Denial-of-Service attacks. However, current understanding of periodic behavior in aggregate traffic is quite limited. Many previous approaches often analyze traffic on a per-flow basis, and are not suited to analyze high speed aggregate traffic. In addition, a number of approaches only indicate that they may reveal periodic patterns, but fall short of proposing automatic detection algorithms and quantitatively evaluating their performance.; This thesis explores the application of spectral and statistical methods to detect periodic patterns in Internet traffic. In our approach we first apply spectral techniques to obtain the traffic spectrum, and then use algorithms based on rigorous statistical methods to automatically detect periodic patterns from the traffic spectrum. One salient feature of our approach is that it operates at the aggregate traffic level and does not require flow separation.; We first carry out controlled lab experiments to demonstrate the spectral characteristics of various periodic patterns. We then propose four non-parametric detection algorithms and evaluate their performance using real-world Internet traffic. Results show that one of them, the Top-Frequency Algorithm, is the best choice in terms of detection performance and algorithm simplicity. It can provide excellent accuracy (up to 95%) for detecting the periodic pattern caused a bottleneck link even when the traffic through the bottleneck accounts for less than 10% of the aggregate traffic observed at the monitoring point.; We also investigate two extensions to our algorithms. The first one is to utilize harmonics, andthe second one is to have parametric detection that considers the variation of traffic spectra according to other factors, such as traffic volume. Evaluation results show that we can get significant improvement by considering harmonics for traffic similar to the training data and marginal improvement by considering traffic volume for parametric detection.

无限制的互联网流量蕴含着丰富的周期性模式。例如瓶颈链路间的常规数据包传输、周期性路由信息交换，以及拒绝服务（Denial-of-Service, DoS）攻击流内部的周期性特征。对这类周期性模式的分析具备广泛应用场景，包括深化对网络流量动态特性的理解、网络异常诊断，以及拒绝服务攻击检测。然而，当前对聚合流量（aggregate traffic）中周期性行为的认知仍较为有限：诸多既往研究方法通常采用按流（per-flow）分析的方式，难以适配高速聚合流量的分析需求；此外，不少相关方法仅提及可挖掘周期性模式，却未提出自动化检测算法，也未对算法性能开展定量评估。本论文探讨了利用频谱技术（spectral techniques）与统计方法检测互联网流量周期性模式的应用路径。所提方案首先通过频谱技术获取流量频谱，随后基于严谨的统计方法设计算法，从流量频谱中自动识别周期性模式。该方案的显著特点之一是直接在聚合流量层面开展分析，无需进行流分离操作。研究首先通过受控实验室实验，验证了各类周期性模式的频谱特征。随后本文提出四种非参数化检测算法（non-parametric detection algorithms），并利用真实互联网流量对算法性能进行评估。实验结果表明，其中的顶频算法（Top-Frequency Algorithm）在检测性能与算法简洁性两方面均表现最优。即便瓶颈链路的流量仅占监测点观测到的聚合流量的10%以下，该算法对瓶颈链路引发的周期性模式的检测精度仍可达95%，具备出色的检测性能。此外，本文还针对所提算法开展了两项扩展研究：其一为利用谐波特征进行优化，其二为引入参数化检测（parametric detection）机制，该机制可根据流量体量等其他因素调整流量频谱的变化特性。评估结果显示，针对与训练数据相似的流量场景，利用谐波特征可实现检测性能的显著提升；而在参数化检测中引入流量体量因素仅能带来小幅性能改进。