目錄
一、迪杰斯特拉算法
1. 術(shù)語定義
2. 算法描述
3. 舉例說明
4.?構(gòu)建從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑
5. 構(gòu)建最低費(fèi)用路徑樹
6. 構(gòu)建轉(zhuǎn)發(fā)表
二、距離向量路由算法
1. 術(shù)語定義
2. 舉例說明
3. 距離向量表
4. 更新距離向量表
5. 舉例說明
三、距離向量路由算法 PLUS
1. 鏈路費(fèi)用改變與鏈路故障
2. 毒性逆轉(zhuǎn)
3. 毒性逆轉(zhuǎn)的 BUG
四、LS 算法和 DV 算法比較
1. 消息復(fù)雜度
2. 收斂速度
3. 健壯性
一、迪杰斯特拉算法
迪杰斯特拉算法屬于 LS 算法。
1. 術(shù)語定義
2. 算法描述
3. 舉例說明
計(jì)算從 u 到所有可能目的節(jié)點(diǎn)的最低費(fèi)用路徑。
計(jì)算過程如表，表中的每一行表示一次迭代結(jié)束時(shí)的算法變量值。
- 代表無窮，/ 代表已經(jīng)加入集合 N' 。
4.?構(gòu)建從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑
5. 構(gòu)建最低費(fèi)用路徑樹
最低費(fèi)用路徑樹不同于最小生成樹。最小生成樹保證連接所有節(jié)點(diǎn)的路徑權(quán)值之和最小，而最低費(fèi)用路徑樹只是保證源節(jié)點(diǎn)到各目的節(jié)點(diǎn)的路徑權(quán)值之和最小。因此，最小生成樹不用指出一個(gè)源節(jié)點(diǎn)，而最低費(fèi)用路徑樹必須指出一個(gè)源節(jié)點(diǎn)。源節(jié)點(diǎn)的不同，會導(dǎo)致最低費(fèi)用路徑樹的不同。
根據(jù)目的節(jié)點(diǎn)找出順序及其前驅(qū)節(jié)點(diǎn)，可以畫出從源節(jié)點(diǎn) u 到所有目的節(jié)點(diǎn)的最低費(fèi)用路徑樹。
根據(jù)得到的最低費(fèi)用路徑樹，可以生成源節(jié)點(diǎn) u 的轉(zhuǎn)發(fā)表。
6. 構(gòu)建轉(zhuǎn)發(fā)表
默認(rèn)路由 * ：用于表示所有具有相同下一跳的表項(xiàng)。即將下一跳相同的項(xiàng)合并為一項(xiàng)，用 * 表示目的節(jié)點(diǎn)。默認(rèn)路由的優(yōu)先級最低：轉(zhuǎn)發(fā)分組時(shí)，只有找不到對應(yīng)表項(xiàng)時(shí)，才使用默認(rèn)路由。
二、距離向量路由算法
1. 術(shù)語定義
最低費(fèi)用路徑的費(fèi)用表示
2. 舉例說明
所有 d 值都是鄰居節(jié)點(diǎn)告訴源節(jié)點(diǎn)的，源節(jié)點(diǎn)只知道它與鄰居節(jié)點(diǎn)的直接鏈路的鏈路費(fèi)用。
3. 距離向量表
初始時(shí) x 并不知道 y 和 z 的距離向量，因此都設(shè)置為無窮。
4. 更新距離向量表
5. 舉例說明
初始節(jié)點(diǎn)只知道自己到鄰居節(jié)點(diǎn)的鏈路費(fèi)用。
開始后，節(jié)點(diǎn)將自己的距離向量表發(fā)送給鄰居，同時(shí)接收鄰居的距離向量表。然后，根據(jù)鄰居的距離向量表來更新自己的距離向量。
注意：c(x, z) 等數(shù)值來源于圖，Dy 和 Dz 來源與鄰居的距離向量表。此外，這一時(shí)刻的 Dx 由 BF 公式計(jì)算而得，跟上一時(shí)刻的 Dx 值無關(guān)（不需要和上一時(shí)刻的 Dx 值比大?。∫虼?，更新的 Dx 值可能更大也可能更小。
只要自己的距離向量更新了，就需要發(fā)送給自己的鄰居節(jié)點(diǎn)，同時(shí)也要接收鄰居節(jié)點(diǎn)發(fā)來的更新的距離向量。
第二次沒有需要更新的距離向量，因此不會再發(fā)送給鄰居節(jié)點(diǎn)，從而算法終止。
總結(jié)：
① 多次重復(fù)從鄰居節(jié)點(diǎn)接收更新的距離向量，并重新計(jì)算距離向量，再向鄰居節(jié)點(diǎn)發(fā)送更新的距離向量，一直持續(xù)到?jīng)]有更新的距離向量發(fā)出為止。
② 算法進(jìn)入暫時(shí)的靜止?fàn)顟B(tài)，直到某個(gè)鏈路的費(fèi)用發(fā)生改變?yōu)橹埂?/p>
③ 再次重復(fù) ① 的操作。
三、距離向量路由算法 PLUS
1. 鏈路費(fèi)用改變與鏈路故障
當(dāng)一個(gè)節(jié)點(diǎn)檢測到它與鄰居節(jié)點(diǎn)之間的鏈路費(fèi)用發(fā)生變化時(shí)，就用 BF 公式重新計(jì)算其距離向量。若距離向量發(fā)生變化，則通知其鄰居節(jié)點(diǎn)。
（1）某鏈路費(fèi)用減少時(shí)的情況
說明：節(jié)點(diǎn)之間鏈路費(fèi)用減少的 好消息 在網(wǎng)絡(luò)中能迅速傳播。
（2）某鏈路費(fèi)用增加時(shí)的情況
Q：為什么計(jì)算出來的新費(fèi)用是錯(cuò)的？
A：由于鏈路費(fèi)用改變，Dz(x) 已經(jīng)不等于 5 了，但 y 還是使用了舊的 Dz(x) 。
產(chǎn)生選路回環(huán)：為到達(dá) x， y 通過 z 選路，z 又通過 y 選路。即目的地為 x 的分組到達(dá) y 或 z 后，將在這兩個(gè)節(jié)點(diǎn)之間不停地來回反復(fù)，直到轉(zhuǎn)發(fā)表發(fā)生新的改變?yōu)橹埂?/p>
說明：鏈路費(fèi)用增加的 壞消息 傳播得很慢！當(dāng)鏈路費(fèi)用增加的很大時(shí)，會出現(xiàn) 計(jì)數(shù)到無窮 問題。如鏈路費(fèi)用 c(y，x) 變?yōu)?10000，c(z，x) 變?yōu)?9999 時(shí)。
2. 毒性逆轉(zhuǎn)
解決 計(jì)數(shù)到無窮 的方法：毒性逆轉(zhuǎn)。
毒性逆轉(zhuǎn)：假如 z 為了實(shí)現(xiàn)最低路徑費(fèi)用而需要通過 y 去到達(dá) x，則 z 告訴 y ：它到 x 的距離是無窮大的，從而 y 將不會再經(jīng)過 z 到 x 。
假設(shè) y 計(jì)算出它到達(dá) x 的最低費(fèi)用路徑為：y→z→...→x，而 z 計(jì)算出它到達(dá) x 的最低費(fèi)用路徑為：z→y→...→x，則會產(chǎn)生選路循環(huán)。因此，如果 z 到 x 需要經(jīng)過 y，則讓 y 到 x 的時(shí)候一定不要經(jīng)過 z，因?yàn)闊o論如何 y 經(jīng) z 到 x 的費(fèi)用都會比 y 到 x 的大（因?yàn)?z 到 x 包含了 y 到 x）
y 內(nèi)心 OS：還不如俺自己去找 x 。
前兩步還是和之前一樣的操作，不過引入毒性逆轉(zhuǎn)后，x 或 y或 z 需要根據(jù)自己的下一跳來通知鄰居節(jié)點(diǎn)其某個(gè)距離向量為無窮。
鏈路費(fèi)用的改變打破了原本的安寧！
z 根據(jù) y 更新的距離向量來更新自己的距離向量。
雖然 z 的距離向量改變了，但由于該路徑還是會經(jīng)過 y，對于 y 仍應(yīng)該是無窮，因此不必再通知 y 了，從而又進(jìn)入了暫時(shí)靜止?fàn)顟B(tài)。
3. 毒性逆轉(zhuǎn)的 BUG
Q：毒性逆轉(zhuǎn)可以完全解決計(jì)數(shù)到無窮的問題嗎？
A：不能。如果是三個(gè)以上節(jié)點(diǎn)的環(huán)路，則不能被毒性逆轉(zhuǎn)技術(shù)檢測到。
Dz(a) 的路徑為：z→y→...→a，進(jìn)一步這條路為：z→y→x→...→a，但是 z 只知道自己的下一跳是誰，而不知道自己的下一跳又去經(jīng)過了 x，因此基于下一跳的毒性逆轉(zhuǎn)策略失效了。
其它解決環(huán)路的方法：
- 定義最大度量，以防止計(jì)數(shù)至無窮大
- 抑制計(jì)時(shí)器
- 水平分割
- 路由毒化
- 觸發(fā)更新
四、LS 算法和 DV 算法比較
1. 消息復(fù)雜度
LS 算法：知道網(wǎng)絡(luò)每條鏈路的費(fèi)用，需發(fā)送 O(nE) 個(gè)報(bào)文；當(dāng)一條鏈路的費(fèi)用變化時(shí)，必須通知所有節(jié)點(diǎn)。
DV 算法：迭代時(shí)，僅在兩個(gè)直接相連鄰居之間交換報(bào)文；當(dāng)鏈路費(fèi)用改變時(shí)，只有該鏈路相連的節(jié)點(diǎn)的最低費(fèi)用路徑發(fā)生改變時(shí)，才傳播已改變的鏈路費(fèi)用。
?
?
2. 收斂速度
LS 算法：需要 O(nE) 個(gè)報(bào)文和 O(n2) 的搜尋，可能會振蕩。
DV 算法：收斂較慢。可能會遇到選路回環(huán)，或計(jì)數(shù)到無窮的問題。
3. 健壯性
Q：當(dāng)一臺路由器發(fā)生故障、操作錯(cuò)誤或受到破壞時(shí)，會發(fā)生什么情況？
LS 算法：路由器向其連接的一條鏈路廣播不正確費(fèi)用，路由計(jì)算基本獨(dú)立（僅計(jì)算自己的轉(zhuǎn)發(fā)表），有一定健壯性。文章來源：http://www.zghlxwxcb.cn/news/detail-428193.html
DV 算法：一個(gè)節(jié)點(diǎn)可向任意或所有目的節(jié)點(diǎn)發(fā)布其不正確的最低費(fèi)用路徑，一個(gè)節(jié)點(diǎn)的計(jì)算值會傳遞給它的鄰居，并間接地傳遞給鄰居的鄰居。一個(gè)不正確的計(jì)算值會擴(kuò)散到整個(gè)網(wǎng)絡(luò)。文章來源地址http://www.zghlxwxcb.cn/news/detail-428193.html
到了這里，關(guān)于DJ4-5 路由算法：LS 和 DV的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
