源路由算法

源路由算法(source routing)是一種不要求中間節點保持路由表，但要求源主機承擔更為繁重工作的路由選擇算法。源路由算法可用於數據報或虛電路的分組交換網。

基本介紹

• 中文名：源路由算法
• 外文名：source routing
• 實質：一種路由選擇算法
• 優點：易於實現、評估等
• 套用：數據報、分組交換網等
• 涉及領域：通信技術等

簡述

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

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

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

步驟

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

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

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

特點

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

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