動態(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)化方法在每一次迭代過程中都需要對若干候選權(quán)重鄰域內(nèi)的大量鄰居權(quán)重進(jìn)行評價，從而有機會獲得更好的權(quán)重。計算全網(wǎng)任意節(jié)點對間的最短路和流量分配是權(quán)重評估的兩個重要步驟。全網(wǎng)最短路的計算效率直接決定了權(quán)重評價的效率。因此，全網(wǎng)最短路計算

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

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

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