基于网络流量自相似特性的研究.ppt

关于网络流量自相似特性的研究 马皓 北大网络实验室 2002年10月31日 提纲 问题提出 自相似的数学描述 产生自相似的原因 自相似对网络性能的影响 国内相关工作 可能的研究方向 问题提出 研究起源 Will Leland, Murad Taqqu, Walter Willinger, and Daniel Wilson, On the Self-Similar Nature of Ethernet Traffic (Extended Version), IEEE/ACM Transactions on Networking, February 1994.(Bellcore 510 citations) Vern Paxson, Sally Floyd, Wide-Area Traffic: The Failure of Poisson Modeling, IEEE/ACM Transactions on Networking,3(3), June 1995. (Lawrence Berkeley Lab. 408 citations, FTP Telnet) J. Beran, R. Sherman, M. S. Taqqu, and W. Willinger, Long-Range Dependence in Variable-Bit-Rate Video Traffic, IEEE Transactions on Communications, February/March/April, 1995. (193 citations) 问题提出 意义 开拓了全新的研究领域，经典的理论分析依据（如泊松过程和马尔可夫模型），不在适合网络流量的分析和建模。 “…..the (r)evolution of the Internet is impacting the world of mathematics in the small as well as in the large --- both on how mathematics is done, and, for understanding the network itself, on what sort of mathematics is done --- and why this, in turn, makes Internet engineering a gold mine for new, exciting and challenging research opportunities in the mathematical sciences.” by Walter Willinger and Vern Paxson in “Where Mathematics meets the Internet” “Goodbye Poisson” “Hello Fractal” ! 问题提出 什么是自相似？ 为什么研究自相似？ 产生自相似的原因？ 泊松过程—随机变量(单位时间呼叫到达的次数)是独立的、且服从相似分布，即 P[Xk＝n]＝e－λ△t(λ△t)n/n! (n≥0) 马尔可夫模型—对过去具有有限记忆，即在已经知道“现在”的条件下，其“将来”不依赖于“过去” 时间t与过去时间t-s，若s足够大，则t与t-s时的业务量是不相关的，即仅考虑s较小时业务到达间的相关性，称之为短时相关Short Range Dependence—SRD模型 自相似的数学描述 网络流量模型 时间序列，表示每单位时间到达的字节数或数据包数量 自相似的物理描述 网络流量在很宽的时间尺度内存在突发现象，“Burst” 时间尺度—几十毫秒、秒、分钟、小时 自相似的数学描述 数学定义 假设前提—平稳随机过程，即统计特性（均值、方差、相关等）不随时间推移而变化。一阶平稳（均值为常数），二阶平稳（均值和方差为常数，任意两时间点之间的协方差只取决于时间间隔，又称之为广义平稳） 自相关函数定义为： r(k)＝E[(Xt－μ)(Xt+k－μ)]/E[(Xt－μ)2] 自相似的数学描述 自相似 条件1—针对一个平稳随机过程 X＝(Xt: t＝0,1,2,3…) 条件2—其自相关函数满足r(k) ～ k－βL1(k)，当k→∞，其中0＜β＜1，L1是慢变函数，即对所有x＞0，limt→∞L1(tx)/L1(t)＝1（常见的慢变函数，如L1(t)＝常数，L1(t)＝㏒(t)） 条件3-对X进行堆叠，堆叠产生的时间序列为X(m)＝(Xk(m)：k＝1,2,3 …)，其中 Xk(m) ＝1/m(Xkm-m+1＋ …＋Xkm)，k＝1, 2, 3, … 自相似的数学描述 自相似(Exactly secon