【正文】 Dest. Next Metric C C 0 B B 2 A ∞ ?路由更新 A B C Dest. Next Metric A A 0 B B 3 C B 5 3 2 Dest. Next Metric B B 0 A A 3 C C 2 Dest. Next Metrict C C 0 B B 2 A B 5 B, 0 A, 3 C, 2 B, 0 A, 3 C, 2 路由更新消息 DV算法中的計數(shù)到無窮問題 A B C 3 2 Dest. Next Metric B B 0 A A 3 C C 2 Dest. Next Metric C C 0 B B 2 A B 5 Dest. Next Metric B B 0 A A ∞ C C 2 A, 5 Dest. Next Metric B B 0 A C 7 C C 2 A, 7 Dest. Next Metric C C 0 B B 2 A B 9 A, 9 無窮計數(shù)！ DV算法不能直接用于 Ad Hoc網(wǎng)絡(luò) ?計數(shù)到無窮問題 ?部分解決方法 ?選擇一個相對較少的數(shù)作為無窮大 ?水平分割 (split horizon)：當一個節(jié)點把路由更新發(fā)送給相鄰節(jié)點時，它并不把從各個相鄰節(jié)點處學到的路由再回送給該節(jié)點 無法發(fā)現(xiàn)路由循環(huán) 限制了網(wǎng)絡(luò)的可擴展性 對兩個節(jié)點的路由循環(huán)有效，更大的路由循環(huán)需要更強的措施 DSDV協(xié)議概述 ? 基于 DV算法 ?簡單，易于實現(xiàn) ?需要的存儲空間?。ㄖ豁毢袜従庸?jié)點交換路由信息） ? 確保無路由回路 ?路由表中的每個表項都帶有目的地序列號（由目的節(jié)點生成） ? 對拓撲變化能作出快速反應(yīng) ?路由表有顯著變化時立即啟動路由公告 (Router Advertisement) ?但是等待不穩(wěn)定路由的公告，以減緩路由波動 (damping fluctuations) ? 先應(yīng)式（表驅(qū)動）路由 ?節(jié)點維護到所有目的地的路由信息 ?路由信息必須周期性的更新（無休眠節(jié)點） ?即使網(wǎng)絡(luò)拓撲無變化也存在著通信開銷 ?維護的路由可能從不使用 DSDV: DestinationSequenced Distance Vector DSDV路由表 ? 序列號（ Sequence number ） ? 由目的端產(chǎn)生，用來防止出現(xiàn)路由回路，并確保路由信息是最新的 ? 格式： Dest_NNN ? 加入時間（ Install Time） ? 路由表項的創(chuàng)建時間，用來刪除過期表項 ? Stable Data ? 指向一個包含有路由穩(wěn)定狀態(tài)信息的表 ? 目的節(jié)點地址 ? 最近沉淀時間（ last settling time） ? 平均沉淀時間 (average settling time) ? 用于緩解網(wǎng)絡(luò)中的路由波動 Dest. Metric Next Seq. Nr Install Time Stable Data A A 0 A550 001000 Ptr_A B B 1 B102 001200 Ptr_B C B 3 C588 001200 PtrC D B 4 D312 001200 Ptr_D 對于同一個目的地，節(jié)點可能接收到來自其它節(jié)點的多條路由信息， settling time定義為第一條路由和最佳路由之間的時間間隔 DSDV路由公告 ?向每個鄰居公告自己的路由信息 ?目的節(jié)點地址 ?Metric：到目的節(jié)點的開銷，一般為到目的節(jié)點的跳數(shù) ?目的地序列號 ?其它信息（例如硬件地址等） ?設(shè)置序列號信息的規(guī)則 ?每次公告增加自己的目的地序列號（只使用偶數(shù)值） ?如果一個節(jié)點不再可達（ timeout） ,則將該節(jié)點的序列號加 1（奇數(shù)序列號），并且設(shè)置 metric為 ∞ DSDV路由選擇 ?將更新信息與自己的路由表比較 ?選擇具有更大目的地序列號的路由，這將保證始終使用來自目的地的最新信息 ?當序列號相等時，選擇具有更好 metric的路由 DSDV協(xié)議操作：更新前路由表 Dest. Next Metric Seq A A 1 A550 B B 0 B100 C C 1 C588 Dest. Next Metric Seq A A 0 A550 B B 1 B100 C B 2 C588 Dest. Next Metric Seq. A B 2 A550 B B 1 B100 C C 0 C588 A B C DSDV協(xié)議操作：路由公告 A, 1, A550 B, 0, B102 C, 1, C588 A, 1, A550 B, 0, B102 C, 1, C588 B遞增序列號 100 102 B向鄰居 A、 C廣播路由信息，其中包含有目的地序列號 Dest. Next Metric Seq A A 0 A550 B B 1 B100 C B 2 C588 Dest. Next Metric Seq A A 1 A550 B B 0 B102 C C 1 C588 Dest. Next Metric Seq. A B 2 A550 B B 1 B100 C C 0 C588 A B C DSDV協(xié)議操作：更新后路由表 Dest. Next Metric Seq A A 0 A550 B B 1 B102 C B 2 C588 Dest. Next Metric Seq A A 1 A550 B B 0 B102 C C 1 C588 Dest. Next Metric Seq. A B 2 A550 B B 1 B102 C C 0 C588 A B C 對拓撲變化的反應(yīng) ?立即公告 ?有關(guān)新路由、鏈路斷開和 metric變化的信息立即傳遞給鄰居節(jié)點 ?完全 /增量更新 ?完全更新：發(fā)送自己路由表中的所有路由信息 ?增量更新：只發(fā)送路由表中那些發(fā)生變化的表項（能包含在一個單獨的分組中發(fā)送） DSDV協(xié)議操作：新節(jié)點加入 D, 0, D000 Dest. Next Metric Seq. A A 0 A550 B B 1 B104 C B 2 C590 Dest. Next Metric Seq. A A 1 A550 B B 0 B104 C C 1 C590 Dest. Next Metric Seq. A B 2 A550 B B 1 B104 C C 0 C590 1. D第一次廣播 , 發(fā)送序列號 D000 A B C D DSDV協(xié)議操作：新節(jié)點加入 Dest. Next Metric Seq. A B 2 A550 B B 1 B104 C C 0 C590 D D 1 D000 2. 插入到 D的表項，序列號為 D000 Dest. Next Metric Seq. A A 0 A550 B B 1 B104 C B 2 C590 Dest. Next Metric Seq. A A 1 A550 B B 0 B104 C C 1 C590 A B C D DSDV協(xié)議操作：新節(jié)點加入 A, 2, A550 B, 1, B104 C, 0, C592 D, 1, D000 A, 2, A550 B, 1, B104 C, 0, C592) D, 1, D000 Dest. Next Metric Seq. A B 2 A550 B B 1 B104 C C 0 C592 D D 1 D000 3. C遞增自己的序列號到 C592，然后 立即廣播