（计算机应用技术专业论文）基于测量和tes模型的接纳控制算法研究.pdf

南京邮电学院学位论文独创性声明 y 、6 2 8 9 2 了 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电学院或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：日期： 南京邮电学院学位论文使用授权声明 南京邮电学院、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电学院研究生部办理。 研究生签名：导师签名：日期： 摘要 传统i p 网络所采用的“尽力而为”转发机制，已经不能满足用户的q o s 要求。q o s 实现阎题一般可分为两部分：( 1 ) q o s 路由问题；( 2 ) 资源共享 问题，其研究对象为各种接纳控制( a d l n i s s i o nc o n t r 0 1 ) 、接入控制( a c c e s s c o n t r 0 1 ) 、缓冲器管理与调度机制等。本文的工作属于后者范畴。 t e s 过程是一个具有任意边缘分布和很宽范围自相关函数的自相关序 列。用t e s 过程对网络业务流进行建模可以产生比较理想的效果。本文用 t e s 过程模拟大业务流( h e a v yt r a f f i c ) 。 基于测量的接纳控制算法( m b a c ) 由两部分组成：估计网络负荷的 测量过程和判别等式( e q u a t i o n ) 。迄今为止，已经提出了许多m b a c 算法。 有关研究工作，通过仿真比较这些m b a c 算法的性能，结果发现它们能取 得相近或相同的性能。 本文基于现有的工作，从理论上证明了所有的m b a c 算法的判别等式 可以表示为相同的结构；证明了m b a c 算法使用相同的测量过程，调整它 们的参数满足一定的条件，就能实现相同的性能，并用仿真证实了这个结 论；还通过仿真，分析与比较了m b a c 算法预测服务失败的能力，结果发 现没有哪一个算法具有精确预测服务失败的能力。因此，影响m b a c 算法 性能的关键因素是测量过程而不是判别等式。 现有髓a c 算法的测量过程，不是用业务流的平均速率就是用它的峰值 速率来表示该业务流的申请带宽。显然，业务流实际占用的带宽大于它的 平均速率又小于它的峰值速率，而业务流的有效带宽则是对业务流实际占 用的带宽的有效描述。为此，本文基于t e s 过程推导出了一个计算大业务 流的有效带宽的简明公式，并用所得到的有效带宽表示大业务流的申请带 宽，对h l b a c 算法进行了仿真分析，结果表明，采用有效带宽后的船a c 算 法能够取得更好的网络性能。 关键词：t e s 过程，接纳控制算法，业务流建模，有效带宽 南京邮电学院硕士论文 a b s t r a c t t h e 们衄i 妇gm e c h a i l i 锄o f “b e s t e 丘o n ”w h i c h i s a d o p t e db y 血e t r a d i 士i o n a 】i pn 咖0 r ki sn o tp o s s i b l et os a t i s 母t h eu 娜q o sn e e dn o wt h e p r o b l e mo fq o s 狐p l 哪e n 诅t i o nc 趾b e d i v i d e di n t ot w op a n s ：( 1 ) q o sm l 曲l g p m b l e m ，( 2 ) r e s o u r c es h a f i n gp r o b l e m ，m e 吼埘e c to fw m c hi s a 1 1k i i l d so f 芦d m i s s i o nc o m r o l ，a c c e s sc o n 仃o l ，b 强rm a a g e m c t 蛆ds c h e d u j es y s t e me t c j o bo f t h i s p a p e r b e l o n g s t o t l l e l a n e r t e sp r o c e s si sa na u 抽c o ”e l a t i o n s e q u e n c e w i ma r b i 缸a r y m a r g m a l d i s t r i b u t i o na n db m n da u t o c o n 弓l a t i o nf i l c t i o m m o d e l i n gn l en 嘶v o r kt r a 伍c u s i n gt e sp r o c e s sc 锄g e n e r a l l yl e a dt o 趾i d e a 王o u t c o m e n l i sp a p e ru s e st e s p r o c e s s 船t om o d e lh e a 、7t r a 丘i c m b a c a l g o r i t l l r n sh a 、他t w oc o l p o n e n t s ：am e a s l l r e m e mp r o c e s sw h i c h p r o d u c e s a i le s t i m a t eo fn e t w o r k1 0 a d 如d e q u a t i o n s a tp r e s e n t ，m o s to f m b a c a l g c d 岫s h a v eb e e n p r o p o s e d s o m e r e s e a r c h e r sl l s es i m u l a t i o nt oc o m p a r em e p e d b r n l a i l c eo f m b a ca l g o 删蚰s t h e yf m d a l l0 f 恤mc a na c l l i “en e a d ym e 5 a m ep e f f b m a n c e t h i sp a p e re x p 锄d s 也ep r o o fi n 【2 0 】a n dd e d u c e st l l a t e q u a t i o n so fa l l m a ca l g o r i m m sh a v et l l es 锄e s t m c t i l r e u s i n g 廿1 es 锄em e a 呲m e m p r o c e s s ，t h i sp 印e rd e m o n s t r a t e st h a tm b a ca l g o r i 也m sc a na c l 正e v et h es 锄e p e 面糊c et l l r o u g ht u n i l l gt l l e 删u 此l b l ep a r a m e t e r so f a l g o r i t h m s 1 1 l i sr e s u l t i sv e r i f i e d b ys h u l a t i o n 1 1 l i s p a p e r a l s oc o r n p a r e sm b a c a l g o r i t h i n s a b i l 崦o f f o r c c 枷n g 血ep m b a b i i 时o f s e i c e 础1 1 1 ef e s u l t so f s i m l a t i o n si nt h i sp 印e r i n d i c a t et h a tn o n eo ft h e d b a c a l 昏痢岫sc a n c l 】r a _ c e l y p r e d i c t t h e p r o b a b i l 时o ft l 地s e i c e 硒l m g 孔u st h ek e y t o ro fi n u e n c i i l gm b a c a l g o i j t h | n s p e m ) m l a n c ei st l l em e a s u 帕m n tp r o c e s st a t h c rt l l 龃e q l l a t i o n s m b a c a 1 9 0 r i t l l m sa tp r e s e mu e i t l l e ra v e r a g eo r p e a l 【e d n e s so f an e wn o w t od e n o t et h eb a n d 、 ，i d mi t a p p l i e s o b v i o l l s l y t h er e q l l i r e db a n d 、v i d t l li sb i g g e r 工h a n a v e r a g e 锄ds m a l l c ft l l 柚p e a k c d m s s e 圩e c t i v eb a n d 、v i d t l li sav a l i d d e s c r i p t o ro f t l l er e q l l i r e db a n d 、：v i d t h s oi nt t l i sp a p e rw e d e r i v eac o m p u 诅t i o n 2 南京邮电学院硕士论文 s i m p l ye 虢c 曲eb a n d 谢d t h 矗m c t i o no fh e a v yt r a m c b a s c do nt e sp r o c e s s ， e m p l o y t h e c o m p u t e d r c s u i t st od e n o t e1 l l e r e m d r c d b 越1 d 、i d m 卸dl l s e 脚m u l a t i o nt oa n a l y z em b a ca l g o r i 也m t h es i 咖l a t i l 培r e 叫t sd e m o i l s 舡a t et h a t am b a ca l g o r i t h mw i t he & c t i v eb a l l 撕d t l lc 龇a c q u i r eb e n e rp e 疵i m a i l c e i 哂7w o r d s ：t e sp r o c e s s e s ，a d m i s s 玉d nc o n t p o la l g o 删瑚，t r a 伍cm o d e l i n g ， e 雎c t i v eb 粕d v v i d t h 3 第一章引言 1 1 连接接纳控制( c a c ) 在a t m 和因特网中的应用 异步传输模式( a t m ) 以信元为单位传输，允许不同业务流的信元在传 输过程中通过统计复用提高网络链路的带宽利用率，而且能够保证各类业 务不同的服务质量( q o s ) 要求，并对网络中出现的拥塞实施流量控制。a t i 网络拥塞控制分为预防式控制和反应式控制，前者在用户呼叫请求时决定 是否为其所要传输的业务建立连接和分配网络带宽资源：反应式控制则通 过发送反馈信元来调整业务端的发送位率，防止拥塞。连接接纳控制( c a c ) 是预防式控制的一种，是i t u t 为a t m 的通信量控制而提出的“1 ，它的作用 是网络在新连接申请建立的时刻。根据新连接的业务特性、质量要求和网 络资源的当前状况对是否接纳此连接申请做出判决。只有当网络中有足够 的资源来保证新连接的q o s 要求，并且网络中其它已经建立连接的q o s 不 会因为它的接入而受到损害时，新连接才被接纳，否则被拒绝。在a t m 中 使用c a c 可以防止拥塞，为各种应用提供q o s 保证。就目前a t m 网络的发 展而言，其交换技术已经比较成熟，但网络的控制和管理方面仍然有许多 问题，包括从拥塞控制、c a c 和路由的实现到光传输协议的制定等等。c a c 是用户网络接口( u n i ) 的一个基本功能，是a t m 的一个关键问题。 近几年来，因特网等计算机网络中音频、视频等实时应用的需求在急 剧增长。这些应用要求网络中为它们提供一定的端到端q o s 保证，即希望 延迟、丢失率和抖动等性能指标处于一定范围”1 。而传统的因特网是“尽力 而为”的网络，其主要思想是当用户提出服务请求时，网络不会拒绝用户 舶要求，但是q o s 要依据网络当时的状况而定，报文的丢失率和抖动等性 能是得不到保证的，因此在因特网中实施c a c 是必要的。 i e t f 为了保证因特网中各种业务流的q o s 要求，设计了能为每一流 ( f l o w ) 保证服务的综合业务( i n t s e r v ) 模型。流是指分组会话中具有 相同q o s 要求的分组集合。c a c 是i n t s e r v 模型的一个重要组成部分，它 基于用户和网络达成服务协议，对用户的访问进行一定的监视和控制，有 6 南京邮电学院硕士论文 带4 于保证双方的共同利益。实旌c a c 能优化网络资源，保证各种业务的q o s 。 在因特网中实施c a c 有两种方式：一是根据已知的端到端网络特性和所需 要保证的q o s ，由端到端直接进行接纳控制；另一种是将c a c 分布在各主机 瓢路由器上，根据端到端的q o s 要求转换成本地q o s 参数，确定各局部节 点是否能接纳到达的流，只要有一个节点无法接纳，则整个流无法被接纳， 需要重新协商或退出。 1 2 基于测量的接纳控制算法的研究 c a c 算法需要流的特征参数输入。根据c a c 获取参数的不同方式，q o s 接纳控制算法可以分为两类：p 队c ( p a r a l t l e t e r b a s e da d m i s s i o n c o n t r 0 1 ) ，m b a c ( m e a s u r e m e n t b a s e da d m i s s i o nc o n t r 0 1 ) 。 p b a c 算法根据给定的业务流统计特征计算出最坏情况下所有业务流所 需的网络资源，其特点是在业务流到达之前能够计算出所需网络资源，适合 于可担保服务。 而m b a c 算法基于确切到达的业务流数量的测量而做出决策。它的特点 是无需知道业务流模型的特征，不能提供严格的q o s 保证，适合于负载受 控服务。 m b a c 算法由测量过程和接纳控制算法组成。接纳控制算法以测量过程 获得的参数为输入，结合新请求流的参数，做出是否接纳新请求流的决定。 如何设置测量过程的参数是很重要的，合适的参数值能提高m b a c 算法的性 能。 近几年，基于测量的q o s 接纳控制已成为研究热点，取得了一些重要成 果。迄今，有关研究可分为四类： 1 ) 对数据源模型有一定的要求或对系统模型进行简化处理 3 一1 0 ； o ，岛是元素j 出现的概率。0 是p ，的累积分布函 数，其中c 。= o ，勺= l 。对于o 毒 1 ，& 所起的作用是使后台t e s 序列的 采样路径更连续川“3 。而反函数法则允许我们把任何均匀分布的随机变量转 为具有任意边缘分布的随机变量，因为，若u 是【o ，1 ) 上均匀分布的随机变 量且f 是一个实际观测到的数据的分布函数，则肖= f - 1 ) 与实际观测到 的数据具有同样的分布f 4 “。 至此，根据上面的公式，就可以产生一个t e s 过程。t e s 过程的其它性 质( 如自相关函数等) 见文献 2 2 2 3 。 2 3 t e s 过程的建模方法 通过上面的描述，可以得出产生一个t e s 过程的流程图如图2 1 所示。 开始产生一个伪随机序列z 。，然后根据定的密度函数办产生圪。通 过模l 运算，k 和u 一，相加，这样就可得到后台序列。后台序列经过两次变 换得到前台序列。第一次变换可以使后台序列的采样路径更平滑，第二次 变换是为了使得前台序列和实际观测到的数据具有相同的边缘分布。 用t e s 理论建模，无需参数调整就能够保证匹配实际；观测到的数据的边 缘分布，但是在匹配自相关函数时，则需在一个大的参数空间里进行启发 式的搜索。因而它需要个软件环境来支持。b m e l a l e d 用t e s t o o l 对t e s 进行了建模“小“，并得出了些重要的结论。 南京邮电学院硕士论文 ， ， 申申： 修正 黼列申申申 扭曲堂室壹、 也一l) l 牟) ， i 图2 一l 产生t e s 过程的流程图 t e s t 0 0 l 是一个可视化、交互的软件环境，它支持t e s 建模。t e s t 0 0 1 允许使用者读入实际观测到的采样路径和计算它们的统计特性( 如概率直 方图、自相关函数等) 。它还允许使用者把由模型得出的统计特性图和由观 ；贝! 数据得出的统计特性图叠加到一起，以便于比较。但是t e s t o o l 的所有 权属于n e c 公司，只作为内部研究用，他们不发布这个软件。在这里，用 m a t l a b 对t e s 进行了建模。m a t l a b 具有高性能的数值计算能力和可视化的 开发环境，它还有几十种成熟的工具箱。它是各个领域的研究和工程应用 的有力的工具。 用t l a b 对t e s 建模的过程如下： ( 1 ) 构造实际观测到的数据的分布函数日，。 ( 2 ) 构造毋的反函数日；。 ( 3 ) 选择t e s 类型( 这里选择的是z e s + ) 。 ( 4 ) 选择一个平滑参数o f 1 。 ( 5 ) 选择修正序列的密度函数办。 ( 6 ) 根据一定的要求进行参数调试。 其中： 南京邮电学院硕士论文 刀2 善矗1 胁 q 9 k 是概率直方图所包含的元素数目；t 、也是元素k 的左右边界；只是元 素k 出现的概率。1 ( d 是集合a 的指标函数。调试过程中，选择 的k 时， 开始使k = l ，看其中是否有符合条件的；如果没有符合的，则连续地增大k 。 我们的目标是取得最小的k 值，使之能够符合条件。 2 4 有效带宽的基础 有效带宽是业务流的描述符( d e s c r i p t o r ) ，它表征为了满足个输入 流的q o s 要求，例如缓冲器的溢出概率、排队时延和丢包率等等，网络所 必须分配给该业务流的最小带宽。它通常由两个参数来描述，这两个参数 分另i j 称为时间参数和空间参数。一般情况下只考虑有效带宽的极限形式 郎让时问参数趋于无限。有效带宽仅仅由空间参数来描述。 有效带宽已成为接纳控制算法的一个重要参数。目前关于有效带宽的 文献很多。 4 4 提出了一个基于队长分布尾渐近行为的带宽估计方法， 4 5 基于一个确定时间间隔内到达的平均业务流数目和最大业务流数目等参 数。给出了带宽估计的近似表达式； 4 6 得到了基于o n o f f 业务流模型的 有效带宽； 4 7 比较了 4 4 4 6 等人提出的模型的一些性质，认为 4 6 提出 的模型无论在准确性还是在实时性上都优于前者。 4 8 讨论了经漏桶算法 规范后的0 n 0 f f 业务的等效带宽估计。 4 9 5 0 给出了马尔可夫链的有效 带宽。【3 7 给出了有效带宽的系统的回顾。 2 5 t e s 过程的有效带宽 3 6 在基于 3 7 的有效带宽定义的基础上给出了t e s 过程的有效带宽， 但他的方法计算复杂，不便于实时控制。在假设业务流是大业务流( h e a v y t r a f f i c ) 的情况下，下面将给出一个计算简单且便于实时控制的t e s 过程 的有效带宽的表达式。 南京邮电学院硕士论文 用t e s 过程可以对大业务流进行建模。当业务流是大业务流时，其有 效带宽可以用它的平均速率和渐近方差来描述( d e s c r i p t ) 5 “。此时，有 效带宽的定义如下： 口( 口) = 确+ 仉( 侈) ， ( 2 1 0 ) 其中，哺为平均速率，2 巩为渐近方差，口为队列长度的衰减速率。 2 5 1t e s 过程的平均速率 t e s 过程自q 平均速率3 为 其中m 为单位圆被分割的数目。石为l m 的向量，满足： 筇h = 筇，万e m = 1 ， ( 2 1 1 ) ( 2 1 2 ) 为m 1 的单位矢量，日+ 为q t e s 过程的一步转移概率矩阵，形式如下： 日+ = ( 2 1 3 ) 以为q t e s 过程的更新序列以( i n n o v a t i o ns e q u e n c e ) 的概率密度函数。定 义如下： 瓦为： 以2 乃( ，) = p = 珐啡，x 歹乙，乙= o ，1 ，m l ( 2 1 4 ) 或= 吉r 5 狮阮 ( 2 1 5 ) 其中：d ( x ) 为t e s 过程的扭曲函数( d i s t o r t e df u n c t i o n ) ，万：上。 2 5 2t e s 过程的方差 自协方差和方差的定义如下： 1，j h 东 氟，；磊 ， ， ， 一 ， 一 ，五 ， 旗站：。旗萌吐：v办九九：。a 南京邮电学院硕士论文 体( r ) = 叫卜， = 一层， 其中，矗为随机过程，以为矗的期望。 因此，：纯( o ) ，而t e s 过程的自协方差函数为。” 识( r ) = 芝刀( f 2 胛) i 西( f 2 疗v ) 1 2 一疋 故，一为： ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 ) = 疗( o ) = 芝i 西( f 2 石v ) l 一一= f d 2 ( x ) 卅 ( 2 1 9 ) 2 5 3t e s 过程的渐近方差 叫v 川z ) = 溉e 陪一嬲毋】n ( 2 2 0 ) 唧椰2 舰： x 一溉研柚 2 。埘， 烛e p 一憋 = 热= “ 2 5 4 一些具体的t e s 过程的有效带宽 本节将求出以在气上服从均匀分布、边缘函数为指数函数时t e s 过程 的有效带宽。 此时： 堕室坚皇堂堕塑主堡塞 日+ ：上 m 由石日+ = 石，霈= l 可缛出： ( 2 2 2 ) ( 2 2 3 ) 凳f 聋! 竺兰w 止塑业生，泣：。， 2 丢e 眦蝴= 杀f ( 1 - 砸) 1 l l 高w h 地竽】。 其中，万：占，五为指数分布的参数。 m 。 由( 2 】1 ) 得： = 寻篓m 一旁k 言写与+ 吉h 半c z z s ， 由( 2 1 9 ) 得： = 虻( 。) = f 。2 ( x ) 出一五22 矗 f l i l 一曲出五2 = 舞一五2 ( 2 2 6 ) 借助于m a t l a b ，分别计算出m 2 2 0 、1 6 0 、1 2 8 0 时t e s 过程的有效带宽。 m = 2 0 时由( 2 2 5 ) 可得： = 热。一b 筹+ 去h 孥= 半 亿z ， 由( 2 2 、( 2 2 7 ) 得： 2 奔。22 奔_ 1 僦( 兄) 2 ( 2 2 8 ) 同理可得m = 1 6 0 、1 2 8 0 时，t e s 过程的平均速率和渐近方差分别如式 ( 2 2 9 ) ( 2 。3 2 ) 所示： 矿= 塾一m 筹+ 嘉k 孥= 罕 眨z 。， 1 8 一 =r 塑室坚皇兰堕堡圭望奎 一 = 斋搿= 舞删6 ( 彳) 2 ( 2 3 0 ) 矿= 寻扣孕h 篙寺孥= 半 c z s ， 一= i 争一= 舞一，。砸y ( 2 髭， 由( 2 10 ) 、( 3 2 9 ) 一( 2 3 2 ) 可得出它证拍有效带宽分别为： 嘣胪i 0 0 3 1 旯+ 丧一o 5 。3 叫) 2 矽 ( 2 3 3 ) q m 妒) = 1 0 0 3 z + 吃苦一o 5 0 3 m 甲矽 ( 2 3 4 ) q m ( 卿= 1 。3 1 五+ 【矗事一。5 0 2 l ( 五甲矽 ( 2 3 5 ) 由( 2 3 3 ) 一( 2 3 5 ) 可以锝出，在业务流为大业务流的情况下，m 的取值 对右斯誉甯的斯信甚本沿什颤影响 2 6 网络仿真工具0 p n e t 简介 0 p n e t 网络仿真软件是目前世界上最先进的网络仿真开发和应用平台， 近两年被第三方权威机构( 如n e t w o r kw o r l d 等) 评选为“世界级网络仿 真软件”第一名。下面将简单介绍一下o p n e t 网络仿真软件。 p p n e t 网络仿真软件是m i l 3 公司的产品，m i l 3 公司是由m i t ( 麻省理工学 院) 的几位教师在1 9 8 6 年创建的，他们把在m i t 的研究成果产品化，开发出 了m l 3 公司的第一个产品m o d e l e r ，并在随后将其扩充、完善为0 p n e t 产品 系列。目前，该产品系列主要包括以下四个产品： ( 1 ) p 1 a n n e r ，亦称i td e c i s i o n g u r u ，是一个独立的网络规划设计工 具，不具有网络节点和协议建模功能仅限于基于基本模型库的网络建模 和模拟。p l a n n e r 与h po p e n v i e w 中的n n m ( n e t w o r kn o d em a n a 屠e r ) 和 h e t m e t r i x ( n e t w o r kt r a f f i cm o n i t o rs y s t e m ) 有最紧密的接口，能够自 动地读入网络的拓扑结构和流量数据。而且，在最新的n e t m e t r i x 软件中 1 9 南京邮电学院硬士论文 已经将p l a n n e ro e m 包括进来，称为s e r v i c es i 叫l a t o r 。 ( 2 ) m o d e l e r ，m i l 3 公司起家的拳头产品，是一种功能十分强大的网 络r d 仿真平台，支持在网络各个层次的设备、链路和协议的精确建模， 并提供丰富的外界开发接口，同时还内含p 1 a n n e r 的全部功能。 ( 3 ) m o d e l e r r a d i o ，在d e l e r 的基础上增加对无线和移动网络仿 真的支持，目前包括移动电话、卫星、无线l a n 等。 ( 4 ) 0 x d ，利用“c o s i m u l a t i o n ”技术，在模型网络环境中验证硬件 的设计。 o p n e t 支持s u n ，h p ，i 嘲，s g i 工作站和一般p c 等硬件设备，可以运 行在u n i x 、n t 或w i n 9 5 9 8 等操作系统上，最好采用1 0 2 4 $ 7 6 8 显示模式， 由于需要开设较多的窗口，建议配置1 7 英寸以上的显示器。 o p n e t 软件采用动态的l i c e n s e 控制方法，用户需要配置一台或多台 l i c e n s es e r v e r ，以及和l i c e n s es e r v e r 在一个子网内的仿真工作站才能 获取l i c e n s e 的使用权。 0 p n e t 模型分为n e t w o r k 、n 0 d e 和p r o c e s s 三个层次( 见图2 2 ) ，分 别在图形界面的p r o j e c te d i t o r 、n o d ee d i t o r 和p r o c e s se d i t o r 工具中 建立。 n e t w o r k 模型是最高层次的模型，由网络节点( d e ) 和连接网络节点 的通信链路( 1 i n k ) 组成，由该层模型可直接建立起仿真网络的拓扑结构。 n 0 d e 模型由协议m o d u l e 和属于连接m o d u l e 的各种c o n n e c t i o n s 组成，如 物理接口m o d u l e 、m a cm d d u l e 、i p1 i i o d u l e 、r o u t em o d u l e 、t c pm o d u l e 、 a p p l i c a t i o nm o d u l e 、p a c k e ts t r e 锄、s t a t i s t i cw i r e s 等等。每个m o d u l e 对应一个或多个p r o c e s s 模型，p r o c e s s 模型由有限状态机来描述，有限状 态机用c 语言编程。用户可以在上述三个层次的任何地方切入编程，建立 所需的n e t w o r k 、n 0 d e 或p r o c e s s 模型。 0 p n e t 采用基于包的建模机制( s i u l a t i o no np a c k e tl e v e l ) ，模拟 实际物理网络中p a c k e t 的流动，包括在网络设备间的流动和网络设备内部 帕处理过程，模拟实际网络协议中的组包和拆包的过程，可以生成、编辑 任何标准的或自定义的p a c k e t 格式，利用d e b u g 功能，还可以在模拟过程 南京邮电学院硕士论文 f p 察看任何特定的p a c k e t 的包头( h e a d e r ) 和净荷( p a y l o a d ) 的内容。 0 p n e t 采用离散事件驱动的模拟机理( d i s c r e t ee v e n td r i v e n ) ，其中 “事件”是指网络状态的变化，也就是说，只有网络状态发生变化时，模 拟机才工作，网络状态不发生变化的时间段不执行任何模拟计算，即被跳 ( a ) n e t v v o r k 模型 ( b ) n o d e 模型 2 1 - 争兮凄滔 一一 9 毒7 南。 ( c ) p r o c e s s 模型 图2 20 p n e t 模型的层次 过。因此，与时间驱动相比，离散事件驱动的模拟机计算效率得到很大提 高。 0 p n e t 具有丰富的统计量收集和分析功能。它可以直接收集常用的各个 网络层次的性能统计参数，并有多种有关统计参数的采集和处理方法，还 可以通过底层网络模型编程，收集特殊的网络参数。o p n e t 还有丰富的图表 显示和编辑功能、模拟错误提示和告警功能，能够方便地编制和输出仿真 报告。 2 7 仿真与结果分析 依据有效带宽理论，对于一个稳定的和遍历的过程，如果把它作为输 入过程，其有效带宽作为服务速率，则它的有效带宽的反函数是排队队长 的衰减速率( 缓冲器是无限的) 或是缓冲器的溢出概率( 缓冲器是有限的) 。 咀下，我们将进行几次仿真，t e s 过程作为输入过程，我们的有效带宽函数 和y a n g s 的有效带宽函数分别作为服务速率。 为了简单起见，网络拓扑只有一条链路，如2 3 图所示。 其中节点s r c 为数据源节点，将按照边缘分布为指数分布的t e s 过程 发送数据；r o u t e 节点为服务节点，服务速率分别为本文推导的有效带宽和 壹室坚皇兰堕堡主笙塞 文 雏 推导的有效带宽；d e s t 节点为目的节点，其功能就是销毁接收到的 数据包。这样，就产生了一个t e s t e s l 队列。我们在仿真工具o p n e t 上 对这个队列进行了仿真，这里假设缓冲器是无限的。基于对排队队长的观 察，实际的累积分布函数( c u 叫l a t i v ed i s t r i b u t j o nf u n c t i o n s ) 能够 图2 3 网络仿真拓扑 利用o p n e t 自带的工具进行计算。排队队长的衰减速率的概率分布就是l 减去累积分布函数。我们将把重点放在排队孰长的衰减速率和有效带宽的 反函数的比较上。 在进行的三次仿真中，t e s 过程的边缘分布的参数分别被设置为5 、2 、 l 相应的计算出来的有效带宽见表2 1 。图2 4 给出了计算出来的有效带 宽和排队队长衰减速率反函数的曲线；图2 5 给出丢包率和网络资源利用 率的曲线。从图2 4 、图2 5 中我们可以锝出以下结论： 排从队长的衰减速率和有效带宽之间的关系是线性。这一点从式( 2 3 3 ) 一( 2 3 5 ) 能够很容易看出。 有效带宽的数值髓着边缘分布参数的增大而增大。这很容易理解。随着 边缘分布参数的增大，数据源的平均到达率也就变大；因此也就需要更 塑室坚皇兰堕堡主堕塞 多的带宽。 一有效带宽和排队队长的衰减速率的反函数匹配的很好。因而，有效带宽 能够用来表征队长的衰减速率。 本文得出的有效带宽的收敛性比y a n g s 的好。原因是本文推导出的有 效带宽是多项式，面y a n g s 是指数函数。 l i i i zc o m p 啦de 盛矧i v eb a n d w i d t h 5 口( 口) = o 2 + 2 5 口 2 口( 护) = 0 5 + 3 8 阳 l 4 徊) = 1 + 0 鲴 表2 1 计算出来的有效带宽 嘶y r t eo f t 翻曲协l 帅o f t 怕q 岜* l 叽曩h 图2 4 排队队长的衰减速率和有效带宽图 壹室塑皇兰堕堡主丝苎 图2 - 5 网络资源利用率和丢包率图 南京邮电学院硕士论文 3 1c a c 基础 3 1 1c a c 的定义 第三章m b a c 算法介绍 按照i t u t 和a t m 论坛的定义，c a c 是网络在新连接申请建立的时刻， 根据新连接的业务特性( 用流量参数表征) 、服务质量要求和网络资源( 带 宽，缓冲区) 的当前状况对是否接纳此连接申请作出判断。只有当网络中 有足够资源来保证蓊连接的q o s 要求，并且网络中其他连接的q o s 不会因 为它的接入而受到损害时，新连接申请才被接纳；否则被拒绝。c a c 要同 时实现两个目标；1 ) 保障所有连接的q o s ；2 ) 有效地提高网络资源利用 率，即在用户需求和网络效益最大化之间取得良好的折衷。 3 1 2c a c 的组成 c a c 的组成部分如下图： 圈3 1c a c 的组成图 在这里，主要描述一下接纳控制方案的三个基本部件：流量描述器， 测量过程和接入准则。图3 1 描述了三个部件的关系，从图中可以看出， c a c 以流量描述器或测量过程获得的参数作为输入，根据接入准则，接纳控 制单元判断是否能接入一个新的请求流，如果能，就接纳新流，否则就拒 绝。 流量描述器 流量描述器是表征信息源特征参数的集合。一个典型的流量描述器是 南京邮电学院硕士论文 令牌捕，它由令牌产生速率r 和令牌桶大小b 组成，由令牌桶描述器表示 盼源在任何时阔佩隔t 最多发送件t + b 个信息，有时一个令牌桶含有峰值 速率p ，它表示最小分组到达间隔是坛。任何情况下，流量描述器允许流 向接纳控制提交它的使用要求。 测量过程 一个接纳算法通常需要几个参数作为输入。一个经常使用的参数是聚 合流的平均到达速率。如果我们假定源可以用流量描述器精确表征它们的 流，接纳单元可以简单地使用流量描述器的参数。然而，实时应用流的特 征很难用流量描述器表征而且令牌桶参数只能提供一个非常宽松的速率边 界。当实际的流突发时，如果按纳控制只是基于呼叫建立阶段的参数，网 络利用率将会非常低。因此，接纳控制单元应该监视网络的动态性，并且 使用测量如网络瞬间负荷和分组延迟作出它的接纳决策。使用测量获得的 参数作为输入的c a c 算法称为班i a c 。 接入准则 接入准则是接纳控制方案用于判断是否接纳一个新请求流的准则。因 为分配给每一优先级类的资源是被所有此优先级的流所共享，接纳一个新 请求流豹决策不仅会影响具有相同优先级的流，也会对优先级较低的流产 生影响。因此，接纳控制决策通常是基于新流的接入对其他流的影响和网 络目标利用率所作出的。 3 2 m b a c 基础 3 2 1 m b a e 的定义 传统的c a c 算法使用流的参数计算最差情况下流的行为，它适用于对 服务有严格要求的可担保服务，不能容许任何q o s 冲突。网络中存在着许 多对服务要求不严格的实时业务，如视频点播等。如果使用传统c a c 会导 致网络豹低利用率，因此提出】i i a c 算法。m b a e 是通过对每个业务流或聚 合流的测量获得流的特征，只要求用户提供新请求流的参数。当新的流发 出接入请求时，m b a c 根据铡量获得的参数和新请求流的参数，判断系统是 壹室堂皇兰堕堡主堡奎一 否有足够的资源满足流的q o s 要求，流的接入是否会影响其他已接入流的 q o s ，只有这两个条件都得到满足，m b a c 才会按纳新的流。从图3 2 也可以 看出，m b a c 算法对用户的要求非常简单，只要求用户提供流的峰值速率。 卜、i l 、 抑_ o_ 、 晨 j 一j - _ - 一 jf l 图3 2 3 2 2m b a c 的优缺点 与传统的接纳控制算法相比，m b a c 算法有以下几个优点： a 对用户要求小。传统的接纳控制算法要求用户提供流的特征参数。 由于网络上各种应用流到达的随机性，多种流汇聚后的流量特性也难以描 述，因而难以构造其流量特征。并且宽带网业务的多样性使得寻求一种精 庳刻划业务特征的方法越来越困难。她a c 通过对网络负荷的实时测量获得 流的特征参数。以此作为接纳依据。只要求新的请求流提供它的特征参数， 舡使参数不精确，对她a c 算法的影响也不大。 b 利用率高。传统的c a c 使用流的特征参数计算流在最差情况下的行 为。当流变的突发时，使用这个方法会导致低的网络利用率。m b a c 算法使 用测量估计流的特征，可以避免这个问题。 c 使用范围广。传统的按纳控制算法常常是基于预知或简化的应用流 量模型，如把应用流的到达都视为泊松过程并假设它们是服从独立分布的， 南京邮电学院硕士论文 有些接纳控制算法仅仅是适合与某些特定分布的应用系统，如果把这些算 法应用于因特网，则无疑会面临严峻挑战。事实上除了t e l n e t 连接和f t p 会话流以外，太部分应用流，如f t p 数据流、w 脚连接以及视频流和音频流 鼯具有长相似性( l r d ) ，它们并不符合泊松分布。 b a c 克服了这个确定， 它无需预知应用流量模型，适用于任意一种应用流。 因为源的行为不是静态的，基于测量的方法不能提供完全可靠的服务。 驵b a c 只能用于能忍受偶然q o s 冲突的c l s 。而且她a c 只有在统计复用高的 时候才可以提高利用率。 b 2 3m b a c 的组成 m b a c 由测量过程和接纳控制算法组成。测量过程描述了如何测量和测 量什么，通过测量估计单流或聚合流的参数。常用的测量机制有时间窗口 测量，点测量和指数平均测量。接纳控制准则以用户的q o s 要求、测量获 得的估计参数和新请求流的参数作为输入，判断是否接纳这个新请求流。 下面详细介绍这两个组成部分。 3 3m b a c 的测量机制 在本节，将介绍三种测量机制：时间窗测量机制“、点测量机制和指数 平均测量机制。这三种测量方法都可以用来测量链路平均负荷、分组平均 延迟和其他的统计值。在这里，我们以网络负荷为例来描述这三个测量方 法。 3 3 1时间窗测量 b 3 1 1 测量过程 时间窗测量是指通过测量周期性的更新估计负荷。估计负荷是当前网 络负荷的估计值，用于接纳控制算法。时间窗测量包括两个参数：泓量窗 长度和抽样周期a 测量窗长度包含若干个抽样周期。在每个测量窗开始时， 把估计负荷置为上一个测量窗口内包含的所有抽样周期中平均负荷最大的 那个抽样值a 如果在某个抽样周期内，新计算出来的平均负荷大于当前估 堕室塑皇堂堕堡主丝苎 一 计负荷，则在下个抽样周期，用此平均负荷更新估计负荷。一旦某个新流 被接纳，估计负荷按照新流所通告的参数增加，同时重新启动测量窗，开 始下一测量窗的测量。 图3 3 显示了如何通过时间窗测量估计负荷。图中横轴表示时间，纵 触表示平均速率。图中的曲线是网络的实际负荷，黑点表示在每个抽样周 期对网络实际负荷的抽样值。横向的虚线表示估计负荷，是上一测量窗口 中的最大抽样值，横向的直线表示当前测量窗中最大的平均速率。t 表示测 量窗长度，s 表示抽样周期。 卜、一o ；一k 一 十撕的一 图3 3使用时间窗测量机制测量负荷 3 3 1 2 参数分析 时间窗长度t 是时间窗测量的一个关键参数，它的大小反映了算法对 历史记忆的长度。由于在每个时间窗口开始时总是把估计负荷的值置为前 一窗口所有抽样周期中平均负荷的最大值，测量不能及时地反应网络的实 际负荷。如图3 3 中所示，在t 1 测量窗口内实际负荷始终小于估计负荷， 但直到一个测量窗口结束时估计负荷才被修改。显然t 越小，通过测量估 计所获得的负荷曲线和网络实际负荷曲线拟合得越好，越能适应负荷的动 态变化，资源利用率越高，接纳的流数目也越多，但可能导致q o s 降低：t 越大，接纳算法越保守，资源利用率越低，但q o s 容易得到满足所以选择 合适大小的t 是非常重要的。 乎坶- 曩奉 另一个参数s 是抽样周期，它对测量的精度也有很大的影响。s 反映了 测量对网络负荷变化的敏感程度，s 越小，测量负