蟻群算法在 obs rwa中的應用

1、蟻群算法在蟻群算法在OBSRWA中的應用中的應用于挺進，張奭，張冰（西安電子科技大學ISN國家重點實驗室，西安710071）摘要：要：光突發(fā)交換（OBS）以一步占用方式為突發(fā)建立端到端的全光連接?，F(xiàn)有的RWA算法通常以源宿結點對間最短路徑作為突發(fā)的路由，沿路逐跳進行波長分配。在非對稱的網(wǎng)絡中，或網(wǎng)絡業(yè)務流量非均勻分布時，會造成鏈路負載不均衡，加大突發(fā)沖突概率。本文基于蟻群思想，提出了一種OBS網(wǎng)絡中分布式RWA算法。對于每一個成功接收的

2、突發(fā)，宿結點向源結點發(fā)送一個ACK，ACK按原路返回。結點利用ACK統(tǒng)計途經(jīng)其輸出鏈路到達某一宿結點的發(fā)送成功概率，并以此作為經(jīng)過該鏈路到此宿結點的“氣味權值”，當新的突發(fā)到達時，按照輸出鏈路上的氣味權值，實時為突發(fā)選擇輸出鏈路和波長。仿真表明，與現(xiàn)有的RWA算法相比，本文算法可以自適應的發(fā)現(xiàn)最佳路由，平衡鏈路負載，減小突發(fā)阻塞概率。關鍵詞：關鍵詞：光突發(fā)交換蟻群算法路由波長分配AntalgithminOBSRWATingJinYuSh

3、iZhangBingZhang(StateKeyLabofISNXiDianUniversityXi’an710071)Abstract:OBSusesonewayreservationprotocoltosetupendtoendallopticalconnections.ThecurrentRWAalgithmsusuallyusetheshtestpathbetweensourcedestinationpairastheroute

4、wavelengthsareassignedhopbyhop.Inanunsymmetricalloadwithunbalanceddistributionwkthisalgithmwillresultlargerprobabilityofloss.InthispaperweproposeadynamicdistributedOBSRWAalgithmenlightenedbyantcolony.Thedestinationnodesf

5、eedACKsbackfeachsuccessfullyreceivedburstcontrolpacket(BCP)usedfresourcereservation.TheACKsarefeedbackalongthesamepathastheonethroughwhichBCPsarefwarded.Ineachnodethesuccesssendingprobabilityfeachsourcedestinationpairisc

6、alculatedbyrecdingthenumberofACKsTheprobabilitiesareregardedasthe“pheromone”oftheoutputlinks.FtheincomingBCPsthenodewillchoosetheoutputlinkbasedonthe“pheromone”.NumericalresultsobtainedfromsimulationshowthatourRWAalgithm

7、canfindtheoptimalroutesadaptivelygetabetterburstblockprobabilityperfmancecomparedwithcurrentRWAalgithms.1引言引言隨著全球范圍內IP業(yè)務的迅猛增長，對傳送網(wǎng)帶寬和交換系統(tǒng)容量的需求正以前所未有的速度增加?，F(xiàn)有的DWDM技術可以使一根光纖上可利用的帶寬達到10Tbits左右可以滿足較長時期內對傳送網(wǎng)帶寬的要求[1]。光分組交換（Opti

8、calPacketSwitching，OPS）是全光網(wǎng)絡的發(fā)展方向。但OPS存在著兩個主要問題：一是沒有合適的光緩存器。目前的實驗系統(tǒng)中采用的光纖延遲線（FiberDelayLineFDL）往往比較笨重，不靈活。1km光纖只能對光信號延遲5us存儲深度有限；二是在OPS交換節(jié)點處的多輸入分組精確同步難以實現(xiàn)。因此，光分組交換的商業(yè)應用前景短時期內并不被看好。光突發(fā)交換（OpticalBurstSwitching，OBS）[2]是近期光通

9、信領域的研究熱點之一，它是基于電路交換的波長路由和光分組交換的有效折中。它的交換粒度介于波長路由和光分組交換之間，帶寬利用率高于波長路由交換，并且比光分組交換易于實現(xiàn)，是很有前途的光交換技術。路由及波長分配（RouteWavelengthAssignmentRWA）是OBS網(wǎng)絡中需要解決的關鍵問題之一。由于OBS網(wǎng)絡采用一步占用（onewayreservation）[2]的方式為突發(fā)分配路由和波長，源節(jié)點不必等待光路建立的確認就可以發(fā)送

10、突發(fā)，具有很大的盲目性，并且由于業(yè)務的突發(fā)性，使得鏈路狀態(tài)變化頻繁，上游結點無法實時掌握下游鏈路的波長占用狀態(tài)，更一步加劇了突發(fā)沖突的概率。選擇合理的RWA算法，成為減小突發(fā)沖突概率的關鍵。蟻群算法是受仿生學上蟻群尋路的啟迪而產(chǎn)生的一種新型模擬進化算法，它具有分布式、正反饋、全局收斂等優(yōu)點。借鑒蟻群算法，本文提出了一種基于蟻群算法的OBSRWA算法（以下簡稱蟻群算法）。經(jīng)過仿真驗證，本文算法與現(xiàn)有的RWA算法相比各方面性能均有很大提高。

11、本文第二節(jié)介紹現(xiàn)有的一些OBSRWA算法；第三節(jié)簡要地介紹仿生學中的蟻群算法；第四節(jié)介紹本文提出的基于蟻群算法的OBSRWA算法；第五節(jié)給出仿真數(shù)據(jù)和分析；第六節(jié)給出結論及下一步工作。2現(xiàn)有現(xiàn)有OBS路由及波長分配算法路由及波長分配算法現(xiàn)有的OBS網(wǎng)絡中的RWA算法將路由和波長分配分成兩個獨立的子問題單獨考慮。路由算法采用靜態(tài)路由，即源宿對間的最短路徑作為突發(fā)傳送的路由。算法的優(yōu)點在于簡單，容易實現(xiàn)。缺點是：對于多個流的情況，如果流的路

12、由存在共用路由，共用路由有可能成為網(wǎng)絡中的瓶頸，造成大量突發(fā)沖突。我們舉例說明，用（sd）表示以s為源結點d為目的結點的源宿對，如圖1所示的非對稱魚型網(wǎng)絡，假設各個鏈路的時延相同，均為5ms。網(wǎng)絡中存在（n0n7）和（n1n8）兩個源宿對。（n0n7）間的突發(fā)將沿最短路徑，即n0→n2→n3→n6→n7傳輸；同理，（n1n8）間的突發(fā)將沿n1→n2→n3→n6→n8傳輸。此時，在兩個源宿對的共用路由n2→n3→n6上將重載，導致大量的突