【正文】 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 分鐘還沒有收到相鄰路由器的更新路由表，則將此相鄰路由器記為不可達(dá)的路由器，即將距離置為 16（距離為 16表 示不可達(dá)）。 2020/6/16 Nanjing university of industry WuJun 81 距離向量算法 收到相鄰路由器（其地址為 X）的一個(gè) RIP 報(bào)文： (1) 先修改此 RIP 報(bào)文中的所有項(xiàng)目：將 “ 下一跳 ” 字段中的地址都改為 X，并將所有的 “ 距離 ” 字段的值加 1。 2020/6/16 Nanjing university of industry WuJun 80 路由表的建立 ? 路由器在剛剛開始工作時(shí) ， 只知道到直接連接的網(wǎng)絡(luò)的距離 （ 此距離定義為 1） 。RIP 選擇一個(gè)具有最少路由器的路由 （ 即最短路由 ） ， 哪怕還存在另一條高速 (低時(shí)延 )但路由器較多的路由 。 ? RIP 允許一條路徑最多只能包含 15 個(gè)路由器 。 2020/6/16 Nanjing university of industry WuJun 77 “距離”的定義 ? 從一路由器到直接連接的網(wǎng)絡(luò)的距離定義為 1。排除特殊地址， 4個(gè)子網(wǎng)應(yīng)借用 3位， 23＝ 8，此時(shí)子網(wǎng)掩碼為。 2020/6/16 Nanjing university of industry WuJun 40 路由技術(shù) 2020/6/16 Nanjing university of industry WuJun 41 路由選擇的作用 ? 路由選擇是在網(wǎng)絡(luò)中選擇一條路徑，用以傳送分組 – 路徑是網(wǎng)絡(luò)中的一個(gè)鄰節(jié)點(diǎn)序列 – 路徑起止于兩個(gè)接入節(jié)點(diǎn) – 路徑連接了源宿兩個(gè)端系統(tǒng) ? IP網(wǎng)絡(luò)中的路由選擇 – 對(duì)主機(jī)（端系統(tǒng)）而言 ? 僅需將分組遞交缺省網(wǎng)關(guān) – 本邏輯子網(wǎng)，物理網(wǎng)絡(luò)進(jìn)行尋址和轉(zhuǎn)發(fā) – 對(duì) IP網(wǎng)關(guān)（路由器、中繼系統(tǒng)）而言 ? IP網(wǎng)絡(luò)是若干 IP網(wǎng)關(guān)作節(jié)點(diǎn)組成的網(wǎng)際網(wǎng)、網(wǎng)際子層 ? 將若干子網(wǎng)內(nèi)的連接，通過一系列網(wǎng)關(guān)的協(xié)調(diào)，組成一個(gè)網(wǎng)際連接的最優(yōu)路徑（ path）， 沿此路徑，將分組從源送到宿 2020/6/16 Nanjing university of industry WuJun 42 路由選擇的協(xié)議層次 ? 路由選擇是七層模型中網(wǎng)絡(luò)層（ N層）的最主要實(shí)體 – routing， 也稱選徑 ? N層的主要功能 – 將鏈路連接組成網(wǎng)絡(luò)連接 – 無連接模式：連通，通常有流（ stream） 存在 ? 為端系統(tǒng)（通過運(yùn)送層， T層）上網(wǎng)，提供網(wǎng)絡(luò)服務(wù) – T層接口：只存在于端系統(tǒng)，屏蔽網(wǎng)內(nèi)細(xì)節(jié)，送上網(wǎng)即可 – N層接口：端系統(tǒng)、中繼系統(tǒng)均有 ? 提供更多的網(wǎng)內(nèi)細(xì)節(jié)，必要時(shí)才使用 ? N層的作用：對(duì) T層提供 N層服務(wù) – 使用 DL層服務(wù) 通過 N層實(shí)體的協(xié)議交互 2020/6/16 Nanjing university of industry WuJun 43 源路由和透明路由 ? 源路由要點(diǎn) – 源路由概念：由源主機(jī)指定整個(gè)路由 – 選擇路由的主體：各個(gè)源主機(jī)自主決定，雙向可能不一樣 – 源路由的特點(diǎn) ? 主機(jī)必須了解網(wǎng)內(nèi)細(xì)節(jié)及拓?fù)渥兓? ? 主機(jī)計(jì)算最佳路由，是主機(jī)智能型，主機(jī)負(fù)擔(dān)可能很重 ? 主機(jī)決定路徑上的逐個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn) – 在分組中明確指定轉(zhuǎn)發(fā)站序列 ? 中繼系統(tǒng)（路由器）僅是存儲(chǔ)－轉(zhuǎn)發(fā)設(shè)備 2020/6/16 Nanjing university of industry WuJun 44 源路由和透明路由 ? 透明路由要點(diǎn) – 透明路由概念 ? 源主機(jī)僅需將分組遞交給缺省網(wǎng)關(guān)：送上網(wǎng)即可 ? 網(wǎng)絡(luò)拓?fù)鋵?duì)主機(jī)透明：主機(jī)不需要了解網(wǎng)絡(luò)拓?fù)浼白兓?xì)節(jié) – 選擇路由的主體 ? 由網(wǎng)絡(luò)內(nèi)（對(duì) IP網(wǎng)，是網(wǎng)際網(wǎng)內(nèi) ）所有網(wǎng)關(guān)決定路由 ? 通常采用分布式計(jì)算：由各個(gè)網(wǎng)關(guān)自行決定，但保持一致 – 透明路由的特點(diǎn) ? 主機(jī)只需知道缺省網(wǎng)關(guān)即可，不需要知道、跟蹤網(wǎng)絡(luò)細(xì)節(jié) ? 由網(wǎng)關(guān)計(jì)算最佳路徑，是路由設(shè)備智能型 ? 各個(gè)網(wǎng)關(guān)內(nèi)維護(hù)一個(gè)全網(wǎng)一致的路由表，決定下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn) ? 分組內(nèi)含有下一跳的物理地址，且逐跳改變 – E網(wǎng)中： IP地址對(duì)一直不變， MAC地址對(duì)逐跳改變 2020/6/16 Nanjing university of industry WuJun 45 源路由和透明路由 ? 源路由和透明路由的比較 – 目前，絕大多數(shù)網(wǎng)絡(luò)采用透明路由， IP網(wǎng)絡(luò)尤其如此 – 主機(jī)進(jìn)行數(shù)據(jù)處理 ? 需要與遠(yuǎn)端交互的數(shù)據(jù)送上網(wǎng)即可 – 各個(gè)網(wǎng)關(guān)協(xié)調(diào)一致 ? 計(jì)算、選擇最佳路徑 ? 進(jìn)行數(shù)據(jù)交換，將數(shù)據(jù)逐跳轉(zhuǎn)發(fā)到宿 – 對(duì) IP的網(wǎng)際網(wǎng)，逐跳的通常作法是 ? 分組逐網(wǎng)轉(zhuǎn)發(fā) ? 下一跳是下一個(gè)網(wǎng)絡(luò)（網(wǎng)號(hào)）的選定網(wǎng)關(guān)的某一接口 2020/6/16 Nanjing university of industry WuJun 46 路由選擇的主要活動(dòng) ? 路由選擇包括兩種基本活動(dòng) – 最佳路徑的判定 ? 非常復(fù)雜 ? 同一體系中有多種不同的算法和協(xié)議 – 轉(zhuǎn)發(fā)（ forwarding） 分組（協(xié)議數(shù)據(jù)單元） ? 相對(duì)較為簡(jiǎn)單 ? 同一體系中只有 1～ 2種協(xié)議 ? 有時(shí)稱為交換（ switching） – 表明在逐個(gè)節(jié)點(diǎn)上切換到不同鏈路上 2020/6/16 Nanjing university of industry WuJun 47 路徑判定 ? 選用一定的判斷準(zhǔn)則－－量度（ metrics） ? 實(shí)時(shí)收集網(wǎng)絡(luò)拓?fù)涞脑敿?xì)數(shù)據(jù) ? 使用某一算法 算出最佳路徑 – 常見算法為 V－ D算法和 L－ S算法 ? 將算出的所有最佳路徑信息存入路由表 – 為減小路由表 ? 所有路徑僅對(duì)宿網(wǎng)絡(luò)而言，一般不針對(duì)個(gè)別主機(jī) ? 可以路由聚合，將宿網(wǎng)絡(luò)歸并為超級(jí)網(wǎng) – 路由表基本內(nèi)容包括：宿網(wǎng)絡(luò)、下一跳網(wǎng)關(guān)地址 ? 維護(hù)路由表，保持全網(wǎng)一致 – 網(wǎng)關(guān)（路由器）經(jīng)常交換拓?fù)渥兓刃畔? ? 如，路由更新信息、鏈路活動(dòng)、路由器活動(dòng)等 – 路由器維護(hù)路由表以反映網(wǎng)絡(luò)拓?fù)洌ǜ禄虮３只顒?dòng)） 2020/6/16 Nanjing university of industry WuJun 48 分組運(yùn)送 ? 分組運(yùn)送也稱為分組交換 ? 主機(jī) – 將分組遞交到缺省網(wǎng)關(guān)（透明路由） – 分組含該網(wǎng)關(guān)物理地址、宿主機(jī)的（ IP） 協(xié)議地址 ? 網(wǎng)關(guān) – 算法框架 ? 檢查宿協(xié)議地址 ? if 不知道 – then 丟棄分組，返回 ICMP/3： 宿不可達(dá) – else 轉(zhuǎn)發(fā)到下一跳：物理地址將改成下一跳網(wǎng)關(guān)的物理地址 ? 在整個(gè)運(yùn)送過程中源宿協(xié)議地址一直不變 – 供各網(wǎng)關(guān)確定下一跳 NetID – 到達(dá)宿網(wǎng)絡(luò)后，供網(wǎng)關(guān)將該分組遞交宿主機(jī) 2020/6/16 Nanjing university of industry WuJun 49 分組運(yùn)送 ? 分組運(yùn)送過程圖例 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 算法設(shè)計(jì)目標(biāo) ? 路由算法一般追求下列（通常不可能是全部）目標(biāo) ? 優(yōu)化 – 選擇最佳路徑。 ” ? 互聯(lián)網(wǎng)都是指用路由器進(jìn)行互連的網(wǎng)絡(luò)。 – 網(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) 路由 選擇 路由選擇處理機(jī) 路由選擇協(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)絡(luò)層 2——數(shù)據(jù)鏈路層 1——物理層 2020/6/16 Nanjing university of industry WuJun 36 ? 互連在一起的網(wǎng)絡(luò)要進(jìn)行通信，會(huì)遇到許多問題需要解決，如： – 不同的尋址方案 – 不同的最大分組長(zhǎng)度 – 不同的網(wǎng)絡(luò)接入機(jī)制 – 不同的超時(shí)控制 – 不同的差錯(cuò)恢復(fù)方法 – 不同的狀態(tài)報(bào)告方法 – 不同的路由選擇技術(shù) – 不同的用戶接入控制 – 不同