光網(wǎng)絡(luò)中資源分配算法的研究.pdf

1、全光網(wǎng)絡(luò)可以在光上直接進(jìn)行交換和路由,突破了傳統(tǒng)光網(wǎng)絡(luò)需要進(jìn)行光電轉(zhuǎn)換的瓶頸。同時(shí)光網(wǎng)絡(luò)中的資源分配問題也由傳統(tǒng)的光硬件資源分配問題擴(kuò)展到路由和波長(zhǎng)資源的分配問題。靜態(tài)路由和波長(zhǎng)分配問題是在全光網(wǎng)絡(luò)中,針對(duì)靜態(tài)業(yè)務(wù)請(qǐng)求提出的路由和波長(zhǎng)資源分配的問題。 在光網(wǎng)絡(luò)中進(jìn)行路由時(shí),單個(gè)鏈路或者節(jié)點(diǎn)損壞都會(huì)引起整條光通路失效。保護(hù)機(jī)制可以使得光網(wǎng)絡(luò)在發(fā)生故障時(shí)及時(shí)切換到備用系統(tǒng),確保網(wǎng)絡(luò)信息順利的傳輸。求解靜態(tài)路由和波長(zhǎng)分配問題時(shí),本文選

2、取基于通路的保護(hù)機(jī)制。此外為了節(jié)省網(wǎng)絡(luò)資源,多個(gè)低速業(yè)務(wù)可以利用業(yè)務(wù)疏導(dǎo)機(jī)制匯聚到一個(gè)高速波長(zhǎng)上傳輸。由于低速業(yè)務(wù)的綁定方式將影響業(yè)務(wù)請(qǐng)求的路由和波長(zhǎng)分配,因此本文研究了路由和波長(zhǎng)分配問題中的業(yè)務(wù)疏導(dǎo)問題。 解決靜態(tài)路由和波長(zhǎng)問題的方法有建立ILP模型求解和啟發(fā)式算法。啟發(fā)式算法可以得到資源分配問題的近似解,求解時(shí)間較短。但是啟發(fā)式算法得到不是最優(yōu)解,而且當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)算法的性能無法判定。 本文的第二章建立了靜態(tài)路由和

3、波長(zhǎng)分配問題的保護(hù)和業(yè)務(wù)疏導(dǎo)ILP模型,同時(shí)針對(duì)大規(guī)模網(wǎng)絡(luò)的路由和波長(zhǎng)分配問題提出了不同的分解機(jī)制。本文利用拉格朗日松弛算法、Primal和Dual分解算法對(duì)大規(guī)模網(wǎng)絡(luò)的ILP模型進(jìn)行了分解求解。利用計(jì)算機(jī)軟件測(cè)試表明,求解ILP模型可以得到資源分配的最優(yōu)解。但是該問題是NP-C問題,在網(wǎng)絡(luò)規(guī)模較大時(shí)求解時(shí)間較長(zhǎng),甚至無法得到可行解。利用數(shù)學(xué)分解的方法對(duì)ILP模型進(jìn)行分解后求解,可以降低減問題的規(guī)模,模塊化解決問題。理論上數(shù)學(xué)分解方法可

4、以得到和原模型相同的最優(yōu)解。測(cè)試表明經(jīng)過有限次迭代,分解算法可以得到接近原模型最優(yōu)解的可行解且求解時(shí)間較短。 光多播利用分光節(jié)點(diǎn)完成光信號(hào)的復(fù)制和轉(zhuǎn)發(fā),減少了光網(wǎng)絡(luò)的資源消耗。由于分光節(jié)點(diǎn)代價(jià)比較昂貴,在光網(wǎng)絡(luò)中只有一部分節(jié)點(diǎn)可以配置成為分光節(jié)點(diǎn)。在有限的分光節(jié)點(diǎn)條件下,優(yōu)化分光節(jié)點(diǎn)配置,使用最少的網(wǎng)絡(luò)資源完成業(yè)務(wù)請(qǐng)求的問題,稱為分光節(jié)點(diǎn)配置問題。本文的第三章在靜態(tài)的業(yè)務(wù)請(qǐng)求下分別提出了解決分光節(jié)點(diǎn)配置問題的ILP模型和MF啟發(fā)

5、式算法。文中搭建計(jì)算機(jī)仿真平臺(tái)驗(yàn)證了,ILP模型可以得到最優(yōu)解,但是求解時(shí)間較長(zhǎng),在網(wǎng)絡(luò)規(guī)模較大時(shí)無法得到可行解。MF算法不依賴于多播樹的建立算法,可以得到接近最優(yōu)解的近似解,求解時(shí)間較短。第四章針對(duì)可預(yù)測(cè)的動(dòng)態(tài)變化的業(yè)務(wù)請(qǐng)求,提出了分光節(jié)點(diǎn)的魯棒配置算法。文中的測(cè)試驗(yàn)證了,利用魯棒算法配置分光節(jié)點(diǎn),與靜態(tài)算法相比可以使網(wǎng)絡(luò)資源的消耗在各種業(yè)務(wù)請(qǐng)求情況下都相對(duì)較優(yōu),穩(wěn)定性好,總的資源消耗少,更符合實(shí)際的網(wǎng)絡(luò)狀況。第五章對(duì)全文進(jìn)行了總結(jié)和