（计算机应用技术专业论文）全光网络中的流量疏导问题研究.pdf

全光网络中的流量疏导问题研究 摘要 i n t e r n e t 的迅猛发展极大地推动了光网络研究的进展，随着波分复用( w d m ) 技术 的日趋成熟，限制光网络传输容量的因素已不再是光纤带宽，而是网络中路由器、交换 机和复用器等电子设备的处理速度造成的瓶颈流量疏导技术的出现为解决这些问题提 供了一种有效途径 流量疏导是当今光网络研究中的一个前沿和热点问题，流量疏导研究的是如何将不 同速率、不同类型的低速业务流打包成高速数据流，复用到一个波长上的过程例如， 一个o c 一4 8s o n e t 环的一条光路可以同时支持1 6 个o c 一3 的通信请求全光网络中利用 的波分复用技术，是指一条光纤可以同时传输几种信号，每个信号使用不同的波长因 此，波长分配问题就是为每对通信请求找到一条光路并为之分配一个波长，且使得共享 一条链路的两条光路分配不同的波长用图论的术语讲，波长分配问题可以抽象为路染 色问题，即为给定的一个路径集合指定颜色，使得共享一条边的路径具有不同的颜色 一般，通信请求有一个粒度g ，称为疏导因子有效的路染色问题就是指至多有共享一 条边的g 条路径使用相同的颜色着色给定一个有效的路染色，一个a d m 至多可以被 使用相同颜色着色的2 9 条路径共享显然，最小化a d m 数是流量疏导问题的一个特例 ( g = 1 ) 1 9 9 8 年，o g e r s t e l ，r r a m a s w a m i 和g s a s a k i 等人提出了环形网络中流量疏导问题 的概念，并证明了其对一般的疏导因子g ，流量疏导问题是n p 完全的过去对流量疏 导问题的研究主要集中于环形网络，通过相关的证明得出了一些有意义的结果 2 0 0 6 年，m s h a l o m 和s z a k s 等人讨论了具有圈长至多是? 的预处理情形的近似算 法，并给出了其算法的性能保证及相关证明 本文主要研究最小化a d m 数问题和各种拓扑结构中的流量疏导问题共分为五章 本文讨论的问题大部分都是n p 一难问题，因此，我们主要集中于近似算法的研究 第一章简要介绍全光网络、s o n e t 环和流量疏导问题的基本概念，并给出了本文的 研究内容及组织结构第二章主要研究最小化a d m 数问题，对具有预处理阶段的近似算 法进一步改善分析，给出了一个更好的性能保证第三章研究单向s o n e t w d m 环中的 多播流量疏导问题，提出了具有更好近似比的近似算法，并证明了所使用的a d m 数与 网络中节点数的关系第四章研究将应用于环形网络中的近似算法进一步改善分析应用 于解决单向s o n e t w d m 环及一般拓扑结构中的流量疏导问题，得到了相似的结果第 五章总结全文，并提出下一步有待解决的问题 关键词：全光网络，波分复用，a d m ，流量疏导，s o n e t w d m 环 ab s t r a c t t h er a p i dd e v e l o p m e n to fi n t e r n e th a sg r e a t l yp r o m o t et h er e s e a r c hp r o g r e s so fo p t i c a l n e t w o r k a st h ew 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 ( w d m ) t e c h n o l o g ym a t u r e sg r a d u a l l y ， t h ef a c t o r st h a tr e s t r i c t i n gt h ec a p a c i t i e so fo p t i c a ln e t w o r kt r a n s m i s s i o ni sn ol o n g e rt h e b a n d w i d t ho ff i b e r ，b u tt h en e t w o r k sb o t t l e n e c kc a u s e db y , t h ep r o c e s s i n gs p e e do fe l e c t r o n i c e q u i p m e n t s ，s u c ha sr o u t e r s ，s w i t c h e sa n dm u l t i p l e x e r si nn e t w o r k s t h ee m e r g e n c eo ft r a f i i c g r o o m i n gt e d m o l o g yh a sp r o v i d e da le f f e c t i v ea p p r o a c ht os o l v et h e s ep r o b l e m s r e c e n t l y , t r a f f i cg r o o m i n gp r o b l e mi so n eo ft h er e s e a r c hf r o n t i e r sa n dah o tt o p o i ci n o p t i c a ln e t w o r ks t u d i e s t r a f f i cg r o o m i n gp r o b l e mm a i n l ys t u d i e sh o wt op a c kl o w e rr a t e t r a f f i cs t r e a m so fd i f f e r e n ts p e e d sa n dd i f f e r e n tt y p e so n t oh i g h e rr a t et r a f f i cs t r e a m sa n d m u l t i p l e xo n t ot h ea v a i l a b l ew a v e l e n g t h s ，e f f e c t i v e l y f o ri n s t a n c e ，al i g h t p a t ho fa no c 一4 8 s o n e tr i n gc a ns u p p o r tu pt o1 6o c 一3s i m u l t a n e o u sc o m m u n i c a t i o nr e q u e s t s i na l l 。 o p t i c a ln e t w o r k s ，w d mt e c h n o l o g yc a nt r a n s m i tk i n d so fs i g n a l so ns i n g l ef i b e r ，a n de a c h s i g n a lu s ed i s t i n c tw a v e l e n g t h t h u s ，w a v e l e n g t ha s s i g n m e n tp r o b l e mi st of i n dap a t hf 6 ra p a i ro fr e q u e s t sf o rc o m m u n i c a t i o n ，a n da s s i g naw a v e l e n t ht oi ts u c ht h a tt w op a t h s s h a r i n g t h es a m el i n kh a v ed i s t i n c tw a v e l e n t h i nt e r m so fg r a p h t h e o r e t i c ，w a v e l e n g t ha s s i g n m e n t p r o b l e mc a l lb ev i e w e da sa s s i g n i n gc o l o r st og i v e np a t h ss ot h a tt h e s ep a t h ss h a r i n ga n e d g eh a v ed i f f e r e n tc o l o r s g e n e r a l l y , c o m m u n i c a t i o nr e q u e s t sh a v eag r a n u l a r i t yg ，k n o w n a sg r o o m i n gf a c t o r av a l i dc o l o r i n gp a t h ss h o u l db ec o l o r e ds ot h a ta tm o s tg p a t h ss h a r i n g ac o m m o ne d g em a yb ec o l o r e dw i t ht h es a m ec o l o r g i v e nav a l i dc o l o r i n g a na d m ( a d d d r o pm u l t i p l e x e r ) c a ns e r v ea tm o s t2 9p a t h sc o l o r e dw i t ht h es a l n ec o l o r o b v i o u s l y , t h e a d mm i n i m i z a t i o np r o b l e m sa r es p e c i a lc a s eo ft h et r a f f i cg r o o m i n gp r o b l e m s ( g = 1 ) i n1 9 9 8 ，o g e r s t e l ，r r a m a s w a m ia n dg s a s a k ie t c i n t r o d u c e dt h en o t i o no ft r a f f i c g r o o m i n gf o rt h er i n gt o p o l o g yn e t w o r k s t h ep r o b l e mw a ss h o w nt ob en p c o m p l e t ef o r r i n gn e t w o r k sa n dag e n e r a lg i np a s t ，t h es t u d yo ft r a f f i cg r o o m i n gp r o b l e mw a sf o c u so n r i n gt o p o l o g yb yd o i n gs o m er e l a t e dw o r ko nt h i sp r o b l e ma n dg o ts o m ev a l u a b l er e s u l t s i n2 0 0 6 m s h a l o ma n ds z a k se t c d i s c u s s e da l la l g o r i t h mt h a th a sap r e p r o c e s s i n g p h a s ed u r i n gw h i c hc y c l e so fl e n g t ha tm o s tl ，a n dp r o v ei th a sap e r f o r m a n c eg u a r a n t e e i nt h et h e s i s ，w em a i n l ys t u d yt h ea d mm i n i m i z a t i o np r o b l e m s ，a n dt h et r a f f i cg r o o m - i n gp r o b l e mf o rd i f f e r e n tt o p o l o g yn e t w o r k s t h et h e s i si sd i v i d e di n t of i v ec h a p t e r s m o s t o fp r o b l e m sw ed i s c u s si nt h i st h e s i sa r en p h a r d ，t h e r e f o r ew ea r em a i n l yi n t e r e s t e di n a p p r o x i m a t i o na l g o r i t h m s i nc h a p t e rl ，w eb r i e f l yi n t r o d u c et h eb a s i cn o t i o no f a l l - o p t i c a ln e t w o r k s ，s o n e t w d m r i n g sa n dt h et r a f f i cg r o o m i n gp r o b l e m s a n dw ea l s ol i s tt h ew o r kw ed oa n dt h es t r u c t u r e o ft h et h e s i s i nc h a p t e r2 ，w em a i n l yd i s c u s st h ea d mm i n i m i z a t i o np r o b l e m ，a n dw e g e tab e t t e rp e r f o r m a n c eg u a r a n t e eb yf u r t h e ri m p r o v i n gt h ea p p r o x i m a t i o na l g o r i t h mw i t h p r e p r o c e s s i n gp h a s e i nc h a p t e r3 ，w ep r o p o s ea na l g o r i t h mw i t hb e t t e ra p p r o x i m a t i o n r a t i o f o rm u l t i c a s tt r a f f i cg r o o m i n gi nu n i d i r e c t i o n a ls o n e t w d mr i n g s ，a n dp r o v et h er e l a t i o n b e t w e e nt h el o w e rb o u n do ft h en u m b e ro fa d m sa n dt h en u m b e ro fn o d e si nt h er i n g s i n c h a p t e r4 ，w em a i n l ys o l v et h et r a f f i cg r o o m i n gp r o b l e mi n u n i d i r e c t i o n a ls o n e t w d m r i n g sa n dt h eg e n e r a lt o p o l o g yn e t w o r k sb ya p p l y i n gt h ea l g o r i t h mw h i c hi n t r o d u c e di nr i n g t o p o l o g yn e t w o r k s ，a n dw eg e ts o m es i m i l a rr e s u l t s i nc h a p t e r5 ，w em a k eac o n c l u s i o nf o r t h ew h o l et h e s i sa n dp r o p o s es o m ep r o b l e m st ob ec o n s i d e r e di nt h ef u t u r e k e yw o r d s ：a l l - o p t i c a ln e t w o r k s ，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 ，a d m ，t r a f f i c g r o o m i n g ，s o n e t w d mr i n g s 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ) 本人郑重声明：此处所提交的博士口硕士回论文全光网络 中的流量疏导问题研究，是本人在导师指导下，在曲阜师范大学攻 | 读博士口硕士囵学位期间独立进行研究工作所取得的成果。论文中 除注明部分外不包含他人已经发表或撰写的研究成果。对本文的研究 工作做出重要贡献的个人和集体，均已在文中以明确的方式注明。本 声明的法律结果将完全由本人承担。 作者签名： 茬磊虔日期：m 哆厶参 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“ ) 全光网络中的流量疏导问题研究系本人在曲阜师范大学攻读博士 | i 口硕士囤学位期间，在导师指导下完成的博士口硕士留学位论 文。本论文的研究成果归曲阜师范大学所有，本论文的研究内容不得 以其他单位的名义发表。本人完全了解曲阜师范大学关于保存、使用 学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电 子版本，允许论文被查阅和借阅。本人授权曲阜师范大学，可以采用 影印或其他复制手段保存论文，可以公开发表论文的全部或部分内 容。 作者签名：锃煮良 作者签名：位永葭 新躲跏秘 日期：砷友弓 日期：土研。 全光网络中的流量疏导问题研究 第一章绪论 这一章将对本文相关的背景知识进行了简要的介绍其中，第一节对全光网络的基 本概念进行了简要概述，第二节简要介绍了s o n e t w d m 环的结构及其工作原理，第 三节介绍了全光网络中的流量疏导问题，第四节列出本文研究的主要内容和组织结构 1 1 全光网络概述 随着现代网络的飞速发展，通信网络中不断增长的容量和服务质量的需求成为光网 络技术研究的驱动力网络用户对电子通信的需求也出现了爆炸式的增长，上个世纪七 十年代，高速专用线路的速率是9 6 k b p s ，然而，今天却提供了高达g b p s 的专用线路 实现g b p s 网络，最有前景的技术就是所谓的全光网络，其主要的传输介质是光纤第一 代网络直到上世纪八十年代，网络中数据传输的主要介质是铜，此时并没有出现可供使 用的光纤技术随后出现了第二代网络，其主要特性是把原有的铜线线路升级为光纤线 路，该网络利用了光纤线路的高带宽和低误码率的优点进行数据的高速的可靠传输，但 是其缺点是网络节点中所有的数据交换都是以电信号的速度处理为了克服通过电信号 处理的速度来实现网络中各个节点的信息交换所带来的电子瓶颈，人们提出了所谓的全 光网络( a o n ) 的概念，即网络中从源节点到目的节点间的数据传输和信息交换的整个 过程都是在光域内进行的，也就是所谓的完全的端到端的光路，中间没有任何电信号的 介入光交换的主要优点是避免了信息间的多重的光电光的转换，也避免了经过链路中 间节点时所需的电交换操作，数据传输透明性高，节省了所需电子处理设备的成本，从 而也减少了网络成本因此，全光网络已经成为下一代高速度、高带宽、高可靠性传输 网络的首选目标 - - o - - - oo - - - - o o 图1 1 光网络结构图 全光网络中的流量疏导问题研究 全光网络中所采用的关键技术有t 时分复用技术( t d m ) 、频分复用技术( f d m ) 和波分复用技术( w d m ) 本文主要以基于波分复用技术( w d m ) 的全光网络为研究 重点与以往传统的通信网络相比较，以波分复用技术为基础的全光网络，具有提供通 信容量更大，传输可靠性更高，传输速度更快，网络成本更低等优点 随着波分复用技术的日渐完善，目前最重要的是减少网络中所使用的电子处理设备 的成本在全光网络中，使用的最基本的电子处理设备是分插复用器( a d m ) ，其具有 分出或插入网络中所需要的波长的功能分插复用器的工作原理【1 j ( 如图1 2 ) 就是把网 络中暂时不需要的波长从光纤中分离出来，把网络中需要的波长插入某个信道以供信息 传输当某个波长被a d m 分离出光纤时，并不表示该波长从此不可用而是可以把该波 长插入到另一条可用信道，从而充分提高带宽的利用率 1 2 s o n e t w d m 环 图1 2 o a d m 随着现代通信网络的迅速发展和光纤通信技术的不断成熟，二十世纪中期，美国提 出了基于光纤通信技术的网络，同步光纤网( s o n e t ) ，该网络是一种用于高速数据通信 的光纤传输网络与一般网络相比，s o n e t 传播的距离更远，最重要的特点是s o n e t 支持环形拓扑结构下面简要介绍一下s o n e t 环的基本概念和工作原理 一个s o n e t 环是由两个以上s o n e t 节点组成的一个封闭环，其中，一部分光纤 为工作环( w o r k i n gr i n g ) ，一部分为保护环( p r o t e c t i o nr i n g ) 工作环用来传输网络中 所需要的数据，保护环是一种备用环s o n e t 环具有自我检测功能，当工作环在数据 传输过程中出现故障时，s o n e t 环就会进行自我检测并在非常短的时间内向保护环提 供控制信息，以使保护环处于工作状态因此，s o n e t w d m 环被称为自愈环，具有自 我修复功能下面主要从s o n e t 环工作环的方向上简要介绍其所具有的特征 2 全光网络中的流量疏导问题研究 在单向s o n e t 环的情况下，工作环的方向是顺时针方向，即仅沿着顺时针方向进 行数据传输工作原理【1 】如图1 3 ， 一l i n k l l m k4 nl i r r ln2 n4 j l i n k5 l m k8 l i n k7 l i n k3 l i n k6ll l i n k2 n3 图1 3 单双向s o n e 环 由上图可知，若要实现n 1 节点与n 2 节点之间的数据通信，则在单向s o n e t 环中 会采用线路1 作为其工作环来进行数据传输若要使得n 2 节点完成对n 1 节点的反馈 信息的传输，则需要使用线路2 、线路3 和线路4 作为其工作环两个工作环的传输方 向都是按照顺时针方向，也即所谓的单向传输在单向s o n e t 环情况下，线路5 、线 路6 、线路7 和线路8 对数据传输都不进行工作，而是作为备用环，用来实现环路的保 护，当工作环中的线路发生故障时，备用环会自动进入工作状态 在双向s o n e t w d m 环情况下，相邻两个节点间相互进行通信的工作方向应是两 个相反的方向，即顺时针方向和逆时针方向，其工作原理i a 】如下( 图1 3 ) ： n 1 节点与n 2 节点通信使用线路1 进行数据传输，但是当n 2 节点要对n 1 节点进 行信息回馈时，使用线路5 进行通信在双向s o n e t w d m 环中，工作环中的一条路 径是顺时针方向，而另一条路径是逆时针方向，即一个完整的双向连接通信中，网络节 点之间的通信使用了双向路径传输若n 1 节点和n 2 节点之间的通信线路发生故障， 则n 2 节点和n 3 节点，n 3 节点和n 4 节点及n 4 节点与n 1 节点之间的线路便成为工作 环，充分体现了s o n e t w d m 环的自愈功能实质上，双向s o n e t 环和单向s o n e t 环的结构及其工作原理极为相似，其主要的区别在工作环的工作方向上 1 3 流量疏导问题简介 在w d m 网络中，每条光纤链接可以承载多个波长上的高速业务流，因此单个光纤 中可以建立多个通信信道虽然单个光纤有超过1 t b p s 的带宽，一个波长信道有超过 1 g b p s 的传输速率，但是网络仍要求能支持比完全波长容量低得多的业务流链接为了 节省网络费用，提高网络性能，对网络运营商来说，能疏导多个低速业务流链接到高容 量波长信道是十分重要的，因此，运用流量疏导技术 实际上，流量疏导问题就是通过有效的复用、交换处理等技术，将低速的业务流汇 聚到高容量的光路中传输，以提高网络资源的利用率用图论的术语来讲，流量疏导问 题可看作是路径染色问题，以使得其中至多有9 条路径共享一条边( g 是疏导因子) 3 全光网络中的流量疏导问题研究 从a d m s 角度来讲，每条光路使用两个a d m ，每个端点上需要一个a d m 具有相同 波长的g 条光路在通过相同的边到达一个节点的情况下，它们可以使用相同的a d m ，这 样就节省了g 一1 个a d m ，其目的是使a d m 数最小化 流量疏导分为静态流量疏导、动态流量疏导、单播流量疏导和多播流量疏导等静 态流量疏导是指在每对结点之间的业务流需求是固定的( 即在一个时间段内不改变) 静 态流量疏导问题是n p 一完全的静态流量疏导问题本质上是一个最优化问题，它可以看 成是对偶问题：原问题是对于给定的业务流需求，满足所有业务请求同时最小化总的网 络费用；其对偶问题是对于给定资源和业务流需求，最大化网络吞吐量，即由网络成功 运载的总业务流量动态流量疏导是指在每对结点之间的业务流量需求可以随时间而改 变单播流量疏导是指对于给定的单播流量需求( 光路从一个源节点到一个目的节点间 构成一条光的通道，中间可经过多个光交叉连接设备( o x c ) ，属于单播) 进行有效地 疏导多播流量疏导是指对于给定的多播流量需求( 从一个源节点发出的光路要同时到 达多个目的节点，属于多播) 进行有效地疏导 流量疏导是当今光网络研究中的一个热点问题目前，与光通讯的高带宽、高速度 相比，电子网络元件的处理速度成为网络通讯中的瓶颈网络的性能主要受限于大多数 电子设备的处理能力，而通过将低速业务流有效地疏导到高容量的光信道上，最小化这 种电子设备可提高网络的性能流量疏导问题可以大大提高网络的吞吐量，在波分复用 ( w d m ) 光网络中使用流量疏导技术能有效降低网络的成本，减少网络节点中业务流的 处理量，从而大大提高网络资源的利用率 近几年，对流量疏导问题的研究主要针对不同的网络拓扑结构( 如r i n g 或m e s h 网 络) ，不同的业务流模型( 如静态或动态业务流) ，不同的目标( 如最小化a d m 数或波长 数或二者的一个线性组合) 等问题在w d m 网络中有两种基本的结构：环形和网状 目前已经建立起来的运行中的大多数光网络都是基于环形结构，由于环形网络特殊的优 点，先前对流量疏导问题的研究也大都是基于环形网络的本文在研究最小化a d m 数 问题的同时，对环形网络及一般拓扑结构中的流量疏导问题也进行了相关的研究，并得 出了相似的结果 1 4 论文主要研究内容和组织结构 在查阅了大量关于全光网络的相关理论和流量疏导问题的相关文献后，对全光网络 中的流量疏导问题进行了深刻地研究，本文主要研究了以下内容： 1 最小化a d m 数问题，将其抽象为图论中的路染色问题，并通过创建最大匹配问 题对已知算法进行改善分析，使其具有更好的性能保证 2 对单向s o n e t w d m 环中的多播流量疏导问题提出了具有更好近似比的算法 3 利用已知的g r o o m b y s c ( k ) 算法，通过改善分析将其应用于解决单向s o n e t w d m 环中的多播流量疏导问题及一般拓扑结构中的流量疏导问题 4 全光网络中的流量疏导问题研究 本文的组织结构如下s 第一章对全光网络的背景知识及其基本概念进行了简要概述，简要介绍了s o n e t 环的结构及其工作原理，简述了流量疏导问题，最后并给出了本文研究的主要内容和组 织结构 第二章主要研究了最小化a d m 数问题，对具有预处理阶段的近似算法，通过进一 步改善分析使其具有更好的性能保证 第三章对单向s o n e t w d m 环中的多播流量疏导问题提出了具有更好近似比的贪 心近似算法，并证明了所使用的a d m 数与网络中节点数的关系 第四章将应用于环形网络中的近似算法进一步改善分析应用于解决单向s o n e t w d m 环中的多播流量疏导问题及一般拓扑结构中的流量疏导问题，得到了相似的结果 第五章对全文进行简要总结，并提出了下一步有待解决的问题 5 全光网络中的流量疏导问题研究 第二章最小化a d m 数一具有更好上界的近似算法 最小化a d m 数问题是近来研究的重点m s h a l o m 针对这个问题提出了一个基本的 近似算法p m m ( ) 引，消除圈长至多为l 的圈，给出了一个性能保证o p t + ；( 1 + e ) ， 丽1 e 孤1 ：酉，其中，o p t 是最优解，是网络中的光路数本文对该近似算法做 了进一步改善分析，进一步缩小了e 的上界和下界之间的间隙，给出了的一个更好的 上界，即丽1 e 而1 2 1 背景知识 给定一个w d m 网络g = ( v e ) ，由光节点和g 的光路集合p = p 1 ，p 2 ，p n 组 成，波长分配就是给每条光路阢分配一个波长假设每条光路p p 包含在g 的一个 圈中，每条光路使用两个a d m ，每个端点处使用一个如果两条相邻的光路分配相同 的波长，则在公共节点处可以共享一个a d m ，这样可以节省a d m 的成本一个a d m 至多可以被两条光路共享在公共节点处共享a d m 的光路可以被认为是串联的，因此 它们形成了更长的路径或圈每条这样的路径或每个这样的圈都不可能两次使用一条边 e e ，否则，它们不可能分配相同的波长，这是共享a d m 的必要条件 2 2 先前的工作 m s h a l o m 和0 g e r s t e l 等人提出了环形网络中的最小化a d m 数问题【引，并在3 ， 4 ，5 】中分别给出了近似比为；，l o ，+ e ，雩的近似算法 6 】中给出了对于一般拓扑结 构中的最小化a d m 数问题提出了一个近似比为；的近似算法t e i l a m 等人也对该问 题进行了相关研究并提出了一个具有预处理阶段的近似算法m ，并证明了此算法的性能 保证为o p t + 1 ( 1 + e ) n ，0 e 丽1 ，其中， o p t 是最优解，n 是网络中的光路 数，f 为圈长 在z = l 的情况下，该算法没有预处理阶段，其性能保证为o p t 十；2 0 0 6 年， m f l a m m i n i 等人进一步证明算法的性能保证为o p t + j 7 r 【引m s h a l o m 通过采用新的 最优化技术，对此算法做了进一步的改善分析，并证明了赤e 靳【9 1 2 3 我们的工作 2 3 1 问题定义 6 全光网络中的流量疏导问题研究 给定问题的一个实例a = ( g ，尸) ，其中，g = ( ke ) 是一个无向图，p 是g 中的 简单路径集合据此，我们给出以下已有定义1 9 】； 定义2 3 1 ：如果路径p ，p ( p ，p ) 有一条公共边，则称它们是冲突( 或重叠) 的用 p 表示，具有这种冲突关系的图称为冲突图( c o n f l i c tg r a p h ) 定义2 3 2sp 的一个合适的染色( 波长分配) 是一个函数u ：phn ，使得当pxp 时，u ( p ) u ( p 。) 定义2 3 3 。实例0 t 的一条有效链( 圈) 是由不同的路径串联而形成的一条路径，且路 径1 9 0 ，p ”，p k 一1 尸彼此间无公共边 定义2 3 4t 实例q = ( g ，p ) 的一个解s 是p 的一个链或圈的集合，且使得路径p p 仅出现在这些集合中的一个集合中 定义2 3 5 ：一个实例口= ( g ，p ) 的一个共享图( s h a r e a b i l i t yg r a p h ) 是一个用边标记 的多重图，使得当且仅当p q 时，在玩上有一条用“标记的边e = ，q ) ，且u 是g 中p 和q 的公共端点 例如：令q = ( g ，p ) 是一个实例，如图2 1 ，其共享图( s h a r e a b i l i t yg r a p h ) g a 如图 2 2 的左图在这个实例中p = a ，b ，c ，d ，e ， ，它组成了乳的节点集合边及其边上的 标记为b = ( 6 ，c ，乱) ，( d ，e ，z ) ，( a ，c ，叫) ，( a ，b ，z ) ，( e ，d ，z ) ，( b ，d ，z ) ，( d ， ) ，( b ，e ，z ) ) 因为b 和c 在公共端点u 上可以串联等该实例对应的7 申突图，如图2 2 中间图，有相同的节点 集，其边集为 ( o ，d ) ，( c ，d ) 路径c ，d p 是冲突的，因为它们有一条公共边，如( w ，v ) 等 图2 1 一个实例图 o q 一芍一o 、( b ) o 、o 图2 2 s h a r e a b i l i t y 图，冲突图和s h a r i n g 图 注意，冲突图的边不在既中，对9 口的任一节点口，连接到节点u 上的边的标记集 合规模最大为2 7 全光网络中的流量疏导问题研究 定义2 3 6t 实例q 的一个解s 的分享图( s h a r i n gg r a p h ) 是吼的一个子图，鼠s = ( p 艮) 当且仅当两条光路p ，q p 在解s 的圈或链中是连续的，则用的一条标记为 的边连接这两条光路，“v 是它们的公共端点我们可将分享图( s h a r i n gg r a p h ) 筒写为9 s 定义2 3 7 ：g s 中一个节点p 的度是指连接到该节点上的边的标记集合的规模，用d ( p ) 表示，d ( p ) = o ，1 ，2 由上例，s = ( 凸，b ，c ) ，( e ，d ，) ) 是有两条链组成的一个解，其分享图( s h a r i n gg r a p h ) 如图2 2 右图定义v i 0 ，1 ，2 ，既( s ) 型 p p i d ( p ) = i ) 1 9 】，且d i ( s ) 型l 现( s ) i 注 意d o ( s ) + d 1 ( s ) 4 - d 2 ( s ) = i p l = n 标记为u 的一条边( p ，q ) e s 对应于用相同颜色 着色的两条光路在其公共端点乱上的串联，因此，这两条光路在节点u 上可以共享一个 a d m ，于是，节省了一个a d m 我们可推断b 的每条边对应于节省一个a d m 因 此，一个解s 的代价为2 i f l i e s l = 2 n l b l ，目标是找到一个解s 使得c o s t ( s ) 的 值最小，即1 l 最大 2 3 2 已知结果 给定一个解s ，对每个节点p p ，d ( p ) 2 ，魄的连通分支或为路径或为圈 一个孤立的节点可看作一条特殊的路径令p s 是鲰的连通分支的路径集合令s 是 具有最小值的解对任一解s ，已有定义【9 】 fr 刚掣d o ( s ) - d = ( s ) - 2 1 v s - i 。r7 。 引理1 ：对任一解s ，c o st ( s ) = c o st ( s ) + ( 1 + e ( s ) ) 1 9 j p m m ( 1 ) 算法有一个预处理阶段，移除了圈长至多为z 的圈，其中，z 是奇数且其 性能保证为o p t + j ( 1 + e ) ，o 西1 2 0 0 6 年，s h a l o m 等人对该算法进行了改善 分析并证明了o p t + ；n ( 1 + ) ，瓣1瓢面1 2 3 3p m m ( 1 ) 算法 我们回顾一下p m m ( 1 ) 算法，该算法有一个预处理阶段，首先移除了长度至多为z 的圈( f 是奇数) ，然后进行算法的处理阶段( 函数m m ) ，具体操作描述如下：从由单个 节点组成的链开始，在每次迭代中，通过创建合适的图和计算最大匹配使最大数目的链 对组合以获得更长的链当最大匹配为空时，即没有两条链可以组合成一条更长的链， 算法结束p m m ( 1 ) 算法描述如下s f u n c t i o nm m ( a ) _ 【 e s = o t h ec h a i n so fg sa r ei s o l a t e dn o d e s 8 全光网络中的流量疏导问题研究 d o b u i l dt h eg r a p h 瓯i nw h i c he a c hn o d ei sac h a i no fg sa n dt h e r ei sa ne d g el a b e l l e du b e t w e e nt w oc h a i n si fa n do n l yi ft h ec h a i n sc a nb em e r g e di n t oo n eb i g g e rc h a i nb yj o i n i n g t h e ma tac o m m o ne n d p o i n t 仳 | | i nt h e f i r s ti t e r a t i o n9 1 = 9 1 f i n dam a x i m u mm a t c h i n gm m o f 瓯 f o re a c he d g ee = ( c ，c ，) o fm m l a b e l l e d “d o m e r g et h ec o r r e s p o n d i n gc h a i n si n t oo n ec h a i nb yj o i n i n gt h e mi nt h ec o m m o ne n d p o i n t t 五 ) u n t i lm