（计算机科学与技术专业论文）自相似网络的可靠性建模与分析.pdf

国防科学技术大学研究生院学位论文 摘要 测量和研究都发现计算机网络的流量呈现出自相似性( 网络的自相似性) ， 该特性对于网络性能分析和网络设计有着重要作用。网络的可靠性是网络设计和 分析必须考虑的重要因素之一，对自相似网络的可靠性进行分析是网络分析的研 究热点之一本文针对自相似网络可靠性开展研究，基于流量模型，提出了网络 业务性能分析模型，同时基于业务性能提出了网络可靠性模型，并进行了分析和 模拟验证。 首先简要介绍了网络可靠性的研究现状，选取网络的有效性作为衡量可靠性 的性能指标。在分析目前常用的用来描述网络流量过程的自相似流量模型的基础 上，选取o n o f f 模型作为流量分析模型，即使用大量o n o f f 源叠加方法产生 网络流量。 基于0 n ，o f f 模型，将网络节点和到达信息流视为g 删1 b 排队模型。针对 o n o f f 流量源的带宽分配，提出了一种自相似网络有效带宽模型。利用大偏差 理论得到稳态队列长度分布，结合溢出概率得到自相似业务流的有效带宽。针对 信息的排队延迟，提出了一种自相似网络平均排队延迟分析模型。基于稳态队列 长度分布，求均值得到稳态平均队列长度，进而通过l i t t l e 定理得到网络的平均 排队延迟时间。针对信息的丢包情况，提出了一种自相似网络平均丢包率分析模 型。利用队列长度与丢包率之间的关系给出了稳态下丢包率的分布，进而得到平 均丢包率。为验证解析结果的正确性，利用n s 2 模拟器对自相似网络的平均排 队延迟和平均丢包率进行了模拟。 为了分析自相似网络可靠性，结合业务性能对网络可靠性指标进行形式化。 通过平均排队延迟和平均丢包率两个业务性能指标，分别提出了基于平均排队延 迟的可靠性模型和基于平均丢包率的可靠性模型，并分别进行了模型分析。为了 更加全面衡量网络的可靠性，提出并讨论了自相似网络的可靠性矢量模型。 在分析现有网络模拟器不足的基础上，设计并实现了针对自相似网络可靠性 的模拟器s n r s ( s e l f - s i m i l a r n e t w o r k r e l i a b i l i t y s i m u l a t o r ) ，它可以对自相似网络 的平均排队延迟和平均丢包率进行模拟，进而分析可靠性通过模拟发现，理论 分析结果与模拟结果是吻合的，从面验证了所建可靠性模型的正确性。 主题词：自相似网络，网络可靠性，o n o f f 模型，平均排队延迟，平均丢包率， s n r s 模拟器 第1 页 国防科学技术大学研究生院学位论文 a b s t r a c t m e a s u r e m e n t sa n dr e s e a r c ha p p e a rt h a tc o m p u t e rn e t w o r k ss h o wt h es e l f - s i m i l a r t r a f 五cf e a t u r e ( s e l f - s i m i l a rp r o p e r t yo fn e t w o r k ) t h ep r o p e r t yi sv a l u a b l et on 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 dn e t w o r kd e s i g n n e t w o r kr e l i a b i l i t yi so l l eo ft h ei m p o r t a n t f a c t o r so fi t sp e r f o r m a n c ea n a l y s i sa n dd e s i g n r e l i a b i l i t ya n a l y s i sb a s e d0 1 3 s e l f - s i m i l a rn e t w o r ki sb e c o m i n go n eo ft h eh o t s p o to fn e t w o r ka n a l y s i s a n dt h e r e l i a b i l i t yo ft h es e l f - s i m i l a rn e t w o r ki sm a i n l yr e s e a r c h e di nt h i st h e s i s n e t w o r k 蛐c p e r f o r m a n c ea n a l y s i sm o d e l sa p r e s e n t e d0 1 1t h eb a s eo f t r a f f i cm o d e l s b a s e d o nt h e s em o d e l s 。r e l i a b i l i t ym o d e l sa p r e s e n t e df u r t h e l oa n dt h e n , t h ea n a l y s i sa n d s i m u l a t i o nw o r k si sd o n ea b o u tt h e m t h er e l a t e dw o r ko fr e l i a b i l i t yi si n t r o d u c e df i r s t l y a n dt h ea v a i l a b i l i t yi n d e xi s c h o s e nt ob et h em e a s t t r e m c n to fn e t w o r kr e l i a b i l i t y t h ec o r a l l o t ls e l f - s i m i l a ri r a t e m o d e l sw h i e l aa u s e dt od e s c r i b et h et l a f f i cp r o c e s s e sa r ea l s op r e s e n t e d t h e n o n o f fm o d e li m p o s i n go i lm a s so n o f ff l o u r c e $ t og e n e r a t es e l f - s i m i l a r 锄ci s e l a o s e nt ob et h e 自m 伍ci i l o d e l b a s e d0 1 3 o n o f fm o d e l , s y s t e mc o m p o s e do fn e t w o r kn o d ea n d 蚴cw a s v i e w e da sag m 1 bq u e u i n gm o d e l t h ee f f e c t i v eb a n d w i d t hm o d e lo fs e l f - s i m i l a r n e t w o r ki sb u i l tf o rt h eb a n d w i d t hd i s t r i b u t i o no f0 1 w d f fs o u r c 韶t h es t a t i o n a r y q u e u el e n g t hd i s t r i b u t i o nw a sd e r i v e db yl a r g ed e v i a t i o nt h e o r yf i r s t l y t h e nt h e e f f e c t i v eb a n d w i d t hi sd e d u c e db yc o m b i n i n gw i t ho v e r f l o wp r o b a b i l i t y a na v e r a g e q u e u i n gd e l a y ( a q d ) a n a l y s i sm o d e lf o rs e l f - s i m i l a rn e t w o r ki sp r e s e n t e df o rt h e q u e u i n gd e l a y s t a t i o n a r ya v e r a g eq u e u el e n g t hw a sg o tb ys o l v i n gt h ea v e r a g ev a l u e o ft h ed i s t r i b u t i o n t h e nt l l ca v e r a g eq u e u i n gd e l a yt i m ei sd e r i v e db yl i t t l e st h e o r y f u r t h e r m o r e 姐a v e r a g ep a c k e t sl o s sm t e ( a p l r ) m o d e lf o rs e l f - s i m i l a rn e t w o r ki s p r e s e n t e df o rt h en e t w o r kp a c k e t sl o s s s t a t i o n a r yp a c k e t sl o s sr a t ed i s t r i b u t i o ni s d e r i v e da c c o r d i n gt ot h er e l a t i o nb e t w e e nq u e u el e n g t ha n dp a c k e t sl o s sr a t e t h e n a v e r a g ep a c k e t sl o s sr a t em o d e l i sg o tb ys o l v i n gt h e a v e r a g ev a l u eo f p a c k e t sl o s sr a t e t h es i m u l a t i o nw o r kf o ra q pa n da p l ri sc o m p l e t e db yn $ - 2t o 嘶f j ，t h ev a l i d i t y o f t h ea n a l y t i c a lr e s u l t s t h ef o r m u l i z a t i o no ft h en e t w o r kr e l i a b i l i t yi n d e xi sc o m p l e t e db a s e d0 1 1t r a f f i c p e r f o r m a n c 总a c c o r d i n g 钿a q dm o d e la n da p l rm o d e l t w or e l i a b i l i t ym o d e l s b a s e do ns i n g l ev a l v ea r cb u i l tr e s p e c t i v e l y ：r e l i a b i l i t yb a s e d0 1 3 a q da n dr e l i a b i l i t y 第1 i 页 国防科学技术大学研究生院学位论文 b a s e do na p l r a n a l y s i sw o r ka b o u tt h et w om o d d si sa l s od o n es u b s e q u e n t l y t h e n r e l i a b i l i t y v e c t o rm o d e li s i m p l e m e n t e d i no r d e rt om e a s u r er e l i a b u i t ym o r e c o m p r e h e n s i v e l y s e l f - s i m i l a rn e t w o r kr e l i a b i l i t ys i m u l a t o r ( s n r s ) i sd e s i g n e da n di m p l e m e n t e d l a s t l yb a s e do nt h ea n a l y s i st ot h ed i s a d v a n t a g e so f p r e s e n tn e t w o r ks i m u l a t o r s s n r s c o u l db eu s e dt om o d e la q da n da p l ro fs e l f - s i m i l a rn e t w o r k , t h e nt oa n a l y z e r e l i a b i l i t y b ye x p e r i m e n t s ，t h es i m u l a t i o nr e s u l t sa r et a l l yw i t ha n a l y s i sc o n c l u s i o n s ， s ot h ev a l i d i t yo f t h e r e l i a b i l i t ym o d e l sa b o v ei sv e r i f i e d k e yw o r d s ：s e l f - s i m i l a rn e t w o r k ，n e t w o r kr e l i a b i l i t y , o n o f fm o d e l 。a v e r a g e q u e u e i n gd e l a y , a v e r a g ep a c k e t sl o s sr a t e ，s n r ss i m u l a t o r 第页 国防科学技术大学研究生院学位论文 图目录 图2 1 自相似过程与平稳随机过程的比较1 2 图2 2p a r e t o 与指数概率密度函数 图2 3 无穷o n o f f 源叠加产生自相似流量 图3 1 节点和到达业务流 1 9 1 9 2 5 图3 2 在不同溢出概率要求下的有效带宽比较2 9 图3 3 不同流量源数量的有效带宽比较3 0 图3 4 有效带宽与流量源数量关系。 图4 1 不同自相似程度下平均排队延迟比较。 图4 2 不同流量源数量下平均排队延迟比较 图4 3 流量源数量与平均排队延迟关系 3 0 一3 5 图4 4 仿真网络结构国3 6 图4 5n s - 2 仿真不同自相似程度下的平均排队延迟 图4 6 平均排队延迟鳃析结果与模拟结果比较一3 7 图4 。7 不同自相似程度下的平均丢包率比较 图4 8 不同流量源数量下的平均丢包率比较 图4 9n s 2 仿真不同自相似程度下平均丢包率。4 0 图4 1 0 平均丢包率解析结果与模拟结果的比较4 1 图5 2 排队网络结构 图5 3 一个简单的环型网络 图5 4 不同自相似程度下网络可靠性d r 比较 图5 5 不同流量源数量下网络可靠性d r 比较。 图5 6 不同自相似程度下网络可靠性l r 比较。 图5 7 不同流量源数量下网络可靠性l r 比较。 图5 8 可靠性乘积与缓存大小之间关系 图6 1s n r s 总体框图。 图6 2 s n r s 输入界面 图6 3 网络拓扑可视化界面 图6 4 模拟不同自相似程度下d - r e l i a b i l i t y 4 3 图6 5 模拟不同网络规模下d - r e l i a b i l i t y 图6 6 模拟不同自相似程度下l - r e l i a b i l i t y 图6 7 模拟不同网络规模下l - r e l i a b i l i t y 6 7 6 8 第i v 页 豇鲐 巧 甜 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文题目： 区丝竺囵缝! 嗑蜒墨塑丝墨奎 学位论文作者签名： 垒要塞日 9 j ：矽f 年f 1 月，归 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留，使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或扫描等复制手段保存，汇编学位论文 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：堑塑! 鱼鱼! 重亟銎鎏堑盗! ：登 学位论文作者签名： 童! l 坠日期：。1 年，月，细 作者指导教师签名：拙塾日期：肼年月，细 国防科学技术大学研究生院学位论文 第一章绪论 1 1 研究背景和意义 计算机网络的可靠性，无论在民用还是军事应用上都有广泛的要求。未来战 争中，网络将成为战争指挥的中枢以及敌方首先打击的目标。目前，网络随着科 技的进步已经得到长足发展：相比之下，对网络可靠性的研究工作由于网络的庞 大而变得越来越复杂，并且滞后于网络的发展。因此，如何设计可靠性较高的网 络以及对现有网络的可靠性进行合理评价已经成为当务之急。 网络通信作为社会的基础设施，必须满足社会的高效运作需求。因此，对于 社会需求来说，设计高有效性的网络是高可靠性网络的重要体现。高有效性两络是 指网络各项性能都能满足社会的需求目前不断增加的网络用户和应用，导致网 络负担沉重，网络设备超负荷运转，从而引起网络性能下降。这就需要对网络的 性能指标进行提取与分析，对网络性能进行改善和提高，因此网络性能研究应运 而生。发现网络瓶颈，优化网络配置，并进一步发现网络中可能存在的潜在危险， 更加有效地进行网络性能管理，提供网络服务质量的验证和控制，对服务提供商 的服务质量指标进行量化、比较和验证，是网络性能研究的主要目的。 网络流量研究是网络性能研究的重要基础部分。越来越多的网络应用程序需 要了解流量等网络运行参数，以支持可区分的服务这些实时的流量信息对于许 多网管业务，如主动式和被动式的资源管理、流量工程、端到端的服务质量保证。 显得尤为重要【l 却】。网络流量特征是分析和研究网络性能、科学规划网络建设的 基础。在目前流量特征下对网络的性能指标分析是直接关系到网络具有高稳定业 务量，可靠运作的必然要求。流量模型是网络性能分析和网络规划设计的基础， 精确的流量模型对设计高性能网络协议、高效网络拓扑结构，业务量预测与网络 规划、高性能价格比的网络设备与服务器、精确的网络性能分析与预测、拥塞管 理与流量均衡都有重要意义。 越来越多的研究和测量发现网络呈现出流量的自相似性，具有这样特性的网 络也被称为自相似网络自相似网络可靠性的研究即是基于反映自相似性质的流 量模型进行网络可靠性的研究，其目的就是通过对网络具有影响的重要因素进行 分析，并进一步对网络可靠性进行分析，最后由此设计出具有高性能和高可靠性 的网络结构，疏通业务量，提升通信服务质量级别，满足社会的通信需求 第1 页 国防科学技术大学研究生院学位论文 1 2 国内外研究现状 1 2 1 网络可靠性研究现状 网络可靠性的研究始于上世纪6 0 年代，并由于d a r p a 对a r p a n e t 的投入 而得到真正的关注和发展。最初建立的模型是在n 个节点和m 条链路的网络中， 考察服从泊松过程的消息通过网络的延迟的数学期望。可靠性的普遍理解是：系 统在规定条件下、规定时间内、完成规定功能的能力。 1 2 1 1 网络可靠性指标研究 目前对网络可靠性的指标研究可以总结为以下三个指标：抗毁性 ( k v u 】n 锄b m 劝、生存性( s u r v i v a b i l i t y ) 和有效性( a v m l a b i l i t y ) 。 抗毁性和生存性是最早提出的两个网络可靠性指标。网络静抗毁性是指为了 中断部分节点之间的通信需要破坏的最少节点数或链路数，粘聚度和连通度眇，国 是抗毁性的两种度量网络抗毁性描述了网络在外界破坏作用下的可靠性，实际 上是网络拓扑结构的可靠性，与网络部件的可靠性无关。抗毁性是军用网的一项 重要指标 考虑网络部件的随机失效的影响而提出的生存性概念是网络在网络部件随机 破坏作用下的网络可靠性指标。网络的生存性是指对于节点或链路具有一定失效 概率的网络，在随机性破坏作用下，能够保持网络连通的概率。生存性指标是概 率性的，它不仅和网络的拓扑结构有关，也和网络部件的故障概率、外部故障以 及维修策略等有关。常用的指标是连通概率，是指在规定的时间内网络一直保持 连通的概率p 一。针对分析的范围不同，其可靠度的意义也有所不同，主要包括端 端可靠度、1 【端可靠度和全端可靠度端端可靠度是指网络中任意两节点之间存 在一条通路径的概率【9 ，1 0 , 1 1 , 1 2 , 妇j k 端可靠度是指网络保持k 个端点之间连通的概 率，即网络中任意给定的节点子集k 中各节点均处于工作状态，且各节点之问至 少存在一条路径的概率【l ”“。全端可靠度是衡量整个网络在部件故障情况下的生 存能力。g i l b e r t 和k e l m a n s 提出了全端可靠度概念原型1 6 ，啪，其假设节点绝对可 靠，链路具有相同的生存概率。f r a n k 把它推广为节点和链路具有一定生存概率 的情况【1 8 1 s r i v a r 睁r a t a n a 等【1 研把神经网络方法运用到全端可靠度的计算中，得 到其近似解s a w i o n e k 等1 2 0 1 假定节点完全可靠，链路故障统计独立，然后用离散 近似优化技术求得网络的全端可靠度。 网络的抗毁性和生存性是从图论或图论与概率论的角度来考察网络的可靠性 问题。实际上，除了生存性问题，人们还要关心的是网络“完成规定功能的能力”， 第2 页 国防科学技术大学研究生院学位论文 为此必须考虑网络的业务性能( 如网络的吞吐量和时延等) 网络的有效性便是 一种基于网络业务性能的可靠性指标，它指出了网络在网络部件失效条件下满足 通信业务性能要求的程度。所以有效性是考虑满足网络业务性能条件下的网络可 靠性，它的测度随着考察业务的不同而不同【2 1 捌。b a + b e r i s 等田】给出了加权端端 连通概率，该指标把网络的端端信息流量对相应的端端连通概率加权，并求全网 的平均值该指标可用于比较具有不同拓扑结构和不同流量分布网络的可靠性， 但没有涉及到网络的具体业务性能。为此，b a r b e d s l 2 3 提出了网络吞吐量超过一个 给定阈值l 的概率，比较好地反映了网络部件失效所引起的网络吞吐量的下降。 d e u e 洳g y e 】提出了一种基于网络吞吐量的有效性指标。p a r k 2 5 1 介绍了一种基于 传输时延的网络有效性指标，b o n a v e n t u r a t 2 6 1 介绍了一种对于电路交换网和分组交 换网的网络有效性指标。陈坚 2 7 1 等利用网络中传输时延阀值选择有效路径并用业 务量对有效路径连通概率进行加权，建立一种基于最小路径的网络的可靠性模型。 为了在网络性能分析中综合考虑各链路容量限制和可靠度对网络性能的影响，k 首先提出了网络容量阀值可靠度的概念 2 r l ，即网络中源点s 至汇点t 的容量不小 于预先给定的最小需求容量的概率，a g g a r w a l 提出了计算网络容量阀值可靠度的 使用方法 2 9 , 3 0 l ，并提出了网络加权可靠度的概念口n 。随后，a g g a 掰a l 口习又提出了 计算网络加权可靠度的快速算法，但该算法的主要计算量在于最小路的展开比较 大。因此刘陈【3 3 】给出了最小路展开的递推公式并提出了容量饱和状态的概念，进 而提出了一种计算网络加权可靠度的新算法。董军等刚提出了网络负荷平衡度的 概念，能很好地反映了各节点间的链路上资源的使用情况，有利于使全网的负荷 达到平衡，使网络具有更好的有效性。以上研究情况表明，网络的有效性研究更 面向通信业务，面向用户，更具直观性，是目前网络可靠性研究的热点。 综上所述，目前存在许多用于描述网络可靠性的测度，它们从不同角度反映 了网络的可靠性。网络的抗毁性反映了网络拓扑结构的可靠性。网络的生存性给 出了网络部件( 节点或链路) 在失效统计独立或相关时的可靠性。网络有效性是 基于网络业务性能的可靠性指标。 由于自相似网络的可靠性研究是通过分析网络业务性能进而进行可靠性分 析，所以本课题主要是针对网络的有效性所做的研究。在本文中，若无特殊说明， 网络的可靠性指的就是网络的有效性。 1 2 1 2 网络可靠性分析方法 网络可靠性的分析方法通常可分为以下几种：图论，故障树分析方法，随机 过程模型，p e t r i 网，计算机仿真等。 ( 一) 图论 第3 页 国防科学技术大学研究生院学位论文 目前网络的抗毁性研究考虑到网络的拓扑结构，采用图论的有关理论和算法 基本上能够有效解决网络抗毁性的评估问题。 例如对一类具有静态结构的通信系统( 即网络部件不可维修且不采用其它保 护措施) ，b a r a n 根据部件生存概率利用m o n t ec a r l o 法模拟随机性破坏引起的节 点和链路失效，在遭到破坏后幸存下来的网络中，选出一个最大连通子网络，其 节点数的平均值占原网络节点数的百分率，即为网络的连通概率的估计d 5 1 。 对网络生存性进行研究时还可以利用图论的基本知识进行分析。 ( 二) 故障树分析 故障树分析方法简单地讲就是把系统最不希望发生的故障作为故障分析的目 标，把选定的系统故障状态称为顶事件，然后找出引起顶事件的底层因素。 故障树分析运用理论符号和逻辑推理对复杂产品的故障逐个地、系统地进行 分析，找出原因及其因果关系，明确基本事件发生的概率和场合，进而求出系统 发生故障的概率，为系统可靠性提供定性和定量分析。 比较简单的网络可以利用故障树模型和已知的故障树分析法进行可靠性分析 评估。周忠宝等针对故障树分析网络可靠性局限性，对故障树分析方法进行了改 进p 6 】。该分析方法适合对简单的网络进行建模，对于比较复杂的网络来说，运用 此方法进行建模是比较困难的。 ( 三) 随机过程模型 随机过程模型包括马尔可夫( m a r k o v ) 模型、排队论模型等，是分析复杂系统 的最常用的模型。网络部件失效本身就可以看作一个随机过程，因此也可以用随 机过程模型来分析网络的可靠性。例如v i c p r a s a n n ak u m a r 等基于随机过程模型 构造系统的最小生成树估计分布系统可靠性即。 ( 四) p c t r i 网 p c t r i 网是进行离散事件动态系统建模与仿真分析的有力工具，它不仅能够描 述同步、并发、资源争用等特性，本身也含有自控制机制，因此适合网络系统描 述与建模。 国防科学技术大学的武小悦教授提出了一种用于分析网络可靠性的扩展的、 面向对象的p c t r i 网模型g o o p n ( g c n e r a l i z c do b j e c to r i e n t e dp c t r in e t ) ，并给出了 进行可靠性建模分析的工具【3 硼。该模型可以统一处理网络的连通可靠性问题，可 以较好地适应系统要素的交化。但通常的p e 嫡网的描述能力仍然有限，对复杂系 统建模时，容易造成状态组合爆炸现象。 ( 五) 计算机仿真 计算机仿真是开发，测试、评估网络的一种重要方法。周鸿志在文献【3 9 】中 对如何利用仿真得到网络有效性的方法迸行了初步的阐述。基于重要性抽样法o s ) 第4 页 国防科学技术大学研究生院学位论文 的技术已经表现出在网络的各个不同领域中具有巨大的应用前景，如j s c o t t s t a d l e r 等利用i s 对网络的行为进行仿真研究 4 0 1 。故障( 包括消息的丢失或损坏、 主机界面或主机的重新安排、本地或远程主机的挂起等) 注入法也是可靠性分析 的一个重要方法，可以研究硬件故障或软件缺陷、通讯故障( 如消息的损坏或丢 失) 、在故障条件下软件行为的改变等对网络行为的影响，该方法一般需要在仿 真环境中进行0 1 1 利用仿真方法进行网络可靠性研究时，当考虑部件具有多种工 作模式和失效模式时，描述网络的模型的状态数将大到惊人的程度，给网络可靠 性的计算带来了极大的困难。为了克服模型规模的限制，许多研究人员对此进行 研究，提出了一些减少计算量的方法 4 2 , 4 3 1 2 2 网络流量模型相关研究 流量模型是网络性能分析的重要前提，模型的选取或建立必须能够反映网络 流量的真实特征。目前已经出现了多种网络流量模型，为了进行准确的性能分析 ( 包括可靠性分析) ，选取或建立一种较好的模型将非常关键。 1 2 2 i 网络流量特征 通过对流量的测量，人们发现互联网通信量的主要特性有m ： 1 t c p ( t r a a s f e r c o n t r o l p r o t o c 0 1 ) 占据了网络的主要流量 网络流量研究显示t c p 协议是互联网上的主要协议【4 飘。近年来t c p 报文是 造成互联网通信量的主要因素，并且在可预见的将来还是这样。 2 数据流是双向的，但通常是非对称的 互联网上大部分的应用都是双向交换数据的，因此网络的数据流是双向的。 但是两个方向上的数据传输率有很大的差异。例如，网站下载文件时，从网站到 客户端方向的数据量比相反方向要多。 3 包的到达过程不是泊松过程 传统的排队理论和网络分析通常都假设包的到达过程是泊松( p 0 i s n ) 过程， 即包到达的间隔时间服从负指数分布。泊松模型因为指数分布的无记忆性，也就 是事件之间的非相关性，使其在应用上要比其它模型更加简单。 然而，近年来对互联网络通信量的测量显示包到达的过程不是泊松过程。大 部分时候是多个包连续到达，即包的到达是有突发性的( 包的到达量在较宽时间 尺度上变化较大，不是平稳到达的) 。泊松过程不足以精确地描述实际网络中包 的到达过程。 4 会话的到达过程是泊松过程 第5 页 国防科学技术大学研究生院学位论文 尽管互联网上包的到达过程不是泊松过程，对于确定的某一个会话，其数据 流的到达过程是泊松过程。 5 包的地址分布非均匀 互联网上约1 0 的主机占据了约9 0 的流量。 6 网络通信量具有局域性 互联网流量的局域性包括时间局域性和空间局域性。用户在应用层对互联网 的访问反映在包的时间和源、目的地址上，从而显示出基于时间的相关( 时问局 域性) 和基于空间的相关( 空间局域性) 。 7 汇聚的互联网通信量表现出自相似性的特性 由于互联网本身的多变性、多种网络应用的混合、网络接口速度的不同、不 同的网络访问技术以及用户行为的变化性，导致描述互联网通信量是很困难的。 不过人们已经发现互联网通信量具有自相似性( s e l fs i m i l a r i t y ) ，它的物理描述为 网络流量在很宽的时间尺度( 几十毫秒，秒、分钟、小时) 内存在突发0 3 u r s t ) 现 象，自相似性普遍存在于各种互联网通信量中。 8 网络流量显示为重尾分布 流量分布的重尾分布，表现为流量分布概率变化趋势是平稳下降的，概率分 布大部分集中在分布曲线尾部。 以上网络流量特征中，第3 、7 、8 点对网络流量研究具有很大的参考意义。 1 2 2 2 网络流量模型介绍 互联网业务量的高突发性以及网络的异构性，使得网络流量呈现复杂的非线 性，建立流量模型越发困难。早期的网络流量模型，是经典流量模型，也即借鉴 公用交换电话网p s t n ( p u b l i cs w i t c ht e l e p h o n e n e t ) 的流量模型，用泊松模型描述 网络的数据流量，以及马尔可夫模型等等。近来网络节点数呈指数形式增加，新 的网络应用( 例如v o d ，v o p ，远程教学等) 的出现，进一步增加了网络流量特 征化的困难，特别是不同的网络应用具有不同的流量特征。但人们对网络流量模 型的摸索也在不断地进行，从而产生了多种模型； 1 经典流量模型p s t n 和马尔可夫模型( m a x k o vm o d e l ) 这两种模型都是基于指数分布来描述包的到达过程的，而且由于泊松或马尔 可夫模型具有短程相关特性即只在很短的时间内表现出突发性，而实际网络业务 流量在多数甚至全部的时间尺度内均表现出很大的突发性，所以这两种模型并不 适用于实际网络流量的分析。 2 流体模型( f l u i dm o d e l ) 第6 页 国防科学技术大学研究生院学位论文 当通信量中的流量种类非常多，汇聚的流量相对于单个子流的流量要大很多 时，每个子流的流量变化对通信量的影响将很小，就像水管中的一个分子的运动 对水管流量的影响一样。在这种情况下，通信量在一段时间内将会保持相对恒定。 流体模型假设通信量在相当长的一段时间内大致恒定。通信量的波动由事件 触发，引起流量的变化。例如，在t c p 仰传输大长度文件，而且网络状态保持不 变时，就可以应用流体模型。显然，流体模型也不能描述出实际流量的突发性。 3 自相似流量模型( s e l f - s i m i l a rm o d e l ) 自相似模型是最接近实际互联网情况的模型，也是目前应用最广泛的互联网 流量模型 4 4 1 。使用较多的自相似模型包括： ( 1 ) 分形布朗运动( f r a c t i o n a lb r o w n i a nm o t i o n ) ； ( 2 ) 分形高斯噪声口m c t i o n a lg a u s s i a nn o i s e ) ； ( 3 ) 分形a r i m a 过程( f r a c t i o n a la u t o r e g r e s s i v ei n t e g r a t e dm o v i n ga v e r a g e p r o c e s s e s ) ： ( 4 ) 小波方法( w a v e l e t ) ； ( 5 ) o n o f f 模型； ( 6 ) p o i s s o n - z e t a 过程； 确定性的混沌映像模型( d e t e r m i n i s t i cc h a o t i cm a p s ) ： ( 8 ) m g 0 。模型； ( 9 ) 叠加a r 0 ) 模型( s u p e r i m p o s i n ga r 0 ) ) 。 这些模型能较好地反映网络流量的突发性。其流量参数化过程描述将在第二 章详细介绍。 ， 4 基于实际测试的网络流量模型 基于实际测试的流量模型是通过对实际网络流量进行大量的测量，通过数据 采集，然后对数据进行统计，提出网络流量到达时间间隔分布规律。这种模型依 赖于测量技术和数理统计技术。 谢高岗在对具体网络进行测试的基础上，提出了网络流量预测和性能分析的 方法，以预澳9 某个时刻的网络流量、延迟及其延迟上界，并定义了预测的精度， 测试表明该方法具有较高的预测精度 4 6 j 。 彭锡涛利用流量采集系统实际采集网络流量的数据，提出了一种基于实测的 网络流量模型m 。模型考虑时间对流量的影响，根据测试的历史数据采用统计的 方法建立网络流量模型。该模型具有很好的流量预测精度，但该模型不适用于流 量比较小的工作主机。 以上两种模型在建立之前对网络流量数据使用直接测量进行采集，而目前高 速网络技术的发展使得对巨大的网络流量进行直接测量几乎不可能。 第7 页 国防科学技术大学研究生院学位论文 1 2 3 基于流量模型的网络可靠性研究现状 目前，越来越多的反映自相似特性的网络流量模型的建立为进行不同流量模 型下的网络性能分析提供了很好的基础。文军等1 4 s l 采用概率分析方法，通过分析 过去的网络业务流流建立量模型，能实时地预测未来的业务流量，并对网络带宽 利用率、网络自相似程度及缓存大小之间关系进行分析。李景聪等f 4 9 】利用o n o f f 流量模型对网络排队性能进行仿真。f i o r i n i t s o 利用并发重尾流量源产生流量及马 尔可夫调制流量模型对网络q o s 进行分析。宋丽华等酬利用n s 2 仿真工具在 0 n 幻f f 模型下对网络排队性能进行了分析。 关于自相似特征下的性能研究大都是通过计算机仿真的方法对网络各项性能 指标进行分析，目的是为了得到服务质量( q o s ) 保障。例如能提供较大的带宽、较 低的包丢失率、满足端到端延迟和抖动限制等。这样便能达到网络资源( 例如缓 存大小和带宽等) 的最佳利用。合理地进行业务流的调度，达到较高的性能，从 而提高网络的可靠性。 以上工作研究了网络基本性能指标( 网络延迟时间、网络吞吐量、网络延迟 抖动、丢包率、网络带宽利用率等) 在流量模型下的特征。这些特征同时也是对 网络可靠性进行分析的重要基础。在1 2 1 1 节中对可靠性研究的众多成果中，可 以发现，它们或者没有以网络流量的自相似到达过程为研究基础，或者是假设流 量到达过程为基于指数分布的据我们所知，目前国内外关于自相似网络的可靠 性研究为数不多。 1 3 主要工作及创新 本文针对自相似流量下的网络可靠性进行研究。基于o n o f f 流量模型对网 络的有效带宽、平均排队延迟及平均丢包率进行分析。在对网络业务性能分析基 础上提出网络的可靠性模型。具体说来，本文的创新工作主要体现在： 1 针对自相似网络可靠性研究的解析分析工作； ( 1 ) 针对o n o f f 流量源的带宽分配，提出了一种自相似网络有效带宽模型。 首先分析节点和到达业务流之间的排队关系，通过大偏差理论结合o n o f f 模型 对自相似网络队列长度分布进行分析，进而给出了自相似网络的有效带宽模型。 ( 2 ) 针对信息的排队延迟，提出了一种自相似网络平均排队延迟分析模型。基 于稳态队列长度分布，求均值得到稳态平均队列长度，进而通过l i t t l e 定理得到 网络的平均排队延迟时问：针对信息的丢包情况，提出了一种自相似网络平均丢 第8 页 国防科学技术大学研究生院学位论文 包率分析模型。利用队列长度与丢包率之间的关系给出了稳态下丢包率的分布， 进而得到平均丢包率。 ( 3 ) 在网络业务性能分析的基础上，提出基于o n o f f 模型的自相似网络可靠 性模型。为了分析自相似网络可靠性，结合业务性能对网络可靠性指标进行形式 化。然后通过平均排队延迟和平均丢包率两个业务性能指标，分别提出了基于平 均排队延迟的可靠性模型和基于平均丢包率的可靠性模型。为了更加全面衡量网 络的可靠性，进一步提出了自相似网络的可靠性矢量模型。 2 为验证解析结果的正确性，针对自相似网络可靠性研究的相关模拟工作： ( 1 ) 给出了自相似网络平均排队延迟和平均丢包率在n s - 2 模拟器上的模拟结 果，并验证了模拟结果与解析结果的一致性。 ( 2 ) 设计并实现了针对自相似网络可靠性的模拟器一s n i 强，它可以对自相似 网络的平均排队延迟和平均丢包率进行模拟，进而分析可靠性。通过模拟发现， 理论分析结果与模拟结果是吻合的，从而验证了所建可靠性模型的正确性。 1 4 论文组织结构 全文共分为七章。 第一章是绪论，主要介绍了课题的背景和意义、目前关于网络可靠性的研究 现状、网络可靠性研究的主要研究内容和可靠性指标、网络流量模型特征及模型 相关研究内容，以及最后介绍了全文的主要研究内容及创新点。 第二章是自相似理论及模型介绍。主要分析了网络流量的自相似性质及描述 网络自相似性质的各种数学和物理流量模型。重点对一种数学模型f b m ( 分形布 朗运动) 和一种物理模型o n o f f 进行了分析。 第三章基于0 n 0 f f 模型对网络的有效带宽进行分析。在分析网络业务流排 队过程和介绍大偏差理论的基础上，结合o n o f f 模型得到自相似网络的有效带 宽模型，最后对有效带宽进行了仿真分析。 第四章基于0 n ，o f f 模型对网络业务性能进行分析。总结前人对网络业务性 能的研究，通过第三章得到的网络队列长度分布性质，结合o n o f f 模型，分别 对自相似网络平均排队延迟和平均丢包率进行了建模分析。并利用n s - 2 模拟器 验证了这两种模型的正确性。 第五章基于0 n o f f 模型的网络可靠性建模与分析。首先介绍了排队的网络， 对网络各节点及链路上的流量关系进行分析。基于业务性能对自相似网络可靠性 指标进行形式化。结合第四章的结论，提出了基于平均排队延迟的可靠性模型和 第9 页 国防科学技术大学研究生院学位论文 基于平均丢包率的可靠性模型，并分别进行了分析。最后提出了自相似网络可靠 性矢量模型，给出了分析结果。 第六章是自相似网络可靠性仿真与模拟。设计并实现了自相似网络可靠性模 拟器s n r s ，对该模拟器的特点、数据结构、工作流程、运行实例等进行了详细 介绍。 第七章是结束语。对本文的工作进行总结，指出今后的研究方向。 第l o 页 国防科学技术大学研究生院学位论文 第二章自相似理论及模型介绍 网络流量的一个重要特性是自相似性自相似模型是网络流量分析的基础， 通过它可以进行排队性能分析和