路由協定有很多種分類方式,依據所影響的範圍可以分成內部路由協定(IGP)和外部路由協定(EGP)兩大類型,而對內部路由協定而言,若依據所採用的路由演算法來區分,則有Distance Vector、Link State以及混合兩者的方法等三種主要類型,而本篇將介紹其中的Link-State路由演算法,並說明其重要特性。
不像Distance Vector路由演算法那樣簡單,Link-State路由演算法的運作方式比較複雜,雖然大部分的路由協定可能都是使用Distance Vector路由演算法,例如RIP、IGRP,但還是有部分路由協定採用Link-State路由演算法。一般常見的Link-State路由協定包含OSPF和IS-IS等等。
簡單來說,Link-State路由演算方式是,網路上每一個節點(也就是路由器)都會擁有自己一份的「網路地圖」,這份網路地圖顯示了從自己這個節點到網路上任一節點的最佳路線,而這些最佳路線都是計算出來的,所以每個節點的地圖不見得相同,也不彼此分享,這份網路地圖也就是Routing Table。與Distance Vector路由協定最大的不同點是,Distance Vector路由協定中的路由器會彼此分享Routing Table。
因此,對於專業的網路管理人員來說,這依然是必備的專業知識之一。在這篇文章中,除了會解釋Link-State路由演算法如何維護路由相關的資訊外,還會提及Link-State路由演算法的優點和缺點,以及使用Link-State路由演算法必須注意的地方。
Link-State路由協定的由來
第一個推出Link-State路由協定的人是John M. McQuillan,於1979年公開這種協定的計算方式。當時,這種計算方式可以針對網路的改變,快速計算出最佳網路路線,讓網路的狀態趨於穩定。
而後來,這種Link State路由協定的設計方式運用於階層式網路架構則更有幫助,因為每個節點(路由器)都不需要擁有整個網路的Routing Table,而只要針對已經區分好的階層式區域(Areas)來計算路由表即可。
近年來,這種技術被IETF(Internet Engineering Task Force)組織發展並標準化成OLSR(Optimized Link State Protocol),並且被運用在無線網狀網路(Wireless Mesh Network)之中,這種網狀網路是採用網狀拓撲技術,由用戶端、路由器及閘道器所組成,採用IEEE 802.11、802.15以及802.16等技術。
路由協定在自治系統的分類
路由協定有很多分類的方式,其中一種就是根據自治系統的運作範圍來做分類。但什麼是自治系統?與路由協定又有什麼關係呢?
自治系統(Autonomous System,AS)指的是處於相同的管理網域(Administrative Domain)下所有網路的集合,而一個管理網域指的是主機、路由器與內部連接網路的集合,而這個集合是歸屬於同樣的管理下運作的。
有些路由協定是運作在同一個自治系統內,而某些路由協定則運作在不同的自治系統之間,若以運作於自治系統的內部與外部來區分路由協定的話,則可以分成內部路由協定(Interior Gateway Protocol,IGP)與外部路由協定(Exterior Gateway Protocol,EGP)。
屬於內部路由協定的路由協定包含RIPv1、RIPv2、IGRP、EIGRP以及OSPF,而屬於外部路由協定的路由協定則有BGP。本文將著重在內部路由協定部分的說明。
路由演算法的分類
對於內部路由協定而言,其所採用的路由演算法大致分為Distance Vector、Link State、Balanced Hybrid三種。
簡單來說,Distance Vector是用方向與所必須經過的設備數目(Hops)來決定路徑,並會在鄰近的路由器設備之間將這些路徑資料互相分享,而Link State則使用最短路徑演算法(Shortest Path First)。
Distance Vector路由演算法與Link State路由演算法最大的不同之處是,Link State演算法只會傳遞少部分更新的路由資料,而且把這樣的更新資料傳遞到各個路由器設備中,而Distance Vector路由演算法則會傳遞整份的資料,並且只傳遞給鄰近的路由器設備。
不過,即使路由資料沒有任何的改變,Distance Vector也會將整份路由資料發送出來,而這裡所謂的整份路由資料,指的就是發送端路由器設備中Routing Table的完整資料。
當鄰近的路由器設備收到這整份路由資料後,就會開始比較已知的路由路徑,並把已更新過的資料同步到本地端路由器設備內。因為這種方式會假設接收到的資料一定是比自己還要新的資料,所以通常也被稱為「謠言路由方式」(Routing by rumor)。
也是因為這樣類似「以訛傳訛」的運作方式,所以會衍生出其他問題,幸好目前這些問題都已經有對應的解決方案。