（计算数学专业论文）最优化网络路由及常重复合码.pdf

摘要 本文分两部分，在第一部分中我们研究的对象是最优化网络路由，在第二部分 中我们研究的是常重复合码。 在网络研究中，最优化网络路由现在已经成为一个值得考虑而且已被很多人关 注的问题了在最优化网络中，一个最优的纤维能够被利用到的最大的带宽被分成 很多通道，每个路由通道使用一个特定的波长任意两个通道能使用同一个波长当 且仅当他们没有相同的连接。关于我们所研究的最优网络我们用到多重分配波长 技术，即被称为w d mo p t i c a ln e t w o r k s 这个概念第一次由a l o ka g g a r w a l ，a m o t z b a r n o y t ，d o nc o p p e r s m i t h ，r a j i vr a m a s w a m i ，r a x u c hs c h i e b e r ，m a d h us u d a n 提出。我们主要的工作就是要使得网络中需要用到的波长教最少因为这个问题的 难度很大，所以到目前为止只得到了很少的结果 本文主要用组合设计中的方法来研究n 9 时的在最优化网络中的路由。我们 所做的工作以及得到的成果主要是以下三点： 1 我们利用一个回溯算法得到了当n = 9 和n = 1 0 的最优解。 2 我们给出参考文献【4 5 】中构造s t e i n e r _ 三元系大集的方法。这个方法在构 造s t e i n e r _ 三元系大集中起了非常大的作用。相信这个方法在这个问题上 也能发挥作用，我们希望利用这个方法能完美的解决这个问题。 3 我们对这个问题做了初步的研究，确定了一些必要条件并找到了几个有用 的h l e s t s 。 上面三点就是本论文的主要结果当然，有些结果还是可以进行改进 的。比如，我们采用现在的模型和算法无法找到当h 为偶数时在循环群下 i 的e g d d ( 2 ，3 ，h 3 ) ，但这并不意味着这个设计不存在。我们可以采用更加微妙 的模式和更加高效率的算法进行试验。这需要我们进一步的研究和探讨 在第二部分中，我们介绍了常重复合码。常重复合码是一种特殊的常重码， 是指在每个码字中每个符号出现的次数是给定的。常重码在编码理论中有很重 要的作用，二元常重码已被很多人研究过了。常重复合码包括重要的置换码， 而且由于它的广泛应用性，常重复合码已被更多的人所重视。我们主要是要研 究( 死，5 ，【3 ，1 】) 3 一码。 在本文中，我们主要是用组合设计中的方法去研究常重复合码我们所做的工 作以及得到的成果主要是以下三点： 1 我们对所要研究的这类码字进行分析得到一些必要条件并且利用一些算法直 接构造了一些最优( n ，5 ，【3 ，1 】) 3 一码。 2 我们利用g d d 和g d c 进行构造( 佗，5 ， 3 ，1 】) 3 一码，并且找了一系列的g d c 。 3 我们构造了一类最优的( 2 4 t + 1 ，5 ， 3 ，1 】) 3 一码，并且亡1 。我们还证明了个数 为4 的( 6 ，5 ， 3 ，1 】) 3 一码的最优解是不存在的。 上面的三点就是本文第二部分所要介绍的主要内容，我想这里还有很多地方可 以改进的。比如，由于我们的算法不够优秀，我们还不能证明一些码的存在性。而 且对t ( 9 ，5 ，【3 ，1 】) 3 一码，我们通过计算机算法遍历完也没有解，但我们还不能从理 论上证明是不存在的，我们可以采用更加微妙的模式和更加高效率的算法进行试 验。这需要我们进一步的研究和探讨。 关键词：最优网络，路由，大集，烛台设计，常值码，w i l s o n 基本构造，可 分组设计，成对平衡设计，常型码，可分组码，递归构造 a b s t r a c t t h e r ea let w op a r t si nt h i st h e s i s ，w ei n v e s t i g a t et h er o u t i n g si no p t i c a ln e t w o r k s i nt h ef i r s tp a r ta n dt h ec o n s t a n t c o m p o s i t i o nc o d ei nt h es e c o n dp a r t i nt h ef i r s tp a r to ft h i st h e s i sw ec o n s t r u c ts e t so fr o u t i n g si nt h ec o m p l e t ed i r e c t e d g r a p hk nt h a tt o l e r a t eu pt off a i l u r e so fn o d e s o rl i n k s f a u l t t o l e r a n tr o u t i n g sw i t h m i n i m u mo p t i c a li n d e xh a sb e e nat o p i co fc o n s i d e r a b l er e c e n ti n t e r e s t i no p t i c a l n e t w o r k s ，t h ev a s tb a n d w i d t ha v a i l a b l ei na no p t i c a lf i b e ri su t i l i z e db yp a r t i t i o n i n g i ti n t os e v e r a lc h a n n e l s ，e a c hr o u t i n gp a t hn s e sap a r t i c u l a rw a v e l e n g t h ，a n dt w o p a t h sc a nu s e t h es a m ew a v e l e n g t hi fa n do n l yi ft h e yh a v en ol i n k si nc o m m o n t h e o p t i c a ln e t w o r k sr e l e v a n tt oo u rw o r ku 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 ：t h e s e a r ec a l l e dw d mo p t i c a ln e t w o r k s t h en o t i o no fr o u t i n g si no p t i c a ln e t w o r k sw a s f i r s ti n t r o d u c e db ya l o ka g g a l w a l ，a m o t zb a r n a y ) ，d o nc o p p e r s m i t h ，r a j i v r a m a s w a m i ，r a r u c hs c h i e b e r ，m a d h us u d a n i ng e n e r a l ，w ew a n tt om i n i m i z et h e t o t a ln u m b e ro fw a v e l e n g t h su s e di nt h en e t w o r k i ti sah a r dp r o b l e ma n do n l ya f e wr e s u l t sh a v eb e e nf o u n db yn o w i nt h i st h e s i s ，w em a i n l yu s et h em e t h o d si nc o m b i n a t o r i a ld e s i g n st os t u d yr o u t - i n g si no p t i c a ln e t w o r k sw h e n 佗9 t h em a i nr e s u l t s ，w h i c hw eh a v eg o t ，a r et h e f o l l o w i n gt h r e ep o i n t s 1 w eu s eas t a n d a r db a c k t r a c k i n ga l g o r i t h mt of i n dt h es o l u t i o n sn = 9 ，1 0 2 w eg i v eam e t h o dt h a tc o n s t r u c tl a r g es e t so fd i s j o i n ts t e i n e rt r i p l es y s t e m s f r o m 【4 6 】t h i sm e t h o dp l a y sa ni m p o r t a n tr o l ei nc o n s t r u c t i n gl a r g es e t so f i i l d i s j o i n ts t e i n e rt r i p l es y s t e m s w eb e h e v ei tw i l lw o r ko no u rp r o b l e m a n dw e t r yt ou s et h i sm e t h o dt os o l v eo u rp r o b l e mc o m p l e t e l y 3 w ec a r r i e do u ta p i l o ts t u d y , a n dh a v ef o u n ds o m eu s e f u lr e s u l t sa b o u th l s t s s a n dw eg e tt h en e c e s s a r yc o n d i t i o nt oc o n s t r u c tt h ee g d d s t h ea b o v et h r e ep o i n t sa r et h em a i nr e s u l t si nt h ef i r s tp a r to ft h i st h e s i s it h i n k s o m er e s u l t sm a yb ei m p r o v e d f o re x a m p l e ，d u et ot h ea l g o r i t h ma n ds t r u c t u r ew e s e l e c t e d ，w ec a n tp r o v et h ee x i s t e n c eo fe g d d ( 2 ，3 ，h 3 ) w h e nhi se v e n b u tt h i s d o e sn o tm e a ni td o e s te x i s t w ec a ni m p r o v eo u r a l g o r i t h ma n dm a k ei tm u c hm o r e e f f i c i e n to rw ec a nt a k eo t h e rd e l i c a t es t r u c t u r et op r o v et h ee x i s t e n c eo fs o m es p e c i a l e p c s i nt h es e c o n dp a r to ft h i st h e s i sw ei n v e s t i g a t et h ec o n s t a n t c o m p o s i t i o nc o d e s a c o n s t a n t - c o m p o s i t i o nc o d ei sas p e c i a lc o n s t a n t w e i g h tc o d eu n d e rt h er e s t r i c t i o n t h a t e a c hs y m b o ls h o u l da p p e a ra g i v e nn u m b e ro ft i m e si ne a c hc o d e w o r d c o n s t a n t w e i g h tc o d e sp l a y sa ni m p o r t a n tr o l ei nc o d i n gt h e o r y b i n a r yc o n s t a n t w e i g h tc o d e s h a v eb e e ne x t e n s i v e l ys t u d i e db ym a n ya u t h o r s t h ec l a s so fc o n s t a n t - c o m p o s i t i o n c o d e si n c l u d e st h ei m p o r t a n tp e r m u t a t i o nc o d e sa n dh a sa t t r a c t e dr e c e n ti n t e r e s t d u et ot h e i rn u m e r o u sa p p l i c a t i o n s i ng e n e r a l ，w ew a n tt od os o m er e s e a r c ho n ( 佗，5 ，【3 ，1 】) 3 一c o d e s i nt h i st h e s i s ，w em a i n l yu s et h em e t h o d si nc o m b i n a t o r i a ld e s i g n st o s t u d v c o n s t a n t c o m p o s i t i o nc o d e s t h em a i nr e s u l t s ，w h i c hw eh a v eg o t ，a r et h ef o l l o w - i n gt h r e ep o i n t s 1 w eu s es o m ea l g o r i t h mt oc o n s t r u c ts o m eo p t i m a lc o n s t a n t - c o m p o s i t i o nc o d e s d i r e c t l y i v 2 w eu s eam e t h o dt h a tc o n s t r u c tf r o mg d d sa n dg d c s ，a n dw eh a v ec o n - s t r u c t e ds o m eu s e f u lr e s u l t sa b o u tg d c s 3 w ec o n s t r u c to p t i m a l ( 2 4 t + 1 ，5 ，【3 ，1 】) 3 一c o d e s ，t 1 a n dw eh a v ep r o v e dt h a t t h e ( 6 ，5 ，【3 ，l 】) 3 一c o d e so fs i z e4d o e sn o te x i s t t h ea b o v et h r e ep o i n t sa r et h em a i nr e s u l t si nt h es e c o n dp a r to ft h i st h e s i s i t h i n ks o m er e s u l t sm a yb ei m p r o v e d f o re x a m p l e ，d u et ot h ea l g o r i t h ma n ds t r u c - t u r ew es e l e c t e d ，w ec a n tp r o v et h ee x i s t e n c eo fs o m eo p t i m a l ( n ，5 ，( 3 ，1 】) 3 一c o d e s a n dt h en o n e x i s t e n c eo f ( 9 ，5 ，【3 ，1 】) 3 一c o d e so fs i z e1 2 w ec a ni m p r o v eo u ra l g o r i t h m a n dm a k ei tm u c hm o r ee f i i c i e n to rw ec a nt a k eo t h e rd e l i c a t es t r u c t u r et op r o v et h e e x i s t e n c eo fs o m es p e c i a lg d c sa n dc o n s t a n t c o m p o s i t i o nc o d e s k e y w o r d s ：o p t i c a ln e t w o r k ，r o u t i n g ，l a r g es e t ，c a n d e l a b r as y s t e m ，c o n s t a n t c o m p o s i t i o nc o d e s ，w i l s o n sf u n d a m e n t a lc o n s t r u c t i o n ，g r o u pd i v i s i b l ed e s i g n ，p a i r - w i s eb a l a n c e dd e s i g n ，c o n s t a n t c o m p o s i t i o nc o d e s ，g r o u pd i v i s i b l ec o d e s ，r e c u r s i v e c o n s t r u c t i o n s v c h a p t e r1 i n tr od u c ti o no fr o u t i n g s 1 1t h eh i s t o r yo fr o u t i n g si no p t i c a ln e t w o r k s t h ed e s i g no fr o u t i n g si no p t i c a ln e t w o r k sh a sb e e nat o p i co fc o n s i d e r a b l er e c e n t i n t e r e s t f o rb a c k g r o u n dm a t e r i a lo no p t i c a ln e t w o r k s ，w er e f e rt o a g g a r w a le ta 1 【3 】t h eo p t i c a ln e t w o r k sr e l e v a n tt oo u rw o r ku 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 ； t h e s ea r ec a l l e dw d m o p t i c a ln e t w o r k s i nt h i sm o d e l ，r o u t i n gn o d e sa r ej o i n e db y f i b e r - o p t i cl i n k s ，a n de a c hl i n kc a l ls u p p o r ts o m e 叙e dn u m b e ro fw a v e l e n g t h s ( s e e ， e g ，b e a u q u i e re ta 1 【7 】a n db e a u q u i e r 【6 】) e a c hr o u t i n gp a t hu s e sap a r t i c u l a r w a v e l e n g t h ，a n dt w op a t h sc a nu s et h es a m ew a v e l e n g t hi fa n do n l yi ft h e yh a v en o l i n k si nc o m m o n i ng e n e r a l w ew a n tt om i n i m i z et h et o t a ln u m b e ro fw a v e l e n g t h s u s e di nt h en e t w o r k w ea r ep a r t i c u l a r l yi n t e r e s t e di n c o n s t r u c t i n gf a u l t t o l e r a n t r o u t i n g s ，t h es t u d yo fw h i c hw a si n i t i a t e db ym au c ha n ds t a c h o 【5 3 1 w ew i l lw a n t t op r o v i d ear o u t i n gb e t w e e na n yt w on o d e si nt h en e t w o r k e v e ni fs o m en u m b e ro f n o d e sa n d o rl i n k sf a i l ( u pt oa s p e c i f i e dt h r e s h o l d ，s a yf t h u s ，g i v e na s o u r c en o d e xa n dad e s t i n a t i o nn o d ey w ew i l lr e q u i r ef + lr o u t i n g sf r o mxt oyt h a th a v en o i n t e r n a ln o d e so rl i n k si nc o m m o n g i v e nt h a ta tm o s tfc o m p o n e n t sf a i l ，i tf o l l o w s t h a ta tl e a s to n eo ft h e s ef + lr o u t i n g sw i l lc o n t a i nn of a i l e dc o m p o n e n t s b e a u q u i e re ta 1 【7 】s u g g e s t st h a ti t i sm o s ta p p r o p r i a t et om o d e la no p t i c a l n e t w o r kb yad i r e c t e dg r a p h ，s a yg = ( v ，e ) al i n ki nt h en e t w o r kc o r r e s p o n d st o ad i r e c t e de d g eo ra r ci nt h ed i r e c t e dg r a p h ，a n dan o d ei nt h en e t w o r kc o r r e s p o n d s t h em a s t e rd e g r e et h e s i so fz h e j i a n gu n i v e r s i t y t oav e r t e xi nt h e 出r e c t e dg r a p h vd e n o t e st h ev e r t e xs e to fga n ded e n o t e st h e a r cs e to fg i nt h en e x ts u b s e c t i o n s ，w ew i l lg i v ed e f i n i t i o n so fs e v e r a ld e s i r a b l e p r o p e r t i e st h a tw ew i l lb es t u d y i n gi nt h es e t t i n go ff a u l t t o l e r a n tr o u t i n g s t h e s e t e r m sh a v ep r e v i o u s l yb e e nd e f i n e di np a p e r ss u c ha s 【4 ，1 0 ，11 1 1 2t h em o d e la n dg o a l so fr o u t i n g si no p t i c a l n e t w o r k s f i b e r - o p t i cn e t w o r k i n gt e c h n o l o g yu s i n gw 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 ) o f f e r st h ep o t e n t i a lo fb u i l d i n gl a r g ew i d e - a r e an e t w o r k sc a p a b l eo fs u p p o r t i n gt h o u - s a n d so fn o d e sa n dp r o v i d i n gc a p a c i t i e so ft h eo r d e ro fg i g a b i t s - p e r - s e c o n dt oe a c h n o d ei nt h en e t w o r k i nw d m o p t i c a ln e t w o r k s e a c ha td i f f e r e n to p t i c a lw a v e l e n g t h e a c hw a v e l e n g t hc a nc a r r yd a t am o d u l a t e da tb i tr a t e so fs e v e r a lg i g a b i t sp e rs e c o n d i ng e n e r a l ，s u c han e t w o r kc o n s i s t so fw a v e l e n g t hr o u t e r si n t e r c o n n e c t e db yp o i n t - t o - p o i n tf i b e ro p t i cl i n k s ( f i g u r e1 ) e a c hl i n kc a l ls u p p o r ta c e r t a i nn u m b e ro fw a v 争 l e n g t h s w a v e l e n g t hr o u t e r sa r et h ea n a l o g so fs w i t c h e si nt r a d i t i o n a ln e t w o r k s e a c h r o u t e ri sa l le n d p o i n to fs e v e r a lo p t i c a ll i n k s e a c hl i n ki sc o n n e c t e dt oe i t h e ra ni n p u t p o r to ft h er o u t e ro ra no u t p u tp o r t t 1 1 er o u t e rd e t e r m i n e sw h i c hi n c o m i n gs i g n a li s t ob et r a n s m i t t e dt ow h i c ho u t g o i n gl i n k t h e r ei sa s i g n i f i c a n ta m o u n to fv a r i a n c e i nt h ef u n c t i o n a l i t yo far o u t e r - i nt e r m so fw h e ni td e t e r m i n e st h er o u t i n gp a t t e r n ， h o wi td e t e r m i n e st h er o u t i n gp a t t e r na n di fi tc h a n g e st h es i g n a l si tt r a n s m i t si n a n yf u n d a m e n t a lw a y t l l eo n ec o m m o nf e a t u r et h a ta l lr o u t e r ss h a r ei st h a tt h e y c a n n o tr o u t et w os i g n a l so nt h es a m ew a v e l e n g t ho nt h es a m eo u t g o i n gl i n k w es h a l l p r e s e n t l ys u m m a r i z et h em a i nc a t e g o r i e so fw a v e l e n g t hr o u t e r s i na d d i t i o nt or o u t e r s a n dl i n k s ，an e t w o r ka l s oc o n s i s t so fs e v e r a le n dn o d e s e a c hn o d ei sc o n n e c t e dt oa r o u t e ro ft h en e t w o r ka n dc o n s i s t so fat u n a b l eo p t i c a lr e c e i v e ra n dt u n a b l eo p t i c a l t r a n s m i t t e r t h et r a n s m i t t e rc a nb et u n e dt ot r a n s m i to na n yo ft h ea v a i l a b l ew a v e - l e n g t h sa n dt h er e c e i v e rc a nb et u n e dt or e c e i v eo na n yo ft h ea v a i l a b l ew a v e l e n g t h s 2 t h em a s t e rd e g r e et h e s i so fz h e j i a n gu n i v e r s i t y f i g u r e1 1 ：p i c l n e t w o r kc o n s i s t i n go fw a v e l e n g t hr o u t e r si n t e r c o n n e c t e db yp o i n t t o - p o i n t f i b e r - o p t i cl i n k s s o m eo ft h ew a v e l e n g t hr o u t e r sh a v en o d e sa t t a c h e dt ot h e mt h a t f o r mt h es o u r c e sa n dd e s t i n a t i o n sf o rn e t w o r kt r a 伍c w a v e l e n g t hr o u t e r s t h es i m p l e s tf o r mo faw a v e l e n g t hr o u t e ri san o n - r e c o n f i g u r a b l e r o u t e r i na n o n - r e c o n f i g u r a b l er o u t e r ，t h ei n c o m i n gt oo u t g o i n gp a t t e r ni sd e t e r m i n e d s t a t i c a l l ya n dc a nn o tb es w i t c h e do n c et h er o u t e ri sb u i l t t h em a i nf e a t u r eo fs u c h r o u t e r si st h ef a c tt h a tt h er o u t i n g p a t t e r nc a l lb eaf u n c t i o no ft h ew a v e l e n g t ho ft h e i n c o m i n gs i g n a l t h u sf o re a c hi n p u tp o r ta n de a c hw a v e l e n g t h ，t h er o u t e ra s s o c i a t e s af i x e ds e to fo u t p u tp o r t so nt ow h i c hi tw i l ls u c ha w a v e l e n g t hr o u t e r i ti sap a s s i v e ( u n p o w e r e d ) d e v i c e ，a n dc a nb er e a l i z e di nm a n yf o r m s t h er e a l i z a t i o nh e r eu s e s p a s s i v ew a v e l e n g t hd e m u l t i p l e x e r sa n dm u l t i p l e x e r s as e c o n df o r mo faw a v e l e n g t hr o u t e ri st h ew a v e l e n g t h i n d e p e n d e n tr e c o n f i g u r a b l e s w i t c h ( i np r e v i o u sv e r s i o n so ft h ep a p e rt h i ss w i t c hw a sa l s oc a l l e da ne l e m e n t a r y s w i t c h ) t h e s es w i t c h e sa r ef u n c t i o n a l l yi d e n t i c a lt os w i t c h e si nt h ec l a s s i c a ln e t w o r k s 3 w a v e l e n g t h d e m u x w a v e l e n g t h m m x f i g u r e1 2 ：p i c 2 an o n r e c o n f i g u r a b l e ( s w i t c h l e s s ) w a v e l e n g t hr o u t e rw i t h3p o r t sc a p a b l eo f h a n d s n g 3w a v e l e n g t h sp e rp o r t e a c hs w i t c hc a nb ed y n a m i c a l l yr e c o n f i g u r e dt oc h a n g ei t si n p u t o u t p u tp a t t e r n h o w e v e r ，t h ei n p u t o u t p u tp a t t e r ni si n d e p e n d e n to ft h ew a v e l e n g t ho ft h ei n c o m i n g s i g n a l t h u sf o raf i x e dc o n f i g u r a t i o no ft h es w i t c h ，t h e r ei saf i x e ds e to fo u t p u tp o r t s o nt ow h i c ha ni n c o m i n gs i g n a li st r a n s m i t t e di n d e p e n d e n to ft h e i rw a v e l e n g t h s at h i r df o r mo fw a v e l e n g t hr o u t e rw h i c hg e n e r a l i z e sb o t ht h ea b o v ef o r m si st h e w a v e l e n g t h - s e l e c t i v er e c o n f i g u r a b l es w i t c h ( i np r e c i o u sv e r s i o n so ft h ep a p e rt h i s s w i t c hw a sa l s oc a l l e dag e n e r a l i z e ds w i t c h ) a si nt h ew a v e l e n g t h - i n d e p e n d e n tc a s e ， t h ei n p u t o u t p u tp a t t e r no ft h ew a v e l e n g t hs e l e c t i v es w i t c hc a na l s ob es w i t c h e d d y n a m i c a l l y h o w e v e r ，i nt h i sc a s et h er o u t i n gp a t t e r nc a nb eaf u n c t i o no ft h e w a v e - l e n g t ho ft h ei n c o m i n gs i g n a l t h u sf o raf i x e dc o n f i g u r a t i o n ，f o re v e r yi n p u tp o r t a n dw a v e l e n g t ho ft h ei n c o m i n gs i g n a l ，t h es w i t c ha s s o c i a t e saf i x e ds e to fo u t p u t p o r t so n t ow h i c hi tt r a n s m i t st h i ss i g n a l i ti sc l e a rt h a tt h i ss w i t c hc a ns i m u l a t e e i t h e ro ft h et o u t e r sm e n t i o n e de a r l i e r i ti sa l s ot r u et h a tac o m b i n a t i o no fn o n r e c o n f i g u r a b l er o u t e r sa n dw a v e l e n g t h - i n d e p e n d e n tr e c o n f i g u r a b l es w i t c h e sc a ns i m u l a t ea w a v e l e n g t h - s e l e c t i v er e c o n f i g u r a b l es w i t c h ( s e ef i g u r e s3 ( a ) a n d ( b ) f o ra n 4 t h em a s t e rd e g r e et h e s i so fz h e j i a n gu n i v e r s i t y e x a m p l eo fh o w aw a v e l e n g t h - s e l e c t i v es w i t c hi ss i m u l a t e db yw a v e l e n g t hm u l t i p l e x e r s a n dd e m u l t i p l e x e r s ，a n dw a v e l e n g t hi n d e p e n d e n ts w i t c h e s ) l a s t l y , w em e n t i o nt h a tt h ef i t e r a t u r eh a sa l s oc o n s i d e r e dac l a s so fw a v e l e n g t h t o u t e r sw i t ha l la d d i t i o n a lf e a t u r et h a to fw a v e l e n g t hc o n v e r s i o n s u c hr o u t e r sa r e c a p a b l eo fc h a n g i n gt h ew a v e l e n g t ho fa ni n c o m i