（通信与信息系统专业论文）forces体系结构中流量矩阵建模及其应用的研究.pdf

f o r c e s 体系结构中流量矩阵建模及其应用的研究摘要流量矩阵可以完整地描述网络中所有流量需求的分布情况，结合网络路由信息还可清晰地反映出各条链路的流量构成，是网络管理和流量工程任务的关键输入。本文首次将流量矩阵的概念引入f o r c e s体系结构路由器，从f o r c e s 路由器内部流量测量的角度对路由器的运行情况进行监控，并获取f o r c e s 路由器内部流量信息对f o r c e s路由器内部流量进行路由优化，实现流量均衡的目的。f o r c e s 体系结构将转发件f e 和控制件c e 分离，中间通过标准的f o r c e s 协议进行通信，控制端运行各种应用协议软件，如s n m p协议软件，o s p f 协议软件，转发端由统一的逻辑功能块l f b 组成。f o r c e s 体系结构的实质是把网络件的软件和硬件在结构上分开，同时将接口和转发器内部模块标准化，进而使网络件的设计成为一个积木化过程。通过分析f o r c e s 体系结构f e 端的网络拓扑及各种流量矩阵估算方法的特点，本文采用重力模型估算所有f e 端的流量需求，估算结果能有效的反映f e 之问真实流量的变化趋势。通过分析基于流量矩阵的各种路由优化算法，采用负价环算法将估算的流量结果用作计算路由优化集的输入，优化高负载链路的流量，优化结果能有效的均衡各链路上的流量。关键词：流量矩阵，路由优化，重力模型，负价环lr e s e a r c ho ft r a f f i cm a t r i xm o d e l i n ga n da p p l i c a t i o ni nf o r c e sa r c h i t e c t u r er o u t e ra b s t r a c tt r a f f cm a t r i xc a nc o m p l e t e l yd e s c r i b et h ed i s t r i b u t i o no fa l lt r a f f i cr e q u i r e m e n t si nt h en e t w o r k ，c o m b i n i n gw i t ht h en e t w o r kr o u t i n gi n f o r m a t i o n ，i tc a na l s oc l e a r l yr e f l e c tt h ec o m p o s i t i o no ft h ef l o w so nt h el i n k s ，a n di st h ek e yi n p u tt on e t w o r km a n a g e m e n ta n dt r a f f i ce n g i n e e r i n gt a s k t h i si st h ef i r s tt i m et h a ti n t r o d u c e st h ec o n c e p to ft h et r a f f i cm a t r i xi n t of o r c e sa r c h i t e c t u r er o u t e r s ，t h r o u g ht h ea n g l eo fi n t e r n a lf l o wm e a s u r e m e n to ff o r c e sr o u t e rt om o n i t o rt h eo p e r a t i o no fr o u t e r s ，a n do p t i m i z et h ef o r c e sr o u t e r si n t e m a lf l o w so nt h ee s t i m a t e df l o wi n f o r m a t i o no ff o r c e sr o u t e ri no r d e rt ob a l a n c et h ef l o w so na l lo ft h el i n k si nt h ei n t e m a lo fr o u t e r f o r c e sa r c h i t e c t u r es e p a r a t e st h ef o r w a r de l e m e n t ( f e ) a n dc o n t r o le l e m e n t ( c e ) ，t h e yc o m m u n i c a t eb yt h es t a n d a r dp r o t o c o lo ff o r c e s ，c o n t l 0 le l e m e n tr u n sv a r i e so fs o f t w a r ea p p l i c a t i o n s ，s u c ha ss n m pp r o t o c o ls o f t w a r e ，o s p fp r o t o c o ls o f t w a r e ，f o r w a r de l e m e n ti sc o m p o s i t e do fu n i f i e dl o g i cf u n c t i o nb l o c k ( l f b ) t h ee s s e n c eo ff o r c e sa r c h i t e c t u r ei st h a ti ts e p a r a t e st h en e t w o r kc o m p o n e n t so fs o r w 踟ea n dh a r d w a r ei nt h es t r u c t u r e ，a n dm a k et h ei n t e r f a c eb e t w e e nc ea n df e ，a n di n t e n a lm o d u l e so ff es t a n d a r d i z e d ，t h u sm a k et h ed e s i g n a t i o no fn e t w o r kc o m p o n e n t sa sap r o c e s so fr e c o n s t r u c t i n gf ea n d- l f bi nf e a c c o r d i n gt ot h et o p o l o g yo ff e si nf o r c e sa r c h i t e c t u ma n da n a l y s i z et h ec h a r a c t e r i s t i c so ft r a f f i cm a t r i xe s t i m a t i o nm e t h o d s ，w ed e c i d et ou s et h eg r a v i t ym o d e lt oe s t i m a t ea l lt h et r a f f i cd e m a n do ff e s ，a n da n a l y s i z et h ee s t i m a t i o na c c u r a c y b ya n a l y z i n gav a r i e t yo fr o u t eo p t i m i z a t i o na l g o r i t h mb a s e do nt h et r a f f i cm a t r i x , w ed e c i d et ou s et h en e g a t i v ev a l e n c er i n ga l g o r i t h mt oc a l c u l a t et h es e to fr o u t eo p t i m i z a t i o n ，t h r o u g ho p t i m i z eh i g ht r a f f i cl o a dl i n k s ，w ec a l lm a k et h eb a l a n c eo ft r a f f i co ne a c h1i n k k e yw o r d s ：t r a f f i cm a t r i x ；r o u t i n go p t i m i z a t i o n ；g r a v i t ym o d e l ；n e g a t i v ev a l e n c er i n g7洲90洲070川2删y1 1 研究背景及意义第1 章绪论在加速推进三网融合发展的大背景下，对网络设备的计算处理性能和报文转发性能提出了更高的要求。从技术发展趋势来看，开放性、分布式、宽带化、模块化、可编程日益成为下一代网络产品的重要特征。但是，现有的网络设备在满足网络发展的需求方面仍显得力不从心。当前工业界和研究机构都在探索利用分布式的体系结构来提高网络设备的处理能力，对此，国际上出现了对新型网络体系结构的研究。新型网络体系结构需要将网络件的各部分模块化，模块间通讯采用开放的，统一的接口，由此可以显著的提高网络的扩展性，灵活性和有效性。i e t f 的转发器和控制器分离( f o r w a r d i n ga n dc o n t r o le l e m e n t ss e p a r a t i o n ，f o r c e s ) 是基于开放可编程思想的新一代网络件体系结构【3 3 】，f o r c e s 协议将网络件分为控制件( c o n t r o le l e m e n t ，c e ) 和转发件( f o r w a r d i n ge l e m e n t ，f e )两大部分，用f o r c e s 协议来实现各部件之间的协同和交互，从而提高网络件系统的可伸缩性和可管理性，增强网络件的扩展性和灵活性。f o 疋e s 网络件的实质是把网络件的软件和硬件在结构上分开同时将接口和转发器内部模块标准化，进而使网络件的设计成为一个积木化过程，同时可以由不同厂家生产控制件( 软件为主) 和转发件( 硬件和底层软件为主) ，这种结构具有当前主要运用的封闭式控制网络件的体系结构所难以实现的众多优点，如：允许网络件功能的快速配置和重组，构建智能化的动态网络，大大加快和方便网络升级及新业务的展开，降低运营成本和风险；网络件中的控制件和转发件在产品层上分离，有利于排除垄断、增强良性竞争，同时专一化也可使产品进步加快，缩短了新产品的上市时间。以上这些特点决定了f o r c e s 网络件能快速有效的为用户提供新业务，同时也能为运营商节约投资。f o 托e s 技术乃至开放架构网络的研究已经有了很好的进展，但是f o 以e s自身的研究离实现网络高效性的研究目标还有较大的差距。这主要体现在目前f o r c e s 的研究主要集中在结构和技术的研究；对f o r c e s 路由器的性能还没有一个评价标准和监控体系。为了确保f o r c e s 的高效运行，并使网络可以为用户6提供更加安全可靠的计算环境，需要对f o r c e s 路由器的内部的运行状况进行实时监控。目前在互联网中大部分流量监控都是针对单个或局部链路进行，但是由于f o r c e s 路由器内部的流量组成的复杂性，如果只对c e 和f e 间或者只对f e 和f e 间的单个或部分通道的流量进行测量，很难对f o 疋e s 路由器的整体性能进行评价和监控分析。可以想见，如果能同时监控到f o 疋e s 路由器中各个通道的网络流量的全部状态，以全网的观点来观察和了解f o r c e s 路由器内部流量的特性和流向情况，建立f o r c e s 路由器内部流量的完整视图，将能更好地监控f o r c e s 路由器的运行情况；从而有望在确保f o r c e s 正常运行的基础上，通过优化路由器的配置和结构，提高f o r c e s 路由器的性能。为了概括在f o 疋e s 路由器内部以全网观点来看待流量的事实，本文将流量矩阵的概念首次引入f o r c e s 路由器中，流量矩阵反映了一个网络中所有源节点和目的节点对，即o d对( t h ep a i ro f o r i g i na n dd e s t i n a t i o n ) 之间的流量需求。流量矩阵是全网流量的透视，能够清晰地反映了f o r c e s 路由器中各个通道的流量构成。流量矩阵不仅是网络监控的重要手段，还是多个重要研究领域的关键输入。例如，流量矩阵可以用于研究流量工程中的路由优化和负载平衡问题，研究网络管理中的容量规划问题，研究网络安全中的异常检测问题等。此外，流量矩阵还可以用于研究性能评价等。自从流量矩阵的概念被提出来后，国内外许多学者围绕流量矩阵的估算建模与应用等相关问题进行了大量的研究，每年都有大量相关高水平学术论文在i n f o c o m 和s i g c o m m 等高级会议上以及软件学报等国内一级刊物上发表。很多研究表明，直接测量获得流量矩阵实际上几乎是不可行的。只能结合某种流量模型，利用网络中可直接测量的信息来估算流量矩阵，这些信息包括链路负载、路由配置、网络拓扑等。因此，近年来，由间接观测进行流量矩阵估算已经成为一个非常热门的研究领域的问题，如v a r d i 首先在1 9 9 6 年提出了网络透视( n e t w o r kt o m o g r a p h y ) 方法，旨在寻求某种途径利用链路流量推算流量矩阵。如何通过有限的测量信息建模估算出满足一定精确度要求的流量矩阵成为很多研究人员关注的焦点。随着估算模型的发展，估算精度在不断提高，流量矩阵的应用也在不断开发中，估算结果逐渐被应用于计算机网络( 流量工程、网络管理、网络安全7等) 的各个领域中，从而给网络技术的发展带来深远的影响。因此，研究对f o r c e s 路由器进行流量矩阵建模，并基于流量矩阵以全网的角度对f o r c e s 路由器内部的流量进行监控及优化f o r c e s 路由器内部路由，在f o r c e s 体系结构、流量矩阵及路由优化研究领域中都具有非常重要的现实意义。1 2 国内外研究现状流量矩阵发展至今，研究重点一直都在估算模型上，以期得到精度更高的流量矩阵。而流量矩阵应用的研究还在起步阶段，但是流量矩阵应用于网络工程领域的优势是有目共睹的，因此相信与流量矩阵模型发展和应用推广相关的研究工作仍将是流量矩阵领域发展过程中的重点。1 2 1 流量矩阵估算模型的发展流量矩阵估算模型的发展经历了三个阶段：第一个阶段只使用s n m p 获得的链路负载信息作为估算依据，以贝叶斯方法、最大期望方法和线性规划方法为代表；第二代方法在第一代方法的基础上结合了路由配置信息和网络拓扑信息，以重力模型法和路由变化法为代表；第三代方法则加入了使用n e t f l o w 测量得到的部分流量信息，以主成分分析法、卡尔曼滤波和扇出方法为代表。每一代估算模型在结合更多可用信息的同时也提高了估算精度。1 、第一代方法贝叶斯方法和最大期望方法都属于统计学方法。文献【1 6 最先将贝叶斯方法应用于流量矩阵估算，并取得了不错的效果。但是，贝叶斯方法也有其自身的缺陷，它假设o d 对之间的流量需求符合泊松分布，可实际并非如此：研究表明，网络流量存在广泛的自相似特性。尽管贝叶斯方法对流量分布假设并不敏感【1 7 1 ，但这仍然会影响其估算精确度。文献 1 8 】使用e m 方法估算流量矩阵，该方法假设o d 对之间的流量需求x 相互独立且符合正态分布，e m 方法通过不断迭代最大步和期望步，估算参数口和流量矩阵x 。g o l d s c h m i d t 将线性规划方法应用于流量矩阵的估算。m e d i n a 对贝叶斯、最大期望和线性规划方法进行了比较和评价，以探究它8们的估算错误率、对先验信息和统计假设的敏感程度。由于无法获得真实的流量矩阵，作者选择合成流量矩阵( s y n t h e t i ct r a f f i cm a t r i x ) 作为估算结果的评判标准。评价结果显示，第一代方法只需要使用s n m p 获得的链路负载信息和路由信息作为估算依据，但其对先验信息十分敏感，误差率在1 0 - - 6 0 之间，这距离i s p 期望的1 0 以内的估算误差相距甚远。2 、第二代方法路由配置反映了i s p 的路由策略，网络拓扑则描述了网络的内部结构。第二代方法在第一代方法的基础上结合了这两种信息，提高了估算精确度。简单重力模型是用简化了的牛顿万有引力定律来估算o d 对之间的流量需求。广义重力模型是简单重力模型的扩展，它细分了链路类型：i s p 骨干网与本地网用户之间的链路称为a c c e s sl i n k ，i s p 骨干网与其它i s p 之间的链路称为p e e r i n gl i n k 。此外，还将网络流量分为4 种不同的类型：穿越流量( t r a n s i tf l o w ) 、输出流量( o u t b o u n df l o w ) 、注入流量( i n b o u n df l o w ) 、内部流量( i n t e r n a lf l o w ) 。经过对链路和流量的细化之后，估算得到的流量矩阵的精确度更高。为了获得更高的估算精确度，z h a n g 等人提出t t o m o g r a v i t y 模型。该方法考虑t o p 对流量需求的空间相关性，是重力模型和t 0 m o g r a p h y 方法0 9 的结合，取得了不错的估算精度。路由变化方法通过改变i g p 链路的权重，得到足够多个不同的路由矩阵，将它们拼接起来，即可得到一个新的满秩的路由矩阵。路由变化方法能够精确地计算流量矩阵，但是该方法也有自身的缺陷。s o u l e 将路由变化方法存在的问题归结为不完整性和不实用性，并对路由变化方法进行了改进，将平均估算错误率限制在1 0 以内，一定程度上解决了这两个问题。文【3 埘简单重力模型、广义重力模型和t o m o g r a v i t y 模型进行了比较。实验表明：t o m o g r a v i t y 模型的精确度最高，估算得到的流量矩阵中大部分元素的错误率都控制在2 0 以内；简单重力模型的精确度不能令人满意，矩阵中大部分元素的估算错误率都在2 0 以外；广义重力模型的估算精确度则介于t o m o g r a v i t y模型和简单重力模型之间。第二代方法结合了路由配置信息和网络拓扑信息，其估算错误率大致可控制在1 5 - 2 0 之间，相对于第一代方法已经有了明显的进步，但仍然不能满足i s p 的要求，需要结合一些其它信息进一步降低估算错误率。93 、第三代方法不论是统计学方法还是重力模型方法，其理想的估算错误率只能达到1 5 0 o - 2 0 ，这与i s p 所期待的1 0 的错误率还有一定的差距。近三年来，学者们提出了具有更高估算精确度的第三代估算算法，这类方法的特点是通过n e t f l o w技术，直接测得少量但精确的流信息，结合已有的估算模型来进一步降低错误率。主成分分析法、卡尔曼滤波方法和扇出方法是典型的第三代估算算法。在文献 2 0 】中，作者正是利用了流量矩阵的低维表示，提出了一种新的流量矩阵估算算法，卡尔曼滤波( k a l m a nf i l t e r ) 估算方法。k a l m a nf i l t e r 方法能够以均方误差最小为准则解决最佳线性过滤和预测问题。该方法的核心是用当前预测值和最近一次的观测值来估算信号的当前值。在用于流量矩阵估算时，将流量矩阵的变化视为线性过滤和预测问题。扇出方法( f a n o u tm e t h o d ) 依赖于直接测量扇出项来估算流量矩阵，经测量，节点的扇出项非常稳定且具有每日模式特征。因此，只需测量单日内的扇出项，结合s n m p 测得的链路负载值即可估算流量矩阵。文献【2 l 】对第三代方法，2 及t o m o g r a v i t y 方法和路由变化方法进行了性能评价。第三代方法的时间错误率明显低于t o m o g r a v i t y 方法和路由变化方法，且p c a方法和卡尔曼滤波方法错误率一直维持在一个较低的水平。虽然第三代方法在精确度上已经能够达多j i s p 的要求，但还需在测量代价和估算精确度上进行权衡。另外，e r r a m i l l i 等人提出了独立连接模型( i n d e p e n d e n tc o n n e c t i o nm o d e l ) 取代了重力模型来获得先验信息，并首次将双向流量的特性结合到流量矩阵模型中。文献【6 】分析了为流量矩阵建立稀疏模型的必要性，并从多尺度的角度给予了分析。z h a n g 等人用时空压缩传感的算法解决流量矩阵估算的问题，取得了不错的估算精度。1 2 2 流量矩阵应用的发展流量矩阵可以完整地描述网络中所有流量需求的分布情况，结合网络路由信息还可清晰地反映出各条链路的流量构成，是许多基本的网络工程任务的关键输入。i s p 需要流量矩阵进行网络规划和路由优化，以提高服务质量。研究人员需要流量矩阵来建立网络仿真环境，不仅可以评估新路由协议的性能，还可以分析网络故障或路由策略变化的影响。此外，流量矩阵在短期内的剧烈变化可用于网络异常检测。除了以上应用，流量矩阵还可以用于网络规划，性能评价和故障分析方面。1 2 3 国内在流量矩阵领域的研究进展近年来，流量矩阵技术也吸引了部分国内研究人员的目光，也取得了一些研究成果。清华大学网络中心在流量矩阵方面进行了深入的研究。文献【3 1 】介绍了多种流量矩阵估算算法，并讨论了部分方法的性能：文献 2 3 】【2 4 对流量矩阵的估算算法做了大量的研究，提出了基于平方根分解的估算模型，估算精度得到了很大的提高；文献【2 5 】利用流量矩阵构造了一个适用于流量矩阵估算的流量测量模型；而文献 2 6 2 7 1 贝j j 利用流量矩阵进行d d o s 攻击检测。国防科大在流量矩阵领域也展开了研究。文献【1 4 】基于多数据源对网络流量矩阵估计；文献【2 8 】利用信息熵理论发现关键流量矩阵，首先计算流量矩阵的信息熵，选取信息熵较大的若干个矩阵作为候选关键矩阵，然后对最小耗费的簇进行合并，直到最后获得需要的流量矩阵。电子科技大学宽带光纤传输与通信网技术重点实验室也对流量矩阵进行了研究。文献【2 9 】对流量矩阵的研究状况进行了综述；文献【2 9 】通过使用广义回归神经网络克服了流量矩阵估计的病态特性，获得精确的估计值。文献【l8 】针对源目的( o d ) 流量估计解的不稳定性和求解方法的复杂性，将广义线性反演应用于大尺度网络流量矩阵估计。另外，天津大学，江苏大学都进行了流量矩阵相关的研究。从国内的研究现状可以看出，已有不少研究组织介入到流量矩阵领域的研究中，但很多研究还处在摸索阶段，尤其是如何研究适合国内网络发展现状的流量矩阵应用模式，有待于进一步发展。1 2 4 路由优化技术的研究进展随着i p 网络规模的不断扩展和流量需求的迅速增加，网络流量的不均衡分布日趋明显：局部网络链路出现拥塞的同时，网络其余链路轻载或空载的情况却普遍存在。虽然网络硬件的快速发展，高速的交换和路由单元以及大容量的网络链路可提供大量的带宽，但这种带宽过量供给的方式是以网络资源利用率低为代价的，并不能有效解决热点链路的拥塞问题，为此提出了流量均衡的概念。流量均衡是流量工程中为避免网络拥塞经常采用的路由优化目标，选择的路径使流量达到均衡分布。路由优化基于不同的路由协议采用不同的优化技术，路由协议包括单路径路由协议和多路径路由协议。现在互联网应用大多采用单路径路由协议，数据沿着一条路径进行传输，单路径路由协议算法简单，易于管理和配置。但路由开销和网络延迟较大，在负载较大的时候容易引起拥塞，路径失效时需要较长的时间重新寻路来恢复数据传输等问题，因此，不能满足应用对网络可靠性、容错性、负载均衡等特性的要求。多路径路由能有效的提高互联网的性能，文献 3 4 1 给出了多路径路由的详细定义：多路径路由模型为任意一对节点同时提供多条可用路径，并允许节点主机选择如何使用这些路径。多路径路由算法为节点间提供多条路径，并确保发往其中一条路径的数据经由该路径到达目的地。多路径路由协议涉及路径发现及维护和流量分配两方面功能。典型的有线网络的多路径路由协议包括源路由、m p l s 、分散路由、中间级路由覆盖和i p f a s t r e r o u t e 等。目前，面向流量工程的路由优化大多基于多路径路由协议。采用的路由优化算法有遗传算法、粒子群算法、蚁群算法等。文献【2 2 】从不同角度对流量工程中的路由算法进行了划分，从中可见，现有的流量均衡模型按路由优化的目标分为两类：最大链路利用率最小化及最小化链路代价和模型，最大链路利用率最小化模型通过调整网络中最大利用率的链路的流量，使最大负载的链路上的流量尽可能小，从而达到流量均衡的目的，这种方法简单直观，但当该最高利用率的链路无法进行优化的时候不考虑其他链路的流量优化。最小化链路代价和模型改进了最大链路利用率最小化的缺点，其路径代价是路径上所有链路的代价之和，但其缺点是在链路利用率比较均匀时，路径上链路数目成为路径代价的主要影响因素。由于最大链路利用率最小化及最小化链路代价和模型存在的固有缺陷，文献 3 4 1 在此基础上又提出了最小化路径代价和模型。根据路由优化输入的流量矩阵的个数，可分为基于单流量矩阵和基于多流量矩阵的路由优化技术。单流量矩阵的路由优化方法是基于已知的、静态的、点到点的流量矩阵，对流量在各路径上进行分配，以使各链路上的流量均衡，减小网络开销，提高网络资源的利用率。为了提高基于单个流量矩阵的路由优化效率，文献【1 5 】提出了基于动态流量矩阵的网络链路权值调整方法。由于准确估算流量矩阵很困难，而且网络流量是不断变化的，因此根据不断变化的网络流量来保持最优路由开销很大。基于多流量矩阵的路由优化是获得一套可用于各种不同的可能的流量场景的最优路由。路由协议分为目的路由协议和流路由协议，目的路由协议的典型代表是o s p f 2 1 ，流路由协议的典型代表是m p l s 13 1 ，根据不同路由协议的特点和多个流量矩阵优化路由本身存在的难点，当使用流路由协议时，可采用凸优化方法和梯度投影法来求解路由优化集，当使用基于目的路由协议时，可采用遗传算法求解路由优化集。1 3 本文的研究内容和主要贡献1 3 1 研究内容本文主要研究f o r c e s 体系结构内部的流量矩阵建模和估算算法，研究基于f o r c e s 路由器中的流量矩阵进行路由优化的方法，为后续f o r c e s 体系结构的性能评价提供依据和支撑，具体包括两个方面：( 1 ) 根据f o r c e s 路由器内部体系结构f e 端的拓扑特征，对路由器的内部f e 端的流量进行流量矩阵建模，并提出了初步的流量矩阵建模方案，即重力模型，用于估算f o r c e s 路由器内部f e 端的流量需求及变化趋势。( 2 ) 通过第一步的研究成果，估算出不同时刻的多个流量矩阵，并基于多个流量矩阵采用负价环算法进行f o r c e s 路由器内部f e 端各通信链路上流量的优化。1 3 2 主要贡献2 0 0 3 年以来，本课题组前期在国家基金等项目资助下对转发与控制分离f o r c e s 结构及协议进行了多项创新性工作，研究始终处于该领域前沿，与国际上其它研究机构一起，为顺利完成f o r c e s 技术研究及推进f o r c e s 应用作出了1 3重要贡献。7 年多时间来，f o r c e s 技术研究已经从少数人的学术研究稳步发展到目前在国际上被主要路由器厂家认可采用，在国内也被厂家和研究机构充分重视，并成为我国“新一代高可信网络”关于新一代可重构路由器研究中明确采用的一项重要基础技术。f o r c e s 架构中流量特征分析和建模的研究为f o r c e s 架构的性能监控提供良好的理论基础，是f o r c e s 开放架构路由器领域研究基础上的自然延伸。本项目研究内容均是在当前f o r c e s 架构下开展的，主要有：( 1 ) 基于f o r c e s 的开放可重构的体系结构f e 端拓扑结构分析和建模，提出一种流量矩阵建模和估算的算法。( 2 ) 针对流量矩阵的不同应用，提出一套基于多个流量矩阵的f o r c e s 内部路由优化的方法。1 4 本文的框架结构本文共分为六章，内容安排如下：第l 章为绪论，首先介绍了本课题的研究背景和意义，然后分析了流量矩阵估算模型在国内外的研究进展及其应用的发展情况，路由优化技术的研究现状。在此基础上，提出了本文的研究内容和组织结构。第2 章对当前普遍存在的流量矩阵估算方法进行了分析，通过对f o r c e s 体系结构中通信过程的分析，结合重力模型的优点，选择采用简单重力模型获取f o r c e s 体系结构中所有f e 之间的流量。第3 章先研究了当前路由优化算法，然后对比了各路由优化算法的优缺点，提出了基于多流量矩阵的路由优化算法，在原来算法的基础上做了相应的修改，并详细介绍了算法实现过程。第4 章阐述了在f o r c e s 体系结构中重力模型的具体实现，解决了f o r c e s内部流量的测量。第5 章介绍了基于多流量矩阵的路由优化算法的具体实现，并对优化的结果路由和没优化的结果做了对比，得出优化后的路由可以很好的优化链路流量。第6 章总结了当前研究工作，并对下一步的研究工作做了一些展望。1 42 1 流量矩阵概念第2 章流量矩阵估算模型的研究流量矩阵表示节点对之间的流量需求，根据节点粒度的不同，流量矩阵可以分为4 类：p o p 级，r o u t e r 级，l i n k 级，p r e f i x 级。由小粒度级别的流量矩阵可以推导出大粒度级别的流量矩阵。流量矩阵通常用大写字母x 表示。假设一个i p 网络中有1 1 个节点，由这n ( n - 1 ) 个节点对所构成的流量矩阵x 的表示为：广 tl ，毛 x n ( n - i ) j ( 2 1 ) ，o 表示第_ ，号节点对之间的流量需求，节点对的编号可以是任意的。每个节点都可与另外的疗一1 个节点组成o d 对，故共有n ( n - 1 ) 个节点对。令y = 【j ， ，y r 7 ，称为链路负载矩阵，表示链路的流量值，是网络中链路的条数。2 ( 嘞) 一c 是，c 阶的o - 1 矩阵，c 是网络中o d 对的个数，如果网络中有刀个节点，则c 2 n ( n 1 ) 。嘞2 1 当且仅当o d 对之间的流量经过链路i ，否则吻20 。矩阵a 中的每一列，指明了某个o d 对之间的流量在网络中传递时所要经过的全部链路，因此，a 是一个包含实际路由信息的矩阵，又称为路由矩阵。链路负载、路由矩阵和流量矩阵之间的关系可以表示为：y = 肛( 2 - 2 ) ，通过s n m p协议可以直接测量得到链路负载矩阵y 。获得路由矩阵a 的方法有很多，一般的做法是收集内部路由协议( i g p ) 的配置信息或者通过收集路由器之间交互的链路状态信息，通过计算最短路径树而得到。这样，问题可以简化为已知y 和a ，通过公式y = 似求解x 。然而，在实际网络中，o d 对的数目要远大于链路的数目，即c 卜，因此a 并不是一个满秩矩阵，这是一种病态的线性逆问题，不能直接通过公式x = 彳“y 来求解流量矩阵。2 2 流量矩阵估算方法估算方法的发展经历了三个阶段：第一个阶段使用s n m p 获得的链路负载信息作为估算依据，以贝叶斯、最大期望和线性规划方法为代表；第二个阶段在第一个阶段研究的基础上结合了路由配置信息和网络拓扑信息，以重力模型和路由变化方法为代表；第三个阶段则在第二个阶段的基础上加入了使用n e t f l o w 钡1 量得到的部分流信息，以主成分分析法、卡尔曼过滤和扇出方法为代表。2 2 1 基于统计学的流量矩阵估算研究贝叶斯方法和最大期望方法都属于统计学方法。使用统计学方法进行估算，首先需要假设o d 对之间的流量需求相互独立且符合某种分布，然后使用某种统计学模型，在给定初始流量矩阵的情况下，结合路由矩阵a 和链路负载矩阵i r ，通过不断迭代求出分布假设中的未知参数，进而得到流量矩阵。作为迭代起始点的初始流量矩阵，又被称为先验信息( p r i o r ) ，最初为经验值或随机值，目前通常使用重力模型获得。1 、贝叶斯方法贝叶斯方法( b a y e s i a na p p r o a c h ) 在各个领域都有着广泛的应用，而且在特定假设和良好先验初值的情况下，有着相对较高的准确率。文n 最先将贝叶斯方法应用于流量矩阵估算，并取得了不错的效果。然而，贝叶斯方法也有其自身的缺陷，它假设0 d 对之间的流量需求符合泊松分布，但实际并非如此：研究表明，网络流量存在广泛的自相似特性。虽然贝叶斯方法对流量分布假设并不敏感，但仍然会影响其估算精确度。另外，贝叶斯方法对先验信息，即初始值的好坏十分敏感，而如何获得好的先验信息却是该方法所无法解决的。2 、最大期望方法最大期望方法( e x p e c t a t i o nm a x i m i z a t i o nm e t h o d ，e m ) 是一种从不完整数据中推算未知参数的数值迭代搜索算法。在应用于流量矩阵估算时，视流量矩阵x 为完整数据，它表示了完整的0 d 对之间的流量需求，而视链路负载矩阵l ，为不完整数据，待推算的未知参数为流量需求分布假设中的未知量。e m 方法估算流量矩阵假设o d 对之间的流量需求工相互独立且符合正态分布，即誓怕毗，d 。定义a = 职，五) 为0 d 对之间的平均流量需求，= 比颐彳，一，篇为协方差矩阵。通常假设均值和协方差之间存在马= 硝的关系( 其中6 是常数，不同的网络b 的取值不同) ，则定义口2 ( ，妒) 表示待推算的未知参数。最大期望方法的迭代过程分为如下两步：1 6m 口a x ，( p 吣，坛) = 一 l - i 1 左k l 嘣， 月三一 j - 1 ( 一爿m ( 2 3 )勘2 e x j , i e , y i ( 2 - 4 )e m 方法需要多次测量链路负载矩阵y ，式( 2 - 3 ) 中用y l ”y k 表示k 次s n m p 的测量值。在给定初始流量矩阵的前提下，通过式( 2 3 ) 计算得到使函数7 ( 0 1 y t ，次)达到最大值的口，式( 2 4 ) 根据0 计算o d 对，在时刻r 的流量需求巧，。式( 2 3 ) 因求函数最大值而得名最大步，式( 2 - 4 ) 由一个数学期望构成，因而得名期望步。e m 方法通过不断迭代最大步和期望步，估算参数0 和流量矩阵x 。3 、线性规划方法线性规划方法( l i n e a rp r o g r a m m i n g ，l p ) 主要用于研究有限资源的最佳分配问题，它不需要先验信息，也不假设流量的需求分布，只要确定目标函数和约束条件即可。g o l d s c h m i d t 将线性规划方法应用于流量矩阵的估算，视链路负载矩阵l ，为有限资源，最佳分配问题为：如何将链路上的负载分配给各个o d 对。作者选择的目标函数和约束条件分别是：i m a x _【丢孵川乩”( 2 埘选择该目标函数的目的是希望网络中的流量需求总和达到一个最大值。但是，如此选择目标函数会导致估算得到的流量矩阵中距离近( 跳数少) 的o d 对被赋予很高的流量值，而距离远的0 d 对却被赋予很低的流量值，甚至是o 。这样的估算结果显然与实际情况相违背。为了解决这个问题，作者建议使用式( 2 - 6 ) 作为目标函数，其中权重吻的取值要反映o d 对之间路径的长度。m a x 川_ _ w j x j ( 2 6 )4 、基于统计学的估算方法的比较和评价m e d i n a 对贝叶斯、最大期望和线性规划方法进行了比较和评价，以探究它们的估算错误率、对先验信息和统计假设的敏感程度。由于无法获得真实的流量矩阵，作者选择合成流量矩阵( s y n t h e t i ct r a f f i cm a t r i x ) n u c c i ，2 0 0 5# 4 3 7 ：r o u g h a n ，2 0 0 5 # 4 3 0 ) 作为估算结果的评判标准。合成流量矩阵是一种人造流量矩阵，是依据流量矩阵的某些属性人为构造的，在文 m e d i n a ，2 0 0 2 # 4 4 1 )中，作者根据“流量需求分布的假设”构造合成流量矩阵。m e d i n a 分别使用了五种不同的流量需求分布：常数分布、均匀分布、泊松分布、正态分布和双峰分布，通过两种网络拓扑结构进行估算方法的验证和对比：一种是简单的4 节点模拟拓扑结构，另一种是复杂的1 4 节点真实拓扑结构。验证对比方法包含以下4 个步骤：1 ) 对于一个给定的拓扑结构，使用5 种不同的流量需求假设分布，分别构造合成流量矩阵，记作x ；2 ) 根据路由协议i s - i s ，生成路由矩阵a ，再由等式( 2 - 2 ) 求出链路负载矩阵y ；3 ) 将彳和，作为输入，分别使用三种待测方法估算出流量矩阵x ：4 ) 将估算的矩阵x 与合成的矩阵x 做比较，得出三种方法的估算错误率。在4 个节点的拓扑结构下，作者使用了最符合贝叶斯方法的泊松分布和最符合e m 方法的正态分布，均使用了好的先验信息，并对线性规划方法目标函数的权重叼做了优化，使其等于0 d 对间路径的长度。使用平均错误率和最大错误率作为评价标准。平均错误率指的是所有0 d 对估算误差的均值，最大错误率指的是所有0 d 对中估算误差的最大值。实验结果显示：线性规划方法的平均错误率为9 8 3 ，最大错误率达到了2 0 7 ；e m 方法的估算效果最好，其平均错误率只有7 6 ，而贝叶斯方法略逊于e m 。在1 4 节点的拓扑下，为了考察待测算法对分布假设和先验信息的敏感程度，作者还使用了好、坏两种不同的先验信息。但是，线性规划方法的结果仍然令人失望，平均错误率接近1 0 0 ，而贝叶斯方法的平均错误率在2 0 - - - , 4 0 之间，e m方法的平均错误率在1 0 , - - - 4 0 之间。实验结果还表明：贝叶斯方法和e m 方法对流量需求分布假设并不是非常敏感，而他们对先验信息却是非常敏感的。基于统计学的流量矩阵估算方法使用s n m p 获得的链路负载信息和路由信息“作为估算依据，但其对先验信息十分敏感，误差率在1 0 - - 6 0 0 , 6 之间，这距离i s p期望的1 0 以内的估算误差相距甚远。2 2 2 基于重力模型的流量矩阵估算研究路由配置反映了i s p 的路由策略，网络拓扑描述了网络的内部结构，基于重力模型的流量矩阵估算方法在基于统计学的估算方法基础上结合了这两种信息提高了估算精度。1 、重力模型牛顿的万有引力定律表明，两个物体之间的引力与两个物体重量的乘积成正比，而与它们之间的距离成反比关系。流量矩阵的重力模型认为：两条链路之间的流量需求正比于从这两条链路进入和流出网络的流量。此处的流量矩阵是链路级的，链路对即为o d 对。应用于流量矩阵估算的重力模型分为三种：简单重力模型( s i m p l eg r a v i t ym o d e l ) ，广义重力模型( g e n e r a l i z e dg r a v i t ym o d e l ) ，t o m o g r a v i t y 模型。重力模型不仅可以估算流量矩阵，还可以生成先验信息，作为其他估算方法的初始流量矩阵。尽管e r r a m i11i 等人提出的独立连接模型也可以用来产生先验信息，但重力模型实现更简单，因而有着更为广泛的使用，如m e d i n a 等人提出的选择模型就是重力模型的一个变种。1 ) 简单重力模型简单重力模型是用简化了的牛顿万有引力定律来估算o d 对之间的流量需求。丁( ；，厶) 是流量矩阵的一个元素，表示由链路，f 进入网络且从链路0 流出网络的流量。用丁”( ) 表示由，f 进入网络的流量总和，严( f j ) 表示从流出网络的流量总和。那么简单重力模型可以表示为：弛j ：，) = 九) 焉或刚2 器( 2 7 )如果网络内部的链路既不产生流量也不消耗流量，那么上面的两个方程是等价的。虽然这个假设并不完全符合实际网络的情况，比如路由协议会产生流量，数据包通过内部链路时会丢失，但相对于全网来说，这些流量可以忽略不计。2 ) 广义重力模型广义重力模型是简单重力模型的扩展，它细分了链路类型：i s p 骨干网与本地网用户之间的链路称为a c c e s sl i n k ，i s p 骨干网与其它i s p 之间的链路称为p e e r i n gl i n k 。此外，还将网络流量分为4 种不同的类型，如图2 - 1 所示：用j p 表示p e e r 网络，口表示a c c e s sl i n k ，p 表示p e e r i n gl i n k ，p 表示所有p e e r i n gl i n k 的集合，a 表示所有a c c e s sl i n k 的集合。对一个p e e r 网络，可能有多条p e e rl i n k 与之相连。则四种流量类型的定义如下：( 1 ) 穿越流量( t r a n s i tf l o w ) ：从一个i s p 网络到达另一个i s p 网络，要穿越本i s p 骨干网的流量。由于这类流量是被穿越的i s p 所不愿意看到的，通常会采取适当的路由策略阻止这类流量，因此该类流量忽略不计。( 2 ) 输出流量( o u t b o u n df l o w ) ：本i s p 网络的用户到其他i s p 网络的流量，如从a c c e s s1 i n kq 到p e e r i n gl i n k 靠的输出流量k 心，岛) 用式( 2 8 ) 计算，其中瑶( 另) 表示本i s p 网到p e e r 弓的流量，硇圬) 表示从a c c e s s1 i n k a ,算，其中上弦v j 表示本网到巧的流量，一r 矿，7 表示从到p e e r 铀p e e r i n gl i n k 集合。一茄瑶够地讹力【q挑( 2 8 )( 3 ) 注入流量( i n b o u n df l o w ) ：其他i s p 网络到本i s p 网络用户的流量，如从p e e r i n gl i n kb 到a c c e s s1 i n kq 的注入流量伪，哆) 用式( 2 9 ) 计算，其中p ) 所有从所进入本i s p 网络的流量，p ( 乃) 表示所有从q 流出本i s p网络的