（通信与信息系统专业论文）稀疏波长变换的wdm光网络阻塞率算法研究.pdf

摘要 摘要 随着网络业务量的爆炸性增长以及高性能的光网络设备( 如光交叉连接器 o x c 、光分插复用器o a d m ) 的出现，波分复用技术( 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 ) 将成为下一代骨干网络的核心技术。w d m 技术对光纤巨大带宽的充 分利用可以导致传输数据的价格大幅度的降低，这使它已经成为广域骨干网络中 最具吸引力的技术，而且可以预言在不远的将来，它还会在其他网络领域中得到 更广泛的应用。 w d m 光网络中，波长变换技术是一项关键技术，然而其使用却一直备受争议。 波长变换技术具有改善网络的性能，简化网络的控制等一系列的优点，但是由于 目前技术的限制，制造理想的全光波长变换器还很困难，而且波长变换器仍处于 实验室制造阶段，当它商用化时，价格将较昂贵。由于技术和价格的限制，有限 范围波长变换的研究和稀疏节点波长变换的研究应运而生。 本文在结合了国内外大量文献资料的分析方法和重要结论的基础上，首先针对 w d m 网络中节点具有部分波长转换能力时网络阻塞率的计算这个问题提出了两 种新的理论分析模型独立模型和关联模型，通过理论推导对网络阻塞率进行 了分析，并结合仿真结果得出了一些重要的结论。接着，对于w d m 光网络中只 有部分节点具有全波长转换能力时网络阻塞率的计算这一问题也提出了其独立模 型的解法。随后本文对全网平均阻塞率的计算问题进行了分析并针对几种常用拓 扑结构网络阻塞率进行了计算并得出相应的结论。再接着介绍了w d m 光网络阻 塞率计算的仿真软件平台和主要数据结构代码，并利用这个仿真平台考察了各种 模型的性能优劣。最后是全文总结。 关键词：阻塞率，全光网，波长路由，波长分割复用，稀疏波长变换 a b s t r a c t a b s t r a c t w i t ht h ee x p l o s i v ei n c r e a s ei nn e t w o r kt r a f f i ca n dt h ee m e r g e n c eo fh i g h p e r f o r m a n c eo p t i c a ln e t w o r kd e v i c e s ，s u c ha so p t i c a lc r o s s c o n n e c t ( o x c ) a n do p t i c a l a d d d r o pm u l t i p l e x e r ( o a 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 ( w d m ) t e c h n o l o g y b e c o m e st h ec o r et e c h n o l o g yo fn e x tg e n e r a t i o nb a c k b o n en e t w o r k s b e c a u s et h i s t e c h n o l o g yc a nf u l l yu t i l i z et h ee n o r m o u sb a n d w i d t ho ft h eo p t i c a l f i b e rt ot r a n s f e r t h ed a t a ，t h ep r i c ef o rt r a n s f e rd a t ac a nb eg r e a t l yd e c r e a s e d t h i se n a b l e si tt ob et h e m o s ta t t r a c t a b l et e c h n o l o g yi nw i d eb a c k b o n e ，n e t w o r k i ti sp r e d i c t e dt h a t i nt h ei l e a l f u t u r e ，t h ew d mt e c h n o l o g yw i l lb eg r e a t l yu s e di no t h e rn e t w o r k s i nw d m n e t w o r k ，t h et e c h n o l o g yo fw a v e l e n g t hc o n v e r s i o ni sak e yt e c h n o l o g y , b u ti ti sa l w a y st h ef o c u so ft h ec o n t e n t i o n a l t h o u g ht h ew a v e l e n g t hc o n v e r s i o nc a n i m p r o v et h ep e r f o r m a n c eo fn e t w o r k ，s i m p l et h ec o n t r o lo fn e t w o r ka n ds oo n ，i ti s d i f f i c u l tt om a n u f a c t u r et h ei d e a la l l o p t i c a lw a v e l e n g t hc o n v e r t e rd u et ot h el i m i to ft h e t e c h n o l o g y a n dm o r et h et e c h n o l o g yi sn o w i nt h el a b o r a t o r y , w h e ni ti so nc o m m e r c i a l u s e ，t h ep r i c ew i l lb ev e r ye x p e n s i v e h o wt oo v e r c o m et h es h o r t c o m i n go ft h e t e c h n o l o g y ? t h et e c h n o l o g y o fm a n u f a c t u r i n gt h ew a v e l e n g t hc o n v e r t e rw i t h l i m i t e d r a n g ec o n v e r s i o nr a n g ea n dt h es p a r s ed i s t r i b u t i o no ft h ew a v e l e n g t hc o n v e r t e r a r eu n d e rr e s e a r c h b a s e do nm a n ya r t i c l e sb o t ha th o m ea n da b r o a d ，t h i sp a p e ra n a l y s e st h eb l o c k i n g p r o b a b i l i t yi nw d m n e t w o r k sw i t hl i m i t e d r a n g ew a v e l e n g t hc o n v e r s i o n f i r s t l yw e i n t r o d u c et w on e wm o d e l sn a m e dt h ei n d e p e n d e n c em o d e la n dt h ec o r r e l a t i o nm o d e lt o a n a l y s et h eb l o c k i n gp r o b a b i l i t yf o rt h el i m i t e d - r a n g ew a v e l e n g t hc o n v e r s i o nn e t w o r k s e c o n d l yw ei n t r o d u c et h ei n d e p e n d e n c em o d e lt oa n a l y s et h es p a r s ew a v e l e n g t h c o n v e r s i o nc a s e t h e nw ec o m p u t et h em e a nb l o c k i n gp r o b a b i l i t yf o raw h o l en e t w o r k a n dd i s c u s ss o m en e t w o r kt o p o l o g i e si nc o m m o nu s e a tl a s tw ee s t a b l i s hap l a t f o r m u s i n gc c + + l a n g u a g et o s i m u l a t et h eb l o c k i n gp r o b a b i l i t yo fn e t w o r k s w ed r a wa c o n c l u s i o nf o ro u rs t u d ya tt h ee n do ft h ep a p e r k e y w o r d s ：t h eb l o c k i n gp r o b a b i l i t y , a o n ，w a v e l e n g t hr o u t i n g , w d m ，s p a r s ew a v e l e n g t h c o a v e r s i o n 简略字表 简略字表 a s o na u t o m a t i cs w i t c h e do p t i c a ln e t w o r k自动交换光网络 n n in e t w o r k - t o - n e t w o r ki n t e r f a c e网络网络接口 o a d m o p t i c a la d d - d r o pm u l t i p l e x e s 光分插复用器 o t n o p t i c a lt r a n s p o r tn e t w o r k 光传送网络 0 v p n o p t i c a lv i r t u a lp r i v a t en e t w o r k 光虚拟专用网络 o x c o p t i c a lc r o s sc o n n e c t 光交叉连接器 月 倒 r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t 选路与波长分配 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 同步数字系列 u n i u s e r - t o - n e t w o r ki n t e r f a 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 i n g 波分复用技术 l d pl a b e ld i s t r i b u t i o np r o t o c o l标记分发协议 盯m a s y n c h r o n o u st r a n s f e rm o d e 异步传输模式 a p i a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e 应用程序接口 c d m ac o d ed i v i s i o nm u l t i p l ea c c e s s 码分多址 s o n e t s y n c h r o n o u so p t i c a ln e t w o r k 同步光纤网络 e d f a e r b i u m d o p e dh b e ra m p l i f i e r 掺珥光纤放大器 0 c h o p f i c a lc h a n n e l 光通道 a o n a l l o p t i c a ln e t w o r k s 全光网络 f w m f o u r - w a v em i x i n g 四波混频 x g mc r o s s g a i nm o d u l a t i o n交叉增益调制 x p mc r o s s p h a s em o d u l a t i o n交叉相位调制 t d mt i m ed i v i s i o nm u l t i p l e x i n g 时分复用技术 m e m sm i c r o e l e c t r o m e c h a n i c a ls y s t e m微电子机械系统 w c w a v e l e n g t hc o n v e r t e r 波长变换器 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：溘滋日期：渺6 年f 月可日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 李晕氏 日期：2 6 d 年占月2 日 第一章绪论 第一章绪论 光纤有着巨大的频带资源和优异的传输特性，是实现高速率、大容量传输的 最理想物理媒质。传统的骨干网络使用的是s o n e t s d h ( s y n c h r o n o u s o p t i c a ln e t w o r k s y n c h r o n o u sd j 【g i t a lh i e r a r c h y ) 技术，传统的s o n e t s d h 技术以 特定的传输速率但5 g b s 或1 0 g b s ，将来渴望提高到4 0 g b s ) 在光纤中1 5 5 0 n m 附近的单个波长信道上传输数据，传输带宽的增加只能单纯依靠提高单个波长的 传输速率来实现【1 】os o n e t s d h 技术需要电的时分复用( t d m ：t i m e d i v i s i o n m u l t i p l e x i n g ) ，而电领域的处理速度由于受量子理论的限制，提高的速度有限，目 前认为4 0 g b s 是单个波长最高实用化的速率，这些都使传统的s o n e t s d h 技 术越来越不能适应数据网络发展的要求。光的波分复用( w d m ：w a v e l e n g t hd i v i s i o n m u l t i p l e x i n g ) 技术正是顺应此潮流而生的产物。 1 1w d m 网络技术的起源与发展 近几年来，密集波分复用技术的发展提供了利用光纤带宽的有效途径，使点 到点的光纤大容量传输技术取得了突出进展。w d m 技术由于能充分利用光纤的 巨大带宽，正在成为骨干长途网中最具吸引力的技术【z j 。光纤的带宽可以达到几十 t b s ，w d m 技术可以把光纤巨大的带宽划分成许多不相重叠的波长信道，每个波 长信道占用一个波长，波长信道的速率在目前电信号处理的速率极限内，在光纤 中可以同时传送多个波长信道的数据。目前商用化的为每光纤3 2 个波长，最高 达到1 6 0 个波长，实验室已达到1 0 0 0 个波长。w d m 技术的普遍应用主要得益 于以下几点：1 光器件和系统价格的下降导致电信骨干网络的设计产生巨大改变， 在以往的设计规划中，鉴于光器件的昂贵，都是尽量少用光器件而多用电器件， 而在过去的十年中，随着光设备和系统的不断进步，w d m 设备的价格不断下降 从而推动其商业化。2 i n t e r n e t 网络中数据业务量爆炸性的增长，使网络承运 商在网络的各个部分，从接入到核心都面临严重问题。3 w d m 技术的发展，提 高了每条光纤可承载的波长数，同时每个波长信道承载的速率也得到提高。这些 电子科技大学硕士学位论文 都极大地推动了w d m 网络的进一步发展。 9 0 年代以来，随着“信息高速公路”的建设，世界发达国家都在逐步引入 w d m 设备，美国各大长途电话公司已经在其骨干网络中基本实现w d m 传输。 我国从1 9 9 7 年开始引入w d m 设备，同时也在进行w d m 网络的设备的研发 和制造，目前光通信的发展已经初具规模。中国电信在多条省级光缆干线上已经 使用了w d m 技术，在2 0 0 0 2 0 0 4 年间又将采用w d m 技术对我国“八纵八横” 光缆网进行改造和升级。2 0 0 0 年1 0 月2 8 日，中国网通开通宽带高速互联网 c n c n e t ，该工程一期工程已建成8 4 9 0 公里，1 0 6 个中继站，贯通了东南部的1 7 个重点城市，网络总传输带宽高达4 0 g b s 。目前点到点的w d m 传送技术已经 成熟，并且已经大量在长途干线和海底光缆系统中使用。已经有许多公司研制出 一些成熟的产品，如日本h a c h i 的a m n 6 0 0 0 、l u c e n t 的w a v e s t a ro l s 4 0 0 g 以及n o r t e ln e t w o r k s 的m u l t i - w a v e l e n g t ho p t i c a lr e p e a t e r ( m o 鼬p l u ss y s t e m 等，这些w d m 产品可以处理的数据传输速率高达3 2 0 g b i t s 或4 0 0 g b i t s 。 从9 0 年代以来，全光网络的研究掀起了一阵高潮，欧、美、日等发达国家 都投入大量的科研经费对全光网络，尤其是光传送网络f 0 t n ：o p t i c a lt r a n s p o r t n e t w o r k ) 的各个方面，从器件到网络体系结构，样机的制造，现场的测试等等进行 了详细的研究，目前许多研究成果都已经商用化，产生了巨大的经济效益，这些 技术的发展使未来实现透明、灵活、经济且具有高度生存性的光网络成为可能。 1 2w d m 光网络器件技术的现状及发展 经过十几年的研究和发展，支持w d m 技术的光器件水平已经达到了一个新 的台阶1 3 1 ，这将为w d m 技术的进一步发展铺平道路，我们将主要从以下两个方 面来介绍这些技术： 1 超大容量，超长光纤传输系统 传统的光纤在频率为1 3 8 5 n m 的波长处有一个很高的信号衰减区，在以前的 w d m 网络中要尽量避免用这个信号衰减区内的波长，这样就会对光纤的容量有一 定的影响，最新的一个令人激动的技术是制造一种全波( a l lw a v e ) 范围的光纤，克 服了这个信号衰减区，使其中的波长也可以被利用。这样就可以大大提高光纤的 容量。但是，仅仅提高光纤容量还是不够的，为了使光纤中的信号传输的更远， 还要有光纤放大器( f i b e ra m p l i f i e r ) 来配合。传统的s o n e t s d h 系统中的放大 第一章绪论 器是光电型的，即在光信号衰减到一定程度时，通过光电转换成电信号，再进行 放大和整形，然后再转换成光信号在光纤上继续传输。在w d m 中，用掺珥光纤 放大器( e d f a ：e r b i u m d o p e df i b e ra m p l i f i e r ) 可以实现直接在光领域中对信号进行 放大。一般的e d f a 的频谱只有3 0 - - 4 0 n m ( - - 般从1 5 3 0 n m - - 1 5 6 0 n m ) ，这样光纤 传输的信号就被要求在e d f a 的频谱之内，实际上限制了光纤的容量。最新的技 术可以大大扩展e d f a 的频谱，从而可以对全波光纤中的所有承载光信号都能进 行放大。另个新技术是赫曼( r a m 砌放大器，它与e d f a 放大器配合使用，可 以使放大器产生的串扰大大降低。从而大大延长了光信号的传输距离( 最高可以达 到4 0 0 0 k m ) 。 2 先进的光交换设备 光交换设备是光网络的一个重要组成部分，机械的，热光的和直接耦合的模 块是制造光交换单元的必须工具 4 1 。传统的机械和固体波导( g u i d e w a v e s o l i d s t a t e l 光交换设备已经不适合商用，因为其尺寸大，交换速度慢，串扰大，只能支持有 限的级联( c a s c a d a b i l i t y ) 。最佳的一项新技术微电机械系统f m e m s ： m i c r o e l e c t r o m e c h a n i c a ls y s t e m ) 可以制造高性能，高集成度的光交叉设备，m e m s 系统具有低串扰，小尺寸等优点，将会在全光网络中得到广泛的应用【”。 1 3w d m 光网络阻塞率的算法问题及研究现状 在w d m 骨干网络中，可以用波长进行路由，故又称波长路由网络。一个波 长路由网络由许多波长路由器和连接它们的光纤链路组成。每根光纤链路利用波 长分割复用( w d m ) 技术支持许多不同的波长通道，而波长路由器根据其波长把 输入光纤的信号转接到输出光纤上去。在一个动态的波长路由w d m 网络中，一 系列源宿结点间的连接请求随机到达并且持续一个随机时间，由于网络容量的限 制，一些连接请求可能不能被满足，这些连接就被阻塞了。波长路由w d m 网络 设计的一个主要目标就是使全网的平均阻塞率最小【6 j 。 根据组成 w d m 网络的节点是否具有波长转换能力，我们可以把波长路由网 络分成以下几类：第一类网络中所有节点均没有波长转换功能，光通道在不同的 光纤段中必须使用同一波长。这样，为了建立一条波长通道，光网络必须找到一 条路由，在组成这个路由的所有光纤段中，有一个公共的空闲波长，如果找不到 这样一条路由则发生阻塞，这个被称为波长连续性限制。第二类网络中所有节点 3 电子科技大学硕士学位论文 均具有波长转换功能，光通道在不同的光纤可以占用不同的波长，从而提高了波 长的利用率，降低了网络的阻塞率。第三类网络介于二者之间，即网络中只有部 分节点具有波长转换能力，其阻塞率也介于前两类网络之间。 在没有波长转换器( 无w c ) 的波长路由网络中，某个源宿节点对间的连接 请求能够建立的条件是在组成这个连接路由的各个链路上，至少存在一个没有被 占用的公共空闲波长，即必须满足波长连续性限制用。波长连续性限制网络不同于 传统的电路交换网络( c i r c u i ts w i t c hn e t w o r k s ) 之处在于，即使在链路上有空闲容 量，也有可能导致阻塞。如图1 1 所示，图中节点1 和节点2 之间用 l 波长， 节点2 和节点3 问用x2 波长，若只有二个空闲波长，则要建立一条从节点1 到 节点3 的光路是不可能的。由此看出，波长连续网络比电路交换网络有更高的阻 塞率。 节点1节点2节点3 图卜1 波长连续性限制示意图 在全波长转换器( 全w c ) 的波长路由网络中，某个源宿节点对间的连接请求 能够建立的条件是组成这个连接路由的各个链路都至少存在一个空闲波长，这种 情形与数字电话系统的电路交换类似。显然，因为不需要满足波长连续性的条件， 全波长转换器网络的阻塞率会大大小于无波长转换器网络的阻塞率。 显然，波长转换器( w a v e l e n g t hc o n v e r t e r ，w e ) 在提高网络性能方面起着十 分重要的作用。但是在目前的技术水平条件下，波长转换器还是一种比较昂贵的 器件，不太可能全网所有节点均配备为w c ，所以有必要也对介于二者之间的情况， 即网络中只有部分节点为波长转换器的情况进行分析，以找到网络造价和性能之 间的最佳平衡点p 1 。 对于这几种不同的波长路由网络，以前的一些书籍和文章均做了比较详细的 分析和研究，主要提出了两种理论模型算法，并结合仿真结果得出一些结论1 9 j 。这 两种理论分析模型在以前的文献中分别称为独立模型( t h ei n d e p e n d e n c em o d e l ) 和关联模型( t h ec o r r e l a t i o nm o d e l ) ，所谓独立模型即不考虑链路之间的关联性， 认为相邻的两条链路是彼此独立的，而关联模型则考虑了链路之间的马尔可夫性， 4 第一章绪论 认为相邻链路之间是相互关联的。这两种模型都有各自的优势和局限性，其中独 立模型( t h ei n d e p e n d e n c em o d e l ) 由于假设各个链路之间的负载是彼此独立的， 即不考虑链路之间的关联性，这种假设会稍微过高估计网络的阻塞率，对连接比 较稀疏的网络( 如环网) 的分析结果会比较粗糙，但随着网络连接度的增加结果 会比较接近实际仿真值。独立模型的一个优点是计算复杂度较低，能在比较短的 时间内得到网络阻塞率的结果。而对于关联模型( t h ec o r r e l a t i o nm o d e l ) 来说， 由于它假设链路负载是彼此关联、互相影响的，考虑了链路之间的马尔可夫性， 所以对网络阻塞率计算的结果是比较精确的，但是它的计算复杂度比较高，耗时 较长。实际运用时需根据具体情况选择恰当的模型进行分析。 1 4 本文的主要贡献及内容安排 对于波长路由w d m 网络的阻塞率算法的问题，以前的研究多是围绕全网均 没有波长转换器或全网均配备波长转换器的情况展开的，针对这两种典型的情况， 以前的文献分别运用独立模型和关联模型对网络阻塞率计算问题建立数学模型进 行分析1 1 0 l ，通过理论推导和仿真计算两种方法对其结果进行比较，得出了许多重 要的结论。接着有一些文献对网络中只有部分节点具有波长转换能力的情况进行 了分析【1 1 】，这种情况下虽然全网只有一部分节点具有波长转换功能，但这些节点 内部都配备了波长个数的波长转换器，其节点内部是全w c 的情况。以前的文献 对这种只有部分节点具有全波长转换能力情况的研究主要是运用关联模型建模对 网络阻塞率进行分析的，也得出了许多非常有价值的结论。实际中还有这么一种 情况，由于波长转换器( w c ) 在目前还是一种比较昂贵的器件，是否有必要在节 点内部配备全波长转换器这一问题还有待于研究，我们有可能仅仅在有限的输出 端口配置波长变换器就可以达到在所有端口配置波长变换器时的性能【1 2 】 1 3 】。对于 这个问题的研究现在国内外还很少涉及，即使有些文献对这种情况下网络阻塞 率的计算进行了一些分析，其研究结果也是建立在计算机仿真的基础上的，很少 看见有关于这方面问题的完整理论分析模型和数学推导过程【1 4 】。本文在借鉴了以 前一些文献的理论模型分析思路的基础上，针对w d m 网络中节点具有部分波长 转换功能时网络阻塞率的计算这个问题提出了两种新的理论分析模型独立模 型和关联模型，通过理论推导对网络阻塞率进行了分析，并结合仿真结果得出了 些重要的结论。 电子科技大学硕士学位论文 另外，本文也针对网络中只有部分节点具有全波长转换能力时网络阻塞率计算 这一问题，提出了一种新的方法对其进行了分析。以前的文献对这个问题的分析 方法多是运用关联模型，假设组成路由的链路之间满足马尔可夫性，从而建立多 维状态空间进行求解。这样虽然能得到比较精确的结果，但其计算复杂度非常大， 计算时间很长，实际运行中对于三跳的路径，已需要运行半小时左右，对于大于 四跳的路径，运行时间长达数小时甚至几天时间，而对于由若干多跳路径组成的 实际网络来说，其运行时间更是呈几何级数的增加，这极大的限制了该方法在实 际中的应用。本文对以前的理论模型进行了一些改进，提出了这个问题的独立模 型并对其进行了分析求解。通过新旧两种方法计算结果的对比可以看出这个新方 法是比较准确的，并且运用新的方法可以在很短的时间内求出网络的阻塞率，计 算复杂度较低，是一种高效计算部分波长变换网络阻塞率的手段。 下面简要介绍一下各章的内容安排： 第一章简要介绍了w d m 网络技术的起源与发展的过程，w d m 光网络阻塞率 的算法问题和现在国内外对这个问题的研究现状和进展情况，提出了本文对这个 问题新的研究进展和大致方向。 第二章针对w d m 网络中节点具有部分波长转换功能时网络阻塞率的算法这 个问题进行了数学建模，运用独立模型对其进行了理论推导并得出其典型单元阻 塞率的计算方法，进而推导出任意l 跳路径端到端阻塞率的计算方法，还通过建 立仿真模型对其结果进行了分析和比较。 第三章也是针对w d m 网络中节点具有部分波长转换功能时网络阻塞率的算 法这个问题，运用关联模型对其进行了数学建模并推导出任意l 跳路径端到端阻 塞率的计算方法。 第四章针对网络中只有部分节点具有全波长转换能力时网络阻塞率的计算这 一问题，提出了独立模型对其进行了理论分析，并根据分析结果得出了一些相应 的结论。 第五章对全网平均阻塞率的计算问题进行了分析并针对有向环网、网孔网、立 方体网络单元、全连接网等常用拓扑结构网络阻塞率进行了分析并得出了相应的 结论。 第六章介绍了w d m 光网络阻塞率计算的仿真软件平台，并利用这个仿真平台 考察了各种模型的性能优劣，还给出了仿真平台用到的一些重要数据结构以及主 要代码。 第七章为全文总结 6 第二章用独立模型分析有限范围波长转换网络阻塞率 第二章用独立模型分析有限范围波长转换网络阻塞率 2 1 研究背景 对于波长路由w d m 网络的阻塞率算法的问题，以前文献的研究多是围绕全 网均没有波长转换器或全网均配备波长转换器的情况展开的，针对这两种典型的 情况，以前的文献分别运用独立模型和关联模型对网络阻塞率计算问题建立数学 模型进行分析，通过理论推导和仿真计算两种方法对其结果进行比较，得出了许 多重要的结论。接着有一些文献对网络中只有部分节点具有波长转换能力的情况 进行了分析，这种情况下虽然全网只有一部分节点具有波长转换功能，但这些节 点内部都配备了波长个数的波长转换器，其节点内部是全w c 的情况。以前的文 献对这种只有部分节点具有波长转换能力情况的研究主要是运用关联模型建模对 网络阻塞率进行分析的，也得出了许多非常有价值的结论。实际中还有这么一种 情况，由于波长转换器( w c ) 在目前还是一种比较昂贵的器件，是否有必要在节 点内部配备全波长转换器这一问题还有待于研究，我们有可能仅仅在有限的输出 端口配置波长变换器就可以达到在所有端口配置波长变换器时的性能。对于这个 问题的研究现在国内外还很少涉及，即使有一些文献对这种情况下网络阻塞率的 情况进行了一些分析，其研究结果也是建立在计算机仿真的基础上的，很少看见 有关于这方面问题的完整理论分析模型和数学推导过程。本文在借鉴了以前一些 文献的理论模型分析思路的基础上，针对w d m 网络中节点具有部分波长转换能 力时网络阻塞率的算法这个问题提出了一种新的理论分析模型独立模型对其 进行了分析，理论推导出了典型单元阻塞率的计算公式，进而得出了任意l 跳路 径端到端阻塞率的计算方法。 2 2 数学模型分析 在没有波长转换器( 无w c ) 的波长路由网络中，某个源宿节点对间的连接 请求能够建立的条件是在组成这个连接路由的各个链路上，至少存在一个没有被 7 电子科技大学硕士学位论文 占用的公共空闲波长，即必须满足波长连续性限制。在全w c 的波长路由网络中， 所有节点均具有波长转换功能，光通道在不同的光纤段中可以占用不同的波长， 这样大大降低了网络阻塞率。而在节点具有部分波长转换能力的w d m 光网络中， 其阻塞率的分析和计算的方法与以前大不相同，下面用独立模型进行数学建模对 这个问题进行分析。 我们之所以称之为独立模型( t h ei n d e p e n d e n c em o d e l ) ，是因为假设各个链路 之间的负载是彼此独立、互不影响的，即不考虑链路之间的关联性。这种假设的 主要优点是简化了数学建模的过程，降低了问题的难度，其计算复杂度较低，能 在比较短的时间内得到网络阻塞率的结果。其缺点是会稍微过高估计网络的阻塞 率，对连接比较稀疏的网络( 如环网) 的分析结果会比较粗糙，但随着网络连接 度的增加计算结果将接近实际仿真值，对于网孑l 型网络( 如m e s h t o r u s 网) 的阻 塞率计算与实际仿真值相当吻合。 我们先对任意l 跳路径端到端的阻塞率进行分析，然后再对整个网络的阻塞 率进行计算。对于独立模型，假设某条路径r 由l 条首尾相连的链路组成，每条 链路都可以容纳c 个不同的波长，每个节点内部都含有f 个波长变换器( f c ) 。 连接请求的到达为泊松过程，持续时间服从l = 1 的指数分布。l 条独立的链路上 都有相应的业务请求，其到达率均为a ，另外还有一个从源节点到宿节点的业务流， 它经过了所有l 条链路，其到达率为ao ( ao a ) ，因为ao n ，x + y - n ( c x ) ，则互换球和盒子的概 念，即把( c y ) 看成盒子，把( c x ) 看成球，即可还原为第一种情况) ： 从c 个盒子中取出( c x ) 个不同颜色的盒子，从c 个球中取出( c v ) 个不 同颜色的球，把球放入盒子中使得恰有f 个球和盒子颜色不匹配的的放法数可如 下分步计算： 1 ) 从c 个球中取出( c y ) 个不同颜色的球，有( ：一。) 种方式。 2 ) 从( c y ) 个不同颜色的球中取出f 个和盒子颜色不匹配的球，有( ：。) 种 方式。此时余下的( c - y f ) 个球和盒子颜色是匹配的，不妨设第c - ( c y n + l 至第c 号球是匹配的。 l l 电子科技大学硕士学位论文 3 ) 将不匹配的f 个球( 不妨设第1 至第f 号球) 放入第1 至第c ( c y - f ) 号 盒子，使球i 不放入盒子i ( i = 1 , 2 ，z ) 中。设放法数为x ，则 x = ( c f - ( 。十) d f 。 4 ) 在余下的c 一( c - y f ) 一f = y 个盒子中取( c x ) 一( c y ) = y x 个盒子( 表示空盒) ， 有( ；一；) 种方式。 故由乘法原理可得恰有f 个球和盒子颜色不匹配的放法数为： 所以由古典概率论知识可知恰有f 个球和盒子颜色不匹配的概率为： p t 鱼止：巫兰竺垒：! ( 2 _ 7 ) 。2e 了。 lz 一， ( + ( ；) ( ) d ，。( 把p 代入p 4 ，再把p 4 代入p b 即可求得两跳路径单元的阻塞率为 p b = ( 1 q z ( o ) ) q 2 ( 0 ) + q l ( o ) ( 1 一q 2 ( 0 ) ) + q l ( o ) q 2 ( o ) + h 如巾积打筹鬻8 ) 对于l 跳路径的一般情况，我们可以利用两跳时的结论来计算其阻塞率，即 把前l 广1 跳看成第一跳，把第l 跳看成第二跳，不停的递归调用两跳时的计算公 2 3 仿真模型分析 以上部分用理论建模的方法分析了独立模型下的两跳路径节点具有部分波长 转换能力时其端到端的阻塞率，现在用c c + + 语言搭建网络平台来仿真两跳路径下 节点具有部分波长转换能力时端到端的阻塞率。对于两跳路径，我们可以如下建 立网络对此种情况进行仿真( 设链路波长数为4 ) ： 第二章 用独立模型分析有限范围波长转换网络阻塞率 。 凰 “ 1 b 国 。 目 图2 - 3 两跳路径单元仿真模型 其中8 条实线表示各个链路上不同的波长，其b a n d w i d t h 和c o s t 都设为1 。c o s t 为o 1 的6 条虚线表示耍使用波长变换器进行波长转换的情况，其b a n d w i d t h 设为 无穷大。c o s t 为0 的3 条虚线引出业务请求的源宿节点，其b a n d w i d t h 也设为无穷 大。由上面的这个转换图可以模拟两跳时节点具有部分w c 情况下的阻塞率，每 经过一个c o s t 为0 1 的虚线，其波长变换器的数目就减1 ，当没有波长变换器时， 就不能通过c o s t 为0 1 的虚线了，此时发生阻塞。 由以上方法可以得到两跳时在链路波长数c = 4 一定的情况f ，节点含有的波 长变换器数目f 变化时，阻塞率随链路负载量变换关系如表2 - 1 所示。 电子科技大学硕士学位论文 表2 - 1c = 4 时两跳路径端到端阻塞率随链路负载量变换关系 l a m b d a = 0 5l a m b d a = 0 6l a m b d a = 0 7l a m b d a = 0 8 l a m b d a = 0 9 l a m b d a = 1 0 f = 0p b = 0 7 1 1 p b = 1 3 0 5 p b = 2 1 4 0 p b = 3 2 3 0 p b = 4 5 7 9 p b = 6 1 7 8 f = 1p b = 0 5 3 9 p b = 0 9 8 9 p b = 1 6 2 3 p b = 2 4 5 4 p b = 3 4 8 5 p b = 4 7 1 2 f = 2p b = 0 4 0 1 p b = 0 7 5 1 p b = 1 2 5 8 p b = 1 9 3 8 p b = 2 8 0 1 p b = 3 8 4 8 f = 3p b = 0 3 2 0 p b = 0 6 0 2 p b = 1 0 1 2 p b = 1 5 6 7 p b = 2 2 7 7 p b = 3 1 4 8 f = 4p b - - 0 3 1 5 p b = 0 5 9 2 p b - - 0 9 9 2 p b = 1 5 3 0 p b = 2 2 1 5 p b = 3 0 5 3 由上表可以画出其变化关系曲线如图2 4 所示。 图2 4c = 4 时两跳路径端到端阻塞率随链路负载量变换关系曲线图 由图2 4 可以看出节点具有部分波长转换功能时，其曲线分布在全w c ( f = 4 时) 和无w c ( f - o 时) 的曲线之间，且波长变换器的引入能大大改善阻塞率，f = 3 时的曲线已经和全w c 时的情况很接近了。 2 4 本章小结 在本章中我们通过建立独立模型，研究了w d m 网络中节点具有部分波长转 换功能时网络阻塞率的计算这个问题。通过大量的概率论和组合数学的公式推导， 利用数学建模的方法首先对其两跳基本路径单元的阻塞率进行了理论分析，随后 1 4 第二章 用独立模型分析有限范围波长转换网络阻塞率 推广到一般的任意l 跳路径的情况。接着我们对这个问题建立了仿真模型进行分 析并得出了相应的一些结论。我们将在下一章利用关联模型对网络中节点具有部 分波长转换功能时网络阻塞率的计算这个问题作进一步的分析。 电子科技大学硕士学位论文 第三章用关联模型分析有限范围波长转换网络阻塞率 3 1 研究背景 在上一章中针对w d m 网络节点具有部分波长转换功能时网络阻塞率的计算 这个问题提出了一种新的理论分析模型独立模型对其进行了分析，理论推导