（通信与信息系统专业论文）obs核心节点调度算法研究与dsp实现.pdf

摘要 摘要 近年来随着技术的广泛应用和对带宽需求的不断上升，波分复用技术己经 被广泛应用。传统的分层网络结构已经不能适应对网络的发展要求，i po v e rw d m 将成为下一代网络的首选结构。光突发交换结合了光电路交换和光分组交换两种 交换技术的优点同时克服其缺点，是一种实现i po v e r w d m 全光互联网的最有竞 争力的交换技术。但由于目前没有成熟的光缓存器件，在光域不能对突发进行随 机存储，而f d l 只能提供有限的时延。因此，o b s 网络的突发丢失率相对于电域 分组交换网要高很多，为了降低突发丢失率提高信道的利用率，研究和设计高效 的调度算法是o b s 领域研究的重点和热点。 在o b s 网络中，核心节点调度算法丢失性能的优劣影响整个网络的性能。第 二章用排队理论分析插空和不插空调度算法的理论丢失性能，并针对o b s 突发丢 失的实际情况提出了分析突发丢失的实际模型，并应用这模型对调度算法进行理 论分析和仿真比较，结果表明爱尔兰b 公式只是突发丢失的理论下限。 第三章提出基于装箱策略的f f d 和b f d 核心节点调度算法。f f d 和b f d 调 度算法是首先将b h p 在核心节点进行缓存、按出端口分类排序、再集中调度，而 不是按照b h p 的到达顺序进行依次调度处理，并对资源表中的波长信道按空闲时 间按降序排序，按首次适应和最佳适应的策略对b h p 对应的突发进行调度处理。 通过该调度算法，可以实现高优先级突发对低优先级的抢占，提供服务质量支持， 并利用o p e n e t 仿真软件对这两种调度算法进行仿真。仿真结果表明，基于装箱 问题的f f d 和b f d 调度算法不仅能提供有效的q o s 支持，还能改善系统总体的 丢失性能。 第四章研究了核心节点调度算法单a d s p 2 1 9 1 芯片实现。应用v i s u a l d s p 3 5 软件仿真对调度算法的实时性能进行时间处理测试。结果表明单片a d s p 2 1 9 1 芯 片不能够满足核心节点对b h p 的实时处理要求，必须多d s p 并行处理。第五章研 究了核心节点调度算法的多d s p 并行处理。对多b h p 批调度算法的实现进行分析， 探讨了多b h p 处理任务的的划分和分配方案；多d s p 间数据通信和传输的d m a 实现；最后对多处理器并行的处理时间进行仿真测试分析。结果表明b h p 处理时 延能够满足核心节点对b h p 处理时延的要求。 关键词：光突发交换，调度算法，服务质量，装箱问题，多d s p 并行处理 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，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 i n g ( w d m ) t e c h n o l o g yh a sb e e n u s e dw i d e l y t h et r a d i t i o n a ll a y e r e dn e t w o r ka r c h i t e c t u r ea l r e a d yc a n ta d a p tt h er e q u e s t o fd e v e l o p m e n tt ot h en e t w o r k ，i po v e rw d mi sc o n s i d e r e da st h ec o r ea r c h i t e c t u r ef o r t h en e x t - g e n e r a t i o no p t i c a li n t e r n e t o p t i c a lb u r s ts w i t c h i n g ( o b s ) ，w h i c hc o m b i n e st h e m e r i t so fw a v e l e n g t hr o u t i n ga n do p t i c a lp a c k e ts w i t c h i n gw h i l ea v o i d i n gt h e i rd e f e c t s ， i sf o c u s e do na san e wd a t at r a n s m i s s i o na n ds w i t c h i n gs c h e m et or e a l i z ei po v e rw d m c o m p a r i n gw i t hc i r c u i tp a c k e ts w i t c h i n g ，t h el o s sr a t eo fb u r s ti no b sn e t w o r k si s m u c hh i 【g h e rb e c a u s eo fa b s e n s eo f m a t u r eo p t i c a lb u f f e rc o m p o n e n t s h o wt od e s i g ne f f i c i e n ta l g o r i t h mf o rs c h e d u l i n gb u r s t si sak e yp r o b l e mi no b s n e t w o r k s c h a p t e r2u s eq u e u et h e o r yt oa n a l y s et h el o s sr a t eo fs c h e d u l i n ga l g o r i t h m s a m o d i f i e da n a l y t i c a lm o d e li s p u tf o r w a r dt oa n a l y z ea l g o r i t h m s w i t ho rw i t h o u t v o i d f i l l i n g t h ea n a l y t i c a la n ds i m u l a t i o nr e s u l t ss h o wt h a tl a u c v fh a st h el o s s p e r f o r m a n c ev e r yc l o s et ot h el o w e rb o u n dc a l c u l a t e db ye r l a n gb f o r m u l a i nc h a p t e r3 ，t w on o v e ls c h e d u l i n ga l g o r i t h m sa r ep u tf o r w a r dt os u p p o r t i n gq o s a c c o r d i n gt ob i np a c k i n gp r o b l e m b h p sa r r i v i n ga r es e n tt od i f f e r e n tq u e u e sa c c o r d i n g t ot h e i ro u t p o r t ，i ne a c ho u r p o r tq u e u e ，b h p sa r ec l a s s i f i e db yt h e i rp r i o r i t i e sa n d s c h e d u l e da sab a t c h t h es i m u l a t i o nr e s u l t ss h o w st h a tf f da n db f dn o to n l yc a n p r o v i d eq o se f f e c t i v e l y , b u ta l s oc a ni m p r o v et h ea v e r a g el o s sf u n c t i o n c h a p t e r4s t u d i e ss c h e d u l i n ga l g o r i t h mo ft h ec o r en o d et oi m p l e m e n to ns i n g l e a d s p 2 1 9 1 t h er e s u l ts h o w st h a tas i n g l ea d s p 2 1 9 1c h i pc a n t s a t i s f yt h eb h p p r o c e s s i n gd e l a yr e q u e s ta n dp a r a l l e lp r o c e s s i n g i si n e v i t a b l e c h a p t e r5p r i m a r i l y s t u d i e st h ec o r en o d e ss c h e d u l i n ga l g o r i t h mw i t hm a n yd s p p a r a l l e lp r o c e s s d e t a i l so f l a u c - v fs c h e d u l i n ga l g o r i t h ma n a l y s i sd a t af l o wo r g a n i z a t i o na n dm i s s i o n d i s t r i b u t i o na r ea r g u e d t h er e s u l t so fs o f t w a r es i m u l a t i o na n dh a r d w a r ed e b u g g i n g i n d i c a t et h a tm a n yd s pp a r a l l e lp r o c e s s i n gi se f f e c t i v ea n dc o i n c i d e n tw i t ht h es y s t e m s d e m a n d k e y w o r d ：o p t i c a lb u r s ts w i t c h i n g ，s c h e d u l i n ga l g o r i t h m ，q u a l i t yo fs e r v i c e ，b i np a c k i n g p r o b l e m ，m a n yd s pp a r a l l e lp r o c e s s i n g i i 主要符号表 缩略词 主要符号表 o b s o p t i c a lb u r s ts w i t c h i n g 光突发交换 b h p b u r s th e a d e rp a c k e t控制分组 d b d a t ab u r s t突发数据 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 i n g 波分复用 d w d md e n s ew a v e l e n g t hd i v i s i o nm u l t i p l e x i n g 密集波分复用 f d lf i b e rd e l a yl i n e 光纤延迟线 l a u cl a t e s ta v a i l a b l eu n s c h e d u l e dc h a r m e l 最近可用时间 l a t e s ta v a i l a b l eu n s t h e d u l e dc h a n n e l l a u c v f 最近可用插空 v o i df i l l i n g o c s o p t i c a lc i r c u i ts w i t c h i n g 光链路交换 o p s o p t i c a lp a c k e ts w i t c h i n g 光分组交换 t w ct u n a b l ew a v e l e n g t hc o n v e r t e r 可调波长变换器 b b pb i np a c k i n gp r o b l e m 装箱问题 q o sq u a l i t yo fs e r v i c e 服务质量 f f df i r s tf i td e c r e a s i n g降序首次适应 b f d b e s tf i td e c r e a s i n g降序最佳适应 v i i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：4 五玉旌 日期：州年j 月“日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：葺崞导师签名：堑簟耻 e l 期：沙6 年1 - 月日 第一章绪论 1 1 引言 第一章绪论 2 1 世纪是一个以网络为核心的信息时代，人们对信息的需求与日俱增。全球 范围内i p 业务的迅速增长，对传送网带宽和交换系统容量的要求愈来愈高，现有 的网络结构，已经造成业务拥挤，带宽“枯竭”的情况，必然要求新一代网络一 全光网络的诞生。全光网络( a o n ，a l lo p t i c a ln e t w o r k ) 是未来信息网络的核 心，以光节点取代现有网络的电节点，在光域完成信号的传输、交换等功能，克 服了现有网络在传输和交换时的电子瓶颈，降低了信息传输的拥塞，大大提高了 网络的吞吐量。 波分复用( w d m ，w a v e l e n g t h d i v i s i o n m u l t i p l e x i n g ) 【l 】技术是目前光纤骨干网 普遍采用的一种传输技术，光纤信道的容量得到了极大的提高。目前在实验室中 w d m 技术已经能在一根光纤中同时传输8 0 一1 2 0 个波长，而每个波长的传输速度 可以达到4 0 g b s ，总容量大于1 0 t b s 。并且由于密集波分复用( d w d m ) 技术的成 熟，为通信网络提供了更巨大的传输容量，d w d m 【2 技术逐步成为主流传输技术。 而在交换部分，由于电域处理的速度仅几个g b s ，电子元件处理速度的提高成为 整个网络性能提高的瓶颈。于是，光纤通信网的性能瓶颈就转移到了交换设备部 分。为了克服这个瓶颈，进而实现透明的、具有高度生存性的全光通信网，目前 许多研究机构致力于研究和开发光交换技术，试图在光层实现全光通信，消除电 子瓶颈的影响。当全光交换系统成为现实，就可以满足飞速增长的带宽和处理速 度需求，同时减少多达7 5 的网络成本，具有诱人的市场前景。 1 2 光交换技术 目前i po v e rw d m 光网络的光交换技术主要有三种方案3 1 ，光路交换( o c s ， o p t i c a lc i r c u i ts w i t c h i n g ) 4 1 、光分组交换( o p s ，o p t i c a lp a c k e ts w i t c h i n g ) 5 6 1 和光突 发交换( o b s ，o p t i c a lb u r s ts w i t c h i n g ) m 1 。 电子科技大学硕士学位论文 1 2 1 光路交换( o c s l 光路交换方式使用和电路交换方式相似的运行机理，它采用o x c 、o a d m 等 光器件设置光通路，中间节点不需要使用光缓存。光路交换具有速度快、带宽大、 对数据速率及格式透明的优点，特别适用于s d h ( s y n c h r o n o u sd i s t a lh i e r a r c h y ) 网络，缺点是对于高突发性的数据业务带宽利用率不高，不适合于高突发性的i p 数据业务。 1 2 2 光分组交换( o p s ) 光分组交换技术是电分组交换向光层的渗透和延伸，采用面向非连接的“存储 转发”的原则，以光分组来存储和转发业务数据，不需要建立实际的物理链路， 采用单向预约机制。光分组交换是一种细粒度的交换机制，由于它允许统计复用 网络通道带宽资源，因此特别适合突发性的数据业务。就承载突发性大并且分布 非对称的i p 数据业务而言，o p s 技术具备高速、高效、高度灵活性、透明性等诸 多优势。但由于受目前光存储和光信息处理技术的限制，在今后相当长一段时间 内，o p s 的应用前景并不看好。 1 2 3 光突发交换( o b s ) 9 , 1 0 1 光路交换( o c s ) 以波长作为网络资源的基本调度单位，因粒度太大而缺乏灵 活性，尤其不适合具有自相似、高突发的数据业务，而o p s 又面临短期内难以克 服的光“处理瓶颈”限制。为充分利用电子技术的处理优势和光子技术的速度优 势，c h u n m i n gq i a o 和j s t u m o r s l 等人提出了光突发交换( o b s ，o p t i c a lb u r s t s w i t c h i n g ) 的概念。与o c s 和o p s 相比，由于o b s 具有突发中等粒度且长度可 变；带宽利用率较高；控制信息和突发数据分离波长信道传送；资源预约灵活以 及中间节点无需缓存等特点，因此o b s 逐渐成为光通信领域的研究热点之一。 1 3o b s 概述 1 3 1 o b s 网络基本构成 o b s 网络基本结构如图l 一1 所示，由边缘节点( e n ，e d g en o d e ) 、核心节 点( c n ，c o r en o d e ) 以及d w d m 链路构成。边缘节点负责对突发数据包( b u r s t ) 的 2 第一章绪论 汇聚和解汇聚功能，并提供各种网络接口，使之可以和其他协议类型的网络互联。 核心节点主要由光交换矩阵( o s m ，o p t i c a ls w i t c h i n g m a t r i x ) $ 1 交换控制单元( s c u ， s w i t c hc o n t r o lu n i t ) 组成。 图1 - 1o b s 网络模型 边缘节点 1 2 1 功能如图1 2 所示，由接口、排队、汇聚懈汇聚、调度、交换和 接收发射功能模块组成。接口模块对各类传送数据的转换及校验功能；排队模块 根据一定的准则将接收到的数据分组进行排队；汇聚模块将多个数据分组合并成 一个突发数据包并产生相应的控制分组( 解汇聚模块进行反操作) ；调度模块的 主要功能是设置偏移时间；交换模块根据各数据分组的目的地址进行转发。 警畦茎凄耀嘲 陵趔信鳖而磊丽磊丽磊闺 + 图1 - 2o b s 边缘节点功能图 核心节点结构如图1 3 主要由交换控制、协议处理、光交换矩阵和线路接1 3 等 功能模块组成。交换控制模块完成处理信令、查找转发路由表、预约资源、调度 和处理资源冲突等功能；协议处理模块主要实现高层协议的处理，包括转发路由 表的维护与更新等；光交叉模块主要由光交换矩阵、光纤延迟线( f d l ，f i b e r d e l a y 电子科技大学硕士学位论文 l i n e ) 和可调的波长转换器( t w c ，t u n a b l ew a v e l e n g t hc o n v e r t e r ) 组成，在控制处 理模块的控制下，为突发数据提供透明光通道。线路接口模块包括m u x 、d m u x 和e d f a 等器件。 1 3 2o b s 的基本原理 图1 - 3 0 b s 核心节点结构 o b s 采用分离的波长来传输突发数据和它们的控制信息。o b s 中的“突发” 可看成是由一些较小的数据分组( m 分组) 组成的超长数据分组，由分组头( b h p ， b u r s th e a d e rp a c k e t ) 和数据两部分组成。b h p 和突发数据在光信道上分离，一般 用一个波长作为数据信道，b h p 和突发数据一一对应，b h p 先于突发数据发出， 二者的时序关系由o b s 采用的资源预留协议来确定，如j i t ( j u s t - i n t i m e ) 1 3 , t 4 、 j e t ( j u s t - e n o u g h - t i m e ) 7 , 1 5 , 1 6 协议。b h p 中包含突发数据的有关信息，如偏移时间、 突发数据的长度、波长信道等。 o b s 网络采用w o m ( 或d w d m ) 技术连接各个节点，w d m 信道组中的一个或 多个波长传输控制分组，称为控制信道，其它波长传输突发包，称为数据信道。 在网络的中间节点处，突发数据不需要转换成电信号进行处理，以光信号透明传 输，而b h p 需要转换成电信号进行处理，包括为突发数据确定路由、预约资源以 及配置光交换矩阵等，以保证当突发数据到达时相应的数据通道己配置好。 4 第一章绪论 1 4o b s 关键技术及研究动态 o b s 技术作为下一代全光网络的一种解决方案，已经引起越来越多研究者的 关注，o b s 的关键技术包括光突发装配、资源预留协议( r e s e r v a t i o ns c h e m e sa n d p r o t o c o l s ) 、信道调度算法、网络服务质量( q o s ) 和冲突处理策略等方面，也是 目前o b s 技术研究的热点问题。 1 4 1 光突发装配技术 突发装配是o b s 网络中一个重要研究主题，o b s 边缘节点作为核心光网络技 术与周围低速网络的连接，其突发汇聚和封装问题 1 7 - 2 3 1 也是边缘节点的关键技术 之。常见的突发装配策略有两种【2 4 0 5 】：一是基于时间( t i m e - b a s e d ) i 拘；二是基于 阈值( t h r e s h o l d - b a s e d ) 。在基于时间的突发装配法中，突发是以固定间隔产生， 并周期性地注入o b s 网络。 1 4 2 资源预留协议 o b s 网络的资源预留协议是突发包和控制包传输时序的关系控制。o b s 一般 常采取单向瓷源预留方式，与双向预约协议相比，首先单向预约可简化光突发接 入控制，即使没有足够的资源，网络也会接入突发，而此时只是简单地丢弃这突 发；其次它还可大大降低了网络时延，因无确认预留就能减少这类传播时延对网 络性能( 如：吞吐量) 的影响。单向预留协议可以为三大类：一是j i t ；二是基 于r l d ( r e s e r v el i m i t e dd u r a t i o n ) 的h o r i z o n t s l ；三是基于r f d ( r e s e r v e f i x e d d u r a t i o n ) 的j e t 。j i t 协议采用发送额外的跟踪控制分组或者带内结束符i b t ( i nb a n dt e r m i n a t o r ) 的方式告之光突发结束位置。r l d 可有效地改进了j i t 协 议，要求源方在预留请求b h p 中告之突发长度。r f d 在预留资源时同时考虑突发 的开始时间和结束时间，信道可仅被预留一段与突发传输时间相当的确定时间。 j e t 协议是基于r f d 的典型，j e t 协议使不同业务的优先级与偏移时间相联系， 对于高优先级突发，给予较大的偏移时间，这样该突发能成功预留所需资源的可 能性就越大，那么它的丢包率也会较低。因此j e t 协议在o b s 网络中应用广泛。 1 4 3 信道调度算法 由于o b s 网络光缓存能力有限，如何降低网络的丢包率是一个十分重要的课 电子科技大学硕士学位论文 题，影响突发丢失率的因素比较多，如交换结构、资源预留协议、调度算法等。 在结构和协议确定的情况下，设计高效的调度算法将影响o b s 网络的突发丢失性 能，突发的丢失率决定于o b s 网络对突发冲突的有效解决。而调度算法的研究主 要是为了提高信道利用率和减少突发的丢失率，同时还要兼顾复杂度和运算时间。 1 5o b s 核心节点调度算法研究现状及进展 调度算法根据控制分组为相应的突发数据分配信道资源，其性能优劣对o b s 网络的性能好坏起到关键性的作用。由于突发数据信道调度问题是n p c 问题，设 计高效调度算法是目前o b s 研究领域的热点和难点。针对o b s 核心节点，目前已 经提出了多种调度算法。 一是基于突发数据或b h p 到达时间顺序调度算法。其中f f ( f i r s tf i o 算法最简 单最直观，没有采取任何优化措施，因而出现大的空隙和信道利用率低。j o n a t h a n s t u r n e r 等提出l a u c ( l a t e s ta v a i l a b l eu n s c h e d u l e dc h a n n e l ) 8 , 2 4 , 2 6 】算法，由于利 用最近可用信道，使信道的空隙有所减少。y x i o n g 等人在l a u c 的基础上进行 改进，提出了插空的l a u c v f ( l a t e s t a v a i l a b l eu n s c h e d u l e dc h a n n e lw i t hv o i d f i l l i n g ) 1 2 6 算法，对波长信道的空隙插空，提高了信道的利用率降低了突发数据的 丢弃率，但调度顺序是按控制包到达的时间进行资源预约的，因此存在潜在的冲 突而造成突发的丢失。c h a n g 和p a r k 提出了一种按照突发包到达顺序分配信道的 f a f a v f ( f i r s ta r r i v a lf i r s ta s s i g n m e n tw i t hv o i df i l l i n g ) 口”调度算法，降低了潜在 的冲突可能，提高信道利用率。 二是基于多b h p 的批调度算法。上述调度算法是基于控制包或突发到达的时 间依次调度处理进行资源预留，由于突发数据、控制包头的相关性和光交换结构 等特点，突发数据的调度问题是n p c 问题。如何对突发分配进行组合优化，提高 信道利用率和降低突发数据丢弃率。s a r v u t 等提出了多b h p 集中分批调度算法， ( g r o u p s c h e d u l i n g ) 2 s l 调度算法，该调度算法是收集在一段时间内的所有到达核心 节点的b h p ，按照突发数据的到达时间和结束时间进行分类，然后对每个分类队 列的b h p 进行调度，应用组合优化方法进行资源分配。y a n j u nl i 提出的批调度算 法( b a t c h c h a r m e l s c h e d u l e a l g o r i t h m ) 口，在重复周期时间内收集b h p ，然后对b h p 按信道分组进行分类，应用l a u c - v f 作为调度的子算法进行调度处理。w e i t a n 提出了支持服务质量的批调度算法( q o s b a s e db a t c hs c h e d u l i n g ) l3 0 ，对每个b h p 延 迟一定时间，收集多个b h p 进行分类，并对高优先级的服务优先服务的原则进行 第一章绪论 调度，采用l a u c v f 作为子算法进行信道分配。 1 6 本文研究的主要内容及章节安排 本文研究的主要内容是o b s 核心节点的调度算法，即根据光突发的控制信息 ( 包括突发长度、偏置时间、输入波长等) 和核心节点的资源表( 主要是路由转发表 和光交换模块各输出端口的资源占用情况等) 进行资源的调度和仲裁，最终提供对 光交换矩阵、f d l 和t w c 的配置信息，为突发数据建立全光透明通路，提高信 道的利用率和降低突发数据的丢失率。 论文的第二章研究了调度算法突发丢失性能。首先分析和总结了调度算法突发 冲突机制的处理策略；其次结合排队理论对o b s 核心节点调度问题进行理论分析， 在此基础上提出分析调度算法丢失性能的模型，并利用该模型对l a u c 和 l a u c v f 算法进行性能分析；最后结合仿真和理论分析，对l a u c 和l a u c 一 算法进行性能比较。 第三章提出两种新型的支持q o s 的批调度算法。首先结合装箱问题和o b s 调 度问题的相关性分析，建立o b s 核心节点批调度模型，对窗时间内的突发进行排 队、分类调度，提供对q o s 支持的批调度算法；并对调度窗时间进行分析，得出 最大的重复周期；最后应用o p n e t 软件对该该调度算法进行仿真比较其性能优 劣。结果表明，该调度算法不仅能有效的为各种优先业务提供服务，而且比b h p 顺序调度算法在丢失性能上有较大的改善。 第四章主要研究o b s 核心节点调度算法的单d s p 实现。先讨论了8 x 4 x 4 的 核心节点光交换结构，确定突发冲突的处理策略；分析了o b s 核心节点的一些关 键参数，如b h p 的处理时延等；最后对l a u c v f 算法在单片a d s p 2 1 9 1 上的实 现，并应用v i s u a l d s p 软件仿真分析调度算法的b h p 处理时间。结果表明，单片 d s p 对b h p 进行调度处理达不到o b s 网络对b h p 处理时延的要求。 第五章主要对o b s 核心节点调度算法的多d s p 并行处理研究。结合o b s 核 心节点调度问题的特点，提出了一种可用重构的多d s p 并行处理硬件平台，用 f p g a 实现多d s p 互联；数据通信协议和方法，接着探讨了调度算法的并行任务 划分和分配，设计多b h p 批调度的多d s p 并行实现，用l a u c v f 作为调度的子 算法进行信道搜索。结果表明，调度算法的多d s p 并行比单d s p 处理提高了数据 处理的吞吐量，增强了b l i p 处理的实时性能。 电子科技大学硕士学位论文 第二章o b s 核心节点调度算法及其性能分析 本章首先讨论了核心节点调度算法及其冲突处理策略，应用排队理论分析调度 算法的丢失性能，分析调度算法在处理冲突时丢失情况分析，得出调度算法丢失 性能的模型，最后应用丢失模型和理论分析对l a u c 算法和l a u c v f 算法进行 分析，和仿真结果进行比较调度算法性能的优劣。 2 1o b s 调度算法的描述 o b s 信道调度算法，就是网络节点根据资源预约请求，为相应的突发数据包 分配一条合适的出端口波长信道。o b s 调度算法首先必须简单快速，这对于构建 可扩展的网络至关重要，因为节点如果具备较小的处理时延和较高的处理速度， 既有助于减小端到端的业务延时，也有助于缓解节点在高负载下的处理拥塞，降 低突发包阻塞率。其次，调度算法必须高效的带宽利用率和低的突发丢失率。由 于目前缺少成熟的光缓存器件，和电域分组交换相比，o b s 交换的突发丢失率要 高得多，高效的调度算法能在一定程度上降低突发丢失率提高信道利用率。o b s 网络将控制信道与数据信道相分离，采用延迟预约，因而o b s 调度会在信道上产 生间隙，所以性能好的o b s 调度算法必须能够有效地利用这些间隙，以提高带宽 利用率。最后，调度算法能够对高优先级业务提供q o s 支持。尽管o b s 网络采 用p j e t ( p r i o r i t y j e t ) 协议可以简单地实现q o s ，但是节点上过大的处理排队时 延往往会扰乱q o s 分级，因此有必要在调度中引入额外的q o s 机制，非常有必要 调度算法能提供对关键业务的q o s 支持。 2 2o b s 调度算法的冲突处理策略 在o b s 网络中，如果两个以上或多个输入光突发在相重叠的时间区间内交换 到同一个输出端口或波长信道时，光突发的传输必然发生冲突。突发竞争的有效 解决，是设计o b s 网络数据信道调度算法的关键问题之一。为了解决突发的冲突， 目前调度算法采取的主要思路有：( 1 ) 减少竞争发生；( 2 ) 竞争发生后尽量消除；( 3 ) 如不能消除则尽量减小竞争造成的数据丢失。 第二章o b s 核心节点调度算法及其性能分析 1 、f d l 光缓存冲突处理 由于突发数据完全在光域处理，不进行0 e o 变换，因此必须采用全光的缓 存技术。由于光存储技术的限制，没有类似随机存储器r a m 的光器件，光域的 缓存很难实现，目前只能采用f d l 的方式来实现，由于f d l 不是真正的随机存 储器，只能提供有限的时延。 目前有关f d l 的结构口l 】研究比较多，其关键参数有f d l 单位延迟d 和级数q 。 d 是一个重要参数。d 值过小，缓存容量差；d 值过大，选择时间分辨率低，所以 应使用折中的d 值，使突发数据的丢失概率不太大。当单位延迟d 增加时，f d l 的容量也随之增加，突发的丢失率会减少，但f d l 是以d 为单位的分配延时而不 是随机延迟的，所以当突发竞争冲突进入f d l 延迟时，会产生空隙。如果没有利 用这些空隙，虽然减少了单个突发数据的丢失，但反而会使系统的资源利用率降 低，而且f d l 的单位延迟大小对系统性能影响不同。由于缓存的大小受限于信号 质量以及交换机的物理空间( 因为缓存一个突发5l ls 就需要至少一千米长的光 纤) 。因而这种方式不能有效的解决高负载情况下的突发冲突。 2 、t w c 波长变换冲突处理 当突发数据到达核心节点，如果与其输入信道具有相同波长的输出信道正处于 “忙”状态，则可以将该突发数据由原输入波长转换到其他波长上输出，从而消 除突发之间的竞争。这种在电信号的控制下完成入波长变换到其它波长的可调波 长变换器t w c 可以有效的解决突发冲突。 从排队论的角度来考虑，在只配置了波长变换器，而无光纤延迟线的这种交换 排队系统，可以视为是多窗口损失制的排队模型。在这种排队模型下，突发数据 包到达时，若无可用的信道可以交换，则马上被丢弃。因此要在这种排队模型下 降低交换的丢包率，就只有从增加可用信道( 即服务窗口数) 的角度出发。另外， 每个数据包所需要占用的系统服务时间也是一个影响交换性能的重要因素。 当存在多个波长信号要同时交换到同一输出端口的同一波长时，可以将其中几 个波长先变换为输出端口其他的空闲波长，再交换到同一输出端口中去。由于目 前全光波长变换技术还不够成熟，必然限制每次调度可用的数据信道，使得该方 法在业务负载较重时难以真正的解决冲突。可调谐波长变换器对交换节点的交换 性能的改善有一定的作用，但是其作用有限，在高负载的情况下，不能单靠使用 波长变换器来解决竞争的问题。 波长备份( w a v e l e n g t h d i m e n s i o n ) 解决突发冲突。波长备份是为每条链路预留多 个备份波长( 或备份光纤) ，一旦出现冲突，可以通过将部分冲突的突发数据调整到 9 电子科技大学硕士学位论文 备份波长进行传输。需要注意的是，若能在同一链路上提供多条光纤，则可以在 一定程度上避免使用( 或减少使用) 波长变换器，例如，两个突发数据同时需要交换 到某端口的波长1 上，多光纤配置意味着存在另一端口与该端口“等效”( 连接的 是同一个设备) ，此时可以将其中一个突发数据交换到等效端口的波长1 ，即可解 决冲突，而不必使用波长变换。 2 3 o b s 核心节点突发丢失模型 排队论在计算机，计算机网络，通讯方面的应用主要开始于七十年代。借助排 队理论来对o b s 网络性能进行分析。如果每个输入、输出端口有n 条波长信道， b l i p 到达过程为泊松过程，在一个端口b h p 的到达速率为九，每个波长信道上到 达的速率为l k ，突发数据长度服从参数为“的负指数分布，可以采用m m n n 作 为核心节点的排队模型。 2 3 1 核心节点交换结构 调度算法的研究必须建立在特定的光交换结构基础上，反过来，不同的光交换 结构影响调度算法的性能。光交换结构是o b s 核心节点物理层的核心，调度算法 和冲突解决方法是核心节点的交换控制部分。光交换结构和交换控制部分之间是 关系密切的，交换控制部分的设计必须建立在确定的光交换结构基础之上，调度 算法和冲突解决方法必须建立在特定的光交换结构基础上进行分析。 2 3 1 18 4 x 4 + f d l 结构 图2 - 1 结构由一个m 个p x p 的光空分交换阵、p 个波分复用器、p x m 个f d l 组成。其中尸是端口数，m 是每根光纤中的波长数。每个入端口的每个波长上都 配置了一个f d l 。 f d l 的构造方式如图2 2 所示。f d l 由足级1 2 光开关、一个合波器、以及 延迟光纤构成。每级l 2 光开关都有2 路输出，其中1 路经延迟光纤后与下一级 光开关的入口相连；另1 路直接与f d l 出端的合波器相连。每级延迟光纤长度都 是相同的。其延迟时间称为单位延迟，记为d 。光开关个数k 称为最大延迟级数， 相应地，f d l 的最大延迟时间为d = k d 。通过合适地配置这k 个1 2 光开关， 经过f d l 的突发包所经历的延迟可以取集合 o ，d ，2 d ，x d 中的任何一个值。 1 0 第二章o b s 核心节点调度算法及其性能分析 图2 18 4 4 + f d l 结构 图2 - 2f d l 结构 2 3 1 28 4 4 + t w c 结构 图2 3 采用了8 4 x 4 的结构，即有8 个交换平面，每个交换平面4 入4 出， 整个交换结构有4 根光纤入，4 根光纤出，每根光纤上面跑8 个波长，在每一路输 入波长上都配一波长变换器，输出到交换平面的对应入脚，经过交换平面交换以 后输出到出端口，因此共需要4 8 个波长变换器( t w c ) 。 电子科技大学硕士学位论文 在该图里面，p ，m 分别表示核心节点的端口数和波长平面数。对应于8 4 4 + t w c 结构模型来说，p 等于4 ，m 等于8 。 2 3 2 无f d l 的核心节点突发排队模型 假定系统内有n 个服务窗，事件按泊松流到达系统，其强度为 。倘若事件 到达系统时发现1 1 个服务窗均忙时，该事件即离开系统另求服务。这种系统就是 多服务窗损失制排队模型3 2 】m m n n 。假设系统各服务窗的服务时间服从负指数 分布，其强度为u 。则该排队系统的损失概率为： p 。= 鲁p 。 ， r 。f 娜p k7 l ( 2 2 ) 其中p2z ，称为业务强度，等于到达率与服务率的比值。表示系统的负 荷水平。公式2 - 2 表示n 个窗口均空闲的概率。不配置光纤延迟线的o b s 核心交 换节点排队交换系统即为这种排队模型。 1 2 第二章o b s 核心节点调度算法及其性能分析 2 3 3 配置f d l 的核心节点的突发排队模型 假定系统内有n 个服务窗，事件按泊松流到达系统，其强度为九。假设该系 统的各服务窗各自独立工作，服务时间服从负指数分布，其强度为p 。假定系统 的容量为m ，即系统最多可以容纳m 个事件( m n 1 ) 。该系统有m n 个供事 件排队等候的位置。倘若事件到达系统时发现1 1 个服务窗均忙，该事件则进入等 候的位置进行等候，若等候的位置也是满的，则离开系统另求服务。这种系统就 是多服务窗混合制排队模型 3 3 】m a w r g n 。则系统的损失概率( 丢包率) 为： d 一咒”p ”d 1 m 一一10f 2 3 ) 乃： 其中p2 乡，称为业务强度，等于到达率与服务率的比值。表示系统的 负荷水平。 图2 1 配置了光纤延迟线的o b s 核心交换节点就是这种排队模型。突发包从 交换结构入端口到出端口之间的完整通路( 称为突发包的交换通路) 上，所有需 要竞争使用的资源，称为“冲突资源”。在不同的交换结构中，冲突资源的种类和数 量也不同。在该结构中主要有以下两种冲突： 一是f d l 出口冲突。图2 2 所示的f d l 出口配置了一个合波器，来自各级光 开关的光纤在此汇聚成一个通路。假定先后有两个突发包b l 和b 2 进入f d l ，它 们使用相同的波长a ，但去往不同的出端口。若鼠需要延迟，那么为了避免在f d l 出口发生重叠，即使b 2 不需要延迟，它也可能不得不等到口t 完全离开f d l 后才 能通过。这种因延迟时间不同而导致突发包竞争f d l 出口的情况就称为“f d l 出 口冲突”。仅就f d l 而言，如果进入f d l 的突发包使用了不同的波长，即使存在 时间上的交叠，在f d l 出口处也不会冲突。但在本结构中进入同一个f d l 的突发 包所用的波长是一样的，所以在本结构中存在f d l 出端口冲突。 二是出波长冲突。当两个突发包来自不同的入端口，并要求去往相同出端口的 某个特定波长通