Internet流量模型分析与评述

　　摘要:Internet流量模型对网络性能管理、QoS、准入控制等都有很重要的意义和作用.首先总结了现阶段已发现的主要网络流量的特性及相关度量参数,概要地介绍网络流量建模的意义和分类,然后按照“传统-自相似-流量建模的新发展”这3个阶段阐述网络流量建模的发展历程与最新的研究成果,最后针对目前网络流量建模中存在的难点问题,展望了该领域未来的研究发展方向.

　　关键词:Internet流量特征;网络流量模型;自相似;长相关;分形

　　自互联网问世以来,关于网络流量的研究一直在不断的探索中.1993年,Leland等学者发现了数据网络的流量具有自相似的特性,掀起了互联网流量特性与建模研究的热潮.随着互联网的快速发展、网络应用的多样化以及新型网络应用的快速部署,网络流量特性也随之不断发生变化.近年来,许多学者针对不断变化的流量新特性,对网络流量的自相似性以及其他相关特性进行了重新审视.本文试图从一个较长的时间轴对互联网流量特性与建模研究工作进行比较系统的梳理,以期对从事相关研究工作的人员有所裨益.

　　传统电信网络的业务可以用经典的泊松过程进行很精确的描述,因此,早期学者们也尝试用泊松过程来描述互联网的流量行为.的确,根据许多现有的马尔可夫过程分析的结论和排队分析的一些基本方法,学者们能够在一定程度上对以近似泊松流作为业务源的排队系统进行性能分析,并且得到等待时间、队列长度等性能参数的近似结论.同时,泊松过程有着十分简单的相关结构,这使得泊松模型具有很好的性能.但是,泊松过程在大多数情况下并不能很好地描述互联网的流量行为.Leland等人在20世纪90年代初发表的具有开创性意义的论文中第一次明确提出了网络流量中存在着自相似现象,随后,Paxson等人对WAN流量、Klivansky等人对NSFNET流量和Crovella等人对WWW流量的测试分析,均发现网络流量具有自相似特性,引发了流量模型从传统模型到自相似模型的转变.21世纪初,Karagiannis等人通过分析Tier1ISP的骨干链路流量,发现目前高带宽和高聚合的链路流量在亚秒尺度下近似泊松过程,从而引发了人们对网络流量特征及建模新的思索和争论.

　　1、网络流量特性与相关度量参数

　　实际网络流量特性以及刻画这些流量特性的度量参数是流量建模的基础和依据,流量建模的目标是能够更好地反映实际流量的特征并且用于更好地指导实际的应用.当前,网络流量公认的、最重要的统计特征是大时间尺度下的自相似性和小时间尺度下的多分形性.这些特性不仅存在于互联网络中,同时也存在于AdHoc网络以及卫星网络中.

　　1.1自相似和长相关

　　自相似(self-similar)是指局部的结构与总体的结构相比具有某种程度的一致性,自相似过程是在统计意义上具有尺度不变性的一种随机过程.从这一点上来说,自相似过程实际上是在随机过程中引入了分形的概念.网络流量具有长相关性,是相对于泊松等短相关(shortrangedependence,简称SRD)模型而言的.从物理意义上看,长相关性(longrangedependence,简称LRD)反映了自相似过程中的持续现象,即突发特性在所有的时间尺度上都存在的现象,也称其为多尺度行为特性.

　　自相似性与长相关性有着密切关系,H≠1/2稳定的自相似随机过程是长相关的.但长相关过程不一定就是自相似的.长相关性是渐近意义上的,它只描述了自相关函数在大延迟下的行为,而对任何固定有限大小延迟下的行为没有限制.而且,长相关性是侧重于业务量的统计特性,而自相似性则是偏重于数学表述上的.自相似过程的重要性还表现在,它为赫斯特效应(Hursteffect)这一经验规律提供了一种解释.Hurst参数是表征自相似特性的一个重要参数,一般来说,H值越大,自相似(长相关)程度越高,突发性也越强.

　　1.2多分形

　　在分形理论中,多分形又称作多重分形测度.对于许多非均匀的分形过程,一个维数无法描述其全部特征,需要采用多重分形测度或维数的连续谱来表示.Riedi等人通过对TCP流量的数值分析,指出长相关只是流量分形性质的一个方面(在较大的时间尺度上);在较小的时间尺度上,流量体现出更为复杂的变化规律,尤其是局部具有突发性.自相似在相对较大的时间尺度上刻画了流量的长相关特性,但无法描述业务的局部特征.因此,研究者又引入了多分形的概念.多分形延伸和细化了网络测量流量中的自相似行为(自相似即单分形),多分形性质体现了依赖于时间的尺度规律,在描述局部时间内的不规则现象时更加灵活.流量的分形特性已经广泛应用到许多工程问题中,如互联网流量建模、TCP流量的拥塞控制、实时估计LRD过程的Hurst参数等.并且,分形理论和其他的数学理论相结合,如应用小波变换的自相似及多分形分析,在流量工程中正体现出越来越重要的作用.

　　1.3周期及混沌

　　实际的网络流量除了人们熟知的自相似特性外,还有其他的一些流量特性不断地被研究人员提出并进行相关研究.如周期性和混沌性等.周期性变化特性反映的是网络流量时间序列随着时间的变化而表现出来的一种季节性的变化规律.所谓混沌就是指在确定性系统中出现的一种貌似无规则的、类似随机的现象,它普遍存在于自然界及人类社会中,是有序与无序的统一、确定性与随机性的统一.网络流量序列中存在着低维混沌,去掉长相关后的数据是一个随机流量数据,这反映了网络流量数据的混沌与网络流量的长相关是有密切联系的,从而为混沌与长相关的密切联系提供了一个有力的证据.因此,把混沌控制的思想和方法引入自相似业务流控制和建模预测是一个非常值得探索的研究方向.

　　2、网络流量建模概述

　　流量模型是流量行为特征的数学近似,网络流量建模的基本原则是:以流量的重要特性为出发点,设计流量模型以刻画实际流量的突出特性,同时又可以进行数学上的研究.从理论角度来看,网络业务流的数学模型提供了对流量特性简明的、抽象化的描述,其价值在于能够提取出网络流量的一些重要特性,并给出一个明确的量化表示.随着网络规模的扩大和各种网络服务的广泛应用,建立一个能够准确、有效地描述网络流量特性的流量模型,对QoS、网络性能管理、准入控制等都有很重要的意义和作用.20世纪70年代和80年代早期,由于当时网络的应用比较单一,数据传输量较小以及受到网络测量技术的限制,人们借鉴公共交换电话网络的模型,使用泊松模型来描述数据网络的流量,并取得不错的效果.进入80年代中后期,随着FAX、数据网络和Web的出现,泊松过程已不能充分反映Internet业务流量的特性.人们随后又逐渐引入了Markov和回归等随机模型来描述网络流量.习惯上,人们称这些早期模型为传统网络流量模型,其共同特点就是所描述的业务序列具有短期相关性.20世纪90年代以来,随着网络节点数呈指数增加和多媒体、视频、远程教育等网络应用的不断出现,流量特性变得更加复杂.由于不同的网络应用具有不同的流量特性,使得网络流量特性也发生了显著变化,这些都增加了网络流量特征化的困难.随着研究的深入,研究人员发现网络流量具有自相似特性,传统的流量模型已不能很好地描述网络的自相似性,而流量的自相似性又是网络的普遍属性并决定了网络的行为,因而基于自相似建模的研究便成为网络研究中的一个重要方向.2004年,Karagiannis等人通过分析Tier1ISP的骨干链路流量,发现目前高带宽和高聚合的链路流量在亚秒尺度下近似泊松过程,从而引发了人们近年来对网络流量特征及建模的新的思索和争论.

　　3、传统(短相关)模型

　　传统的网络流量模型一般是基于泊松过程的,这些模型产生的流量通常在时域上仅具有短相关性.随着时间分辨率的降低,即时间尺度变大,网络流量将趋于一个恒定值,即流量的突发性得到缓和.下面介绍几个经典的网络流量模型.

　　3.1泊松(Poisson)模型

　　泊松模型是20世纪初Erlang根据电话业务的特征提出来的,最初用于电话网的规划和设计,可以较为准确地描述电话网中的业务特征并得到广泛的应用.在网络流量建模的早期,人们便使用泊松模型来研究网络流量.泊松模型即指在时间序列t内,包到达的数量n(t)符合参数为λt的泊松分布,其相应的包到达的时间间隔序列T呈负指数分布,即F(t)=1.e.λT.其中,泊松过程的强度λ表示单位时间间隔内出现包数量的期望值,即包到达的平均速率,其值为λ=1/E(t).泊松模型假设网络事件(如数据包到达)是独立分布的,并且只与一个单一的速率参数λ有关.泊松模型较好地满足了早期网络的建模需求,在网络设计、维护、管理和性能分析等方面发挥了很大的作用.然而,根据泊松流量模型,从不同的数据源汇聚的网络流量将随着数据源的增加而日益平滑,这与实际测试的流量是不符合的,因而该模型变得已不适于刻画实际的网络流量.

　　3.2马尔可夫(Markov)模型

　　对于一个给定的状态空间S={s1,s2,…,sm},Xn表示在n时刻状态的随机变量,如果Xn+1=sj的概率只依赖于当前的状态,{Xn}就形成了一个Markov链[30].如果状态转换发生在离散时间序列(0,1,…,n,…),则称Markov链是离散的,否则称为连续的Markov链.Markov属性意味着未来状态只依赖于当前状态,这使得描述一个状态持续时间的随机变量的分布呈指数分布(连续时间)或几何分布(离散时间).在一个简单的Markov流量模型中,每次状态转换代表一个新的到达,因此到达间隔呈指数分布.Markov模型是利用某一变量的现在状态和动向去预测该变量未来的状态和动向的一种分析方法.Markov模型在随机过程中引入相关性,可以在一定程度上捕获业务的突发性.同时,Markov方法是一种具有无后效性的随机过程,应用十分广泛.Markov模型的缺点是只能预测网络的近期流量,而且无法描述网络的长相关性.

　　3.3回归(regression)模型

　　在回归模型随机序列中,下一时刻的随机变量是由过去一个特定时间窗口中的随机变量以及一个白噪声移动平均值来决定的.常见的回归模型有以下几种:自回归模型是Yule在1927年为了预测太阳黑子的数目而提出来的,该模型采用自动回归法,强调时间序列未来的点数由同一时间序列过去的值来决定;在技术上,它采用线张宾等:Internet流量模型分析与评述性映射,用过去的值来映射未来的值,在给定的时间序列中选取函数的参数使得预测结果的误差最小.

　　3.4传统模型的不足

　　传统流量模型的优点是相应的概率理论知识发展比较完善,队列系统性能评价易于数学解析.由于传统的业务模型只有短相关性,即在不同的时间尺度上有不同特性,从而无法描述网络的长相关性.从传统模型得到的结论是:这些模型仿真产生的业务,通常在时域仅具有短相关性,当业务源数目增加时,突发性会被吸收,聚合业务变得越来越平滑,不能反映业务突发性;而且,传统模型产生的业务流高频成分多而低频成分少,相关结构呈指数衰减,因而不能准确地描述流量自相似性.总结起来,有以下几点:1)实际的数据包和大部分连接的到达是相关联的,并不严格服从泊松分布;2)传统的业务模型只具有短相关性,而流量自相似性反映业务在较大时间尺度具有突发性,对缓存的占用比传统排队论的分析结果要大,这样会导致更大的延时.这说明泊松到达流量模型会降低网络的性能;3)对于传统模型,当业务源数目增加时,突发性会被吸收,聚合业务会变得越来越平滑,但却忽略了流量的突发性.

　　4、自相似(长相关)模型