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

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

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

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

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