動(dòng)態(tài)最短路算法在IP網(wǎng)絡(luò)權(quán)重規(guī)劃中的應(yīng)用研究.pdf

1、在IP網(wǎng)絡(luò)中，鏈路權(quán)重決定了網(wǎng)絡(luò)的流量分布，因此通過優(yōu)化IP網(wǎng)絡(luò)鏈路權(quán)重可以達(dá)到優(yōu)化網(wǎng)絡(luò)流量分布的目的?；卩徲蛩阉鞯臋?quán)重優(yōu)化方法是被公認(rèn)為目前解決IP網(wǎng)絡(luò)權(quán)重優(yōu)化問題最行之有效的方法之一?；卩徲蛩阉鞯臋?quán)重優(yōu)化方法在每一次迭代過程中都需要對(duì)若干候選權(quán)重鄰域內(nèi)的大量鄰居權(quán)重進(jìn)行評(píng)價(jià)，從而有機(jī)會(huì)獲得更好的權(quán)重。計(jì)算全網(wǎng)任意節(jié)點(diǎn)對(duì)間的最短路和流量分配是權(quán)重評(píng)估的兩個(gè)重要步驟。全網(wǎng)最短路的計(jì)算效率直接決定了權(quán)重評(píng)價(jià)的效率。因此，全網(wǎng)最短路計(jì)算

2、的效率增加將大大提高鄰域搜索算法的效率。
　　由于傳統(tǒng)的計(jì)算全網(wǎng)最短路算法在網(wǎng)絡(luò)規(guī)模較大時(shí)算法效率較差，因此鄰域搜索算法難以在合理的時(shí)間內(nèi)找到滿足要求的權(quán)重。作者根據(jù)鄰域搜索算法中不同的鄰居權(quán)重之間只有少數(shù)鏈路權(quán)重發(fā)生變化的特點(diǎn)，將效率更高的動(dòng)態(tài)最短路算法應(yīng)用于鄰域搜索算法中。本文在第二章首先介紹傳統(tǒng)的靜態(tài)和動(dòng)態(tài)最短路算法；接下來，描述在實(shí)現(xiàn)動(dòng)態(tài)最短路算法的過程中要注意的問題并提出有效的改進(jìn)意見；然后，對(duì)比3種不同的最短路算法的效

3、率，為鄰域搜索算法選擇計(jì)算最短路的方法提供參考；最后，作者發(fā)現(xiàn)實(shí)現(xiàn)流量分配所需的信息可在計(jì)算動(dòng)態(tài)最短路過程中進(jìn)行動(dòng)態(tài)更新，于是提出了結(jié)合流量分布的動(dòng)態(tài)最短路算法。在鄰域搜索算法中引入結(jié)合流量分布的動(dòng)態(tài)最短路算法后，算法的效率得到了較大地提高。
　　為了便于管理，一個(gè)IGP網(wǎng)絡(luò)常被劃分為多個(gè)區(qū)域，其中TSA域的節(jié)點(diǎn)具有不知曉外部網(wǎng)絡(luò)的具體路由，只能將數(shù)據(jù)轉(zhuǎn)發(fā)給離自己最近的邊界節(jié)點(diǎn)的特點(diǎn)。傳統(tǒng)的最短路算法對(duì)這樣的多區(qū)域網(wǎng)絡(luò)已不再適用，

4、目前也沒有文獻(xiàn)給出基于多區(qū)域網(wǎng)絡(luò)的最短路算法。因此，為了實(shí)現(xiàn)在多區(qū)域網(wǎng)絡(luò)中進(jìn)行IP網(wǎng)絡(luò)權(quán)重規(guī)劃，本文在第三章提出了適合多區(qū)域網(wǎng)絡(luò)的靜態(tài)最短路算法和動(dòng)態(tài)最短路算法。
　　對(duì)有抗毀需求的IP網(wǎng)絡(luò)權(quán)重規(guī)劃，完成一次權(quán)重評(píng)估需假定每一條鏈路失效進(jìn)行分析，所以有抗毀要求的權(quán)重優(yōu)化算法權(quán)重評(píng)估的時(shí)間是普通權(quán)重評(píng)估m(xù)倍，其中m為網(wǎng)絡(luò)中的鏈路數(shù)目。為了減小鄰域搜索算法抗毀迭代的時(shí)間，本文提出了一種適應(yīng)于考慮抗毀性能的權(quán)重優(yōu)化問題的全網(wǎng)動(dòng)態(tài)最短路算