`

Structural Analysis of Network Traffic Flows

阅读更多
Structural Analysis of Network Traffic Flows

目录
1主要观点和解决的问题 2
2关键技术 2
2.1介绍 2
2.2背景 3
2.2.1OD流量 3
2.2.2主要组件分析 3
2.3数据收集 5
2.3.1网络研究 5
2.3.2流量数据收集 5
2.3.3从原始流量到OD流量 5
2.4分析OD流量 5
2.4.1OD流量的低维度 6
2.4.2OD流量的结构 7
2.5了解eigenflows 8
2.5.1eigenflows的分类 9
2.5.2分解OD流量 11
2.6流量架构的时间稳定性 12
2.7相关工作 14
3总结 15













1主要观点和解决的问题
众所周知,网络流量的增加主要是由于源端和目的端(OD)的叠加造成的,因此想要彻底理解OD流量,必须知道基本的网络流量模型,和能够定位各类问题。比如流量工程,流量矩阵估计,计划容量,预测和异常检测。然而一直到今天,OD流量也没有很彻底的研究,很多有关他们的属性都不清楚。
    我们两种不同的主干网(Abilene和Sprint-Europe)得出了第一种分析OD流量时间序列的方法。使用PCA(Principal Component Analysis),我们发现OD流量的集合有一些内在组件。实际上,即使在超过几百OD流量的网络里,也能利用少数的(10或者更小)的独立组件,精确的对这些流量建模。我们将展示如何用PCA系统的将OD流量时间序列结果分解为三个主要的组件:周期性趋势,短暂的脉冲和噪音。我们将明确指出各类组件是如何组成整个OD流量结构的,研究随着时间分解的程度。
2关键技术
2.1介绍
以往的网络流量分析专注于研究在孤立的单一链路流量,然而现在网络研究
者面临的大部分重要的问题是建模需求和同时存在的流量分析,包括流量工程,流量矩阵估计,异常检测,攻击检测,流量预测和容量计划。
不幸的是,全部的网络流量分析都是建模在所有同时连接的链路上,这跟原来单一的链路相比是一个很复杂的任务。主要的挑战是OD流量高维多元的结构。高维性使OD流量分析问题的主要来源。核心问题是“维数的诅咒”。
通常解决高维性的方式是寻找低位近似来代替结构中重要的属性。寻找组成
高维的独立变量来降低维数。本文的方法是PCA,给定一个高维对象和其相关的一致空间,PCA寻找新的一致空间来降低维数。我们称这些低维数为对象的“内维”。
本文利用PCA从两种不同的主干网获取数据,每个主干网都有超过100的OD流量集合。经研究发现,使用5-10个维数,就可以精确的近似OD流量。
在这里我们先引入一个概念“eigenflows”,是一个从OD流量中获取特定变量的时间序列。每个OD流量表达为eigenflows的权重值。分为三类:(1)deterministic eigenflows(定期趋势);(2) spike eigenflows(短暂的脉冲);(3)noise eigenflows(噪音)。其中最大的OD流量是定期和预测的,稍微温和些的OD流量是指短暂的脉冲和噪音。最差的OD流量是指短暂的脉冲(Sprint-Europe)和噪音(对Abilene来说)。
2.2背景
我们假设网络的OD流量数为P,时间间隔数为t,X定义了整个网络的OD流量的时间序列。
2.2.1OD流量
OD流量包括一个网络接入点和接出点。这些接入点和接出点是为一群独立的人群服务的,每个OD流量来自于这些人群的活动。
    链路y和流量x之间的关系可以用一个路由矩阵A来获取。
                                                
流量工程就是一个不断调整A的过程,使得A满足上述公式。由于OD流
量数随网络节点数n呈 变化。因此OD流量x的维数会很高。因此需要通过一些方法来降低维数,在本文中选取了PCA作为我们的解决方法。
2.2.2主要组件分析
第一种主要组件主要由源数据获取而来,用一个单数轴表示。第二种由剩余
能量的最大值获得,与第一个数轴呈正交。由几何解释方法转变为线性代数,计算主要组成相当于求解对称矩阵特征值问题。具体来说是根据 求每个主要组件 是第i个特征向量 。
 
这里的 是对称正定矩阵,因此它的特征向量是一个非负向量。且由大
到小为
计算X的主要组件相当于计算 的特征向量。令 为X的第一个主要组成,获取数据中最大的能量。

欲计算X第一主要组成 相当于计算 的第一特征向量。

同样的结论,计算第k个主要组成相当于寻找 的第k个特征向量。
   
上式表示了所有的OD流量,权重为v ,代表了数据的一个维数。u 则获取了主要的数轴i。其中 获取了OD流量的最强趋势, 获取了下一个最强,一一如此。我们称u 为X的“eigenflows”.
所有的v 向量可以组成一个V矩阵, 型的。同样,我们可以用u 组建一个 型的U矩阵。
利用式3得出他们之间的关系:
   
X 指的是第i条OD流量的时间序列。
图2显示了特征向量u 和它对应的主要数轴v ,

其中X是r维的矩阵,


2.3数据收集
2.3.1网络研究
Sprint-Europe是欧洲主干网和US一级ISP,共有13个节点,为大公司贸易
服务,Abilence是Internet2主干网,有11个PoP,主要用于美国大学校园。
2.3.2流量数据收集
我们从网络中每个路由器收集简单的流量数据,在SE网络,用思科netFlow
来收集每250个数据包。在Abilence用juniper’s 流量采样工具获取1%的随机数据包。检测粒度为5元组。我们限制采样时间控制在10到5分钟,以避免采样到同步数据。
这种方法有两个主要缺点:
(1)在每N个数据包中我们只选取了1%-5%。
(2)在检测流量时有些包的检测不是同时的。
2.3.3从原始流量到OD流量
我们利用BGP和ISIS路由表来达到从原始数据到OD流量的转化。

2.4分析OD流量
如第二节所示,我们主要的目标是利用PCA将OD流量分解为特征向量的
结合。我们将组成OD流量的必要的特征向量来精确的构造,将时间序列降到一个很低的维度。然后我们将测试OD流量的结构是如何分解成特征向量组成的。
2.4.1OD流量的低维度
图4的结果显示了大部分流量都是由前面一些eigenflows组成的。可以看到OD流量时间序列可以降至5-10的维度,远低于OD对的个数。因此我们利用低维重塑OD流量时,我们可以选取前5个eigenflows,如图3所示。可以将OD流量的特征描述的很好。在执行PCA前我们将OD流量正常化。
  
如果正常化后OD流量的维数依然很高,我们将知道在流量还有时间模式存
在。经PCA正常化后的结果如图5所示。
图5和图4在相同的位置依然尖锐,但相对于前几个eigenflows已经有明显
的减弱。

2.4.2OD流量的结构
第一个发现,OD流量是由一些显著的eigenflows组成的。
显著的标准时设立一个阈值,统计有多少列超过这个阈值。图6显示了超过
阈值的个数,看以看到大部分V的列的eigenflows个数都是小于20的。最大的也没有超过35个。即每个OD流量都可以由不超过35个显著的eigenflows来组成,而且大部分比这还少。这个结果意味着我们可以猜想每个OD流量仅只有一小些特有的属性,
第二个发现是:OD流量如何区别开来
图7我们知道:(1)大部分显著项集中在某个范围内,(Sprint-Europe很明显)
              (2)大流量由最多的显著eigenflows构成,而小流量则由显著
性较小的eigenflows构成。

2.5了解eigenflows
该节主要展示eigenflows的三种常见形式。
2.5.1eigenflows的分类
有三类不同的eigenflows,图8所示。

第一行显示了很强的周期性,称这类eigenflows为d-eigenflows。
第二行显示了短暂脉冲的eigenflows,称之为s-eigenflows.可以清楚的获取
网络流量的短暂爆发的特性。
最后一行显示了n-eigenflows。获取了存于的随机流量源的变异(噪音)。
提出以下疑问:
(1)eigenflows在12或24小时内时候有傅里叶频谱的高峰值。
(2)eigenflows是否包含最少一个异常超过平均值5个偏差。
(3)eigenflows是否会表现近似为高斯频谱。
图9是一些实例:
(a)表示了d-eigenflows在24点处有一个短暂的脉冲。
(b)表示了s-eigenflows超过平均值5-sigma。
(c)表示了n-eigenflows组成类似高斯频谱。

图10表示了将OD流量分为以上三类,更好的分析OD流量的属性。

因此我们使用三个eigenflows来表示一个OD流量的特性:(1)它的周期性
平均值,(2)尖锐的脉冲,(3)随机的噪音。
由图11可知,D-eigenflows主要体现在前5个eigenflows,而后面5-6eigenflows主要是s-eigenflows,二者之间的区别(SE和A)主要是12个eigenflows以后。在A中,后面的显著eigenflows基本上都市n-eigenflows。在周期性趋势中,d-eigenflows占主要成分,后s-eigenflows是很重要的,最终,在数据集里大部分的数据都成为了n-eigenflows。如表2所示。

2.5.2分解OD流量
根据上述三个eigenflows分解OD流量,由图12可知,在OD流量的高容
量区,以d- eigenflows为主。到了图右边,主要因素变为其他两个网络出现,对S来说,低容量区以脉冲为主。然而不管容量如何,都具有噪音属性。A在低容量区以噪音为主。

这些结果告诉我们在收集OD流量时,应该将注意力集中在高容量-低容量
的差异上,和不同网络架构之间的差异上。
2.6流量架构的时间稳定性
许多应用都是实时变化的。研究OD流量的分解为eigenflows的方法是否也
适用于分析不在PCA分析过程的输入数据。因此产生了两个问题:
(1)这样分解的组成是否是低维的?
(2)原先的分类是否还适用?
验证第一个问题的方法是近似为小数目的低维组成后去测量错误。
图13显示了OD流量从左到右减少,相对应的错误的平均值并不大。因此维数降低了。图14X(1)和X(2)的对比显示了eigenflows的分类方法依然适用,而且在几个星期内都保持了稳定。



2.7相关工作
流量矩阵估计:处理y=Ax,但是x维数远大于Y
时间序列的异常检测:OD流量时间序列很难脱离手工检测异常,因此次方
法提出阈值模式检测异常。
流量预测:利用对d-eigenflows的预测建立起对周期性OD流量的预测;
流量工程:找出主要的周期OD流量和次要的噪音OD流量.
3总结
本文分析了两种不同网络下的OD流量时间序列的结构,Sprint-Europe和
Alience。
第一个问题是OD流量能否用低维来表示,前人的工作表明OD流量是一个
高维且服务于不同人群。结构复杂,难以建模。利用PCA我们将上百的OD流量用5-10个独立的维数来表示。
低维问题的解决诞生了第二个问题:怎么比较OD流量之间的相似与不同。
最后我们利用eigenflows来更好的考虑OD流量的结构,并且我们发现了OD流量的三个特性:周期性、脉冲性、噪音。大部分OD流量体现为周期性,少部分体现为噪音和脉冲。利用PCA我们能够将OD流量分解为不同的组成特性。
我们最后一个目标似乎检验OD流量的时间稳定性,我们发现利用PCA的
结构来分解OD流量的结构在数星期内产生的错误几乎可以忽略不计。低维的分解更体现了其稳定性。


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics