路由和波長分配PPT課件

1、路由和波長分配1. 基本概念基本概念n路由和波長分配（Routing and Wavelength Assignment，RWA）問題是光網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中一個(gè)很重要的子問題n即在給定了網(wǎng)絡(luò)拓?fù)浜凸?jié)點(diǎn)間連接請求（光路/呼叫）的前提下，需要：1.為這些連接請求尋找源節(jié)點(diǎn)到目的節(jié)點(diǎn)間的路由路由2.為這些路由分配合適的波長波長 光通路、光路、 Light Path OXCOXCOXCOXCOXCOXCOXC連接請求Client Network AClient Network B入口節(jié)點(diǎn)出口節(jié)點(diǎn)光通路 (OXC)Light Path = route + wavelength網(wǎng)絡(luò)節(jié)點(diǎn)結(jié)構(gòu)網(wǎng)絡(luò)節(jié)點(diǎn)結(jié)構(gòu)OXCN

2、xNPhotonic Switch1NxNPhotonic Switch2NxNPhotonic Switch3NxNPhotonic Switchw.光纖123w123w123w123w光纖結(jié)構(gòu)之一：全波長轉(zhuǎn)換全波長轉(zhuǎn)換結(jié)構(gòu)之二：無波長轉(zhuǎn)換無波長轉(zhuǎn)換的光交叉連接設(shè)備，每個(gè)端口一根光纖，每根光纖復(fù)用個(gè)波長波長轉(zhuǎn)換波長轉(zhuǎn)換n此外還有：有限波長轉(zhuǎn)換有限波長轉(zhuǎn)換 波長變換器只能把輸入的部分波長轉(zhuǎn)換成輸出的部分波長，即波長轉(zhuǎn)換器的波長轉(zhuǎn)換范圍不能覆蓋整個(gè)復(fù)用波長集稀疏波長轉(zhuǎn)換稀疏波長轉(zhuǎn)換 只在部分節(jié)點(diǎn)配置了波長轉(zhuǎn)換器（可以是完全或部分波長轉(zhuǎn)化器） 光通道類型光通道類型n與有、無波長變化相對應(yīng)，光通道可

3、分為兩種類型：n波長通道波長通道（wavelength path，WP）n虛波長通道虛波長通道（virtual wavelength path，VWP）流量類型流量類型 n通常將網(wǎng)絡(luò)支持的業(yè)務(wù)分為以下兩類。n靜態(tài)流量業(yè)務(wù)靜態(tài)流量業(yè)務(wù)：事先給定一組光路連接請求，需要為這些請求尋找路由并在其路由上分配波長，以使網(wǎng)絡(luò)地性能達(dá)到最優(yōu)n動態(tài)流量業(yè)務(wù)動態(tài)流量業(yè)務(wù)：光路請求以滿足一定概率分布地方式到達(dá)和離開網(wǎng)絡(luò)，相應(yīng)的性能指標(biāo)通常是請求的阻塞率n按照所支持的業(yè)務(wù)類型劃分，可將RWA的問題分為靜態(tài)靜態(tài)RWA問題問題和動態(tài)動態(tài)RWA問題問題尋路和信令光網(wǎng)中的尋路OSPF-TE、ISIS-TE、或距離向量協(xié)議等源

4、選路(Source Routing)光網(wǎng)中的信令根據(jù)尋路結(jié)果來建立光通路（Light Path)CR-LDP，RSVP-TE等2. RWA問題簡介n傳統(tǒng)網(wǎng)絡(luò)中網(wǎng)絡(luò)尋路和資源分配問題IP網(wǎng)絡(luò)提供盡力而為盡力而為服務(wù)，只有尋路，沒有資源分配沒有資源分配ATM、Packet over SDH等網(wǎng)絡(luò)需要尋路，同時(shí)也有資源的分配問題，但是資源的分配不具有全局重要性不具有全局重要性nWDM網(wǎng)絡(luò)中的波長一致性條件波長一致性條件要求從入口到出口使用同一個(gè)波長入口到出口使用同一個(gè)波長波長分配具有全局重要性全局重要性合適地選擇波長，可以使：所需波長數(shù)目最小、網(wǎng)絡(luò)吞吐率最大，或連接請求阻塞率最小連接請求阻塞示例OX

5、C-aOXC-cOXC-dOXC-bOXC-eOXC-gOXC-f11連接請求1(a-g)連接請求2(c-g)請求被組塞波長重用波長重用格形網(wǎng)絡(luò)拓?fù)湓诓煌逆溌房梢詫?shí)現(xiàn)波長重用在不同的鏈路可以實(shí)現(xiàn)波長重用節(jié)點(diǎn)執(zhí)行波長信道的交換波長連續(xù)性限制波長連續(xù)性限制當(dāng)輸入端有兩個(gè)波長相同的信道需要交換到同一根輸出光纖時(shí)，會發(fā)生阻塞此時(shí)加入波長變換器波長變換器可以消除這種沖突，增加波長重用的靈活性3. 路由選擇算法路由選擇算法 n路由選擇算法一般是基于一定的優(yōu)化目標(biāo)（如路徑最短路由、負(fù)載均衡等）為連接請求決定最佳路由n路由的計(jì)算既可采用離線離線方式，也可采用實(shí)時(shí)實(shí)時(shí)計(jì)算的方式n目前常見的路由算法有以下四種：

6、 A. 固定路由（固定路由（Fixed Routing，F(xiàn)R）n這是最簡單的路由方法，即采用最短路算法（如Dijkstras 算法）為網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)對之間預(yù)先計(jì)算一條路由，路由選好后固定不變n當(dāng)源、宿節(jié)點(diǎn)對之間的連接請求到達(dá)時(shí)，在預(yù)先計(jì)算好的路由上為連接請求分配波長，從而建立光連接n如圖，節(jié)點(diǎn)0到節(jié)點(diǎn)2的最短路由為012n最短路徑算法的缺點(diǎn)是有時(shí)會使網(wǎng)絡(luò)中某些鏈路過于擁擠；改進(jìn)的方法是采用負(fù)載均衡負(fù)載均衡選路 B. 備選路由（備選路由（Alternate Routing，AR）n這種方法預(yù)先為網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)對之間預(yù)先計(jì)算多條路由，并按照路由長度從短到長排列，構(gòu)成備選備選路由集路由集n當(dāng)

7、源、宿節(jié)點(diǎn)對之間的連接請求到達(dá)時(shí)，首選選擇其相應(yīng)路由表中的第一條路由分配波長n如果沒有找到可用波長，再選擇第二條路由進(jìn)行嘗試，直到成功建立光路為止 n如圖所示，節(jié)點(diǎn)0到節(jié)點(diǎn)2首選路由首選路由和備用路由備用路由分別為012和0542n與固定路由法相比，連接被阻塞的概率顯著減小C. 自適應(yīng)動態(tài)路由（自適應(yīng)動態(tài)路由（Adaptive Dynamic Routing，ADR）n這種方法根據(jù)網(wǎng)絡(luò)狀態(tài)實(shí)時(shí)進(jìn)行選路實(shí)時(shí)進(jìn)行選路 n如圖所示，節(jié)點(diǎn)0和節(jié)點(diǎn)2之間的自適應(yīng)路由為05432ADRn這種路由方案能根據(jù)網(wǎng)絡(luò)當(dāng)前的狀態(tài)和資源使用情況來計(jì)算路由，所以在提高網(wǎng)絡(luò)資源利用率和降低網(wǎng)絡(luò)阻塞率方面優(yōu)于前兩種路由方案

8、優(yōu)于前兩種路由方案n但這種方案需要光網(wǎng)絡(luò)控制和管理平面提供網(wǎng)絡(luò)狀態(tài)狀態(tài)信息信息，網(wǎng)絡(luò)節(jié)點(diǎn)之間還有不斷交換鏈路狀態(tài)信息，所以實(shí)現(xiàn)起來較復(fù)雜較復(fù)雜n而且RWA算法的運(yùn)行速度不及路由預(yù)計(jì)算的方式 路由算法比較nFR方法可以節(jié)省業(yè)務(wù)到達(dá)時(shí)由于實(shí)時(shí)計(jì)算路由所花費(fèi)的時(shí)間，從而提高RWA 算法的運(yùn)行速度，但這樣得到的路由往往不是當(dāng)前網(wǎng)絡(luò)狀態(tài)下的最佳路由nADR方式可以克服離線路由計(jì)算的不足，但付出的代價(jià)就是導(dǎo)致RWA 算法的運(yùn)行速度降低n為了兼顧預(yù)計(jì)算在時(shí)間上的優(yōu)勢和實(shí)時(shí)計(jì)算在優(yōu)化路由選擇上的優(yōu)勢，可以在采用預(yù)計(jì)算時(shí)計(jì)算多條候選路由，在連接請求到達(dá)時(shí)根據(jù)網(wǎng)絡(luò)狀態(tài)選用其中最佳的路由，AR就屬于此類算法4. 波

9、長分配算法波長分配算法 1.隨機(jī)分配（Random Assignment，RA）法2.首次命中（First Fit，F(xiàn)F）法3.最大使用（Most-Used，MU）法4.最少使用（ Least-Used，LU）法5.最小乘積（ Min-Product，MP）法6.最輕承載（Lest-Loaded，LL）法7.最大和法（MAX-SUM）8.相對容量損失法（RCL）1）隨機(jī)分配（）隨機(jī)分配（Random Assignment，RA） n首先搜索所有可用波長的集合，找出路由可用的波長子集n再從中隨機(jī)選取波長分配給光通道隨機(jī)選取波長分配給光通道n這種算法簡單，不必知道全網(wǎng)的狀態(tài)信息2）首次命中（）首次

10、命中（First Fit，F(xiàn)F）法）法n這種方法將所有的波長按一定的規(guī)則進(jìn)行編號，按編號從小到達(dá)的順序搜索可用波長n找到的第一個(gè)可用波長即被分配給光路找到的第一個(gè)可用波長即被分配給光路n與RA相比，F(xiàn)F不必搜索全部可用波長，找到一個(gè)可用波長就停止，因此計(jì)算量較小3）最大使用（）最大使用（Most-Used，MU）法）法n這種方法的基本思想是，將網(wǎng)絡(luò)流量集中在少數(shù)將網(wǎng)絡(luò)流量集中在少數(shù)波長上波長上，即通過統(tǒng)計(jì)當(dāng)前波長的占用情況，優(yōu)先優(yōu)先選取被最多鏈路占用的波長選取被最多鏈路占用的波長n這樣，后續(xù)光通道就有更多的可選波長。n有關(guān)研究表明該方法的效率明顯優(yōu)于前兩種 4）最少使用（）最少使用（ Leas

11、t-Used，LU）法）法n這種方法根據(jù)波長被占用情況的統(tǒng)計(jì)，優(yōu)先選取被最優(yōu)先選取被最少鏈路占用的波長少鏈路占用的波長n這種算法的出發(fā)點(diǎn)是使得網(wǎng)絡(luò)流量更均勻的分?jǐn)偟礁鱾€(gè)波長上，即波長的負(fù)載均衡負(fù)載均衡n但LU下，較長的光通道往往被拆開較長的光通道往往被拆開，只有較短的光通道容易保持波長一致性5）最小乘積（）最小乘積（ Min-Product，MP）法）法n這種方法是一種適用于多纖多纖光網(wǎng)絡(luò)的算法 n它先給所有波長編號，對于每個(gè)波長j，計(jì)算 ，其中Dlj表示鏈路l上的波長j已被占用的光纖數(shù)，(p)表示光通道p所經(jīng)過的鏈路集合n優(yōu)先選擇能使乘積項(xiàng)最小且編號較低的波長優(yōu)先選擇能使乘積項(xiàng)最小且編號較低

12、的波長n當(dāng)每條鏈路的光纖數(shù)是1時(shí)，MP就退化為FF( )ljlpD6）最輕承載（）最輕承載（Lest-Loaded，LL）法）法n這也是一種適用于多纖多纖光網(wǎng)絡(luò)的算法n它首先計(jì)算 ，其中Sp表示光通道p上空閑波長集合，Ml指鏈路l上的光纖數(shù)n優(yōu)先選擇滿足上式且編號較小的波長優(yōu)先選擇滿足上式且編號較小的波長nLL算法的出發(fā)點(diǎn)是將最空閑的波長優(yōu)先分配給最將最空閑的波長優(yōu)先分配給最繁忙的鏈路繁忙的鏈路，它的效果比MU法好 ()maxmin()lljlpj SpMD7）最大和法（）最大和法（MAX-SUM）n既可用于單纖單纖網(wǎng)絡(luò)又可用于多纖多纖網(wǎng)絡(luò)的算法n它首先計(jì)算波長j在鏈路l上的空閑容量（定義為鏈

13、路l上的光纖總數(shù)減去鏈路l上占用波長j的光纖總數(shù)），然后優(yōu)先選擇能使空閑容量最大的那個(gè)波長進(jìn)行波長分配n該算法考慮了資源分配對整個(gè)網(wǎng)絡(luò)的影響，而不僅僅是對所選路由和波長的影響，因而能夠獲得較好的性能。該算法適用于靜態(tài)波長靜態(tài)波長分配問題 8）相對容量損失法（）相對容量損失法（RCL）n這種方法類似于MAX-SUMnMAX-SUM法致力于將絕對絕對空閑容量最大化n而RCL法則致力于將相對相對空閑容量最大化n它們都適用于流量非標(biāo)準(zhǔn)的網(wǎng)絡(luò)，其中RCL的性能稍好 分析分析n總體來說，波長分配方法所考慮的網(wǎng)絡(luò)狀態(tài)（如波長使用率、波長在網(wǎng)絡(luò)鏈路上的空閑容量等）越全面，則波長分配方法對網(wǎng)絡(luò)資源優(yōu)化率越高n但

14、這樣的波長分配方法的復(fù)雜度復(fù)雜度也越高n因此，為了在兼顧RWA算法性能的基礎(chǔ)上盡量降低算法的復(fù)雜度，目前大量研究在解決波長分配問題時(shí)都使用了FF或RA波長分配方法 5. 靜態(tài)靜態(tài)RWA問題問題 n靜態(tài)RWA問題又稱為靜態(tài)光路建立靜態(tài)光路建立（Static Lightpath Establishment, SLE）問題，即預(yù)先給出多條光路連接需求，計(jì)算路由和分配波長n這種計(jì)算可以是離線（off line）的，即不需在線（on line）的實(shí)時(shí)計(jì)算n靜態(tài)RWA問題所考慮的是，如何從全局優(yōu)化的角度來如何從全局優(yōu)化的角度來為所有光路連接需求建立光路為所有光路連接需求建立光路靜態(tài)靜態(tài)RWA問題問題n常用

15、的優(yōu)化準(zhǔn)則有兩種：常用的優(yōu)化準(zhǔn)則有兩種： 1.在滿足所有連接請求的前提下，使用最少的波長數(shù)或光纖數(shù)2.在波長/光纖數(shù)目給定的前提下，滿足盡可能多的連接請求靜態(tài)靜態(tài)RWA問題問題nRWA問題中涉及到了虛拓?fù)涮撏負(fù)洌╒irtual Topology）n虛拓?fù)涮撏負(fù)涫侵附鉀Q靜態(tài)RWA問題后，所有光路構(gòu)成的邏輯上的網(wǎng)絡(luò)拓?fù)?，也稱為WDM光傳送網(wǎng)的邏輯拓?fù)溥壿嬐負(fù)洌↙ogical Topology）n虛拓?fù)渲械墓?jié)點(diǎn)就是網(wǎng)絡(luò)物理拓?fù)涞墓?jié)點(diǎn)，這些節(jié)點(diǎn)通過建立的光路光路連接起來靜態(tài)靜態(tài)RWA問題問題n按照虛拓?fù)渌С值纳蠈訕I(yè)務(wù)種類的不同上層業(yè)務(wù)種類的不同，可以將靜態(tài)RWA問題分為兩類：1.支持電路交換業(yè)務(wù)的靜

16、態(tài)支持電路交換業(yè)務(wù)的靜態(tài)RWA算法算法2.支持分組交換業(yè)務(wù)的虛拓?fù)湓O(shè)計(jì)支持分組交換業(yè)務(wù)的虛拓?fù)湓O(shè)計(jì)n前者的業(yè)務(wù)請求矩陣給出了每個(gè)節(jié)點(diǎn)對間需要支持的光路數(shù)光路數(shù)n而后者的業(yè)務(wù)請求矩陣中存放的是節(jié)點(diǎn)對之間歸一化的平均分組業(yè)務(wù)強(qiáng)度平均分組業(yè)務(wù)強(qiáng)度1）支持電路交換業(yè)務(wù)的靜態(tài)）支持電路交換業(yè)務(wù)的靜態(tài)RWA算法算法 n靜態(tài)RWA可通過整數(shù)線性規(guī)劃（Integer Linear Programming，ILP）方法求解n但I(xiàn)LP求解復(fù)雜度隨著網(wǎng)絡(luò)規(guī)模的增大而急劇增加n因此，一般可以把將靜態(tài)RWA問題拆成選路子問題選路子問題和波長分配子問題波長分配子問題，分成兩步解決n第一步，為每條光路建立請求選擇路由n選取

17、了路由之后，第二步就是分配波長 路由選擇路由選擇n路由選擇方法通常采用FR或ARn由于FR通常采用的路由是最短路由，即光路經(jīng)過的物理鏈路跳數(shù)或代價(jià)總和最小，因此此時(shí)波長分配方法對網(wǎng)絡(luò)性能有很大影響n在采用AR時(shí)，需要預(yù)先為每個(gè)節(jié)點(diǎn)對之間計(jì)算多條備用路由，組成備用路由集。再按照一定的順序檢查備用路由集中的各條路由，尋找合適的路由并為其分配波長波長分配波長分配n波長分配方法通常采用RA或FFn最簡單的波長分配方法是RAn由于波長連續(xù)約束波長連續(xù)約束，該方法使得長光路相對于短光路來說更容易被阻塞n為了克服這個(gè)缺點(diǎn)，可采用“長路由優(yōu)先長路由優(yōu)先”，即按照按照光路長度遞減的順序分配波長光路長度遞減的順序

18、分配波長2）支持分組交換業(yè)務(wù)的虛拓?fù)湓O(shè)計(jì)）支持分組交換業(yè)務(wù)的虛拓?fù)湓O(shè)計(jì) n在支持分組業(yè)務(wù)的WDM光網(wǎng)絡(luò)中，RWA涉及虛拓?fù)湓O(shè)計(jì)n虛拓?fù)湓O(shè)計(jì)的目的，是為了將光域的波長路由技術(shù)光域的波長路由技術(shù)和電域電域的傳統(tǒng)交換技術(shù)的傳統(tǒng)交換技術(shù)結(jié)合，以便更好地支持上層的分組業(yè)務(wù)分組業(yè)務(wù)n確定應(yīng)該在哪些節(jié)點(diǎn)對之間建立光路，以及如何分配有限資源，此問題稱為“虛拓?fù)湓O(shè)計(jì)虛拓?fù)湓O(shè)計(jì)”問題n支持分組業(yè)務(wù)的WDM光傳送網(wǎng)，其設(shè)計(jì)的核心核心就是如何得就是如何得到網(wǎng)絡(luò)性能最佳的虛拓?fù)涞骄W(wǎng)絡(luò)性能最佳的虛拓?fù)?虛拓?fù)湓O(shè)計(jì)虛拓?fù)湓O(shè)計(jì)A數(shù)據(jù)網(wǎng)數(shù)據(jù)網(wǎng)DCBEASON網(wǎng)絡(luò)網(wǎng)絡(luò)F6. 動態(tài)動態(tài)RWA問題問題 n在動態(tài)情況下，光路連接請求隨

19、機(jī)、順序隨機(jī)、順序到達(dá)網(wǎng)絡(luò)，要求進(jìn)行實(shí)時(shí)實(shí)時(shí)RWA計(jì)算；一條光路維持一段有限時(shí)間后又被拆除n動態(tài)RWA算法的目標(biāo)，一般都是有效地選擇光路路由和合理分配波長資源，以使光路建立的阻塞率阻塞率最低n通常又稱為動態(tài)光路建立（Dynamic Lightpath Establishment，DLE）問題 動態(tài)業(yè)務(wù)動態(tài)業(yè)務(wù)n動態(tài)業(yè)務(wù)需求在下列情形下可能出現(xiàn)：1.當(dāng)業(yè)務(wù)分布出現(xiàn)較大變化，或者鏈路、節(jié)點(diǎn)出現(xiàn)故障，需要對網(wǎng)絡(luò)重新配置時(shí)2.隨著寬帶業(yè)務(wù)（如虛擬專用網(wǎng)、ISP租用速率超過2.5Gb/s的線路等）的出現(xiàn)和增長，業(yè)務(wù)需求有可能隨時(shí)間而改變 動態(tài)動態(tài)RWA：分層圖分層圖n在動態(tài)RWA中，在網(wǎng)絡(luò)規(guī)模不太大時(shí)，

20、可以采用分層圖分層圖(Layer Graph)方法將選路和波長分配選路和波長分配集合集合在一起考慮動態(tài)動態(tài)RWA：ADRn但隨著網(wǎng)絡(luò)規(guī)模增大，為了減小復(fù)雜性，常將選路和將選路和波長分配分兩步進(jìn)行波長分配分兩步進(jìn)行n常用的選路方法可采用前面介紹的FR、AR及ADR三種n前兩種選路方式與靜態(tài)RWA問題中一樣，下面僅介紹基于ADR的動態(tài)RWA算法 動態(tài)動態(tài)RWA：ADRn在在ADR算法中，源、宿節(jié)點(diǎn)間的路由根據(jù)網(wǎng)絡(luò)的狀態(tài)進(jìn)行動態(tài)選擇算法中，源、宿節(jié)點(diǎn)間的路由根據(jù)網(wǎng)絡(luò)的狀態(tài)進(jìn)行動態(tài)選擇 , 1 如果：鏈路 代價(jià)基本代價(jià)其他jjfjf1876543211912101318765432119121013(a)(b)18765432119121013(a)7. 集中還是分布集中還是分布n集中式控制網(wǎng)管中心集中控制資源分配（決策者）光節(jié)點(diǎn)只負(fù)責(zé)利用信令建立/拆除光通路（實(shí)施者）n分布式控制光節(jié)點(diǎn)自主尋路，需要運(yùn)行尋路協(xié)議集中還是分布集中還是分布n集中式控制減少光節(jié)點(diǎn)復(fù)雜度阻塞率降低可擴(kuò)展性差，容錯(cuò)性較差n分布式控制容錯(cuò)性能較好需要復(fù)雜的尋路協(xié)議8. 波長轉(zhuǎn)換與波長轉(zhuǎn)換與RWA算法算法 n