WDM網(wǎng)絡(luò)及IP網(wǎng)絡(luò)中的多播算法研究.pdf

1、多播傳輸能有效節(jié)約帶寬資源,并具有高效、靈活、可控等諸多優(yōu)點(diǎn),是實(shí)現(xiàn)多媒體應(yīng)用的重要方法。近年來(lái),光網(wǎng)絡(luò)的迅速普及,WDM(Wavelength DivisionMultiplexing)網(wǎng)絡(luò)成為未來(lái)Internet骨干支撐網(wǎng)的首選。隨著光學(xué)技術(shù)日益成熟,原來(lái)需要在業(yè)務(wù)交換層面完成的多播業(yè)務(wù)被移植到了光層,光網(wǎng)絡(luò)多播技術(shù)正是近年來(lái)廣受關(guān)注的熱點(diǎn)之一。本文主要研究了WDM網(wǎng)絡(luò)和IP網(wǎng)絡(luò)中的多播算法,針對(duì)以下三方面的問(wèn)題進(jìn)行了深入研究:WD

2、M網(wǎng)絡(luò)中的多播保護(hù)算法,OBS網(wǎng)絡(luò)中多播匯聚機(jī)制以及基于網(wǎng)絡(luò)編碼的多播業(yè)務(wù)靜態(tài)規(guī)劃算法。 WDM技術(shù)可以大大提高鏈路的傳輸容量,同時(shí)也使網(wǎng)絡(luò)部件失效時(shí)可能遭受比傳統(tǒng)網(wǎng)絡(luò)更大的損失,網(wǎng)絡(luò)的生存性問(wèn)題日漸突出,WDM網(wǎng)絡(luò)中多播保護(hù)問(wèn)題受到了廣泛的關(guān)注。本文第二章首先對(duì)現(xiàn)有的啟發(fā)式保護(hù)算法進(jìn)行分析,發(fā)現(xiàn)大多數(shù)啟發(fā)式算法沒(méi)有考慮工作樹(shù)與保護(hù)樹(shù)之間的鏈路復(fù)用問(wèn)題,導(dǎo)致其帶寬利用率低,阻塞率高；然后通過(guò)數(shù)學(xué)模型描述了針對(duì)單鏈路失效情況下的多

3、播保護(hù)樹(shù)；再提出了兩種基于路徑分離的改進(jìn)啟發(fā)式算法。這兩種改進(jìn)算法分別從不同的角度描述了工作樹(shù)與保護(hù)樹(shù)之間的相互影響關(guān)系,再由此確定了路由過(guò)程中的冗余鏈路,并分別根據(jù)冗余邊的特點(diǎn)設(shè)計(jì)路由算法,減少多播保護(hù)的資源消耗。 光突發(fā)交換(OBS, Optical Burst Switching)作為一種IP-over-WDM的光交換技術(shù),結(jié)合了波長(zhǎng)路由交換和光分組交換的優(yōu)點(diǎn),同時(shí)也克服了二者的不足,能提高帶寬利用率、減少波長(zhǎng)資源消耗,降

4、低業(yè)務(wù)阻塞率,對(duì)OBS網(wǎng)絡(luò)中的多播實(shí)現(xiàn)方式的研究具有現(xiàn)實(shí)意義。本文第三章提出一種基于稀疏分光配置的OBS網(wǎng)絡(luò)的共享多播機(jī)制。該機(jī)制對(duì)包含相同分光節(jié)點(diǎn)的業(yè)務(wù)進(jìn)行匯聚,并且在資源預(yù)約過(guò)程中引入了優(yōu)先級(jí)來(lái)區(qū)分主干鏈路和分枝鏈路,保證多播樹(shù)的主干鏈路能優(yōu)先搶占資源。相比傳統(tǒng)多播機(jī)制,該方式的多播樹(shù)匯聚算法的冗余度更低,且能減少多播業(yè)務(wù)的丟包率和冗余包的數(shù)量,提高資源利用率。 本文最后研究了口網(wǎng)絡(luò)中基于網(wǎng)絡(luò)編碼的多播業(yè)務(wù)靜態(tài)規(guī)劃問(wèn)題。網(wǎng)絡(luò)

5、編碼是近年來(lái)IP網(wǎng)絡(luò)中的研究熱點(diǎn),通過(guò)中間節(jié)點(diǎn)對(duì)傳輸數(shù)據(jù)編碼的方式實(shí)現(xiàn)多播最大流傳輸。使用網(wǎng)絡(luò)編碼可以在很大程度上提高網(wǎng)絡(luò)吞吐量,但是不可避免地會(huì)增加網(wǎng)絡(luò)的復(fù)雜性?，F(xiàn)有的啟發(fā)式路由算法通常只能為單個(gè)多播業(yè)務(wù)尋找最優(yōu)路由,無(wú)法優(yōu)化網(wǎng)絡(luò)的整體吞吐量；而用普通整數(shù)線(xiàn)性規(guī)劃(ILP, Integer LinearProgramming)模型描述網(wǎng)絡(luò)編碼業(yè)務(wù),通常會(huì)因?yàn)榫W(wǎng)絡(luò)編碼業(yè)務(wù)的多播圖復(fù)雜,導(dǎo)致問(wèn)題規(guī)模變大,求解困難。運(yùn)用column gen

6、eration算法解決靜態(tài)業(yè)務(wù)規(guī)劃問(wèn)題,對(duì)多個(gè)約束條件進(jìn)行拉格朗日松弛,再為松弛系數(shù)賦予具體的物理含義,使系數(shù)之間存在相互關(guān)聯(lián)關(guān)系,并根據(jù)物理含義進(jìn)行路徑更新。與啟發(fā)式算法相比,column generation從整體上提高了網(wǎng)絡(luò)的吞吐量,改善了網(wǎng)絡(luò)的負(fù)載均衡。同時(shí),與普通ILP規(guī)劃算法相比,column generation的路徑更新更有針對(duì)性,無(wú)需計(jì)算大量備選路徑,問(wèn)題規(guī)模小,收斂速度更快,且能夠解決部分ILP無(wú)法處理的大規(guī)模規(guī)劃問(wèn)