（计算机应用技术专业论文）在obs中有限制偏射路由研究.pdf

在o b s 中有限制偏射路由研究 摘要 随着科技进步和计算机网络技术的飞速发展，信息产业及其应用得到了巨大的发展， 政府、金融、电信及个人用户对计算机网络的应用越来越多，尤其是点到点的多媒体流和 基于i p 的实时服务的快速增长，这也就使网络的通信量迅猛增长，传统的电网络已经不能 满足通信量、业务和性能需求的变化，并且随着光技术的快速发展，已经有能力实现在光 纤上进行信息的传输，在现行的光传输体系结构中，o b s 网络有能力成为有效、灵活的下 一带光网络传输体系结构。由于o b s 网络采用单向资源预约机制，容易导致资源冲突，为 了减少突发包丢失率和提高网络的性能，解决突发包冲突是至关重要的，所以在o b s 网络 里如何解决突发包的冲突成为研究的热点。 在o b s 网络里解决冲突的方法主要有光纤延迟线、波长转换器、偏射路由、突发包 分割以及它们的组合，由于光纤延迟线只能提供比较小的延迟和有限的灵活性，还不能满 足像电域r a m 那样能的缓存能力，所以很少单独使用它来解决突发包冲突；波长转换器 对光技术的要求更高，现阶段如果要实现波长转换则需要很大的代价；突发包分割则对突 发数据可以分成多个数据段( s e g m e n t s ) ，并不丢掉整个突发数据，而仅仅是丢掉冲突的( 重 叠的) 数据段，但被丢弃的分组仍有可能与其它分组发生冲突，降低了网络的利用率，在 核心节点它还需要一些额外的功能去控制和处理那些分片，所以我们这里主要研究的就是 偏射路由，利用较容易实现的有限制偏射路由来降低突发包丢失率和提高网络的性能。 有限制偏射路由算法就是对最短路径优先随机偏射路由算法的改进，在这个算法上增 加了一个偏射检测函数和在边缘节点的重发机制，在冲突发生的情况下，通过偏射检测函 数来判断是否偏射这个突发包，从而减少了被偏射以后被再被丢弃的现象，节约了网络资 源，提高了网络的性能，在边缘节点的重发机制保证了被丢弃的突发包能在o b s 层被重发， 而不是到了高层( t c p 传输层) 来重发，这也减少了突发包在网络里的传输时间，提高了 网络的吞吐量，通过增加偏射检测函数和边缘节点的重发机制，使偏射路由算法由一个被 动的算法转变成一个主动的、动态的有限制偏射路由算法，它不但能有效的降低突发包的 丢失率，还能提高了网络的吞吐量，充分利用网络的资源。 第一章介绍了文章的研究背景、光网络的发展概况和o b s 网络研究现状，并对论文的 主要研究内容作了说明。第二章对o b s 网络的基本原理、各种协议思想和算法实现、网络 功能节点和偏射路由进行了介绍。第三章着重讲述了最短路径优先偏射路由的思想和算法 进行了详细的介绍。第四章提出了有限制偏射路由算法并仿真。第五章是总结与展望。 关键词：o b s ；冲突解决；偏射路由；检测函数；重发机制 在o b s 中有限制偏射路由研究 a b s t r a c t w i t hr a p i dd e v e l o p m e n to fc o m p u t e rn e t w o r kt e c h n o l o g y , t h ei n f o r m a t i o ni n d u s t r ya n d i t sa p p l i c a t i o n sh a v em a d et r e m e n d o u sp r o g r e s s t h e r ei si n c r e a s i n gd e p e n d e n c eo nn e t w o r kf o r i n d i v i d u a lu s e r sa n de n t e r p r i s eu n i t s ，s u c ha sg o v e r n m e n t s ，f i n a n c i a li n s t i t u t i o n s ，t e l e c o m i n d u s t r y , e t e e s p e c i a l l yw i t hr a p i do fi n c r e a s i n go fp o i n t t o p o i mm u l t i m e d i ai n f o r m a t i o na n d i p b a s e dr e a l t i m es e r v i c e ，w h i c hl e a dt ot h er a p i dg r o w i n ge x p o n e n t i a l l yo fi n t e r a c tt r a f f i c t h e t r a d i t i o n a ln e t w o r kc a l ln ol o n g e rm e e tt r a f f i c ，o p e r a t i o n a la n dt h ec h a n g eo fp e r f o r m a n c e ，a n d w i t ht h er a p i dd e v e l o p m e n to f o p t i c a lt e c h n o l o g y , a tt h es a n l et i m e ，t h eq u i c ke v o l u t i o no f o p t i c a l t e c h n o l o g i e sh a sa l l o w e dt h et r a n s m i s s i o no fh u g ea m o u n to fd a t ao no p t i c a lf i b e r u n d e rt h e e x i s t i n gs t r u c t u r eo ft h eo p t i c a lt r a n s m i s s i o ns y s t e m ，o p t i c a lb u r s ts w i t c h i n g ( o b s ) h a v et h e p o t e n t i a lt ob e c a m ea ne f f i c i e n ta n df l e x i b l es w i t c h i n gp a r a d i g mf o rt h en e x t - g e n e r a t i o no p t i c a l i n t e m e t a so b sr e l i e so no n e w a yr e s e r v a t i o ni tc a s i l yo c c u rc o n t e n t i o n , i no r d e rt oa c h i e v ea l o wb u r s tl o s sp r o b a b i l i t ya n de f f i c i e n tp e r f o r m a n c e e f f i c i e n tc o n t e n t i o nr e s o l u t i o ni ss i g n i f i c a n t , t h e r e f o r eh o wt or e s o l v et h eb u r s tc o n f l i c ti sk e yi s s u e c o n t e n t i o ns i t u a t i o n si no b sc a nb er e s o l v e di nf d l ，w a v e l e n g t hc o n v e r s i o n ，d e f l e c t i o n r o u t i n g ，b u r s ts e g m e n t a t i o na n dt h e i rc o m b i n a t i o n b e c a u s ef d lo n l yr e f e r r e dt or e l a t i v e l y s m a l ld e l a ya n dl i m i t e df l e x i b i l i t y i tc a l ln o tp r o v i d ew i t i lt h er a mc a c h ec a p a c i t y , s oi tr a r e l y u s e da l o n et or e s o l v et h eb u r s tc o n f l i c t i o n w a v e l e n g t hc o n v e r s i o nr e q u i r e sa d v a n c e do p t i c a l t e c h n o l o g y , n o w a d a y s i tm u s tb ea tt h el a r g eo f c o s t , i f w a v e l e n g t hc o n v e r s i o nc a nb ec a r r i e do u t b u r s ts e g m e n t a t i o nc 姐d i v i d eb u r s t si n t os e v e r a lp a r t s a n di to n l yd r o p p i n gt h ea c t u a l l y c o n t e n d i n gp a r t so fab u r s t b u tt h ed r o p p e dp a r t sc 趾c o n f l i c tw i t ho t h e rb u r s t s , i tr e d u c et h e n e t w o r ku t i l i z a t i o n ，a l s or e q u i r e sa d d i t i o n a lf u n c t i o n a l i t yi nt h ec o r en o d e st oc o n t r o la n ds i g n a l t h es e g m e n t a t i o np r o c e s s t h e r e f o r e ，d e f l e c t i o nr o u t i n gw i l lb ec o n s i d e r e df o rt h er e m a i n d e ro f t h i st h e s i s m a k i n gu s i n go fm o r ee a s i l ya c h i e v e dl i m i t e dd e f l e c t i o nr o u t i n gr e d u c eb u r s tl o s s p r o b a b i l i t ya n di m p r o v en e t w o r kp e r f o r m a n c e t h el i m i t e dd e f l e c t i o nr o u t i n gi m p r o v e st h ep e r f o r m a n c eo fs h o r t e s tp a t hp r i o r i t i z e d r a n d o md e f l e c t i o nr o u t i n gb ya d d i n gad e f l e c t i o nc h e c kf u n c t i o na n do b se d g en o d e ss e n d e r r e t r a n s m i s s i o n i nt h ec a s eo fc o n f l i c t i o n ，d e f l e c t i o nc h e c kf u n c t i o nc a nm a k eac h o i c ew h e t h e r t od e f l e c tt h eb u r s t , c o n s e q u e n t l yi tc a np r e v e n tt h ed e f l e c t e db u r s tf r o mb e i n gd r o p p e d ， e c o n o m i z en e t w o r kr e s o u r c e sa n di m p r o v en e t w o r kp e r f o r m a n c e t h es e n d e rr e t r a n s m i s s i o ni n o b se d g en o d ee n s u r et h a tt h ed r o p p e db u r s tc a l lb er e t r a n s f e r r c di no b sl a y e rb u tn o ti nh i g h e r l a y e r ss u c h 翘t c pl a y e r w h i c hr e d u c e st h et i m et h a tt h eb u r s tb et r a n s m i t t e di no b sn e t w o r k i n c r e a s e st h en e t w o r kt h r o u g h o u t b ya d d i n gad e f l e c t i o nc h e c kf u n c t i o na n do b se d g pn o d e s 在o b s 中有限制偏射路由研究 s e n d e rr e t r a n s m i s s i o n , t h es h o r t e s tp a t hp r i o r i t i z e dr a n d o md e f l e c t i o nm u t i n gc a l lb et u m e dt o t h el i m i t e dd e f l e c t i o nr o u t i n gf r o map a s s i v ea l g o r i t h mt oa c t i v ea n dd y n a m i ca l g o r i t h m ，t h e l i m i t e dr o u t i n gn o to n l ya c h i e v eal o wb u r s tl o s sp r o b a b i l i t ya n de f f i c i e n tp e r f o r m a n c eb u ta l s o i m p r o v en e t w o r kt h r o u g h o u ta n dt h eu t i l i z a t i o no f n e t w o r kr e s o u r c e s c h a p t e ro n ei n t r o d u c e st h er e s e a r c hb a c k g r o u n d ，t h ed e v e l o p m e n to fo p t i e a tn e t w o r k s ， o b sn e t w o r kr e s e a r c hs t a t u sa n dt h ec o n t e n to ft h i sp a p e r c h a p t e rt w od i s c u s s e st h eb a s i c p r i n c i p l eo fo b s ，c o n t r o lp r o t o c o l sa n da l g o r i t h mi m p l e m e n t a t i o n , t h ef u n c t i o n so fc o r ea n d e d g en o d e sa n dd e f l e c t i o nr o u t i n g t h ea l g o r i t h ma n dt h ei d e ao ft h es h o r t e s tp a t hp d o r i 够 d e f l e c t i o nr o u t i n ga r em a i n l ya n a l y z e di nc h a p t e rt h r e e i nc h a p t e rf o u rw ep r o p o s ean e w r e s t r i c t e dd e f l e c t i o nr o u t i n ga l g o r i t h mt o g e t h e r 、i t i lt h es i m u l a t i o nr e s u l t sw h i c hs h o w st h a tt h e t e c h n o l o g i e sp r o p o s e di nt h i sp a p e ra c h i e v eab e t t e rn e t w o r kp e r f o r m a n c et h a nt r a d i t i o n a lo n e s c o n c l u s i o na n df o r e c a s t i n gc o m e sl a s t k e y w o r d s ：o b s ；c o n t e n t i o nr e s o l u t i o n ；d e f l e c t i o nr o u t i n g ；c h e c kf u n c t i o n ； r e t r a n s m i s s i o nm e c h a n i s m 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ”) 本人郑重声明：此处所提交的博士口硕士口论文在o b s 中有限制 偏射路由研究，是本人在导师指导下，在曲阜师范大学攻读博士口硕士 口学位期间独立进行研究工作所取得的成果。论文中除注明部分外不包含他 人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的个人和集 体，均己在文中已明确的方式注明。本声明的法律结果将完全由本人承担。 僦名。细办、 嗍多舻午 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“”) 在o b s 中有限制偏射路由研究系本人在曲阜师范大学攻读博士口 硕士口学位期间，在导师指导下完成的博士口硕士口学位论文。本论文的 研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位的名义发 表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定，同意学校 保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。 本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文，可以公开 发表论文的全部或部分内容。 作者签名： 导师签名： 虿、司柯、 皿酮 j 日期：2 因o ，斗 日期：沙。，牛- 彳 在o b s 中有限制偏射路由研究 第一章绪论 随着社会的发展，人们所需要和了解的信息越来越多，这也促进了计算机技术、信息 技术和通信技术的快速发展。特别是通过i n t e m e t ，人们可以很方便地产生、发送、获取和 利用信息。对于i n t e m e t 上的信息系统和网络来说，一方面要保持原有特性如互连、开放 和资源共享等，另一方面又必须确保网络信息的及时、快速和有效的传输。随着信息量的 不断增加，人们开始利用光纤来进行信息的传输，因为光纤能提供比较高的带宽和可靠性， 因此光传输网络成为现在的主干网络，怎么在光网络中及时、快速和有效地进行信息的传 输成为当今世界各国计算机专家和学者关注的热点问题。 1 1 研究背景 近年来随着i p 业务量的迅速增长，对传输网的带宽和交换系统容量的需求正以前所未 有的速度增加，人们对计算机网络的研究已经开始从传统的电网络转向对光网络的研究。 在最近的2 0 多年里，i n t e r n e t 网络已经从一开始的资源共享网络转变成一个通讯网络， 它扩展了因特网的不同范围的应用，这包括电子邮件、万维网、点到点多媒体流和基于m 的实时服务的快速增长。在美国几年之前i n t e m e t 数据通信量已经远远的超过了语音流量 并且持续快速增长。自从1 9 9 7 年以来每年以接近2 倍的速度快速增长，假定以这个速度 增长的话，目前的电网络传输体系结构和协议将不能满足这个巨大的通信量：并且同时随 着光技术的快速发展，已经有能力实现在光纤上进行信息的传输，为了满足用户对信息的 需求，因此对光网络传输体系结构和协议的研究已经成为信息技术中最为重要、最追切、 最艰巨的任务”j 。 1 2 光网络的概念 为了满足不断增长的网络带宽需求以及降低网络的运行成本，人们对光网络开展了大 量的研究。对于光网络它既没有严格的定义，也不是一个被定义好的网络技术，它随着技 术的发展和人们对它的需求在过去的几十年里一直发展。但是不论如何发展光网络的最基 本的一点是通过光纤进行数据的传输，用光信号对数据进行传输比用电信号对数据进行传 输的最大的优点就是在高速率下有非常低的信号损耗和干扰，这是因为没有电磁辐射的影 响，所以光信号能在信号不损耗和干扰的情况下进行长距离的传输。再者就是通过 w d m ( w a v e l e n g t h d i v i s i o nm u l t i p l e x i n g ) 技术使一根光纤能同时传输多个波长，提高了传输 容量。光网络的基本模型如图： 在o b s 中有限制偏射路由研究 图1 1 光网络的一般模型 1 3 现有的光网络传输体系结构 s v n c l l r o n o l l so p t i c a ln e t w o r k ( s o n e t ) 和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 ( s d h ) 是当今主 流的技术，它们取得成功的最主要的原因在于它们的帧包含有丰富的控制信息。但是也有 很明显的缺点，为了进行信息的传输，这些帧必须在每个节点被读取，也就意味着这些帧 要进行光一电一光的转换，就需要额外的花销和时问的浪费。为了有效、及时和快速进行 光信息的传输，到目前为止主要有下面三中光传输体系结构【2 】。 o c s ( o p t i c a lc i r c u i ts w i t c h i n g ) 光路交换网络：在w d m 网络里我们如果采用o c s 就是一 个波长被用来建立一个端到端的连接，这个连接分为链路建立和链路拆除两个阶段，在两 个端点一旦建立了连接，这个波长就被这个链路所占有，不能被其他的链路使用，即使在 这个波长空闲的时候，并且如果这个链路建立的时间大于这个链路传输数据的时间，那么 这个链路的利用率就很低，就浪费了网络资源。如图所示： 在没有波长转换器的情况下和有波长转换器的情况下光路交换网络的工作过程，如下 图的左面部分所示，因为波长五1 在交换机s l 到交换机s 3 之间是可以使用的，所以链路建 立机制选择波长a l 从用户a 到交换机s l ，在s 3 和s 4 之间五l 正在被用户g 到用户f 使用，所 以这个链路的建立在s 3 处被终止，我们可以看到在缺少波长转换器的情况下可以发生高阻 塞率，浪费了网络资源。如右面部分所示，在有转换器的情况下可以在s 3 处把波长五l 转换 成五2 从而可以建立用户a 到用户e 的光路，进而就减少了冲突的发生。 2 在o b s 中有限制偏射路由研究 b cd n一 _ 一 塞 f 一、嚣二因斜 冬；勺 ， 毫 擎 图1 2 光交换网络的工作过程 o p s ( o p t i c a lp a c k e ts w i t c h i n g ) 光包交换网络：基于e t h e m e t 、a t m 和i p 的电包交换技 术的成功也刺激了光包交换网络的研究，光包交换网络与传统的电域包交换网络非常相 似，只不过是光包交换网络没有任何光一电一光的转换，它所有的处理都是在光域进行的， 并且在光交换机处需要光缓冲器，它需要快速的光交换机制和先进的端到端的资源预留机 制，f d l 缓冲池可以用来解决光包冲突。它的最大的特点就是能快速的传输数据，但是由 于光技术和光器件成本的限制，这只是一种理想化的网络，在现有的条件下还不能有实际 的实现。 o b s ( o p t i c a lb u r s ts w i t c h i n g ) 光突发交换：光突发交换网络结合了前两种传输体系的优 点并且克服了它们的缺点而提出的一种新的网络传输体系，o b s 网络与一般的光网络的最 根本的区别就是o b s 网络中传输数据需要两个部分：1 ) 控制信息包：它包含一些控制信息 像o f f s e t t i m e 、b u r s t 长度、目的地址、c o s ( 服务类别) 优先级等。2 ) 数据突发包：它在边 缘节点按照一定的算法被组装，它包含多个i p 包。还有在o b s 网络中采用的是单向资源预 留机制，它首先发送控制包，然后经过一定的o f f s e tt i m e 再发送数据包。下面这个图能很好 的说明o b s 网络的整体情况。 图1 3o b s 网络环境 在o b s 中有限制偏射路由研究 1 4o b s 网络研究现状 在现行的光网络中，主要有三种网络体系结构；o c s ( o r l t i c a lc i r c u i ts w i t c h i n g ) 也 就是w a v e l e n g t hr o u t i n g i nw d m n e t w o r k s 、o p s ( o r i t i c a lp a c k e ts w i t c h i n g ) 、o b s ( o p t i c a l b u r s ts w i t c h i n g ) 。o c s 是很容易去实现，但是对于动态的通信量和链路状态缺乏灵活性， o b s 与o c s 相比就是有一个比较细的粒度和更好的带宽利用灵活性；o p s 是理想的，但是 它对光技术要求很高，就现在的光技术发展的情况来看还不能满足它的要求，o b s 与0 p s 相比就是有一个相对粗的粒度和一个适中的交换时间；0 b s 就是结合了这两者的优点的一 种新的体系结构 3 1 。目前对0 b s 网络的研究主要集中在以下几个方面： ( 1 ) o b s 网络边缘节点的突发包组装：英国剑桥大学的d a m o nw i s c h i k 和伦敦大学 的m d u s e r 用大偏差理论来估计自相似业务流中数据分组长度的均值和方差，进而提出利 用估计值来使突发包长度获得稳定的自适应组装算法；台湾新竹交通大学的m c y u n g 提 出了称为q b t ( q o sb u r s t i f i e a t i o n ) 组装算法，它着眼于在不同类的业务之间保证公平性。 此外，还有其他一些关于组装算法的研究报道。虽然理论分析表明上述组装算法都可以得 到定的效果，但它们都过于复杂。因此，目前用于o b s 研究的最通用的算法仍然是传统 的基于组装时间加突发包长度限制的算法。 ( 2 ) o b s 信令协议：美国纽约州立大学的m y u n g s i ky o o 和c h u n m i n gq i a o 提出了适 用于o b s 的带宽效率很高的传输协议j e t ( j u s te n o u g ht i m e ) 协议，该协议还能利用 额外的偏置时间来在o b s 网络中实现对业务q o s 的支持；t e l c o r d i a 公司的j o h ny w e i 等 人提出将j i t 协议用于o b s 网络，并在m o n e t 平台上做了j r r 协议的实验。 ( 3 ) o b s 网络节点结构：波士顿n o k i a 研究中心的s a n j e e vv e n n a 对o b s 与 i p o v e r - d w d m 的结合进行了研究，提出了网络边缘节点处m a c 层的功能结构；华盛顿大 学的j o n a t h a ns t u r n e r 和a l c a t e l 美国分公司的y i j u nx i o n g 也对o b s 网络节点的结构进 行了研究和设计。 ( 4 ) o b s 网络核心节点的信道调度算法：j o n a t h a ns t u r n e r 提出了水平调度算法， 该算法也被称为l a u c 算法；a l c a t e l 公司的l i u b i at a n e e v s k i 在l a u c 算法的基础上提出 了效率更高的l a u c v f 算法；美国得克萨斯大学的m e iy a n g 提出了一种支持q o s 的调度 算法，该算法以l a u c v f 为基础，采用了高优先级的突发包先分配信道的策略；鉴于 l a u c 和l a u c - v f 都是按控制分组到达顺序分配信道的调度算法，韩国的j i n - b o n g c h a n g 提出了一种按突发包到达顺序分配信道的调度算法f a f a v f ( f i r s ta r r i v a lf i r s t a s s i g n m e n tw i t hv o i df i l l i n g ) ，其仿真研究表明：在相同条件下，f a f a v f 算法与l a u c v f 算法相比可以使突发包丢失率得到一定程度的降低。此外，日本的m i i z u k a 等人也提出一 个与f a f a v f 类似的调度算法。 4 在o b s 中有限制偏射路由研究 ( 5 ) 突发包竞争的解决方案：这方面的研究多集中在o b s 网络中的光缓存管理和偏 射路由方面。此外还有几种技术，如s a n j e e vv e r m a 提出的突发包数据流整形技术和意大 利罗马大学的a n d r e ad e t t i 提出的组合式突发包技术o c b s ，以及得克萨斯大学的v i n o dm v o k k a r a n e 提出的突发包分段技术。 ( 6 ) o b s 网络的数学理论建模：目前，对o b s 的研究绝大多数都是基于计算机仿 真的方法，而采用数学分析方法的研究很少，但已经开始起步。比如，北卡罗来纳大学的 l i s o n g x u 提出了0 b s 网络边缘节点的一种数学理论模型。 ( 7 ) o b s 与其他技术的结合：这方面也有一些研究报道。例如，一部分学者研究了 o b s 在网络组播方面的应用；c h u n m i n gq i a o 提出了标记o b s ( l o b s ) 的概念；还有一 部分学者研究了o b s 与波长路由技术的结合。 除了上述理论方面的研究，o b s 实验系统设计方面的研究工作也开始出现。美国华盛 顿大学的“太比特突发交换技术”项目就是其中比较早的一个。该项目从硬件上设计了一 个具有突发交换能力的核心节点，但其最初采用的交换矩阵是电的a t m 交换矩阵，因而 实现的不是严格意义上的o b s 。不过，该项目中设计的控制单元具有通用性，而且该项目 在后续的研究中也开始引入了光交换矩阵。另外，美国北卡罗来纳大学的i l i ab a l d i n e 等人 在其研究项目“j u m p s t a r t ”中对j i t 协议在o b s 中的应用进行了研究，而p r o n i t am e h r o t r a 等人则设计了一种可用于o b s 网络的网络处理器。我国2 0 0 2 年的“8 6 3 计划”中，也把 建立光突发交换实验系统定位“光突发交换关键技术和实验系统”的研究目标，目前，该 项目正在紧张地进行中。 迄今为止，尽管o b s 的研究取得了相当的进展，但o b s 仍然处于实验室研究阶段。 真正的o b s 网络还不存在，o b s 离商用化尚有一段距离。o b s 还有一些问题尚未解决， 在诸如o b s 网络如何支持i p 等业务、如何把来自不同网络的数据适配进o b s 网络并组 装成突发包、如何最有效地解决突发包之间的竞争、o b s 协议及其具体实旄、o b s 与 m p l s 的结合以及o b s 网络节点的硬件实现等问题上还需要进一步的研究。 1 5 本文主要的研究内容 因为在0 b s 网络中采用的是单向资源预留机制，在b h p 和突发数据包之间没有确认， 所以就容易产生冲突，为了达到一个很好的q o s ，在核心节点有效的冲突解决方法是很重 要的。本文的研究工作主要是在o b s 网络中突发包在发生冲突的情况下怎样解决突发包竞 争的问题。本文的主要工作和创新之处如下： 分析了常用光网络体系结构的优缺点。 对o b s 网络进行系统、详细的介绍。 5 在o b s 中有限制偏射路由研究 通过比较各种冲突解决方法，采用偏射路由上正常流量的端到端总丢包率来确定每个 节点的最大丢包率，提出了有限制偏射路由。 对于最短路径随机偏射路由算法进行改进，在此偏射路由算法上加上一个检测函数， 该检测函数可以以偏射路由上包的丢失率为判断条件，以此来决定是否来偏射这个冲 突的突发包。 增加了节点的重发机制，在突发包被丢弃的情况下，采取在o b s 层重发机制，减少 了数据突发包的在网络中的传输时间。 6 在o b s 中有限制偏射路由研究 第二章0 b s 网络和偏射路由 2 10 b s 网络的概述 自从上世纪末由c h u n m i n gq i a o 和j o n a t h a ns t u r n e r 分别提出o b s n 现在，虽然只有短 短几年的时间，但是o b s 已经受到了国内外越来越多的研究机构和学者的重视。目前，美 国、日本、韩国、欧洲、我国大陆和台湾等国家和地区都有研究机构从事o b s 方面的研究。 其中较有影响的有美国的纽约州立大学、华盛顿大学、卡罗来纳大学以及阿尔卡特公司美 国分公司等。在我国，2 0 0 1 年和2 0 0 2 年连续两年的“8 6 3 计划”都把o b s 列为前沿性探索 类( a 类) 课题。 2 1 10 b s 网络边缘节点的组装和拆解 在o b s 网络边缘节点的突发包的组装和拆解是在电域进行的，突发包的组装参数和算 法影响网络的q o s 。在o b s 网络的一个接入节点，它把接收到的数据按照不同的目的地 址、q o s 或者m p l s 等进行分类，它把具有相同一类的数据放在一个队列里，等待着突发 包组装算法来对这个队列的数据进行组装成一个新的突发包，这个新的突发包包含多个i p 包。在组装新的突发包的同时也产生了b h p ( 突发包头部控制包) ，这个b h p 它包含一些 控制信息像o f f s e tt i m e 、b u r s t 长度、目的地址、c o s ( 服务类别) 优先级等【4 j ，两者被 传送到发射缓冲区里，并且按照一定的调度策略首先把突发包的b h p 发送到0 b s 网络里， 然后再把这个突发包发出。 把多个i p 包组装成一个突发包的好处是可以在光网络里进行更有效的传输，可以减少 很多的控制信息，同时还可以减少在o b s 网络里核心节点的交换机对转发和交换的需求， 这就确保了在核心节点的高传输速率不是必须要很短的交换和转发的时间，而是可以通过 把多个口包组装成一个突发包来补偿这个时间。由于这个突发包的组装是在客户层完成的 而不涉及到o b s 网络服务层，所以o b s 网络能传输各种不同的网络技术的数据。 图2 1 边缘节点的工作策略 在边缘节点的突发包的拆解也就是突发包组装的逆过程，当收到一个数据突发包的时 7 在o b s 中有限制偏射路由研究 候根据它的b h p 的控制信息来对它进行分解成多个i p 包。 这个包的组装和拆解的优点是以在o b s 网络边缘节点( 组装节点和拆解节点) 增加 额外的功能为代价的，由于包的收集、组装、调度和拆解是在电域进行的，它的实现比在 o b s 网络核心节点实现要容易的多。o b s 网络边缘节点的通信量的聚集、突发包的组装和 突发包的发送模型在一些文章了都被做了仔细的描述。 2 1 2o b s 网络里的资源预留 o b s 网络里为每个突发包进行资源预留是通过b i - i p 控制包来进行的，这个控制包 是在一个专门的波长信道上进行传输的，这个资源的预留是一个端到端的范围，同时突发 包调度也应用在o b s 网络核心节点资源的选择和管理。在o b s 网络里采用的是单向资源 预留机制，- 即数据比预约请求稍后发出，而无需等待资源成功预约的应答，在b h p 和突发 包之间没有确认，由于无需等待应答信号，这种信令方式能使网络时延大大降低。 预约请求( 即控制包) 是在一个独立的信道传送，且比相应的突发数据包提前一个偏 置时延。这个偏置时延必须足够大，以使得中问节点能够及时的进行电子处理和为即将抵 达的突发数据包配霞光开关矩阵。当一个突发抵达交换节点时，相应的交换矩阵已经建立， 所以突发数据包可一直保持在光域内。 c h u n m i n g q i a o 提出的j u s t - e n o u g h - f l m e ( j e t ) 协议垆】，采用了两种独特的特性，即偏 置时间和延迟预留，在控制包和突发之间保留足够的时间，使得中间节点能够在突发抵达该 节点前及时处理。如图2 1 所示，源节点先发送一个b h p ，随后发送突发数据，两者之间的 偏置时间t 兰( 图中假设节点数为h ，且在每个节点处b h p 的平均时延为 ，则_ i ) 。 由于突发数据在源节点被缓存于电域，所以在b h p 传输期间，中间节点无需使用f d l 。 sd 图2 2j e t 协议的基本思想 j e t 使用d r ( d e l a yr e s e r v a t i o n ) 如图2 2 所示。在节点i ( i = l ，2 ，) 处，输出链路上的带 宽从突发数据预期到达时间t 开始预约，而非时间r ( b h p 处理完毕，已作带宽预约请求时 间) 。这里，t - - - t + t ( i ) ，t ( i ) 取决于偏置时间t 和b h p 在节点i 的处理时间。带宽预约直至预期 突发数据离开该节点时p j t + l ( 1 为预期突发数据的时长) 。 8 在o b s 中有限制偏射路由研究 图2 3j e t 的延迟预留 2 1 30 b s 网络里突发包的调度 由于资源预留是一个端到端的过程，所以数据突发包为了在网络上的传输不得不在 o b s 网络核心节点被调度，j o n a t h a ns t u r n e r 提出了水平调度算法，该算法也被称为 l a u c 算法；a l c a t e l 公司的l j u b i at a n c e v s k i 在l a u c 算法的基础上提出了效率更高的 l a u c v f 算法。 l a u c 算法：它的基本思想就是为到达的数据突发选择最近可用未调度数据信道。给定 数据突发到达光交换矩阵的时间为t 和数据突发持续时间为l ，交换控制单元首先查 找t 时刻是否有未被调用的可用输出数据信道，如果至少有一个输出数据信道未被调 度，则选择最近可用未调度信道，也就是选择时刻t 和上一个数据突发结束时刻之间 间隙最小的信道携带数据突发，被选中的数据信道未调度时间更新到( t + l ) 。 l a u c v f 算法：它的基本思想就是为每一个新到达的突发数据选择最近可用的信道来 最小化它们的空隙。假设数据突发到达的时间为t ，它在光交换矩阵中的持续时间为t ， 交换控制单元首先从数据信道中找到从时间t 到t + l 这段时间没有被使用的数据信道， 如果至少存在一条满足此条件的信道，那么就在这些信道中选择最近可用的信道，具 体的说就是在这些信道中找出时刻t 和该信道上t 时刻前的一个突发数据的离开时刻 之间差值虽小的信道。 其他的一些调度算法：美国得克萨斯大学的m e iy a n g 提出了一种支持q o s 的调度算 法，该算法以l a u c - v f 为基础，采用了高优先级的突发包先分配信道的策略；鉴于 l a u c 和l a u c v f 都是按控制分组到达顺序分配信道的调度算法，韩国的j i l l b o n g c h a n g 提出了一种按突发包到达顺序分配信道的调度算法f a f a - v f ( f i r s t a r r i v a lf i r s t a s s i g n m e n tw i t hv o i df i l l i n g ) ，其仿真研究表明：在相同条件下，f a f a v f 算法与 l a u c - v f 算法相比可以使突发包丢失率得到一定程度的降低。此外，日本的m i i z u k a 等人也提出一个与f a f a v f 类似的调度算法。 2 1 40 b s 网络冲突解决 因为在o b s 网络中采用的是单向资源预留机制，在b h p 和突发包之间没有确认，所以就 容易产生冲突，为了达到一个很好的0 0 s ，在核心节点有效的冲突解决方法是很重要的。 到目前为之，0 b s 冲突解决方法的研究仍然是集中在单一的核心节点或者是具有均衡通信 9 在o b s 中有限制偏射路由研究 量的网络拓扑环境中。在理论上o b s 网络中冲突解决的方法主要是下面的3 个方面【6 】： 1 ) 在波长域方面：在w d m 网络中，两个光交换机之间的光纤链路可同时运行多个 波长。可以利用多个波长来减少冲突。我们设想两个突发包需同时经同一个输出端口向外 发送。两个突发包均可以被发送，不过要在两个不同的波长。这个方法在减小外部阻塞上 有一定的潜能，因为在单个光纤上运行的波长数目不断地在增加。例如，在不久的将来一 个光纤上就可以有1 6 0 - 3 2 0 个波长。波长转换是一个将输入信道上的波长转换到输出信道的 另一个波长