（計(jì)算機(jī)軟件與理論專業(yè)論文）clos交叉矩陣中的路由算法研究.pdf

摘要 摘要 c l o s 網(wǎng)絡(luò)自從誕生以來，廣泛應(yīng)用于電話網(wǎng)絡(luò)、多處理器系統(tǒng)以及路由交換 機(jī)中。作為一種流行的的多級交叉結(jié)構(gòu)，具有成本低、可擴(kuò)展性好以及良好的路 由性能的特點(diǎn)，因此一直是研究的熱點(diǎn)。 目前智能光網(wǎng)絡(luò)的發(fā)展要求交叉矩陣具有高容量、快速的端口配置和組播支 持能力。而目前的c l o s 交叉矩陣，主要采用可重構(gòu)無阻塞結(jié)構(gòu)，在發(fā)生阻塞時(shí)需 要對交叉矩陣的狀態(tài)進(jìn)行重構(gòu)，目前的算法搜索重構(gòu)解的時(shí)間長，無法找到最優(yōu) 的重構(gòu)解，受影響的業(yè)務(wù)多，在單播業(yè)務(wù)和組播業(yè)務(wù)同時(shí)存在的時(shí)候組播業(yè)務(wù)的 阻塞率太高。 本文主要對c l o s 交叉矩陣中的路由算法進(jìn)行了研究，主要的工作和貢獻(xiàn)包括 以下兩個(gè)方面： 1 針對單播業(yè)務(wù)中的重構(gòu)問題，提出了一種改進(jìn)的路由算法一最優(yōu)重構(gòu)路 由算法( o r r a ) 。該算法首先采用順序方法分配中間模塊，出現(xiàn)阻塞時(shí)再進(jìn)行重構(gòu)， 采用的重構(gòu)算法是一種最優(yōu)重構(gòu)算法，它是在p a u l l 算法的基礎(chǔ)上，通過并行搜索 不同的重構(gòu)解，并在搜索過程中將這些重構(gòu)解的集合構(gòu)成輸入重構(gòu)樹和輸出重構(gòu) 樹，重構(gòu)樹的每一個(gè)路徑代表一個(gè)重構(gòu)解，每個(gè)路徑的深度代表一個(gè)重構(gòu)解的重 構(gòu)次數(shù)，故按照此算法搜索到的第一個(gè)找到的解即為最優(yōu)重構(gòu)解。該重構(gòu)算法是 基于p a u l l 算法的改進(jìn)算法，因此重構(gòu)樹在有限的高度下必然能夠找到最優(yōu)的重構(gòu) 解。通過o p n e t 軟件的仿真，發(fā)現(xiàn)通過o r r a 算法在搜索出最優(yōu)重構(gòu)解的基礎(chǔ) 上并沒有增加算法的運(yùn)行時(shí)間和交叉矩陣中的阻塞率。 2 研究了c l o s 交叉矩陣中的組播問題，并提出了一種基于四級c l o s 交叉矩 陣結(jié)構(gòu)的單組播混合業(yè)務(wù)的路由算法一置換路由算法( p r a ) 。該算法在三級c l o s 交叉矩陣的輸入級前增加一級，稱之為置換級，路由時(shí)先將每一個(gè)請求業(yè)務(wù)按照 其扇出值及輸入模塊的負(fù)載置換到不同的輸入模塊，利用輸入模塊完成扇出，最 后采用o r r a 算法完成扇出后業(yè)務(wù)的路由。通過o p n e t 軟件的仿真結(jié)果可以看 出，通過該算法能夠明顯的降低單組播混合業(yè)務(wù)的阻塞率，特別是組播業(yè)務(wù)的阻 塞率。 關(guān)鍵詞：o l o s 交叉矩陣路由算法組播重構(gòu) a b s t r a c t c l o sn e t w o r kh a sw i d e l yu s e di nt e l e p h o n en e t w o r k s ，m u l t i - p r o c e s s o rs y s t e ma n d s w i t c h r o u t e r ss i n c ei tw a sf i r s tp r o p o s e d a n dc l o sn e t w o r k ，o n et y p eo ft h em u l t i - s t a g e n e t w o r k ，w a se x t e n s i v e l yr e s e a r c h e db e c a u s eo fi t sc h a r a c t e r i s t i c so fg o o ds c a l a b i l i t y , l o w e rh a r d w a r ec o s ta n de x c e l l e n t r o u t i n gp e r f o r m a n c e a tp r e s e n t ，t h ed e v e l o p m e n to fi n t e l l i g e n to p t i c a ln e t w o r kr e q u i r e st h em a t r i xw i t h 1 1 i g h - c a p a c i t y , r a p i dp o r tc o n f i g u r a t i o na n dm u l t i c a s ts u p p o r t e d b u tt h ew i d e l yu s e d r e a r r a n g e a b l et h r e es t a g ec l o sm a t r i xs h o u l db er e a r r a n g e dw h e nt h ec a l li sb l o c k e d ，a n d t h ec u r r e n tr o u t i n ga l g o r i t h mh a st h ed i s a d v a n t a g eo fm o r et i m ec o n s u m i n g ，m o r e e x i s t i n g c o n n e c t i o ni n f l u e n c e d ，h i g h e r p e r c e n t a g e o fm u l t i c a s tt r a f f i c b l o c k i n g p r o b a b i l i t y , a n dr e a r r a n g es o l u t i o ni sn o to p t i m a l t os o l v et h i sp r o b l e m ，t w on e w r o u t i n ga l g o r i t h m sa r ep r o p o s e df o rc l o sn e t w o r k t h e m a j o rw o r k sa n dc o n t r i b u t i o n sa r et h ef o l l o w i n gt w oa s p e c t s o r r a ( o p t i m a lr e a r r a n g e a b l er o u t i n ga l g o r i t h m ) w h i c hs o l v e st h ep r o b l e m so f u n i c a s tc o n n e c t i o n sr e a r r a n g e m e n t ，s e a r c h e sp a t hi ns e q u e n c eo r d e ra tf i r s t a n dt h e c l o sm a t r i xs h o u l db er e a r r a n g e di ft h ec a l li sb l o c k e d t h er e a r r a n g e a b l ea l g o r i t h mo f o r r ai m p r o v e df r o mp a u l la l g o r i t h m ，i sat y p eo fo p t i m a lr e a r r a n g e a b l ea l g o r i t h m i t s e a r c h e sa l lt h e r e a r r a n g e m e n ts o l u t i o n s i nt h e p a r a l l e l f a s h i o nu n t i lt h ef i r s t r e a r r a n g e m e n ts o l u t i o ni sf o u n d f o rt h es a k eo fr e c o r d i n gr e a r r a n g e m e n ts o l u t i o n st h e i n p u tr e a r r a n g et r e ea n do u t p u tr e a r r a n g e m e n tt r e ea r ec o n s t r u c t e d e v e r yp a t ho ft r e e r e p r e s e n t sar e a r r a n g e m e n ts o l u t i o n , a n dt h er e a r r a n g e m e n tt i m ec o u l db ed e n o t e db y t h ed e e po ft h ep a t h s i m u l a t i o n sw e r ec a r r i e do u to nd i f f e r e n ts c a l ec l o sm a t r i xw i t h o p n e ts o f t w a r e ，a n dt h er e s u l t ss h o wt h a tt h eo p t i m a lr e a r r a n g e m e n ts o l u t i o ni s a c h i e v e dt h r o u g ho r r aw i t h o u ti n c r e a s i n gt i m ec o n s u m i n ga n db l o c k i n gp r o b a b i l i t y p r a ( p e r m u t a t i o nr o u t i n ga l g o r i t h m ) w h i c ha p p l i e df o ru n i c a s ta n dm u l t i c a s t t r a f f i ci si n t r o d u c e dt of o u rs t a g e sc l o sm a t r i xw h i c ha d d so n ep e r m u t a t i o ns t a g eb e f o r e i n p u ts t a g eo ft h r e es t a g ec l o sm a t r i x i nt h ef i r s tp l a c e ，t h ec a l l sa r ep e r m u t a t e dt o d i f f e r e n ti n p u tp o r t sb yt h ep e r m u t a t i o ns t a g ea c c o r d i n gt ot h ef a n o u to fc a l la n dt h e o u t p u tp o r tl o a d so fi n p u tm o d u l e ，a n dt h e nc o m p l e t e dt h ef a n o u ti nt h ei n p u ts t a g e f i n a l l y , r o u t et h eu n i c a s tc a l l st h r o u g ho r r aa l g o r i t h m s i m u l a t i o n sw e r ec a r r i e do u t i nd i f f e r e n ts c a l ef o u rs t a g e sc l o sm a t r i x 謝t 1 1o p n e ts o f t w a r e ，a n dt h er e s u l t ss h o w t h a tp r aa c h i e v e sal o w e rb l o c k i n gp r o b a b i l i t yt h a no t h e ra l g o r i t h m s ，e s p e c i a l l yf o r m u l t i c a s tt r a f f i c k e y w o r d ：c l o sm a t r i xr o u t i n ga l g o r i t h m m u l t i e a s t r e a r r a n g ea l g o r i t h m 創(chuàng)新性聲明 本人聲明所呈交的論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究 成果。盡我所知，除了文中特別加以標(biāo)注和致謝中所羅列的內(nèi)容以外，論文中不 包含其他人已經(jīng)發(fā)表或撰寫過的研究成果；也不包含為獲得西安電子科技大學(xué)或 其它教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我一同工作的同志對本研究所做 的任何貢獻(xiàn)均已在論文中做了明確的說明并表示了謝意。 申請學(xué)位論文與資料若有不實(shí)之處，本人承擔(dān)一切相關(guān)責(zé)任。 本人簽名：蓖鱟鱟 關(guān)于論文使用授權(quán)的說明 本人完全了解西安電子科技大學(xué)有關(guān)保留和使用學(xué)位論文的規(guī)定，即：研究 生在校攻讀學(xué)位期間論文工作的知識產(chǎn)權(quán)單位屬西安電子科技大學(xué)。本人保證畢 業(yè)離校后，發(fā)表論文或使用論文工作成果時(shí)署名單位仍然為西安電子科技大學(xué)。 學(xué)校有權(quán)保留送交論文的復(fù)印件，允許查閱和借閱論文；學(xué)?？梢怨颊撐牡娜?部或部分內(nèi)容，可以允許采用影印、縮印或其它復(fù)制手段保存論文。( 保密的論文 在解密后遵守此規(guī)定) 本學(xué)位論文屬于保密在一年解密后適用本授權(quán)書。 本人簽名： 導(dǎo)師簽名： 壺絲壘： 日期圣竺查：三：了 日期上趟蓋乒 第1 章緒論 第1 章緒論 1 1 研究背景及現(xiàn)狀 隨著i n t e m e t 的迅速發(fā)展，人們對數(shù)據(jù)業(yè)務(wù)的需求激增，特別是具有突發(fā)、多 變、不確定等特性的i p 業(yè)務(wù)正在成為網(wǎng)絡(luò)中的主導(dǎo)業(yè)務(wù)，并且以指數(shù)式增長。而 傳統(tǒng)的光傳送網(wǎng)在傳送i p 業(yè)務(wù)方面有著明顯的不足，主要表現(xiàn)在：網(wǎng)絡(luò)支配過于 復(fù)雜、傳輸開銷過大；網(wǎng)絡(luò)互聯(lián)方面不夠靈活；無法實(shí)現(xiàn)帶寬的動態(tài)分配。這一 系列缺點(diǎn)都促使開發(fā)新一代的光網(wǎng)絡(luò)以滿足用戶以及開發(fā)商對不斷增長的數(shù)據(jù)業(yè) 務(wù)需求。 通信技術(shù)的發(fā)展歷史其實(shí)是一個(gè)不斷提高載波頻率和增加傳輸容量的的歷 史。自從1 9 6 6 年英籍華裔科學(xué)家高錕( c k k a o ) 提出利用光纖進(jìn)行信息傳輸?shù)?可能后，光通信技術(shù)不斷更新?lián)Q代，通信能力不斷提高，應(yīng)用范圍不斷擴(kuò)大。目 前的光網(wǎng)絡(luò)傳送層基本是以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 ) 和w d m ( w a v e d i v i s i o nm u l t i p l e x i n g ) 兩層構(gòu)筑，采用環(huán)式拓?fù)浣Y(jié)構(gòu)，主要應(yīng)用在靜態(tài)傳輸網(wǎng)絡(luò)中， 使得光網(wǎng)絡(luò)向動態(tài)、高度靈活性方向發(fā)展受到了極大限制，因此，研究人員正在 積極研制下一代光網(wǎng)絡(luò)，以便集傳輸、交換、智能于一體，實(shí)現(xiàn)高度靈活和適應(yīng) 性強(qiáng)的大容量光傳送網(wǎng)。 1 1 1 自動交換光網(wǎng)絡(luò) 光傳送網(wǎng)逐漸從單純的傳送平臺演進(jìn)為一個(gè)與上層業(yè)務(wù)網(wǎng)緊密結(jié)合的綜合 網(wǎng)，網(wǎng)絡(luò)的組網(wǎng)靈活性、高可靠性和智能性已成為人們關(guān)注的焦點(diǎn)。為了順應(yīng)光 網(wǎng)絡(luò)的演進(jìn)趨勢。使現(xiàn)有的靜態(tài)傳輸網(wǎng)絡(luò)向動態(tài)、可運(yùn)營管理的智能化網(wǎng)絡(luò)演進(jìn)， 人們將a t m 和i p 路由功能引入到光傳送網(wǎng)中，使得以w d m 為基礎(chǔ)的光層組網(wǎng) 技術(shù)和以i p 為基礎(chǔ)的網(wǎng)絡(luò)智能化技術(shù)迅速發(fā)展并結(jié)合起來，形成了自動交換光網(wǎng) 絡(luò)a s o n ( a u t os w i t c ho p t i c a ln e t w o r k ) 。 a s o n 通過在傳統(tǒng)的靜態(tài)光網(wǎng)絡(luò)中引入動態(tài)交換和智能控制能力，完成“光傳 送網(wǎng)+ 智能化”，從而使光網(wǎng)絡(luò)從傳統(tǒng)的“承載網(wǎng)絡(luò)”向“業(yè)務(wù)網(wǎng)絡(luò)”演進(jìn)，從被動的網(wǎng) 絡(luò)管理( 監(jiān)控) 向主動地控制網(wǎng)絡(luò)演進(jìn)。這種演進(jìn)以現(xiàn)有傳送網(wǎng)的光層網(wǎng)絡(luò)為基 礎(chǔ)，是一個(gè)無縫融合的革新過程；既保護(hù)了運(yùn)營商的原有投資，又把富有潛力的 光網(wǎng)絡(luò)發(fā)展成能高度自主地應(yīng)對業(yè)務(wù)需要、經(jīng)濟(jì)有效、可在光層上直接為全網(wǎng)提 供端到端服務(wù)的智能化控制光網(wǎng)絡(luò)，而且可以根據(jù)不同也業(yè)務(wù)提供不同的服務(wù)等 級，保證高優(yōu)先級的業(yè)務(wù)的服務(wù)質(zhì)量【2 】。 a s o n 的每個(gè)網(wǎng)元都具有智能性，網(wǎng)元間可進(jìn)行路由信息和鏈路狀態(tài)信息的 2 c l o s 交叉矩陣中的路由算法研究 交換【3 1 。每個(gè)網(wǎng)元依據(jù)動態(tài)路由協(xié)議掌握著整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和相關(guān)鏈路的狀 態(tài)，實(shí)現(xiàn)資源的動態(tài)發(fā)現(xiàn)【4 】o 網(wǎng)元知道哪些網(wǎng)元具有可達(dá)性，并知道通過哪些路徑 可達(dá)。智能光網(wǎng)絡(luò)充分簡化了網(wǎng)絡(luò)管理系統(tǒng)，通過一個(gè)網(wǎng)管系統(tǒng)就可實(shí)現(xiàn)對網(wǎng)絡(luò) 的有效管理，實(shí)現(xiàn)端到端的配置、故障管理和性能管理等功能。 a s o n 具有自身的網(wǎng)管系統(tǒng)，它是光傳送網(wǎng)網(wǎng)管體系結(jié)構(gòu)的一個(gè)組成部分【5 】。 在邏輯上，a s o n 網(wǎng)管系統(tǒng)與s d h 網(wǎng)管系統(tǒng)、w d m 網(wǎng)管系統(tǒng)并行管理光傳送網(wǎng)， 它們屬于同一層面。因此，a s o n 網(wǎng)絡(luò)管理應(yīng)采取以a s o n 網(wǎng)管系統(tǒng)管理為主， 需要時(shí)應(yīng)與s d h 網(wǎng)管系統(tǒng)相配合來協(xié)調(diào)管理整個(gè)傳送網(wǎng)，充分發(fā)揮a s o n 網(wǎng)在傳 送網(wǎng)中的智能化電路調(diào)度作用。同時(shí)以網(wǎng)格狀的組網(wǎng)方式，通過分布式智能管理， 提供更為完善的恢復(fù)機(jī)制、快速的電路響應(yīng)、有效的資源利用和便捷的帶寬管理。 新一代智能光網(wǎng)絡(luò)a s o n 具有多方面的優(yōu)勢： 1 智能化：快速提供網(wǎng)絡(luò)業(yè)務(wù)，提供新的業(yè)務(wù)利潤增長點(diǎn)，如光虛擬專網(wǎng) ( o v p n ) ，業(yè)務(wù)流量工程( t e ) ，三重播放( t r i p l ep l a y ) 等高a r p u ( a v e r a g er e v e n u e p e ru s e r ) 值業(yè)務(wù)；提高業(yè)務(wù)的生存性，有效抵抗網(wǎng)絡(luò)多點(diǎn)故障，真正達(dá)到9 9 9 9 9 以上的電信級業(yè)務(wù)等級； 2 標(biāo)準(zhǔn)化：通過采用標(biāo)準(zhǔn)化的協(xié)議和接口實(shí)現(xiàn)多廠商，多運(yùn)營商環(huán)境下的 網(wǎng)絡(luò)互操作； 3 個(gè)性化：靈活提供不同的業(yè)務(wù)等級滿足目前迅速發(fā)展的差異化( d i f f - s e r v ) 服務(wù)的需要； 4 簡易化：實(shí)現(xiàn)對業(yè)務(wù)的自動保護(hù)和拓?fù)浒l(fā)現(xiàn)，減少人工配置的工作量， 充分降低維護(hù)難度。 a s o n 在傳統(tǒng)的靜態(tài)光網(wǎng)絡(luò)中引入動態(tài)交換和智能控制能力，從而使傳送網(wǎng) 實(shí)現(xiàn)從承載網(wǎng)向業(yè)務(wù)網(wǎng)的演進(jìn)。隨著它的技術(shù)框架體系結(jié)構(gòu)和協(xié)議的成熟，作為 傳送網(wǎng)的主流發(fā)展方向已獲得業(yè)界的普遍認(rèn)同。目前各大通信設(shè)備提供商均有 a s o n 網(wǎng)絡(luò)設(shè)備，而且各大運(yùn)營商已經(jīng)開始在局部地區(qū)構(gòu)建a s o n 網(wǎng)絡(luò)。 1 1 2a s o n 網(wǎng)絡(luò)中的業(yè)務(wù) 在傳統(tǒng)的光網(wǎng)絡(luò)中，主要提供端到端的面向連接業(yè)務(wù)，隨著寬帶技術(shù)的不斷 發(fā)展，f t p 、h t t p 、s m t p 等傳統(tǒng)數(shù)據(jù)業(yè)務(wù)已經(jīng)難以滿足人們對信息業(yè)務(wù)的需求， 視頻點(diǎn)播、遠(yuǎn)程教學(xué)、新聞發(fā)布、網(wǎng)絡(luò)電視等業(yè)務(wù)將成為新一輪運(yùn)營競爭的焦點(diǎn)。 這類新型業(yè)務(wù)的特點(diǎn)是，由一個(gè)服務(wù)器( 媒體流服務(wù)器) 發(fā)布信息，大數(shù)量的客戶 端接收信息，其數(shù)量可能是成千上萬，而且具體數(shù)目不固定。而組播技術(shù)非常適 合這類新型業(yè)務(wù)，并具有下列優(yōu)點(diǎn)： 1 ) 流服務(wù)器不必知道某個(gè)客戶端是否存在，它只負(fù)責(zé)按組播地址將媒體流播放 出去； 2 ) 流數(shù)據(jù)在網(wǎng)上僅僅傳送一份即可，即使有成千上萬個(gè)客戶端； 第1 章緒論 3 3 ) 用戶端如果希望接收某媒體流服務(wù)器的數(shù)據(jù)時(shí)，只需加入該媒體流服務(wù)器播 放數(shù)據(jù)使用的組播組即可1 6 j 。 所以傳送網(wǎng)能否很好的支持組播業(yè)務(wù)則對傳送網(wǎng)性能的又一大挑戰(zhàn)，對于傳 輸網(wǎng)絡(luò)要支持組播業(yè)務(wù)的關(guān)鍵就是要交叉連接設(shè)備能夠?qū)崿F(xiàn)一對多或多對一的輸 入輸出端口完成交換功能；做為交叉連接設(shè)備的核心，交叉矩陣是實(shí)現(xiàn)交換的最 終承擔(dān)者，因此這也是本文研究的意義所在。 m l c - 0 x c ：組播光交叉連接：具有組播能力的光交叉連接設(shè)備 圖1 1 光網(wǎng)絡(luò)中的組播 圖1 1 是一個(gè)光網(wǎng)絡(luò)中的組播實(shí)例，數(shù)據(jù)從一個(gè)客戶節(jié)點(diǎn)s 要同時(shí)傳送到三 個(gè)目的客戶節(jié)點(diǎn)d 1 、d 2 、d 3 ，如果網(wǎng)絡(luò)中的交換設(shè)備不支持組播交換，那么就需 要從原節(jié)點(diǎn)到目的節(jié)點(diǎn)分別建立連接；但是如果交叉連接設(shè)備具有組播功能，如 圖1 1 中的m c o x c ，那么就可以通過在交叉連接設(shè)備中進(jìn)行扇出，如藍(lán)色線條 所示。從圖中可以看出要實(shí)現(xiàn)網(wǎng)絡(luò)的組播，網(wǎng)絡(luò)中必須包含具有組播能力的交叉 連接設(shè)備，通過該交叉連接設(shè)備來實(shí)現(xiàn)一對多的連接，因此具有組播能力的交叉 連接設(shè)備是支持網(wǎng)絡(luò)實(shí)現(xiàn)組播業(yè)務(wù)的基礎(chǔ)。 1 1 3 光網(wǎng)絡(luò)中的傳輸設(shè)備 交叉矩陣是a s o n 節(jié)點(diǎn)設(shè)備傳送平面的核心部分，a s o n 設(shè)備和傳統(tǒng)的 s d h m s t p 設(shè)備相比，除了增加控制平面外，在傳送平面硬件方面也有更高的要 求。例如交叉容量的提升和交叉矩陣對組播業(yè)務(wù)的支持。這主要是基于以下三方 面的原因：首先，a s o n 是基于格狀網(wǎng)絡(luò)構(gòu)建的，相對于以往的環(huán)網(wǎng)結(jié)構(gòu)來說，a s o n 節(jié)點(diǎn)設(shè)備上要提供更多的光接口，要有更強(qiáng)的業(yè)務(wù)調(diào)度和疏導(dǎo)能力。其次，在基 于格狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的a s o n 網(wǎng)絡(luò)中，網(wǎng)絡(luò)的保護(hù)和恢復(fù)都是根據(jù)網(wǎng)絡(luò)中當(dāng)前資 源進(jìn)行動態(tài)實(shí)時(shí)配置，因而交叉矩陣必須能夠快速的完成輸入輸出端口的配置， 來提高恢復(fù)時(shí)間。最后，交叉矩陣具有組播能力可以更好地支持a s o n 網(wǎng)絡(luò)中的 組播業(yè)務(wù)。 目前在交換設(shè)備中應(yīng)用最為廣泛的交換結(jié)構(gòu)為c r o s s b a r 結(jié)構(gòu)和三級c l o s 結(jié) 4 c l o s 交叉矩陣中的路由算法研究 構(gòu)，c r o s s b a r 結(jié)構(gòu)具有但組播嚴(yán)格無阻塞的特點(diǎn)，但是成本高，可擴(kuò)展性差的不 足，目前主要采用b i t s l i c e 技術(shù)來提高單板的交叉能力。三級c l o s 結(jié)構(gòu)是一種多級 網(wǎng)絡(luò)結(jié)構(gòu)，常用的是重構(gòu)無阻塞結(jié)構(gòu)，他的優(yōu)點(diǎn)是成本低，可擴(kuò)展性好，但是在 存在組播業(yè)務(wù)時(shí)，網(wǎng)絡(luò)的阻塞率比較高，由于傳統(tǒng)的三級c l o s 矩陣的重構(gòu)無阻塞 特性，在網(wǎng)絡(luò)發(fā)生故障時(shí)，a s o n 節(jié)點(diǎn)設(shè)備的交叉連接要進(jìn)行內(nèi)部路由搜索，延 長了全網(wǎng)恢復(fù)時(shí)間。 1 2c l o s 網(wǎng)絡(luò)的介紹 c l o s 網(wǎng)絡(luò)于1 9 5 3 由貝爾實(shí)驗(yàn)室的c h a r l e sc l o s 提出i | 7 1 ，它通過使用多個(gè)較小 交換容量的交換單元來構(gòu)建大容量交叉矩陣。c l o s 網(wǎng)絡(luò)具有良好的可擴(kuò)展性瞄馴、 高度的靈活性和可靠性【1 0 d 1 1 。良好的可擴(kuò)展性是指網(wǎng)絡(luò)的規(guī)模能夠適應(yīng)網(wǎng)絡(luò)業(yè)務(wù) 發(fā)展的需要，隨著網(wǎng)絡(luò)業(yè)務(wù)量的增長，網(wǎng)絡(luò)的交換容量可以平滑升級，提高網(wǎng)絡(luò) 設(shè)備初期投資的利用率；高度的靈活性指的是網(wǎng)絡(luò)能夠滿足傳輸網(wǎng)絡(luò)業(yè)務(wù)多樣化、 綜合化的要求，能夠?qū)崿F(xiàn)多顆粒度，不同服務(wù)質(zhì)量保證的業(yè)務(wù)轉(zhuǎn)發(fā)要求；網(wǎng)絡(luò)的 可靠性指的是網(wǎng)絡(luò)結(jié)構(gòu)具有路徑多樣性，擁有強(qiáng)大的容錯能力并且具有對業(yè)務(wù)轉(zhuǎn) 發(fā)的自動保護(hù)機(jī)制，因此能夠適應(yīng)網(wǎng)絡(luò)業(yè)務(wù)對傳輸設(shè)備可靠性的要求。 1 2 1 結(jié)構(gòu)及分類 常見的三級對稱的c l o s 網(wǎng)絡(luò)如圖1 2 所示，第一級是由r 個(gè)n x m 交換單元構(gòu) 成；第二級是由m 個(gè)r r 交換單元構(gòu)成；第三級是由r 個(gè)m n 交換單元構(gòu)成， 相鄰兩級的任意一對模塊之間均存在一條物理鏈路，因此可以用符號c ( m ，n ，r ) 來表示。如果將一個(gè)三級c l o s 網(wǎng)絡(luò)中的任一級交換模塊用一個(gè)三級c l o s 網(wǎng)絡(luò)來代 替，就可以構(gòu)造出一個(gè)五級的交叉矩陣，以此類推可以構(gòu)造出任意奇數(shù)級的c l o s 網(wǎng)絡(luò)【1 2 1 。 圖1 2 三級c l o s 交叉矩陣c l o s ( m ，刀，) 一。 “ 。一一 ；州一一 第1 章緒論 5 1 2 2 單播阻塞條件分析 對于一個(gè)c l o s 交叉矩陣，按照網(wǎng)絡(luò)狀態(tài)的特征( 網(wǎng)絡(luò)狀態(tài)定義為正在進(jìn)行的 呼叫在中間級交換單元的占用格局) ，定義某些空閑的輸入輸出端口對之間不能建 立連接的網(wǎng)絡(luò)狀態(tài)為阻塞狀態(tài)。根據(jù)網(wǎng)絡(luò)的阻塞特性可以將其分為以下三種【1 3 】： ( a ) c l o s 網(wǎng)絡(luò)是可重配置無阻塞的( r e a r r a n g e a b l e ) 指的是當(dāng)且僅當(dāng)給定一 組正在進(jìn)行的呼叫和任一對空閑的輸入輸出端口，通過對當(dāng)前進(jìn)行中的呼叫重選 路由，可以在這對空閑的輸入輸出端1 2 1 之間至少建立一條連接路徑。d s l e p i a n i l 4 】 證明了三級c l o s 網(wǎng)絡(luò)v ( m ，1 1 ，) 的可重配置無阻塞條件為m 刀。 ( b ) c l o s 網(wǎng)絡(luò)是廣義無阻塞的( n o n b l o c k i n gi nt h ew i d es e n s e ) ：指的是當(dāng)且僅 當(dāng)合理的為每個(gè)呼叫分配路徑以避免阻塞狀態(tài)而且還能為每對空閑輸入輸出端口 分配新的路徑，而不需要重新調(diào)整已建立的連接路徑。a j a j s z c z y k 和c lj e k e l 在 r e p a c k i n g 概念的基礎(chǔ)上提出了r e p a c k a b l e 無阻塞的概劊1 5 j 。通過定義非永久狀態(tài) ( n o n p e r m a n e n t ) 和過載狀態(tài)( o v e r w e i g h ts t a t e ) ，他們證明如果網(wǎng)絡(luò)的控制算法使得 網(wǎng)絡(luò)的每一個(gè)過載狀態(tài)都是非永久狀態(tài)，網(wǎng)絡(luò)的無阻塞充要條件是 m 2 n - f n ( r - 1 ) 。 ( c ) c l o s 網(wǎng)絡(luò)是嚴(yán)格無阻塞的( n o n b l o c k i n gi nt h es t r i c ts e n s e ) ，是指不管采用 何種選路策略都不存在任何阻塞狀態(tài)。c h a r l e s c l o s 最早給出了三級c l o s 網(wǎng)絡(luò) v ( m ，刀，) 的嚴(yán)格無阻塞條件為m 2 n 一1 。 上面給出了可重配置無阻塞三級c l o s 交叉矩陣，廣義無阻塞三級c l o s 交叉矩 陣和嚴(yán)格無阻塞三級c l o s 交叉矩陣的定義以及條件，可以看出區(qū)別在于中間級交 換單元的數(shù)目以及為到達(dá)的呼叫采用的選路策略。雖然廣義無阻塞和嚴(yán)格無阻塞 的c l o s 交叉矩陣可以無阻塞的建立連接，但是由于成本和實(shí)際應(yīng)用中負(fù)載不可能 達(dá)到飽和，因此可重構(gòu)無阻塞交叉矩陣的應(yīng)用最為廣泛。 1 2 3 組播阻塞條件分析 對于組播業(yè)務(wù)目前理論上只給出了嚴(yán)格無阻塞和一些廣義無阻塞的條件，對 于可重構(gòu)無阻塞目前還沒有理論上的結(jié)論。而且對于組播業(yè)務(wù)阻塞特性和交叉矩 陣的組播扇出位置有很大關(guān)系。 g m m a s s o n 和b w j o r d a n 在文獻(xiàn)【l6 】中第一次提出了嚴(yán)格無阻塞條件和可重構(gòu) 無阻塞條件，當(dāng)中間級交換單元數(shù)目滿足條件m n + 【廠+ 1 ) 一l 時(shí)，則c l o s 交叉 矩陣對于組播業(yè)務(wù)是嚴(yán)格無阻塞的，而當(dāng)滿足條件m 玎木，時(shí)，網(wǎng)絡(luò)對于組播業(yè)務(wù) 則是可重構(gòu)無阻塞的。這個(gè)條件的得到是基于輸入級扇出機(jī)制下得到的，網(wǎng)絡(luò)成 本很高，沒有實(shí)用價(jià)值。h w a n g 在文獻(xiàn)【l7 1 指出，如果中間級交換單元沒有組播扇 出能力時(shí)，以至于所有連接扇出必須在第一級和第三級進(jìn)行，在這種假設(shè)條件下 m a s s o n 提出的對中間級交換單元數(shù)目的要求實(shí)現(xiàn)可重構(gòu)無阻塞則是充分必要的。 6 c l o s 交叉矩陣中的路由算法研究 后來y u a n y u a ny a n g 又在【1 8 】提出了當(dāng)m 1 1 1 j h ( ( 1 1 - - 1 ) ， + ，”，其中x 表示組播業(yè)務(wù) 使用的中間模塊數(shù)，并且滿足l sx s 蛐n 【n - l , r ) ，這樣該c l o s 交叉矩陣對于組播 業(yè)務(wù)可以實(shí)現(xiàn)無阻塞條件。下表1 1 是在給定扇出值f 時(shí)，各種不同扇出模式下嚴(yán) 格無阻塞條件，其中扇出值f 表示一個(gè)組播業(yè)務(wù)要占用的輸出模塊數(shù)i l 圳。 上面簡要分析了c l o s 交叉矩陣中組播無阻塞條件，而且對于任意一個(gè)組播嚴(yán) 格無阻塞網(wǎng)絡(luò)，需要的開關(guān)數(shù)最少為u i 川j 【2 0 1 ，上面的嚴(yán)格無阻塞c l o s 交叉矩陣 的規(guī)模已經(jīng)遠(yuǎn)遠(yuǎn)超出了c r o s s b a r 網(wǎng)絡(luò)的規(guī)模，因此采用傳統(tǒng)的c l o s 交叉矩陣對于 組播業(yè)務(wù)來說阻塞率太高。 表1 1 各種結(jié)構(gòu)限制下的嚴(yán)格無阻塞的充分必要條件 網(wǎng)絡(luò)結(jié)構(gòu)特點(diǎn)( 扇出機(jī)制) 充分必要條件 三級均可自由扇出 m m i n ( n l 一1 ) 廠+ 他，( l - 1 ) f ，2 ) 第一級無扇出能力 m m i n n 2 一吃+ ( + n 2 1 ) n 2 ，1 ) 第二級無扇出能力 m _ n i n ( t t 一咖一1 + n i n 呸) “一驂廠 州疋呸 ，趣) 第三級無扇出能力 m m i n ( r 一1 ) f + t h ，( m 一1 ) f + m i n f , 吃) ，m ) 1 2 4 阻塞率分析 對于傳統(tǒng)的三級c l o s 交叉矩陣，在全單播的情況下，要建立一條從確定的輸 入端口到確定的輸出端口之間連接，則要從輸入模塊到某個(gè)中間模塊之間的鏈路 和中間模塊到輸出模塊之間的鏈路均為空。如果用p 表示每條鏈路被占用的概率， 則p = pn m ，q = l - p 表示為空的概率，經(jīng)過某個(gè)中間模塊建立成功的概率為( 1 p ) 2 ， 由于有m 個(gè)中間模塊，因此一個(gè)單播請求被阻塞的概率p b = 1 - ( 1 - p ) 2 】m 。對于一個(gè) 多鏈路c l o s 結(jié)構(gòu)，由于每組有v 條鏈路，因此每一組全被占用的概率為p v ，這樣 阻塞的概率p b = 1 一( 1 - p v ) 2 】m 。 對于一個(gè)組播請求，用輸出模塊表示，那么扇出值f 則滿足1 ，用q ，吃， 表示從輸入模塊到中間模塊之間的連接，瓦表示該鏈路被占用，q 表示該鏈路空閑； 魄。，：，k 表示從中間模塊到輸出模塊k 之間的鏈路。用e 表示對一個(gè)扇出為f 的 組播請求產(chǎn)生阻塞的狀態(tài)，o 表示輸入級與中間級之間的鏈路的狀態(tài)，尸( i 口) 表 示在狀態(tài)表示在狀態(tài)0 下產(chǎn)生阻塞的概率，尸( 仃) 表示處于該狀態(tài)的概率。那么對 于該請求的阻塞率可以表示如下【2 1 】： 名( f ) = p ( s ) = p ( 仃) 尸( sl 仃) ：= 薹( ：l 戶j ，”一尸( 占f 百，：i - ，口t + - ，a ) ( 。) 其中： 第1 章緒論 7 p ( s 雨，- ，) 1 _ ( 1 一p ) ，( 1 2 ) 將式( 1 2 ) 代入式( 1 1 ) 后阻塞率可以表示為： w ) 2 敲聲p - k l - ( t 卅，( 1 3 ) 假如組播請求的輸出值均勻分配分布，那么對于任意扇出的阻塞率可以對式 ( 1 3 ) 中所有的扇出情況可以取平均值表示如下： b = 尼( 廠) = 吾烈：戶p - k ，如) ， 。，4 ， 雖然以上的分析給出了阻塞率與負(fù)載和扇出值的關(guān)系，但是首先從輸出單元 的限制性上考慮到輸出單元自身的限制性可以對式( 1 2 ) 描述的阻塞概率表達(dá)式 加以修改。這里考慮點(diǎn)對多點(diǎn)和點(diǎn)對點(diǎn)兩種連接，且每一個(gè)輸出單元有n 個(gè)輸出 端1 3 ，如果某一個(gè)輸出交換單元在一個(gè)組播請求中被選中，那么這個(gè)輸出交換單 元至少有一個(gè)空閑輸出端口，最多有n - 1 個(gè)輸入端口處于忙狀態(tài)。特別是當(dāng)k n 1 的情況，f 個(gè)輸出交換單元中每個(gè)都必須有空閑的輸入端口。所以在k n 1 時(shí)p b = o 。 其次從處于忙狀態(tài)的鏈路比例考慮到在任意時(shí)刻輸入級和中間級處于忙狀態(tài) 的鏈路數(shù)目以及中間級和輸出級之間處于忙狀態(tài)的鏈路數(shù)目，仍然分析點(diǎn)對多點(diǎn) 和點(diǎn)對點(diǎn)的連接請求。一般來講輸入級到中間級的處于忙的鏈路數(shù)應(yīng)該比從中間 級到輸出級處于忙狀態(tài)的鏈路數(shù)要少。所以在這里假設(shè)從中間級到輸出級鏈路遇 忙的概率和空閑的概率分別為所和吼 島2 ；q b2 1 一p b ( 1 5 ) 這樣從輸入級到中間級的鏈路遇忙和空閑的概率則可以修改為 島= a 見；和吼= 1 一見 ( 1 6 ) 其中口1 ，所以計(jì)算扇出值f 的組播請求被阻塞概率表達(dá)式( 1 3 ) 又被修改 成下面形式 忍( 廠) = n - , o 。2 兒”一?！? 一( 1 一見) ，】 b = 吾嘉莖( ? 卜。見”廿c 一。一見七，l c n - 1 【兄= 0 1 c 行 ( 1 7 ) ( 1 8 ) 8 c l o s 交叉矩陣中的路由算法研究 1 3 論文內(nèi)容及結(jié)構(gòu) c l o s 網(wǎng)絡(luò)是一種應(yīng)用非常廣泛的多級網(wǎng)絡(luò)結(jié)構(gòu)，特別是在大容量的交換設(shè)備 中，隨著光網(wǎng)絡(luò)的智能化的發(fā)展，網(wǎng)絡(luò)中的服務(wù)要求越來越高，網(wǎng)絡(luò)規(guī)模越來越 大，而且組播業(yè)務(wù)的出現(xiàn)給交叉矩陣的結(jié)構(gòu)和算法的設(shè)計(jì)提出了更高的要求，本 文主要是在c l o s 網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上，給出c l o s 交叉矩陣的路由算法設(shè)計(jì)的基礎(chǔ)。 本文的內(nèi)容及結(jié)構(gòu)安排如下：第二章分別介紹并比較了c l o s 交叉矩陣中的幾 種單播和組播算法；第三章在原有的單播算法的基礎(chǔ)上提出了單播業(yè)務(wù)的o 鼬乙； 第四章在第三章算法的基礎(chǔ)上，結(jié)合四級c l o s 交叉矩陣提出了種可以同時(shí)支持 單播和組播業(yè)務(wù)的路由算法；第5 章總結(jié)全文。 第2 章現(xiàn)有的路由算法研究 9 第2 章現(xiàn)有的路由算法研究 c l o s 交叉矩陣根據(jù)其阻塞特性可以分為三類，嚴(yán)格無阻塞、廣義無阻塞和可 重構(gòu)無阻塞。嚴(yán)格無阻塞和廣義無阻塞雖然可以消除交叉矩陣中的阻塞問題，但 是成本過高，因此一般應(yīng)用中均采用可重構(gòu)無阻塞交叉矩陣。在可重構(gòu)無阻塞交 叉矩陣中當(dāng)業(yè)務(wù)量較小時(shí)，c l o s 交叉矩陣可以滿足幾乎所有的請求，并可以建立 成功的所需輸入輸出連接，這時(shí)無需對已有連接進(jìn)行調(diào)整；但是在實(shí)際應(yīng)用中， 業(yè)務(wù)量是隨機(jī)的，很多時(shí)候會有突發(fā)的業(yè)務(wù)到來，這時(shí)就會引起交叉矩陣的阻塞， 使得業(yè)務(wù)無法建立，于是需要對現(xiàn)有的連接進(jìn)調(diào)整，即重構(gòu)，使得所需要的連接 能夠建立成功。本章主要討論可重構(gòu)無阻塞條件下的路由算法。 在交叉矩陣中的組播業(yè)務(wù)根據(jù)目的節(jié)點(diǎn)數(shù)目的不同，可以分為單播、組播和 廣播三種類型，單播是指待轉(zhuǎn)發(fā)的消息在傳送網(wǎng)中要求實(shí)現(xiàn)點(diǎn)對點(diǎn)的傳輸；廣播 業(yè)務(wù)是指在傳送網(wǎng)中把待轉(zhuǎn)發(fā)的一個(gè)消息從源節(jié)點(diǎn)轉(zhuǎn)發(fā)到傳送網(wǎng)的全部輸出端口 上，而組播業(yè)務(wù)是則把消息轉(zhuǎn)發(fā)到傳送網(wǎng)中的一組輸出端口上。故從廣義上來講， 單播和廣播是組播的一個(gè)特例。雖然單播業(yè)務(wù)可以理解為組播業(yè)務(wù)的一個(gè)特例， 但是在路由算法的設(shè)計(jì)和性能上還是有很大的區(qū)別，因此根據(jù)處理的業(yè)務(wù)的不同 可以將算法分為單播算法和組播算法，其中組播業(yè)務(wù)包括廣播業(yè)務(wù)。下面就分別 對不同的算法進(jìn)行介紹。 2 1 單播路由算法分析 c l o s 交叉矩陣中的單播路由算法主要解決在輸入和輸出模塊確定時(shí)中間模塊 的分配及調(diào)整的問題，因此在路由時(shí)都是以模塊為路由單位，將輸入端口和輸出 端口的編號映射成模塊編號進(jìn)行處理。如表2 1 為一個(gè)c ( 3 ，3 ，4 ) 的一個(gè)可重構(gòu)無阻 塞c l o s 交叉矩陣的請求輸入輸出端口表示，表2 2 為對應(yīng)的模塊表示。具體連接 關(guān)系見圖2 1 ，在以下的所有的路由算法中，如果沒有特殊說明，均采用模塊對來 表示交叉矩陣中的請求鏈路。 表2 1 端口表示 表2 2 模塊表示 1 0 c l o s 交叉矩陣中的路由算法研究 圖2 1 交叉矩陣路由分配圖 根據(jù)路由算法對新到的請求的處理方式不同可分為一次統(tǒng)一調(diào)整和逐條調(diào)整 法兩大類。一次統(tǒng)一調(diào)整是將已建立的請求和新到的請求進(jìn)行統(tǒng)一處理，進(jìn)行一 次全網(wǎng)的輸入輸出匹配。具體算法有： 1 多步分解法； 2 矩陣分解法； 3 二部圖的最大匹配與著色； 逐條調(diào)整算法則是對于每一條新到的請求分配，如果沒有空閑的中間模塊供 分配，則按照一定的規(guī)則將已建立的連接進(jìn)行調(diào)整，以釋放出空閑的中間模塊， 來建立新的連接。最經(jīng)典的為p a u l l 算法，以及以此為基礎(chǔ)的一些改進(jìn)算法。以下 將分別對這些算法進(jìn)行分析對比。 2 1 1 一次統(tǒng)一調(diào)整算法 1 多步分解法 多步分解法是基于c l o s 交叉矩陣可重構(gòu)證明理論( h a l l 定理) 的一種算法， 因此首先給出h a l l 定理，然后說明h a l l 定理在c l o s 交叉矩陣可重構(gòu)的證明中的應(yīng) 用。 h a l l 定理： 對于集合a 的r 個(gè)子集a 卜a 2 、，a r ，存在r 個(gè)不同的相異元素，a l 、a 2 、 a r ，滿足a i e a i 及i j 時(shí)啦碼的充分必要條件是a l ，a 2 ，a r 中任意k 個(gè)子集的 并集有至少k 個(gè)元素，其中1 k r 。 證明： 在c l o s 交叉矩陣中以輸出模塊為集合a ，每個(gè)輸入模塊所對應(yīng)的輸出模塊為 第2 章現(xiàn)有的路由算法研究 一個(gè)子集，應(yīng)用以上定理可以在每個(gè)子集中找出一個(gè)相異元素，由這些相異元素 組成一個(gè)相異代表系s d r ( s y s t e md i s t i n c tr e s p r e s e n t a t i v e ) ，由于這些相異元素屬于 不同的子集，即不同的輸入模塊，同時(shí)它們又各不相同，即屬于不同的輸出模塊， 因此可以給這些請求分配一個(gè)中間模塊。同樣在剩下的元素同樣滿足h a l l 定理， 因此進(jìn)行n 1 次分配就可以完成交叉矩陣中的所有請求的路由。如圖2 2 所示為一 相異代表系分配的中間模塊。 i n p u ts t a g e m i d d l es t a g e o u t p u ts t a g e 圖2 2 中間模塊分配圖 m h a l l 給出了一個(gè)求s d r 的算法，由于所討論的問題已經(jīng)證明符合h a l l 定理， 因此只討論相異代表系一定存在時(shí)的情況田】。算法的具體實(shí)現(xiàn)如下： 設(shè)有元素集合s l ，一，s n ，用集合d 表示相異代表系并置為為空；從集合s i 任意 選取一個(gè)元素a i ，如果a i 與集合d 中的元素不沖突，則將該元素置入集合d 中， 繼續(xù)搜索下一個(gè)集合s i + l ；如果到集合s ，時(shí)無法找到一個(gè)元素不于集合d 中已有 的元素沖突，那么意味著集合s ，中的元素b l ，“，b t ，已經(jīng)包含在了相異代表系中， 這樣就必須對現(xiàn)有的相異代表系進(jìn)行調(diào)整，如果將b 1 ，“，b t 作為一個(gè)有序列表，并 記為t l ，那么第二個(gè)列表t 2 就由t l 加上以b 1 為代表元素的集合中不屬于序列t l 的元素組成表示為b b , b t ，k l ，”，b 。；如果用s ( b i ) 表示以b i 為代表元素的集合，那 么依次類推可以用列表t i 加上s ( b i ) 中沒有添加到列表t i 中的元素構(gòu)造出列表t i + l ； 如果在列表瓦中找到一個(gè)元素b u ，它不是任何集合的代表元素，也不屬于列表t l ， 但是屬于集合s ( k ) 中的元素，并且不在列表k l 中，這里t 1 2 要滿足條件u 2 u ， 如果k 屬于列表t l ，那么就用b u 作為集合s ( k ) 中的代表元素，用屯作為集合s r 的代表元素；如果k 不屬于列表t l ，那么k 必然屬于集合s ( k ) ，并且滿足u 3 a ( a ) 交叉矩陣狀態(tài)( b ) 矩