內部路由協定大觀園 細說Link-State路由演算法
內部路由協定大觀園 細說 Link-State 路由演算法
這學期研究所 - 碩士二年級 的 電腦網路 Computer Networking 課。教授出的作業二裡的，其中一題，是有關 Show how, step by step. Node A constructs its routing table using Link-state routing and Distance Vector routing, respectively.
在寫這一題時，遇到問題。去請教我們公司資訊部網管的一位好同事，他教我怎麼看和怎麼算 Link-state routing and Distance Vector routing。
路由協定可以分成內部路由協定和外部路由協定兩大類型，而對於內部路由協定而言，所採用的路由演算法有三種類型：Distance Vector、Link State以及混合前面兩種的方法。而本文要介紹的是其中的Link-State路由演算法。
LS演算法和DS演算法的比較
路由演算法的分類
對於內部路由協定而言，其所採用的路由演算法大致分為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）。
也是因為這樣類似「以訛傳訛」的運作方式，所以會衍生出其他問題，幸好目前這些問題都已經有對應的解決方案。
對於內部路由協定而言，其所採用的路由演算法大致分為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）。
也是因為這樣類似「以訛傳訛」的運作方式，所以會衍生出其他問題，幸好目前這些問題都已經有對應的解決方案。
Link-State路由演算法簡介
所謂的路由演算法，就是如何選擇網路路徑以便於發送網路封包。而Link-State路由演算法，其實是使用所謂的SPF（Shortest Path First，最短路徑優先）演算法來決定網路路徑，顧名思義，就是以最短的網路路徑為最佳網路路經的優先考量，Link-State路由演算法就是採用這種方式來維護其存放網路路徑的資料庫內容。
Link-State路由演算法的儲存資料
Link-State路由演算法會使用以下五種資訊來維護整個路由資訊：
· LSA（Link-State Advertisements）
· 網路拓撲資料庫（Topological Database）
· 最短路徑優先演算法（SPF）
· 最短路徑優先樹狀結構
· 存放網路路徑的Routing Table
其中，網路拓撲資料庫也被稱為Neighbor-ship Database，而最短路徑優先樹狀結構也被稱為Link-State Database，而最後用來存放網路路徑的Routing Table就相當於存放「最佳路徑」的地方。
所謂的路由演算法，就是如何選擇網路路徑以便於發送網路封包。而Link-State路由演算法，其實是使用所謂的SPF（Shortest Path First，最短路徑優先）演算法來決定網路路徑，顧名思義，就是以最短的網路路徑為最佳網路路經的優先考量，Link-State路由演算法就是採用這種方式來維護其存放網路路徑的資料庫內容。
Link-State路由演算法的儲存資料
Link-State路由演算法會使用以下五種資訊來維護整個路由資訊：
· LSA（Link-State Advertisements）
· 網路拓撲資料庫（Topological Database）
· 最短路徑優先演算法（SPF）
· 最短路徑優先樹狀結構
· 存放網路路徑的Routing Table
其中，網路拓撲資料庫也被稱為Neighbor-ship Database，而最短路徑優先樹狀結構也被稱為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路由演算法這樣的設計主要是用來彌補Distance Vector路由演算法的缺點。Link-State路由演算法能夠針對網路的變化做出比較快速的回應動作。
當網路有所變化時，Link-State路由演算法會發送更新過的網路路徑資訊，而平常的時候，Link-State路由演算法也會固定發送路徑更新資訊，預設上是每隔30秒發送一次。根據這樣的概念，時間久了之後，整個網路上所有的路由器設備之間的網路拓撲資料庫內容就能愈趨一致，因為資料會互相做同步的動作。
為何稱為Link-State路由演算法
為什麼要稱為Link-State路由演算法？其實這裡所指的Link是代表路由器設備的連接埠介面，而State所代表的是由某個介面連接到鄰近路由器設備的連線關係資訊。
此連線關係的資訊包含：連接埠介面上的IP位址、子網路遮罩、所連接的網路種類，以及所連接的鄰近路由器設備的資訊等等。這些Link和State所累積起來的資料，就是這裡所指的Link-State的意思，也是代表網路拓撲資料庫的內容。
網路拓撲資料庫是用來計算網路中的最佳網路路徑，計算方式是使用著名的Dijkstra SPF演算法，並且會建立SPF的樹狀結構，而最佳網路路徑會從SPF樹狀結構中選出，然後放到Routing Table內。
為什麼要稱為Link-State路由演算法？其實這裡所指的Link是代表路由器設備的連接埠介面，而State所代表的是由某個介面連接到鄰近路由器設備的連線關係資訊。
此連線關係的資訊包含：連接埠介面上的IP位址、子網路遮罩、所連接的網路種類，以及所連接的鄰近路由器設備的資訊等等。這些Link和State所累積起來的資料，就是這裡所指的Link-State的意思，也是代表網路拓撲資料庫的內容。
網路拓撲資料庫是用來計算網路中的最佳網路路徑，計算方式是使用著名的Dijkstra SPF演算法，並且會建立SPF的樹狀結構，而最佳網路路徑會從SPF樹狀結構中選出，然後放到Routing Table內。
Link-State路由演算法的優點
由於Link-State路由演算法是使用雙層式網路架構，這種網路架構最大的優點就是，因為分成多個獨立的Area，所以能夠減少Routing Table中的資料筆數，提升網路效能。
另一個優點就是，每個Area內的網路異常都不會影響其他Area網路的正常運作。所以如果拿Link-State路由演算法與一般傳統式的Distance Vector路由演算法來比較的話，Link-State路由演算法所具備的優點如下所列（這裡所取用的Distance Vector路由演算法的範例為RIPv1或RIPv2）：
1. Link-State路由演算法根據實際的網路路徑成本來 考量並選擇出最佳網路路徑，而這樣的成本計算更能反映出網路路徑的好壞。
2. Link-State路由演算法的路由資料更新頻率比較不 那麼高。
3. Link-State路由演算法將網路區分成雙層式網路架 構，而在這種架構內也分成多個Area，因為在同一個Area中所發生的網路變動，並不會影響到其他Area，所以路由資料的更新範圍比較小。此外，網路改變所造成的影響也比較少，並不需要牽動到整個網路所有的路由器。
4. Link-State路由演算法可用最快的速度達到網路路 由收斂，因為當網路發生變化時，Link-State路由演算法可以馬上送出更新過後的網路狀況給同質性網路內的所有路由器，所以收斂速度自然比Distance Vector路由演算法快。
5. 因為每個路由器都有完整的網路路徑資料，所以事 實上不太可能會發生像Distance Vector那樣的路由迴圈（Routing Loop）狀況。
6. 之前所提到的LSA網路封包，其實裡面是有序號 的，其所具備的資料也是有時限性的，所以套用Link-State路由演算法的路由器會選擇最新的LSA封包，並參考其裡面的內容。
7. 若有優良的網路設計，就可以減少Link-State路由 演算法中網路拓撲資料庫的資料筆數，這樣就可以減少SPF演算法的計算次數，也能夠降低演算法所花費的時間。
8. Link-State路由演算法的網路設定一般而言還算蠻 簡單的，但也不會因為如此就失去它原有的能力。當套用到比較複雜的網路環境時，藉由調整Link-State路由演算法設定參數值，也可以讓設定比較複雜且具有彈性，換句話說，Link-State路由演算法適用於簡單的網路環境，也可以應用在複雜的網路環境。
9. 在疑難排解上，Link-State路由演算法也比Distance Vector路由演算法來得更容易，這裡指的是當網路管理人員要做疑難排解時，不需要牽動到太多路由器設備，因為每一台路由器設備都擁有整個網路的路由資料。
Link-State路由演算法的缺點
雖然上面列出了不少Link-State路由演算法的優點，但Link-State路由演算法還是有許多的缺點，以下就來加以說明：
1. Link-State路由演算法要維護的資料較多，也比 較複雜，與Distance Vector路由演算法相較，Link-State路由演算法除了Routing Table外，還要維護網路拓撲資料庫（Topology Database）、鄰近設備資料庫（Adjacency Database）以及封包轉發資料庫（Forwarding Database），所以一旦網路環境較為複雜時，這些資料所佔用的記憶體就會很多，所以硬體設備的需求較大。
2. 因為Link-State路由演算法是使用Dijkstra的最短路 徑演算法來計算網路內的最短路徑，而這種演算法需要大量的CPU運算時間，所以當網路架構很龐大，或者擁有很複雜的網路架構時，Link-State路由演算法就會佔用許多CPU運算。此外，如果網路中經常發生設備不穩定或網路連線不穩的情況，就會造成Dijkstra演算法計算頻率升高，如此一來也會讓CPU使用率飆高。
3. 前面提到，因為Link-State路由演算法可能讓CPU 使用率飆漲，也會佔用大量記憶體，所以可能的解決方案就是盡可能地善用雙層式網路架構，並且切割成多個Area，如此一來，每個Area內的網路就會比較簡單，同一個Area中的Link-State路由演算法計算次數也會比較少，而且Routing Table以及各種資料庫內的資料筆數也會較少。但是，這樣的網路設計會有許多的限制，例如切割好的各個Area網路必須是連續性的，而且每個Area中的每一台路由器設備要永遠都能接收並且發送LSA網路封包到同一個Area中的其他路由器設備。此外，每個Area中的Area Border Router都必須能夠連接到Backbone Area上，不然的話，這個Area就沒有辦法與其他的Area做資料傳輸的動作。
4. 在複雜的網路架構中，雖然可以把Link-State路由 演算法的設定調整成能夠適用於複雜的網路，但是設定的方式相當麻煩，是一項相當大的挑戰。
5. 前面關於Link-State路由演算法優點的介紹中提 到，疑難排解會比較簡單，其理由不外乎是因為Link-State路由演算法會將整個網路的資訊全部儲存起來，所以對某一台路由器設備做疑難排解時，還不至於需要動用其他路由器設備，但由於資料多且複雜，所以必須對Link-State路由演算法有相當的了解，才能較順利地疑難排解。
由於Link-State路由演算法是使用雙層式網路架構，這種網路架構最大的優點就是，因為分成多個獨立的Area，所以能夠減少Routing Table中的資料筆數，提升網路效能。
另一個優點就是，每個Area內的網路異常都不會影響其他Area網路的正常運作。所以如果拿Link-State路由演算法與一般傳統式的Distance Vector路由演算法來比較的話，Link-State路由演算法所具備的優點如下所列（這裡所取用的Distance Vector路由演算法的範例為RIPv1或RIPv2）：
1. Link-State路由演算法根據實際的網路路徑成本來 考量並選擇出最佳網路路徑，而這樣的成本計算更能反映出網路路徑的好壞。
2. Link-State路由演算法的路由資料更新頻率比較不 那麼高。
3. Link-State路由演算法將網路區分成雙層式網路架 構，而在這種架構內也分成多個Area，因為在同一個Area中所發生的網路變動，並不會影響到其他Area，所以路由資料的更新範圍比較小。此外，網路改變所造成的影響也比較少，並不需要牽動到整個網路所有的路由器。
4. Link-State路由演算法可用最快的速度達到網路路 由收斂，因為當網路發生變化時，Link-State路由演算法可以馬上送出更新過後的網路狀況給同質性網路內的所有路由器，所以收斂速度自然比Distance Vector路由演算法快。
5. 因為每個路由器都有完整的網路路徑資料，所以事 實上不太可能會發生像Distance Vector那樣的路由迴圈（Routing Loop）狀況。
6. 之前所提到的LSA網路封包，其實裡面是有序號 的，其所具備的資料也是有時限性的，所以套用Link-State路由演算法的路由器會選擇最新的LSA封包，並參考其裡面的內容。
7. 若有優良的網路設計，就可以減少Link-State路由 演算法中網路拓撲資料庫的資料筆數，這樣就可以減少SPF演算法的計算次數，也能夠降低演算法所花費的時間。
8. Link-State路由演算法的網路設定一般而言還算蠻 簡單的，但也不會因為如此就失去它原有的能力。當套用到比較複雜的網路環境時，藉由調整Link-State路由演算法設定參數值，也可以讓設定比較複雜且具有彈性，換句話說，Link-State路由演算法適用於簡單的網路環境，也可以應用在複雜的網路環境。
9. 在疑難排解上，Link-State路由演算法也比Distance Vector路由演算法來得更容易，這裡指的是當網路管理人員要做疑難排解時，不需要牽動到太多路由器設備，因為每一台路由器設備都擁有整個網路的路由資料。
Link-State路由演算法的缺點
雖然上面列出了不少Link-State路由演算法的優點，但Link-State路由演算法還是有許多的缺點，以下就來加以說明：
1. Link-State路由演算法要維護的資料較多，也比 較複雜，與Distance Vector路由演算法相較，Link-State路由演算法除了Routing Table外，還要維護網路拓撲資料庫（Topology Database）、鄰近設備資料庫（Adjacency Database）以及封包轉發資料庫（Forwarding Database），所以一旦網路環境較為複雜時，這些資料所佔用的記憶體就會很多，所以硬體設備的需求較大。
2. 因為Link-State路由演算法是使用Dijkstra的最短路 徑演算法來計算網路內的最短路徑，而這種演算法需要大量的CPU運算時間，所以當網路架構很龐大，或者擁有很複雜的網路架構時，Link-State路由演算法就會佔用許多CPU運算。此外，如果網路中經常發生設備不穩定或網路連線不穩的情況，就會造成Dijkstra演算法計算頻率升高，如此一來也會讓CPU使用率飆高。
3. 前面提到，因為Link-State路由演算法可能讓CPU 使用率飆漲，也會佔用大量記憶體，所以可能的解決方案就是盡可能地善用雙層式網路架構，並且切割成多個Area，如此一來，每個Area內的網路就會比較簡單，同一個Area中的Link-State路由演算法計算次數也會比較少，而且Routing Table以及各種資料庫內的資料筆數也會較少。但是，這樣的網路設計會有許多的限制，例如切割好的各個Area網路必須是連續性的，而且每個Area中的每一台路由器設備要永遠都能接收並且發送LSA網路封包到同一個Area中的其他路由器設備。此外，每個Area中的Area Border Router都必須能夠連接到Backbone Area上，不然的話，這個Area就沒有辦法與其他的Area做資料傳輸的動作。
4. 在複雜的網路架構中，雖然可以把Link-State路由 演算法的設定調整成能夠適用於複雜的網路，但是設定的方式相當麻煩，是一項相當大的挑戰。
5. 前面關於Link-State路由演算法優點的介紹中提 到，疑難排解會比較簡單，其理由不外乎是因為Link-State路由演算法會將整個網路的資訊全部儲存起來，所以對某一台路由器設備做疑難排解時，還不至於需要動用其他路由器設備，但由於資料多且複雜，所以必須對Link-State路由演算法有相當的了解，才能較順利地疑難排解。
如何選擇適用的路由演算法
到底在怎樣的情況下需要採用Link-State路由演算法呢？當然這就是網路管理人員所必須思考的問題。這裡提出一些可以思考的地方供大家參考。
首先，要看看本身所負責的網路架構，如果每個網路區段的路由器設備相當多，基本上並不建議使用Link-State路由演算法，因為LSA封包的更新，在路由器設備數目很高的情況下很可能造成負擔。
如果路由器設備的硬體規格（如CPU和記憶體等）還算不錯的話，是可以考慮使用Link-State路由演算法。看完這篇文章的介紹後，應該就可以知道Link-State路由演算法需要比較好的硬體設備來處理路由資料，無論是儲存或是運算都需要。否則的話，還是使用Distance Vector路由演算法比較適合。
到底在怎樣的情況下需要採用Link-State路由演算法呢？當然這就是網路管理人員所必須思考的問題。這裡提出一些可以思考的地方供大家參考。
首先，要看看本身所負責的網路架構，如果每個網路區段的路由器設備相當多，基本上並不建議使用Link-State路由演算法，因為LSA封包的更新，在路由器設備數目很高的情況下很可能造成負擔。
如果路由器設備的硬體規格（如CPU和記憶體等）還算不錯的話，是可以考慮使用Link-State路由演算法。看完這篇文章的介紹後，應該就可以知道Link-State路由演算法需要比較好的硬體設備來處理路由資料，無論是儲存或是運算都需要。否則的話，還是使用Distance Vector路由演算法比較適合。
留言
張貼留言