最短路徑樹動態(tài)算法的研究.pdf

1、隨著Internet技術(shù)在全球范圍的飛速發(fā)展，OSPF（Open Shortest Path First）協(xié)議目前已成為Internet廣域網(wǎng)和Intranet企業(yè)網(wǎng)廣泛采用的路由協(xié)議之一。由于OSPF協(xié)議是基于鏈路狀態(tài)的路由協(xié)議，同時可以支持大規(guī)模的網(wǎng)絡(luò)（1000多臺路由器）,所以它存在計算最短路徑樹（Shortest Path Tree，SPT）所使用的算法復(fù)雜，耗時較長，CPU的負(fù)擔(dān)較重的問題。
　　為了縮短SPT的計算時間

2、，使得全網(wǎng)能在最短的時間內(nèi)穩(wěn)定下來，近年來已有學(xué)者在這方面做了大量的研究。他們將最短路徑樹算法做了改進(jìn)提出了最短路徑樹動態(tài)算法。本文首先對這些已有的動態(tài)算法做了分析，給出了這些算法的思想以及框架，同時也比較了每個算法的不同之處。
　　在第三章作者給出了基于圖的分解的動態(tài)最短路徑樹算法。然后在不同的情況下分別將該算法與其它的幾個算法進(jìn)行了比較。當(dāng)單條邊的權(quán)重發(fā)生變化時，通過理論分析和算法的性能比較得出了影響動態(tài)算法的因素，并通過實驗

3、對其進(jìn)行了驗證。在多條邊的權(quán)重同時發(fā)生變化的情況下，文章中使用了一個實際的例子來統(tǒng)計當(dāng)有多少條邊的權(quán)重同時發(fā)生變化，使用動態(tài)算法與靜態(tài)算法所需要的時間相同。
　　在前兩章的研究基礎(chǔ)上，在第四章考察了動態(tài)最短路徑樹算法對全網(wǎng)性能的影響。網(wǎng)絡(luò)的收斂時間有一部分是由計算SPT所需要的時間組成的，以上的動態(tài)算法只是針對單個節(jié)點如何快速地計算新的SPT。但是在全網(wǎng)中，我們更注重的是所有的節(jié)點如何能夠快速地得到新的SPT。所以在本章中首先研究

4、單條邊的權(quán)重變化對多棵樹的影響，給出了如何判斷那些樹受到影響的方法以及確定這些受到影響的樹計算新的SPT所需要的時間與那些因素有關(guān)。最后，通過實驗來驗證了作者給出的理論分析。結(jié)合以上結(jié)論，在本章的最后，使用了一個實際的網(wǎng)絡(luò)拓?fù)鋱D統(tǒng)計了單條邊的權(quán)重變化時使用靜態(tài)算法以及各種動態(tài)算法下的收斂時間。并且引出了定義瞬時失效的一種可能思路。
　　綜上，該文章所做的工作主要是OSPF協(xié)議中的SPT計算部分的研究。首先只是針對算法做了一些研究，