（计算机应用技术专业论文）epfts交换调度算法仿真与性能分析.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 针对下一代i n t e m e t 网络体系结构要求精简高效的特点，四川省网络通信 重点实验室提出了“单物理层用户数据传输与交换平台体系结构( s u p a ) ”，采 用带外信令控制思想将i n t e m e t 现有的协议栈保留在其“信控管理平台” ( s & m p l a t f o r m ) 上，以保持与i n t e r a c t 的互联互通能力，而利用“面向以太 网的物理帧时槽交换( e p f l s ) 技术”将数据链路层的分帧与转发功能同复用 功能合并到物理层中，由此将用户数据传输与交换平台简化为单物理层结构， 这正是本文的研究背景。 本论文中反映的研究工作是用户平面中与交换结构和交换机制相关的服务 质量保障技术一- - e p f t s 中的队列调度算法，研究的重点是受配额约束的多优 先级业务队列调度策略以及为降低传统交换结构及其相应调度算法的复杂性研 究适合e p 兀s 环境的交换转发核心。 论文首先描述了在输入排队与输出排队下相应调度算法的原理，并通过仿 真实验分析各自的特性。然后针对业务流的服务质量需求引入优先级类别并改 进了相应的调度算法，结合仿真实验的结果提出了一种受配额约束的多优先级 业务队列调度策略。受配额约束的多优先级业务队列调度策略针对传统的严格 优先级队列调度算法对低优先级业务完全不公平的缺点，结合e p f t s 交换环境 中服务质量协商阶段定义的规则等因素，为每个优先级业务分配一定的配额， 规定各种优先级业务都不能超过其配额，否则超过配额部分的业务量不能得到 其服务质量要求的保障。本文通过模拟试验详细分析了各种业务流在不同的配 额下调度算法的性能，为e p f t s 交换机制的研究提供了一定的参考。另外本文 也简单模拟分析了网络业务流的自相似特性对调度算法的性能影响。为降低传 统n n 交换结构及其调度算法的复杂性，最后本文基于输入与输出排队下调 度算法各自的优势提出了一种多输入单输出复用直通前传结构，该结构将 n n 的复杂度降低到n 1 ，避免了输入排队调度算法在输入输出端口对之间 进行的多次匹配，并且通过引入少量的高速缓存提高了系统的吞吐率。 论文中作者的主要工作与贡献可以概括为： 详细描述了输入排队与输出排队下的队列调度算法原理，并对已有的典 型算法进行仿真实验，通过实验结果对比分析其主要性能参数； 针对不同业务的不同服务质量需求，同时为了解决严格优先级调度算法 存在的公平性缺陷以及针对e p f t s 交换环境中服务协商阶段定义的规则等因 西南交通大学硕士研究生学位论文第1 i 页 素，提出了一种受配额约束的优先级调度算法。针对为各种业务流分配不同的 配额，仿真得到了在不同配额下各种优先级业务的时延特性，为提高调度系统 的总体性能提供了一种参考； 针对网络业务流的自相似特性，本文采用流叠加法建立仿真模型仿真网 络流量的自相似性。在不考虑业务的优先级特征下，仿真自相似性对调度算法 的影响，并与同等条件下的泊松过程结果进行对比分析； 为了降低n 交换结构的设计复杂性，提出了一种多输入单输出复用 直通前传结构( n i s o m e f s ) ，该结构将复杂性降低到x 1 ，而且避免了输入 排队调度算法要求输入输出端口对之闯进行的匹配，缩短了数据的等待时延， 大大降低了调度算法实现的复杂度，同时又避免了输出排队对交换核心高加速 比的要求，提高了系统的吞吐率。 关键字：受配额约束的多优先级业务队列调度算法( o u o t a - l ，1 3 ) ： 多输入单输出复用直通前传结构( n 璐0 加巳f s ) ； 基于优先级的并行迭代匹配算法( p - i s u p ) ； 面向以太网的物理帧时槽交换技术( e p f r s ) ： 网络业务流的自相似特性( s e l f - s i m i l a r i t y ) 西南交通大学硕士研究生学位论文第1 il 页 a b s t r a c t t h eb a c k g r o u n do ft h i st h e s i si st h en e wn e t w o r ka r c h i t e c t u r ec a l l e ds u p a ( s i n g l ep h y s i c a ll a y e ru s e r - d 砒at r a n s f e r & s w i t c h i n gp l a t f o r ma r c h i t e c t u r e ) a i m i n g a tn e x tg e n e r a t i o n n t e m e t t os i m p l i f yt h eu s e r - d a t at r a n s f e r & s w i t c h i n gp l a t f o r m i n t oas i n g l el a y e r , an o v e lt e c h n i q u ec a l l e de p f f s ( e t h e m e t - o r i e n t e dp h y s i c a l f r a m et i m e s l o ts w i t c h i n g ) i si n t r o d u c e d e p 丌sc o m b i n e s t h e f r a m i n g a n d s w i t c h i n gf u n c t i o n so ft h ed a t al i n kl a y e rw i t hm u t t i p l e x i n gf u n c t i o nt oap h y s i c a l c h a n n e l t h ew o r kp r e s e n t e di n t h i st h e s i si sq o s g u a r a n t e e dt e c h n i q u e sp e r t i n e n tt o s w i t c hf a b r i ca n ds w i t c h i n gm e c h a n i s m so fu - p l a t f o r m i tf o c u s e so nq u e u i n gi s s u e s a n d s c h e d u l i n ga l g o r i t h m s i ne p f t s 。1 1 b c e m p h a s i s h a s b e e n g i v e 丑t o q u o t a - c o n s t r a i n tm u l t i p r i o r i t yq u e u i n gs c h e d u l i n ga l g o r i t h m sa n de f f i c i e n ts w i t c h i n g & f o r w a r d i n gc o r e w h i c hi sp u r p o s e dt or e d u c et h ec o m p l e x i t yo f t r a d i t i o n a ls w i t c h f a b r i ca n dr e l a t e ds c h e d u l i n ga l g o r i t h m s n ep a p e rf i r s td e s c r i b e st h eb a s i cp r i n c i p l e so fq u e u i n gs c h e d u l i n gu n d e rt h e i n p u ta n do u t p u tq u e u i n g ，a n da n a l y z e st h e i rp e r f o r m a n c eb ys i m u l a t i o n s s e c o n d l y , i ti n t r o d u c e sp r i o r i t y b a s e dq u e u i n gs c h e d u l i n ga l g o r i t h m si nc o n s i d e r a t i o no ft h e s e r v i c e s q o sr e q u i r e m e n t s a i m e da tt h eu n f a i rs h o r t c o m i n go fs t r i c tp r i o r i t y b a s e d q u e u i n ga l g o r i t h m sa n dt h er e g u l a t i o n so fo o sn e g o t i a t i o np r o t o c o lu n d e rt h e e p f t se n v i r o n m e n t ，i t p r o m o t e s a q u o t a c o n s t r a i n tm u l t i p r i o r i t yq u e u i n g s c h e d u l i n ga l g o r i t h m s ( q u o t a p q ) ，w h i c hc a ng e tb e t t e rq o sg u a r a n t e ef o re a c h c l a s ss e r v i c e u n d e rt h ed i f f e r e n tq u o t a so f e a c hc l a s ss e r v i c e t h et h e s i ss i m u l a t e si t s e f f e c t st ot h eq u e u i n ga l g o r i t h m s 。f u r t h e r m o r e ，t h et h e s i ss i m u l a t e st h ee f f e c t so f s e l f - s i m i l a r i t y c h a r a c t e r i s t i ct o q u e u i n gs c h e d u l i n g a l g o r i t h m sb ym o d e l i n g a s e l f - s i m i l a rs o u r c e w h i c hj ss y n t h e s i z e db ym a n ys o u r c e sa n de a c hs a t i s f i e sp a r e t o d i s t r i b u t i o n a tl a s t t h et h e s i sp r e s e n t san e ws w i t c h & f o r w a r d i n gc o r e ，w h i c hh a s m a n ya d v a n t a g e sw i t hl o wc o m p l e x i t y t h et h e s i s sm a i nw o r ka n dc o n t r i b u t i o n sc a nb es u m m a r i z e da s ： ( 1 ) i td e s c r i b e st h en o n o rp r i o r i t i z e dq u e u i n gs c h e d u l i n gp r i n c i p l e su n d e rt h e i n p u ta n do u t p u tq u e u i n g ，a n d a n a l y z e st h e i rp e r f o r m a n c eb ys i m u l a t i o n s ； ( 2 ) i tp r o m o t e saq u o t a c o n s t r a i n tm u l t i p r i o r i t yq u e u i n ga l g o r i t h m s ，w h i c h a v o i d st h es h o r t c o m i n go fa b s o l u t ep r i o r i t y - b a s e ds c h e d u l i n ga l g o r i t h m sa n dc a ng e t b e t t e rq u sg u a r a n t e ef o re a c hc l a s ss e r v i c e u n d e rt h ed i f f e r e n tq u o t a so fe a c hc l a s s 西南交通大学硕士研究生学位论文第l v 页 s e r v i c e t h er e s u l t so fs i m u l a t i o n si n d i c a t et h a tt h en e wa l g o r i t h mi sv a i n a b l ef o r s w i s hd e s i g n ( 3 ) c o n s i d e r i n go fs e l f - s i m i l a r i t yc h a r a c t e r i s t i co fs e r v i c ef l o w , t h ep a p e r m o d e l s t h es e l f - s i m i l a rs o u r c ea n ds i m u l a t e si t se f f e c t st os c h e d u l i n ga l g o r i t h m s ，c o n t r a s t i n g w i t ht h er e s u l t su n d e rt h ep o i s s o nt r a 伍c ( 4 ) t or e d u c et h ec o m p l e x i t yo fn x n s w i t c hf a b r i ca n di t ss c h e d u l i n ga l g o r i t h m s ， t h et h e s i s p r e s e n t s a ne f f i c i e n t s w i t c h i n g f o r w a r d i n g c o r e n i n p u t s i n g l e o u t p u tm u l t i p l e x e de x p r e s sf o r w a r d i n gs t r u c t u r e ( n i s o m e f s ) i t r e d u c e st h ec o m p l e x i t yt on x l ，a n da v o i d st h em u l t i p l em a t c hp r o c e s s e sa tt h ei n p u t a n d o u t p u tp o r t s i n i n p u tq u e u i n ga l g o r i t h m s f u r t h e r m o r e ，i t sp e r f o r m a n c e a p p r o a c h e st ot h eo n et h a ti so b t a i n e du n d e rt h eo u t p u tq u e u i n g , b u ti t d o e sn o t r e q u i r es oh i g ht os w i t c hf a b r i ca so u t p u tq u e u i n gd o e s k e yw o r d s ：q u o t a - r e s t r i c t e dm u l t i e r l o f i t yq u e u i n g a l g o r i t h m ( q u o t a - p o ) ； n - i n p u t - s i n g e o u t p u tm u l t i p l e x e de x p r e s sf o r w a r d i n gs t r u c t u r e ； p r i o r i t y - b a s ei t e r a t i o ns l i p ( p - i s l i p ) ； e t h e m e t - o r i e n t e dp h y s i c a lf r a m et i m e s l o ts w i t c h i n g ( e p f t s ) ； s e l f - s i m i l a r i t y 作者学号q 塑! ! 蛭 西南交通大学学位论文使用授权书 e 堕s 銮携调度篡鎏值真星性能筮扭 系本人在西南交通大学攻读博士，硕士 学位期间= b2 0 0 7 月在导师的指导下完成的学位论文本人完全了解“西南交通大 学图书馆关于保存、使用学位论文的规定”，同意： ( 1 ) 按照学校要求提交学位论文的印刷舨和电子版本 ( 2 ) 图书馆按规定保存所提交论文的印刷版和电子版。 ( 3 ) 本人授权西南变通大学田书馆可以采用影印、缩印或其他复制手段保存论文授权西南交 通大学图书馆为教学和科研的目的，可以将公开的学位论文( 包括解密后的学位论文) 作为资料 在我校图书馆、资科室等场所或本校的校园网以及部分和我校存在馆际合作关系的高校的用户进 行阅读和浏览 作者签名 说明：本授权i5 由研究生在办理离校手续时受剑图书馆 指导教师始嗜 ( 有密缴要求的掰提供学校卡u 关部f 的定薷i f 查结论在解南后遵，奇此规定j 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 本课题的研究背景 本课题的宏观研究背景是四川省网络通信技术实验室为针对i n t e m e t 体系 结构所面临的“高速交换、多媒体服务质量保障和安全问题”三大挑战而提出 的“单物理层用户数据传输与交换平台体系结构”( s u p a s i n g l ep h y s i c a ll a y e r u s e r - d a t a t r a n s f e r & s w i t c h i n g p l a t f o r m a r c h i t e c t u r e ) 1 1 - 7 1 。s u p a 采用带外信令控 制的思想，将控制与管理信息的传输与交换平台( 简称s & m 平台) 与用户数 据传输与交换平台( 简称u 平台) 相分离，最大限度地简化为单物理层的u 平台，以提高对用户数据的传输与交换效率和适应高速交换( 单信道或单波长 数十、上百g b p s 的速率) 的需要和克服了多层u 平台难以保障服务质量的困 难。s u p a 的另一个长远目标是将i n t e r n e t 现有的协议栈转移到s u e a 的s & m 平台以保持与i n t e m e t 的互联互通，再逐步通过对该协议栈的简化和改进，解 决i n t e m e t 的安全性问题。 为了解决s u p a 中u 平台数据的高速、高效交换问题，实验室提出了“面 向以太网的物理帧时槽交换”( e p f t s e t h e m e t o r i e n t e dp h y s i c a lf r a m e t i m e s l o ts w i t c h i n g ) 技术【孔。鉴于以太网技术是目前9 5 以上的计算机和用 户域网络( c p n c u s t o mp r e m i s e sn e t w o r k ) 使用的物理层和数据链路层技术， 因此，e p f t s 以“以太网m a c 帧”作为s u p a 骨干网的单物理层平台透明运 载的主要对象；以能够装载最大长度m a c 帧的固定长度作为“面向以太网的 物理帧”( e p f e t h e m e t o r i e n t e dp h y s i c a lf r a m e ) 的净荷( p a y l o a d ) 字段的长度， 以给定信道波长数据率传输下单个e p f 传输时间作为基本“时槽”( t i m e s l o t ) ， 实现对m a c 帧的异步透明传输。这就是为什么称之为“面向以太网的物理帧 时槽交换”技术的原因。 更准确地讲，本论文所反映的工作的直接研究背景是e p f t s 技术。e p f t s 涉及多方面的技术，从u 平台的用户网络接口( u n i ) 、网络网络接口( n n i ) 、 交换机的交换结构( s w i t c hf a b r i c ) 、u 平台服务质量保障机制( q o sp r o v i s i o n i n g m e c h a n i s m s ) 、数据存储方式和位置分配、输入输出单元和交换单元的e p f 排 队方法和仲裁调度算法，到新型交换结构。本论文的研究重点是与交换相关的 排队方式与交换仲裁调度算法、不同的排队方式和仲裁调度算法在不同的输入 数据到达规律下对交换服务质量主要参数的影响。 西南交通大学硕士研究生学位论文第2 页 1 2 s u p a 与e p f r s 1 2 1 提出s u p a 的动因 i n t e r n e t 的成功与广泛应用使之成为目前计算机网络的主流技术。因此，当 人们开始探讨如何以数字通信技术和分组技术为基础实现网络对音、视频业务 与文本类业务的综合传输与交换之时，自然地把目光转向在i n t e m e t 技术上。 但是，i n t e m e t 技术是在上一世纪七十年代后期发展起来的技术，当时的通信技 术速率低( k b p s 数量级) ，误码率高( 1 0 5 1 0 r 6 ) ，网络应用业务以文本数据为 主，因此i n t e r n e t 体系结构上必然打下了这一历史的烙印。这一烙印具体地体 现在其体系结构的通信子网的u 平台为三层结构，i n t e m e t 协议栈充分体现在 通信子网中的多层的“逐节点”检错与重传纠错以及在端系统之间的“端到端”检 错重传机制上。正因为i n t e r n e t 是以文本数据传输为对象的网络，不适应音视 数据流的传输服务需要，它所提供的服务质量后来被广泛地称为“尽其所能服 务”( b e s te f f o r ts e r v i c e ) 。 随着实时音、视数据在i n t e m e t 应用数据流中所占比重的增加，“尽其所能 服务”的i n t e m e t 传输干网越来越表现出在服务质量保障方面的缺陷。为此， 从上世纪九十年代开始i e t f 提出了一系列的改进服务质量的措施，制定了包 括资源预留协议( r s v p ) 1 1 4 、集成服务( i n t e g r a t e ds e r v i c e ) i 5 j 和区分服务 ( d i f f e r e n t i a t e d s e r v i c e ) 1 6 - 1 7 j 等为代表的协议，试图在p 层内通过资源预留的 方式为单个或一类数据流提供服务质量。实践表明：由于i n t e r n e t 的u 平台的 多层结构，在口层实施资源预留必须依靠数据链路层和物理层具有相应的支持 机制，而现有的多数数据链路层和物理层协议和技术并不具备对上述技术的支 持机制，因此，效果并不理想。 当人们意识到，i n t e m e t 中造成实时性要求较高的数据传输服务质量难以保 障的重要原因之一在于用户数据传输的通信子网使用了复杂的3 层传输平台 时，c i s c o 公司提出利用带外信令控制( o u t o f - b a n ds i g n a l i n g ) 的思想，将用 户数据传输平台简化为增强型的两层结构，即在传统的物理层和数据链路层之 上，增加一个标签子层( t a gs u b 1 a y e r ) ，以用t a g 代替i p 地址作为进行交换的 基础，这一技术被称为标签交换( t a gs w i t c h i n g ) 1 8 】。，r f 将t a g 改名为l a b e l ， 并将相关技术称为多协议标签交换( m u l t i p r o t o c o l l a b e l s w i t c h i n g , m p l s ) 1 9 锄i 。m p l s 在一对用户之间提供面向连接的服务，因而更适合i n t e m e t 中越来越多的以流为基础的应用数据的传输。m p l s 首先在信令控制平台内利 用评地址和l p 路径表在多个节点间逐段建立多段连接，将各段连接映射为数 西南交通大学硕士研究生学位论文第3 页 据传输平台上2 0 比特的标签，从而在入口和出口边界路由器间形成一条虚通路 ( v i a u a lp a t h ) 。标签是节点间的连接标识符，同时又与“前传等价类”( f o r w a r d e q u i v a l e n c ec i a s s ，f e c ) 挂钩，因此，对不同用户数据流选择标签的同时，隐 含了对用户数据转发的服务类别。m p l s 以2 0 比特的标签作为交换字段为用户 数据选径，比用3 2 比特的i p v 4 地址和1 2 8 比特的i p v 6 地址为报文分组选径 更快捷；两层的用户数据传输平台的效率也比3 层的口平台高，但是由于其对 下层的依赖性，m p l s 在解决服务质量问题上的困难与i n t e r n e t 的三层结构u 平台差不多。 文献【1 1 】详细地分析了m p l s 在服务质量保障方面的先天不足，指出：由 于m p l s 必须依赖于现有的数据链路层协议，而服务质量本质上是对物理层传 输质量的度量，因此，它对用户所承诺的数据传输服务质量能否兑现，在很大 程度上取决于标签子层之下的数据链路层和物理层对传输服务质量( 特别是后 者) 的支持程度和能力。例如，m p l s 在a t m s d h 之上的服务质量很容易得 到保障，因为在该种配置下的a t m 网络本身对服务质量保障的支持就很理想。 但是，如果将m p l s 置于无连接的e t h e m e tm a c 协议或所有用户都只能共用 同一连接的p p p 协议之上，即使在物理层采用像s d h 那样的时分复用技术， 由于标签在数据链路层缺少相应的映射机制，服务质量很难得到保障。 进一步分析表明：计算机网络服务质量能否得到保证，关键在于物理层对 用户数据传输和交换的机制中是否具备对服务质量基本参数( 传输速率、传输 时延、抖动等) 的控制能力。这是多层结构u 平台在保证用户数据服务质量方 面先天不足引发四川省网络通信技术实验室对s u p a 研究的根本原因。 1 2 2s u p a 与s i 腊n e t s u p a 始于城域网体系结构的研究1 1 】其基本思想是利用带外信令控制思想 将u 平台简化为单层结构。其具体做法是：将传统数据链路层的“成帧” ( f r a m i n g ) 、对物理信道的复用( m u l t i p l e x i n g ) 功能和传统网络层或数据链路 层对分组或帧的交换( s w i t c h i n g ) 功能融为一体，作为物理层复用与交换子层 的基本功能，从而避免多层结构中上层对下层的依赖关系。由于其u 平台为单 层结构，故该体系结构被称为“单物理层的用户数据传输与交换平台体系结构”， 相应的网络被称为s u p a n e t 。 为了保持s u p a n e t 与i n t c r n e t 的互联互通，i n t e r n e t 现有的协议栈被保留 在s u p a n e t 的s & m 平台；为了适应全面服务质量保障的需要，除了u 平台 上的各种服务质量保障机之外，在s & m 平台上增加了服务质量协商等与服务 质量保障机制相关的协议。s u p a n e t 可工作与i n t e r n e t 模式和s u p a 两种模式， 西南交通大学硕士研究生学位论文第4 页 在前一种模式下其工作过程与i n t e r n e t 相同：在s u p a 模式下，使用高效的单 物理层u 平台并提供相应的服务质量保障。图1 - 1 为s u p a 模式下所需协议与 层次结构示意图j 用户一网络接口)网培一网络接口) 图1 - 1s u p a 模式下s u p a n e t 域内接口与协议层次结构图 文献【1 ，2 ，4 ，5 】对s u p a 层次结构进行了详细的介绍，文献【3 1 对s u p a n e t 中服务质量保障体系进行了较为详细的讨论。鉴于本论文反映的工作是以 e p f t s 为具体背景，在此不就s u p a 体系结构做进一步的讨论。 1 2 3 面向以太网的物理帧时槽交换技术 文献【8 9 】在详细分析了现有各类单层复用与交换技术的利弊之后，提出物 理帧时槽交换的概念，最后定名为e p f t s 。早期，出于节约物理帧开销的考虑， 物理帧格式直接借用了e t h c m e t 的m a c 帧格式，将在s u p a 域内不需要的m a c 帧的部分字段重新定义为物理帧的控制字段，故将e p f t s 解释为：“类以太网 物理帧时槽交换”( e t h e m e t 1 i k ep h y s i c a lf r a m et i m e s l o ts w i t c h i n g ) 。后期的研 究表明：在e t h e m c tm a c 帧之外增加物理帧专用字段概念上更清晰，更符合网 络分层的习惯，在s u p a 与i n t e m e t 边界上操作也更为简便，字段的扩展性也 更好，故最后定名为“面向以太网的物理帧时槽交换”( e p f t s e t h e m e t - o r i e n t e d p h y s i c a lf r a m et i m e s l o ts w i t c h i n g ) a e p f t s 的定名充分考虑了“9 5 以上的计算机系统和用户域网络( c p n c u s t o mp r e m i s i sn e t w o r k ) 使用以太网技术”这一现实，“面向以太网”的设计 西南交通大学硕士研究生学位论文第5 页 思想有利于实现对数据链路层的主流格式的帧( m a c 帧) 的透明传输，从而 保证e p f t s 技术在与现有网络的接口的“方便性”和“普适性”。这与目前r r u 和“城域以太网论坛”( m e f m e t r o p o l i a n e t h e r n e t f o r u m ) 将以太网技术作为 未来城域网和广域网的主流交换技术的努力和实现电信级的以太网传输网络 ( c e c a r r i e r - d a s se t h e m e t ) 相关工作有一定的相似性。 定长物理帧、异步交换和提供面向连接的虚线路服务w l s v i r t u a ll i n e s e r v i c e 是e p f t s 的三个基本特征。仿真实验表明：定长帧交换有利于改善交 换节点中的传输时延、抖动等服务质量参数，因此，面向以太网的物理帧( e p f e t h e m e t o r i e n t e dp h y s i c a lf r a m e ) 的“净荷”( p a y l o a d ) 部分定为最大m a c 帧长度，即1 5 3 0 字节，其传输时间固定，因而在e p f t s 交换节点内可用于转 发e p f 的时间也固定，有利于交换机的设计和仲裁调度。 e p f t s 在时槽间的同步采用异步方式，以避免高速通信与交换中节点间时 钟同步的困难。e p f t s 对用户数据流提供虚线路( v i r t u a ll i n e ) 服务，更适应 数据流的传输和服务质量保证的需要，避免i n t e m e t 中为单个口报文选择路径 选择可能造成的报文错序或丢失。 1 3 本课题研究的内容 迄今为止，实验室已开展的关于e p f t s 的前期研究已经奠定了e p f t s 基 本技术框架并对部分典型技术进行了部分探讨，这包括：超前交换技术( s f s s t e pf o r w a r ds w i t c h i n g ) 2 1 】、波长e p f 的配额( q u o t a ) 的限额与动态调整机制 【列、基于服务质量协商参数的u 平台入网控制机制( u a c u s e r - d a t a a d m i s s i o n c o n t r 0 1 ) 2 2 】、输出流量整形( t r a f f i cs h a p i n g ) 2 3 】等。但是从整体上讲，对e p f t s 交换节点应当采用的排队方式和交换结构的仲裁调度算法以及它们对不同数据 到达规律对交换服务质量关键参数的影响还缺少系统的研究，因此，对从保障 典型服务质量参数的角度出发，e p f t s 交换机应采用何种交换结构以及交换机 内应采用何种排队方式及仲裁调度策略上缺少定量分析与设计的依据。因此， 本课题就是希望通过软件仿真求解上述问题的答案，为e p f t s 交换机的设计提 供依据。 第二章分别介绍了输入排队与输出排队下的调度算法的原理，并针对无优 先级业务流满足泊松到达过程的情况对调度算法进行仿真实验，通过实验结果 验证了模型的f 确性，为后续的实验与分析奠定了基础。 第三章在第二章的基础上根据业务流的服务质量需求引入了优先级特性， 详细描述了在输入排队与输出排队下相应的调度算法并通过仿真实验分析其性 西南交通大学硕士研究生学位论文第6 页 能特征。然后针对基于严格优先级的调度算法所存在的不公平性以及在e p f t s 中建立连接阶段时服务协商阶段所定义的规则，提出了一种受配额约束的优先 级调度算法，并通过仿真实验结果分析了配额对业务服务质量的影响，为e p f t s 交换机的参数设计提供了一定的依据。 第四章针对网络业务流的自相似特性，简要描述了自相似的相关特性以及 流量建模模型，然后通过物理建模模型来模拟业务的自相似特性，并通过仿真 实验分析自相似特性对调度算法的影响。 第五章根据前述章节的实验结果，分析了输入排队与输出排队调度算法的 优缺点，提出了一种结合输入排队与输出排队优越性的多输入单输出复用直通 前传结构，该结构既降低了n n 交换结构的复杂性，同时又避免了输入排队 中输入输出端口对之间的匹配过程，通过将对数据分组的交换前传分解为独立 的两个部分，利用简单的调度算法获得了逼近输出排队下调度算法的高性能优 势。 西南交通大学硕士研究生学位论文第7 页 第2 章e p f t s 无优先级数据交换调度算法 2 0 本章前言 本章首先简单描述了调度算法的工作原理，并对目前流行的调度算法进行 分类。队列调度算法的研究已比较成熟，针对各种情况都有相应的算法，然而 大部分算法都具有较高的复杂度，例如很多算法都需要计算及保存时间，并进 行相应的比较后再决定分组的调度，这种情况不能满足e p f f s 所期望的性能， 首先e p f t s 帧格式的特殊性，因此不必考虑处理变长数据分组的附加代价：其 次，e p f t s 的目的是在物理层实现对用户数据的高速交换和为不同的网络应用 提供相应的服务质量保障，音频、视频等多媒体业务流在网络中所占的比例日 渐增多，但传统的数据流仍将占用一部分带宽。因此，e p f f s 的调度策略必须 能够满足对时延要求低的文本数据，也需要满足对时延敏感的音、视像数据， 因此需要所采用的调度策略能够对不同的业务流加以区分；再次，根据智能网 以及软交换技术的发展，交换核心只完成最基本的转发任务，而其他附加功能 由其他模块处理，因此在设计中尽可能简化交换核心的功能，并提高效率；最 后，e p f t s 也是为适应网络高速交换而提出的，所以要求其队列调度策略控制 尽量简单，能够由硬件直接实现，否则不可能满足这一要求。 本章详细描述了输入排队中经典的i - s l i p 算法的工作原理，然后针对 i - s l i p 与简单输出排队策略建立仿真模型，通过仿真结果对两种调度算法的性 能进行详细的对比分析。 2 1 队列调度算法概述 网络业务流从数据源到目的的传输过程中，需要在中间交换节点进行缓存， 根据一定的调度策略对不同的输入业务流分别进行调度服务，使所有的输入业 务流能够按照预定的方向共享交换节点的处理资源以及输出链路带宽，满足各 种业务不同的服务质量需求。调度策略是按照一定的规则对到达交换节点的不 同业务进行缓存、调度和服务，同时实现流量的管理与控制、冲突处理、带宽 的分配与管理等功能。 在网络的中继节点，对缓存队列中所属不同业务流的分组进行调度的基本 模型如图2 - 1 所示。输入业务到达交换节点后，分别暂存到相应的缓存队列中， 根据不同的调度策略从n 个队列中选择下一个将要传输的分组，然后将分组发 西南交通大学硕士研究生学位论文第8 页 送到输出端口。 图2 1 队列调度模型原理 队列调度算法作为交换系统中的一个核心部分，业界学界进行了大量的研 究，已提出了很多算法。根据不同的原则可以分为很多类，简单讨论如下： 按照系统的工作模式，调度算法可分为持续型与断续型两种【2 卅。在持续型 调度算法中，只要系统中有等待发送的分组，调度器就按照一定的规则选择一 个分组进行服务，只有缓存中没有分组时，输出链路才会空闲，这样可以获得 很高的链路利用率，典型算法包括：通用处理机共享g p s l 2 5 2 6 ，加权公平排队 w f q 2 7 1 ，加权轮循调度w r r l 2 8 i 、借还- 力日权轮循调度b r w r r 2 9 1 、改进的差 额力口权轮循调度i d w r r 3 0 l 以及优先级调度p q 3 1 】等：在断续型调度算法中， 即使系统中有等待发送的分组，调度器也可能因为分组的调度合法时间没到暂 时不对其进行服务，一般用于调度之前的整形处理，好处在于可以对端到端时 延和抖动进行控制，但其链路利用率较低，典型算法包括：分层轮循调度 h r r 3 2 1 ，停等调度s t o p a n d g o 3 3 l 以及j i t t e r - e d d 3 4 】等。 按照处理单元，分组调度算法可以分为基于时签和基于轮循的调度算法两 种。基于时签的调度算法根据一个系统虚拟时间v t 为每个分组保持两个表示 开始服务与结束服务的时签，系统根据一定原则根据时签选择分组，典型的算 法包括加权公平排队w f q 2 7 、最坏情况的公平加权公平排队w 产q 【3 捌、虚拟时 钟v c 3 6 l 以及自时钟公平排队s c f q 3 7 】等；基于轮循的调度算法是调度器循环 地对每个队列进行服务，不需要进行时签比较，实现简单，典型算法包括 d r r 3 8 】、w r r 2 8 】、b r w r r 2 9 j 以及分层轮循调度h r r 3 2 】等。 按照交换结构的缓存设置，交换结构可以分为：基于输入排队i q 、基于输 出排队o q 、基于交叉点排队c q 以及各种情况的联合下的交换结构等。对各 种交换结构，存在相应的调度算法，如对i q 交换结构，典型调度算法有最大 匹配m s m 3 9 1 、并行迭代匹配p i m 4 0 l 、多次轮循并行迭代匹配i s l i p 4 1 l 以及并 行迭代双重轮循匹配i d r r m l 4 2 1 等。 由于e p f t s 是为适应高速交换而提出的，所以要求其队列调度策略控制尽 西南交通大学硕士研究生学位论文第9 页 量简单，能够由硬件直接实现，而且其交换字段e p f 的定长格式使得没有专门 讨论变长数据包如何调度的必要。另外e p f f s 的目的是在物理层实现对用户数 据的高速交换和为不同的网络应用提供相应的服务质量保障，因此调度算法需 要适应不同业务流的不同服务质量需求。 2 2 输入排队的典型调度算法i - s l i p 传统的输入排队( i q ) 调度算法中，为每个端口设置一个缓存队列采用f i f o 方式进行服务，这种方式由于存在头部阻塞的问题，其吞吐率仅为5 8 6 1 * 3 1 ， 因此一般采用虚拟输出队列( v o q ) 方式】来提高吞吐率，即为每个输入端口 设置n ( n 为交换机输出端口数目) 个缓存队列，每个队列面向一个输出端口。 在均匀流量分布以及合适的调度算法的条件下，其吞吐率可达1 0 0 1 4 5 1 ，本文 所讨论的i q 调度算法都是基于v o o 队列。输入排队调度算法的基本工作原理 如图2 2 所示： i 。萌硒西万j - 竺竺一泽 图2 2 输入排队调度算法工作原理模型 图2 2 中，交换单元连接m 个输入端口和个输出端口，对每个输入端口 i 都设置个v o q 队列，分别代表个输出端口。任一输入端口f ( 1 f j m ) 的 e p f 到达过程是离散时间过程。每个时隙开始时在每一个输入端口有0 或1 个 e p f 到达，而每个e p f 都须经一个输出端口f ( 1 主辟) 输出。定义输入端口f 到输出端口，的到达过程为a i ，( r ) ，其到达率为 ，则对所有输入端口到达有 a ( t ) = “( f ) ；( 1 s f 兰m ) ) ，任一输出端口j 的离开过程d ，o ) 是一个离开率为a