WDM光網(wǎng)絡(luò)虛拓魯棒規(guī)劃算法研究.pdf

1、隨著全球“信息高速公路”的發(fā)展，以及寬帶視頻、多媒體、網(wǎng)絡(luò)游戲等業(yè)務(wù)的日益興起，特別是Intemet業(yè)務(wù)的快速增長(zhǎng)，對(duì)廣域骨干網(wǎng)的帶寬提出了越來(lái)越高的要求。因此在有限的網(wǎng)絡(luò)資源下，如何合理的配置、有效的利用光纖網(wǎng)絡(luò)資源，適應(yīng)新業(yè)務(wù)的需求，是當(dāng)今網(wǎng)絡(luò)設(shè)計(jì)面臨的一個(gè)重要問(wèn)題。近年來(lái)，在許多研究領(lǐng)域，如IP網(wǎng)絡(luò)中VPN資源配置、可擴(kuò)展大規(guī)模交換結(jié)構(gòu)，以及并行計(jì)算機(jī)互聯(lián)的研究人員陸續(xù)提出了許多新的網(wǎng)絡(luò)設(shè)計(jì)方法或者資源配置方法。其目標(biāo)是在業(yè)務(wù)量矩

2、陣不確定的情況下，如何配置網(wǎng)絡(luò)節(jié)點(diǎn)之間的路由和帶寬資源，使得全網(wǎng)絡(luò)資源得到最佳利用，并盡可能滿足何種業(yè)務(wù)請(qǐng)求。這種在業(yè)務(wù)量矩陣不確定的情況下的網(wǎng)絡(luò)設(shè)計(jì)方法被稱為“魯棒設(shè)計(jì)”(Robust Design)。作為通信骨干網(wǎng)，WDM網(wǎng)絡(luò)已成為重要的基礎(chǔ)設(shè)施，并提供吉比特(Gigabits)或者太比特(Terabits)級(jí)的容量。本文將主要研究在業(yè)務(wù)量矩陣不確定的情況下，如何設(shè)計(jì)規(guī)劃WDM光網(wǎng)絡(luò)虛拓?fù)洌瑑?yōu)化網(wǎng)絡(luò)資源，提高網(wǎng)絡(luò)性能，主要包括以下部

3、分： (1)基于高斯分布業(yè)務(wù)矩陣下的虛拓?fù)漪敯粼O(shè)計(jì)。主要包括兩個(gè)部分：以最小擁塞為優(yōu)化目標(biāo)的虛拓?fù)湓O(shè)計(jì)和以最小時(shí)延和時(shí)延抖動(dòng)為優(yōu)化目標(biāo)的虛拓?fù)湓O(shè)計(jì)。作為WDM光網(wǎng)絡(luò)設(shè)計(jì)的一個(gè)經(jīng)典問(wèn)題，虛拓?fù)湓O(shè)計(jì)問(wèn)題已有大量的研究成果。但是傳統(tǒng)的設(shè)計(jì)方法都是基于精確業(yè)務(wù)矩陣，不適合不確定業(yè)務(wù)矩陣下的要求。本文第二章首先將每個(gè)用戶的實(shí)際業(yè)務(wù)需求描述為一特定的概率分布，并假設(shè)用戶之間的業(yè)務(wù)需求獨(dú)立并具有相同的概率分布。因此，根據(jù)中心極限定理，骨干網(wǎng)節(jié)

4、點(diǎn)之間的業(yè)務(wù)需求為呈高斯分布的隨機(jī)變量。根據(jù)這一業(yè)務(wù)模型，本文引入了p百分?jǐn)?shù)來(lái)描述光路上的負(fù)載。并以減少網(wǎng)路擁塞為優(yōu)化目標(biāo)，引入不確定因子，提出了新的啟發(fā)式算法ID-MLTDA。本文第三章在高斯分布業(yè)務(wù)矩陣的基礎(chǔ)上，針對(duì)IP業(yè)務(wù)的特點(diǎn)，以分組傳送的最短時(shí)延和最小時(shí)延抖動(dòng)為優(yōu)化目標(biāo)，提出了新的啟發(fā)式算法WVDA。相對(duì)于傳統(tǒng)的算法，WVDA算法的核心思想是將節(jié)點(diǎn)對(duì)間的業(yè)務(wù)量和物理鏈路的長(zhǎng)度結(jié)合起來(lái)用以決定光路的搭建，同時(shí)將節(jié)點(diǎn)間的跳數(shù)和路徑

5、長(zhǎng)度結(jié)合用以決定最短路徑。通過(guò)該算法得到的網(wǎng)絡(luò)結(jié)構(gòu)，具有較小的時(shí)延和時(shí)延抖動(dòng)。 (2)基于Hose模型下的虛拓?fù)漪敯粼O(shè)計(jì)。在WDM光網(wǎng)絡(luò)中，hose模型給出了流入/流出傳送網(wǎng)節(jié)點(diǎn)的業(yè)務(wù)上限，但沒(méi)有說(shuō)明各個(gè)節(jié)點(diǎn)對(duì)之間的具體業(yè)務(wù)量。 近年來(lái)L．G．Valiant提出的負(fù)載平衡思想可以很好的適應(yīng)IP動(dòng)態(tài)業(yè)務(wù)的特性，而且其內(nèi)在的多路徑特性使得網(wǎng)絡(luò)的生存性、業(yè)務(wù)的可恢復(fù)性得到了保障。但是 Valiant負(fù)載平衡思想需要全連接的網(wǎng)絡(luò)

6、拓?fù)?。但WDM光網(wǎng)絡(luò)由于波長(zhǎng)等資源的限制，幾乎不可能提供全連接的虛拓?fù)浣Y(jié)構(gòu)。在Valiant負(fù)載平衡兩條選路網(wǎng)絡(luò)的基礎(chǔ)上，本文第四章將主要研究以使全網(wǎng)代價(jià)最小為優(yōu)化目標(biāo)，用全網(wǎng)流代價(jià)為判決標(biāo)準(zhǔn)，從全網(wǎng)N個(gè)節(jié)點(diǎn)選出M個(gè)節(jié)點(diǎn)做為兩條選路虛拓?fù)浣Y(jié)構(gòu)的轉(zhuǎn)發(fā)節(jié)點(diǎn)，進(jìn)而完成基于hose業(yè)務(wù)模型下虛拓?fù)涞臉?gòu)建。此虛拓?fù)湓O(shè)計(jì)方法具有良好的性能，搭建的網(wǎng)絡(luò)具有較小的網(wǎng)絡(luò)代價(jià)和數(shù)據(jù)具有較短的時(shí)延。本文的第五章介紹了仿真和計(jì)算工作，對(duì)仿真程序進(jìn)行了簡(jiǎn)要的介紹