蟻群算法在 obs rwa中的應(yīng)用

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

2、突發(fā)，宿結(jié)點(diǎn)向源結(jié)點(diǎn)發(fā)送一個(gè)ACK，ACK按原路返回。結(jié)點(diǎn)利用ACK統(tǒng)計(jì)途經(jīng)其輸出鏈路到達(dá)某一宿結(jié)點(diǎn)的發(fā)送成功概率，并以此作為經(jīng)過該鏈路到此宿結(jié)點(diǎn)的“氣味權(quán)值”，當(dāng)新的突發(fā)到達(dá)時(shí)，按照輸出鏈路上的氣味權(quán)值，實(shí)時(shí)為突發(fā)選擇輸出鏈路和波長。仿真表明，與現(xiàn)有的RWA算法相比，本文算法可以自適應(yīng)的發(fā)現(xiàn)最佳路由，平衡鏈路負(fù)載，減小突發(fā)阻塞概率。關(guān)鍵詞：關(guān)鍵詞：光突發(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引言引言隨著全球范圍內(nèi)IP業(yè)務(wù)的迅猛增長，對(duì)傳送網(wǎng)帶寬和交換系統(tǒng)容量的需求正以前所未有的速度增加?，F(xiàn)有的DWDM技術(shù)可以使一根光纖上可利用的帶寬達(dá)到10Tbits左右可以滿足較長時(shí)期內(nèi)對(duì)傳送網(wǎng)帶寬的要求[1]。光分組交換（Opti

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

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

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

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

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