基于蚁群算法的IP网络流量矩阵估计

J o u r n a l o f C o mp u t e r Ap p l i c a t i o n s

I S SN 1 0 01 . 9 081

2 01 3. 01 01

计算机应用， 2 0 1 3, 3 3 ( 1 ): 9 2— 9 5文章编号： 1 0 0 1—9 0 8 1 ( 2 0 1 3 ) 0 1— 0 0 9 2— 0 4

C ODE N J YI I DU

h t t p:// w w w . j o c a . c n

d o i: 1 0 . 3 7 2 4/ S P . J . 1 0 8 7 . 2 0 1 3 . 0 0 0 9 2

基于蚁群算法的 I P网络流量矩阵估计魏多’,吕光宏(四川大学计算机学院，成都 6 1 0 0 6 5 ) ({通信作者电子邮箱 w e i d u o 4 4 6 1 2 9 1 1 7@y a} l o o . c o n. c n )

摘

要：针对 I P网络流量矩阵( T M)估计的高度病态性，导致很难精确估计网络流量矩阵，因此提出了一种基于

蚁群优化( A C O)算法的 I P网络流量矩阵估计方法。通过适当的建模，将流量矩阵估计问题转化为最优化问题，再通

过蚁群算法求解模型，有效解决了网络流量矩阵估计。通过测试结果分析，与现存的方法相比，所提算法的精度比最大熵和二次规划稍差，但这两种方法复杂度太高，不适用于大规模网络，因此，在网络规模较大的情况下，算法是较优的，可提高流量矩阵估计的精度。

关键词： I P网络；源一目的流；流量矩阵估计；蚁群优化算法中图分类号： T P 3 9 3 . 0 7 文献标志码： A

I P t r a ic f ma t r i x e s t i ma t i o n b a s e d o n a nt c o l o n y o pt i mi z a t i o nW EI Du o,LYU Gu a ng h o n g( C o l l e g e o f C o m p u t e r S c i e n c e,S i c h u a n U n i v e r s i t y,C h e n g d u S i c h u a n 6 1 0 0 6 5,C h i n a )

A b s t r a c t:I t i s v e r y d i f f i c u l t t o e s t i m a t e t h e T r a f i f c M a t r i x( T M)o f t h e n e t w o r k, b e c a u s e i t i s a h i g h l y i l l

— p o s e d p r o b l e m . T o s o l v e t h e p r o b l e m,a t r a f f i c m a t r i x e s t i m a t i o n m e t h o d b a s e d o n t h e A n t C o l o n y O p t i mi z a t i o n( A C O )a l g o i r t h m w a sp r o p o s e d .T h r o u g h a p p r o p r i a t e mo d e l i n g,t h e t r a f i f c ma t i r x e s t i ma t i o n p r o b l e m wa s t r a n s f o r me d i n t o t h e o p t i mi z a t i o n p r o b l e m, a n d t h e n t h e mo d e l w a s s o l v e d b y AC O a l g o r i t h m,w h i c h c o u l d e f e c t i v e l y e s t i ma t e t h e t r ff a i c ma t r i x .T h r o u g h t h e t e s t r e s u h s, c o mp a r e d wi t h t h e e x i s t i n g me t h o d s,t h e a c c u r a c y o f p r o p o s e d a l g o i r t h m i s a b i t w e a k e r t h a n e n t r o p y ma x i mi z a t i o n a n d q u a d r a t i c p r o g r a mmi n g .B u t t h e s e t wo me t h o d s h a v e h i g h c o mp l e x i t y,a n d t h e y c a n n o t b e a p p l i e d t o l a r g e - s c le a n e t wo r k . T h e r e f o r e,i n t h e l a r g e— s c a l e n e t w o r k,t h e p r o p o s e d a l g o i r t h m i s b e t t e r .I t c a n i mp r o v e t h e a c c u r a c y o f t r a f f i c ma t ix re s t i ma t i o n.

Ke y w o r d s:I P n e t w o r k;O i r g i n— D e s

t i n a t i o n( O D) f l o w;T r f a f i c Ma t i r x( T M) e s t i m a t i o n;A n t C o l o n y O p t i m i z a t i o n( A C O )a l g o i r t h m

0 引言流量矩阵( T r f a f i c Ma t r i x,T M)表示整个 I P网络中所有源~目的( O i r g i n— D e s t i n a t i o n,O D)节点对之间的流量需求，从全局范围内描述了整个 I P网络的特征。由于流量矩阵需要

系统具有高度的病态性。要精确估计网络的流量矩阵是非常困难的，因此，流量矩阵估计是一个具有挑战性的研究课题。 自从流量矩阵的概念被提出来后，许多学者围绕网络流量矩阵估计的算法相关问题进行了研究，也取得了一定的成效，当然与实际网络监控应用的需求还有一段距离。研究者曾使用概率统计的方法对 O D流建模以估计 I P网络的流量矩阵，重力场模型也已经成功地用来进行大规模的流量矩阵估计。

捕获网络流量的全局状态，直接监控代价非常高，几乎不可行。网络运营商通过流量矩阵估计来进行网络管理、网络规划以及流量监测等工作。流量矩阵是流量工程的一个关键输入参数。但是，在大规模 I P网络中，直接测量网络的流量矩

但是，概率统计推断技术对先验信息是敏感的，虽然使用重力场模型能够减少对先验信息的敏感性，但仍然存在着较大的估计误差。研究发现网络流量，尤其是高速网络流量具有重

阵是不现实的，而链路负载可以通过简单网络管理协议 ( S i m p l e N e t w o r k M a n a g e m e n t P r o t o c o l, S N MP )获得，路由矩阵可以通过 I P网络的状态信息和配置信息获得。因此，通过适当的建模，采用间接的方式对流量矩阵进行估计是一个比较有效的方法。流量矩阵、路由矩阵和链路负载之间的关系可以用如下线性系统表示：Y ( t )=A X( t ) ( 1 )

尾分布、自相关和长相关特性。经典的概率统计模型都无法适应大规模 I P网络流量矩阵估计的上述特性。文献[ 3]中， 作者将 O D流建模为独立同分布的正态模型，并修改传统的

最大期望 ( E x p e c t a t i o

n . Ma xi mi z a t i o n,E M)算法来获取流量矩

阵估计值；文献[ 4]中，作者使用贝叶斯方法研究流量矩阵的估计。但由于计算先验信息比较困难，作者使用了马尔可夫链蒙特卡罗算法估计流量矩阵；文献[ 5]作者使用了神经网络的方法进行流量矩阵估计；文献[ 6]中作者使用遗传算法估计流量矩阵。通过对文献[ 5— 6]中实验结果数据的分析可知，采用启发式算 …… 此处隐藏：1955字，全部文档内容请下载后查看。喜欢就下载吧 ……