突发交换边界组装和调度算法的研究.pdf

上海交通大学 硕士学位论文 光突发交换边界组装和调度算法的研究 姓名：陈俊峰 申请学位级别：硕士 专业：电磁场与微波 指导教师：陈建平 2003.2.1 光突发交换边界组装和调度算法的研究 摘要 i 光突发交换边界组装和调度算法的研究 摘 要 internet的蓬勃发展使得人们在 internet上开展的业务种 类越来越多随着各个业务流量的不断增加对于网络的带宽也提 出了越来越高的要求由于 dwdm技术的使用光纤能提供几乎无 限的带宽从而具备了成为承载未来迅猛发展的信息的主要传输媒 体的能力为了更好地支持 internet上各种不同的业务现在光 网也正朝着和 ip相融合的方向发展 为了实现 ip over wdm人们新提出了光突发交换obs方 案相对于光分组交换方式光突发交换能降低对于光器件的要 求全面的支持各种不同的业务交换同时提供更为有效和完善的 qos服务保证适合于在承载未来高突发业务的局域网lan中的 各种应用能更好的支持当今互联网的 ip标准 本文主要针对在 obs 系统实现中的边缘路由器进行分析通过 一定的理论和模拟掌握路由器的算法和结构对于 obs 边缘端的性能 影响本文一共分为六个部分每个部分分别讨论以下几个问题 一第一章对于光突发交换obs技术的引入主要包括 光突发交换的产生背景与光分组交换的关系以及光突发交换的 设计思想和主要优点 二第二章介绍光突发交换的网络系统结构包括边缘路由 器的结构核心路由器的结构以及边缘路由相关的信令控制帧格 式以及 qos质量相应的算法 光突发交换边界组装和调度算法的研究 摘要 ii 三第三章在第二章介绍核心光网络之后主要介绍光突发 交换接入部分的数据流的自相似突发理论 四第四章结合了第二章和第三章的内容给出仿真模拟边 缘路由器的模型和具体算法 五第五章是第四章仿真模拟的结果分析在这个章节中 通过仿真结果可以估计在边缘路由器的突发数据包的组装和调度 算法以及路由器相应的参数对于整体系统性能的影响包括时延 突发程度的改善等等 六第六章是总结章节同时对于今后的研究提出了展望 关键词光突发交换obsdwdm边缘路由器自相似 光突发交换边界组装和调度算法的研究 abstract iii studies on assembly and scheduling algorithm in the edge router of optical burst switch networks abstract with the expanding of internet, the content and kinds of services are growing rapidly. therefore, more and more bandwidth is needed to satisfy the ever-growing service demand. thanks to the emerging of dwdm technology, the optical network can provide almost infinite bandwidth for the future enormous information services. the optical network tends to converge with the ip protocol which was used widely in the internet. optical burst switching (obs) was introduced to solve the issues related with ip over wdm. compared to the optical packet switching technologies, it can reduce the demand on optical switching hardware. it can support many different kinds of service, provide more effective and better qos. it is suitable to carry bursty services of the future high-speed lans and well supports the ip protocol standard of the internet. in the paper, we study the edge router in obs networks via theoretical analysis and simulation. attention is paid to problem how the assembly and scheduling algorithm in the edge router affect the edge performance of the whole obs networks. the work provides clues for better design of the future work. the paper has six sections, which are organized as follows: (1) section i is the general introduction of the obs concept, including the background of the optical burst switch, the relation with the 光突发交换边界组装和调度算法的研究 abstract iv optical packet switching (ops) and the merit and thought of the design for obs. (2) the network architecture of obs system has been presented in section ii. in the section, we discussed the structure of the core router and edge router, the control signal, which is concerned with the edge router, the frame format and method of qos guaranty. (3) section iii is focused on the theory of self-similar in the data transmission flow from the subnet. in the section we conclude some method that can generate the self-similar data flow for simulation and can test self-similarity from given data flow (4) in section iv, we construct a model and a set of algorithm for simulation of the edge router according to the former section. (5) section v is the analysis resulted from the section iv. in the section, we estimate the effect of algorithm and parameter for the assembling and allocating in the edge router on the system edge performance, including the delay, self-similarity. (6) section vi is conclusion of the paper. also given in brief is the suggestion for the future research. key word:optical burst switching, dwdm, edge router, self- similar 光突发交换边界组装和调度算法的研究 第一章 obs 的概念 1 第一章o b s的概念 1 . 1业务量的发展与传统光网络 飞速发展的因特网要求更高操作速度的路由器以保证 ip 数据包传输的高 容量和高速度日益发展的密集波分复用技术dwdm使得在单根光纤上以 g 比特速率传输多路信号成为可能估计单根光纤传输的容量超过 10tb目 前密集波分复用技术可以提供单根光纤超过 100 根信道数每信道 10gbit 总传输容量 1tb/s预计不久可以达到每信道 40gbit,从而使得传输容量超过 3.2tb/s1随着光纤主干网网络使用 wdm 技术从而通信容量提高以满足日 益增长的因特网的同时路由部分将逐渐成为未来主干网传输的瓶颈尽管过 去的几年基于硬件的高速 ip 电交换有所发展ip 包的交换容量可以高达数百 gbit/s但是仍然无法匹配 wdm 光传输信道带宽的需求由于电交换的限制 无论开关采取 crossbar 式或者共享缓存形式要达到超过 1tbit/s 的交换容量 必须采用多级的信道交换的体系结构这种体系结构可以是全电交换的也可 以在中间层加入光开关交换2但无论怎样采用多级交换从物理层上来说降 低了 ip 路由的健壮性而且采用如此复杂的核心路由设备极大地增加了设备的 体积和整体运营的成本 因此采用全光 wdm 交换建立 t 比特光数据包交换和路由实现从端到 端的对于 ip 包透明的 ip over wdm 方案在核心交换和路由部分不需要光电/ 电光转换显得十分必要传统的光传输方式需要建立中间层如 sonet/sdh 和 atm这样不可避免地带来了冗余的问题如果采用 ip over wdm方案由 于 ip over wdm 使用较少的中间层而且可以更好的利用成熟的光接口因此将 成为下一代以太网的有效的解决方案 目前在光层上按照交换粒度区分有三种交换方式光路交换波长路 由光分组交换和光突发交换其中光突发交换与光分组交换有着密切的关 系 光路交换通常是指波长交换(或路由)即:当有通信请求时 首先要建立波 长通道一旦成功 主叫用户和被叫用户之间就建立起了一条实或虚的波长通 光突发交换边界组装和调度算法的研究 第一章 obs 的概念 2 道 并且在通话过程中始终由二者占用直到通话结束在这种方式下 除了 全光波长交换尚有困难 非全光的波长交换和光纤光缆空间交换比较成熟线 路交换采用双向资源预留方式设置光通路中间节点不需要光缓存可提供有 保证的服务但线路交换是粗粒度的不能实现统计复用带宽利用率低不 适于传输突发速率的数据波长通道的建立要等待一段时间对长距离网络来 说其回环时间round trip time大延迟长另外由于波长数目有限线 路交换不能建立全连接的网络导致网络中负载的不均衡当波长数不足时 很容易引起阻塞3 光分组交换的概念可以看作是电的分组交换概念在光域的延伸 交换粒度 以高速传输的光分组为单位4 图 1-1 光分组交换节点结构 figure 2-1 the structure of oxc for ops 虽然光分组可长可短在光域中进行分组交换能很好的适用 ip 数据业 务 但要在全光域中实现却是不容易做到的首先 由于交换设备必须具备 处理最小分组的能力 光分组交换要求节点的处理能力非常高光逻辑器件还 很不成熟 且没有性能较好的光存储器其次 光信号处理技术不成熟这 样 只有在节点处进行 o/ ee/ o的转换 因此早先提出的全光交换 要求控制信号在光域处理 但由于上述所说 的光分组交换对光子器件提出了很高的要求有很多关键技术如快速严格同 光突发交换边界组装和调度算法的研究 第一章 obs 的概念 3 步光缓存等还有待突破光逻辑器件到目前为止依然无法实用化等原因 全光分组交换只能进行实验室演示因此目前国际上通行的做法实际上已经脱 离了早期所谓实现分组透明交换的初衷 采用的是光电混合的办法实现光分组 交换 即数据在光域进行交换 而控制信号在交换节点被转换成电信号后再 进行处理5 虽然分组/信元交换能对 dwdm 的巨大带宽进行更灵活更有效地分配和 利用但是在电域里实现分组交换 很显然这样做系统开销会增加 并且电 的处理速度总比不上光传输容量的增加速度 最终这将成为整个网络的瓶 颈 而影响到整个网络性能的提高 目前世界上许多发达国家已经开始进行光分组交换网方面的研究如欧洲 race 计划的 atmos 项目acts 计划的 keops 项目以及 smop 项目美国 的 darpa支持的 pond项目和 cord项目英国 epsrc 支持的 waspnet项 目日本 ntt 光网络实验室的项目等其中欧洲方面的研究起步最早取得的 成果最大主要是 race 的 atmos(atm optical switching)结构欧洲 acts advanced communications technology and services的 keops(keys to optical packet switching) 结构以及共享内存光分组smopshared-memory optical packet结构6 目前成熟的光路由器的控制部分仍然要用电控制处理普通的 32 路 wdm 以 10gbit/s 的速度传输的话传输总容量将达到 320 gb/s 直接在光路由器中 对 ip 数据包进行路由的主要限制在于路由器电处理和控制能力和容量上 一 个普通的 44byte 的 ip 包在 10 gb/s wdm 信道上的只能持续 35.2 ns 的传输时 间 为了降低核心路由器对于其控制的光信道的负担从而增加路由器整体的吞 吐量应该需要把零散的 ip 包整合成一个较大的数据包改变数据包的颗粒度 以适合路由器处理时间的需求因此 obs 的概念得以产生 1 . 2o b s网络系统的引入 光突发包的概念首次引入主要是在 80 年代其开始应用于在 tdm(时分多 路)上集中传输声音和数据信号7每个突发包在 obs 中都是有表头和负载两 部分组成的负载的长度信息携带在表头中obs 使用分离的波长/信道方式 光突发交换边界组装和调度算法的研究 第一章 obs 的概念 4 传送突发包的负载和它的表头突发包负载也被称为数据突发包突发包的表 头被称为 burst header packet(bhp) obs 的一个本质的特征是突发包负载和他们的包头在实际传输过程中的分 离这有助于表头在光核心路由器进行便利的电处理并且提供突发包负载的端 到端透明光传输因此 obs 网络可以被认为像二个被叠加在一起的网络: 纯粹 的光网络传递数据 burst 和混合的控制网络传递 bhps控制网络仅仅是一个 packet 传输的网络 以 bhps 所携带的信息为基础光网络中控制数据突发包的 路由上述的表头和负载的分离可以充分利用电交换技术的成熟和光交换信道 的高容量两者的优势8 对于“突发包颗粒度的传输”的这个设想可以建立在有相同的目的地址和载 荷大小差不多以及诸如像 qos服务品质的关键需求等因素的基础上同一 类的 ip 包被组装在一个突发包之内并且被通过主干网发送到同一个目的地在 一个 obs 网络中packet 进入突发包之前在网络入口先行装配并且在网络出口 目的地址的边缘路由器中解包还原 packet 突发交换obs兼有波长路由和光分组交换的优点而同时避免了其缺 点obs 是基于单向预留协议突发数据随着控制建立包后而无需等待 响应包这样就比光路交换大大减少了端到端的时延9当将之应用于下一代 光互联网控制包将在每一个中间 ip 节点实体建立一条全光路径通过配置 wdm 交换而相应的突发包如多个 ip 包在经由的中间节点将仅通过预 配置好的 wdm 交换在高速智能光器件不完全成熟条件下它比分组交换实 现容易同时它能很好的支持 qos 和优先级服务满足多种多样的业务需求 因此obs 是当前全光网通信的一种最佳选择 1 . 3 本论文的研究重点和创新之处 本论文主要研究光突发交换网络中边缘路由器的组装和调度算法以及相关 的网络参数对路由器性能的影响 论文的主要工作与创新在于 1 原来大多数的网络流量分析着重于利用泊松排队模型给出理论预 测这种分析由于没有考虑到网络实际流量的突发性因此与实际 的性能表现有一定的差距本论文是建立在 ip 数据流的自相似特性 光突发交换边界组装和调度算法的研究 第一章 obs 的概念 5 的基础上对边缘路由器的模型结构和数据组装算法进行设计的 2 在分析丢包率的时候针对同速率不同信道数和同容量不同速率两 种基本情况仿真了边缘路由器的组装和调度过程这更符合输出 光信道 dwdm的情况 3 论文模拟计算了输出数据包的突发特性以及输出信道参数与边缘丢 包率的关系从而得到突发包输出流量的形状时延和突发特性受 组装缓存和调度最大时延的影响以及边缘丢包率受输出参数和输入 数据包自相关参数的制约等结论论文同时涉及的网络参数较多 通过改变单变量从而得出该参数对路由器性能相应的影响 本文的研究主要通过自相似网络流量模型和边缘路由器功能模型的建立 借助于计算机仿真的方法得到相应的分析比较结果 光突发交换边界组装和调度算法的研究 第二章 obs 网络概述 6 第二章o b s网络概述 对 obs 的理解可以从以下几个方面展开网络系统的结构突发控制方 法边缘和核心节点算法优化要求 2 . 1o b s的网络系统结构 2 . 1 . 1 o b s网络的物理结构 a c e s s l a y e r a s s i g e n m e n t l a y e r o p t i c a l l a y e r 图 3-1 obs 网络系统结构图 figure 2-1 the structure of obs networks 图 2-1 给出光突发交换系统结构obs 包含全光核心交换机wdm 光网 络链路和电的边缘路由器10在边缘节点收集来自接入网的数据流量并 会聚成较大的数据单元即突发包burst核心网络的核心节点可以无需任 何处理透明的交换突发数据整个系统需事先在边缘路由上通过控制信令 从而使得系统预留资源并配置交换矩阵要做到这样只要让控制包与数据包 突发包完全分离通过不同波长传输就可以了控制波长需经过 o/e/o 处 光突发交换边界组装和调度算法的研究 第二章 obs 网络概述 7 理而数据在光域进行交换透明传输 2 . 1 . 2 o b s的网络分层结构 obs 协议参考模型如图 2-2 所示分为三层接入层obs 层和物理层 11 图 2-2 obs 网络分层结构图 figure 2-2 the structure of layers in obs 接入层是 obs 层的用户层可以为目前存在的各种网络如 ipatmsdh 等也可以是终端用户obs 层向上层提供各种 obs 服务它又可分为适配子 层网络子层链路子层各层功能如下 1) 适配子层的功能是接入层和光层间比特率的适配上层数据的会聚分 类和整形及突发数据分组的组装和拆卸 2) 网络子层的功能是读取控制分组中的信息并根据网络的状况资源拓 扑等进行路由和通道调度在源边界路由处网络层还要完成分组头 的产生和 offset time 的设置 光突发交换边界组装和调度算法的研究 第二章 obs 网络概述 8 3) 链路子层通过波长和资源分配实现业务到物理媒质的控制并对数据流 进行比特控制以满足在物理媒质上传输的要求 物理层实现光比特的透明传输和放大光交换 2 . 1 . 3 o b s的核心路由器 核心节点的基本结构如图 2-3 所示每根光纤有多个波长其中有一个特定 波长携带信令控制分组经 o/e 转换进入控制单元控制单元读取控制分组中 的信息根据控制分组中的信息及掌握的网络状况进行路由以及控制通道和数 据通道的调度和资源分配和处理阻塞等产生相应的控制信号设置交换矩阵 波长转换器fdls如果有的话等为突发数据分组提供直通通道或预留资 源 c o n t r o l u n i t f d l s o p t i c a l s w i t c h w c w c w c o / e b h p - t x f i b e r f i b e r d c g e - s w i t c h c c g m u xd m u x o / e o / e b u f f e r 图 2-4 obs 核心路由器结构图 figure 2-3 the structure of core router of obs 核心路由器的控制单元由消息引擎交换控制器组成消息引擎含有一个 高速缓存可以存储路由信息和各种资源信息库连接请求通过消息引擎发给交 换控制器具体包括解析消息做出判决产生波长预约的消息传给交换矩 光突发交换边界组装和调度算法的研究 第二章 obs 网络概述 9 阵并产生新的信令消息传给下一节点交换控制器维护一张时间调度表并 及时的发送配置信息给交叉设备控制单元将完成所有的意外处理时延估算 和标准的 oam 及流量控制等12 光交换矩阵实现将任意输入端口光纤中的任意波长通道交换到任意输出端 口的相应波长通道从而为数据分组提供光通路实现突发数据的交换电交 换交换矩阵则负责为控制分组的路由 核心路由器的任务是对光突发数据进行转发与交换每个突发包由具有相 同出口边缘路由器地址和相同 qos 要求的 ip 包组成突发数据是光突发交换 网中的基本交换单位 如图 2-3 所示的 obs 网核心路由器结构这里假定其入口出口光纤数均 为 n每根光纤的波长数为 k .其中一个波长传输 dcg这个波长在各个中间 节点首先要进行 o/e 变换然后再进行电的路由表查找交换矩阵控制等处理 过程最后更新 dcg 并进行 e/o 变换 ;其余(k-1)个波长传输突发数据这些 波长在各个中间节点都不需要 o/e/o 变换 从而保证了数据的透明性 而在光分组交换中为了提取光分组头在每个节点对所有波长都必须提 取一部分光信号进行 o/e/o 变换因而过于复杂而且这种光信号提取方式也 会严重影响其再生距离图中控制分组进行 o/e 变换后可以进入 buffer 中暂 存等待转发表查找建立交换连接等入口 fdl 在光分组交换方式中是必需 的在 obs 中通过让 bcp 比对应的突发数据提前适当的一段时间 t 出发 为突发数据预约恰好相等的一个时间段可以使所有中间节点省去入口光缓存 fdl;还可通过将业务区分为不同的优先级为优先级高的突发数据设置较长的 时间偏移量 t 使其获得更大的预约成功机会来实现 wdm 层的 qos 保 证 光交换矩阵是光突发交换系统的核心器件和决定网络性能的关键因素目 前提出的光突发交换矩阵的典型结构有基于空间光开关矩阵和基于awg的光 突发交换结构半导体光逻辑门soa波导开关微电子机械光开关 mems: micro electro mechanical system液晶光开关等光开关技术和集成 化都取得了很大的突破13 机械开关在插损隔离度消光比和偏振敏感性方面都有很好的性能但 光突发交换边界组装和调度算法的研究 第二章 obs 网络概述 10 它的开关尺寸比较大开关动作时间比较长一般为几十毫秒到毫秒量级而 且机械开关不易集成为大规模的矩阵阵列 随着液晶技术的成熟液晶光交换机将会成为光网络系统中的一个重要设 备该交换设备主要由液晶片极化光束分离器成光束调相器组成而液晶 在交换机中的主要作用是旋转入射光的极化角当电极上没有电压时经过液 晶片的光线极化角为90当有电压加在液晶片的电极上时入射光束将维持它 的极化状态不变 而由声光技术实现的光交换机可以实现微秒级的交换速度可方便地构成 端口较少的交换机但它不适合用于矩阵交换机 波导开关的开关速度在毫秒到亚毫秒量级体积非常小而且易于集成为 大规模的矩阵开关阵列但其插损隔离度消光比偏振敏感性等指标都比 较差 开关速度扩展性可靠性插损 2d memsms32x32 to 512x512震动敏感37db 3d memsms大矩阵特敏感 3d fast memsus liquid crystalms有限可靠低 liquid crystal grating0.1ms小矩阵可靠1 是整数 基于偏置时间的 qos 能分离等级 而相应的高优先级可能获得需要的带宽(波长)不管低优先级的负荷如何换句 话说 在给定时间上的带宽以分层次序分布 从最高优先级(-1 级)到低优先 级 (0 级)这样即使阻塞暂时存在最高优先级仍可不受阻塞影响 第 2 种类型的阻塞 通常涉及基于约束的路由算法 对均匀流量分布的 网络是可靠的 .基于偏置时间的 qos 不受这些算法约束 因此 能由任何适当 的路由算法而很好的工作 在边缘路由器中采用了 lauc-vf 算法可以很好 的利用时间间隙从而减少丢包率保障 qos性能 基于偏置时间的 qos对每个突发包根据它的优先级别分配不同的额外偏置 时间通过使用额外的偏置时间能实现各级分离(或服务区分)提供端到端优 先级实现端到端 qos 我们主要讨论使用基于偏置时间的 qos方案解决级间争夺问题为简单起 见假设只有两级(obs)服务0级和 1级而且 1级的优先权高于 0级在基 于偏置时间的 qos方案中给出 1级有高优先权的资源预约对 1级流量给出额 外的偏置时间为 1 0 t(而 0级的为0 0 0 =t)另外假设基本偏置时间相对额外偏 置时间可忽略一条链路数据只有一个波长实际模拟中不止一个波长但 是波长资源的不足是一样的 现在假设 i a t 和 i s t 分别为 i级请求(用 req(i)表示)的到达时间和服务开始时 间l(i)是由 req(i)请求的突发长度=0和 1假设第 1个请求到达时没 有突发包在服务中考虑下面 2种情况可能在 2个级别之间流量会有分配冲 突 第 1种情况req(1)首先到达并预约波长而 req(0)后到达显然如果 0 a t 1 s t 或 1 s t +=则可避免阻塞给出的 1 0 t 只是稍后于 0 a t 1 0 t 必 光突发交换边界组装和调度算法的研究 第二章 obs 网络概述 17 须大于 0级中所有突发包中最长的突发包长度才能为 req(1)完全避免由 req(0)引起的阻塞18 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 18 第三章obs数据流理论分析 3 . 1自相似与分形 3 . 1 . 1 自相似的特征 在许多实际场合人们发现排队分析所得的预测结果与实际观察到的性能 差异很大我们知道排队分析的有效性依赖于数据通信量的泊松性质最近 几年有几项研究表明在某些环境中通信量分布是自相似self-similarity的而 不是泊松的19 自相似性self-similarity的概念与另外两个获得广泛注意的概念即分形和 混沌chaos理论有关自相似数据通信量的讨论涉及自相似性存在的证据以 及其关键特征通过研究与泊松通信量相比较这类通信量对于系统性能的意 义在于能为自相似通信量建立模型及估计关键参数在所有这些讨论中我们用 到的一个重要参数hurst 参数进行描述 cantor集揭示了在所有自相似现象中都可以看到的两个特性20 图 3-1 二维 cantor 实例图 figure 3-1 the sketch of 2d cantor 1它在任何小尺度上都有结构如果我们不断地将这个集合的一部分放 大我们就会不断地看到由各种大小的空隙分隔开的点的复杂图样一环套一 环的过程似乎无休无止与此不同的是如果我们用不断放大的尺度看一个光 滑连续曲线我们看到的东西越来越没有什么特征 2各个尺度上的结构是重复的一个自相似结构在所有尺度上都包含着 自己的复制本例如在每一步 cantor集的左上半以及右上半部分都是上一步 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 19 中全集的精确复制本 对于实际现象来说这些特性并不是无限地有效下去的在某一级放大中 结构和相似性就不再有了但在很宽的尺度范围上许多现象表现出自相似 性 从网络性能的观点看也许最引人注目的特征是结团现象的持续存在 对于泊松通信量而言结团只出现在短时间小时间尺度内长时间来看 结团就被平滑掉了在设计一个服务员和缓存排队组成的系统时我们可以将这 种长期的平滑特性考虑进来这意味着由于从长期来看到达是平滑的因此只 需要中等大小的缓存排队可能在短期建立起来但在一个较长的时间段上缓 存会排空掉然而如果突发行为本身是突发的即到达簇也结成更大的簇 那么排队大小就会比泊松通信流量造成的排队更大这就导致一个结果 传统的排队分析由于假定了泊松通信量而可能没有精确预计自相似通信量的性 能 图 3-2 具有自相似分布的流量和指数分布流量的比较 figure 3-2 the comparison of self-similar stream and exponential distribution stream 精确自相似是指一个给定的模式在不同的尺度上重复出现对于一个确定 性时间序列这种精确自相似性可以构造出来然而数据通信量最好看成是一 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 20 个随机过程我们这时只能谈论统计自相似性 作一个类比会有助于理解确定性周期信号的特征是其对于时间变换的不 变性它在时间移动整数个周期的情况下保持不变例如对于周期为 t 的确定 性周期函数)(tg )()(attgtg+= 2, 1, 0=a 与此不同对于一个平稳遍历随机过程过程的统计特性对时间变换保持 不变均值与时间无关而自相关函数只与时间差有关 一个确定性自相似信号对于尺度变换保持不变对于一个随机过程我们 可以说过程的统计特征对时间尺度上的变化保持不变无论是定性还是定量地 看这样的过程都没有特征尺度过程的短期平均行为与其长期平均行为是一 样的这样的非确定自相似性在自然和人工现象中都十分常见自然风景中 地震分布上海流中湍流中股市的涨跌中通信信道上的误码和数据流量 模式中都可以看到它 其中的时间函数在不同的时间尺度上并不是精确重复的但在不同时间尺 度上的波形彼此是类似的 3 . 1 . 2 连续时间定义 自相似随机过程的一种常见定义基于连续时间变量的一种直接的尺度变 换一个随机过程)(tx在统计意义上是以参数 h15 . 0 h自相似的如 果对于任意实数0随机过程)( -h atx与x(t)刚有相同的统计特征这个关 系可以用以下 3项条件表达 1 h a ex(at) ex(t)=均值1 2 h a 2 varx(at) varx(t)=方差2 3 h x x a asatr str 2 ),( ),(=自相关3 参数 h被称为 hurst 参数或自相似参数它是自相似程度的一个主要度 量更确切地说h是一种随机的持续性的度量它是一个随机过程的长程依 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 21 赖程度的长度的一种度量5 . 0=h表示没有自相关性h越接近 1持续性或 长程依赖性的程度越大 3 . 1 . 3 离散时间定义 对于一个平稳时间序列 x我们定义 m重聚集时间序列 ,2 , 1 , 0, )()( =kxx m k m 的方法是将原时间序列分成大小为 m的块然后在各块 中求出平均值这可以表达为 = = km mkmi i m k x m x )1( )( 1 4 例如 )3( x被定义为 3 31323)3(kkk k xxx x + = 5 观察多重聚集时间序列的一种方法是将其看作压缩时间尺度的一种技巧 我们可以认为 )1( x是就这个时间序列而言可能有的最高放大率或最高分辨率过 程 )3( x是将同一过程的放大率减小 3倍的结果由于在每 3个点上进行平均我 们就失去了在最高放大率时可以看到的细节如果经过压缩而过程的统计特性 均值方差自相关等保持不变则我们遇到的就是一个自相似过程 我们也可以将序列 )(m x的各个点看成是过程 x的一个时间平均对于遍历 过程而言时间平均应该等于样本空间平均并且时间平均的方差应该在 m变 大时相当迅速地趋向于零这种情况对于自相似过程并不存在方差确实趋向 于 0但比平稳遍历过程要慢得多 过程正被称为参数为 p的准确自相似exactly self-similar过程0 p l如果对于所有,2 , 1=m有 m var(x) )var(x(m)方差6 )()(r (m) x krk x =自相关7 可以证明参数 与前面所定义的 hurst 参数有关具体地说即 /2)(-1h=对于平稳遍历过程1=而且时间平均的方差以速率m/1衰减到 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 22 零对于自相似过程时间平均的方差衰减得更慢 较弱的一个条件是过程 x被称为是渐近自相似的asymptotically self- similar如果对于所有足够大的 k使得 m var(x) )var(x(m)方差8 )()(r (m) x krk x 时当m自相关9 因此使用这种自相似性定义则多重聚集过程的自相关就和原过程的有相 同的形式这意味着变化的程度或突发性在不同时间尺度上是相同的 前述定义的一个有趣特征是多重自相似过程的自相关并不随着m而趋 于零这个特征与通常用作分组数据模型的随机过程形成对照后一种随机过 程满足下列关系式 0)(r (m) 时当m10 等于零的自相关函数)(r 和白噪声即有着均匀功率谱的纯粹随机的随机 过程的特征是一致的 前述定义的另一个有趣特征是 (m) x的方差在m时减少得比m/1更慢 它以与 3 /1 m 成比例的速率减小通常用于分组数据模型的随机过程的方差以与 m/1成比例的速率减小这后一种减小速率不难理解因为 (m) x是一种时间平 均而对于遍历过程来说它与采样大小为 m的采样平均从统计意义上是等价 的采样平均的方差就等于原随机变量方差除以 m然而 m重聚集合的自相似 过程和采样大小为 m的采样平均并不相同因为自相似过程的统计特性在不同 时间尺度上是持续存在的 3 . 1 . 4 长程依赖性l o n g r a n g e d e p e n d e n c e 自相似过程最重要的特性之一是所谓长程依赖性这个特性是由当增加 时的自协方差)c(的行为定义的 许多过程的自协方差随的增加而迅速衰减例如具有增量 l和均值 的泊松增量过程的自协方差在l时是 0-)r()c( 222 =11 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 23 一般地短程依赖shortrange dependent过程满足如下条件即它的自 协方差至少衰减得同指数方式一样快 | c(k) k 时当|k10=时当x0的 pareto 分布其密 度和分布函数如下 0)()(=xfxf)(kx 18 1 )( + = x k k xf = x k xf1)()0;(kx19 其均值为 kxe 1 = ) 1( 20 参数 k确定这一随机变量可以取的最小值参数 确定这一随机变量的均 值和方差 如果2则这一分布具有无穷大的方差而如果1它就具有无穷 大的均值和方差 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 25 图 3-3 pareto分布的概率密度 figure 3-3 the probability distribution density of pareto 图 3-3 是 pareto 分布密度函数在不同参数下的比较 3 . 2网络自相似数据量 报道证实多种实际连网情形中数据通信量的模式可以用自相似过程很好 地描述 3 . 2 . 1 以太网通信量 on the self-similar nature of ethernet traffic这篇论文随后修订扩充 为lela94121虽然在此前有好几篇论文对后来被证明可用自相似过程 描述的数据通信量作了非形式的描述但谁也没有引进自相似这一关键概念 这篇论文打破了使用泊松通信量假设进行直接的排队分析就足以描述所有网络 通信量的幻想利用大量的数据和仔细的统计分析这篇论文指出以太网通信 量需要采用一种新的描述和分析方法这篇论文触发了这个论题方面的大量研 究几乎每个月都有新的论文出现它们证实在其他类型的数据通信量中也存 在自相似性 这篇论文报告了在 1989到 1992年间所做的详细的高分辨率s20 的时 间精度以太网通信量测量所得的结果数据中包括四组通信量测量值每组 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 25 图 3-3 pareto分布的概率密度 figure 3-3 the probability distribution density of pareto 图 3-3 是 pareto 分布密度函数在不同参数下的比较 3 . 2网络自相似数据量 报道证实多种实际连网情形中数据通信量的模式可以用自相似过程很好 地描述 3 . 2 . 1 以太网通信量 on the self-similar nature of ethernet traffic这篇论文随后修订扩充 为lela94121虽然在此前有好几篇论文对后来被证明可用自相似过程 描述的数据通信量作了非形式的描述但谁也没有引进自相似这一关键概念 这篇论文打破了使用泊松通信量假设进行直接的排队分析就足以描述所有网络 通信量的幻想利用大量的数据和仔细的统计分析这篇论文指出以太网通信 量需要采用一种新的描述和分析方法这篇论文触发了这个论题方面的大量研 究几乎每个月都有新的论文出现它们证实在其他类型的数据通信量中也存 在自相似性 这篇论文报告了在 1989到 1992年间所做的详细的高分辨率s20 的时 间精度以太网通信量测量所得的结果数据中包括四组通信量测量值每组 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 26 都代表了连续的 20到 40小时的以太网通信量并包括总共 100多万个分组数 据是各个以太局域网上收集的 这组测量值包括了连续 27小时对以太网通信量的监测结果基于多种统 计检验估计出以大网通信量是自相似的并且其 hurst 参数 h是 0.9 will971中采用并进行了细致分析的方法是将以太网通信量描述为许 多 pareto 型的 onoff通断信源叠加产生的每个这样的信源都在 on 阶段和 off或空闲时段之间交替在 on时段信源就发送一串分组如果我们 假设各个时段都是由独立同分布的随机变量描述并且每个信源都服从同一种分 布那么就可能但很困难确定多个这种信源的叠加或复用后的行为实际 上这种方法可以用来产生对应于传统通信量模型的通信量关键的因素是要 使用一个有限方差分布诸如指数或几何分布来描述 on和 off时段的长度 可以看到这些模型并不反映真实的以太网通信量 一种能采取的方法是用具有无穷大方差的分布特别是采用参数 介于 1 和 2 之间的 pareto 分布作为 onoff时段的模型在这个范围内 pareto 分布 随机变量具有有限均值和无穷大的方差可以证明许多 pareto 分布随机变量的 叠加结果就是 hurst 参数 2/ )3(ah=的自相似通信量对于 21h其中25 这可以重写为 )2log()log(/loghnhsr26 如果我们将r/s与 n的关系画在一张对数对数图上则所得曲线应 符合一个斜率为 h的直线24 3 . 3 . 3 w h i t t l e估值器 方差时间图和 rs 图属于启发式或肉眼直观的方法并应该如此对待 光突发交换边界组装和调度算法的研究 第三章obs数据流理论分析 29 它们不应该用来对 h进行精确估计而只能用来粗略地估计一个给定的数据集 是否与自相似特征一致5 . 0h或者它是否落入传统的短程依赖模型 5 . 0h的范围内而 whittle 估值器是一种具有更多的统计严格性但也要 求底层的数据满足一定假设条件的估值器 3 . 3 . 4 周期图 随机过程理论中的一个经典问题是利用过程有限的一段实现估计平稳过程 )(tx的功率谱)(s根据)(tx在一段有限时间内的一个样本对于离散平稳随 机过程自相关和谱密度定义为 )()()(ktxtxekr+= = k jk ekrs )()(27 如果我们假设过程从相关的角度看时间平均等于样本空间平均是遍历 的那么我们就可以用下式估计其自相关 = += 1 0 )()( 1 )( n n n nxknx n kr28 由于谱密度)(s是自相关函数)(kr的傅里叶变换可能在自相关函数上 做一次傅里叶运算就可以为谱密度产生一个好估计 在离散时刻定义的随机过程对,2 , 1 , 0,)(=txtx t 的谱密度可以通过在时 间段 n上取傅里叶级数做出估值 = = n k jk kn ex n i 1 2 | 2 1 )( 29 这个估值器在文献中被称为一个周期图periodogram或强度函数 3 . 3 . 5 估计 h 假定我们假设所观察到的时间序列是参数为 h的一个自相似随机过程并且 我们假设它具有一个特定的形式那么该过