最短路徑樹動(dòng)態(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é)議，同時(shí)可以支持大規(guī)模的網(wǎng)絡(luò)（1000多臺(tái)路由器）,所以它存在計(jì)算最短路徑樹（Shortest Path Tree，SPT）所使用的算法復(fù)雜，耗時(shí)較長，CPU的負(fù)擔(dān)較重的問題。
　　為了縮短SPT的計(jì)算時(shí)間

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

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

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