基于四叉堆優(yōu)先級隊列的OSPF算法.pdf

1、路由算法是指通信子網(wǎng)的節(jié)點機在接收到一個分組之后,應(yīng)選擇哪條鏈路把它輸送出去所采用的策略.路由算法類型有確定型路由算法(即靜態(tài)路由算法)和適應(yīng)型路由算法(即動態(tài)路由算法).現(xiàn)代計算機網(wǎng)絡(luò)通常使用動態(tài)路由算法,有兩種動態(tài)算法,即距離矢量路由選擇算法(RIP)和鏈路狀態(tài)路由選擇算法(也稱SPF算法)是最常見的.鏈路狀態(tài)路由選擇算法的主要優(yōu)點是路由器可以獨立地計算出路由;排錯較為容易;確保了路由算法的收斂性;報文的長短獨立于互連網(wǎng)絡(luò)中的網(wǎng)絡(luò)數(shù)

2、.因此,SPF算法的性能優(yōu)于RIP,更適于大規(guī)?；ミB網(wǎng)絡(luò)的情況.鏈路狀態(tài)路由選擇在實際網(wǎng)絡(luò)中得到了廣泛的應(yīng)用.OSPF協(xié)議和IS-IS協(xié)議就是兩個廣泛使用的鏈路狀態(tài)路由選擇的例子.IS-IS協(xié)議被用于多種因特網(wǎng)骨干網(wǎng)中和一些數(shù)字蜂窩系統(tǒng);OSPF協(xié)議被越來越多地應(yīng)用于因特網(wǎng).OSPF屬于內(nèi)部網(wǎng)關(guān)協(xié)議,OSPF協(xié)議的基本要素包括:LSA、鏈路狀態(tài)數(shù)據(jù)庫、可靠的泛洪和路由選擇計算.每個路由器都會生成一個或多個LSA,所有路由器產(chǎn)生的LSA形