動態路由
路由協定的二個類別,大部分路由演算法可區分成二類別之一:
距離向量路由法決定到在互連網路上的任何鏈路的方向或向量和距離。鏈路狀態法會真正產生整個互連網路的真正拓樸。
距離向量路由協定(distance vector routing protocol)
距離向量路由演算法周期性地傳遞從路由器到路由器的路由表的複本。這些規律的路由器間的更新溝通拓樸改變。距離向量路由演算法也被稱為Bellman-Ford 演算法。
每個路由器收到從它的直接相連的鄰居路由器來的路由表。路由器B收到從路由器A 來的資訊。路由器 B 加上距離向量數,諸如跳躍數(number of hops)。此數增加距離向量。然後路由器 B 傳遞此新的路由表到它的其他的鄰居,路由器C。相同的逐步程序發生在鄰居路由器的所有方向。
演算法最終是要聚集網路距離,以致它能維護一個網路拓樸資訊的資料庫。然而,距離向量演算法不允許路由器知道互連網路的真正拓樸,因為每個路由器只看到它的鄰居路由器。
使用距離向量路由的每個路由器首先識別它的鄰居。引導到每個直接連接網路的介面有0的距離。當距離向量發現程序進行,路由器依據他們從每個鄰居路由器收到的資訊來發現到目的地網路的最佳路徑。路由器 A 認知其他網路是依據從路由器B收到的資訊。在路由表的每個其他的網路登錄點有一個累積的距離向量來顯示給予方向的網路有多遠。
當拓樸改變時,路由表更新會發生。如同網路發現程序,拓樸改變更新從路由器到路由器逐步進行。距離向量演算法要求每個路由器發送它的完整的路由表到每個它的鄰接鄰居。路由表包括關於由它的權值定義的總額路徑成本的資訊和在表格內的每個網路的路徑連到的第一路由器的邏輯位址,距離向量的一個比擬可為高速公路交流道上發現的標識。標識指向目的地和指出到目的地的距離。更沿著高速公路下去,另一個標識指向目的地,但是現在距離是較短的。只要距離愈短,交通是在最佳路徑上。
鏈路狀態演算法 (link-state algorithm )
鏈路狀態演算法也是被稱為 Dijkstra 的演算法或稱最短路徑優先 (SPF) 演算法。鏈路狀況路由演算法維護一個複雜的拓樸資訊的資料庫。距離向量演算法有關於遠離網路的非特定的資訊但是沒有遠離路由器的知識。鏈路狀態路由演算法維護遠離路由器的完整知識及他們如何互連。
鏈路狀態路由使用下列的功能:
Network discovery processes for link state routing
鏈結狀態路由的網路發現程序
當路由器交換 LSA,他們以直接相連網路開始,因為他們有相關的資訊。每個路由器建造由所有交換的
LSA 組成的拓樸資料庫。
SPF 演算法計算網路的可到達性。路由器建造此邏輯拓樸如同一棵樹木,以它自己當作樹根。此拓樸由到每個在鏈路狀態協定互連網路上的網路的所有可能的路徑組成。路由器然後使用SPF 來排序這些路徑。路由器列示最佳路徑和到這些目的地網路的介面到路由表內。它也維護其他的拓樸元件的資料庫和狀態細節。
認知鏈路狀態拓樸改變的第一個路由器傳送資訊,因此所有其他的路由器能使用它來更新。共通的路由資訊被傳送給在互連網路上的所有路由器。要達到收歛,每個路由器知道它的鄰居路由器。這包括每個鄰居路由器的名稱、介面狀況和連接到鄰居的鏈路的成本。路由器建造 LSA 封包,它列示新鄰居的資訊、鏈結成本的改變、不再有效的鏈路。LSA
封包隨後被送出,因此所有其他的路由器收到它。
當路由器收到一個 LSA ,它以最近的資訊更新路由表。蓄積的資料被用來產生互連網路地圖且 SPF 演算法被用來計算到其他網路的最短路徑。每次 LSA 封包導致鏈路狀態資料庫改變,SPF 重新計算最佳路徑和更新路由表。
SPF 演算法計算網路的可到達性。路由器建造此邏輯拓樸如同一棵樹木,以它自己當作樹根。此拓樸由到每個在鏈路狀態協定互連網路上的網路的所有可能的路徑組成。路由器然後使用SPF 來排序這些路徑。路由器列示最佳路徑和到這些目的地網路的介面到路由表內。它也維護其他的拓樸元件的資料庫和狀態細節。
認知鏈路狀態拓樸改變的第一個路由器傳送資訊,因此所有其他的路由器能使用它來更新。共通的路由資訊被傳送給在互連網路上的所有路由器。要達到收歛,每個路由器知道它的鄰居路由器。這包括每個鄰居路由器的名稱、介面狀況和連接到鄰居的鏈路的成本。路由器建造 LSA 封包,它列示新鄰居的資訊、鏈結成本的改變、不再有效的鏈路。LSA 封包隨後被送出,因此所有其他的路由器收到它。
當路由器收到一個 LSA ,它以最近的資訊更新路由表。蓄積的資料被用來產生互連網路地圖且 SPF
演算法被用來計算到其他網路的最短路徑。每次 LSA 封包導致鏈路狀態資料庫改變,SPF 重新計算最佳路徑和更新路由表。
認知鏈路狀態拓樸改變的第一個路由器傳送資訊,因此所有其他的路由器能使用它來更新。共通的路由資訊被傳送給在互連網路上的所有路由器。要達到收歛,每個路由器知道它的鄰居路由器。這包括每個鄰居路由器的名稱、介面狀況和連接到鄰居的鏈路的成本。路由器建造 LSA 封包,它列示新鄰居的資訊、鏈結成本的改變、不再有效的鏈路。LSA 封包隨後被送出,因此所有其他的路由器收到它。
當路由器收到一個 LSA ,它以最近的資訊更新路由表。蓄積的資料被用來產生互連網路地圖且 SPF 演算法被用來計算到其他網路的最短路徑。每次 LSA 封包導致鏈路狀態資料庫改變,SPF 重新計算最佳路徑和更新路由表。
和鏈路狀態協定相關的有三個主要關鍵點:
路由器使用鏈路狀態協定比使用距離向量路由協定的路由器需要更多記憶體和處理更多資料。
鏈路狀態路由器需要足夠的記憶體來含括從各種資料庫來的所有的資訊、拓樸樹和路由表。 啟始的鏈路狀態封包氾送會消耗頻寬。在啟始的發現程序,使用鏈路狀態路由協定的所有路由器發送 LSA 封包到所有其他路由器。此活動氾送到互連網路和暫時減低可用來載送使用者資料的繞送訊務交通的頻寬。 於此啟始氾送之後,鏈路狀態路由協定通常需要最小頻寬來發送不常的或事件觸發的反應拓樸改變的 LSA 封包。
- Distance vector 距離向量
- Link-state 鏈路狀態
距離向量路由法決定到在互連網路上的任何鏈路的方向或向量和距離。鏈路狀態法會真正產生整個互連網路的真正拓樸。
距離向量路由協定(distance vector routing protocol)
距離向量路由演算法周期性地傳遞從路由器到路由器的路由表的複本。這些規律的路由器間的更新溝通拓樸改變。距離向量路由演算法也被稱為Bellman-Ford 演算法。
每個路由器收到從它的直接相連的鄰居路由器來的路由表。路由器B收到從路由器A 來的資訊。路由器 B 加上距離向量數,諸如跳躍數(number of hops)。此數增加距離向量。然後路由器 B 傳遞此新的路由表到它的其他的鄰居,路由器C。相同的逐步程序發生在鄰居路由器的所有方向。
演算法最終是要聚集網路距離,以致它能維護一個網路拓樸資訊的資料庫。然而,距離向量演算法不允許路由器知道互連網路的真正拓樸,因為每個路由器只看到它的鄰居路由器。
使用距離向量路由的每個路由器首先識別它的鄰居。引導到每個直接連接網路的介面有0的距離。當距離向量發現程序進行,路由器依據他們從每個鄰居路由器收到的資訊來發現到目的地網路的最佳路徑。路由器 A 認知其他網路是依據從路由器B收到的資訊。在路由表的每個其他的網路登錄點有一個累積的距離向量來顯示給予方向的網路有多遠。
當拓樸改變時,路由表更新會發生。如同網路發現程序,拓樸改變更新從路由器到路由器逐步進行。距離向量演算法要求每個路由器發送它的完整的路由表到每個它的鄰接鄰居。路由表包括關於由它的權值定義的總額路徑成本的資訊和在表格內的每個網路的路徑連到的第一路由器的邏輯位址,距離向量的一個比擬可為高速公路交流道上發現的標識。標識指向目的地和指出到目的地的距離。更沿著高速公路下去,另一個標識指向目的地,但是現在距離是較短的。只要距離愈短,交通是在最佳路徑上。
鏈路狀態演算法 (link-state algorithm )
鏈路狀態演算法也是被稱為 Dijkstra 的演算法或稱最短路徑優先 (SPF) 演算法。鏈路狀況路由演算法維護一個複雜的拓樸資訊的資料庫。距離向量演算法有關於遠離網路的非特定的資訊但是沒有遠離路由器的知識。鏈路狀態路由演算法維護遠離路由器的完整知識及他們如何互連。
鏈路狀態路由使用下列的功能:
- Link-state
advertisement (LSA) - a small packet of routing
information that is sent between routers
鏈路狀態通告
(LSA) - 一個在路由器間傳送的路由資訊小封包 - Topological
database - a collection of information gathered from LSAs
拓樸資料庫 - 從LSA得到的資訊集合 - SPF algorithm - a calculation performed on the database that
results in the SPF tree
SPF 演算法 - 對資料庫執行計算以產生 SPF 樹 - Routing table - a list of the known paths and interfaces
路由表 -
己知路徑和介面的表列
Network discovery processes for link state routing
鏈結狀態路由的網路發現程序
當路由器交換 LSA,他們以直接相連網路開始,因為他們有相關的資訊。每個路由器建造由所有交換的
LSA 組成的拓樸資料庫。
SPF 演算法計算網路的可到達性。路由器建造此邏輯拓樸如同一棵樹木,以它自己當作樹根。此拓樸由到每個在鏈路狀態協定互連網路上的網路的所有可能的路徑組成。路由器然後使用SPF 來排序這些路徑。路由器列示最佳路徑和到這些目的地網路的介面到路由表內。它也維護其他的拓樸元件的資料庫和狀態細節。
認知鏈路狀態拓樸改變的第一個路由器傳送資訊,因此所有其他的路由器能使用它來更新。共通的路由資訊被傳送給在互連網路上的所有路由器。要達到收歛,每個路由器知道它的鄰居路由器。這包括每個鄰居路由器的名稱、介面狀況和連接到鄰居的鏈路的成本。路由器建造 LSA 封包,它列示新鄰居的資訊、鏈結成本的改變、不再有效的鏈路。LSA
封包隨後被送出,因此所有其他的路由器收到它。
當路由器收到一個 LSA ,它以最近的資訊更新路由表。蓄積的資料被用來產生互連網路地圖且 SPF 演算法被用來計算到其他網路的最短路徑。每次 LSA 封包導致鏈路狀態資料庫改變,SPF 重新計算最佳路徑和更新路由表。
SPF 演算法計算網路的可到達性。路由器建造此邏輯拓樸如同一棵樹木,以它自己當作樹根。此拓樸由到每個在鏈路狀態協定互連網路上的網路的所有可能的路徑組成。路由器然後使用SPF 來排序這些路徑。路由器列示最佳路徑和到這些目的地網路的介面到路由表內。它也維護其他的拓樸元件的資料庫和狀態細節。
認知鏈路狀態拓樸改變的第一個路由器傳送資訊,因此所有其他的路由器能使用它來更新。共通的路由資訊被傳送給在互連網路上的所有路由器。要達到收歛,每個路由器知道它的鄰居路由器。這包括每個鄰居路由器的名稱、介面狀況和連接到鄰居的鏈路的成本。路由器建造 LSA 封包,它列示新鄰居的資訊、鏈結成本的改變、不再有效的鏈路。LSA 封包隨後被送出,因此所有其他的路由器收到它。
當路由器收到一個 LSA ,它以最近的資訊更新路由表。蓄積的資料被用來產生互連網路地圖且 SPF
演算法被用來計算到其他網路的最短路徑。每次 LSA 封包導致鏈路狀態資料庫改變,SPF 重新計算最佳路徑和更新路由表。
認知鏈路狀態拓樸改變的第一個路由器傳送資訊,因此所有其他的路由器能使用它來更新。共通的路由資訊被傳送給在互連網路上的所有路由器。要達到收歛,每個路由器知道它的鄰居路由器。這包括每個鄰居路由器的名稱、介面狀況和連接到鄰居的鏈路的成本。路由器建造 LSA 封包,它列示新鄰居的資訊、鏈結成本的改變、不再有效的鏈路。LSA 封包隨後被送出,因此所有其他的路由器收到它。
當路由器收到一個 LSA ,它以最近的資訊更新路由表。蓄積的資料被用來產生互連網路地圖且 SPF 演算法被用來計算到其他網路的最短路徑。每次 LSA 封包導致鏈路狀態資料庫改變,SPF 重新計算最佳路徑和更新路由表。
和鏈路狀態協定相關的有三個主要關鍵點:
- Processor overhead 處理器額外負荷
- Memory requirements 記憶體需求
- Bandwidth consumption 頻寬消耗
路由器使用鏈路狀態協定比使用距離向量路由協定的路由器需要更多記憶體和處理更多資料。
鏈路狀態路由器需要足夠的記憶體來含括從各種資料庫來的所有的資訊、拓樸樹和路由表。 啟始的鏈路狀態封包氾送會消耗頻寬。在啟始的發現程序,使用鏈路狀態路由協定的所有路由器發送 LSA 封包到所有其他路由器。此活動氾送到互連網路和暫時減低可用來載送使用者資料的繞送訊務交通的頻寬。 於此啟始氾送之後,鏈路狀態路由協定通常需要最小頻寬來發送不常的或事件觸發的反應拓樸改變的 LSA 封包。