2.4.1 尋找路徑

網絡層的主要任務就是尋找一條轉發數據包的路徑，我們稱之為路由算法。路由算法分為兩類：一類稱為鏈路狀態算法，另一類稱為距離向量算法。但是無論是何種算法，我們都需要為每一個機器節點指定一個唯一編號，之后各個機器節點交換信息的時候就用這個唯一編號作為對方的標識符。我們以ID作為每個機器節點的編號代稱。接下來大致介紹一下這兩種類型的算法。

1．鏈路狀態算法

鏈路狀態（LS）算法的思路如下。

1）確認所有物理相連的機器節點：每加入一個機器節點機器，該機器就需要確認所有與其物理相連的機器節點，并獲取其唯一編號。具體方法是，向整個網絡中的機器節點都發送一個用于探測機器節點的數據包，當機器節點接收到該數據包后，返回一個對應的數據包，其中包含其ID。

2）測量到每個機器節點的時間長度：我們需要測量出當前機器節點到與其相連的機器節點到底需要花多長時間。方法是向對應的機器節點發送一個數據包，接收方回送一個數據包。發送方就可以根據發送和接收響應數據包的時間來確定發送數據消耗的時間。

3）共享信息：各個機器節點會向其他機器節點廣播自己的連接信息，這樣所有的機器節點都可以逐步構建起整個網絡的拓撲結構。

4）根據拓撲結構尋找最短路徑：然后我們可以使用最短路徑算法，根據機器節點的網絡圖（每個機器節點是圖中的一個節點），使用Dijkstra算法來計算出最短路徑。Dijkstra算法大家應該都比較熟悉，這里不過多闡述。

2．距離向量算法

我們可以看到鏈接狀態算法是全局性算法，需要在每個機器節點構建出全局網絡并計算路徑。但這樣會消耗太多的系統資源。與此相對的是局部性的距離向量（DV）算法。

該算法的思路如下。

1）建立路由表：路由表很簡單，只記錄當前機器節點到達其他各個機器節點的一個權值，權值越大，路徑越長。并記錄這種情況下應該將數據轉發給哪個相鄰機器節點。

2）計算與相鄰機器節點的鏈接權值：每個機器節點只計算與自己直接相連的機器節點的路徑權值（可以理解為數據的到達時間），計算方法可以采取與LS相同的方法。

3）每隔一段時間將自己的路由表發送到相鄰機器節點：每個機器節點每隔一段時間將自己最新的路由表發送給相鄰的機器節點，通過各個機器節點局部性地不斷傳遞，各個機器節點逐步修正路由表。

4）在轉發消息時，只要選擇與目標機器節點權值最小的那個相鄰機器節點，并將消息轉發出去即可。

我們可以看到，這種方式消耗的資源較少，處理速度也較快。另外我們也可以證明，路由表最后是可以收斂的，對此感興趣的讀者可以自行查閱資料進行研究。