（光学工程专业论文）分组交换光网络中的调度算法研究与仿真.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 随着i n t e m e t 网络的高速发展和宽带技术的不断更新，宽带视频、多媒体等各种实时 数据流量急剧增加，对通信网的带宽和核心路由器的性能提出了更高的要求一更高的传输 速率和提供确定的服务质量保障( 时延抖动、吞吐量等) 。 为了适应日益增长的带宽资源需求，作为通信网的两大主要组成部分一传输和交换都 在不断的发展和革新。近几年，由于光通信技术尤其是d w d m 技术的成熟，光网络因其巨 大的频带资源和优越的传输性能，使主干链路的传输带宽不再成为问题。然而，传统的基 于总线和中央处理器结构的路由器，由于其体系结构上的局限已经无法满足组建高速主干 网络的需求。国际上提出了用交换结构提高各接口单元之间的数据通信速度的基本思想， 交换结构成为影响交换机性能的核心模块，光交换技术已经成为实现全光网络的核心技 术。但目前世界上的光交换技术都处于电控光交换阶段，即信号交换是全光的，光器件的 控制仍由电子电路来完成。 为了保证一定的服务质量，核心路由器必须设法增加交换能力。在普遍采用的定长分 组交换结构中，忽略同步和传输时延的情况下，核心交换机的性能主要受排队策略和调度 算法的影响。排队策略决定如何缓存到达的分组；调度算法则是通过解决在每一个时隙中 发生在相同输出端口的冲突问题，控制业务流对交换网络结构的有序访问。 本文中基于目前最有发展前景的电存储一光交换混合结构，针对带有虚拟输出队列 ( v o q ) 的交换网络结构，研究了分组交换光网络中的高吞吐量和低抖动的调度问题，采 用基于矩阵分解的静态调度算法进行求解。在深入研究和分析了以往的调度模型与调度算 法的基础上，针对带有v o q 的c r o s s b a r 交换结构中的调度问题( n p h a r d 问题) ，提出采 用遗传优化算法来解决，并制定了该问题特有的编码、交叉和变异等遗传算子的设计方案。 最后，运用仿真程序分析了该算法的吞吐量、抖动性能，并与传统的算法进行了比较。 关键词：调度，虚拟输出队列，遗传算法，抖动，吞吐量 第1 页 a b s t r a c t a l o n gw i t hh i g hd e v e l o p m e n to fi n t e m e t ，u n c e a s i n gr e n e w a lo fw i d t h t e c h n o l o g ya n ds h a r p g r o w t ho fe a c hk i n do fr e a l t i m ed a t as u c ha sv i d e o ，m u l t i m e d i aa n ds oo n ，h i g h e rd e m a n d sf o r b a n d w i d t ha n dp e r f o r m a n c eo fc o r er o u t e rh a v eb e e ns e t a st w ob i gc o n s t i t u e n t so fn e t w o r k ，t e c h n o l o g i e so ft r a n s m i s s i o na n ds w i t c hn e e dr a p i d d e v e l o p m e n t i nr e c e n ty e a r s ，w i t ht h em a t u r i t yo fo p t i c a lc o m m u n i c a t i o nt e c h n i q u e si n p a r t i c u l a rd w d ma n do p t i c a ln e t w o r k sh u g ec a p a c i t y , b a n d w i d t hi sn ol o n g e rt ob e c o m et h e q u e s t i o n h o w e v e r ，t r a d i t i o n a la r c h i t e c t u r eo fr o u t e rb a s e do nb u sa n dc e n t r a lp r o c e s s o ri su n a b l e t os a t i s f yh i 曲s p e e dn e t w o r k o ni n t e r n a t i o n a l ，at h o u g h to fu s i n gs w i t c hs t r u c t u r et oe n h a n c e t h es p e e do fd a t ac o m m u n i c a t i o nb e t w e e nv a r i o u sc o n n e c t i o n su n i ti sp r o p o s e d t h i ss t r u c t u r e h a sb e c o m et h ec o r em o d u l et h a ti n f l u e n c es w i t c hp e r f o r m a n c e ，o p t i c a ls w i t c ha l r e a d yb e c o m e s c o r et e c h n o l o g yo fh i g hs p e e dn e t w o r ka n di sa tt h es t a g eo f o p t i c a ls w i t c hw i t he l e c t r i c a lc o n t r o l p r e s e n t l y t h a t 。m e a ns i g n a l sc a l lb et r a n s m i t t e de n t i r e l yi no p t i c a lf o r m a l 。b u tt l i ec o m p o n e n t s o fc o n t r o ls t i l lc o m p l e t e db yt h ee l e c t r o n i cc i r c u i t i no r d e rt og u a r a n t e ec e r t a i n q u a l i t yo fs e r v i c e ( q o s ) ，t h ec o r er o u t e rm u s tt r yt oi n c r e a s e t h es w i t c hc a p a c i t y i nt h e s i t u a t i o no fu s i n g f i x e d 1 e n g t hp a c k e ti ns w i t c hs t r u c t u r e ，w h e n s y n c h r o n i z a t i o na n dp r o p a g a t i o nl a t e n c ya r es o l v e d ，t h ec o r er o u t e sp e r f o r m a n c e sa l ei n f u e n c e d b yq u e u i n gs t r a t e g ya n ds c h e d u l i n ga l g o r i t h m t h es t r a t e g yo fq u e u ed e c i d e st h eb u f f e rh o wt o d ow i t ha r r i v a lc e l l sw h i l es c h e d u l i n ga l g o r i t h mc o n t r o l sv i s i tt ot h en e t w o r ka n ds o l v ec o n f l i c t o c c u ri ne a c ht i m es l o t i i lm et h e s i s ，p a c k e ts c h e d u l i n ga l g o r i t h m sb a s e do nm a t r i xd e c o m p o s i t i o ni ss t u d i e dw i t h t h ea r c h i t e c t u r eo fc r o s s b a rs w i t c ha n dv i r t u a lo u t p u tq u e u e ( v o q ) t h e s ea l g o r i t h m sa r eb a s e d o nt h es t r u c t u r eo fo p t i c a ls w i t c hw i t he l e c t r i c a l m e m o r y ag e n e t i ca l g o r i t h mf o rh i g h t h r o u g h p u ta n dl o wji t t e rp e r f o r m a n c ei sp r o p o s e dt os o l v et h i sn p h a r dp r o b l e m i nv i e wo ft h i s p r o b l e m ，s p e c i f i cg e n e t i co p e r a t o r sa r ed e s i g n e d ，i n c l u d i n gc o d i n g ，s e l e c t i o n ，c r o s s o v e ra n d m u t a t i o n i nt h ee n d ，t h ep l a t f o r mo fs i m u l a t i o ni su s e dt os t u d y t h e s ea l g o r i t h m s p e r f o r m a n c e k e y w o r d s ：s c h e d u l i n g ，v o q ，g e n e t i ca l g o r i t h m ，j i t t e r , t h r o u g h p u t 第1 i 页 南京邮电大学硕士研究生学位论文 符号说明 符号说明 g ag e n e t i ca l g o r i t h m 遗传算法 b vb i r k h o f fv o n - n e u m a n na l g o r i t h m b v 算法 g l j g r e e d yl o wj i t t e ra l g o r i t h m贪婪低抖动算法 i l p i n t e g e rl i n e a rp r o g r a m m i n g整数线性规划 o p s o p t i c a lp a c k e ts w i t c h光分组交换 v o q v i r t u a lo u t p u tq u e u e 虚拟输出队列 h o lh o l d o f l i n e 链头阻塞 q o sq u a l i t yo fs e r v i c e服务质量 w d m w a v e l e n g t hd i v i s i o nm u l t i p l e x波分复用 p o np a s s i v eo p t i c a ln e t w o r k 无源光网络 o n u o p t i c a ln e t w o r ku n i t 光网络单元 o l t o p t i c a ll i n et e r m i n a l 光线路终端 。范 o o p t i c a l e l e c t r i c a i o p t i c a l 光电光转换 第v i 页 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 始蜘期：遍够侈髋蝼各渺瓤坐华够侈 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 二鲁雅名：埤嗍挫弛哆 南京邮电大学硕士研究生学位论文 第一章绪论 第一章绪论 随着计算机和通信网络的发展，人们对网络服务种类和质量提出越来越高的要求。针 对现有的网络规模，如何高效管理和使用这些网络资源，如何对有限的网络资源进行合理 分配，以便使现有的网络资源最大限度的发挥功效，来为更多的用户提供更优质的服务， 成为网络调度的一个核心问题。网络调度不仅需要一个好的网络结构，更重要的是设计一 种好的调度算法控制和协调业务流量，为用户提供满意的服务质量。相反，如果一个效率 低下的调度算法，不仅会浪费资源，甚至会导致死锁，使得网络不能正常运行甚至瘫痪。 1 1 调度的基本概念 广义的调度通常是指对工作、任务、资源等进行适当的分配和规划，从而满足预定的 目标。狭义的调度是指一个与时间次序有关的资源分配的概念，即在多个用户争用资源时， 如何确定一种服务次序，使各方面的利益最大化。 从理论体系上讲，调度算法属于排对理论的一个分支。包括六个要素：调度者、被调 度对象、调度目标、调度结构、调度算法和调度代价。其中调度算法( 调度规则、调度机 制) 是连接其它各个要素的纽带。而设计调度算法时，往往需要在调度代价和调度目标之 间进行折衷。因此，调度问题实际上可以描述为一个多目标优化问题。 1 2 调度算法类型 根据被调度对象和调度代价的行为是否呈现出随机时变特性，可以将调度算法分为两 种类型：静态调度和动态调度。静态调度是指事先为每一个预计要发生的特定业务分配一 个固定的服务时隙，故也称为分配调度，属于一种非权重调度算法。动态调度则是根据业 务需求的动态变化，在发生资源争用的情况下，灵活地采用相应策略对资源进行重新分配， 避免了业务的拥塞和长时间等待，属于一种有权重调度算法。 静态调度和动态调度优缺点：由于静态调度中，给定的资源需求和约束通常是在一段 时间内固定不变的，所以调度算法不受计算时间的限制，一般可以采取优化方法进行求解。 而动态调度中，资源需求是随着时间的变化而变化的，调度算法也必须根据资源变化，相 应的做出快速响应。与静态调度算法相比，动态调度算法提供了较好的时延和公平特性， 第1 页 南京邮电人学硕士研究生学位论文 第一荦绪论 但对算法求解速度也有一定的要求。这时采用优化方法就无法满足动态调度在运算速度方 面的要求，所以大多数动态调度算法采用的是近似算法。 在传统的网络调度问题中，由于网络资源需求情况是随机变化的，需要调度算法及时 做出响应，因此主要考虑采用动态调度策略。但本文中讨论的是分组交换光网络中的调度 问题，由于光交换机中的光路重配置时间较长，为提高传输效率及降低内部工作速率，输 入输出端口之间的匹配关系必须固定维持一段较长的时间。本文中针对流量需求变化不大 的流量结构，考虑选用静态调度算法进行研究，并为以后研究动态调度算法奠定基础。 1 3 网络调度的主要性能指标 调度算法在不同环境下有不同的应用。例如：调度算法可以用于隔离恶意业务流，为 正常业务提供服务质量保证；调度算法还可以让用户平等地共享链路的可用带宽；或者实 现分级的链路共享等。网络调度需要达到一定的网络服务质量。网络服务质量( q u a l i t yo f s e r v i c e ，简称q o s ) 是指网络与用户之间以及网络上互相通信的用户之间关于信息传输与共 享的一种约定。q o s 的性能研究主要集中在以下几方面：1 、算法的效率( 即带宽利用率、 吞吐量) ；2 、算法的时延( 要能保证不同服务类型的数据包的时延要求) ；3 、算法的公平 性( 支持不同优先级服务、无饥饿现象) ；4 、算法的复杂性。近年来，国内外学者对高性 能调度算法进行了大量研究，但众多算法中只有极少数得到了应用，原因是各种算法有着 这样或那样的不足。下面详细叙述网络调度的几个常用的性能指标【i 】： 吞吐量( t h r o u g h p u t ) ：网络中发送数据包的速率，可用平均速率或峰值速率表示。吞 吐量是速率的衡量指标，吞吐量越大，网络的发送数据包的速率越大。 时延( l a t e n c y ) ：指两个参照点之间发送和接收数据包的时间间隔。调度算法应该为不 同的业务提供端到端的最小时延保证，而且只与此业务流的某些参数( 如带宽需求等) 有 关，而与其他的业务流无关。 公平性( f a i m e s s ) ：是指以公平的方式将可用的链路带宽进行有效地分配，为各个业 务流所共享。此外，基于队列的调度算法必须能够隔离不同的业务流，各种业务只占用属 于自己的带宽，这样即使存在恶意或高突发性业务，也不至于影响到其他正常的业务流。 一个公平的调度算法可以防止某些节点或端口一直被服务，而有些却得不到服务，出现“饥 饿 现象。 时延抖动：也称为抖动( j i t t e r ) ，是指在同一条路径上发送的一组数据流中，数据包 之间的传输时间间隔最大值与最小值的差。抖动会引起接收端口意想不到的流量拥塞，同 时需要大量的缓存予以处理。在光网络中，大容量的缓存需求意味着大的代价和能量消耗、 第2 页 南京邮电大学硕：b 研究生学位论文 第一章绪论 管理的复杂性。所以减少抖动从而减少光缓存的使用量至关重要。由于实时业务( 语音、 视频) 对网络传输时延、延时抖动较为敏感，所以低抖动性能成为衡量实时业务调度算法 好坏的一个重要标准【2 1 。 总的来说，上述四个性能指标是彼此联系的。对于静态调度算法来说，节点间数据包 传输的时延低意味着单位时间内网络的吞吐量高；端口间的低抖动意味着分组等待传送的 时间相同，可间接保证公平性。因此，本文中在设计调度算法时只考虑吞吐量和抖动的约 束。 1 4 光交换网络 未来的全光交换技术是指系统的逻辑、控制和交换均在光域完成，不经过任何的o e o 转换，输入端光信号可以直接交换到任意的输出端。为了保证交换性能，处理时延抖动需 要大量的缓冲器，而目前的光缓存技术还相当的不成熟，主要采用昂贵而且非常笨重的光 延迟线来实现，存储器工作速率的发展远远跟不上链路容量的发展，成为限制i m e m e t 速 率增长的瓶颈。尽管对光交换作了大量的研究，但是对全光分组交换节点，仍然没有权威 性的结构设计。目前主要使用混合的解决方案：传输与交换在光域实现，存储和转发控制 功能以电的方式实现。 1 4 1 交换节点结构 通用的光分组交换节点的结构模型如图1 1 所示。 图1 1 光分组交换节点结构模型 第3 页 l c = ) n c = ) 。0n一解 南京邮电大学硕士研究生学位论文 第一荦绪论 分组交换光网络的核心是交换机，为了能在分组级上实现吉比特的快速交换，交换速 度必须达到纳秒量级。光交换与电交换的原理一样，也是通过控制开关矩阵的出线和入线 的接通和断开，来完成信号的交换。图1 1 中调度器的功能主要是完成对分组在交换矩阵 中选路的控制，处理所有的包头信息，决定分组的输出端口和波长，并完成对交换矩阵的 配置工作。交换矩阵部分包括交换矩阵和波长变化器。交换矩阵的主要功能是：在调度器 的控制下，能够完成基于分组级的信号处理，实现信号的选路工作。交换矩阵必须在两个 相继分组到达的时间间隙内完成重新配置和交换。例如，在一个1 0 g i t s 系统中，如果分组 长度为1 2 5 b y t e ( 1 k b i t ) ，一个分组要完全离开输入端口到达交换矩阵需要大约l o o n s ，所以交 换矩阵重新配置和交换的时间必须达到纳秒级。但对于光电混合结构的m e m s 光交换机而 言，端e i 的重新配置时间比电交换要长得多例。出于传输效率的考虑，输入输出端口的匹 配不可能像电交换机每个时隙更新一次，而要在多个时隙中重复使用。因此，光交换机中 的分组调度的基本特点是基于帧的。在每一帧开始的边界上确定端口匹配，进行光路配置， 再传输分组。交换机的内部传输需要肌的加速比，帧长f = c + t ，c 和t 分别为重配置时 间和传输时间。波长转换器可以对输入的光信号的波长进行变化，是解决交换过程中的冲 突问题的另一种手段。现在的波长转换器一般由o e o 转换器来组成，全光域的波长转换 器还没有进入实用阶段。 与电交换不同的是，在光交换中要控制的是光信号，所以光交换中更多的要考虑结合 光的物理特性来进行交换。光开关是完成光交换最基本的功能器件，将一系列光开关组成 一个阵列，构成一个多级互联的网络，在这个阵列中完成光信号的交换。常用的光开关器 件有半导体光放大器、波长转换器等。半导体光放大器可以对输入的光信号进行放大，并 且可以利用一种被称为偏置电信号的器件来控制光信号的放大倍数。当偏置电信号的值为 o 时，输入的光信号不能从光放大器的输出端输出，相当于光开关的断开；当偏置电信号 的值不为0 时，输入的光信号可以从输出端输出，相当于电开关的接通，其结构如图1 2 所示。 输 出光 控制电流 图1 2 半导体光放大器结构图 波长转换器有多种实现方式，一种比较简单的o i e i o 转换方式是：当一个波长丑的光 第4 页 壹塞坚皇查堂堡主塑塑竺堂垡丝- 文 笙二! 堕丝 信号输入时，由一个被称为光电探测器的器件把它转变为一个电信号，然后通过外调制器 或激光器把这个电信号转换为一个波长为旯的输出光信号，其系统结构如图1 3 所示。光 交换中大多是使用半导体光放大器作为光开关。在无源缓存网络中，当前的技术水平是， 在4 英寸的模块上集成几十个光开关，运行速度可达每秒几十g b i t 。这些器件也能实现一 些无源功能，如波长的复用与解复用，在环型城域网上，实现非常简单的波长上下路功能。 缺点是噪声系数和信道串扰高。但是合理的设计能克服这些缺点，信道容量能达到t b s 的 量级。 输 墼盔卜 厂 、 7 yy 探测叫外赢i i 入光 百 旱激光 输出 1 4 2 光分组交换帧格式 图1 3o 啪波长转换器 光分组交换的帧结构包括分组头和载荷，如图1 4 所示。 光 图1 4 光分组交换的帧格式 分组头结构中包括分组头同步比特和路由标记，载荷则包括载荷同步比特和净荷。在 分组头荷载荷的中间存在一定的保护时隙。为了补偿光器件的交换时间、节点处可能存在 的抖动以及在网络节点处同步单元的有限冲突，在分组头前和载荷后都要插入保护时隙。 为了简化同步操作，光分组采用具有固定比特率的分组头。而净荷只具有固定的时隙，而 比特率是可变的【4 1 。 第5 页 南京邮电大学硕十研究生学位论文 第一章绪论 1 5 光分组交换技术 光网络交换分为光路交换( c i r c u i ts w i t c h i n g ) 和分组交换( p a c k e ts w i t c h i n g ) 类型。 光路交换是指在业务进行传送之前，物理光通道就已经建立。分组交换是指在业务传送时， 并不需要建立通信双方的物理连接，而是将要交换的信息进行存储转发。 随着数据、语音、视频等通信业务的融合，而且数据流量逐渐超过语音流量，这就需 要将面向连接的电路交换方式向支持数据业务的分组交换方式转变。分组交换保留了电路 交换传输时延小的优点，同时克服了线路利用率差的缺点。客观的说，目前，在电域可望 取得的进展，仅能满足实现分组交换的短期需求。调查显示，电域t d m 技术的增长系数 是1 5 年，而带宽需求增长系数是8 年，两者的增长比例严重不匹配。随着互联网快速 增长和w d m 光传输基础设施的实用化，为了能满足网络的长期需求，研究显示光开发技 术具有巨大的潜力。将分组技术应用于光域，能实现交换容量与w d m 的传输容量相匹配， 从而驱动了光分组交换技术( o p s ：o p t i c a lp a c k e ts w i t c h ) 的快速发展【5 ，6 ，丌，实现了较高的 信道利用率和低的能量损耗。伴随着电的交换和路由技术的处理速度和容量的巨大进步， 光分组交换技术也已经在一些领域内取得了重大进展。目前，以密集波分复用技术为基础 的光传输和光交换技术在光通信领域内得到了广泛的应用，其网络节点根据光信号的波长 进行路由，是一种较粗粒度的信道分割方式。分组技术与o x c 、m p l s 等新兴技术的结合， 将w d m 透明光网络的传送能力和分组传送模式结合起来。将分组头信息和分组净荷信息 分开处理，根据分组头信息进行选路，是一种较细粒度的信道分割。从而能够实现网络的 优化和带宽的合理利用。 光分组交换包括a t m 光交换、透明光分组交换、光突发交换等。a t m 光交换是对 a t m 信元进行交换，遵循电信号领域a t m 交换的基本原理，采用波分复用、电或光缓冲 技术，先对信元波长进行选路，依照信元的波长，将信元传输到输出端口的光缓冲存储器 中。光分组交换具有大容量、数据率和格式的透明性、可配置性等特点，能够提供端到端 的光通道或无连接的传输。这对未来支持不同类型的数据是非常重要的。光分组交换的主 要优点是带宽利用效率高，而且能提供各种服务，满足客户的需求。在本文中，就针对光 分组交换网络中的调度算法进行研究。 第6 页 南京邮电大学硕士研究生学位论文 第一章绪论 1 6 网络中的重要问题 1 6 1 分组竞争 分组竞争是指两个及两个以上的分组要从交换矩阵的同一个出口输出的情况。为了解 决分组竞争，可以从三个方面来考虑：波长域、时间域、空间域，对应的解决方案是波长 转换、光缓存、偏转路由。光分组缓存是当两个分组竞争一条输出链路时，一个分组被传 输，另一个被送入光存储器中，让它经过充分的延迟来解决竞争问题。波长转换则是通过 转换发生竞争的多个分组的波长来解决竞争。当多个分组要从一个出口以相同的波长输出 时，选择一个分组直接通过交换矩阵，另外的分组均要进行波长转换。偏转路由通过改变 分组在交换矩阵中的路由来解决竞争，只有一个分组按照原来选定的路径传输，其他竞争 失败的分组被送往其他的端口，并经过更长的路径才能到达最初的目的地。 这三种方法各有利弊：光分组缓存能够提供高的网络吞吐量，但目前的光r a m 技术 仍然不成熟，光缓存一直需要依赖光延迟线来实现，而且需要较多复杂的硬件进行控制。 缓存的大小对分组丢失率也有很大影响，今天最大的缓存容量可以达到6 4 个分组，但在 传统的交换结构下，仍然不能保证低的丢包率。偏转路由方法比较容易实现，所需的硬件 较少，但其网络性能较低，网络负载不能太大；波长转换可减少光缓存器的数量或减小分 组的丢包率。在实际中，常常是以上三种中的某几种的结合使用，以减少冲突的发生和提 高解决竞争的效率。 1 6 2 同步 在通信领域，“同步 概念是指频率的同步，即网络各个节点的时钟频率和相位同步， 其误差应符合标准的规定。时间同步是指网络各个节点时钟以及通过网络连接的各个应用 界面的时钟的时刻和时间间隔与协调世界时( u t c ) 同步，最起码在全国范围内要和北京 时间同步。目前，在通信网中，频率和相位同步问题已经基本解决，而时间的同步还没有 得到很好的解决。 对于光分组交换网络而言，分组长度固定且在给定时隙内交换，一般要求严格的同步 关系。要求各个节点在时隙的起始时刻才能收发数据，首先需要各个节点在时间上进行同 步，保证数据包所到达的时隙和发送的时隙恰好在某时隙的开始处，避免数据包的错误接 收【8 】。另外，网络的同步分为比特级同步和分组级同步两种类型。比特同步能容忍比特的 抖动；分组同步能容忍分组的抖动。在粒度上，又分为粗同步和细同步。为了保持比特率 笫7 页 南京邮电大学硕卜研究生学位论文 第一章绪论 和编码的端到端透明传输，粗、细同步都必须在光域完成。在同步实现过程中，时钟的恢 复与提取也是非常重要的，这涉及到o e o 的转换。 1 6 3 时延 在实际的各种网络拓扑结构中，任何两个节点之间的地理位置不可能完全相同。例如： 在环型网络中，相邻节点的距离无法完全保证相同；在星型网络中，各个节点到中心节点 距离也不可能完全一致。不同的传输距离必然导致不同的传播时延。由于传播时延不同， 可能会出现数据包发送或接收的时刻偏离某个时隙的起始时刻，无法实现同步；也可能会 造成到达某一节点的数据包在时间上有所重叠，从而使数据包无法正确接收。 本文中对上述问题不作详细研究，假设网络中各节点均已实现了同步，任意两点之间 的数据包的传播时延均已得到解决【9 l ，仅对分组交换光网络中的调度算法进行研究b o 。 参考文献 【l 】a m a c i i ，e m a c i i ，t w o l f , e ta 1 d e l a ya n dp a c k e tl o s sa n a l y z e so fi n p u tb u f f e r e da t m s w i t c ha r c h i t e c t u r e s j s y s t e m sa n a l y s i sm o d e l l i n gs i m u l a t i o n 19 9 7 ，2 8 ：6 9 【2 】j 一m c h u n g ，h m s o o j i t t e ra n a l y s i so fh o m o g e n e o u s t r a f f i ci nd i f f e r e n t i a t e ds e r v i c e s n e t w o r k s j i e e ec o m m u n i c a t i o n sl e t t e r s 2 0 0 3 ，7 ：13 0 3 “yp a n w a rs ，c h a oh j f r a m e b a s e dm a t c h i n ga l g o r i t h m sf o ro p t i c a ls w i t c h e s c ，i e e e h p s r 0 3 t o r i n o ，i t a l y , 2 0 0 3 【4 】卞佳丽编著现代交换原理与通信网技术【m 】北京：北京邮电大学出版社，2 0 0 5 【5 】d j b l u m e n t h a l ，p r p r u c n a l ，j r s a u e r p h o t o n i cp a c k e ts w i t c h e s ：a r c h i t e c t u r e sa n d e x p e r i m e n t a li m p l e m e n t a t i o n s c p r o c e e d i n g so f t h ei e e e ，1 9 9 4 ，8 2 ：1 6 5 0 【6 】e - s c h o a , x z h a o ，x y u ，e ta 1 a no p t i c a lp a c k e ts w i t c hb a s e do nw d mt e c h n o l o g i e s j l i g h t w a v et e c h n o l o g , , 2 0 0 5 ，2 3 ：9 9 4 【7 】张煦光通信网的光信号处理和光分组交换【j 】现代通信，2 0 0 4 1 0 ，0 0 1 ：3 - 5 【8 】z h a a s ，o p t i c a ls l o ts y n c h r o n i z a t i o ns c h e m e j e l e c t r o n i c sl e t t e r s ，1 9 9 2 ，2 8 ：2 1 8 4 - 2 1 8 5 【9 】ys j i n ，c h a n d r a s e k a r , s ，r a y b o n ，q ，e ta 1 s l o ts y n c h r o n i z a t i o ni nw a v e l e n g t h r o u t e ds t a r n e t w o r k sb a s e do nb r o a d c a s t i n gf r a m e sf r o mam u l t i f r e q u e n c yl a s e r j o p t i c a lf i b e r c o m m u n i c a t i o n sc o n f e r e n c e ，2 0 0 3 ，l ：13 0 - 131 【1 0 】马丽红，蔡祥宝带v o q 的输入队列交换网络中的分组调度算法研究【j 】光子技术， 2 0 0 6 9 ：1 6 7 - 1 7 0 第8 页 南京邮电大学硕士研究生学位论文 第二章交换体系结构与调度算法概述 第二章交换体系结构与调度算法概述 为了构造高性能的交换机，首先要解决好以下三个问题：1 ) 、交换结构：将分组从输 入端口交换到所需的指定输出端口的部件：2 ) 、队列：需要在输入( 或输出端) 设置缓冲 队列，缓冲由输入链路传输来的分组，避免仲裁时的分组丢失；3 ) 、调度：是一种策略或 算法，对于交换网络中的调度来说，就是在所有的输入端口和输出端口之间找到一个没有 冲突的匹配，控制分组的被服务次序并保证提供一定的q o s ，实现快速高效交换。 2 1 交换机内核结构 交换结构是实现宽带交换机的关键技术，直接影响着交换机的性能。光信号的分割复 用方式有空分、时分和波分三种，因而光交换结构相应地也存在时分、空分和波分三种， 它们分别完成空分信道、时分信道和波分信道的交换。时分交换结构是指，在时间轴上将 复用的光信号的时间位置f ，转换成另一时间位置t ，如共享存储器、共享总线、共享环等。 但由于容量受共享资源带宽的限制，通常不适合作为高性能交换机的结构；空分交换结构 由执行交换功能的交换单元构成，交换单元按照一定的拓扑形式相连接，通过对光开关矩 阵进行控制，建立任意一对光纤之间的物理传输通路，这种连接可在输入和输出端之间同 时建立多条路径，交换单元可根据分组的路由信息将其送往指定的输出端，使多个分组可 以同时通过交换结构。空分交换结构又分为纵横交叉连接( c r o s s b a r ) 、分离通路和b a n y a n 类网络等。 2 1 1c r o s s b a r 交换结构 由2 x 2 的光开关和其他的光开关( 如1 2 开关) 级联、组合，可以构成大型的空分光交 换单元。基于空分交换的纵横交叉式c r o s s b a r 网络结构，由于其内部无阻塞、交换速度等 于开关端口速度、内部工作在线速、具有较好的扩展性，并且允许多个分组同时穿过 c r o s s b a r 网络结构，降低了拥塞，因此是目前高速交换机使用较多的交换结构。它由2 个 可独立操作的交叉点组成，交叉点与二维矩阵有一种对应的映射关系，可以在任意输入与 输出端口间建立连接。每个交叉点有两种状态：r p c r o s s 和b a r 。当要在输入端口f 和输出端 1 2 1j 建立连接，只需要交叉点( f ，_ ，) 设置成闭合状态即可。c r o s s b a r 结构支持高带宽的原因 有两个：1 、将交换结构的物理连接简化为点到点连接，该连接的运行速率很高。2 、该结 第9 页 塑塞塑皇叁兰堡：! 堑窒生堂垡堡茎苎三童銮垫垡! 墨笙塑皇塑壅簦鲨竖垄 构可以支持多个连接并同时以最大的速度传输数据，极大地提高了整个系统的吞吐量。 一般高性能的c r o s s b a r 交换结构都采用了定长分组交换方式，在分组进入交换结构以 前，把它分割成一个个固定长度的数据包，在网络中进行转发( 例如在m p l s 网络中，数 据包根据被打上的标签进行转发；在a t m 网中，信元是依靠v p v c 来转发) ，通过交换结 构后再按原样把它组织成原来的变长分组。c r o s s b a r 交换一个分组的时间为一个时隙。基 于c r o s s b a r 的输入交换机能在低成本的条件下支持高速交换。 图2 1 是一个nx n 的基于c r o s s b a r 的交换机结构，它包含输入端口集x 和输出端口集y ， x = z ，fe n ，y = 一，n ) ，其中n 为自然数集。在输入端1 ：3 设置了个虚拟输出 队列( v o q ) ，解决链头阻塞( h o l ) h - 题。 = = 2 2 缓冲队列结构 图2 1 基于c r o s s b a r 的交换机架构 交换机中存在两种阻塞形式：内部阻塞和外部阻塞。所谓内部阻塞是指目的端口不同 的两个或两个以上的分组，需要经过一条相同的内部链路进行传送时，这些分组就在该链 路上产生冲突而形成内部阻塞。而当两个或两个以上的分组在相同时隙趋向同一个输出端 口时，就会出现外部阻塞。内部阻塞可以通过采用纵横交叉结构克服；而外部阻塞却是不 可避免的，需要在交换结构的不同位置设置缓冲区，缓冲方式分为输入队列缓冲、输出队 列缓冲。 2 3 交换机调度算法 根据分组缓冲队列的位置，可以把调度算法分为输入队列调度算法、输出队列调度算 法、组合输入输出队列调度算法三大类。目前研究的热点是带虚拟输出队列的输入队列调 第1 0 页 壹室堂皇查兰堡堕窒生堂垡堡文 笙三兰奎垫竺壅笙塑：兰塑壁蔓鲨塑垄 度算法。为交换机设计一个好的调度算法至关重要，在每一个分组周期之前，调度器根据 输入队列的状态决定数据通道，即决定某段时间内输入和输出端口间的无冲突的匹配关 系，再把调度决定并行传给输入端口和交叉结构。交叉开关用这个配置来决定每个交换单 元的开关，而如何在交叉开关内选择不冲突的配对就是调度算法要研究的问题。 2 3 1 输出队列调度算法 传统的交换机大多采用输出队列( o m p u tq u e u i n g 简称o q ) 交换结构，即分组缓存被置 于交换机的输出端。输出队列交换机也被称为共享缓存交换机，去往各个输出端口的分组 共享缓存。到达输入端口的分组被立即送往输出端口，各个分组在输出端口排队。输出队 列可以实现交换机的最大吞吐率，另外，输出排队管理策略可以通过精确控制不同链路中 不同分组的离开时间，来控制分组的延迟，以提供不同的q o s 保证。该调度算法在理论上 已得到深入研究，其应用特点是实现简单。但输出排队交换机制有一个很大的问题是需要 n 倍的加速比，也就是说在一个n n 端口的交换结构里，内部带宽和输出队列速率必须是 输入速率的倍。随着光通信技术的发展，线速已经达到1 0 g b p s ( o c l 9 2 ) 甚至4 0 g b p s ( o c 7 6 8 ) ，当端口数增加，所需共享缓存的读写速率和数量都迅速上升，具有，倍加速比的 交换结构和存储器在当前的技术条件下难于实现【i 】，所以不适于高速交换机。 2 3 2 输入队列调度算法 目前高性能交换机一般采用输入队列( i n p u tq u e u i n g 简称i q ) 交换结构。在各输入端的 缓冲区中设置一个f i f o ( 先入先出) 队列，用以缓冲尚未得到服务的业务流，每次调度取 位于队首的分组进行输出。存储器可以工作在链路速率，不需要加速比，可扩展性大大优 于输出队列结构。同时输入队列交换结构比传统的共享存储交换阵列能提供更大的交换能 力。然而，在f i f o 队列中，只有每个队列头的分组能被服务，当队列头的分组受阻时， 跟在其后的所有准备发送的分组也将受阻。既使在当前时隙内，第一个分组之后的所有分 组的目的端口处于空闲状态，也无法在此时参与交换，这种现象即称之为链头阻塞 h o l m e a do f l i n e ) 现象，严重降低了内部带宽的利用率。 每个时隙到达时，只有在缓冲器队列中的第一个分组( 头分组) 才能参与对输出端口 的竞争，且每个输出端口最多只能接收一个分组。若输入端口只采用简单的f i f o 队列机 制，当分组到达服从到所有输出端口独立均匀分布的贝努乖l j ( b e m o u l l i ) 分布，趋近无穷 时，吞吐率只能达到5 8 6 【2 】，而周期性的链头阻塞可能导致更差的效果。因此，输入队列 第1 l 页 南京邮电大学硕士研究生学位论文 第2 2 章交换体系结构与调度算法概述 交换机在2 0 世纪9 0 年代前未得到广泛研究。近几年，随着链路速率和存储器速率矛盾的 r 益突出，输入队列调度算法【3 1 引起了研究人员的普遍重视。 2 3 3 带v o q 的输入队列调度算法 为了克j 艮h o l 阻塞，人们提出了各种基于缓冲结构的排队策略及其调度算法。h l u c h y j 提出了窗口接入技术【4 】，其实质是放弃f i f o ，允许输入缓存器前形个( 矿表示窗口大小) 分组参与对输出端口的竞争，使输出线获得最大限度的利用，但该方法并不能完全消除 h o l 阻塞，其最大吞吐率只能达到9 4 。另外一种方法是提高内部工作速率，但实现起来 很困难。 采用虚拟输出队列( v i r t u a lo u t p u tq u e u e 简称v o q ) 的方案【5 】可以彻底消除h o l 阻塞， 而且克服了输出队列交换机中存储带宽与端口数成正比的缺点，提供低成本的高速交换， 因此得到了广泛应用，但前提是需要有可靠的调度算法作技术保证。一个nxn 交换结构 模型，将输入缓冲区设置成多重队列，即每一个输入端口设有个f i f o 队列，分别缓存发 往个输出端口的分组，这种缓冲策略称为虚输出队列( v