【正文】 tion about a route back in the direction from which the original packet came A B C E0 S0 S0 S1 S0 E0 X X X Routing Table S0 S0 S0 S0 1 2 0 0 Routing Table E0 S0 S0 S0 1 2 0 0 Routing Table S0 S1 S1 E1 1 2 0 0 Solution 2: Route Poisoning ? Routers set the distance of routes that have gone down to infinity A B C E0 S0 S0 S1 S0 E0 X Routing Table S0 S0 S0 S0 1 2 0 Infinity Routing Table E0 S0 S0 S0 1 2 0 0 Routing Table S0 S1 S1 E1 1 2 0 0 Solution 2: Poison Reverse ? Poison Reverse overrides split horizon A B C E0 S0 S0 S1 S0 E0 X Routing Table S0 S0 S0 S0 1 2 0 Infinity Routing Table E0 S0 S0 S0 1 2 0 0 Routing Table S0 S1 S1 E1 Possibly Down 2 0 0 Poison Reverse Solution 3: HoldDown Timers ? Router keeps an entry for the work possibly down state, allowing time for other routers to repute for this topology change Network is down then back up then back down Update after holddown Time Network is unreachable A B C E0 S0 S0 S1 S0 E0 X Update after holddown Time Solution 4: Triggered Updates ? Router sends updates when a change in its routing table occurs A B C E0 S0 S0 S1 S0 E0 X Network is unreachable Network is unreachable Network is unreachable 2020/6/16 Nanjing university of industry WuJun 101 水平分割 水平分割保證路由器記住每一條路由信息的來源，并且不在收到這條信息的端口上再次發(fā)送它。 (3) 若 3 分鐘還沒有收到相鄰路由器的更新路由表，則將此相鄰路由器記為不可達的路由器，即將距離置為 16（距離為 16表 示不可達）。 2020/6/16 Nanjing university of industry WuJun 81 距離向量算法 收到相鄰路由器（其地址為 X）的一個 RIP 報文： (1) 先修改此 RIP 報文中的所有項目：將 “ 下一跳 ” 字段中的地址都改為 X，并將所有的 “ 距離 ” 字段的值加 1。 2020/6/16 Nanjing university of industry WuJun 80 路由表的建立 ? 路由器在剛剛開始工作時 ， 只知道到直接連接的網(wǎng)絡的距離 （ 此距離定義為 1） 。RIP 選擇一個具有最少路由器的路由 （ 即最短路由 ） ， 哪怕還存在另一條高速 (低時延 )但路由器較多的路由 。 ? RIP 允許一條路徑最多只能包含 15 個路由器 。 2020/6/16 Nanjing university of industry WuJun 77 “距離”的定義 ? 從一路由器到直接連接的網(wǎng)絡的距離定義為 1。排除特殊地址， 4個子網(wǎng)應借用 3位， 23＝ 8，此時子網(wǎng)掩碼為。 2020/6/16 Nanjing university of industry WuJun 40 路由技術 2020/6/16 Nanjing university of industry WuJun 41 路由選擇的作用 ? 路由選擇是在網(wǎng)絡中選擇一條路徑，用以傳送分組 – 路徑是網(wǎng)絡中的一個鄰節(jié)點序列 – 路徑起止于兩個接入節(jié)點 – 路徑連接了源宿兩個端系統(tǒng) ? IP網(wǎng)絡中的路由選擇 – 對主機（端系統(tǒng)）而言 ? 僅需將分組遞交缺省網(wǎng)關 – 本邏輯子網(wǎng)，物理網(wǎng)絡進行尋址和轉(zhuǎn)發(fā) – 對 IP網(wǎng)關（路由器、中繼系統(tǒng)）而言 ? IP網(wǎng)絡是若干 IP網(wǎng)關作節(jié)點組成的網(wǎng)際網(wǎng)、網(wǎng)際子層 ? 將若干子網(wǎng)內(nèi)的連接，通過一系列網(wǎng)關的協(xié)調(diào)，組成一個網(wǎng)際連接的最優(yōu)路徑（ path）， 沿此路徑，將分組從源送到宿 2020/6/16 Nanjing university of industry WuJun 42 路由選擇的協(xié)議層次 ? 路由選擇是七層模型中網(wǎng)絡層（ N層）的最主要實體 – routing， 也稱選徑 ? N層的主要功能 – 將鏈路連接組成網(wǎng)絡連接 – 無連接模式：連通，通常有流（ stream） 存在 ? 為端系統(tǒng)（通過運送層， T層）上網(wǎng)，提供網(wǎng)絡服務 – T層接口：只存在于端系統(tǒng)，屏蔽網(wǎng)內(nèi)細節(jié)，送上網(wǎng)即可 – N層接口：端系統(tǒng)、中繼系統(tǒng)均有 ? 提供更多的網(wǎng)內(nèi)細節(jié)，必要時才使用 ? N層的作用：對 T層提供 N層服務 – 使用 DL層服務 通過 N層實體的協(xié)議交互 2020/6/16 Nanjing university of industry WuJun 43 源路由和透明路由 ? 源路由要點 – 源路由概念：由源主機指定整個路由 – 選擇路由的主體：各個源主機自主決定，雙向可能不一樣 – 源路由的特點 ? 主機必須了解網(wǎng)內(nèi)細節(jié)及拓撲變化 ? 主機計算最佳路由，是主機智能型，主機負擔可能很重 ? 主機決定路徑上的逐個轉(zhuǎn)發(fā)節(jié)點 – 在分組中明確指定轉(zhuǎn)發(fā)站序列 ? 中繼系統(tǒng)（路由器）僅是存儲－轉(zhuǎn)發(fā)設備 2020/6/16 Nanjing university of industry WuJun 44 源路由和透明路由 ? 透明路由要點 – 透明路由概念 ? 源主機僅需將分組遞交給缺省網(wǎng)關：送上網(wǎng)即可 ? 網(wǎng)絡拓撲對主機透明：主機不需要了解網(wǎng)絡拓撲及變化細節(jié) – 選擇路由的主體 ? 由網(wǎng)絡內(nèi)（對 IP網(wǎng)，是網(wǎng)際網(wǎng)內(nèi) ）所有網(wǎng)關決定路由 ? 通常采用分布式計算：由各個網(wǎng)關自行決定，但保持一致 – 透明路由的特點 ? 主機只需知道缺省網(wǎng)關即可，不需要知道、跟蹤網(wǎng)絡細節(jié) ? 由網(wǎng)關計算最佳路徑，是路由設備智能型 ? 各個網(wǎng)關內(nèi)維護一個全網(wǎng)一致的路由表，決定下一跳轉(zhuǎn)發(fā)節(jié)點 ? 分組內(nèi)含有下一跳的物理地址，且逐跳改變 – E網(wǎng)中： IP地址對一直不變， MAC地址對逐跳改變 2020/6/16 Nanjing university of industry WuJun 45 源路由和透明路由 ? 源路由和透明路由的比較 – 目前，絕大多數(shù)網(wǎng)絡采用透明路由， IP網(wǎng)絡尤其如此 – 主機進行數(shù)據(jù)處理 ? 需要與遠端交互的數(shù)據(jù)送上網(wǎng)即可 – 各個網(wǎng)關協(xié)調(diào)一致 ? 計算、選擇最佳路徑 ? 進行數(shù)據(jù)交換，將數(shù)據(jù)逐跳轉(zhuǎn)發(fā)到宿 – 對 IP的網(wǎng)際網(wǎng)，逐跳的通常作法是 ? 分組逐網(wǎng)轉(zhuǎn)發(fā) ? 下一跳是下一個網(wǎng)絡（網(wǎng)號）的選定網(wǎng)關的某一接口 2020/6/16 Nanjing university of industry WuJun 46 路由選擇的主要活動 ? 路由選擇包括兩種基本活動 – 最佳路徑的判定 ? 非常復雜 ? 同一體系中有多種不同的算法和協(xié)議 – 轉(zhuǎn)發(fā)（ forwarding） 分組（協(xié)議數(shù)據(jù)單元） ? 相對較為簡單 ? 同一體系中只有 1～ 2種協(xié)議 ? 有時稱為交換（ switching） – 表明在逐個節(jié)點上切換到不同鏈路上 2020/6/16 Nanjing university of industry WuJun 47 路徑判定 ? 選用一定的判斷準則－－量度（ metrics） ? 實時收集網(wǎng)絡拓撲的詳細數(shù)據(jù) ? 使用某一算法 算出最佳路徑 – 常見算法為 V－ D算法和 L－ S算法 ? 將算出的所有最佳路徑信息存入路由表 – 為減小路由表 ? 所有路徑僅對宿網(wǎng)絡而言，一般不針對個別主機 ? 可以路由聚合，將宿網(wǎng)絡歸并為超級網(wǎng) – 路由表基本內(nèi)容包括：宿網(wǎng)絡、下一跳網(wǎng)關地址 ? 維護路由表，保持全網(wǎng)一致 – 網(wǎng)關（路由器）經(jīng)常交換拓撲變化等信息 ? 如，路由更新信息、鏈路活動、路由器活動等 – 路由器維護路由表以反映網(wǎng)絡拓撲（更新或保持活動） 2020/6/16 Nanjing university of industry WuJun 48 分組運送 ? 分組運送也稱為分組交換 ? 主機 – 將分組遞交到缺省網(wǎng)關（透明路由） – 分組含該網(wǎng)關物理地址、宿主機的（ IP） 協(xié)議地址 ? 網(wǎng)關 – 算法框架 ? 檢查宿協(xié)議地址 ? if 不知道 – then 丟棄分組，返回 ICMP/3： 宿不可達 – else 轉(zhuǎn)發(fā)到下一跳：物理地址將改成下一跳網(wǎng)關的物理地址 ? 在整個運送過程中源宿協(xié)議地址一直不變 – 供各網(wǎng)關確定下一跳 NetID – 到達宿網(wǎng)絡后，供網(wǎng)關將該分組遞交宿主機 2020/6/16 Nanjing university of industry WuJun 49 分組運送 ? 分組運送過程圖例 SHost R1 R2 R3 Dhost To: DHost (IP) R11 (MAC) 1 2 3 4 To: DHost (IP) R22 (MAC) To: DHost (IP) R33 (MAC) To: DHost (IP) DHost (MAC) 2020/6/16 Nanjing university of industry WuJun 50 算法設計目標 ? 路由算法一般追求下列（通常不可能是全部）目標 ? 優(yōu)化 – 選擇最佳路徑。 ” ? 互聯(lián)網(wǎng)都是指用路由器進行互連的網(wǎng)絡。 – 網(wǎng)橋和路由器的混合物：橋路器 (brouter)。 2020/6/16 Nanjing university of industry WuJun 34 直接交付和間接交付 間接交付 間接交付 間接交付 A B C 直接交付 直接交付 直接交付不需要使用路由器 但間接交付就必須使用路由器 2020/6/16 Nanjing university of industry WuJun 35 典型的路由器的結(jié)構(gòu) 路由 選擇 路由選擇處理機 路由選擇協(xié)議 路由表 3 輸入端口 3 交換結(jié)構(gòu) 輸入端口 輸出端口 分組 轉(zhuǎn)發(fā) 轉(zhuǎn)發(fā)表 分組處理 輸出端口 … … 1 1 1 3 3 1 2 2 2 2 3——網(wǎng)絡層 2——數(shù)據(jù)鏈路層 1——物理層 2020/6/16 Nanjing university of industry WuJun 36 ? 互連在一起的網(wǎng)絡要進行通信，會遇到許多問題需要解決，如： – 不同的尋址方案 – 不同的最大分組長度 – 不同的網(wǎng)絡接入機制 – 不同的超時控制 – 不同的差錯恢復方法 – 不同的狀態(tài)報告方法 – 不同的路由選擇技術 – 不同的用戶接入控制 – 不同