分形网络流量的时间延迟计算

分形网络流量的时间延迟计算 - 1 - 分形网络流量的时间延迟计算# 王安琪，李 明** (华东师范大学信息科学技术学院，上海 200241) 5 摘要:本文介绍了分形流量通过服务器时的时间延迟计算 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 。与传统流量的约束界相比， 在分形流量的统计约束界下，分形流量引入小尺度收缩系数 r的(2D-5)次 幂即 r.^(2D-5)和大 尺度收缩系数 a 的(-H)次幂即 a.^(-H)，能缩小传统的约束界。r 是小尺 度因子，a 是大尺 度因子。本文的贡献在于给出了一些实例 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 分形流量的延迟 d与小尺度 收缩系数 r.^(2D-5) 和大尺度收缩系数 a.^(-H)的关系。结果表明，随着 r.^(2D-5)和 a.^(-H) 的减小，分形流量的10 延迟 d减小，小尺度因子 r和大尺度因子 a增大。 关键词:网络流量;分形流量;收缩系数;时间延迟 中图分类号:TN911.72 Delay analysis of fractal traffic passing through network 15 servers WANG Anqi, LI Ming (School of Information Science Technology, East China Normal University, Shanghai 200241) Abstract: This paper introduces method of delay analysis of fractal traffic passing through network services. Compared with conventional traffic, small-scale and large-scale tighten 20 coefficients of fractal traffic are r.^(2D-5) and a.^(-H) respectively, which can flexibly tighten the conventional traffic. r is small-scale factor and a is large-scale factor. Contribution presented in this paper is that we give some cases to analyze the relationship between delay d and tighten coefficients r.^(2D-5) and a.^(-H) of fractal traffic. We found that with the decrease of r.^(2D-5) and a.^(-H), delay d becomes smaller and scale factors r and a become larger. 25 Key words: network traffic; fractal traffic; tighten coefficient; time delay 0 引言 在网络通信系统中，流量通过服务器会产生时间延迟[1]，时延分析是一个极具挑战性的 问题。很好地把握时延有助于确定网络容量和通信状态，提高系统的服务效率。计算机通信30 领域有两类通信系统:实时系统和非实时系统。其中，实时通信系统规定预定的时间延迟[2,3]， 按约束强度又细分为硬实时系统和软实时系统两类。在硬实时系统中，确定的时延约束必须 有保证，否则认为通信失败[4,5,6,7]。因此，时延估算对硬实时通信系统而言显得尤为重要。 本文着重介绍流量通过硬实时通信系统的时延估算方法，具体借助最小加卷积[8]进行运 算。进而引入分形流量，用分形维度 D 和 Hurst 指数 H 两个参数描述。与传统流量相比，35 分形流量引入小尺度收缩系数 2 5Dr ?? 和大尺度收缩系数 Ha?? ，据此研究了分形流量的时间延 迟与两个收缩系数的关系。研究发现， 2 5Dr ?? 和 Ha?? 越小，时间延迟越小。 文章第一部分包含传统网络流量的概念及时延的计算方法，第二部分介绍分形流量，第 三部分说明本文采用的分形流量时延的计算方法，第四部分展示分形流量时延的研究结果， 第五和第六部分对全文进行讨论和 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 。 40 - 2 - 1 传统流量的时延分析 1.1 到达的流量 ( )x t 表示通信系统中到达服务器端的流量时间序列。 ( )A t 表示[0, ]t 时间间隔内的流量 总和，t > 0。上界约束满足[9] 0 ( ) ( ) t A t x t dt t?? ???? ?? ???? (1.1) 45 这是传统流量的约束形式。 ( )A t 称为流量的到达曲线，是广义增函数。 传统流量以 ( , )?? ?? ?? 满足: 为约束界，约束模型记为 ( ) ( , )A t ?? ???? 。?? 和 00 lim ( ) t t x t dt ?? ?? ???? (1.2) 0 ( ) lim t t x t dt t ?? ???? ?? ?? (1.3) 令流量 ( )x t 的约束函数为 ( )F t t?? ???? ?? ，是线性函数，可以通 过估计?? 和 ?? 来确定流50 量的约束界，从而限制到达服务器的流量范围。?? 表示 ( )A t 的突发性，是流量的局部特性。 ?? 表示 ( )A t 的长期平均率，是流量的全局特性。由式子(1.2)和(1.3)可知，传统边界 ( , )?? ?? 的范围宽松，提供给用户的网络资源会需求过剩，所以引入统计边界，缩小约束范围，提高 通信效率。下文会进行讨论。 1.2 离开的流量与延迟 55 ( )A t 到达服务系统 ( )S t 后，经过等待时间 tw和服务时间 ts 离流量 开服务系统，产生时 间延迟 d。离开系统的流量记为 ( )Y t ，过程如下图 1 所示。 ( )S t 称作服务曲线，与 ( )A t 拥 有相同的性质，满足 ?? ?? ?? ??S t A t?? 。 Service device S(t) Buffer tw = waiting time Departure traffic A(t + d) Arrival traffic A(t) d = delay = tw + ts ts = service time 图 1 单个服务器排队系统 60 Fig. 1 Queuing system for single server 可得 ( ) ( )Y t A t d?? ?? 。又由式子(1.1)得 ( ) ( )A t d t d?? ???? ?? ?? ?? ，所以 ( ) ( )Y t t d?? ???? ?? ?? 。 1.3 最小加卷积 , ( )s t R?? ?? ?????? ，当 s t?? 时有 ?? ?? ?? ??f s f t?? ，则 f 称为广义增函数。 S 表示当 t < 0 时 ?? ??=0f t 的广义增函数或序列的集合。设 1 2( ) ( )X t X t S??、 ， 符号??表示最小加卷积运65 算，定义为: 1 2 1 2 0 ( ) ( ) inf { ( ) ( )} u t X t X t X u X t u ?? ?? ?? ?? ?? ?? (1.4) //.paper.edu - 3 - 中国科技论文在线 因为 ( )A t 是广义增函数， ( )S t 与 ( )A t 有相同的性质，所以 ( )S t 也是广义增函数。又 由文献[10]可知， ( )S t 、 ( )A t 和 ( )Y t 满足 ( ) ( ) ( )A t S t Y t?? ?? 。令 ( ) ( ) ( )ASY t A t S t?? ?? ，则 有 ( ) ( ) ( ) ( )ASY t Y t A t d t d?? ???? ?? ?? ?? ?? ?? ， 0 ( ) inf { ( ) ( )}AS u t Y t A u S t u ?? ?? ?? ?? ?? 。流量通过服务70 系统的延迟d 为: ( )ASY t td ?? ?? ?? ?? ?? ?? (1.5) 所以，对于传统的网络流量 ( )x t ，求出到达曲线 ( )A t ， 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 服务曲线 ( )S t ，并结合给 定的约束界?? 和 ?? ，即可求得延迟 d。 2 分形流量的时延分析 75 由前文可知传统流量的约束界为 ( , )?? ?? ，为了进一步提高约束强度，有学者引入分形 流量的统计边界 ( , )?? ???? ?? [11]。分形时间序列有自相似性(SS)和长相关性(LRD)两个特性，分 别用分形维度 D 和 Hurst 指数 H 表示。分形流量将传统流量的突发性约束?? 与局部特性参 数 D 和小尺度因子 r 结合，将长期平均率约束 ?? 与全局特性参数 H 和大尺度因子 a 结合。 本节从分形时间序列的角度介绍求解统计界 ( , )?? ???? ?? 和时延 d 的方法，如下所述。 80 2.1 分形维度 D 和 Hurst 指数 H 许多对分形序列的研究都基于分形高斯噪声(FGN)模型，这类方法只能用单个参数来线 性表示 FGN 的统计特性，即 D = 2 – H。研究表明，与 FGN 相比，广义柯西(GC)模型更吻 合实际的流量，且可单独表示分形序列的这两个特性。本文基于 GC 模型对分形流量进行研 究，并根据柯西模型的自相关函数生成流量数据。 85 设 ( )x t 为一个平稳的高斯信号，若自相关函数 ( )C ?? 为: /( ) [ ( ) ( )] (1 | | )C E X t X ?? ?? ???? ?? ?? ?? ???? ?? ?? ?? (2.1) 则 ( )x t 为广义柯西过程[12]。?? 为时间间隔，E 为数学期望，0 2 0?? ???? ?? ??， 。 若 ( )C ?? 不可积，则 ( )x t 为 LRD 长相关。有近似关系 ( )~C ???? ?? ???? ????， (2.2) 90 GC 过程的 Hurst 指数为: 1 / 2H ???? ?? (2.3) 若 ( )C ?? 在 (0, )?? 充分光滑且有近似 (0) ( )~ 0C C c ???? ?? ???? ??， (2.4) GC 过程的分形维度为: 95 2 / 2D ???? ?? (2.5) 根据文献[13]，用白噪声信号 ( )w t 为激励生成服从 GC 过程的流量 ( )x t ，系统的冲激函 数为 ( )h t ，则有 ( ) ( ) ( )x t w t h t?? ?? (2.6) ??代表卷积运算。白噪声的频谱函数取为 ( )( ) [ ( )] | |j f cW f F w t e f f ???? ?? ??， 。F 是傅里叶变100 换， ( )f?? 是随机分布的函数， cf 是截止频率，所以 1( ) [ ( )]w t F W f???? 。在白噪声的激励 //.paper.edu - 4 - 中国科技论文在线 下，系统函数 ( )H f 满足 2( ) = [ ( )]H f F C ?? ，则有 1 0.5( ) {[ ( ( ))] }h t F F C ?????? 。因此，本实验 中我们给定流量的 D 和 H，据式子(2.6)即可生成满足条件的流量序列 ( )x t 。 2.2 尺度因子 r 和 a 由文献[11]可知，令 ( )x t 为平稳高斯过程，若 ( )x t 是 v 阶局部自相似序列，则它的突发105 性约束可表示为 1vr ???? ?? ，D = 2 – v/2。若 ( )x t 在大时间尺度上是指数为 H 的自相似序列，则 长期平均率约束可表示为 Ha ???? 。所以分形流量到达曲线的上界为 2 5( ) D HA t r a t?? ???? ???? ?? (2.7) 突发性约束和长期平均率约束分别为 2 5Dr?? ?????? ?? 和 Ha?? ?????? ?? ，有 ( )A t t?? ???? ???? ?? ，所以 约束模型为 ( ) ( , )A t ?? ???? ???? 。令系数 2 5Dr ?? 和 Ha?? 小于 1，则?? ???? ?? ， ?? ???? ?? ，?? 缩小到110 2 5Dr ???? ， ?? 缩小到 Ha ???? ，加强了对传统边界 ( , )?? ?? 的约束。 对于到达的流量 ( )x t ，根据初始选取的约束值?? 和 ?? 规定收缩系数 2 5Dr ?? 和 Ha?? ，即可 求出小尺度因子 r 和大尺度因子 a。特别地，当 2 5Dr ?? 和 Ha?? 等于 1 时，有 r = a = 1，为传统 流量。 例如某一流量 ( )x t ，设 00 lim ( ) t t sigma x t dt ?? ?? ?? ， 0lim( ( ) / ) t t ro x t dt t ???? ?? ?? ，初始估计值115 5 sigma?? ?? ， 5 ro?? ?? 。令小尺度收缩系数 2 5Dr ?? 和大尺度收缩系数 Ha?? 均等于 0.5，有 ( ) 0.5 0.5 = 2.5 2.5 A t t sigma ro t?? ???? ?? ?? ?? 成立。若流量 D = 1.9，H = 0.8，则 2 5 2 1 . 9 5 0.5Dr r?? ?? ???? ?? ， 0.8 0.5Ha a?? ???? ?? ，可求出 r = 1.78，a = 2.37。该分形流量的统计 约束界为 (0.5 ,0.5 )?? ?? ，传统界为 ( , )?? ?? ，可见统计界能缩 小约束范围。 2.3 时延分析 120 由前文可知，有 ( ) ( ) ( ) ( )ASA t S t Y t Y t?? ?? ?? 。而分形流 量的离开曲线 ( )Y t 为 2 5( ) ( ) ( )D HY t A t d r a t d?? ???? ???? ?? ?? ?? ?? ，得分 形流量的时延为 2 5( ) D HAS H Y t r a t d a ?? ?? ?? ?? ?? ?? ?? ?? ?? (2.8) 对于分形流量，通过到达曲线 ( )A t 、服务曲线 ( )S t 、初始约束界 ?? 和 ?? ，结合收缩 系数 2 5Dr ?? 和 Ha?? ，即可求得延迟 d。 125 本文研究当小尺度收缩系数 2 5Dr ?? 和大尺度收缩系数 Ha?? 取不同值时，时延 d 与系数 2 5Dr ?? 和 Ha?? 的关系，对比在传统界 ( , )?? ?? 和统计界 ( , )?? ???? ?? 下延迟的大小。求出 r 和 a， 观察 r 和 a 与系数大小的关系。 //.paper.edu - 5 - 中国科技论文在线 3 实验方法 设 00 lim ( ) t t sigma x t dt ?? ?? ?? ， 0lim( ( ) / ) t t ro x t dt t ???? ?? ?? 。 为了便于分析，实验中初始选定 10 sigma?? ?? ， 10 ro?? ?? ，满足 ( )A t t?? ???? ?? ，显然约束较为宽松。 引入分形流量，令 2 5Dr ?? 和 Ha?? 依次取 1、0.5、0.2、0.125、 0.1，?? 和 ?? 依次缩小到原先的 1、0.5、0.2、0.125、 0.1 倍，能满足 2 5( ) D HA t r a t?? ???? ???? ?? 。 实验中，根据式子(2.6)生成一列服从 GC 过程的流 量 序 列 ( )x t ， 根 据 式 子 (1.1) 求 出 ( )A t ， 并 取 = 2 (( ))S t A t 。令 2 5Dr ?? 和 Ha?? 分别等于 1、0.5、0.2、 0.125、0.1，根据式子(2.7)求出 r 和 a，根据式子(2.8) 求出延迟 d。将求得分形流量的到达曲线记为 A(t;D， H，r，a)，观察小尺度因子 r、大尺度因子 a、延迟 d 与 2 5Dr ?? 和 Ha?? 的关系。传统流量的延迟记为 1d ，分形 流量的延迟记为 2d ，对比分形流量与传统流量延迟的 大小，用??表示，记为 2 1d d???? 。不考虑流量到达的 时间间隔，本实验的延迟 d 无量纲。具体流程见图 2。 和 取1、0.5、0.2、 0.125、0.1 选取初始的σ和ρ 分别计算d 计算sigma和ro 2 5D r ?? H a ?? 生成流量序列 图 2 延迟 d 计算流程 Fig.2 Process of calculating delay d 4 实验结果 130 本实验一共选取 4 个 case 进行延迟 d 的计算，分形流量到达曲线 A(t; D，H，r，a)和 时延 d 依次如下表所示。 Case 1:D = 1.3，H = 0.95，sigma = 693，ro = 741.1596 表1 case 1到达流量A(t;D，H，r，a) Tab.1 case 1 arrival traffic A(t;D，H，r，a) 135 Ha?? d A(t;D，H，r，a) 分形流量延迟 d 缩小的程度 2 5Dr ?? 和 1 450.7726 A(t;1.3，0.95，1，1) 2d = 1d 0.5 400.5795 A(t;1.3，0.95，1.33，2.07) 2d = 0.8887 1d 0.2 250.0000 A(t;1.3，0.95，1.95，5.44) 2d = 0.5546 1d 0.125 99.4205 A(t;1.3，0.95，2.37，8.92) 2d = 0.2206 1d 0.1 0.9658 A(t;1.3，0.95，2.61，11.28) 2d = 0.0021 1d Case 2:D = 1.5，H = 0.95，sigma = 118，ro = 677.5797 表2 case 2到达流量A(t;D，H，r，a) Tab.2 case 2 arrival traffic A(t;D，H，r，a) 2 5Dr ?? 和 Ha?? d A(t;D，H，r，a) 分形流量延迟 d 缩小的程度 //.paper.edu - 6 - 中国科技论文在线 1 450.5799 A(t;1.5，0.95，1，1) 2d = 1d 0.5 400.6760 A(t;1.5，0.95，1.41，2.07) 2d = 0.8888 1d 0.2 250.7078 A(t;1.5，0.95，2.23，5.44) 2d = 0.5554 1d 0.125 99.5650 A(t;1.5，0.95，2.82，8.92) 2d = 0.2219 1d 0.1 0.7607 A(t;1.5，0.95，3.16，11.28) 2d = 0.0017 1d Case 3:D = 1.7，H = 0.95，sigma = 105，ro = 793.4985 表3 case 3到达流量A(t;D，H，r，a) 140 Tab.3 case 3 arrival traffic A(t;D，H，r，a) 2 5Dr ?? 和 Ha?? d A(t;D，H，r，a) 分形流量延迟 d 缩小的程度 1 450.9283 A(t;1.7，0.95，1，1) 2d = 1d 0.5 400.6963 A(t;1.7，0.95，1.54，2.07) 2d = 0.8886 1d 1.7，0.95，2.73，5.44) 2d = 0.5544 1d 0.2 250.0000 A(t; 0.125 99.3037 A(t;1.7，0.95，3.66，8.92) 2d = 0.2202 1d 0.1 1.1604 A(t;1.7，0.95，4.21，11.28) 2d = 0.0026 1d Case 4:D = 1.9，H = 0.95，sigma = 340，ro = 740.3989 表4 case 4到达流量A(t;D，H，r，a) Tab.4 case 4 arrival traffic A(t;D，H，r，a) 2 5Dr ?? 和 Ha?? d A(t;D，H，r，a) 分形流量延迟 d 缩小的程度 1 451.0740 A(t;1.9，0.95，1，1) 2d = 1d 0.5 400.8055 A(t;1.9，0.95，1.78，2.07) 2d = 0.8886 1d 0.2 250.0000 A(t;1.9，0.95，3.82，5.44) 2d = 0.5542 1d 0.125 99.1945 A(t;1.9，0.95，5.65，8.92) 2d = 0.2199 1d 0.1 1.3425 A(t;1.9，0.95，6.81，11.28) 2d = 0.0030 1d 上表中 1 代表参数?? 和 ?? 没有缩小，0.5、0.2、0.125、0.1 代表?? 和 ?? 分别缩小到 0.5、145 0.2、0.125、0.1 倍。由表可知， 2 5Dr ?? 和 Ha?? 越小，延迟 d 越小，尺度因子 r 和 a 越大。延 迟 d 无量纲。 //.paper.edu - 7 - 中国科技论文在线 (a) 150 (b) (c) (d) 155 图 3 生成的流量序列 (H = 0.95) (a) D = 1.3，(b) D = 1.5 ，(c) D = 1.7， (d) D = 1.9 Fig.3 traffic sequence (H = 0.95) (a) D = 1.3，(b) D = 1.5， (c) D = 1.7， (d) D = 1.9 图 4 case 1 柯西序列和流量序列的自相关函数 Fig.4 case 1 autocorrelation function of Cauchy and traffic sequence 160 case 1 中广义柯西序列和生成流量序列的自相关函数均方误差为 8.9385e-04，所以认为 //.paper.edu - 8 - 中国科技论文在线 本实验用广义柯西过程的自相关函数生成流量的方法合理可用。 (a) (b) (c) (d) 图 5 广义柯西过程的自相关函数 (H = 0.95) (a) D = 1.3，(b) D = 1.5 (c) D = 1.7 (d) D = 1.9 Fig. 5 autocorrelation function of GC process (H = 0.95) (a) D = 1.3 (b) D = 1.5 (c) D = 1.7 (d) D = 1.9 (a) (b) //.paper.edu - 9 - 中国科技论文在线 (c) (d) 图 6 延迟 d 与系数 2 5Dr ?? 和 Ha?? 的关系 (a) case 1 (b) case 2 (c) case 3 (d) case 4 165 Fig. 6 relationship between delay d and coefficients 2 5Dr ?? and Ha?? (a) case 1 (b) case 2 (c) case 3 (d) case 4 上图中，横轴 1 代表?? 和 ?? 没有缩小，0.5、0.2、0.125、0.1 代表?? 和 ?? 缩小到 0.5、 0.125、0.1 倍。由图也可知小尺度收缩系数 2 5Dr ?? 和大尺度收缩0.2、 系数 Ha?? 越小，延迟 d 越小。 5 讨论 170 实验中先选取初始约束界?? 和 ?? ，使得到达的流量满足 ( )A t t?? ???? ?? 。为了讨论方便， 选取 10 sigma?? ?? ， 10 ro?? ?? 。考虑分形流量，引入分形维度 D 和 Hurst 指数 H，则有小 尺度收缩系数 2 5Dr ?? 和大尺度收缩系数 Ha?? 满足 2 5( ) D HA t r a t?? ???? ???? ?? ，加强了对流量的约 束。实验结果表明，引入分形流量能使估计的延迟 d 减小。随着 2 5Dr ?? 和 Ha?? 的减小，延迟 d 减小，小尺度因子 r 和大尺度因子 a 增大。由于没有考虑到流量的时间间隔，本文估算的175 时延 d 无量纲。 6 结论 与传统的网络流量相比，引入分形流量后，传统的约束界限 ( , )?? ?? 变为 ( , )?? ???? ?? ，延 迟 d 也随之减小。?? 和 ?? 分别缩小到 2 5Dr ???? 和 Ha ???? ，加强了约束范围。随着小尺度收缩 系数 2 5Dr ?? 和大尺度收缩系数 Ha?? 的减小，分形流量的延迟 d 减小，小尺度因子 r 和大尺度180 因子 a 增大。 [参考文献] (References) [1] IN??S TEJADO. Dealing with fractional dynamics of ip network delays[J]. International Journal of Bifurcation & Chaos, 2012, 22(4): 537-557. [2] S. Natarajan, W. Zhao. Issues in building dynamic real-time systems[J]. IEEE Software, 1992, 9(5): 16-21. 185 S. Chakraborty, J. Eberspcher. Advances in Real-Time Systems[M]. [3] Springer, New York, NY, USA, 2012. [4] W. Zhao, K. Ramamritham, J.A. Stankovic. Scheduling tasks with resource requirements in hard real-time systems[J]. IEEE Transactions on Software Engineering, 1987, 13(5)5: 564-577. [5] W. Zhao, K.Ramamritham. Virtual time CSMA protocols for hard real-time communications[J]. IEEE Transactions on Software Engineering, 1987, 13(8): 938-952. 190 [6] G.C. Buttazzo. Hard Real-Time Computing Systems[M]. Springer, New York, NY, USA, 2011. [7] A. Raha, S. Kamat, W. Zhao, W. Jia. Admission control for hard real-time connections in ATMLANs[J]. IEE Proceedings: Communications, 2001, 148(4): 217-228. [8] J.Y. Le Boudec, P. Thiran. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet[J]. //.paper.edu - 10 - 中国科技论文在线 Springer-Verlag, 2001, 72(8): 735-742. 195 [9] H. Michiel, K. Laevens. Teletraffic Engineering in a Broad-Band Era[J]. Proc. IEEE, 1997, 85(12): 800-819. [10] M. Li. Delay Bound: Fractal Traffic Passes through Network Servers[J]. Mathematical Problems in Engineering, 2013, 2013(8): 206-226. [11] M. Li. Representation of a Stochastic Traffic Bound[J]. IEEE Transactions on parallel and distributed systems, 2010, 21(9): 1368-1372. 200 [12] M. Li and S. C. Lim. Modeling network traffic using generalized Cauchy process[J].Physica A, 2008,387(11): 2584-2594. [13] M. Li and S. C. Lim. Generation of teletraffic of generalized Cauchy type[J]. Physica Scripta, 2010, 81(2): 025007. 205