源路由算法

源路由算法不要求中間節點保持路由表，但要求源主機承擔更繁重的工作。在分組發送之前，源主機必須知道目的主機的完整路由，並將該信息包含在分組頭中。根據這個路由信息，分組節點可以將分組轉發到下一個節點。 ^[2] 

在發送分組之前，源主機必須知道到目的地主機的完整路由，以便將路由信息包含在分組頭中。路由信息包含有途經節點的次序，而且可以給中間節點提供足夠的信息，以使它們能將分組轉發到下一個節點，直至到達分組的目的地。 ^[1] 

源路由算法的實現是建立在TCP/IP提供的源路由功能基礎之上。在源路由算法中，每個數據分組中添加了從源節點到目的節點所經過的所有節點的地址序列，中間節點並不負責路由計算，而是按照路由序列轉發分組。在源路由協議中，源路由的建立與維護由源節點負責。嚴格的源路由算法可以杜絕路由環路的存在，減少分組對中間節點路由能力的依賴。DSR是自組網中典型的源路由協議。 ^[3] 

源路由算法包括兩個步驟：路由發現和路由指示。

路由發現，就是由發送站向目標發送詢問，詢問幀通過網橋轉發到目標站後，在應答幀中記錄了幀經歷的路徑，發送站從所有應答幀中確定最短的路由；

路由指示，就是在數據幀中增加表示轉發路徑的指示字段，所有收到數據幀的網橋檢查自身是否位於指示路徑之中，若是則向指定的LAN段轉發，否則不做處理。 ^[4] 

源路由算法的優點是，通過把分佈式問題轉化成集中式問題而使算法本身更加簡潔。源節點維護全局網絡狀態，本地計算整個路由，這樣不但避免了分佈式算法帶來的很多不便，同時還確保了無環路由。另外，源路由算法概念簡單，易於實現、評估、調試以及升級。而且，集中式啓發式算法要比分佈式啓發式算法更容易設計。

源路由算法面臨的最大問題是算法的可擴展性較差。對於源路由算法，每介網絡節點必須維護全局網絡狀態信息，而這些信息為了能夠更精確地反應網絡的動態特性，必須及時更新。對於一個較大的網絡，頻繁的信息更新會造成很大的網絡負載。另外，QoS路由協議提供的網絡狀態信息的不精確性對源路由算法的影響相對較大，導致算法得到的路徑最終不能滿足業務需求。源路由算法往往具有很高的計算複雜性，尤其在網絡較大時更是如此。 ^[5]