內部路由協定大觀園
細說Link-State路由演算法
胡凱捷
路由協定可以分成內部路由協定和外部路由協定兩大類型，而對於內部路由協定而言，所採用的路由演算法有三種類型：Distance Vector、Link State以及混合前面兩種的方法。而本文要介紹的是其中的Link-State路由演算法。
從運作方式來看，Link-State路由演算法比較複雜，不像Distance Vector路由演算法那樣簡單，雖然各種的路由協定可能大都是使用Distance Vector路由演算法如RIP、IGRP等等，但還是有部分路由協定採用Link-State路由演算法，因此對於專業的網路管理人員來說，這依然是必備的專業知識之一。在這篇文章中，除了會解釋Link-State路由演算法如何維護路由相關的資訊，還會提及Link-State路由演算法的優點和缺點，以及使用Link-State路由演算法所必須注意的地方。
路由協定在自治系統的分類
路由協定有很多分類的方式，其中一種分類方式是根據自治系統的運作範圍來做分類。自治系統，就是指Autonomous System，簡稱為AS。一個自治系統是所有處於相同管理網域（Administrative Domain）下所有網路的集合，而一個管理網域指的是主機、路由器與內部連接網路的集合，而這個集合是歸屬於相同管理下運作的。
有些路由協定是運作在同一個自治系統中，而某些路由協定則運作在不同的自治系統之間。若以運作於自治系統的內部與外部來區分路由協定，則可以分成內部路由協定（Interior Gateway Protocol）與外部路由協定（Exterior Gateway Protocol）。內部路由協定簡稱為IGP，外部路由協定則簡稱為EGP。屬於內部路由協定的路由協定包含RIPv1、RIPv2、IGRP、EIGRP和OSPF。而屬於外部路由協定的路由協定則有BGP。而本文將著重在內部路由協定的部分。
路由演算法的分類
對於內部路由協定而言，其所採用的路由演算法大致分為以下三種： 1. Distance Vector 2. Link State 3. 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）。就是因為這樣類似「以訛傳訛」的運作方式，所以會產生一些問題，但幸好這些問題都已經有了對應的解決方案。
Link-State路由演算法簡介
所謂路由演算法，就是如何選擇網路路徑以便於發送網路封包。而Link-State路由演算法，其實就是使用所謂的最短路徑優先演算法（Shortest Path First，SPF）來決定網路路徑，顧名思義，就是以最短的網路路徑為最佳網路路經的優先考量，Link-State路由演算法就是用這種方式來維護其存放網路路徑的資料庫內容。
Link-State路由演算法會使用以下五種資訊來維護整個路由資訊：
1. LSA（Link-State Advertisements） 2. 網路拓樸資料庫（Topological Database） 3. 最短路徑優先演算法（SPF） 4. 最短路經優先（SPF）樹狀結構 5. 存放網路路徑的Routing Table
其中，網路拓樸資料庫也被稱為Neighbor-ship Database，而最短路徑優先（SPF）樹狀結構也稱為Link-State Database，而最後用來存放網路路徑的Routing Table就相當於存放「最佳路徑」的地方。 經典的Link-State路由演算法有OSPF路由協定和IS-IS路由協定，其中OSPF的概念與相關詳細運作內容被定義在RFC 2328文件中，有興趣的讀者可以前往閱讀，其RFC 2328的網址是「http://www.ietf.org/rfc/rfc2328.txt」。
基本上，Link-State路由演算法會從其他路由器中收集有關於整個網路的路徑資訊，也就是說，整個網路中所有的路由器會互相交換並傳遞所知的網路路徑資訊。到最後，每一台網路中的路由器設備都會對整個網路有一定的了解，因此整個網路上的每一台路由器設備都會有整個網路的路徑表，等到收集完整個網路的路徑資訊之後，每一台路由器設備自行計算屬於自己的「最佳網路路徑」，而這樣的資訊在各個路由器設備之間是不完全相同的。
事實上，Link-State路由演算法這樣的設計主要是用來彌補Distance Vector路由演算法的缺點。Link-State路由演算法能夠針對網路的變化做出比較快速的回應動作。當網路有所變化的時候，Link-State路由演算法會發送更新過的網路路徑資訊，而平常的時候，Link-State路由演算法也會固定發送路徑更新資訊，預設是每隔30秒做一次。根據這樣的概念，整個網路上所有的路由器設備在一段時間之後，彼此之間的網路拓樸資料庫內容就越能一致，因為資料會互相做同步的動作。
為什麼要稱為Link-State路由演算法？其實這裡所指的Link是代表路由器設備的連接埠介面，而State所代表的是由某個介面連接到鄰近路由器設備的連線關係資訊，這連線關係的資訊包含：連接埠介面上的IP位址、子網路遮罩、所連接的網路種類以及所連接的鄰近路由器設備的資訊等等。
而這些Link和State所累積起來的資料就是這裡所指的Link-State的意思，也是代表網路拓樸資料庫的內容。而網路拓樸資料庫是用來計算網路中的最佳網路路徑，計算方式是使用著名的Dijkstra SPF演算法，並會建立SPF的樹狀結構。而最佳網路路徑會從SPF樹狀結構中選出，然後放到Routing Table之中。
當網路發生問題時，Link-State路由演算法就會開始發送LSA網路封包，其發送的方法是透過群播（Multicast）的方式來對整個所在網路做發送的動作。當網路上所有套用Link-State路由演算法的路由器設備收到這樣的LSA封包之後，會複製一份LSA給自己用，而這份LSA會拿來更新自己的網路拓樸資料庫的內容，然後再把原本的LSA轉發給其他鄰近的路由器設備。
一旦有任何的路由器設備發送LSA封包出來，就會讓所有的路由器設備重新計算自己的網路路徑，更新它們的Routing Table，也因為這樣，所以單一個網路中，使用Link-State路由演算法的路由器設備最好不要太多，不然網路一旦發生變化，就會迫使整個網路的所有路由器設備全都重新計算Routing Table和最佳網路路徑等資料。
這樣設計的結果是，所有使用Link-State路由演算法的路由器都會持有一份完整的網路拓樸資訊，當然包含這些網路之間是如何連接等種種資料。另外，LSA的觸發是當網路變化時就會馬上送出，所以網路資料「收斂」速度比較快。
Link-State的雙層網路架構 Link-State路由演算法提供兩層式的網路架構環境，而在這兩層的網路架構中，有Area和Autonomous System這兩個主要的構成元素。
其中，Autonomous System又稱為自治系統，有時候也稱為Domain，一個自治系統包含一堆使用相同路由設定的網路，而一個自治系統可以分成多個Area。一個Area指的是一群連續的網路，多個Area可組合成一個自治系統。而整個雙層式網路架構如下圖所示：
 |
| ▲兩層式網路架構環境 |
上圖中，中間的網路區段與下面兩個網路區段所形成的網路就是自治系統。在每一個自治系統中，必須有一個稱為Backbone Area的網路，這個Backbone Area是與外部路由網路互相連接的區段，也負責外部路由網路與自治系統內部其他網路的溝通，所以也就是Transition Area。除了Backbone Area之外，自治系統中其他的網路區段就是Non-Backbone Area。
這裡必須注意的是，自治系統中所有的Non-Backbone Area都必須連接到Backbone Area上，而在OSPF路由協定中，Non-Backbone Area可以被設定成為Stub Area或設定為Stubby Area，也可以設定成所謂的NSSA（Not-So-Stubby Area）網路，以便於降低Link-State路由演算法所需的資料庫大小，也可以減少Routing Table的資料筆數，而提升網路整體的效能。
在這種雙層式網路架構中，各個路由器都扮演著許多不同的角色，而每種角色在OSPF路由協定和IS-IS路由協定中的名稱又不相同，以下就分別列出在這種網路架構中的各種路由器角色：
1. 在Backbone Area中，路由器C在OSPF路由協定中稱為Backbone Router，而在IS-IS路由協定中又稱為L2 Router。這種角色的路由器的工作就是提供不同Area之間的連接性。
2. 在Backbone Area中，Router B被稱為Autonomous System Boundary Router（ASBR），亦即自治系統邊界路由器，用來連接外部路由網域和自治系統。
3. 在Non-Backbone Area中，路由器D和路由器E在OSPF路由協定中稱為Area Border Routers（ABRs），而在IS-IS路由協定中則被稱為L1/L2 Routers。這種路由器用於連接不同的Area，並維護所連接Area的Link-State路由資料庫，當然也負責轉送封包到其他的Area中。
4. 在Non-Backbone Area中，除了ABR（也就是L1/L2 Routers）之外的其他路由器，在OSPF路由協定中都稱為Non-Backbone Internal Router，而在IS-IS路由協定中則稱為L1 Routers。因為這種路由器是接在Non-Backbone Area的內部，所以所接觸的網路只限於Non-Backbone Area內部，也因此，這些路由器只須要維護所屬Area相對應的路由資料庫即可。
而路由器A當然是屬於其他的自治系統。另外，ABR會向內部Area中其他路由器發送預設路由設定，讓所有其他路由器的預設路由都指向ABR，如此一來，當Non-Backbone Internal Router要發送網路封包到其他Area時，就會送到ABR的手上。
Link-State路由演算法的優點
Link-State路由演算法採用雙層式網路架構，此種網路架構最大的優點就是，因為分成多個獨立的Area，所以可以減少Routing Table中的資料筆數，提升網路效能。另一個優點就是，每一個Area中的網路異常都不會影響其他Area網路的正常運作。如果拿Link-State路由演算法與一般傳統式的Distance Vector路由演算法比較，Link-State路由演算法所具備的優點如下（這裡所取用的Distance Vector路由演算法的範例為RIPv1或RIPv2）：
Link-State路由演算法根據實際的網路路徑成本來考量並選擇出最佳網路路徑，而這樣的成本計算更能反映出網路路徑的好壞。另外，Link-State路由演算法的路由資料更新頻率比較不高。 由於Link-State路由演算法將網路區分成雙層式網路架構，而在這種架構中，也分成多個Area，因為在同一個Area中所發生的網路變動，是不會影響到其他Area，所以路由資料的更新範圍比較小，網路改變所造成的影響也比較少，並不需要牽動到整個網路所有的路由器。
另外，最重要的當然就是Link-State路由演算法可以用最快的速度達到網路路由收斂，因為一旦網路發生變化，Link-State路由演算法可以馬上送出更新過後的網路狀況給同質性網路中的所有路由器，所以收斂速度自然比Distance Vector路由演算法還快。也因為每個路由器都有完整的網路路徑資料，所以很難發生類似Distance Vector那樣的路由迴圈（Routing Loop）的狀況。
之前所提到的LSA網路封包，其實裡面會有序號，其所具備的資料也是有時限性的，就因為如此，所以套用Link-State路由演算法的路由器會選擇最新的LSA封包，並參考其裡面的內容。
除此之外，若有優良的網路設計，就可以減少Link-State路由演算法中網路拓樸資料庫的資料筆數，這樣一來，就可以減少SPF演算法的計算次數，也可以降低演算法所需的時間。 Link-State路由演算法的網路設定一般而言還算蠻簡單的，但也不會因此而失去原有能力。如果套用到比較複雜的網路環境時，可以調整Link-State路由演算法設定參數值，也可以讓設定比較複雜且具有彈性，也就是說，Link-State路由演算法適用於簡單及複雜的網路環境。
而在疑難排解方面，Link-State路由演算法也比Distance Vector路由演算法來得容易許多，這裡指的是當網路管理人員要做疑難排解時，毋須牽動到太多路由器設備，因為每一台路由器設備都擁有整個網路的路由資料。
Link-State路由演算法的缺點
雖然上面列出不少Link-State路由演算法的優點，但其實Link-State路由演算法還是有許多的缺點，以下就分別列出關於Link-State路由演算法的缺點。
Link-State路由演算法要維護的資料比較多，也比較複雜，與Distance Vector路由演算法比較起來，Link-State路由演算法除了Routing Table之外，還要維護網路拓樸資料庫（Topology Database）、鄰近設備資料庫（Adjacency Database）和封包轉發資料庫（Forwarding Database）。一旦網路環境比較複雜的時候，這些資料所占用的記憶體就會很多。所以，硬體設備的需求就會比較大。
因為Link-State路由演算法是使用Dijkstra的最短路徑演算法來計算網路中的最短路徑，而這種演算法需要大量的CPU運算時間，所以如果網路架構很大或是擁有很複雜的網路架構時，Link-State路由演算法就會占用許多CPU運算。此外，如果網路中常常發生設備不穩定或是網路連線不穩定的情況，就會造成Dijkstra演算法計算頻率升高，如此一來，也會讓CPU使用率飆高。
前面提到因為Link-State路由演算法可能會讓CPU使用率飆漲，也會占用大量記憶體，所以可能的解決方案就會是盡可能地善用雙層式網路架構，並且切割成多個Area，這樣每個Area中的網路就會比較簡單，同一個Area中的Link-State路由演算法計算次數也會比較少，而且Routing Table和各種資料庫中的資料筆數也會比較少，但前提是這樣的網路設計會有很多很多限制，例如切割好的各個Area網路必須是連續性的，而且每個Area中的每一台路由器設備必須永遠都能接收並且發送LSA網路封包到同一個Area中的其他路由器設備。
此外，每個Area中的Area Border Router都必須能夠連接到Backbone Area上，不然的話，這個Area就沒有辦法和其他的Area作資料傳輸的動作。
而在複雜的網路架構中，雖然可以把Link-State路由演算法的設定調整成可以適用於複雜的網路，但是設定的方式相當麻煩，將會是一項相當大的挑戰。
前面關於Link-State路由演算法的優點中提到，疑難排解會比較簡單，其理由不外乎是因為Link-State路由演算法會將整個網路的資訊全部儲存起來，所以對某一台路由器設備做疑難排解，還不至於需要動用其他路由器設備，但由於資料又多又複雜，所以必須對Link-State路由演算法有相當的了解才能進行比較順利的疑難排解。 此外，在套用Link-State路由演算法的一開始，由於對於每一台路由器設備而言，都需要完整的網路資訊，但是在套用初期，每一台路由器設備都沒有這樣的資訊，因此所有設備會在一開始瘋狂傳遞LSA網路封包，以便互相分享網路的所有資訊，但是這個時候，整個網路可能就沒有辦法傳遞其他正常的網路封包。雖然這種情況只會發生在套用Link-State路由演算法最開始的時期，但是這種影響卻非常容易被觀察出來。
混合式路由協定截長補短
以前文章所提到的Distance Vector路由演算法以及這一篇文章所提到的Link-State路由演算法，從中不難看出，這兩種路由演算法似乎各有好壞。簡單的路由演算法，雖然好用，但是卻容易發生問題，而複雜的路由演算法雖然問題比較少，但卻需要花費比較多的資源（如CPU運算、記憶體空間、初期網路頻寬）。
為此，出現了採用Distance Vector路由演算法和Link-State路由演算法的混合式路由協定。而Cisco專屬的EIGRP路由協定正是使用這種混合式的作法。
大致而言，這種混合式的路由協定會採用Distance Vector路由演算法，將之套用在比較精確的資料上，以便於決定網路上的最佳路徑。何謂比較精確的資料？因為這種混合式的路由協定雖然在這方面是採用Distance Vector路由演算法的方式，但卻和一般的Distance Vector路由演算法不同，這種混合式的路由協定並不會定期發送網路的狀態與資訊的更新。
這裡所採用的方式是當網路發生變化時，馬上發送相關的網路資訊給每個路由器，去觸發這種路由更新的動作，在這方面算是學習到Link-State路由演算法的優點，去除了Distance Vector路由演算法的缺點。
也因為這樣，這種混合式的路由協定，其網路路由收斂速度比原本的Distance Vector路由演算法還要快上許多。不僅如此，這種混合式的路由方式也不會像Link-State路由演算法一樣會耗費大量的CPU資源、記憶體資源和網路資源。在這方面，混合式路由協定所強調的是更經濟的作法。
如何選擇適用的路由演算法
那麼到底怎樣的情況下要採用Link-State路由演算法呢？當然這就是網路管理人員所需要思考的問題。這裡筆者提出一些可以思考的地方讓讀者做參考。首先，要看看讀者所負責的網路架構，如果每個網路區段的路由器設備相當多的話，基本上不太建議使用Link-State路由演算法，因為LSA封包的更新在路由器設備數目很高的情況之下，很可能造成一定的負擔。
如果路由器設備的硬體規格（CPU和記憶體等等）還算不錯的話，可以考慮使用Link-State路由演算法。讀者看完這篇文章的介紹，應該也能體會到Link-State路由演算法需要比較好的硬體設備來處理路由資料，無論是儲存或運算都是如此。否則，還是使用Distance Vector路由演算法會比較適合。
結語
本文講述了Link-State路由演算法的詳細運作流程、儲存資料的方式、所使用的雙層式網路架構，還有在這樣的雙層式網路架構中，各個路由器所扮演的角色。當然，最重要的莫過於最後拿Link-State路由演算法與Distance Vector路由演算法來比較的優缺點，各位讀者也可以自行比較Link-State路由演算法與Distance Vector路由演算法的差異，這將有助於了解這兩種演算法的不同。最後也提到混合式路由協定的產生，就結合了這兩種路由演算法的優點，也就是著名的Cisco EIGRP路由協定。
