（计算机应用技术专业论文）光突发交换网络数据信道调度问题研究.pdf

光突发交换网络数据信道调度问题研究 摘要 波分复用技术的发展和成熟，使光网络在大容量的中间节点实现全光交换成为可能。 目前的三种光交换技术中，光突发交换o b s ( o p t i c a lb u r s ts w i t c h ) 因具有适中的交换粒度 和较高的带宽利用率，比光电路交换灵活，比光分组交换贴近实用，成为下一代全光网络 的理想候选模式之一。 o b s 网络的关键技术包括：边缘节点组装算法、资源预约机制、传输控制协议、q o s 机制、信道调度算法等。其中，数据信道调度算法与网络的丢包率、信道利用率、q o s 支 持等多个方面密切相关，其性能的优劣对整个网络的性能影响很大，是一项相当重要的研 究课题。一个好的算法应该在突发包到达之前，尽可能的为突发包选择一条可用的信道， 以降低突发包的丢失率，并能有效支持业务区分。 本文首先介绍了o b s 网络的产生背景、基本概念以及几种关键技术，对三种交换技术 进行了分析比较，尤其对光突发交换技术进行了综合评价；然后在第二章讨论了o b s 网络 的结构，在第三章详细介绍了o b s 网络的若干关键技术。本文的创新贡献主要是第四章 基于突发的可用信道数组调度算法。最后一章是关于作者工作的总结和展望。 第四章主要研究了o b s 网络的信道调度算法。首先介绍了当前两种典型的信道调度算 法：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 ) 算法和l a u c v f ( l a t e s ta v a i l a b l e u n s c h e d u l e dc h a n n e l v o i df i l l i n g ) 算法。接着讨论了f a f a ( f i r s ta r r i v a lf i r s ta s s i g n m e n t ) 算法 和基于优先级的重新调度算法。其中，f a f a 算法是l a u c v f 算法的改进算法，重新调 度算法结合了l a u c 和l a u c v f 两种典型调度算法的优点( 高性能、低丢包率和低复杂 度) 。 通过仿真我们比较了几种算法的性能，指出了各种算法的优缺点。在此基础上，首次 提出了有关突发的可用信道数组的概念，并建议了基于突发的可用信道数组调度算法。该 算法在只搜索一次数据信道组状况下，可以达到多次重新调度的效果，避免了多次为突发 包搜索信道组的情况，也避免了突发包需要被重调度时因为偏置时间已经不足于再次搜索 一次信道组而导致突发包被丢弃。论文最后仿真分析了该算法，并设计了为突发建立可用 信道数组的方法和步骤。 关键字：光突发交换；信道调度算法；重调度算法；丢包率；可用信道数组 i l 光突发交换网络数据信道调度问题研究 a b s t r a c t | 黝t h ed e v e l o p m e n ta n dm a t u r i t yo ff 仞mt e c h n o l o g y , i tb e c o m e sp o s s i b l et or e a l i z e a 1 1 o p t i c a ls w i t c hi nl a r g ec a p a c i t yi n t e r m e d i a t en o d e so fo p t i c a ln e t w o r k s c u r r e n t l yt h e r ea re t h r e em e t h o d su n d e ri n v e s t i g a t i o n ：0 c s ，o b sa n d0 p s ，a m o n gw h i c h0 b s ( o p t i c a lb u r s t s w i t c h i n g ) i sm o s tp r o m i s i n gb e c a u s ei t sp r o p e rg r a n u l a r i t ya n dt e c h n o l o g i c a lf e a s i b i l i t y k e yt e c h n o l o g i e sf o ro b sn e t w o r k si n c l u d e ：e d g en o d ea s s e m b l ya l g o r i t h m ，r e s o u r c e r e s e r v a t i o nm e c h a n i s m ，t r a n s m i s s i o nc o n t r o lp r o t o c o l 。q o sm e c h a n i s m 嬲w e l la sc h a n n e i s c h e d u l i n ga l g o r i t h m t h ed a t ac h a n n e ls c h e d u l i n ga l g o r i t h ma n dt h en e t w o r kp a c k e tl o s sr a t e c h a n n e lu t i l i z a t i o n , q o ss u p p o r tm a n ya s p e c t s ，s u c ha sc l o s e l yr e l a t e dt ot h em e r i t so fi t s a l g o r i t h mt ot h ee n t i r en e t w o r kg r e a t l ya f f e c tt h ep e r f o r m a n c e i sa ni m p o r t a n tr e s e a r c ht o p i c a g o o dm e t h o ds h o u l db eb e f o r et h ea r r i v a lo ft h eb u r s t ，a sf a ra sp o s s i b l et oc h o o s ea b u r s to f a v a i l a b l ec h a n n e l st or e d u c et h er a t eo fs u d d e nl o s so ft h ep a c k a g e a n dc a ne f f e c t i v e l ys u p p o r t t h ed i s t i n c t i o nb e t w e e nb u s i n e s s t h i sp a p e rw i l li n t r o d u c et h eo b sn e t w o r kb a c k g r o u n d ，t h eb a s i cc o n c e p ta n ds e v e r a lk e y t e c h n o l o g i e s ，t h r e es w i t c h i n gt e c h n o l o g yw i l lb ea n a l y z e da n dc o m p a r e d ，p a r t i c u l a r l yo p t i c a l b u r s ts w i t c h i n gt e c h n o l o g yw i l lb ee v a l u a t e d t h e ni nt h es e c o n dc h a p t e ro nt h eo b sn e t w o r k s t r u c t u r e ，d e t a i l e di nc h a p t e ri i io ft h e0 b sn e t w o r ko fan u m b e ro fk e yt e c h n o l o g i e s t h em a i n c o n t r i b u t i o no ft h i si n n o v a t i o ni st h ef o u r t hc h a p t e r b a s e do nt h es u d d e na r r a yo fa v a i l a b l e c h a n n e la l g o r i t h m 硼1 ef i n a lc h a p t e ri so nt h ew o r ko ft h ea u t h o r ss u m m a r ya n do u t l o o k c h a p t e ri vo nt h em a i nc h a n n e lo ft h eo b sn e t w o r ka l g o r i t h m f i r s t0 nt h ec u r r e n tt w o t y p i c a lc h a n n e la l g o r i t h m ：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 ) a l g o r i t h ma n d l a u c v f ( 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 v o i df i l l i n g ) a l g o r i t h m t h e nd i s c u s s e dt h e r 姒( f i r s ta r r i v a lf i r s ta s s i g n m e n t ) a l g o r i t h ma n dt h ep d o r i t yo fr e s c h e d u l i n ga l g o r i t h m o n e r 气f a a l g o r i t h mi sl a u c - v fa l g o r i t h mi m p r o v e da l g o r i t h m r e s c h e d u l i n ga l g o r i t h mc o m b i n e s t h el a u ca n dl a u c v ft w ot y p i c a la d v a n t a g e so ft h ea l g o r i t h m ( 1 l i 曲- p e r f o r m a n c e ，l o w p a c k e tl o s sa n dl o wc o m p l e x i t y ) t h es i m u l a t i o nw ec o m p a r et h ep e r f o r m a n c eo fs e v e r a la l g o r i t h m st h a tt h ea d v a n t a g e sa n d d i s a d v a n t a g e so ft h ev a r i o u sa l g o r i t h m s o nt h i sb a s i s t h ef i r s tt i m ep r o p o s e das u d d e na r r a yo f a v a i l a b l ec h a n n e l st h ec o n c e p ta n ds u g g e s t e dt h a tb a s e do nt h es u d d e na r r a yo fa v a i l a b l ec h a n n e l a l g o r i t h m t h es e a r c ha l g o r i t h mi no n l yo n ed a t ac h a n n e lg r o u pc i r c u m s t a n c e s ，c a na c h i e v et h e e f f e c to fm u l t i p l er e s c h e d u l i n gt oa v o i du n e x p e c t e dp a c k a g e sf o ran u m b e ro fs e a r c hc h a n n e l g r o u pa n da l s ot oa v o i das u d d e nn e e dt ob er e s c h e d u l i n gp a c k a g ea tt h et i m eb e c a u s eo f l a c ko f b i a so n c ea g a i ni ns e a r c hc h a n n e lg r o u pw h i c hb u r s tw a sd i s c a r d e d s i m u l a t i o no ft h el a s tp a p e r s o ft h ea l g o r i t h m ，a n dd e s i g n e df o r t h eb u r s tp a c k e te s t a b l i s h m e n to fa na r r a yo fc h a n n e l s a v a i l a b l em e t h o d sa n ds t e p s k e y w o r d s ：o p t i c a lb u r s ts w i t c h i n g ；c h a n n e ls c h e d u l i n ga l g o r i t h m ； r e s c h e d u l i n ga l g o r i t h m ；p a c k e t l o s sr a t e ；a v a i l a b l ec h a n n e la r r a y i i i 光突发交换网络数据信道调度问题研究 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ) 本人郑重声明：此处所提交的博士口 硕土吲论文光突发交换网络数 v 据信道调度问题研究，是本人在导师指导下，在曲阜师范大学攻读博士口硕 士e l 学位期间独立进行研究工作所取得的成果。论文中除注明部分外不包含他 人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的个人和集 体，均已在文中已明确的方式注明。本声明的法律结果将完全由本人承担。 作者签名：刘卷氧日期：2 0 0 留午t6 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“4 ) 光突发交换网络数据信道调度问题研究系本人在曲阜师范大学攻读 博士口硕士口学位期间，在导师指导下完成的博士口硕士d 学位论文。 本论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位 的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定， 同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅 和借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文， 可以公开发表论文的全部或部分内容。 作者签名： 刹老缕 日期： 2 _ 0 0 留午 剔磁锄，皿嘲 醐一穆牛c 7 光突发交换网络数据信道调度问题研究 第一章绪论 1 1 光网络的发展 当今时代，信息技术的迅猛发展，尤其是i p 技术的爆炸式增长改变了人们的生活。浏 览网页、电子商务、网上教育、网络游戏等成为人们生活的一部分，信息沟通的渠道多种 多样，各种新业务尤其是数据业务的出现，使带宽的需求呈快速增长趋势，这就对传统的 骨干网提出了巨大的挑战【l j 。 传统的骨干网使用的是s d h ( s y n c h r o n o u sd i g i t a lh i e r a r c h y ) 技术，该技术以特定的传 输速率( 1 5 5 m b s 、6 2 2 m b s 、2 5 g b s ，将来有望提高到4 0 g s ) 在光纤中1 5 5 0 n m 或1 3 1 0 n m 附近的单个波长信道上传输数据，传输带宽的增加只能单纯依靠提高单个波长的传输速率 来实现。s d h 技术需要电的时分复用( t d m ：t i m ed i v i s i o nm u l t i p l e x i n g ) ，而电领域的处 理速度由于受量子理论的限制，提高的速度有限，目前认为4 0 g b s 是单个波长最高实用化 的速率，同时s d h 技术主要支持语音业务，而支持i p 等数据业务时因不能灵活的分配带宽 浪费严重，网络带宽紧张，这些都使传统的s d h 技术越来越不能适应数据网络发展的要 求。这种情况下，光波分复用( w d m ) 技术应运而生，尤其是密集波分复用【2 j ( d w d m ) 技术在各大运营商的长途骨干网中得到大量商用。 w d m 技术由于能充分利用光纤的巨大带宽，正在成为骨干长途网中最具吸引力的技 术。光纤的带宽可以达到几十t b s ，w d m 技术可以把光纤巨大的带宽划分成许多不相重 叠的波长信道，每个波长信道占用一个波长，波长信道的速率在目前电信号处理的速度极 限内，在光纤中可以同时传送多个波长信道的数据。目前商用化的为每光纤3 2 或4 0 个波 长，主要集中在1 5 5 0 h m 波长附近，最高达到1 6 0 个波长，实验室已达到1 0 0 0 个波长【3 j 目前对i p 数据的支持主要以i po v e rs d ho v e rw d m d 形式，网络结构层数较多，为简 化网络结构，提高网络效率，提出i p o v e r w d m 5 】技术，取消了中间的s d h 层。 目前实用的全光网是建立在w d m 技术基础上、在节点利用波长上下话路 ( o a d m ：o p t i c a la d dd r o pm u l t i p l e x e r ) 6 j 或进行交叉连接( o x c ：o p t i c a lc r o s sc o n n e c t ) 削 来构成。基于o a d m 或o x c 的全光网采用波长路由的方式，可以称为光线路交换系统， 由控制平面建立链路和分配波长，波长选路所需的时间较长，网络的可升级性，动态适应 性比较差，还不能实现真正意义上的分组交换网络，只不过是一种光的电路交换方式。 随着i n t e r a c t 业务量不断增加，利用高性能的高端路由器和成熟的w d m 传输，以p o s ( p a c k e to v e rs d h ) 、a t m 或g e ( g i g a b i te t h e m e t ) 方式在数个波长上传送信号，实现 i n t e m e t 的升级，处理能力有限，网络q o s 也无法保证。为了更有效、灵活地承载未来的 i p 包分组业务，提出了光分组交换与光突发交换这两种适应未来光因特网的交换技术。 光分组交换可以看作是电分组交换在光域的延伸，交换粒度以高速传输的光分组为单 位。虽然光分组可长可短，但由于交换设备必须具备处理最小分组的能力，光分组交换节 光突发交换网络数据信道调度问题研究 点的处理能力要求非常高。目前常采用的是光电混合的办法实现光分组交换，交换机都以 存储转发方式工作，因此必须采用光缓存。实现光分组交换需要的关键技术包括光分组的 产生、同步、缓存、再生，光分组头重写及分组之间的光功率的均衡等。其中分组的实时 同步、再生、分组头重写，由于码率太高，电设备无法完成，而全光的办法也只停留在实 验阶段。人们对于未来光因特网的希望是支持多种业务，保证q o s ，但光分组交换本身不 直接支持q o s 。 由于现在光器件的局限，缺少快速的光开关器件，实现完全的光分组交换网络还比较 困难，在这种情况下，提出了光突发交换【7 】( o b s ) 网络。它的主要思想是将比较小的i p 包组装成一个大的突发包，这种突发包通过光开关的时间为毫秒级，现在的光器件可以满 足这一要求。而一个i p 分组要求光开关的速度为纳秒级，甚至更少。o b s 技术将控制信 道和数据信道分离，每一个突发的数据分组对应于一个控制分组，并且控制分组先于数据 分组传送，通过“数据报 或“虚电路 路由模式指定交换机分配空闲信道，实现数据信 道的带宽资源动态分配。数据信道与控制信道的隔离简化了突发数据交换的处理，且控制 分组长度非常短，因此使高速处理得以实现。这种交换机充分发挥了现有的光电子技术的 特长，实现成本相对较低、非常适合于在承载未来高突发业务的因特网中应用，超大容量 的光突发交换机同样可用于构建骨干网。 业务导向的网络使得o b s 从技术研究阶段走到了应用阶段，这主要是o b s 技术结合 了光电路交换【8 】和光分组交换【9 】的优点，可以提供透明的、可变粒度的、高效的数据传输， 直接满足这种业务的需求，同时还具有较低的成本。 1 2 论文的主要工作 ( 1 ) 对o b s 技术现状、光突发交换网络作了总体的介绍，同时介绍了o b s 技术的 资源预约方案、节点汇聚技术、传输控制协议、冲突处理机制、q o s 机制。 ( 2 ) 详细介绍并分析了o b s 网络中典型的传输控制协议j i t 协议和j e t 协议，以及 信道调度算法。 ( 3 ) 根据两种典型的信道调度算法l a u c t l 0 1 算法、l a u cv f t l l 】算法和重调度算法【1 2 j 思想，首次提出突发的可用信道数组的概念，以及在此基础上提出的基于突发的可用信道 数组的调度算法。 ( 4 ) 比较分析了新算法与已有算法相比对系统丢包率方面的改进。在建立突发的数 据信道数组时，分别以l a u c v f 和f a f a 算法为原则确定可用信道数组的第一可用信道， 并进行了分析和比较。最后使用仿真软件对算法进行数据分析。 1 3论文内容和组织 论文分为五章，第一章介绍了光突发交换技术的发展和现状。第二章介绍了三种光交 换技术以及o b s 网络结构和节点结构。第三章详细介绍了o b s 网络的基本原理，包括边 缘节点汇聚技术、两种典型的传输控制协议：j i t 协议和j e t 协议、o b s 路由技术和q o s 2 光突发交换网络数据信道调度问题研究 机制。第四章详细介绍了典型的信道调度算法l a u c 算法、l a u cv f 算法以及重调度算 法，在分析以上算法的优缺点的基础上，提出两种新算法：改进的重调度算法和基于突发 的可用信道数组的调度算法。该算法在系统较为繁忙时，与重新调度算法相比，可花费较 小的代价，达到重新调度算法特别是多级重新调度算法很难达到的效果，有效减少系统的 丢包率。特别是基于突发的可用信道数组的调度算法，理论上可把系统的丢包率降到最低。 第四章最后详细分析了建立突发的可用信道数组的几种算法，并进行了数据仿真。第五章 结论部分是对整个论文工作的总结，最后对全文作出总结，并提出一些研究上的不足和今 后的研究方向。 3 光突发交换网络数据信道调度问题研究 第二章光交换技术 2 1光交换技术 实现透明的、具有高度生存性的全光通信网络是带宽通信网未来发展的目标。从系统 角度看，支撑全光通信网络的关键技术基本上可分为光传输技术、光交换技术、光放大技 术和光处理技术等几大类。光交换技术作为全光网络系统中的一个重要支撑技术，在全光 通信网络中发挥着重要的作用。光交换技术的发展在某种程度上也决定了全光通信网络的 发展。随着d w d m ( 密集波分复用) 技术的成熟和商用，通信网络的容量越来越大。传 输系统容量的增长带来的是对交换系统发展的压力和动力【1 3 】。传输带宽的增加导致信息传 输的成本迅速下降，信息交换所花费的成本相对占据的比例越来越高，通信网络中交换系 统的规模越来越大，运行速率也越来越高，未来的大型交换系统将需要护理总量达几百、 上千太比特每秒的信息。为解决电子瓶颈限制，降低交换成本，开始在交换系统中引入光 子技术，实现光交换。光交换技术是指不经过任何光电转换，在光域上直接将输入光信 号交换到不同的的输出端。按照不同的交换对象和参照依据，光交换技术有不同的分类。 按照复用方式的不同，光交换技术可以分为以下几种： 2 1 1 光电路交换技术 光电路交换类似传统的电路交换方式，是基于双向的资源预留协议，基本过程包括连 接建立阶段、信息传送阶段和连接释放阶段。源节点先发出一个控制分组预留带宽，然后 等待从目的节点发回的确认信息，数据只有在连接建立成功且收到确认信息后才能发送出 去。数据在透明的光通道上传输，中间节点不需要光缓存，因此可提供有保证的服务。但 光电路交换的交换单元是一次呼叫，因而是粗粒度的，不能实现统计复用，带宽利用率低， 不适于传输突发性的数据；对长距离网络来说，其回环时间与延迟太长；由于波长数目有 限，还不能建立全连接的网络，导致网络中负载的不均衡。 2 1 2 光分组交换技术 光分组交换类似于传统的i p 分组交换，采用存储转发交换方式。光分组由数据净荷和 首部( 内带信令) 组成，数据伴随其首部一起发送出去。中间节点接收到光分组后，对首 部进行处理( 全光处理或在o e 变换之后电子处理) ，根据首部中包含的目的地址对各个 分组进行独立选路，同时数据暂存于光缓存中，对首部处理完毕之后，根据选定的路由将 数据和首部( 若是电子处理则需要经过e o 转换) 一起发送出去。光分组交换中交换单元 是口分组，因而是细粒度的，可以实现统计复用，带宽利用率高，传输质量高，可靠性较 高。从长远来看，为了提高交换速率和带宽利用率，并结合i po v e rw d m 技术，全光的分 组交换能对d w d m 的巨大带宽进行更灵活、更有效地分配和利用。 4 光突发交换网络数据信道调度问题研究 在光分组交换中，需要解决的问题很多，如光开关矩阵性能、控制协议、物理参数管 理与控制以及光分组的产生、同步、缓存、再生、分组头重写以及分组之间的光功率等基 本技术。 光分组技术经历了多年的研究，有些关键技术问题( 尤其是核心光子器件) 仍有待解 决，如长时延和高速缓存器、高速光交换矩阵、光分组头的光处理和同步、光时钟提取与 恢复等，这使得实现全光分组交换还比较困难。目前，o p s 仍然处于不成熟阶段，而且成 本很高。 2 1 3 光突发交换n 钔5 1 技术 光突发交换是一种单向资源预留方案，其控制分组和数据分组在信道及时间上是分离 的，控制分组先于数据分组在特定w d m 信道中传输，核心交换路由器根据控制分组中的 信息和当前网络状况为响应的数据分组建立全光通路。数据分组经过一段延迟后，直接在 预留的全光通道中透明传输。与前两种方案比较，首先，光突发交换提供可变长度的突发 流量，其交换粒度介于电路交换单元和分组信元之间，与光分组交换相比降低了控制开销； 其次，光突发交换可在无目的节点确认的情况下完成单向的数据信道带宽资源的动态分 配，减少了建立通道的延迟等待时间，提高了带宽利用率：最后，光突发交换实行数据分 组和控制分组分离的异步传输交换机制，使数据业务的交换完全在光域内完成，控制分组 在独立于数据分组的w d m 传输链路中的一个特定光信道中传送，每一个突发的数据分组 对应一个控制分组，在源端设置控制分组与数据分组之间的偏置时间，因此不需要执行光 同步和光缓存，这就降低了对光子器件的要求和中间节点的复杂度。 表1 - 1o b s 、o c s 、o p s 的比较 交换方式带宽利用率建立延迟光缓存开销 适应性 实现难度 o c s 低高不需要低弱低 o p s 高低需要局强两 o b s 局低不需要低 强 中 2 2o b s 网络结构u 引 o b s 网络由光核心路由器、边缘路由器及光电路组成。在骨干网络边缘，来自接入 网的i p 分组在边缘路由器中按照数据包的目的地址和服务等级等信息，对数据包进行分 类，缓存和封装，组成光突发单元，并产生b c p ，然后发送给与之最邻近的o b s 核心节 点。核心节点根据b c p 的路由信息，对到达的突发包进行交换。在网络的出口处，边缘节 点将突发包拆卸，发送到其他子网或终端用户。边缘节点提供各种网络接口，使之可以完 成各种协议类型的网络互联。 5 光突发交换网络数据信道调度问题研究 核心路由器 图2 - 1 光突发交换网络结构 突发包在o b s 网络中的交换传输完全在光域内完成，不需要进行光电光转换。突 发数据包由一些口分组组成，这些i p 分组可以是来自传统m 网中不同的电域i p 路由器。 b c p 在独立于数据通道的光信道中传输，每个突发包对应于一个b c p ，源节点需要设置 b c p 与突发包的偏置时间t ，即b c p 与相应的突发包出发时间的间隔。通过设置恰当的偏 置间隔，可以保证一定的q o s 并且不需要光缓存和执行光同步。b c p 中包含突发包传输交 换所必需的控制信息，如突发包的长度、偏置时间等。b c p 在中间节点需要光电转换，在 电域内进行路由判断，保证突发包在偏置时间内完全在光域内完成传输和交换。由于突发 包是统计占用带宽资源，从而提高了不同连接之间的传输效率。在w d m 系统中，b c p 占 用一个波长或者几个波长，突发包占用其他波长；对于多光纤系统也可以是b c p 占用一根 光纤或其中的几个波长，其他光纤和波长用于突发包的传输。 o b s 节点分为核心节点和边缘节点。边缘节点负责b d p 的分类、组装和拆卸，可提 供各类业务接口，而核心节点的任务是完成b d p 的转发和交换。o b s 核心节点结构与光 分组交换不同，它只需要在电域处理控制信令。边缘节点的功能又分为入口边缘节点功能 和出口边缘节点功能，两个功能都是每个边缘节点必须具备的。 2 2 1 核心节点 o b s 网络的核心节点主要由光交换矩阵、交换控制单元、输入f d l s 以及一些波长转 换器组成。核心节点要完成的功能有一般的b c p 处理、选路、数据突发交换和数据信道 调度等。核心节点功能结构如图2 - 2 所示：入口和出口光纤数均为n ，每根光纤支持的波长 数均为k + l ( k 个波长用于传输突发数据包，一个波长用于传输突发控制分组) 。用于传 输突发控制分组的波长在网络中间节点需要进行光电光转换，在电域进行路由表查找、 6 光突发交换网络数据信道调度问题研究 对光交换矩阵进行控制、更新b c p 相应数据与等操作。用于传输突发数据包的波长信道， 不需要进行光电光转换。整个交换和传输系统都在光域内完成。中间节点只需要对少量 波长( 控制波长) 进行光电光转换，然后在电域进行处理和控制光交换矩阵等。光交换 矩阵前的光纤延迟线f d l ( f i b e r 、d e l a yl i n e ) 是可选的，通过设置恰当的偏置时间，可以 使b d p 不需要在中间节点缓存而直接通过o b s 网络。但使用f d l 可以减少数据包丢失。 光纤l 光纤2 k 个数据波长 2 2 2 边缘节点 图2 - 2o b s 核心节点功能结构 光纤1 光纤2 o b s 网络的边缘节点位于o b s 网络和各种传统网络之间，把多个运行于传统链路层 协议之上的子网连接到o b s 网络中。来自接入网的一定数量具有相同出口边缘地址和q o s 要求的i p 包在入口边缘路由器被组装成突发数据包b d p ( b u r s td a t ap a c k e t ) ，并产生一个 相应的突发控制分组b c p ( b u r s tc o n t r o lp a c k e t ) ，b c p 中包含b d p 输交换所必需的控制信 息。包括b d p 的大小、偏置时间、出口地址、q o s 等信息。b c p 提前于其对应的b d p 在 分离的控制信道上发送，b d p 经过偏置时间后直接发送，b c p 信号在中间节点被转换成电 信号进行处理。边缘节点的功能如图2 3 所示。在口层和w d m 层有一个媒介接入控制 层( m a c ：m e d i u m a c c e s sc o n t r 0 1 ) 。入口边缘节点m a c 层需要完成i p 分组的组装，形成 b d p ，计算b d p 和对应b c p 之间的偏置时间，并将含此偏置时间的b c p 发送到光层控制 信道，然后在偏置时间后送出相应的b d p 。在出口边缘节点完成相反操作。 7 光突发交换网络数据倍道调度问题研究 ，1 i 缓爱物i p 分缎l p 层静分缀戮鳜纭嬲 li k l ， 、 突发数据组装f ： li 1 r iii 接收， y2 obs缘节点功能结构3 光突发交换网络数据信道调度问题研究 第三章o b s 基本原理与技术特点 3 1o b s 网络基本原理 o b s 网络中用信道( c h a n n e l ) 来表示两个相邻路由器间的某种单向传输能力。信道可 以是由一个波长或时分( 码分) 复用下的波长的部分组成的。传输b c p 的称为控制信道， 传输b d p 的称为数据信道。信道组是由一组具有相同类型和节点信息的信道组成。一个 w d m 链路代表两个路由器间的整体传输能力，每个方向都有一个数据信道组和一个控制 信道组组成。数据信道组和控制信道组在物理上可是是同一根光纤，也可以是不同的光纤。 o b s 网络中的基本交换单位是突发数据包，它由具有相同的出口边缘路由器地址和相 同的q o s 要求的i p 分组组成。突发数据包的长度是可变的，在入1 3 边缘节点突发包产生 时，同时会产生一个与其相对应的b c p 。一般的o b s 网络中，每一根光纤各有多个波长 用作数据信道，一个波长用作控制信道。数据信道与控制信道的隔离可以简化对突发包交 换的处理。传送数据时，首先在控制信道上发送相应的b c p ，确定b d p 的输出信道。b d p 等待一定的时间后发送，该段时间叫做偏置时间。通过设置适当的偏置时间，可以大大降 低突发包的丢失率。b c p 一般要通过电域处理，而b d p 不需要进行光电光转换和电路 由器转发。b c p 中包含了对应突发包的相关信息，包括偏置时间大小、突发包长度、优先 级、目的o b s 节点等。b c p 的目的是同通知到目的o b s 节点的途经中间节点，在一定时 间( 偏置时间) 后，将有一个突发包到达，并请预留资源，以便这些中间节点进行路由、 交换结构配置，并在突发包持续的时间内，将突发包传送到相应的端口和波长。源节点不 需要等待目的节点的确认，直接在数据信道中全光传输。o b s 网络中，b c p 的长度很小， 使得高速处理成为可能。同时，由于b c p 与b d p 是通过b c p 中含有的可“重置 的时延 信息相联系的，传输过程中可根据链路的实际状况，对b c p 进行光电转换后，对其中的控 制信息作相应的调整。b c p 和b d p 都不需要光同步。o b s 网络充分发挥了现有的光子技 术和电子技术的特长，实现成本相对较低。 由于在发送突发包之前，并不预先建立连接，在b d p 经过的节点中，有可能无法预留 资源，此时突发包可能被丢弃。利用f d l 、波长变换、偏射路由等手段可以解决它发数据 包的丢失问题。对于时延允许的业务，也可以通过上层的重传机制，只要重传的比例不大， 将不会对网络性能造成重要影响。 根据偏置时间的大小，o b s 网络又可以分为3 类，无预留：发送b c p 后，立即发送 突发包。单向预留：b c p 发送完成后，经历一小段时间发送突发包，源节点不等待目的节 点的确认。其偏置时间的大小介于b c p 的发送时间与b c p 的往返传输和处理时间之间， 不同的o b s 机制在该范围内可选择不同的偏置时间。双向预留：偏置时间为从目点节点收 到一个确认信息的时间。这类很接近光路交换，偏置时间较长，会引起较长的数据传输延 9 光突发交换网络数据信道调度问题研究 迟。 3 2o b s 网络边缘节点汇聚技术 o b s 网络由边缘节点和核心节点构成，采取将控制信息和数据信息剥离的方法，提前 发送控制分组，沿路为数据信息预留节点资源，数据信息在o b s 网络的边缘接入节点按照 一定规则进行汇聚组装。如何把来自不同网络的数据适配进o b s 网络并组装成突发包是 o b s 网络中的关键技术之一，边源汇聚【1 7 】技术将对o b s 网络性能产生重要影响。 为完成o b s 网络的数据传输，待传数据接入边缘节点后，首先要适配成突发数据包才 能接入o b s 网络。边源节点对i p 业务按目的地址和业务类型进行分类汇聚，根据业务流 量的特性进行突发包组装和偏置时间计算。这意味着在o b s 网络中突发数据包长度是流量 相关的，即突发数据包长度是可变长的。为使得数据业务平稳，突发包长度的变化频率和 幅度应该降低到最小。边源节点的接入数据包需适配成突发分组才能接入o b s 网络，这涉 及b d p 汇聚、调度和突发分组帧格式的设计等问题。边缘节点包括入口边缘节点和出口边 缘节点。入口边缘节点完成b d p 的整合和适配，出口边缘节点完成相应的拆分和提取。 在o b s 网络的入口边缘节点处，接入的数据业务来自各种分组交换网络( 包括局域网、 广域网、a t m 网) ，这些信息流具有长时相关性自相似性。即：当对此业务流进行多时间 尺度的测量时，业务流会产生相似的特性，与传统的业务流量模型的短时相关性具有明显 的不同。所以在设计边缘业务模型的时候，就应该基于自相似模型，通过一种有效的算法， 利用定时器和队列长度特性共同决定队列长度，使得汇聚后的突发包尽可能减少长时相关 性。 图3 - 1边缘汇聚节点基本结构框图 1 0 光突发交换网络数据信道调度问题研究 o b s 网络入口边缘节点的突发汇聚功能模块对接入业务进行整合，降低接入业务的突 发性。假设对于每一个出口边缘节点和每一个q o s 等级，都有一个专用的队列用于汇聚 b d p ，所有接入的数据分组将根据其o b s 目的地址或q o s 等级被转发到相应的队列。当 达到某一设定门限时，汇聚完成，产生b d p ，并对它进行有效封装，接着产生相应的b c p ， 并对其进行有效的设置。 图3 1 给出了一种典型的o b s 边缘节点结构，交换单元将接入端经过交换后的数据 包转发给突发组装单元。去往相同出口节点的突发包被送到相同的突发组装单元内，一般 为每一种优先级的突发包专门设计一个特定的组装队列，并由突发调度模块控制。突发调 度模块负责建立突发数据包和与它相应的控制包，为每一个突发数据包配置相应的偏置时 间，在每一个链路上调度相应的突发包，并转发这些突发包以及他们的控制包到o b s 的核 心网络中。 3 2 1 固定汇聚时间算法： 固定汇聚时间( f a p ) 算法非常简单且直观，其基本原理是：当队列中分组的最大时 延达到汇聚时间门限时，汇聚完成，产生一个b d p ，并产生相应的b c p 。使用该算法， b d p 的产生几乎是周期性的。由于这种周期性，该算法将引起很高的连续冲突概率，即使 在负载很低的情况下，也可能如此。负载较大时，该算法有可能产生过大的b d p 。这对于 支持多级q o s 的o b s 网络，不利于优先级的实现。还将导致过大的偏置时间，甚至其本 身可能超过时延敏感业务的最大允许时延。该算法对于入口o b s 边缘节点存储器的容量需 求也较大。而且相对于小的b d p ，较大b d p 更容易被冲突。 ( 分组到 完成一些初 始化的操作 ( 默认) 图3 - 2f a p 算法状态转移图 址和 启动 突发包，产生突 相应控制分组 应队列、计数器 器 光突发交换网络数据信道调度问题研究 3 2 2 固定汇聚长度算法+ ： 固定汇聚长度( f s a ) 算法的基本思想是将到达同一个目的节点且属于同一优先级的 分组汇聚到同一个队列，队列的长度达到设定的门限时，就产生突发数据包，并产生相应 的b c p 。固定汇聚长度算法比较简单，易于实现。但当接入负载很低时，汇聚时间将很大， 可能超过实时业务的门限。固定汇聚长度算法的状态转移图如3 3 图所示： 包，产生突发 制分组 ( 默认) 清空相应队列和计数器 图3 - 3f s a 算法状态转移图 3 2 3 最大长度最大汇聚时间算法 一个好的汇聚机制，需要同时考虑突发数据包的长度和汇聚时延，最大长度最大汇聚 时间( m s m a p ) 算法把f a s 和f a p 有机结合起来，兼顾了两者优点，同时避免了两者的 不足。在该算法中，当某个队列的长度达到汇聚门限或其相应的最大时延达到汇聚时间门 限时，就产生突发包，并产生一个相应的突发控制分组。最大长度最大汇聚时间算法的状 态转移图如图3 - 4 所示： 3 2 4 自适应汇聚长度算法 自适应汇聚长度( a a s ) 算法根据相关接入的负载情况，自动地调节相应的长度门限， 并确保汇聚时间不超过固定的汇聚时间。为避免最大长度最大汇聚时间( m s m a p ) 等算 法中突发大小随着接入业务过快地变化，自适应( a a s ) 算法应入了一个窗口，从而降低 了业务的突发性，在一定程度上对业务进行了平滑。假设q h i g h ( q l o w ) 表示高( 低) 突 发长度门限，它们之间有一个窗口，当业务量增大或减小时，窗口相应地上滑或下滑。 当某个队列的长度达到汇聚门限或其相应的汇聚时延达到时间门限时，就产生突发包，并 1 2 光突发交换网络数据信道调度问题研究 产生一个相应的控制分组。该算法可以根据介入流量的情况，自适应地改变突发数据包的 大小，具有较好的汇聚效果。自适应汇聚长度算法的状态转移图如图3 5 所示： 将 和 如 启 检 生突发包和相应 ( 默认) 清空相应队列、计数器和定时器 图3 - 4m s m a p 算法状态转移图 将到达的分组根据目 的地址和q o s 放到相 ( 默认) 图3 - 5a a s 算法状态转移图 汇聚成突发包， 产生突发包和相 应控制分组 清空相应队列和 计数器和定时器 如果队列大小大 于高门限，增加 高低门限，如果 小于低门限则减 少低门限，但高 低门限不超过最 大和最小突发包 大小 光突发交换的汇聚组装算法不仅