知識星球(點選上方公號，快速關註我們)
作者：王奎，個人公號：不止思考
在計算機網路中，路由器的一個很重要責任就是要在端對端的節點中找出一條最佳路徑出來，透過自己與相鄰節點之間的資訊，來計算出從自己位置到目的節點之間的最佳線路，這種演演算法我們可以理解為路由演演算法。
路由的樣式又主要分為「靜態路由」和「動態路由」。靜態路由協議是由網路管理員手動輸入配置的，適用於小型的不太複雜的網路環境中，或者有特定需求的網路場景中。而動態路由協議是現代計算機網路中最為常用的一種方式。動態路由演演算法能夠根據網路拓撲結構去適應流量的變化。
本文主要聊的就是「動態路由演演算法」，你知道動態路由演演算法有哪些嗎？
動態路由演演算法大致可以分為兩類：
-
距離向量路由演演算法
-
鏈路狀態路由演演算法
下麵我們來看一下這兩類演演算法的特點：
一、距離向量路由演演算法
距離向量路由演演算法（Distance Vector Routing），它是網路上最早使用的動態路由演演算法，也稱為Bellman-Ford或者Ford-Fulkerson演演算法。基於這類演演算法實現的協議有：RIP、BGP等。
如圖，
這類演演算法的基本思路是：網路中每一個路由器都要維護一張 矢量表 ，這個 矢量表 中的每一行都記錄了從當前位置能到達的標的路由器的最佳出口（介面）和距離（跳數）。
每隔一段時間當前路由器會向所有的鄰居節點傳送自己的這個表，同時它也會接收每個鄰居發來的它們的表。並會將鄰居的表和自己的表做一個對比更新。
比如當前 路由器X 離 鄰居Y路由器 的距離是m，此時收到 鄰居Y 發來的表中寫到了“ 鄰居Y離路由器Z的距離是n ”，那 當前路由器X 就知道它離 路由器Z 的距離可能就是 m+n 了，如圖：
就這樣繼續類推，要不了多久，每個路由器就可以將網路中所有路由節點和子網線路都匯聚起來了。這樣的話，每個路由器只需要查詢自己的表就可以很容易的知道到達目的地的最佳出口（介面）是哪個了。
當然，當網路結構發生變化的時候，各個路由器中的矢量表也會隨之動態更新。
好了，講到這裡，基本上對「距離向量路由演演算法」大概原理有個認識了，現在我們再來仔細分析分析這個演演算法的名字，可以發現，它的名字取的還是蠻有意思的，非常貼切。“距離”這個詞就基本表明瞭這個演演算法是透過 距離（跳數/時間）來度量2個路由網路之間的線路的，而“向量”這個詞，可以看出線路是有方向性的，且路由表中只記錄了資料包去往目的地應該走哪個出口方向，並不會記錄到達目的地的整條路徑。
「距離向量路由演演算法」的優點很明顯：非常簡單清晰，且任何加入到網路中的新節點都能很快的與其它節點建立起聯絡獲得補充資訊。
缺點呢，首先就是每次傳送資訊的時候，要傳送整個全域性路由表，太大了，因為每個路由器需要在矢量表中記錄下整個網路的資訊，導致需要較大儲存、CPU、網路開銷，對資源的要求越來越高。還有一個問題就是收斂時間太慢，也就是路由器共享路由資訊並使各臺路由器掌握的網路情況達到一致所需的時間比較久，收斂速度慢會導致有些路由器的表更新慢，從而造成路由環路的問題。
二、鏈路狀態路由演演算法
鏈路狀態路由演演算法（Link State Routing ），基於Dijkstra演演算法，它是以圖論作為理論基礎，用圖來表示網路拓撲結構，用圖論中的最短路徑演演算法來計算網路間的最佳路由。基於這類演演算法實現的協議有：OSPF 等。
如圖，
這類演演算法的基本思路是：採用的是不停的拼接地圖的方式。每一個路由器首先都會發現自己身邊的鄰居節點，然後將自己與鄰居節點之間的鏈路狀態包廣播出去，傳送到整個網路。這樣，當某個路由器收到從網路中其它路由器廣播來的路由資訊包（鏈路狀態包）之後，會將這個包中的資訊與自己路由器上的資訊進行拼裝，最終形成一個全網的拓撲檢視。
當路由器中形成了全網的拓撲檢視後，它就可以透過最短路徑演演算法來計算當前節點到其它路由器之間的最短路徑了。當某臺路由器的鏈路狀態發生變化時，路由器採用洪泛法向所有路由器傳送此資訊，其它路由器使用收到的資訊重新計算最佳路徑，重新生成路由表（拓撲圖）。
這裡可以做一個類比，有一個路人甲人去問路，然後本地人A只知道A自己生活方圓5公里的地圖，本地人B只知道B自己生活的方圓5公里的地圖，但是路人甲要去的地方需要穿過A和B所在區域，那麼就把A和B的2份地圖拿來拼裝在一起，然後去往目的地的完整路線就可以查出來了。
鏈路狀態路由演演算法簡單而言就是五個步驟：
-
發現鄰居節點，並瞭解鄰居網路地址
-
測量到鄰居節點的距離或成本度量值
-
構建一個包含自己所擁有資訊的鏈路狀態包
-
將這個包廣播到網路中，並接收其它路由器的鏈路狀態包
-
計算出當前節點到其它節點之間的最短路徑（基於Dijkstra演演算法）
鏈路狀態路由演演算法 不會像 距離向量路由演演算法 那樣傳送整個路由表，鏈路狀態路由協議只會廣播更新的或者改變了的網路拓撲，這樣傳播的資訊量會少很多，同時對頻寬和CPU資源也是一種節省。
「鏈路狀態路由演演算法」具有很好的擴充套件能力，也具有更快的收斂速度，能夠快速的適應網路變化，且由於一個路由器的鏈路狀態只涉及與其相鄰的路由器的聯通狀態，因而與整個網際網路的規模並無直接關係，因此鏈路狀態路由演演算法可以用於大型的或者路由資訊變化劇烈的網際網路環境。
將上述兩種演演算法做一個簡單的對比：
圖片來源網路，經供參考
以上，就是對計算機網路中的動態路由演演算法的基本講解了，歡迎大家一起交流。
【關於作者】
王奎：不止思考的技術人，一名駐紮在武漢網際網路的程式員老兵，我有一個公眾號 bzsikao 平時寫一些工作的心得和技術文章。
【關於投稿】
如果大家有原創好文投稿，請直接給公號傳送留言。
① 留言格式：
【投稿】+《 文章標題》+ 文章連結
② 示例：
【投稿】《不要自稱是程式員，我十多年的 IT 職場總結》：
http://blog.jobbole.com/94148/
③ 最後請附上您的個人簡介哈~
覺得本文有幫助？請分享給更多人
關註「演演算法愛好者」，修煉程式設計內功
