AODV VS DSR

Ad hoc On-demand Distance Vector Routing Protocol (AODV) 

AODV 屬於 On-demand 路由協定，當來源節點有資料要傳送且路由表中 沒有目的節點的路徑資訊時，才會啟動路徑搜尋程序。

A. 路徑搜尋程序 

   
     當來源節點需要一條路徑到目的節點，會廣播一個Route REQuest (RREQ) 封包到網路中，然後等待 Route REPly (RREP)封包。RREQ 封包中包含來源節 點與目的節點的 IP 位址、廣播 ID、來源節點與目的節點最新的 Sequence number，如圖 2.5。每當節點收到 RREQ 封包後，都會紀錄下來源節點的 IP 位址與廣播 ID，當節點將 RREQ 封包廣播出去後，會設定一段預設的時間， 如果節點在這一段時間內接收到擁有相同來源節點的 IP 位址與廣播 ID 的 RREQ 封包時，就會丟棄此 RREQ 封包。如果沒有接收過此 RREQ 封包，節 點接著會判斷自己是否為目的節點或自己是否擁有到目的節點的路徑資訊， 如果滿足其中一項，則回覆 RREP 封包到來源節點，反之，則在 RREQ 封包 的 Hop 欄位加一後，廣播 RREQ 封包。另外，當節點接收到 RREQ 封包時， 會建立一條指向來源節點的反向路徑資訊到路由表中，如圖 2.6，實線箭頭代 表 RREQ 封包傳送的路徑，來源節點 A 廣播的 RREQ 封包，中間節點收到 RREQ 封包後再將此 RREQ 封包廣播出去，直到目的節點 G 收到為止。
 
     在 RREP 封包回覆到來源節點 A 的過程中，當中間節點接收到 RREP 封包時，會建立一條指向目的節點的正向路徑資訊到路由表中，然後傳給上 游節點，直到 RREP 封包傳到來源節點 A。如圖 2.7，虛線箭頭代表 RREP 封 包傳送的路徑，目的節點 G 收到 RREQ 封包後，沿著 RREQ 封包傳來的路徑 回傳 RREP 封包給來源節點 A。如果來源節點 A 在找路計時器倒數到 0 時還 沒有收到 RREP 封包，來源節點 A 會重覆廣播 RREQ 封包，重傳次數加一。 當來源節點 A 重傳次數超過預設的最大值，則此條連線宣告失敗。

    在 AODV 中，每個節點會維持一個路由表，路由表中記錄所有可用路徑 的資訊，最新的路徑資訊可以透過 Sequence number 來判斷。在 AODV 中， 每個節點都擁有屬於自己的 Sequence number，有兩種狀況節點會單調遞增自 己的 Sequence number：第一，當來源節點要發出 RREQ 封包時；第二，當目 的節點收到 RREQ 封包，準備要回傳 RREP 封包時。每個節點的路由表中， 針對通往目的節點的路徑都有一個 Sequence number，所以，每當節點收到 RREQ 封包時都會檢查控制封包中來源節點的 Sequence number 訊息；如果收 到 RREP 封包時會檢查控制封包中目的節點的 Sequence number 訊息。如果控 制封包中來源節點或目的節點的 Sequence number 大於路由表中的 Sequence number，則立即將控制封包中相關節點的 Sequence number 的值取代路由表中 的 Sequence number，然後更新關於此路徑的資訊。如此，節點可以擁有通往 目的節點的最新路徑資訊

B. 路徑維持程序
   
     當連結因為斷裂而失效時，其上游節點發覺後，會將經過此連結的路徑設為 無效，然後會根據路由表的資訊，發送 Route Error (RERR)封包給需要經過此 連結到達目的地的鄰近節點。鄰近節點收到 RERR 封包後，會將受到影響的路徑設為無效，再繼續發送 RERR 封包給受影響的鄰近節點。當來源節點收 到 RERR 封包後，如果還有需要，會啟動路徑搜尋程序。

AODV 和 DSR 都有類似的 route discovery 過程，都強調是在 source 工作站需要的時候才會去建立到目的地工作站的路徑，但是兩者仍然 有相當的差異：

（1） DSR 所需的路徑資訊較 AOVD 來得多。DSR 在一個 cycle 下完 成 request route 後，source 工作站可以獲得目的地工作站和所有中 間工作站的路徑資訊。每一個中間工作站也可以獲得到達其他中 間工作站的路徑資訊。而 AODV 得到的路徑資訊則是有限的，只 認得封包的下一個轉送點，所以可能會造成工作站常常執行 route discovery，而使得網路流量變大。

（2） 在 AODV 中，因為 AODV 只為每一個工作站維護一筆路徑資 訊，所以目的地工作站只回應最先到的 route request，慢到的一律 丟棄。在 DSR 中，因為是使用 route cache，目的地工作站會回應 所有的 route request 封包，即使是重複的。這使得 source 工作站可 以在 route cache 中保留許多條到同一目的地的路徑，所以當最短 路徑不通時，在 route cache 中還有另一個選擇。此機制節省了啟 動 route discovery 的機會和網路流量，但是回應每一個 route reply 卻可能造成網路流量的氾濫。

（3） 在 AODV 中，路徑的時效是由 sequence number 來決定，永遠會 選擇最新的路徑資訊，並且如果過一段時間後此路徑都沒用過， 就從 routing table 中刪除。在 DSR 中則無法分辨路徑資訊是新的 還是舊的，只有等到 route error 封包通知時，才會把 route cache 中無效的路徑資訊刪除。

（4） 在 AODV 中，一旦發出 route error 封包，會送達給所有用到此 連線的工作站，讓它們刪去無效的路徑。但是 DSR 的機制只會傳 給唯一的上游工作站，直到 source 為止。不在此一路徑上的其他 工作站都不會被通知。