計(jì)算機(jī)網(wǎng)絡(luò)系列博文——目錄

鏈路狀態(tài)(Link State,LS)路由選擇算法

• 全局式的路由選擇算法；

鏈路狀態(tài)廣播算法

• 為獲取全局網(wǎng)絡(luò)信息，實(shí)踐中要求每個(gè)節(jié)點(diǎn)向網(wǎng)絡(luò)中所有其它節(jié)點(diǎn)廣播鏈路狀態(tài)分組；
• 節(jié)點(diǎn)廣播的結(jié)果是，所有節(jié)點(diǎn)都具有了該網(wǎng)絡(luò)等同的完整的視圖；

鏈路狀態(tài)路由選擇算法

• 具體的鏈路狀態(tài)路由選擇算法可選用Dijkstra算法等單源最短路徑算法；
• 每個(gè)節(jié)點(diǎn)都在其上運(yùn)行單源最短路徑算法，以獲取到達(dá)每個(gè)目的地的下一跳路由節(jié)點(diǎn)，從而構(gòu)造轉(zhuǎn)發(fā)表；

Dijkstra算法

c(x,y): 結(jié)點(diǎn)x到結(jié)點(diǎn)y鏈路費(fèi)用；如果x和y不直接相連，則=∞
D(v): 從源到目的v的當(dāng)前路徑費(fèi)用值
p(v): 沿從源到v的當(dāng)前路徑，v的前序結(jié)點(diǎn)

每輪迭代，從最短路徑未確定的節(jié)點(diǎn)集合中，選取一個(gè)路徑最短的節(jié)點(diǎn)，到該節(jié)點(diǎn)的當(dāng)前最短路徑就是到該節(jié)點(diǎn)的最短路徑，將之加入最短路徑已確定節(jié)點(diǎn)集合，并更新到該節(jié)點(diǎn)鄰接節(jié)點(diǎn)的當(dāng)前最短路徑；

k次迭代后，得到到達(dá)k個(gè)目的結(jié)點(diǎn)的最短路徑

算法復(fù)雜性

對(duì)n個(gè)節(jié)點(diǎn)

時(shí)間復(fù)雜度

更高效的實(shí)現(xiàn)

鏈路狀態(tài)路由算法的問(wèn)題

存在震蕩(oscillations)可能

在狀態(tài)a下，算法判定轉(zhuǎn)換到狀態(tài)b費(fèi)用更底，
在狀態(tài)b下，算法判定轉(zhuǎn)換到狀態(tài)a費(fèi)用更底；

這是由于由于算法選擇的路由會(huì)影響鏈路擁塞程度，鏈路擁塞程度會(huì)影響鏈路權(quán)重，鏈路權(quán)重又會(huì)影響算法選擇的路由；