自相似流与自相似性

自相似流与自相似性Self-similarTrafficandSelf-similarity链路级主机-节点间流量入网/出网节点间流量主机-主机间流量传统的业务流模型基于泊松（Poison）--连续时间基于贝努利（Benolli）--离散时间Birth-DeathProcessesEkEkEk+1Ek-1DeathBirthtt+tPk（t+t）=Pk（t）pk,k（t） +Pk-1（t）pk-1,k（t） +Pk+1（t）pk+1,k（t） +O（t） k≥1概率分布函数（Poisoncase）概率密度函数a(t)t≥0t≥0M/M/1排队系统012k-1kk+1MarkovProcess当前时间t与过去的时间（t-s），若时间差足够大，则t与（t-s）间隔的业务量是不相关；在s较小时，考虑到达业务量的相关性，称之为“短相关”模型（SRD）自相似（self-similar）Leland对Bellcore的局域网的测试与分析结果，表明实际网络的业务流在很长的时间范围内都具有相关性，即LRD。Hurst系数描述一个过程的自相关函数只需要方差问题：自相似流作仿真时，数据源如何产生？控制流量生成程序，如何得到符合特定方差和Hurst系数的自相似流？与用户数、用户数据流的特征、网络拓扑结构等物理量关联。自相似系数的在线测量如何实施？如何减少计算量并得到精度允许的估计值？1.自相似过程的概念设X（t）是随机过程，R（t）是该随机过程的相关函数。如果R（t）的积分是∞，则称X（t）是长相关过程（LRD：LongRangeDependence）。如用二阶距性质描述X（t）

，只需要一个Hurst系数，称之为H参数。令X（t）是宽平稳随机过程存在均值E[X]有限方差自相关系数仅取决于k假设：L（k）是随k缓慢变化的函数。构造新的随机序列 X(m)(m=0,1,2…) X(m)的每一个序列值k≥1是X（t）的大小为m的不相交块的算术平均值。如果X(m)的相关函数R(m)(k)与R(k)相等，则称X（t）是严格二阶自相似过程。如果X(m)的相关函数R(m)(k)在m→∞时趋于R(k)，则称X（t）是二阶渐近自相似过程。X（t）的Hurst系数

H=1-（/2）½<H<12.自相似过程的产生Mandelbrot给出了自相似流的产生方法。分形波朗运动（FBM，FractionalBrownianMotion）令B（t）为维纳过程，FBM是维纳积分的形式来表示。BH（0）=0其中（t）是伽玛函数。BH（t）是零均值的高斯过程B（t）的积分。BH（t）的性质：BH（t）是平稳增量过程；BH（t）的相关函数BH（t）的方差2|t|2H；BH（t）与aH

BH（t）同分布FGN,FractionalGaussianNoise分布高斯噪声（FGN）是BH（t）在单位时间内的增量。ZH（t）=BH（t）-BH（t-1）将BH（t）-BH（0）离散化为高斯随机变量的无穷和，忽略积分的高阶泰勒展开式，然后推出部分和间的叠代关系，由叠代算法得出其结果。自相似过程的生成算法M/G/∞队列：G是具有重尾分布（无限方差的分布）的随机服务时间。流叠加法：更新过程（renewalprocess）W（t），更新间隔UK是具有无限方差的随机变量。随机中值替代法（RMD，RandomMidpointDisplacement）傅立叶变换法FARIMA过程小波变换混沌映射法评估标准：简易性、准确性。 （1）RMD的计算量为O（n），计算量最小； （2）傅立叶变换法或小波变换产生的自相似序列，其准确性高。1.因特网流量数据的采集和分析评价网络能力增加网络资源改进网络协议网络性能参数的测量网络性能：理论分析、模型仿真泊松模型：点到点的传递方式有目的地收集、整理和分析当前网络运行的状态数据，为下一代Internet体系结构的制定提供依据。仿真、测量、统计的方法理论分析多播在流量统计分析中得出的理论模型，能以简单的形式拟合实际流量的特征。自相似模型验证自相似模型的理论结果，需要在大的网络规模上进行大量的测量。1.1因特网测量BMWG：网络互连技术的性能参数测量方法。/html.charters/bmwg-charter.htmlTEWG:负责定义、开发、制定和推荐关于因特网上流量工程相关的原则、技术和机制，同时提供一个通用的论坛，以研讨和推动TE的发展。/html.charters/tewg-charter.htmlIPPM:负责研究和制定衡量、评估因特网数据传输的质量、性能和可靠性指标的标准测度，并开发和推广准确、有效的网络测量技术。/html.charters/ippm-charter.html

全球性的测量平台NIMI：NationalInternetMeasurementInfrastructure（卡乃基梅隆大学）LBL,LawrenceBerkeleyLaboratory

网络分析基础体系结构（NAI）美国国家网络应用技术研究实验室（NLANR）

下属的网络测量和运行分析小组（MOAT）

因特网性能测量和分析（IPMA）项目密执根大学和Merit研究动态的路由行为

美国高级网络和服务公司的Surveyor

测端到端的单向包延迟、包丢失以及因特网路由信息的测量体系1.2网络测量机制网络工程：测量网络本身的行为特征接入点处测量（应用层）：使用FTP、WWW测试网络服务器的响应性能Ttcp和Netperf工具利用传输层的服务来注入测量的流量数据Ping、Traceroute和Treno等工具利用网络层的ICMP协议进行测量网络参数测量方法：PASSIVEMonitoringACTIVEMonitoringBasedSNMPMonitoring监测网络流量，如OCXmon向网络注入测试流量数据，并从其响应结果数据中测量网络的状态参数，如Traceroute、Skiller为网络运行和管理服务，收集数据加以统计、分析自相关函数的性质，采用数学方法构造出自相似流，其物理意义不够明确，无法解释自相似性的成因。

基于测量数据的自相似流生成方法2.经验型的自相似流的生成方法 引入级联模型中流量分层的思想，以网络业务的统计特征（会话到达间隔分布、会话持续期分布、分组到达间隔）为基础，生成具有特征性质的自相似流。

1.1原型模型设一更新过程W（t），t=0，1，2，…更新间隔UK是具有无限方差的随机变量，例如服从Pareto分布。更新间隔内，W（t）的值是一个服从有限方差分布的随机变量WK，在每个更新间隔内保持恒定。经验型生成方法原理令Sk=∑i=0Uim个更新过程W1….Wm叠加，则叠加过程m和t→∞，W（t，m）的极限过程是分布布朗运动（FBM）。参考模型—HTTP的流量模型WWW服务器的服务端口是TCP的80，并用IP地址区分不同的流；请求包响应包文档请求包响应包文档页面页面思考连续请求概率HTTP流:请求包的长度（Requestlength）响应包的长度（Replylength）每个页面内的文件数（Documentsize）相邻页面请求间隔（Thinktime）对同一服务器的连续请求概率（Consecutivedocumentretrievals）A.Math对实际的流量进行了测量请求包长度呈双峰分布；响应包长度为重尾分布，比请求包的长度要长。基于时间的诱导型方法识别同属一个页面的文件：TthresholdC1C2TthresholdC1C2具有相同的IP地址，且T<Tthreshold的文件属于同一页面。80%页面的文件数在4个以下，同一服务器连续的请求数小于6个（80%）。自相似性形成是由网络中各协议层交互作用的结果：TCP自适应性IP层路由的不稳定性链路层资源的可用性TCP的影响TCP的工作机制：实现数据分组的可靠传输。当TCP的端到端建立连接后，发送端将维护一个拥塞窗口cwnd，表示网络允许TCP发送的字节数；接收端维护一个接收窗口rwnd,表示接收端可用的缓冲区字节大小；接收窗口的值通过ACK传到发送端，发送端的发送窗口swnd=min（cwnd，rwnd）；TCP接收端的确认信号是采用累计确认方式。若收到一个不是所期待的数据包（失序）：接收端发送发送重复确认信号：超时重传：重传定时器的值是通过自适应算法动态计算得到的；快速重传：如果收到3个要求重传第k个报文的重复确认信号。为了实现快速重传，接收端必须连续收到至少3个失序数据包。TCP运行的4个阶段：慢启动阶段：cwnd从1开始，每收到一个ACK确认，cwnd的值加倍，直到大于慢启动门限（ssthresh）；拥塞避免阶段：每收到一个ACK确认，cwnd的值加1；快速重传阶段：当连续收到3个序号相同的ACK时，立即重传该序号起的报文字节，同时将慢启动门限减半，拥塞窗口为慢启动门限加3倍的报文大小；快速恢复阶段：启动快速恢复后，每收到一个重复的ACK，拥塞窗口设为ssthresh，并开始拥塞避免过程。

RTTcwnd5101520102030数据包拥塞窗口的动态特性：一个TCP报文的字节数主要集中在1500，576，66几个值上TCP单位时间内发送的报文数呈突发性。仿真两条TCP流竞争瓶颈链路时，各自窗口的变化规律：12Buffer=20C=0.2Mbit/s链路时延D=10ms从混沌映射的角度分析TCP拥塞窗口：SendRecvH(w)ACK反馈控制系统输入输出包括分组的丢失、误码、失序，重复。cwndn=