（计算机系统结构专业论文）网络流量的半马尔柯夫模型.pdf

- 。一j 一， 严 摘要 流量模型研究是网络领域的一项基础性研究，它是网络性能分析和通信网络规 划设计的基础高质量的流量模型对于设计高性能网络协议和高效的网络拓扑结 构；对于设计高性价比的网络设备与服务器；对于精确的网络性能分析与预测；对 于拥塞管理与流量均衡提高服务质量等都具有非常重要的意义流量模型的建立是 现代网络管理系统中一个重要的组成部分，它可以使管理人员掌握网络的特性，合 理调配网络资源，实现网络的高效管理网络流量模型化的核心是提取网络流量中 关键随机属性虽然对计算机网络流量特性、流量建模以及排队性能等方面的研究 已经开展了十多年，但是在网络流量模型上仍然没有取得一致的结论。没有一种网 络流量模型能像泊松模型在电信网络中那样，在口网络研究领域中得到广泛的承认 和应用。 本文的研究旨在引入半马尔柯夫过程描述网络流量特性，试图提出个既精确 描述网络流量特征，又计算简便的网络流量模型，使得我们能更好地理解网络流量 行为，能更准确地预测网络流量，能更有效地管理、配置网络资源本文创新性工 作如下： 1 提出了一个网络流量半马尔柯夫模型该模型根据m 网络流量组成及不同时期 的特性将网络流量划分为西个状态：忙、闲、上升和下降通过状态划分将系 统关键随机特性分离，使其更加突出，从而易于提取对不同状态下流量特征 的研究和不同状态之间转换规律的研究构成了一个完整的描述网络流量的半 马尔柯夫模型根据各状态下传输协议对流量特性的影响，特别是对于流速率 变化的影响，我们提出了以下假设：忙状态下网络流速率服从几何布朗运动； 空闲状态下网络流速率服从正态分布；上升和下降状态下网络流速率服从指数 分布我们利用国际通用的流量数据进行验证，并由此探索揭示提取模型参数 值的方法及模型参数的物理意义实验结果表明，9 5 n 以上的流量数据在其所 对应的状态下具有我们所假设的各状态下的流量特性。 2 应用此模型计算一个重要的网络性能指标一网络利用率我们采用网络当前 负载量与最大理论负载量之比来计算网络利用率，给出了基于网络流量半马尔 柯夫模型的网络利用率计算公式基于三组国际通用的流量数据的分析和验证 结果表明，计算值与实际统计值之间的相对误差小于5 ，说明了网络流量半马 s i 一 网络流量的半马尔柯夫模型： a b s t r a c t 尔柯夫模型描述网络流量特性的能力 3 流量预测广泛应用于网络应用、网络管理当中，对于网络性能分析、网络管理 和控制均具有重要意义为了检验网络流量半马尔柯夫模型的应用性，同时也 可从另一角度验证此模型的正确性，我们应用该模型进行流量预测基于网络 流量半马尔柯夫模型的流量预测算法将重点放置于预测某时刻可能的流量峰 值，而不是预测某时刻精确的流量值基于此思想，我们推导了基于网络流量 半马尔柯夫模型的流量峰值预测公式，并通过实验对预测性能进行了检验预 测1 秒和3 分钟后的流量，预测精度达到8 0 。短期预测可达9 5 ，表明我们的 预测方法同时适用于长期和短期预测偏离度的实验结果表明大部分的预测上 界值与实际流量值之间的误差较小，特别对于主干网数据而言，其误差低于 1 5 。 这个工作难度很大现在的工作只能说是个开始，许多工作仍有待进行， 尤其是关于网络流量半马尔柯夫模型的实际应用的研究工作还有待进一步深入 但不管如何，流量模型作为网络领域的基础研究，对予了解网络行为、网络设计 规划以及提高网络性能等具有非常重大的意义，具有良好的前景 j关键词：半马尔柯夫过程；几何布朗运动；流量模型；流量预测； 产 2 4 l l - as e m b m a r k o vm o d e lf o rn e t w o r kt r a f f i c h u a n gx i a o l u ( c o m p u t e r a r c h i t e c t u r e ) d i r e c t e db ym i ny i n g h u a a sab a s i cr e s e a r c hi nn e t w o r k i n ga r e a , t r a f f i cm o d e l i n gi sf u n d a m e n t a lf o rn e t w o r k p e r f o r m a n c ea n a l y s i sa n dp l a n n i n g af i n et r a f f i cm o d e li sv e r yi m p o r t a n tt op l a n h i g h - p e r f o r m a n c ep r o t o c o t , t od e s i g na l le f f i c i e n tt o p o l o g y , t op r o v i d eh i g l lq u a l i t yo f s e r v i c ew i t hh i g hr a t i oo f p e r f o r m a n c ea n dc o s t , t oa c c u r a t e l ya n a l y s i sp e r f o r m a n c ea n d p r e d i c tf r a n c , a n dt oc o n t r o lc o n g e s t i 伽a n ds m o o t hl r a t 五c t r a f f i cm o d e l i n gi sa l s oa n i m p o r t a n tc o m p o n e n to f t h em o d e m n e t w o r km a n a g e m e n ts y s t e m , w h i c hc a r lm a k el 塔 u n d e r s t a n dn e t w o r kc h a r a c t e r i s t i c s , a c c o m m o d a t en e t w o r kr e s o u r c er a t i o n a l l ya n dr e a l i z e e f f i c i e n tn c t w o d 【m a n a g e m e n t 1 l 璩c o r eo ft r a f f i cm o d e l i n gi sg e t t i n gk e ys t o c h a s t i c p r o p e r t yi nn e t w o r kt r a f f i c a l t h o u g hc o m p u t e rn e t w o r kt r a 街cm o d e l i n ga n dq u e u e p e r f o m a n c eh a v eb e e ns t u d i e df o rm o l x ：t h a nt e ny e a r s , i th a sn o tg o tac o n s i s t e n t c o n c l u s i o ni nn c t 、o r kt r a f f i cm o d e l i n g n o n eo f w a f f i cm o d e l sc a r lb ew i d e l ya p p r o v e d a n da p p l i e d i n i p n e t w o r k i n g a r e a , j u s t l i k e p o i s s o n m o d e l i n t e l e c o m m u n i c a t i o n s d o e s 皿et h e s i sp r e s e n t san e wt r a f f i cm o d e lb a s e do ns e m i - m a r k o vp r o c e s st od e s c r i b e n e t w o r kt r a f f i cc h a r a c t e r i s t i c s , a n dc a t c hi a f f i cp r o p e r t ya c c u r a t e l y i ti sa l s ot r a c t a b l e i nc o m p u t i n g b a s e d0 1 1t h em o d e l , w ec o u l du n d e r s t a n dt r a f f i cb e h a v i o rb 她p r e d i c t u a 伍cm o r aa c c u r a t e l y , m a n a g ea n da l l o c a t en e t w o r kn 渤u 1 1 m o l ee f f e c t i v e l y i n n o v a t i o n so f t h et h e s i sa r ea sf o l l o w s 1 as e m i - m a r k o vm o d e lf o rn e t w o r kt r a f f i ci s p r e s e n t e d a c c o r d i n gt o t r i o c o m p o n e n t sa n dc h a r a c t e r i s t i c s i nd i f f e r e n ts t a g e s , t h em o d e ld i v i d e sn e t w o r kn 棚c i n t of o u rs t a t e s ：b u 跣i d l e ，r i s i n ga n df a l l i n g , t h r o u g hs e t t i n gb u s ya n di d l et h r e s h o l d s t on e t w o r kt r a f f i c i ns u c hw a y , k e ys t o c h a s t i cp r o p e r t i e sa r cm o r ed i s t i n c t i v ea n d e a s i e rt ob ei n d u c e d 伽cc h a r a c t e r i s t i c si nd i f f e r e n ts t a t e sa n dr e l a 廿o a s h i p s b c t w e g ns t a t e sa ee x p l o r e dt od e s c r i b et h en e t w o r kt r a f f i cs e m i - m a r k o vm o d e l c o m p l e t e l y a c c o r d i n gt ot h ei n f l u e n c eo fp r o t o c o lo n 锄ci n e a c hs t a l e 9 e s p e c i a l l y0 1 1 c h a n g eo ft r a f f i cr a t e ，t h ef o l l o w i n gi sa s s u m e d ：t h ea v e r a g et r a f f i c t r a n s m i s s i o nr a t eu n d e rab u s ys t a t ef o l l o w sg e o m e t r i cb r o w nm o t i o n , t h a tu n d e ra n i d i es t a t ei tf o l l o w san o r m a ld i s t r i b u t i o n , a n dt h a tu n d e rr i s i n go rf a l l i n gs t a t e si t f o l l o w se x p o n e n t i a ld i s t r i b u t i o n sr e s p e c t i v e l y t ov e e r ya b o v ea s s u m p t i o n sa n dt o d e d u c em e t h o d so f e s t i m a t i n gp a r a m e t e r so f t h em o d e la n dt h e i rp h y s i c a lm e a n i n g s , s o f t i e i n t e r n a t i o n a lg e n e r a ld a t aa r e 醐a l y z e d t h es t a t i s t i c a la n a l y s i ss h o w st h a t a b o v e9 5 伽cd a t ah a s t h ec h a x a c t e r i s t i ct h a th y p o t h e s i z e du n d e ri t s c o r r e s p o n d i n gs t a t e , a n dt h eh y p o t h e s e s a r ca c c e p t a b l e 2 av e r yi m p o r t a n tn e t w o r kp e r f o r m a n c ec r i t e r i o n , n e t w o r ku t i l i z a t i o n , sc o m p u t e d v f1；l ， c 一 图目录 图4 。l 网络流量半马尔柯夫模型示意图3 i 图4 2b e l l 流量数据已知后继状态为下降状态条件下忙状态保持时间分布5 0 图4 3i _ k 流量数据已知后继状态为下降状态条件下忙状态保持时间分布5 0 表4 1 参数小结 表目录 表4 2 关于忙状态下流速率的假设检验 表4 3 关于闲状态下流速率的假设检验 表4 4 关于下降状态下流速率服从指数分布假设检验结果 表4 5 关于上升状态下流速率服从指数分布假设检验结果 表4 6 状态极限概率 表4 7 模型参数总结 表5 1 网络利用率5 9 表6 1 基于网络流量半马尔柯夫模型的流量上界预测结果 钙 钉 耜 的 的 h 观 第一章引言 1 1 流量模型研究的重要意义 泊松模型精确地描述了电话网络中的电话呼叫到达行为，其良好的解析性质极 大地简化了排队分析过程。基于泊松模型，人们可预测电话呼叫到达行为；可分析 电话网络和电信设备性能；可根据用户需求设计相应的电信设备 f m 9 4 g m 9 9 1 。 泊松模型创始了公有事业中的数学方法，在电信系统中得到了广泛的应用，对电信 系统的推广和发展有着重要的作用所有这些基于泊松过程的流量模型成功地描述 了电信网络中的流量行为，由此可见流量模型的重要性 流量模型是网络性能分析和通信网络规划设计的基础，精确的流量模型对设计 高性能网络协议、高效网络拓扑结构、业务量预测与网络规划、高性价比的网络设 备与服务器、精确的网络性能分析与预测，拥塞管理与流量均衡都有重要意义流 量模型的建立是现代网络管理系统重要的组成部分，它可以使管理人员掌握网络的 特性，合理调配资源，实现网络的高效管理。具体体现为以下几个层次上的意义： 1 ) 业务量特性的研究与认识； 2 ) 特殊业务量的特性研究与认识； 3 ) 端端业务特性； 4 ) 业务特性对核心设备系统参数设计的影响； 5 ) 对网络测量的辅助作用； 6 ) 对路由的影响研究； 7 ) 对端端网络行为特性的影响研究； 8 ) 对全网的影响研究 网络流量模型化的核心是提取网络流量中关键随机属性虽然泊松模型在电信 网络中取得了极大的成功。但它是否适用口网络，仍有争议征 f 9 5 】b 引入了相关性 c i n h r 7 5 1 由于翻。) 中的非0 的自相关性，它们可潜在地抓住流量 的突发特性考查一个具有离散状态空间连续时间的马尔柯夫过程 m = ( 膨( f ) ) 二，m 具有以下性质：在状态f 的保持时间仅依赖于状态f ；服从参 数为jf 的指数分布；以概率胁从状态i 跳转至状态且矩阵严d 啊是一个概率矩 阵【c t n l a r 7 5 。在一个简单的马尔柯夫流量模型中，马尔柯夫过程中的每一跳解 释为信号( 包) 的一个到达，如此到达的间隔时间服从指数分布，且其速率参数 只依赖于发生跳转的状态，这是由马尔柯夫性所决定的 离散时间的马尔柯夫过程将时间按时间片( s l o t ) 进行划分，可由具有一个 8 第二章流量模型研究介绍 马尔柯夫转移矩阵尸t 】的过程口。 定义这里，状态卜一般对应连续到达之间 间隔的f 个空闲时间片，则助为在给定之前间隔了f 个时间片的条件下下一个间 隔是_ ，个时间片的概率所谓到达则有可能是一个单个的包( 或信元) 、一批包 或一个连续量到达过程自身也可由一个马尔柯夫链进行描述。反之连续状态、 离散时间的马尔柯夫过程可模型化同步到达系统的负载不论哪种情形，马尔柯 夫模型引入了到达之间闻隔、批大小和后继负载之问的相关性 此后，又产生了马尔柯夫更新模型，其一般是离散状态的马尔柯夫过程，仍 然保留了简单性和易于解析分析的优点 f m 9 4 1 一个马尔柯夫更新过程 r = ( 厶，毛) ) 二由一个马尔柯夫链( 坛 和与其相关的跳转时间编) 所定义，使其 服从以下约束：下一个状态( “l ，如+ 1 ) 对和跳转问的间隔时问只依赖于当前 状态 磊，但不依赖于以前的状态和以前的跳转间隔时间如果我们将( 们的跳 转( 迁移) 解释为包或信元的到达，我们则为包或信元的到达过程引入了相关性 与马尔柯夫过程不同的是，马尔柯夫更新过程的到达间隔时间可以为任意分布， 且这些分布依赖于跨越每个相继到达间隔两头的状态 马尔柯夫调制模型 f m 9 4 在流量模型中是一类极为重要的流量模型。其思想 是引入一个明确的概念来表述一个业务流：即一个辅助的马尔柯夫过程和其当前 状态控制流量机制的概率法则设m = ( m ( f ) ) 乙是一个连续时间马尔柯夫过程， 具有状态空间 l ，2 ，m ( 状态空问也有可能更为复杂) 现在假设当肘处 于状态k 时，流量到达的概率法则完全依赖于k ，这对于每一个k ，l t 所都 成立当m 经历了一个转变，即由状态k 迁移至状态 则一个新的完全依赖于 _ ，的到达概率规则开始起作用，如此等等。因此，到达的概率法则被m 中的状态 调制( 这样的系统也称为双重随机，但是术语“马尔柯夫调制”似乎更好一点， 因为它首先说明流量是随机的，其次服从于 厶 马尔柯夫调制过程当然比一个 连续时问、离散状态的马尔柯夫过程更为复杂( 保持时间不需要严格约束为指数 分布随机变量) ，因而具有复杂的解析性 最经常使用的马尔柯夫调制模型是马尔柯夫调制泊松过程( m p p ) 模型 m m m c m 0 3 ，它结合了调制( 马尔柯夫) 过程与被调制( 泊松) 过程各自的简 单性。在这种情形中，调制机制简单地规定处于膨中的状态七时，到达服从以 速率九的泊松过程随着状态的改变，速率也随之改变m m p p 模型可有多种 9 中国科学院博士学位论文一网络流量的半马尔柯夫模型 使用方式例如模型化一个具有可变速率的单个业务流一个简单的马尔柯夫调 制泊松流量模型可将流速率量化为一组有限的速率等级，每个速率等级对应于马 尔柯夫调制过程的一个状态可以验证，速率等级的保持时间服从指数分布是一 个恰当的描述其中m 的马尔柯夫转移矩阵q = 【q 胡可很容易地从经验数据中 估计，即对经验数据进行简单地量化，统计从状态k 至状态_ ，在所有状态转变中 所占比例来估计q b 这样的一个两状态m m p p 模型广泛应用于模型化音频流 h l 7 4 。其中一个状态是“o n ”，具有一个与之相关的服从泊松分布的流速率； 另一个状态是“o f f ，其流速率为0 ( 这样的模型也被称为中断泊松) 显然“o n ” 状态对应于一次持续的讲话( 当讲话者发出声音时) ，。o a 一状态则对应于一个 沉默( 当讲话者停顿时) 这个基本的m m p p 模型能扩展至独立业务流的聚合 每一个业务流都用m m p p 模型化，由一个以上描述的单独的马尔柯夫过程肠 调制令j ( t ) = j l 以以( f ) ，j 妁) ，其中聃是第f 类业务流的活动源个数，且让 坝沪m ( f ) ， 磊( 回，以力) 是对应的向量值的马尔柯夫过程，每个分量均取非负 整数。在状态u l ，五，五) 中般力的第f 类业务流的至0 达速率是m 。 以上的马尔柯夫调制过程，其调制的是一个状态变化一下状态调制，转变 为对状态转换的调制，这就产生了转换调制过程。一个状态转移能简单地用一对 状态描述，即用转移前的状态和转移后的状态组成让m = m ( f ) 二是一个在正 整数状态空间上的离散时间的马尔柯夫过程令状态转移在时间片边缘上发生， 且由一个m x m 的马尔柯夫转移矩阵q t 【岛】控制让岛表示在时间片f i 中包或 信元的到达数，并且假设概率户( 马i 女lm - - i 西州可 = 幻 与任何过去的状态信 息无关( 假设参数已给定) 由此( ， “i ) 表示在时间片刀中从状态 厶 转移至状态坛+ j 。此外，流量在时间片甩中包或信元到达的个数完全由调制链 的转移所决定( 即由参数以妨决定) 。由此可以看出，马尔柯夫调制流量模型是 马尔柯夫转移调制的一个特殊情形，即简单地当条件事件是 磊尸o 时，此时 “驴“p ，时间片疗的调制链仅依赖于状态f ，而与下一个时间片，什l 中的状态 _ ，无关相反，马尔柯夫转移调制过程也可看作是马尔柯夫调制模型，只不过具 有更大的状态空间确实，如果 j l 劬是马尔柯夫的，则其转移过程 ( 磊 缸1 ) 也一定是马尔柯夫的同样，利用多个转移调制流量模型就能对每个感兴趣的业 务流类型进行定义。而一个完整的流量模型则由单个流的流量模型的叠加组成 1 0 第二章流量模型研究介绍 t s h 9 4 马尔柯夫流量模型作为早期的网络流量模型，对于推动网络的进步和发展起 到了重要的作用但是，马尔柯夫模型关于状态保持时间是指数分布的假设使其 在应用上有着巨大的局限性另一方面，马尔柯夫模型，特别是马尔柯夫调制模 型，通常具有相当多的状态个数每增加一个状态，马尔柯夫流量模型的参数就 要增加近一倍因此随着状态个数的增长，马尔柯夫模型的复杂度也迅速增长。 从而影响了模型的解析性和应用性 2 3 自相似网络流量模型 w i l le l c l a n d 和j b e r a n 等人于上世纪九十年代提出了自相似网络流量模型 l t w w 9 4 b e r a n 9 4 】他们分别通过对于以太网中大量包流量数据的观测分析 以及对由v b r 视频服务产生的帧数据分析，发现由i p 包组成的流量呈现出自相 似的统计特性。此现象产生了关于宽带网络的模型化、设计和控制研究的一个重 要分支自相似( 或分形) 现象指的是在所有的时间尺度上( 至少在一个很宽的 范围内) 结构呈现相似的图形或趋势。对于口包组成的流量，已证明从几毫秒 到分钟再到小时之间的每一个时间尺度，流量突发具有明显的相似性，即在辟 包流量具有自相似性主要的自相似随机模型有分形高斯噪声 m n 6 8 和分形 a r i m a 过程 6 j 8 0 两大类有多种方式可验证样本的自相似特性，如：依据在 原点发散的光谱密度，依据自回归函数的不可求和的特性( 体现了样本的长相关 性) ，或可依据样本均值方差( 是关于样本大小疗的函数) 的衰减慢于l n 的特 性 c o x 8 4 特征化这些现象的关键参数称为赫斯特参数一阢用于检测给定的实 际流量数据的自相似程度p - x u , 蚶o 。令饵 ：是一个实际的时间序列，且其具有 样本均值珩o 和样本方差s 2 ( n ) 。一个r s 统计量由r ( n ) s ( n ) 给出： r ( n ) = m a x ：l ( 一玖功) ：l 七s 打 - m m ：。( e 一玖坳：l s 七茎打) s o ) 5 击e 一m ) ) 2 从经验上说，许多自然产生的时f 可序列均遵循这个关系：对于较大的疗有 研五( ) ，s ( h ) 】兰1 8 ， ( 2 5 ) 典型的日取值大约为o 7 3 另一方面，对于更新和马尔柯夫序列，可证明 中国科学院博士学位论文网络流量的半马尔柯夫模型 对于较大的n ，( 2 5 ) 式在h = o 5 时成立叶i n 6 8 1 。这种差异或矛盾通常被称为赫 斯特现象，是时问序列的自相似程度的一个测度，可从实际流量数据中估计从 数学的观点来看，自相似流量在以下几方面有别于其他流量模型 c o x 8 4 。让j 表示某时间尺度下的一个时问单位，如f 1 0 辨秒( m - - 0 , l ，2 ，) 对于每 一个时间尺度j ，令x “ = z ? ，表示根据业务流计算的每j 个时间单位内的个 体( 包，字节、信元等) 个数组成的时间序列。传统的流量模型具有下面的属性： 即随着j 的增长，聚合过程从曲逐渐成为一个l i d 随机变量序列( 协方差平稳 白噪声) 。另一方面，在画关于时间的流量图时，对应的实际流量数据的聚合过 程产生揭示了两种相关的行为类型的时间序列从亩这两种行为类型从视觉上 很难相互区分( 严格自相似) ，但是在纯噪声上却可以将= 者很明显地区分；或 者他们聚合于一个具有非退化自相关结构的时间序列( 渐近自相似 相反依据 传统流量模型进行的仿真，其白噪声在时间尺度增长2 至3 个数量级之后迅速收 敛同样，当尝试用自相似流量数据来拟合传统流量模型时，随着采样数的增加， 所需要的参数个数迅速增加相反，自相似流量模型能以一个极其节俭的方式( 大 约l 至4 个参数) 抓住i p 包流量的所观测到的分形特性参数估计方法对于大 多数自相似模型均适用，m o n t ec a r l o 方法也同样适用于产生较长综合的自相似 流量 b s t w 9 5 】 如今，i p 网络流量的自相似特性已得到了大家的广泛认可，在其基础之上 又提出了长相关o o n g - r a n g ed e p e n d e n c e ，l r d ) 、重尾分布( h e a v y - t a i l e d ) 、分形 ( f r a c t i o n ) 及多重分形( m u l t i - f r a c t i o n ) 等概念的流量模型 c b 9 7 s t 9 9 田s t w 9 5 】 【w v s 9 8 1 但令人遗憾的是，经过十多年的研究，基于自相似特性的应用却并不 多见自相似流量模型参数估计时的复杂计算，性能分析时的繁琐等等使得其只 能成为理论研究园地远处的一道亮丽风景，而无法真正融入整个网络架构体系当 中，成为指导网络基础建设和管理的好帮手 2 4 ( t r , p ) 流量模型 r e n el c r u z 于1 9 9 1 年提出了( 口。，) 流量模型 c r u z 9 1 a 1 c r u z 9 m 。此 模型不同于以前用随机过程描述的流量模型它假设流量是。未知的”。但满足 某些规则性限制。然后主要研究具有这些流量限制特性的网络性能。模型中考虑 第二章流量模型研究介绍 的限制首先是影响流量突发性的设定，称为。突发限制”( 口，p ) 模型的分析 则由一系列与流量相关的在网络中不同点上所满足的突发限制组成突发限制定 义以下：假设包的最大长度为工比特，一个业务流由一组具有可变长度的包组成 若给定某通信链路上的一个业务流，则可用一个非负函数r 表示此业务流：对于 任意两个时刻x 和弘且) ，x ，r 在区间i x , ，】上的积分表示该业务流在时间b ，y 】 内在链路上传输的数据量因此，r 表示此业务流在时刻t 的瞬时流速率如 果l o 且r 是给定链路上某一业务流的流速率函数，假设r ( f ) 仅取两个值：0 和 链路传输速率，即c 比特，秒( 链路带宽) 。换句话说，链路或空闲或满负荷传输 给定庀o 且p 卸，r 瓴p ) 当且仅当对于所有满足必的x 和y 有 rr 蔓口+ 础- x )( 2 1 ) 式( 2 1 ) 就是( 口，p ) 模型对流量所定义的突发性限制。因此如果r 力， 则说明对于任何时间段h 力内流过的流量总量总是存在一个上界。此上界即等 于常数盯加上正比于时间段长度的某个值如果对于业务流而言存在一个平均流 速率，即为( 2 1 ) 式中的p 对于一个固定的p 值，盯表示该业务流所允许的突 发能力；a 越大则潜在的突发能力越大 对于流量的突发性限制，还有一个更有意思的解释对任意函数r 和常数 p o ，可定义函数 ( r ) o ) 2 m a x 【j ：r p ( f s ) l ， 一 f c o ( 2 2 ) 很明显当且仅当r 以p ) 时，对于所有的t 有矿肛耋盯成立此时的 呒似) o ) 表示一个以速率函数r 接收数据，以速率p 传输数据的恒定工作系统在 时刻t 的积压量( 即未完成的工作量) 可通过呢( r ) ( f ) 这种形式表示在进行精 确分析时难处理的包服务过程因为包进入一给定结点的传输延时与包进入该结 点的到达过程相关；此外，不同结点的流量到达过程经常相互影响，使得进行相 关性能分析时会比较难处理呒僻) 可很好地对其进行描述。 如果包大小就是工比特，且如果蚴 o ，c ，则对于某个t 可能存在 f + “。r ：因此如果r 细，则盯必须满足下面的条件： o 丛u - p c ) ( 2 3 ) 1 3 中国科学院博士学位论文网络流量的半马尔柯夫模型 如此可考虑比( 2 1 ) 式更一般的流量限制特别地，如果b 是在非负实数 上所定义的任意函数，则对于所有的y z 。r 是一个满足下式的非负函数 r r 6 ( ) 一力 ( 2 4 ) 记为r 6 一般假设任一这样的限制函数b 是非递减的如此，就用一个上 界函数对流量进行了约束通过这个流量上界函数可以更加灵活地对包到达过程 进行描述，来方便分析网络性能 ( 口，p ) 模型的一个最大好处是能够简单有效地实现对网络性能上界的精 确分析由于网络流量的复杂性，使得能精确描述网络流量特性的随机模型很难 用一个简单的形式表达另一方面也造成了网络流量模型的精确性与高解析性无 法共存的一个局面基于自相似的流量模型不能得到广泛应用的一个最主要的原 因即是其解析上的复杂性，无法基于自相似模型实现对网络性能的高效分析。尤 其是精确的分析而( 一，p ) 模型干脆抛开了对网络流量具体特征的考虑，直接 用一些规律性的限制来约束网络流量：即平均流速率p 和突发限制口( 或直接通 过一个流量上界函数6 实现的流量的限制) 通过这种方式，( 口，p ) 模型将通信 网络模型化为一组无错的点到点通信链路链接的队列网络，在此基础上分析固定 路由策略下以包模式运行的包括了网络延时，缓冲需求及吞吐量等重要网络性能 指标的精确分析 该模型存在一个问题，即分析结果过于保守这是因为其有一基本认定：即 如果进入网络的流量不是太突发，则在网络中流动的流量也不会太突发可是当 前i p 网络的主要特征和造成当前网络流量研究难点的主要原因就是i p 网络流量 的突发性因此( 盯，p ) 模型虽然具有非常良好的解析性质，且在实时通信中有 着广泛的应用前景，但是随着网络规模的增大( 即其模型中流量所经过的网络元 索个数的增加) 其结果的误差也越来越大而达到不可用的地步而且( 口，p ) 模 型试图只用两个参数描述网络流量，必然会放弃某些流量的关键属性，影响性能 分析的准确性。当网络规模较小时，尤其是流量传输的跳数较少时，基于( o ，p ) 模型的性能分析可大大帮助我们对网络进行规划和管理；但当网络规模较大时。 尤其是流量传输的跳数增多时，基于( ，p ) 模型的性能分析将有可能大大低估 网络的能力，而造成带宽和资源的浪费 1 4 第二章流量模型研究介绍 2 5 本章小结 早期的网络流量模型是直接借鉴传统p s t n 中的泊松模型发展起来的；很快 研究者们便发现了i n t e m e t 流量与电话流量特性的重大区别于是一方面人们开 始对传统的泊松模型进行改进，如定义与时间相关的泊松过程；另一方面也开始 寻找其他的适用于i p 网络流量特性的流量模型，于是泊松模型的近亲一马尔柯 夫模型被引入网络流量模型中，提出了大量的基于马尔柯夫的流量模型。在上世 纪九十年代i p 网络流量的自相似特性得到了大家的公认，以此为分水岭，掀起 了新的一轮网络流量模型研究热潮。虽然已经过了1 0 多年对流量特性、流量建 模以及排队性能的研究，但是在网络流量特性的研究方面，仍然没有取得一致的 结论，仍没有一种网络流量模型能像泊松模型在电信网络中那样，在网络流量模 型研究领域中得到广泛的承认和应用泊松模型并不适用于m 网络，马尔柯夫 模型的马尔柯夫性使其带有天生的缺陷，而自相似模型的复杂性使其得不到广泛 应用口网络流量自身的特点也为网络流量模型的研究工作带来了很多困难 因此，建立一个既能准确描述网络流量特性，又具有计算简单、应用便捷的网络 流量模型仍是我们需努力的目标 第三章随机过程基础知识 网络流量研究是为了从网络流量中提取关键的随机特性，为我们更好地理解 网络流量行为，管理和维护网络正常运营提供有效的研究手段。网络流量建模即 根据网络流量的关键随机特性，使其能用数学方法进行描述或预测本章简要介 绍在本文中将用到的随机过程概念和相关基础知识f 所有相关知识请参见文献 【s m 9 7 马o o l 】晰吴7 9 】) 本章组织如下；首先介绍半马尔柯夫过程的基础：马尔柯夫链；然后介绍一 些与半马尔柯夫过程相关的随机过程基础知识；在第三节详细介绍随机过程：半 马尔柯夫过程；最后小结本章 3 1 马尔柯夫链 马尔柯夫链是随机过程中非常重要的一类随机序列在半马尔柯夫过程的定义 和应用当中均使用了马尔柯夫链的某些概念和性质 定义3 1 马尔柯夫链设随机序列 坝破n = o , l 2 ) 的离散状态空间为若 对于任意m 个非负整数i t 1 ，n 2 ，“0 埔( 啦 0 ，则称从状态i 可到达状态_ ，两个相互可到达的状 态f 与，称为相通的，记作f 付，称相通的两个状态属于犀一个类若任意两个 类要不不相交要不就相同，没有相交的情况，则称此过程彳是格点自吼马尔柯夫 链是不可约的。 3 2 5 交错更新理论 考虑一个系统，它有两个状态，开或关最初它是开的且持续开的时间是z 1 ； 而后关闭且持续关闭的时间为y l ；之后，经过时间z 2 又打开；经过时间玛又关 闭，；如此等等。假设随机交量( 乙l 强行l ，独立同分布即随机变量序列( z ， 与 晶) 都是独立同分布的；但允许磊与晶是相依的换言之，每当过程打开时， 切就重新开始，但当它关闭时，允许关闭的时间依赖于前一段打开的时问 设日是厶的分布，g 是矗的分布，而f 是磊+ k ，l ，的分布又令 只伊- p 时刻t 系统开着 定理3 3 若鼢跏 一，x f 是非格点的，则 l i m 聃= 器 3 2 - 6 强大数定律 设以是事件a 在n 次独立随机试验中的出现次数，在每次试验中事件a 出 现的概率是p ，则 3 - 2 7 正态分布 设随机变量x 的概率密度为 l i m 丝：p h - 刀 ! 兰! 1 删2 丽。”2 一 x 佃 中国科学院博士学位论文惆络流量的半马尔柯夫模型 其中一0 0 o 为常数，则称；j 服从参数为 的指数分布其均值为1 3 2 9 几何布朗运动 几何布朗运动在微观经济当中得到广泛应用如股权涨落就服从几何布朗运 动几何布朗运动通过随机差分方程d s = ，芷油+ a 蹦形定义其中口和口是常数 通常，f 表示偏移的百分比例如。口- - - - 0 1 表示在不存在随机性影响的情况下。 股票价格在年内将上涨1 0 而口表示看作抖动的百分比如果e = 0 3 则表 示一年间的股票价格抖动范围在现在股票价格的3 0 以内 方程d s = ，黜+ 删表明，在非常短的一段时间a t 内的股票价格变化可 近似为s = # s a t + o s a w 其中4 表示在时间4 ，内标准布朗运动的变化量 4 f 越小，等式近似越精确。此方程存在一个解，即最= p 姐一1 2 ) t - s y ”w t s 根据 正态分布的性质，从上解可看出l n ( s t s , ) 是具有均值- - o r 2 2 ) ( t s ) 和方差 口2 ( f 一曲的正态分布。 3 3 半马尔柯夫过程 一个半马尔柯夫过程是一个随机过程，其状态变化遵循一个马尔柯夫链，而 状态变化的时间间隔是随机变量更确切地说， 定义3 2 半马尔柯夫过程；考虑一个具有状态空间s = o l ， 的随机过程， 满足以下条件：每当它在f o 时进入状态 o ) 下一个进入的状态是_ ，的概率为p c , 搿o 。 ( i i )在下一个进入的状态是，的条件下，从最近一次进入状态i 到发生从i 到f 第三章随机过程基础知识 转移为止的时间有分布r 。 若以z 记时刻t 的状态，则f 2 吼f 0 ) 称为半马尔柯夫过程。 以冠记半马柯夫过程在转移之前处于状态，的时间的分布，对下一个可能的 状态求和，可见日( f ) = 弓( f ) ，以h 记其均值，即以= f 尉峨o ) ， 定义3 3 内嵌式马尔柯夫链： 若 z 娃f 0 ) 是个半马尔柯夫过程，以蜀记第栉个到达的状态，则 o ) 是一个转移概率为岛的马尔柯夫链，它称为半马尔柯夫过程的嵌入马尔柯夫 链。若嵌入马尔柯夫链是不可约的，则称此半马尔柯夫过程是不可约的。 以死记相继进入状态f 之间的间隔时间，且令j # = 研瓦】运用交错更新过 程理论，可导出半马尔柯夫过程的极限概率的表达式。 定理3 4 若半马尔柯夫过程是不可约的，且瓦具有非格点的分布与有限的均 值，则 只；i i m p z ( t ) = i i z ( o ) = ) 存在且与初始状态无关更进一步，只：丝 p o 说明：每当过程进入状态f 就说一个循环开始，且当过程进入状态f 时就说 过程是。开的”，不在状态f 时则它是。关的”于是我们有了一个交错更新过程， 它开着的时间有分布局，而它的循环时间为死。 虽然定理3 4 给出了极限概率的表达式，但它并不是一个实际计算只的方法。 下面给出极限概率的实际计算公式为要计算乃，假设嵌入马尔柯夫链( 蜀，疗o ) 不可约、正常返( 各状态在有限时问内可重新回到起始状态) ，又设它的平稳分布 是万。j 0 即 芹，= 疗弓 乃= l j - o 有唯一解，且乃可解释为等于- 的蜀所占的比率若马尔柯夫链是非周期的，则 2 1 中国科学院博士学位论文一网络流量的半马尔柯夫模型 x j e 等t - 舰p 以= d 既然乃等于进入状态，的转移的比率，而一是每一次 转移到，后处于状态，的平均时问，所以直观地看来，极限概率应与乃，成比例 现在我们证明这一点 定理3 5 若半马尔柯夫过程是不可约的，且死具有非格点的分布与有限的均 值，且嵌入马尔柯夫链打o 是正常返的，则 只2 麸 证明：定义记号如下： e c ，) = 第，次到达状态i 后在状态f 逗留的时间，i , j o 。 沏) = 在半马尔柯夫过程的前m 次转移中到达状态f 的次数 利用上述记号可见，在前肼次转移中处于状态i 的时间的比率( 记为，) 如下： 只。= j i 广 “z ( 3 2 ) ( 埘) r u ) 。 ：竺鱼丝塑! 争丝盟擎鱼垃 由于埘一c o 时，j ( m ) 寸o o ，从强大数定律推得 篙焉一“智川( 朋) “ 由更新过程的强极限律得 ! 丛堕一( 研两次到达晓间的转移次数】) 。：万 m 因此，在( 3 2 ) 中令卅 - - - hm 证明了 一l i r a p - 2 羲 证毕 第三章随机过程基础知识 从以上定理得出，极限概率只依赖于转移概率乃与平均时间肛，0 确定半马尔柯夫过程的极限分布的问题并未因为求出了n 而完全解决。例如， 我们可能想求在时刻t 处于状态，下一次转移在时刻m 之前转移到状态_ ，的概 率在t _ 时的极限为了表示这个概率，令 h 沪从t 到下一次转移的时问 辨之后首次转移进入的状态 则此概率为： l i m p z ( t ) = 】，( f ) 而s o ) = f