一文詳解路由演算法
- 2020 年 3 月 9 日
- 筆記
我們都知道，電腦網路的通用分層模型是五層分級模型（物理層、鏈路層、網路層、運輸層、應用層）。每一層都承擔著不同任務，你能順利地和小姐姐在網上聊天，這五層缺一不可?。今天，我們要講的便是網路層的重要內容。 「咳咳，現在開始上課！」
網路層的核心功能
泛泛來講，網路層在電腦網路中承擔的主要功能是：將數據從一台主機移動到另外一台主機。詳細一點說，網路層的主要功能是：路由和轉發。
不用說你也知道，承擔路由和轉發功能的部件是路由器。
那麼問題來了，路由器究竟是如何將聊天資訊數據從你的主機轉移到小姐姐的主機呢？
簡單的說，當你在聊天窗口按下「發送」按鈕後，你的聊天數據被應用層打包成數據包，經過運輸層向路由器運送，而路由器會將數據包中包含地址資訊解析出來，交給路由轉發表處理，路由轉發表就能夠確定數據包在本路由器如何轉發分組。
問題又來了，路由轉發表到底是啥？他怎麼能夠知道我的資訊要轉發到小姐姐那裡呢？
這就涉及到我們今天的主角：路由演算法。路由演算法能夠確定去往目的網路的最佳路徑，而轉發表則能夠確定數據包在本路由器如何轉發分組。
為了方便處理，我們一般將網路抽象為圖。其中，路由器為圖中的結點，網路鏈路抽象為圖中的邊，鏈路長度則為圖中的權值。
路由演算法的分類
路由演算法從配置方式劃分，分為靜態路由和動態路由；而動態路由的路由演算法，從掌握網路拓撲資訊的規模來說，又可以分為全局路由選擇演算法和分散路由選擇演算法。
靜態路由和動態路由
所謂靜態路由，是基於手工配置的路由方式。我們可以類比獲取IP的方式，ip獲取方式也有兩種，一種是靜態，一種是動態。靜態就是由網路管理員來配置網路ip，而動態則是由網路運營商直接分配。如果你還是不太明白，你可以設想下民國時期打電話的方式：你撥通電話，並非直接打到目的地，而是達到了電話局，由電話局接線，才能撥通。所以說，靜態路由的網路管理員，扮演的就是接線員的角色。
靜態路由有如下特點：
- 路由資訊更新慢
- 優先順序高
同樣的，動態路由是基於演算法的方式是基於某種路由演算法實現的，這種方案自動化程度高，是非常明智的選擇。
動態路由有如下特點：
- 路由更新快
- 定期更新（周期性）
全局資訊和分散資訊
全局資訊方案的代表是鏈路狀態路由演算法，分散資訊的代表方案是距離向量路由演算法。
鏈路狀態路由演算法
在鏈路狀態路由演算法中，網路拓撲和所有的鏈路費用都是已知的。所有的結點或者說路由器都掌握著完整的網路拓撲和鏈路費用。
到這裡，你是否能猜到鏈路狀態路由演算法是誰了吧？
沒錯，他就是我們的老朋友——迪傑斯特拉演算法。
從前面介紹中我們也能知道，不論是鏈路狀態路由演算法還是距離向量選擇演算法，核心要義都是四個字：」最短路徑「。
所以，知道了整張網路拓撲，最佳的方案就是迪傑斯特拉演算法。當然，另外一個最短路徑演算法」Prim「也是一個選擇，這裡不做展開。
我們還是先從一個例子開始。
在上圖中，我們以u為起點，計算u到z的最短路徑。可見，若要計算u到z的路徑，那麼必須考慮全局資訊。
實際上，迪傑斯特拉演算法的核心內容是：找最小，然後找最小的鄰居。
具體過程參考下圖。
- 初始化 與u相鄰的置為權值，不與u相鄰的置為無窮。
- 找到最小 在上圖中，與u相鄰的權值最小的是（w，3），所以將w加入集合中。
- 在其餘中找最小 5為最小，則將x加入集合。經過x，可以到達z，這樣最短，將z更新為14。
- 接著找最小 6為最小，將v加入集合。經過uwv，可以到達y，最小值為10，則更新。
- 依次類推，得到最終結果
所以，我們能夠得到最終的轉發表。
|
目的 |
鏈路 |
|---|---|
|
v |
u-w-v |
|
x |
u-x |
|
y |
u-w-v-y |
|
w |
u-w |
|
z |
u-w-v-y-z |
|
|
|
距離向量路由演算法
距離向量路由演算法，是基於Bellman-Ford方程，也就是動態規劃演算法實現的。
在距離向量路由演算法中，同樣是計算由u到其他任意一點。但在這種演算法中，u無需知道整個網路的拓撲結構。對u來說，最重要的事情是知道，如果需要把數據運往z，最合適的鄰居節點究竟是哪一個。
即節點只需獲取最短路徑的下一跳，無需知道整個網路拓撲的情況，並且該資訊用於轉發表中。
所以，距離向量路由演算法是一種迭代的、非同步的、分散式的演算法。
迭代很好理解，在每個節點只需要知道他的下一跳的目的地的情況下，想要求得最小路徑，那麼必然需要使用迭代，使得最短路徑不斷趨近於真實值。
為什麼說是不斷趨近於真實值呢？一開始，也就是初始化時，結點只知道他到其鄰居結點的距離，而不知道到其他結點的距離。
這就必然造成此結點到其直接鄰居結點的距離並非是最優的，可能是繞過一個或兩個結點再到此結點的情況，才是最短的路徑。
所謂非同步的，是因為我們不要求結點的步調整齊一致，也就是計算最短路徑的時間可以是不同的。實際上，時間基本上就是不同。
所謂分散式的，是說每個節點都能接收到來自其鄰居的資訊，並執行計算，然後再將計算結果分發給鄰居，鄰居再將收到的數據進行計算，如果發現了其他最短路徑，那麼就會更新自身的資訊，又進入了一個迭代的過程。
整個演算法中最重要的是這樣一個方程：
先來解釋一下這個方程。
我們要找到從x到y找到最短路徑，就需要知道x到底是經過哪個結點到達y的總長度最短（也可以不經過鄰居結點，此時y就是x的鄰居）。
即我們需要知道，x到底是經過了哪一個鄰居，才使得x到鄰居到y的距離最短。
所以，我們來總結一下。
距離向量路由演算法的核心思想是：
- 每個結點都不定時地將其自身的距離向量（到達其鄰居）的估計（非精確，後期迭代可能會調整）發送給其鄰居
- 當x接收到鄰居新的距離向量時，根據動態規劃方程更新距離向量估計。若數據不發生變化，則無需更新和發送。
具體描述如下（DV即為距離向量）
寫在最後
所謂「金無足赤人無完人」。以上演算法同樣如此，不論是鏈路狀態路由演算法還是距離向量路由演算法，都有其自身的問題。他們在實際應用中都有著非常明顯的問題，從而又有解決這些問題的方法出現。
電腦科學乃至是任意一門科學，都是在不斷地發現問題、解決問題的迭代過程中漸漸趨於真相。
我們要相信，儘管眼前可能看起來麻煩很多，但是我們找到了解決麻煩的方法時，就會驚喜的發現：「Trouble is a friend」。
好了，今天文章就到這裡，感謝您的閱讀，如果你喜歡我的文章，請點個贊吧！
引用： 《電腦網路：自頂向下》 中國大學MOOC，哈爾濱工業大學電腦網路，李金龍等
