（无线电物理专业论文）一种网络数据流的动态资源分配算法.pdf

一种网络数据流的动态资源分配算法 专业： 硕士生： 指导老师： 无线电物理 余丹娴 余顺争教授 摘要 在支持多种服务类型的计算机网络中，如何保证各种数据流的服务质量 ( q o s ) 一直是一个热门的研究题目，而队列调度算法是其中进行拥塞控制的重 要组件。综合分析多种队列调度算法，差额加权循环( d w r r ) 算法具有突出的 优势，得到广泛应用。但是d w r r 算法缺乏估计数据流所需带宽的机制，且不 能保证时延抖动，不适合应用于实时性数据流。有效带宽( e f f e c t i v eb a n d w i d t h ) 概念是一种根据流量特征和q o s 要求计算所需带宽的策略，可以作为d w r r 的 有效补充。 针对d w r r 算法的不足，本文结合有效带宽概念和d w r r 算法提出了一种 网络数据流的动态资源分配( a d a p t i v e e f f e c t i v e b a n d w i d t h a l l o c a t i o n , a e b a ) 算 法。该算法利用有效带宽算法估计数据流所需带宽，实时监控数据流的时延与丢 包率，并根据q o s 要求动态调整带宽分配和d w r r 各队列的配额分配，从而控 制时延抖动。本文通过o p n e t 进行仿真，与单纯采用d w r r 算法相比较，以 证明该算法的有效性。 关键词：q o s 队列调度d w r r 有效带宽动态资源分配 中山大学硕士学位论文 a n a d a p t i v er e s o u r c ea l l o c a t i o na l g o r i t h m f o rn e t w o r kt r a f i l e m a j o r ： n a m e ： r a d i o p h y s i c s d a n x i a ns h e s u p e r v i s o r ： p r o f e s s o rs h u n z h e n gy u a b s t r a c t t ol o v i d eg l m r a n t e e dq u a l i t yo fs e r v i c e ( q o s ) h a sb e e nap o p u l a rt o p i ci n d i 腮e r vn e t w o r k q u e u es c h e d u l i n gd i s c i p l i n e sa r ei m p o r t a n tc o m p o n e n t st oa v o i d n e t w o r kc o n g e s t i o n c o m p a r e dw i t i io t h e ra l g o r i t h m s d y n a m i cw e i g h t e dr o u n dr o b i n w r r ) s c h e d u l i n gi sm o l ea d v a n t a g e o u sa n dw i d e l ya c c e p t e d b u td w r r l a c k st h e m e c h a n i s mt oe s t i m a t eh o wm u c hb a n d 、v i d t hi sn e e d e db yt h en e t w o r kt r a f f i ca n di t m a ya l s oe , a u s eg r e a td e l a yj i t t e r t h ec o n c e p to fe f f e c t i v eb a n d w i d t h i su s e dt o c a l c u l a t et h en e e d e db a n d w i d t ha n dc o u l db eas u p p l e m e n tt od w r r i no r d e rt os o l v et h el i m i t a t i o no fd w r r , w ep r o p o s ead y n a m i cr e s o u r c e a l l o c a t i o na l g o r i t h mc a l l e da d a p t i v ee f f e c t i v eb a n d 谢d t ha l l o c a t i o n ( a e b a ) ，w h i c h c o m b i n e sd w r ra n de f f e c t i v eb a n d w i d t hc o n c e p tt op r o v i d eb e t t e rq o s i tc h e c k s d e l a ya n dp a c k e tl o s sr a t i oo ft h en e t w o r ka n dd y n a m i c a l l ya d j u s t st h ea l l o c a t e d b a n d w i d t ho fd i f f e r e n tt r a f f i ci na c c o r dw i t ht h eq o sr e q u i r e m e n t s i m u l a t i o nr e s u l t s w i t h0 p n e td e m o n s t r a t et h a to u rm e t h o di sb e t t e rt h a nt h eu s eo f d w r ro n l y k e yw o r d s ：q o s ，q u e u es c h e d u l i n gd i s c i p l i n e s ，d w r r , e f f e c t i v eb a n d w i d t h , d y n a m i cr e s o u r c ea l l o c a t i o n “ 第2 章 1 1 论文选题背景和意义 第1 章绪论 在支持多种服务类型的计算机网络中，如何保证各种数据流的服务质量 ( q o s ) 一直是一个热门的研究题目。网络资源的分配与调度是其中很有挑战性 的方面，各种调度算法都努力在复杂度、公平性、有效性和资源利用率之间取得 平衡。一系列的队列调度算法：先进先出队列( f i f o ) 、优先级队列( p q ) 、公 平队列( f q ) 、加权公平队列( w f q ) 、加权循环队列( w e i g h t e dr o u n dr o b i n , w r r ) 、差额加权循环队列( d w r r ) 等，都试图解决资源分配问题。采取何种 算法，必须考虑以下要求：是否实现带宽在不同业务类型的流量中的公平分配； 是否满足不同流量的q o s 要求，如丢包率、数据包时延等：是否保证充分合理 地利用带宽资源。 d w r r 队列调度算法与其他算法相比，具有算法简单，计算复杂度低，容 易在硬件设备上实现等优点。d w r r 算法调度时考虑到分组的大小问题，各个 队列可真正得到和权重相当的带宽，提供良好的公平性，能较好保证数据流的 q o s 要求，得到了广泛的应用。但是，d w r r 本身不能有效估计数据流所需资 源。并且，它虽然能保证数据流的低时延要求，但却可能造成较大的时延抖动， 不适合实时性数据流，因此需要进一步的改进。 根据已知的网络资源，逼近计算出数据流达到一定q o s 要求所需的带宽一 一有效带宽( e f f e c t i v eb a n d w i d t h ，e b ) 这个概念在1 9 8 8 年首次提出后f i j ，便吸 引了大量学者的研究。有效带宽能够衡量网络资源的多少，提供接入控制 ( c o n n e c t i o na d m i s s i o nc o n t r o l ，c a c ) 、资源分配等，保证数据流q o s 要求， 应用广泛。结合有效带宽与队列调度算法，为实时进行数据流资源分配和调度提 供了有效的途径。因此，本文结合有效带宽概念和d w r r 队列调度算法，提出 了一种网络数据流的动态资源分配( a d a p t i v ee f f e c t i v eb a n d w i d t ha l l o c a t i o n , a e b a ) 算法，以满足不同数据流的q o s 要求。 中山大学硕士学位论文 1 2 论文主要工作 本论文针对现有队歹旷调度算法的不足以及有效带宽概念的应用，提出了一种 网络数据流的动态资源分配算法。该算法能较好保证各种不同数据流的时延、丢 包率、时延抖动等q o s 要求，并尽量提高带宽资源的利用率。 本论文采取o p n e t 建模并仿真，考虑多种流量类型，设计多种不同的数据 流统计复用场景，对有效带宽算法的有效性进行了验证，为a e b a 算法提供了 可靠的理论依据。并搭建了一个具有多种不同服务类型的网络，采取a e b a 算 法对数据流进行处理，比较单纯采用d w r r 队列调度算法与采用a e b a 算法后 的性能改善，证明a e b a 算法的有效性。 1 3 论文架构 本文共分为六章。第1 章为绪论部分，介绍了论文选题的背景和意义，概述 了论文的主要工作；第2 章介绍了区分服务体系的队列调度机制，并指出现有 d w r r 算法的不足；第3 章介绍了有效带宽概念的原理和两种主要算法，并用 o p n e t 仿真多个场景，证明流模型法计算有效带宽的有效性；第4 章结合有效 带宽概念和d w r r 队列调度算法，提出了一种数据流的动态资源分配算法；第 5 章使用o p n e t 对算法进行仿真实验，并分析实验结果；第6 章对全文进行了 总结，并对后续工作进行展望。 2 第2 章 第2 章区分服务体系的队列调度机制 随着计算机网络不断发展，产生了大量实时性要求较高的应用，如i p 语音 和i p 视频会议等。同时，为所有不同类型的数据流提供可预测的服务层次，保 证服务质量( q o s ) 已成为网络管理人员的重要任务。实现可预测的区别服务层 次，是保证所有的应用数据流可依据各自所提供的功能获得所需要的服务层次的 关键。所以，要善用网络上的各项资源，以满足网络上的各项服务要求是网络发 展的重点。 2 1q o s 的定义 q o s 可从多个不同的途径来定义，从技术角度而言，q o s 是网络中管理数据 流的可用带宽、延迟、抖动以及分组丢弃等的技术集合。所有的q o s 机制的目 的就是影响这4 个特征中的至少一个，某些情况下甚至是全部【2 】。 1 带宽 带宽自身的定义是在特定的网络介质或者协议中额定的吞吐量。由于q o s 并不能对任何给定链路的实际容量产生影响，因此在q o s 中带宽特指带宽的分 配。换言之，没有一种q o s 机制可以产生额外的带宽，但q o s 机制使管理员能 更有效地利用现有带宽。 2 时延 在q o s 中时延有几个方面，处理时延( p r o c e s s i n gd e l a y ) 指从设备接收了数 据帧到该帧由目的端! e l 转发出去的时间间隔，串行时延( s e r i a l i z a t i o nd e l a y ) 指 实际传输一个分组或数据帧所需的时间，端对端时延( e n d - t o - e n dd e l a y ) 指分组 从源端发送到达目的端的总时延。 3 时延抖动 时延抖动是分组间到达和离开时的差异，也就是不同分组之间在时延上的偏 差。 3 中山大学硕士学位论文 4 分组丢失 分组丢弃( p a c k e tl o s s ) 仅指沿转发路径所产生的分组丢失，导致分组丢失 的原因很多，比如缓冲器拥塞、线路出错、甚至q o s 机制本身也会有意地丢弃 分组。 另一种更实用的q o s 定义是管理不公平，即用特定的策略来决定哪些数据 流可以享受优先服务。在q o s 中，管理不公平是十分重要的，因为网络必须为 每一种应用提供不同层次的服务，有时必须为某一应用分配比其他应用更多的带 宽。 2 2 区分服务体系 有两种主要的q o s 体系模型，由i e t f 分别在1 9 9 4 年和1 9 9 8 年提出了综合 服务( i n t e g r a t e ds e r v i c e ，i n t s c r v ) 体系t 3 1 , o 区分服务( d i f f e r e n t i a t e ds e r v i c e ， d i f f s e r v ) 体系m 。 d i t t s e r v 体系的基本单位为网络上的一个节点，这些节点分为边界节点和内 部节点。边界节点根据用户的规定将进入网络的单流分类、整形、聚合为不同的 流聚集，这种聚集信息存储在每个i p 包头的d s 标记域中，称为d s 标记( d s c p ) 。 内部节点根据d s c p 选择特定质量的调度转发服务。d i f f s e r v 简化了网络内部节 点鲍服务机制，在内部节点只需进行简单的调度转发，而流状态信息的保存与流 监控的实现等只在边界节点进行，内部节点是状态无关的。因此，d i f f s e r v 十分 易于扩展，适合在大型网络中使用。 数据流在进入d i f f s e r v 边界节点时，必须进行分类，网络内部节点根据数据 包的d s c p 来给予不同的p h b ( p e rh o pb e h a v i o r ) d i 。p h b 是某一个节点对特 定聚集行为的传送描述。也就是数据包传送方式的设定。目前，i e t f 定义了三 种类型的p h b ：d e f a u l t ( b e s te f f o r t ) 、e f ( e x p e d i t e df o r w a r d i n g ) 7 1a f ( a s s u r e d f o r w a r d i n g ) 【9 1 。 4 1 b e s t e f f o n 第2 章 这是最基本的一种等级。在网络发生拥塞时，这种等级的数据包只能尽力送 出，没有q o s 保证，所以数据包的时延，丢失率、时延抖动都会比较大。 2 e f e f 等级是d i f f s e r v 体系中拥有最低时延、最低丢失率、最低时延抖动的一 种等级，通常会使用高优先级的队列进行调度。 3 a f a f 在预设中分为四种等级，每个等级有三种不同的丢弃优先权，四种等级 可能拥有不同数量的资源，在节点发生拥塞时，会根据数据包的丢弃优先权对其 进行相应的丢弃处理。 为了区别e f 、a f 、b e 的p h b ，i e t f 在r f c 2 4 7 4 t g ! 中定义了d s c p ，总共 有6 b i t 大小，以这六位来代表不同的p h b 。表2 1 列出了已定义的d s c p 值。 e fa f b e 丢弃优先权 低 由 高 d s c p1 0 1 l l oa f l 0 0 l o l 0 0 0 1 1 0 00 0 l l l 0o o o 0 0 0 a f 2 0 1 0 0 i o0 1 0 1 0 0o l o l l o a f 3 0 1 1 0 1 0o l i l o o0 l l i l o a f 4 1 0 0 0 l o1 0 0 1 0 0l o o l l 0 2 3 队列调度机制 表2 - ii e t f 己定义的d s c p 值 d i f f s e r v 网络由不同的组件对基于类别的流进行整形、拥塞控制和拥塞避免， 其中队列调度算法是进行拥塞控制的重要组件。在网络中面临的一个重要问题是 如何对有限的共享资源( 缓冲区大小、带宽等) 进行合理分配。队列调度算法通 过选择当前被服务的数据包，使得某一类数据流可以获得资源。各种调度算法都 5 中山大学硕士学位论文 努力在复杂度、公平性、有效性和资源利用率之闻取得平衡f l o l 。当网络发生拥塞 时，将会增加端到端的时延，引起时延抖动，并增大丢包率，因此，采取有效的 手段减少拥塞非常重要。常用的队歹| j 调度策略，是在有限的网络资源( 缓冲区大 小、带宽等 下，实现合理的带宽分配。队列调度算法必须满足： 1 ) 公平分配。所谓公平分配，指的是能够按照数据流的需求，分配相应的 带宽。伪如，有些数据流比其它流需要更多的带宽，可以通过给它分配更高的优 先级来实现。 2 ) 对不同类型的流进行保护，即避免不正常业务类型的流对其他数据流的 影响，在某些业务类型表现不正常的时候，保证其他业务类型仍然得到正常的服 务。 3 合理地共享带宽，就是将分配给一种业务类型的剩余带宽，给其它业务 类型共享。 4 算法必须是硬件可实现的，才能快速地调度数据流。 现有的常用队列调度策略有：f i f o ( 先进先出) 、p q ( 优先级队列) 、f q ( 公平队列) 、w v o ( 加权公平队对) 、加权循环( w e i g h t e dr o u n dr o b i n , w r r ) 、 差额加权循环( d w r r ) 等。 1 先进先出( f i r s ti nf i r s to u t ，f i f o ) f i f o 是一种最基本的队列调度策略。f i f o 按照数据包的到达顺序入队，又 按照这个顺序对每个包进行无区别的服务，如图2 - 1 所示。 6 匿2 - 1f i f o 队列调度算法 第2 章 f i f o 相比其它队列调度机制，其算法异常简单，并且它调度数据包的顺序 完全可以预测，所有的数据包都不会被重新排序。算法本身不会给数据流增加明 显的时延，最大的时延取决于队列的缓冲区大小。但每个包都被无差别地对待， 先来先服务，因此不支持区分服务，难以保证一些特殊业务类型的服务要求。 2 优先级队列( p r i o r i t yq u e u e ，p q ) p q “l 】提供了支持不同优先级队列的相对简单的算法。它把数据包分到不同 优先级队列中。低优先级队列必须等到高优先级队列为空时，才能被调度，同一 优先级队列中的数据包按照f i f o 的顺序进行调度，如图2 2 所示。其特点是关 键的业务可以得到保证。其缺点是在高优先级队列流量较大的情况下，较低优先 级的队列会长时间的处于饥饿状态，甚至被丢弃。 图2 - 2 l q 队列调度算法 3 公平队列( f a i rq u e a e ，f q ) f q u 2 j 由j o h l ln a g l e 在1 9 8 7 年首次提出。f q 提出的目的是保证所有数据流 都能公平获得网络资源。它把不同的数据流分配到不同的队列中，然后对各个队 列循环服务，每一队列在一次循环中只传送一个数据包，如图2 3 所示。f q 也 称为基于流的队列调度( f l o w - b a s e dq u e u i n g ) ，其特点是防止突发流对网络资源 的强占，使各个队列享有完全相同的输出带宽。它缺点是当一个队列中的数据包 长度明显大于其他队列中的数据包时，这个队列就会占有比其他队列更多的带 宽，所以它并不能真正实现带宽的公平分配。并且，它也不能根据不同数据流的 优先级分配不同的带宽资源，不能满足实时性数据流的要求。 7 中山大学硕士学位论文 图2 - 3 f q 队，口调度算法 4 加权公平队列( w e i g h t e df a i rq u e u e ，w f q ) w f q 1 j 是f q 的一种改进。w f q 被称为公平的，因为它调度时考虑了队列 的长度。从理论上讲，它可以看作按比特为单位不断循环调度，如图2 - 4 所示。 比如队歹i j 一与队列二的长度之比是2 ：l ，则w f q 每次循环从队列一调度两个比 特，而从队列二调度一个比特。实际应用上不能这样实现。w f q 根据这种思想， 按照端口速率、队列数量、数据包长度等计算出数据包调度完成的时间，然后最 先调度最早完成的数据包。w f q 还可以通过给各个队列分配不同的权重来满足 不同业务对于带宽的不同要求。但是w f q 的计算复杂度高，必须保存大量有关 数据流状态的数据，并且必须反复记录数据包的至达与发送情况。w f q 的高复 杂度使得它只能支持少量不同类型的数据流，可扩展性差，而且它的计算开销也 会增加很多不必要的时延。 8 图2 4 w f q 队，b 调度算法 第2 章 5 加权循环( w e i g h t e dr o u n dr o b i n ，w r r ) w r r i 算法是对p q 、f q 的改进，它也被称为基于类别的队列调度 ( c l a s s b a s e dq u e u i n g ) 。针对f q 的不足，w r r 为每种业务类型分配不同的优先 级。高优先级队列每次循环可以调度多于一个的数据包。针对p q 的不足，在 w r r 次循环当中，每个队列至少可以发送一个数据包。w r r 把数据流分类到 不同的队列中，每次循环时，w r r 访问各个队列的次数的比例与所分配带宽的 比例相同，如图2 5 所示。它的缺点是当一个队列中的数据包明显大于其他队列 中的数据包时，它仍然不能真正实现带宽的公平分配。 图2 - 5 w r r 队列调度算法 6 差额加权循环( d e f i c i tw e i g h t e dr o u n dr o b i n d w r r ) d w r r 1 5 l 是由m s h r e e d h a r 和1 2 v a r g h e s e 在1 9 9 5 年提出的，它克服了w f q 和w r r 的局限性。针对w f q 的不足，d w r r 定义了一种简单的计算方法，大 大降低计算复杂度。针对w r r 的不足，d w r r 考虑了数据包的长度，按照需要 精确分配各个队列可以使用的带宽资源。 d w r r 用赤字计数器( d e f i c i t c o u n t e r ) 表示当前队列可以被发送的数据量。 每次调度一个队列时，一定的配额( q u a n t u m ) 被加到当前d e f i c i t c o u n t e r 上， 然后发送不超过d e f i c i t c o u n t e r 大小的数据包并减去相应的已传输的包长度，如 图2 - 6 所示。q l l a n t i 蛐根据队列的权重来设置。d w r r 算法简单，计算复杂度低， 容易在硬件设备上实现，支持高速网络；调度时考虑到分组的大小问题，各个队 列可真正得到和权重相当的带宽。d w r r 具有算法简单、提供良好的公平性、 各队列间互不影响、可按需要给各个队列分配不同带宽等优点，得到了广泛的应 9 中山大学颐士学位论文 用。 图2 - 6d w r r 队列调度算法 2 3d w r r 队歹i j 调度算法的改进研究 综上所述，d w r r 算法提供了良好的公平性，且算法简单，容易实现，因此 得到广泛的应用。但d w r r 存在以下问题 i 6 - i - ： 1 d w r r 解决的是如何调度不同服务质量的数据包，在已知各个队列所需 资源比例的情况下，d w r r 可以通过设置各个队列的q i j a n t u n l 值从而为其分配 相应的带宽资源。但是d w r r 算法本身不能估计数据流所需带宽，不能有效进 行带宽分配。即对于各种不同类型的数据流，缺乏一种机制，可以有效衡量d w r r 每一轮调度过程中，不同的队列应该分配多少的q u a n t u m 值。 2 d w r r 可以很好控制各个队列的时延，但对于时延抖动却没有保证。然 而网络中的一些数据流，比如实时性的媒体流和语音流，尽管时延是一个重要的 服务质量要求，但并不是越快把数据包传送出去越好，而是要在一定的时延范围 中传送，太大的时延抖动将影响这种数据流的服务质量。考虑最坏的情况，假设 有n 个队列，队列i 刚刚被服务过，新的一轮调度刚刚开始，每个队列都增加了 相应的q u a n t 啪值，并且每个队列都有数据包需要调度，且所需要调度的数据 包总长度都超过了相应的d c f i c i t c o u n t c r 值，于是队列i 必须等待其他n - 1 个队 列调度结束才能再一次得到服务。也就是说，在最坏的情况下，队列i 必须等待 1 0 第2 章 一i ( d e f i c i t c o u n t e r j + q u a n t u m 。) 字节的数据包调度完毕后才能再一次被调度，此 时时延抖动将非常大。 解决以上问题，一是引进一种数据流所需带宽资源的估计机制，二是动态调 整各个队列的q u a n t u m 值，从而控制每一轮调度的时间间隔和队列的实际长度， 达到控制时延抖动的目的。本文将结合有效带宽( e f f e c t i v eb a n d w i d t h ) 的概念， 提出一种网络数据流的动态资源分配算法。 中山大学硕士学位论文 第3 章有效带宽的概念与分析 3 1 有效带宽的原理 有效带宽【l l 概念提出以来，吸引了很多学者的研究。提出“有效带宽”概念 的目的是：将它作为描述通信业务对网络资源需求的统的准确的表达；根据已 知的链路容量、缓冲队列闽值，逼近计算出队列小于期望的丢包率，或者是排队 延迟低于截止期限时所需的带宽需求。所谓“有效”，是指该有限的容量可以在 一定程度上保证系统的性能。 有效带宽的理论值是一个介于数据流峰值速率与平均速率之间的数值。有效 带宽的计算基于以下条件：假设一定的已知参数，如缓冲区大小b 、链路容量c 等，通过一种机锚可以预测各种数据流所需的带宽口。，使得各种数据流满足特 定丢包率小于占的q o s 要求，即p q u e u el e n g t h 研占，且口n j 特尉适合于通信网络和信息系统的结构化模块：o p n e t 提供了各种通信 网络和信息系统的处理构件和模块，如t c p 模块、a t m 模块等，用户可以直接 调用这些模块。 3 ) 图形化：o p n e t 采用图形化界面建模，为使用者提供三层( 两络层、节 点层、进程层) 建模机制来描述现实的系统，o p n e tm o d e l e r 的几个编辑器提 供了用户编辑模型及o p n e t 本身内置模型的直观化模型，并且提供了丰富的编 程函数供用户调用。 4 ) 有限状态机f s m ( f i n i t es t a t em a c h i n e ) ：在过程层次中使用有限状态机 来对其它协议和过程进行建模，用户模型及o p n e t 内置模型将会自动生成用c 语言实现、可执行的高效、高离散事件的模拟流程。 5 ) 强大的统计性和集成分析功能：o p n e t 内建了很多性能统计器，它会自 动采集模拟过程的结果数据，回时o p n e t 也允许用户自定义程序来增强这些统 计器的性能。并且对这些采集的数据进行大量的分析，同时以文件和图形的方式 形成输出。 6 ) 系统的完全开放性及应用程序接口( a p i ：o p n e tm o l d e r 中的源代码 全部开放，用户可根据自己的需要添加、修改已有的源代码。其特有的应用程序 接口功能，使它的模型和数据文件可以很容易的被其它工具调用。 7 ) 支持各种业务模型：o p n e t 几乎预定义了所有常用的业务模型，如均匀 分布、泊松分布等，同时还集成了e m a i l 、h t t p 、f t p 、远程终端、电视会议 和数据库等常用的客户一服务器应用业务模式。 3 3 1 2o p n e tm o l d e r o p n e tm o d e l e r 是一种网络技术开发环境，几乎包含了o p n e t 所有其他产 品的功能，凭借其巨大的灵活性，m o d e l e r 广泛的应用于通信网络、设备、协议 和应用的设计及研究。m o d e l e r 为开发人员提供了建模、仿真以及分析的集成环 境，降低了编程以及数据分析的工作量。针对不同的领域，它表现出不同的用途： ( 1 ) 对于企业网的模拟，m o d e l e r 调用已经建好的标准模型组网。在某些 1 6 第3 章 业务达不到服务质量要求的情况下，如网上交易、数据库等业务响应时间慢于正 常情况，m o d e l e r 捕捉重要的流量进行分析，从业务、网络、服务器三方面找瓶 颈。 ( 2 ) 对于比企业网更复杂的i s p 网的模拟，m o d e l e r 焦点放在整个业务层、 流量的模拟，使i s p 有效查出业务配置中产生的错误，例如有哪个服务器配置不 好，容易遭受黑客进攻，哪些业务的参数配置不适合等情况。 ( 3 ) 针对研发的需求，m o d e l e r 提供了一个开放的环境，使用户能够建立 新的协议和配备，并且能够将细节定义并模拟出来。 o p n e tm o l d e r 中提供多种编辑器来帮助用户完成网络建模和仿真运行，包 括以下几个部分： 1 ) 网络编辑器( n e t w o r ke d i t o r ) ：网络编辑器用于编辑网络的拓扑结构， 它具有图形化的编辑界面，并且提供由各种通信实体组成的模型库，如h u b 、路 由器等。用户可以通过简单的拖放操作在网络编辑器的工作区中快速、方便的配 置起自己的网络拓扑，也可以对网络中各种设备的属性进行设置。用户还可以建 立新的模型或在已有模型的基础上进行修改。o p n e t 引入了子网的概念，这里 的子网被视为一个独立的对象，子网内节点的数目和子网中的设备可由用户自行 设定。同时，o p n e t 还支持子网的无限层嵌套。 2 ) 节点编辑器( n o d ee d i t o r ) ：节点编辑器用于定义网络中节点的结构和描 述节点中( 软件或硬件) 模块间的数据流。节点编辑器描述了协议的层次结构， 并通过描述功能模块之间的数据流来实现一个网络器件或系统的体系结构。 3 ) 进程编辑器( p r o c e s se d i t o r ) ：进程编辑器定义了节点内功能模块中各事 件之间的控制流，使用符合工业标准的状态图来描述功能模块内的状态和状态间 的控制流。进程模型在进程编辑器中用p r o t oc 语言描述，p r o t oc 语言是o p n e t 为协议和算法的开发而设计的，它基于状态转换图( s t d ) 的组合，是一个类似 于内核程序( k e r n e lp r o c e d u r e s ) 的高级命令库，同时具有c + + 程序语言的基 本功能。另外，o p n e t 自带4 0 0 多个内核程序( k e r n e lp r o c e d u r e ) ，方便了用 户对协议和算法开发与实现。 4 ) 包格式编辑器( p a c k e tf o r m a te d i t o r ) ：包格式编辑器用于创建用户定义 的各种类型的包。 7 中山大学硕士学位论文 5 ) 探针编辑器( p r o b ee d i t o r ) ：探针编辑器可以收集内置的统计数据，也可 以根据用户的要求收集数据，还可以将统计数据以动画的形式表现出来。 3 3 1 3o p n e t 的建模 o p n e tm o d d c r 提供了三层建模机制，分别在进程层，节点层和网络层进 行由下到上的建模。同时在仿真的过程中它采用了离散事件驱动的模拟机理。 进程模型( p r o c e s sm o d e i ) 的基础是用有限状态机f s m 来描述各种协议。 各个状态再分别进行编程实现。 节点模型( n o d em o d e l ) 由进程模型构成，可以组成完整的协议栈，真实的 反映所建模设备的特性。各模块间通过数据包和状态信息的传递来进行各种操 作，进而实现设备的功能。 网络模型( n e tm o d e l ) 由节点模型组成，可以通过不同的拓扑设计来构造出各种 不同的网络结构。 o p n e t 的建模过程如下： l 了解建模对象 深入理解实际的仿真对象。在a o d v 协议中要深入的了解路由表的处理规 财、队列的处理规则、路由建立和维护的过程等。在建模时还需要对实际的模型 进行一定的简化。目标是要实现协议的行为，因此一些对仿真结果没有影响的内 容可以进行简化或删除。比如对于i p 地址可以简化为一个8 位的整型数字来代 替。 2 ) 确定建模目的 确定要得动的结果和要解决的问题。设定好参数和观察变量，比如若要得到 阿络的时延特性，需要在进程模型中设定观察变量。 3 ) 模型设计 基于f s m 对各个状态进行初始的定义；进行p a c k e t 建模；设定s t a t i s t i c s 定义数据结构；编程实现模型功能。 4 ) 仿真调试 对模型进行测试。修改完善。 5 验证结果 1 8 第3 章 查看结果，验证模型的正确性。 以上各步骤循环进行，直到得到预定的结果。 3 3 1 4o p n e t 的通信仿真机制 o p n e t 采用离散事件驱动( d i s c r e t ee v e n td d v e n ) 的模拟机理，即是说， 只有网络状态发生变化时，模拟机才工作，网络状态不变化的时间段不执行模拟 计算，也就是被跳过。因此，与时间驱动相比，离散事件驱动的模拟机计算效率 得到很大的提高。仿真核心实际上为离散事件驱动的事件调度器( e v e n t s c h e d u l e r ) ，它对所有的进程模块希望完成的事件和计划该事件发生的事件进行 列表和维护。 事件调度器主要维护一个具有优先级的队列，它按照事件发生的时间对其中 的工作排序，并遵循先进先出的顺序执行事件。而各个模块之间的通信主要依靠 传递包的方式来实现。 3 3 2 有效带宽的仿真实验 有效带宽是根据已知的链路容量、缓冲队列阈值，期望丢包率，期望排队时 延而计算出来的数据流所需的带宽需求。本节通过仿真实验，以验证在不同网络 场景下有效带宽的准确性与有效性。 本节考虑多种流量类型，设计多种不同的数据流统计复用场景，分析有效带 宽流模型法在不同网络情况下的适应情况 2 9 - 3 0 l 。流模型法的核心是保证丢包率控 制在期望阔值以下，因此，仿真中分析不同场景的丢包情况，同时也分析数据包 时延。 仿真实验拓扑如图3 2 所示： 图3 - 2 有效带宽仿真实验拓扑 1 9 中山大学硕士学位论文 其中s u b n e t 节点为数据源，在不f 可场景下包含不同的数据流。r o ys t a t i o n 节 点为接收端。q u e u e 节点是路由器，对数据流进行转发。在这个实验中，q u e u e 节点采用了最简单的f i f o 队列诃度算法，即对所有类型的数据包都相同地进行 简单的转发。 1 单一数据流 缓冲区3 m b ，数据包目标丢失率e 5 ，峰值速率= 4 m b ，平均突发时长= l o o m s 。 在单一数据流的情况下，不存在统计复用增益问题，可以直接采取流体模型计算 在不同科用率下的有效带宽，如图3 - 3 图3 - 3 单一数据流的有效带宽 用o p n e t 分别仿真利用率为4 0 和8 0 时的队列性能，两个场景的参数设 置如表3 1 所示。 信源 场景一场景= 目标丢失率 e 5e - 5 流量模型 o n - o f f ( 4 0 )o n - o f f ( 8 0 l o n ：o i so n ：0 1 s o f f ：0 1 s so f f ：0 0 2 5 s 平均速率 1 6 m b s3 2 m b s 计算的有效带宽2 4 m b s 3 3 m b s 下接第2 1 页 13霄辱强懈 第3 章 续上表 场景一场景二 l 数据包到达间隔 e x p o n e n t i a l ( o 0 0 3 s )e x p o n e n t i a l ( o 0 0 3 s ) l 数据包大小 e x p o n e n t i a l ( 1 5 0 0 b )e x p o n e n t i a l ( 1 5 0 0 b ) 表3 - 1 单一数据流的参数设置 仿真结果如图3 - 4 和图3 5 所示。 图3 4 数据包平均时延 图3 - 5 场景二平均丢包率 2 1 中山大学碗士学位论文 场景一平均时延4 6 m s ，没有数据包丢失；场景二平均时延2 8 8 m s ，平均丢 包率小于e 5 。可见在单一数据流下，用流体模型计算的有效带宽保证了队列的 性能要求，并且此时的有效带宽基本接近实际所需的带宽。 2 少数同类型数据流复用 缓冲区3 m b ，数据包目标丢失率e 5 ，5 个同类型数据流，每个流的峰值速 率= 4 0 m b ，平均突发时长= 1 0 m s 。 流体模型和统计复用增益模型计算的有效带宽如图3 - 6 。5 个高速数据流， 复用度不高，因此统计复用增益模型高估了有效带宽。相比而言，流体模型较好 地估计了有效带宽。取e b = m i n c f ，c g 。 图3 - 6 少数哥类型数据流复用的有效带宽 用o p n e t 分别仿真利用率为4 0 和8 0 时的队列性能，参数设置如表3 2 所示。仿真结果如图3 7 所示。 下接第2 3 页 第3 章 续上表 场景一场景二 流量模型 o n o f f ( 4 0 )o n o f f ( 8 0 ) o n ：l o r e s o n ：l o m s 0 f f ：1 5 m s0 f f ：2 5 m s 平均速率1 6 m b s 。5 个数据流 3 2 m b s ，5 个数据流 计算的有效带宽1 2 3 m b s1 6 8 m b s 数据包到达间隔 e x p o n e n t i a l ( o 0 0 0 3 s )e x p o n e n t i a l ( 0 0 0 0 3 s ) 数据包大小 e x p o n e n t m l ( 1 5 0 0 b )e x p o n e n t i a l ( 1 5 0 0 b ) 表3 - 2 少数同类型数据流复用的参数设置 图3 7 数据包平均时延 场景一平均时延3 1 m s ，场景二平均时延1 4 m s 。两个场景都没有数据包丢 失。在这两个场景中，无论是流体模型还是统计复用增益模型都较大地高估了实 际所需带宽。 3 大量同类型数据流复用 缓冲区3 m b ，数据包目标丢失率e 5 ，4 5 个同类型数据流，每个流的峰值速 率= 4 m b ，平均突发时长= l o o m s 。 中山大学硕士学位论文 流体模型和统计复用增益模型计算的有效带宽如图3 8 。此时数据流统计服 用度高，统计复用增益模型比流体模型更好地估计了有效带宽，但在高负载的情 况下，流体模型估计更准确。取e b = m i c f , c g 。 图3 - 8 大量同类型数据流复用的有效带宽 用o p n e t 仿真两个场景。场景一利用率为3 0 ，从上图可见，此时有效带 宽是由统计复用模型计算出来的。场景二利用率为8 0 ，有效带宽由流体模型计 算得出。两个场景的参数设置如表3 3 所示。 信源场景一 场景二 目标丢失率 e - 5e 5 流量模型o n o f f ( 3 0 )o n - o f f ( 8 0 1 o n ：1 0 0 m so n ：l o o m s 0 f f ：2 3 3 m s0 f f ：2 5 m s 平均速率1 2 m b s ，4 5 个数据流3 2 m b s ，4 5 个数据流 计算的有效带宽 9 2 m b s1 5 l m b s 数据包到达间隔 e x p o n e n t i a l ( 0 0 0 3 s ) e x p o n e n t i a l ( 0 0 0 3 s ) 数据包大小 e x p o n e n t i a l ( 1 5 0 0 b )e x p o n e n t i a l ( 1 5 0 0 b ) 表3 3 大量同类型数据流复用的参数设置 第3 章 图3 - 9 数据包平均时延 仿真结果如图3 - 9 所示。场景一平均时延小于l m s ，场景二平均时延约为 1 2 m s 。两个场景都没有数据包丢失。可见有效带宽的算法能够保证队列的性能。 但是，仿真结果优于期望性能，说明它高估了实际所需的带宽大小，造成了带宽 资源的浪费。因此，必须在队列调度算法中对其进行改进，以提高链路带宽利用 率。 4 不同类型数据流( 一) 1 0 个数据流，流峰值速率= l m b ，利用率= 6 0 ，目标丢失率为e - 5 。1 0 个数 据流的平均突发时长分别为o 1 s 、0 2 s 、o 9 s 、l s 。用流体模型计算有效带宽， 则各个数据流的有效带宽从6 3 5 k b 到8 2 3 k b 递增。总体有效带宽为它们的和， 共7 4 m b 。 仿真结果如图3 1 0 所示。 中山大学硕士学位论文 图3 1 0 ( t ) 数据包瞬时时延 图3 i o ( 2 ) 数据包平均时延 由图3 - l o 可见，平均时延小于l m s ，没有丢包。由于l o 个数据流的特征不 同，有效带宽算法只是简单她对个体带宽求和，而忽略了统计复用增益，因此较 大高估了实际所需带宽。 5 不恩类型数据流( 二 这个场景考虑另一种多类型的数据流复用：突发程度相差很大的数据流的复 第3 章 用。l o 个数据流，其中9 个数据流的峰值速率= l m b ，利用率= 1 0 ，平均突发时 长卸1 s 。第l o 个流的峰值速率= 2 0 m b ，利用率= 5 ，平均突发时长= i s 。由于数 据流突发程度大，队列缓冲区设置为1 0 m b ，期望丢失率仍然为e 5 。 可以计算得出：1 , , - 9 个数据流的总体有效带宽为9 9 0 k b ，第l o 个流的有效 带宽是1 9 1