（通信与信息系统专业论文）大容量atm交换机服务质量控制策略及其性能仿真研究.pdf

摘要 a t m 交换机的服务质量( q o s ) 是保证a t m 网络性能的关键之一。本文结合项 目“星上1 0 g b p s 大容量交换原型样机”，重点研究了共享缓存a t m 交换机的q o s 控制策略及性能仿真与评估。 论文简要介绍a t m 交换技术原理、交换结构功能和几种常见的交换结构以 及q o s 相关概念，综述了共享缓存a t m 交换机的q o s 控制策略，主要包括缓存 管理策略、信元丢弃策略、信元调度策略和拥塞控制策略等。在此基础上，详细 研究了基于轮询的信元调度算法，并提出了新型信元调度方案。利用o p n e t 仿 真软件建立了共享缓存a t m 交换机的仿真模型，完成了性能仿真软件的设计， 并对其进行了性能测试。最后重点测试了不同的调度策略对共享缓存a t m 交换 机性能的影响，通过对仿真结果的分析，得到适合于共享缓存a t m 交换机的优 化调度策略。论文工作为保证共享缓存a t m 交换机的q o s 提供了良好基础。 关键词：控制策略服务质量共享缓存a t m 交换机o p n e t 仿真 a b s t r a c t t h eq u a l i t yo fs e r v i c e ( q o s ) f o ra t ms w i t c hi so n eo ft h ek e yf a c t o r st og u a r a n t e e t h ep e r f o r m a n c eo f a t mn e t w o r k s s p o n s o r e db yt h ep r o j e c tn a m e d p r o t o t y p eo f a1 0 g b p sl a r g ec a p a c i t ya t m s w i t c ho n - b o a r d ”，t h ee m p h a s i z e ds t u d yo ft h i sd i s s e r t a t i o n i so nt h eq o sc o n t r o ls t r a t e g i e so fas h a r e d - m e m o r ya t ms w i t c ha n dt h e i r p e r f o r m a n c ee v a l u a t i o nt h r o u g h s i m u l a t i o n s t h i sd i s s e r t a t i o nb r i e f l yi n t r o d u c e st h et h e o r yo fa t m s w i t c h i n gt e c h n o l o g y , t h e f u n c t i o no fa t ms w i t c h i n gs t r u c t u r e ，s e v e r a lc o m m o ns w i t c h i n gs t r u c t u r e sa n d c o n c e p t s r e l a t e dt oq o s i ta l s os u m m a r i z e st h eq o sc o n t r o ls t r a t e g i e so fa s h a r e d m e m o r ya t ms w i t c h ，i n c l u d i n gt h es t r a t e g i e so fb u f f e rm a n a g e ，c e l ld i s c a r d ， c e l ls c h e d u l i n ga n dc o n g e s t i o nc o n t r o l ，e t c a f t e rt h i sb a s i ci n t r o d u c t i o n , t h e d i s s e r t a t i o nd e t a i l e d l ys t u d i e st h er o u n d - r o b i nb a s e dc e l ls c h e d u l i n gs c h e m e ，a n dp u t s f o r w a r dan e wc e l ls c h e d u l i n gs c h e m e w i t l lt h eh e l po ft h eo p n e ts i m u l a t i o n s o f t w a r ed e v e l o p m e n tk i t ( s d k ) ，as i m u l a t i o nm o d e lo fas h a r e d - m e m o r ya t ms w i s h i sb u i l t ，t h ed e s i g na n di m p l e m e n t a t i o no ft h es i m u l a t i o ns o f t w a r eh a sb e e n a c c o m p l i s h e d ，a n dt h ep e r f o r m a n c eo ft h es i m u l a t i o nm o d e lh a sb e e ne v a l u a t e d t h e s i m u l a t i o nw o r kf o c u s e so nt h ei m p a c to fd i f f e r e n tc e l ls c h e d u l i n gs c h e m e so nt h e p e r f o r m a n c eo fa na t ms w i t c h a c c o r d i n g t ot h ea n a l y s i so ft h es i m u l a t i o nr e s u l t s ，t h e m o s ta p p r o p r i a t ec e l ls c h e d u l i n gs c h e m ef o ras h a r e d m e m o r ya t ms w i t c hb e c o m e s a v a i l a b l e t h ew o r ki nt h ed i s s e r t a t i o np r o v i d e saf a v o r a b l ef o u n d a t i o nt og u a r a n t e et h e q o so f as h a r e d m e m o r ya t ms w i t c h k e yw o r d s ：c o n t r o ls t r a t e g i e sq u a l i t yo fs e r v i c e ( q o s ) s h a r e d m e m o r y a t m s w i t c h0 p n e ts i m u l a t i o n 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：二年立峰 日期： 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。 ( 保密的 论文在解密后遵守此规定) 本学位论文属于保密，在上年解密后适用本授权书。 本人签名： 导师签名： 日期塑晕三。址 日期：z ：幽 第一章绪论 第一章绪论 1 1 研究背景和意义 2 0 世纪8 0 年来以后，异步传输模式a t m ( a s y n c h r o n o u st r a n s f e rm o d e ) i l l 于 其技术思想的优势得到了飞速的发展。随后被确立为宽带综合业务数字网b i s d n 的核心技术，是b i s d n 信息复用、传输和交换的基本模式。a t m 交换不同于传 统的交换方式，它结合了传统的电路交换和分组交换的优点，是一种面向连接的 统计复用技术。a t m 技术定义了不同的业务类型，对于不同的业务有合理地处理 方式。它可以适应从低速率到高速率的宽带业务要求，能提供较高的网络性能， 所以在骨干网和接入网上得到了很大的发展。 9 0 年代末，人们对于服务质量是越来越关注。服务质量反映了网络元素主机 或交换机等网络元素在保证信息传输和满足服务要求方面的能力。由于对a t m 网络q o s 的深入研究，已形成了a t m 网络q o s 体系的框架结构。 a t m 交换机是a t m 网络的重要组成部分，其作用主要是存储和转发信元， 它是影响a t m 网络服务质量的关键因素之一。目前，对a t m 交换机q o s 的研究 也较成熟。其q o s 策略主要包括缓存管理策略、信元丢弃策略、信元调度策略、 拥塞控制和选路等。现在学术界对各个部分的研究成果也非常多，对于一个有确 定性能指标的a t m 交换机来说，选用合适的策略将直接影响到a t m 交换机的整 体性能。 a t m 交换机的流量控制对于整个网络的拥塞控制有很大的影响，一般来说， 交换机的流量控制包含两个方面：信元调度和反压控制。 信元调度是实现网络服务质量控制的主要机制之一，主要是针对链路带宽的 合理地分配。在一段时间内，我们根据一定的链路状态信息来控制各个队列对链 路带宽的占用率，从而达到对时延、信元丢失率等性能指标的影响。从网络的角 度来说，不管是a t m 网络或p 网络，人们对于信元调度算法已经有了深入的研 究，产生的算法达到了几十种，通常常见的有基于轮询的算法、基于通用处理器 共享的算法及基于时延的算法等。 反压控制主要是针对a t m 交换机内部缓存区的一种流控方式，当缓存区分散 时，后一级缓存区在存储达到一定数量时，会通知前一级缓存区控制其发送信元 的速率，一般包括证实、许可或部分反压等方式。 本文结合“星上1 0 g b p s 大容量交换原型样机 项目，首先对a t m 交换机的 交换原理、q o s 策略做了详细的学习，接着详细研究了基于轮询的信元调度策略， 2 大容量a t m 交换机服务质量控制策略及其性能仿真研究 提出了一种权值动态更新的方案。然后利用o p n e t 网络仿真软件建立了共享缓 存型a t m 交换机的仿真系统，测试了突发业务下不同的信元调度方案对于交换 机性能的影响，为选择合适的q o s 策略提供了重要的理论参考。 1 2 论文主要研究内容 本文的主要内容安排如下： 第一章首先简要介绍了a t m 的基本情况，结合项目“星上1 0 g b p s 大容量交 换原型样机 阐述了论文的研究背景和意义，并说明了论文的研究内容。 第二章首先叙述了a t m 交换技术的相关内容，主要包括a t m 交换原理、交 换结构功能、分类以及几种常用的交换结构。然后介绍了a t m 技术的发展趋势。 第三章首先叙述了服务质量的相关情况。然后针对共享缓存a t m 交换机，详 细讲述了其q o s 策略，包括缓存管理策略、信元丢弃策略、信元调度策略及拥塞 控制等。 第四章首先详细研究了基于轮询的信元调度算法的现状，并提出了一种改进 的信元调度方案，然后我们以样机原型为例，说明反压控制的实现方式及其特点。 第五章首先对o p n e t 软件和共享缓存a t m 交换机模型的原理做了简单的介 绍，接着详细叙述了仿真模型主要模块的功能，最后对在突发业务情况下几种信 元调度策略对交换机的性能的影响做了简要分析。 第二章a t m 交换原理 第二章a t m 交换原理 a t m 是i t u t ( i 垂i 际电信联盟电信标准化部门，原国际电报电话咨询委员会 c c i t t ) 确定用作宽带综合业务数字网( b r o a d b a n di n t e g r a t e ds e r v i c ed i g i t a l n e t w o r k - - b i s d n ) 的复用、传输和交换的模式。a t m 交换应实现高速、高吞吐 量和高服务质量的信息交换，提供灵活的带宽分配，适应从低速率到高速率的宽 带业务的交换要求。本章我们就详细阐述a t m 交换有关的知识。 2 1a t m 交换的概述 a t m 是以电路交换和分组交换为基础的一种面向连接的分组交换技术。a t m 的信元长5 3 个字节，包括5 个字节的信元头和4 8 个字节的数据域两部分，信元 头里面装载的是控制信息。a t m 交换的过程依靠信元头里的虚通道标识符 v p i ( v i r t u a lp a t hi d e n t i f i e r ) 和虚通路标识符v o ( v i r t u a lc h a n n e li d e n t i f i e r ) 来完成。 v p i 和v c i 的结合构成一个信元的路由信息，因此，我们把它记做v p i v c i 。 除了承载用户信息的普通信元( 一般称为用户信息信元) 外，还有一些特殊用途 的a t m 信元，它们包括： ( 1 ) 指挥交换机动作，例如建立、拆除虚通道、虚信道等等信令的信令信元； ( 2 ) 承载b i s d n 中的运行和维护信息的运行维护信元； ( 3 ) “填充 空闲信道的空闲信元。 因为a t m 信元是定长的，并且在信道空闲时使用空闲信元来进行“填充， 所以事实上可以把信道看作是由一个个等长的时隙构成，每个时隙内都正好装载 一个a t m 信元。这颇类似于同步时分复用话路，而不同于分组交换，因此又称 之为异步时分复用( a s y n c h r o n o u st i m ed i v i s i o nm u l t i p l e x i n g ) 。 与原来的交换技术相比，a t m 交换具有以下特点： ( 1 ) a t m 交换是固定长度的信元交换，信元实际上是很短的分组。采用很短 的信元可以减少交换节点内部的缓冲器容量以及排队时延和时延抖动。信元的长 度固定，则有利于简化交换控制和缓存器管理。 ( 2 ) a t m 使用光纤传输，由于光纤的误码率极低，且容量很大，因此在a t m 网内不必在链路层进行差错控制和流量控制( 放在高层处理) ，因而明显的提高了 信元在网络中的传送速率。 ( 3 ) 网络通过呼叫接入控制来判别是否接纳用户的呼叫请求。如果不能接纳， 则拒绝；如果接纳，则给这个呼叫建立一条从源节点到目的节点的虚信道连接。 这里的“虚 表示只有在真正传送信息时用户才会占用信道资源，即在网络中动 4 大容量a t m 交换机服务质量控制策略及其性能仿真研究 态地为用户分配网络资源。面向连接的特性保证了a t m 网络中每个业务信元发 送和接收的次序一致。接入控制将无法满足的呼叫业务拒绝在网络之外，保证已 建立连接的服务质量。 2 2a t m 交换结构 2 2 1a t m 交换结构的功能与分类 1 a t m 交换结构的功能【1 1 1 a t m 交换结构s f ( s w i t c h i n gf a b r i c ) 是实现a t m 交换的关键技术之一，是 a t m 交换系统中必不可少的重要组成部分。 a t m 交换结构应能够实现任意出入线之间的信元交换，也就是任一入线的任 一逻辑信道的信元要能够被交换到任一出线上的任一逻辑信道中去。为此，a t m 交换结构应具有信头变换、选路和排队这三项基本功能。 ( 1 ) 信头变换 信头变换主要是指v p i v c i 值的变换，即入v p i v c i 变换为出v p i v c i 。 v p i v c i 的变换体现了信元交换的重要概念，意味着入线上某逻辑信道中的信息 被传送到出线上的另一逻辑信道中去。这与数字程控电路交换中的时间交换有些 相似，因为各个逻辑信道的信元也占用着不同的时间位置；但是应该注意到，时 间交换是固定的时隙位置之间的交换。 v p i v c i 的值只在当前的链路上有意义，当进入下一条链路时，它会在适当 的时候重新映射。而且为了实现信头变换，在建立连接时，就生成了翻译表。 ( 2 ) 选路 选路表示任一入线的信息可被交换到任一出线，具有空间交换的特征。信头 变换加上选路功能，才能实现a t m 交换结构的交换功能。这也就是说，在翻译 表中从入线的? i c i 应能查出出线号码以及新的v p i v c i 值。当然，这都是在 建立连接阶段写入的。 选路功能相当于数字交换中的空间交换。当然，数字交换中的空间交换是在 同一内部时隙下的交换，而a t m 交换是异步时分交换，其空间选路功能谈不上 同一时隙的问题。 ( 3 ) 排队 由于是统计复用的异步时分交换，在连接建立后的传送信息阶段，经常会发 生在同一时刻有多个信元争抢公用资源的情况，例如争抢出线或交换结构中的内 部链路。因此，a t m 交换结构需要有排队功能，以免在发生资源争抢时丢失信元。 第二章a t m 交换原理 要实现排队就要有一定数量的缓存器。缓冲器的设霞方式是在a t m 交换结构的 设计中的重要问题，在很大程度上影响到交换结构的性能和复杂性。 除了上述3 项基本功能外，a t m 交换结构通常还应具备多播( m u l t i c a s t ) 功能 和优先级( p r i o r i t y ) 控制功能，以适应带宽业务的多样性。前者是指输入信元可通 过交换结构送到多个目的地，后者是指可以按照各类业务的优先级高低来控制服 务质量，例如当不同优先级的信元在争抢资源时，应该保证优先级高的信元先得 到服务，优先级低的信元在缓存器中等待。 a t m 交换结构应提供良好的性能，以保证所需的服务质量。与服务质量有关 的主要参数是时延、时延抖动和信元丢失率。 在a t m 交换结构的设计中，还有两个重要参数：吞吐率和连接阻塞率。吞 吐率定义为交换结构的每个输出端口平均每个时隙所传送的信元数。每个时隙相 当于在一定传送速率下一个信元的传送时间，因此吞吐率最大为1 。连接阻塞率 表示在连接建立阶段交换结构内部找不到足够的资源来建立新的连接的概率。有 些交换结构内部不会发生连接阻塞。 2 a t m 交换结构的分类 a t m 交换结构可以从不同的方面进行分类，本节主要从时分与空分、单通路 与多通路、单级与多级、阻塞与无阻塞等方面作概念性说明。 ( 1 ) 时分与空分 a t m 交换结构可分为时分与空分两大类，如图2 1 t n 】所示。 时分交换结构 厂_ l 空分交换结构 共享存储器 共享媒体单通路 厂- 总线型环型基于c m s s b 越 基于b a n y 锄 广l 广l 扩展复份b e n e sc l o s b a n y a nb a n y a n 矩阵型全互惩型绂i 中型尤缓冲翌 图2 1a t m 交换结构分类 时分交换结构的基本特征是所有输入和输出端口共享一条高速的信元流通 道，这条被共享的高速通路既可以是共享介质媒体( s h a r e dm e d i u m ) ，也可以是共 享存储器( s h a r e dm e m o r y ) 。整个交换矩阵的交换容量是由这个共享通路的吞吐量 ( 如纵向速度、存储器容量和存取速度等) 所限制。竞争公共资源是时分结构主要 特征之一。 空分交换结构的基本特征是可以在多对输入端口和输出端口之间同时并行地 传送信元，它具有更好的硬件扩展性，可以增加端口而不影响交换机的吞吐量。 6 大容量a t m 交换机服务质量控制策略及其性能仿真研究 空分交换结构按其在任意一对输入输出端口问的路径数可分为单通路和多通路 两大类。 ( 2 ) 单通路与多通路 单通路是指任意一对输入输出端口间只有一条通路，多通路则在任意一对输 入输出端口问有多条通路可以选用，它是针对单通路中网络对突发业务应变能力 差的弱点提出来的，它可以通过增加交换单元的串联级数来达到提高性能的目的。 单通路的两种典型结构称为基于c r o s s b a r 的结构和基于b a n y a n 的结构。c r o s s b a r 的含义为交叉开关型，源于纵横制交换机中纵横接线器( c r o s s b a rs w i t c h ) 的结构， 其特点是交换结构的复杂度( c o m p l e x i t y ) 随着2 而增长，为输入、输出端1 3 数。 c r o s s b a r 结构又分为矩阵型和全互连型，b a n y a n 结构又分为内部缓冲型和内部无 缓冲型，多通路可具有多种结构，如扩展b a n y a n 、c l o s 等等。 ( 3 ) 单级与多级 空分的c r o s s b a r 结构是典型的单级结构，单一的时分交换模块也属于单级结 构。单级交换结构的容量不可能太大，而采用多级结构则可以比较经济的扩大容 量。多级结构通常称为多级互连网络( m u l t i s t a g ei n t e r c o n n e c t i o nn e t w o r k m 咖，由 分为若干级的多个交换单元( s w i t c h i n ge l e m e n t s e ) 以一定的拓扑结构互连而成。 其中，s e 可以是基于c r o s s b a r 的空分结构，也可以是基于共享存储器的时分结构。 m n 在a t m 交换中得到了广泛的应用，大部分商用交换芯片都可以通过级联来 达到预计的吞吐容量。 ( 4 ) 阻塞与无阻塞 面向连接的a t m 交换不仅在连接建立阶段可能产生阻塞，就是在连接被接纳 以后的信元传送阶段也有可能会遇到阻塞。我们把在信元传送阶段中多个信元对 同一公共资源的争抢称为竞争( c o n t e n t i o n ) 或冲突( c o n f l i c t ) 。于是，会出现两种竞 争：内部竞争和输出端口竞争。内部竞争是多个信元争抢交换结构的同一内部链 路或缓冲器，输出端口竞争是多个信元争抢同一输出端口。内部竞争的有无与交 换结构的内部拓扑结构、工作速率等因素有关，如果不存在内部竞争，就称为无 阻塞结构，否则就是有阻塞结构。c r o s s b a r 是典型的无阻塞结构，b a n y a n 网络则 是典型的有阻塞结构。要注意这里定义的无阻塞是指在信元传送阶段没有内部阻 塞。无阻塞结构的性能优于有阻塞结构，但硬件结构较复杂，成本较高。 2 2 2 几种常见的a t m 交换结构 1 共享存储器交换结构 共享存储器结构【1 是指存储器为所有的输入端口和输出端口共用。从各个输 入到达的信元通过复用器被复用成单一的输入信元流而写入共享存储器。实际上， 第二章a t m 交换原理 7 在存储器内部仍可划为若干个逻辑队列，每个队列对应于一个输出端口。因此在 写入时，应按照各个信元的目的端口而控制写入对应的输出队列。在写入的同时， 又按顺序从各个输出队列读出队首的信元而形成输出信元流，经过分路后传送到 各个输出端口。如图2 2 所示。 l 2 n 沁存储器 y 1 l 2 n 图2 2 共享存储器结构 共享存储器结构要有足够高的处理速度，使得处理时间很短，从而能与信元 流的输入速率相适配。处理时间主要是指判定输入信元流中各个信元应编入哪个 输出队列并控制写入的过程。因此，对存储器访问速度的要求比较高。当交换结 构的入线出现数为n ，每线速率为v ，则存储器写入或读出的速度都将取决于n v 。例如说，对于具有w 位宽的存储器，访问时间等于w 2 n v ，如采取双端 口存储器，访问时问的要求可降低为w n v 。可以看出，由于受到存储器访问速 度的限制，交换结构的容量( 端口数及链路速率) 不可能太大。 存储器容量的设计也是一个重要问题。共享存储器应具有一定的容量，使信 元丢失率保持在一定限度以下。存储器容量不但与交换结构容量、流入负荷和业 务流模型有关，而且与存储器的共享方式有关。例如说，可以有完全共享和完全 分离两种方式。完全共享是各个输出队列可以共享整个存储区，只有当整个存储 区占满时才会发生信元丢失。完全分离是将整个存储区划分为n 个区域，每个区 域对应一个输出队列。当某个输出队列已满，则再到达该输出端口的信元将被丢 弃。显然，完全共享方式的存储器的使用效率较高，在相同条件下，存储器的容 量可以减少。但是当出现非均匀业务流时，例如某个或几个输出端口的负荷很高， 会出现整个存储区被少数几个输出端口占有的不公正情况。完全分离方式保证了 对各个输出端口的公正性，但存储器效率不高。一种折衷的方式是划出一部分存 储区作为所有输出端口的共享区。此外，还可以有基于每个端口的最小分配或最 长队列以及队列长度的动态控制等方式。 2 共享媒质交换结构 在共享媒质交换结构中，入线和出线使用共用的传输媒介，在媒介控制器的 控制下完成信元的交换。共享总线和令牌环就是两种常用的共享媒质交换结构。 下面以共享总线结构为例进行说明。共享总线的交换结构如图2 3 1 3 2 】所示。 在共享总线交换结构中，为避免多条入线同时占用总线而引起的总线冲突， 需要有一个总线仲裁单元或者总线控制器，通过它来保证在任一时刻，只能有一 大容量a t m 交换机服务质量控制策略及其性能仿真研究 条入线上的一个信元出现在总线上。而各条出线则通过识别信头中的v p i v c i 来 接收输出到它的信元。 共享总线交换方式结构比较简单，但由于总线的工作速率应为入线速率的n 倍( n 为入线的数量) ，所以在小容量时比较容易实现，但对大容量交换来说，由 于对总线的工作速率要求非常高，实现起来则比较困难。 入 线 出 线 图2 3 共享总线交换 有许多为专用的局域网互联而开发的小容量a t m 交换机都采用共享总线的 交换结构。如f o r es y s t e m s 的a x s 1 0 0 交换机、g t e 的s p a n e t 交换机、c a s c a d e 的b s t d x9 0 0 0 和w e l l f l e e t 交换机，还有m m 的早期实验产品p a r i s 系统以及 后来的p l a n e t 系统。 3 e r o s s b a r 交换结构 c r o s s b a r 交换结构是一种空分的、无阻塞的交换结构，与其他交换结构相比， 具有很高的交换能力。一般c r o s s b a r 的交换结构可以分为矩阵型和全互连型【1 1 1 。 ( 1 ) 矩阵型 n x n 的矩阵具有 产个交叉点，图2 4 给出了两种实现方式，均以4 x 4 为例。 图2 4 ( a ) 中的交叉点是一个2 x 2 的传送门，如图2 5 ( a ) 所示。传送门的2 个输 入可称为横向输入与纵向输入，2 个输出可称为横向输出与纵向输出。从图2 5 ( a ) 可以看出，整个矩阵的输入是位于最左一列的各个传送门的横向输入，矩阵的输 出是位于最下一行的各个传送门的纵向输出。 2 x 2 传送门有2 个状态：b a r 和c r o s s ，见图2 5 ( b ) 、( c ) 。所谓b a r 状态，是指 横向输入连到纵向输出，纵向输入连到横向输出；所谓( ；r o s s 状态，是指横向输 入连接到横向输出，纵向输入连到纵向输出。 第二章a t m 交换原理 9 o l 卣 ，j l ， r 口口 上上 白白吁 - l卜 1 一j 卣 广j l l b j 一 i卜1卜 i ji j 卣 l j 一 广j 、 il - l卜 il ui _ ju l234l 23 4 r o ) ，当高低级信元到达且信元队长不低于t o r , 时，丢弃到达 t l 一 1 吾兀o ( 4 ) “门限+ 推出 法：除了为高、低级信元流分别设置门限r o 、z 之外，还 维持两种信元流各自的虚拟队列。在一个高级信元到达且低级信元队长正时， 以某种推出策略丢弃一个低级信元，反之，则在缓存器己满时丢弃到达的高级信 元。 3 2 3 信元调度 1 调度的概念 信元调度，又称为流控，是实现对链路带宽的管理，是指路由器( 或交换机) 按照某种规则从多个( 或一个) 队列中选择下一次待转发的分组，使得所有的输入 业务流能够按照预定的方式共享输出链路带宽，占有相应的网络资源，满足自己 要求的服务性能。通过调度，我们可以达到以下目标： ( 1 ) 保证每个队列至少享用其预约的带宽。 ( 2 ) 在系统有剩余带宽的情况下，在各队列间公平分享剩余带宽。 ( 3 ) 保证满足各个队列的时延要求。 2 衡量一个调度算法的准则 不论一个调度算法的怎样设计，我认为一个好的调度算法应该满足以下几个 方面的指标： ( 1 ) 低的端到端时延( 1 0 we n d t o e n dd e l a y s ) ：算法必须对每个业务流提供端到 端的时延保证。 ( 2 ) 利用率( u t i l i z a t i o n ) ：算法必须能够提供有效的链路带宽以保证能够传输数 据，尽量避免浪费带宽。 ( 3 ) 公平性( f a i r n e s s ) - 所有队列应该可以公平地享用链路带宽。事实上，这里 讲的公平其实是相对公平的概念。各优先级业务流其是对时延的要求是又区别的， 我们根据其对时延的要求，对其分配相应的带宽，满足其性能要求。 第二章a t m 交换机的服务质量控制策略 2 l ( 4 ) 算法的复杂度：算法的复杂度包括时间复杂度和实现的复杂性。时间复杂 度就是我们用软件实现时其运行的时间，而实现的复杂性是我们用硬件来完成其 功能所耗费的人力、物力等。很多的调度算法依赖于共享输出链路的连接数，因 此，调度算法的简单性直接影响它在高速网络环境中的实现。 然而，以上几个指标本身也是相互制约的，随着现在业务种类的增多，公平 性的要求也越来越高。现阶段，也没有一个算法可以同时兼顾到几个方面，其本 身也是不可实现的。而在现实的使用中，也有将几个好的算法共同使用。我认为， 一个好的算法是在保证各种业务相对公平的情况下，结合现有的硬件和软件设备 尽可能的降低时延和算法的时间复杂度，达到我们的实践要求。 3 2 4 拥塞控制 拥塞控制是a t m 网络传输控制与管理的核心问题。一般来说，当一个链路的 输入信息量大于输出信息量时，就会发生拥塞。拥塞控制的主要功能是在维护对 用户的网络资源公平分配的同时，确保好的吞吐量和时延性能。a t m 交换机作为 网络的重要组成部分，其内部也存在着拥塞，因此，提高它对拥塞的处理能力， 对于提升整个网络的性能是有很大好处的。 由于交换机的有些交换结构的缓存器分设在各处，例如具有内部缓存的多级 网络的每一级都有缓存器，采用输入缓存与输出缓存的单级或多级网络的缓存器 分设在输入端和输出端。对于这些缓存方式的交换结构，信元的丢失不仅可能由 于竞争所致，还可能由于后级缓存器溢f l j ( o v e r f l o w ) 而引起。当然，争抢缓存器也 可以看成是一种竞争。如何对待后级缓存器的溢出，也是控制机理中必须考虑的 问题。 多级缓存的交换结构有两种内部的传送方式：反压控制与排队损失。 所谓反压控$ 1 j ( b a c k p r e s s u r e b p ) ，就是后级应向前级发送表明后级缓存器是否 占满的反向信号，使得前级在后级缓存器占满时不向后级发送信元，信元仍保留 在前级的缓存器中，反压策略降低了信元的丢失率，但控制比较复杂，增加了对 速度的要求。反压控制也就是交换结构内部的流量控制。 排队损失( q u e u el o s s q l ) 是另一种方式，就是不论后级缓存是否占满，前级 总是向后级发送信元，如遇到后级缓存器占满，信元就丢失。 下一章我们以样机原型为例，重点说明反压控制的作用。 第四章流量控制策略及改进研究 第四章流量控制策略及改进研究 a t m 交换机内部的流量控制主要包括了信元调度和反压控制，它们的选择对 于网络的拥塞控制起着重要的作用。 在上一章中，我们已经简单介绍信元调度和反压控制在q o s 中所起到的重要 作用。而本章我们首先将从信元调度算法的研究现状和我们所提出的改进方案两 个方面重点阐述国内外的科研人士对其所作的贡献；然后我们以样机原型为例， 说明反压控制的实现方式及其特点。 4 1 流量控制策略研究现状 4 1 1 信元调度的研究现状 现阶段，信元调度算法主要分为基于轮询的调度算法和基于通用处理器共享 的调度算法。前者包括先来先服务调度排队( f c f s ) 、优先级排队( p q ) 、公平排队 法( f q ) 及加权轮询排队( w r r ) 等。后者包括虚拟时钟调度算法( v q ) 、加权公平排 队( w f q ) 等。 对于实现全局的公平性来说，轮询策略比其它的调度策略简单，它常常以单 独的队列对每个流进行操作，更详细的说，多路复用的实现是通过对所有队列进 行循环扫描，而后从每个队列输出一个信元来实现的。在轮询机制中，调度器是 不考虑信元的到达率的。 信元调度的研究很重要的原因就是现实业务发展的需要。早期业务单一的时 候，先到先服务调度排队( f c f s ) 就可以满足q o s 的需要。而后，随着业务的多样 化，比如，视频、音频等。多种业务对时延的要求各有不同，我们就需要能够应 对不同时延要求的算法。十几年来，人们就提出了很多的算法和一些改进策略， 本节我们将从各个时期的经典算法出发，详细叙述信元调度算法的研究与发展。 1 先到先服务队列调度算法 先到先服务( f i r s tc o m e f i r s ts e r v i c e ) 队列调度算法是一种基本的调度算法，它 的原理很简单，各个输入流的信元按照到达的先后顺序进入队列，队列就按照信 元进来的先后顺序给信元提供服务，如图4 1 所示。 f c f s 算法最大的优点就是队列管理简单，调度实现方便。同时最大的弊端就 是对待不同种类业务一视同仁，这样，实时性要求高的必然不能满足q o s 要求。 大容量a t m 交换机服务质量控制策略及其性能仿真研究 f l o w1 f l o w 2 f l o w3 i ，1 l 斗 路 2l 斗由 i 3l 。器 f c f sq u e u e s 衄 图4 1f c f s 队列调度算法 2 优先级调度算法 优先级调度算法p q ( p r i o r i t yq u e u e i n 曲可以为不同等级的服务提供一种相对 简单的调度算法。在传统的优先级排队中，系统先将信元进行分类，然后分配到 不同的优先级队列中，队列之间按照优先等级进行服务，在一个队列中按照f c f s 进行服务，如图4 2 所示。 高f l o w1 中f l o w2 低f l o w3 ”弱ii l 卜+路 2 2 卜+由 1 3 3i 卜_ +器 p q q u e u e 30 ，回唧 图4 2p q 队列调度算法 p q 策略最大的优点是它可以为业务提供不同等级的服务，可以通过为实时业 务设定较高的优先级来更好的保证它们的服务质量。严格的优先级排队策略保证 路由器总是先服务高优先级队列的信元，并且只有在高优先级的所有队列为空时 才为低优先级队列提供服务。因此，他存在一个重大的问题：当高优先级队列的 业务流很繁忙时，那么低优先级业务流会得不到服务，从而出现队列“饿死现 象，这样，p q 调度算法也不是一个好的解决方案。 3 加权循环队列调度算法 加权循环调度w r r ( w e i g h t e dr o u n dr o b i n ) 的出现，是信元调度研究方向的 里程碑。它支持不同的带宽需求，可以为不同的队列分配不同比例的输出带宽。 在w r r 算法中，信元首先被分成不同的服务等级( 如实时业务、交互信息、 数据传输等) ，然后被分配到与之相对应的队列，对每一个队列采用轮询服务，因 此在一个轮询周期内每一个队列至少有一个信元被传送，所以避免了p q 调度中 的低优先级队列“饿死 现象。权重的分配是根据业务优先级来分配的，这样， 我们就可以给不同的业务提供q o s 保证。如图4 3 所示。 w r r 调度算法最显著的优点是它可以根据业务不同的需求，提供较为合理的 q o s 保证。然而，他自身也存在一个显著的问题：由于其权值的固定，它在处理 第四章流量控制策略及改进研究 突发业务时效率很低，这样，在存在突发业务的队列里信元将产生更多的时延。 因此，很多科研人员也在这方面做出了很多的努力，下面我们来说几种改进的算 法以及它产生的问题。 f l o wl f l o w2 f l o w3 ll p 一 一， 路 l 2 i 2 p _ 由 器 | ，ll 。l黜沪 w r rq u e u e 坩。哑丑，哑碉 图4 - 3w r r 队列调度算法 4 基于队长门限的调度算法 基于队长门限的加权调度算法q l w r r ( q u e u el e n g t h b a s e dw e i g h t e dr o u n d r o b i n ) 是w r r 的一种改进形式，它是根据上面的问题提出的。 我们现在举例来说明q l w r r 的工作过程。如图4 4 ( a ) 所示，我们假设当前某 一个队列来了一个突发信元，而其权值为1 ，对于w r r 来说，在一个确定的周 期内，两个信元同时到达，而其权值为l ，队列在每个调度周期内只能服务一个 信元，因此，另一个信元只能等到下一个周期传送，这样，信元的时延增加了。 而q l w r r 引入两个参数队长门限值q f 和权值因子u 来改善这样的情况，如 图4 4 ( b ) 所示。当队列长度超出队长门限q f 。时，此时，我们会给其指定一个额 外的权值因子u 给队列，在图4 4 ( a ) 的情况下，我们把权值因子u 赋为1 ，此时， 权值就变成了2 ，说明在这个周期内可以服务的信元为2 ，那么就可以把当前的两 个信元在同一个周期内输出。 c e l l a r r i v a l c e l l d e p a r t u r e c e l l a r r i v a l c e l l d e p a r t u r e ( a ) w r r ( b ) q l w r r 图4 4q l w r r 队列调度算法 q l w r r 最大的特点就是通过为每个队列设置队长门限瓯，以此作为调整权 大容量a t m 交换机服务质量控制策略及其性能仿真研究 值的依据，从而达到优化算法的目的。然而，它却给我们带来了新的问题：我们 应该怎样设定队长门限q ， 和权值因子u 才能达到性能优化呢? 5 改进的公平加权调度算法 改进的公平加权调度算法n f w r r ( n o v e lf a i rw e i g h t e dr o u n dr o b i n ) 也是 w r r 的一种改进，它兼顾了队列之间的相对公平性。 n f w r r 的核心思想是当网络没有发生拥塞并且所有业务类队列长度相对较 小没有超过预定阀值时，按照普通w r r 的算法进行调度。用户可以根据不同业 务的服务等级或用户的需要预先设定各业务类的权重。当网络发生拥塞或者某优 先业务类数据突发时，队列长度增加，当某一优先业务类的队列长度超过预定的 阀值幺时，权重改变机制开始启动。此时将该拥塞队列的权重增加一个比值 ( 0 ，1 ) ，同时，将服务等级高于该业务类的所有优先业务类都按相同的比例增 加它们的服务权重，而比该业务类服务等级低的所有业务类包括尽力服务业务类 权重不变。这样使得服务等级高的业务仍然具有高的权重，保证了各业务类的相 对公平性同时，由于它仅改变了部分业务类的权重，处理拥塞队列更有针对性， 能够更迅速地消除拥塞。当该拥塞队列的长度降至阀值q f 以下时，将所有优先级 高于该队列且队列长度不超过的队列恢复为原始权重。如图4 5 所示。 q q 图4 5n f w r r 队列调度算法 n f w r r 的特点是它在处理突发业务的同时，兼顾了队列的相对公平性，但 是，它这样的处理方式存在一个问题，当某一优先级业务超出阀值以后，比他高 的优先级业务我们都要作相应的处理，然而如果某一优先级业务其实不需要在额 外给它增加权值，这样就产生了低的利用率。 6 结合优先级队列与权值的调度算法 结合优先级队列与权值的调度算法p q w r r ( p r i o r i t yq u e u i n gw e i 曲t e dr o u n d r o b i n ) 是优先级队列调度和加权循环调度的结合，是针对实时业务设计的。 p q w r r 的核心思想是把业务时延要求低的队列采用w r r 进行调度，业务时 延要求高的队列和w r r 调度的业务时延低的队列结合起来采用优先级队列进行 调度，如图4 6 所示。 p q w r r 的特点是提高了高优先级业务的性能指标，其实它也是通过牺牲一 第四章流量控制策略及改进研究 2 7 部分低优先级业务的性能指标换取的，所以，高优先级业务达到了优先级队列调 度的性能，而低优先级业务性能介于p q 策略和w r r 策略之间。 f l o w0 f l o w1 f l o w2 f l o w3 j 曩 i - 路 p q w r q u e u e l | 重削-路 由 32 2 | l 圈图 jlw r r q u e u e ， 22阻- 由咖3 阿i 阶器 r 器 i1 3l 3 陬 ， 图4 6p q w r r 队列调度算法 4 1 2 反压控制的实现方式 上一章最后我们提到了反压控制是交换机内部的流量控制，它是一种很好又 常用的