寬帶通信網(wǎng)中Valiant負載平衡技術(shù)研究.pdf

1、Valiant負載平衡技術(shù)來源于多處理器領(lǐng)域，其實質(zhì)為每個結(jié)點將分布式系統(tǒng)賦予的任務(wù)均勻分配給其他所有結(jié)點處理，使得整個系統(tǒng)的負載趨于平衡，從而提高了整個系統(tǒng)的效率。近年來，隨著Internet數(shù)據(jù)業(yè)務(wù)量的爆炸式增長以及服務(wù)質(zhì)量(QoS，Quality of Service)要求的不斷提高，十分有必要對寬帶通信網(wǎng)的整體架構(gòu)、選路算法以及核心節(jié)點的實現(xiàn)方式等方面進行改進創(chuàng)新，以滿足網(wǎng)絡(luò)業(yè)務(wù)的高速增長和動態(tài)變化。相應(yīng)地Valiant負載平衡

2、技術(shù)應(yīng)用于寬帶通信網(wǎng)中，為寬帶通信網(wǎng)的相關(guān)研究產(chǎn)生了新的思想和新的方法。本文研究了Valiant負載平衡技術(shù)在寬帶通信網(wǎng)中的應(yīng)用問題，主要圍繞以下兩個方面展開：(1)Valiant負載平衡的兩級交換機；(2)WDM光網(wǎng)絡(luò)中Valiant負載平衡的魯棒選路算法。 Valiant負載平衡交換機分為兩級交換結(jié)構(gòu)，第一級交換結(jié)構(gòu)連接輸入和中間輸入，起分散負載的作用，第二級交換結(jié)構(gòu)連接中間輸入和輸出，將負載最終送到輸出端口。Valiant

3、負載平衡交換機具有良好的擴展性；同時可以提供100％吞吐量保證。但是，Valiant負載平衡交換機的基本結(jié)構(gòu)會出現(xiàn)分組亂序的情況，這將導(dǎo)致網(wǎng)絡(luò)交換性能的下降。 在第二章中提出了一種在兩級Valiant負載平衡交換機中保證分組順序到達的BPS(Blank Packet Stuff)算法。BPS算法通過向輸入隊列中填充分組從而形成滿幀，使得分組順序通過交換機。BPS算法具有良好的交換特性(平均時延及吞吐量)，同時也是一種分布式算法，

4、各個端口可以獨立地進行操作。 在WDM網(wǎng)狀網(wǎng)中，靜態(tài)/動態(tài)條件下傳統(tǒng)的選路和波長分配(RWA)算法適用于光路業(yè)務(wù)量/速率矩陣確知的情況，然而在實際應(yīng)用中往往難于估計。 第三章研究了WDM網(wǎng)狀網(wǎng)在單粒度光路連接請求(即連接請求的帶寬等于一個波長的帶寬)的Hose不確定業(yè)務(wù)模型下Valiant負載平衡的魯棒選路問題。本章的研究共分以下三個方面。(1)針對靜態(tài)Hose不確定業(yè)務(wù)模型下全網(wǎng)總代價最小的優(yōu)化設(shè)計問題，作者在整數(shù)線性

5、規(guī)劃(ILP,Integer Linear Programming)的基礎(chǔ)上，提出了MRUF(Maximizing Resource Utilizaiton First)的啟發(fā)式算法。MRUF算法從最大化資源利用率的角度出發(fā)計算負載分配向量，從而有效地在WDM網(wǎng)狀網(wǎng)中建立了全連接的虛拓撲，使得該虛拓撲能為靜態(tài)Hose不確定業(yè)務(wù)模型下所有的業(yè)務(wù)量矩陣都能提供100％的網(wǎng)絡(luò)吞吐量。(2)針對Valiant負載平衡的魯棒選路算法下的WDM網(wǎng)狀

6、網(wǎng)的抗毀設(shè)計問題，作者基于專用通道保護(Dedicated Path Protection)的方式，提出了TMRUF(Two-StepMRUF)的啟發(fā)式算法。計算機仿真表明 TMRUF算法在提供魯棒性保護的同時具有較小的全網(wǎng)總代價。(3)針對邏輯全連接的光交換網(wǎng)絡(luò)在動態(tài)Hose不確定模型下的魯棒選路問題，基于Valiant負載平衡機制，作者提出了LBADF(Load Balancing with Adjustable Distribut

7、ion Fraction)算法。LBADF算法根據(jù)網(wǎng)絡(luò)中當前各條鏈路上空閑光路的數(shù)目對Valiant負載平衡機制中的分配系數(shù)進行即時動態(tài)地調(diào)整，從而達到了優(yōu)化網(wǎng)絡(luò)性能的目的。在WDM網(wǎng)狀網(wǎng)中，傳統(tǒng)的業(yè)務(wù)量疏導(dǎo)(Traffic Grooming)算法適用于不同粒度連接請求的業(yè)務(wù)量矩陣確知的情況，然而在實際應(yīng)用中往往很難估計業(yè)務(wù)量矩陣。 第四章研究了WDM網(wǎng)狀網(wǎng)在多粒度帶寬連接請求(即連接請求的帶寬不盡相同，都小于一個波長的帶寬)的

8、Hose不確定業(yè)務(wù)模型下Valiant負載平衡的魯棒選路問題。本章的研究共分以下兩個方面。(1)針對多粒度連接請求條件下的全網(wǎng)總代價最小的優(yōu)化設(shè)計問題，考慮到網(wǎng)絡(luò)中存在多種不同粒度的連接請求并且連接請求不可再分的情況，作者提出了Hose模型分解(Hose Model Separation)的方法，將Hose不確定業(yè)務(wù)模型分為不同粒度的Hose子模型，并且分別為它們計算負載分配向量。作者提出了IMRUF(Improved MRUF)的啟發(fā)

9、式算法，并通過計算機仿真驗證了算法的有效性。(2)針對OC-1連接請求條件下的Hose模型吞吐量最大的優(yōu)化設(shè)計問題，作者提出了SBR&MRUF(Shortest Balanced Routing & MRUF)的啟發(fā)式算法。SBR&MRUF算法對于短距離路徑的節(jié)點對采用最短路徑的方法，對于長距離路徑的節(jié)點對采用平衡選路的方法，因此SBR&MRUF算法具有較優(yōu)的網(wǎng)絡(luò)性能。 第五章研究了基于IP的光網(wǎng)絡(luò)在Hose不確定模型下的網(wǎng)絡(luò)規(guī)

10、劃問題，其目標為在保證Hose不確定模型魯棒選路的前提下建立最小代價網(wǎng)絡(luò)。作者考察了幾種適用于Hose不確定模型魯棒選路的基本網(wǎng)絡(luò)結(jié)構(gòu)，包括傳統(tǒng)的以電路交換為基礎(chǔ)的單跳選路的網(wǎng)絡(luò)結(jié)構(gòu)，以點到點電路連接為基礎(chǔ)的多跳選路的網(wǎng)絡(luò)結(jié)構(gòu)，和最新的Valiant負載平衡的兩跳選路的網(wǎng)絡(luò)結(jié)構(gòu)；并針對Valiant負載平衡的兩跳選路的網(wǎng)絡(luò)結(jié)構(gòu)提出了新的NSRLB(Non-Uniform Selective Randomized LoadBalancin