路由表的建立算法

1、路由表

1）什么是路由表

路由表是指路由器或者其他互聯網網絡設備上存儲的一張路由信息表，該表中存有到達特定網絡終端的路徑，在某些情況下，還有一些與這些路徑相關的度量。

2）路由表分類

（1）靜態路由表

由系統管理員事先設置好固定的路由表稱之為靜態路由表，一般是在系統安裝時就根據網絡的配置情況預先設定的，它不會隨未來網絡結構的改變而改變。

（2）動態路由表

動態路由表是路由器根據網絡系統的運行情況而自動調整的路由表。路由器根據路由選擇協議（Routing Protocol）提供的功能，自動學習和記憶網絡運行情況，在需要時自動計算數據傳輸的最佳路徑。

2、路由表項

• 目的地址：用來標識IP包的目的地址或者目的網絡。

• 網絡掩碼：與目的地址一起標識目的主機或者路由器所在的網段的地址。

pre：標識路由加入IP路由表的優先級?？赡艿竭_一個目的地有多條路由，但是優先級的存在讓他們先選擇優先級高的路由進行利用。

cost：路由開銷，當到達一個目的地的多個路由優先級相同時，路由開銷最小的將成為最優路由。

interface：輸出接口，說明IP包將從該路由器哪個接口轉發。

nexthop：下一跳IP地址，說明IP包所經過的下一個路由器。

3、路由表的相關算法

1）總體式路由算法。

采用總體式路由算法時，每個路由器都擁有網絡中所有其他路由器的全部信息以及網絡的流量狀態。這些算法也被稱為LS（鏈路狀態）算法。

2）分散式路由算法

采用分散式路由算法時，每個路由器只有與它直接相連的路由器的信息——而沒有網絡中的每個路由器的信息。這些算法也被稱為DV（距離向量）算法。

距離向量路由算法，也叫做最大流量演算法，其被距離向量協議作為一個算法，如RIP就是一種分布式的基于距離向量的路由選擇協議。使用這個算法的路由器必須掌握這個距離表，它告訴在網絡中每個節點的最遠和距離。在距離表中的這個信息是根據臨近接點信息的改變而時時更新的。表中數據的量和在網絡中的所有的接點(除了它自己本身)是等同的。這個表中的列代表直接和它相連的鄰居，行代表在網絡中的所有目的地。每個數據包括傳送數據包到每個在網上的目的地的路徑和距離/或時間在那個路徑上來傳輸(我們叫這個為“成本”)。這個在那個算法中的度量公式是跳躍的次數， 等待時間，流出數據包的數量，等等。

在距離向量路由算法中，相鄰路由器之間周期性地相互交換各自的路由表備份。當網絡拓撲結構發生變化時，路由器之間也將及時地相互通知有關變更信息。

鏈路狀態算法的思想是要求網絡中所有參與鏈路狀態路由協議的路由器都掌握網絡的全部拓撲結構信息，并記錄在路由數據庫中。鏈路狀態算法中路由數據庫實質上是一個網絡結構的拓撲圖，該拓撲圖由一個節點的集合和一個邊的集合構成。在網絡拓撲圖中，結點代表網絡中路由器，邊代表路由器之間的物理鏈路。在網絡拓撲結構圖中，每一條鏈路上可以附加不同的屬性，例如鏈路的狀態、距離或費用等。如果沒一個路由器所保存的網絡拓撲結構圖都是一致的，那么個路由器生成的路由表也是最佳的，不存在錯誤路由或循環路由。

特征一：向本自治系統中的所有路由器發送信息。這里使用的方法是洪泛法（Flooding），即路由器通過所有的輸出端口向所有的相鄰路由器發送信息。而每一個路由器又將此信息發往其所有的相鄰的路由器（但不包括剛剛發來信息的那個路由器）。

特征二：發送的信息就是本路由器相鄰的所有路由器的鏈路狀態，但這只是路由器所知道的部分信息。所謂“鏈路狀態”就是說明本路由器和那些路由器相鄰，以及該鏈路的“度量”。對于OSPF，鏈路狀態的“度量”主要用來表示費用、距離、時延、帶寬等。

特征三：只有當鏈路狀態發生改變時，路由器才用洪泛法向所有路由器發送此信息。

OSPF就是使用分布式的鏈路狀態協議。