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

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

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

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

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