【正文】 擇協議 （ 這屬于本部門內部的事情 ） ， 但同時還希望連接到因特網上 。 分層次的路由選擇協議 ? 因特網采用 分層次的路由選擇協議 。 默認路由 ? 在路由表中，一般還有默認路由。 靜態(tài)路由 ? 靜態(tài)路由是一種特殊的路由 ， 它是由網絡管理員采用手工方法在路由器上配置而成 。 對所有不在 N中的節(jié)點 ， 有： D(v)＝ L(i,j) ；若節(jié)點 v與節(jié)點 1直接相連 D(v)＝ ∞； 若節(jié)點 v與節(jié)點 1不直接相連 N中的節(jié)點 w， 其 D(w)值 最小 ， 把 w加入到 N中 ， 然后對所有不在 N中的節(jié)點 ， 用[ D(v)， D(w)＋ L(w,v)]中較小的值去更新原有的 D(v)值 ， 即 : D(v)← Min[ D(v)， D(w)＋ L(w,v)] 。 ? 設某個節(jié)點為源節(jié)點 ， 每次尋找一個節(jié)點到源節(jié)點的最短路徑 ， 直至找到所有的節(jié)點 。 最出名的最短路徑算法有兩個： BellmanFord算法和 Dijkstra算法 。 ? 實際的路由選擇算法 ， 應盡可能接近于理想的算法 。 ? 這里 “ 代價 ” 并不一定是僅指 “ 錢 ” ， 而是由一個或幾個因素綜合決定的一種 度量(metric)， 如鏈路長度 、 數據率 、 鏈路容量 、是否要保密 、 傳播時延等 ， 甚至還可以是一天中某一個小時內的通信量 、 結點的緩存被占用的程度 、 鏈路差錯率等 。 ? 算法應具有穩(wěn)定性 。 3. A到 B和 B到 A的數據報的路徑可能不同。 路由表的信息 ? 典型地，路由表包含許多 (N,R) 向量，其中 N是目的網絡的 IP地址， R是為了到達相應目的網絡要經過的下一個路由器的 IP地址 (下一跳， next hop)。 分組到了目標網絡后，由終端路由器將分組 送到目標主機。 這會產生一定的時延 。 ? 處理器 CPU：微處理器或 RISC微處理器 ? 存儲器 ： ROM、 NVRAM FLASH RAM、 RAM ? 接口 ：控制臺接口 ? 局域網接口：以太網、令牌環(huán)網、光纖網 ? 廣域網接口： ATM、 X2 DDN、 FRN、 ISDN ? 邏輯接口： LOOP BACK， NULL， CHANNEL 典型的路由器的結構 路由 選擇 路由選擇處理機 路由選擇協議 路由表 3 輸入端口 3 交換結構 輸入端口 輸出端口 分組 轉發(fā) 轉發(fā)表 分組處理 輸出端口 … … 1 1 1 3 3 1 2 2 2 2 3——網絡層 2——數據鏈路層 1——物理層 分組處理 ? 路由器收到分組后，根據分組中包含的目的地址，在轉發(fā)表中選擇適當的輸出端口，轉發(fā)分組。 ? 如果是 ， 就將數據報 直接交付 給目的主機 B 而不需要通過路由器 。 ? 如果目的主機與源主機 A 不是連接在同一個網絡上 ， 則應將數據報發(fā)送給本網絡上的某個路由器 ， 由該路由器按照轉發(fā)表指出的路由將數據報轉發(fā)給下一個路由器 。 ? 若路由器處理分組的速率趕不上分組進入隊列的速率，則隊列的存儲空間最終必定減少到零，這就使后面再進入隊列的分組由于沒有存儲空間而只能被丟棄。 物理層處理 數據鏈路層 處理 網絡層處理 分組排隊 交 換 結 構 輸入端口的處理 從 線 路 接 收 分 組 查表和轉發(fā) 輸出端口將交換結構傳送來的分組發(fā)送到線路 ? 當交換結構傳送過來的分組先進行緩存 。 一般來說，第一個階段才是路由的實質階段，它關系到分組穿越網間網的路徑。 ? 選路表的大小取決于互聯網中網絡的數量，它僅在添加新網絡時才增大。 因特網的路由選擇協議 有關路由選擇算法的幾個基本概念 ? 分層次的路由選擇協議 ? 內部網關協議和外部網關協議 ? 距離向量算法，鏈路狀態(tài)算法 ? 路由信息協議 RIP (Routing Information Protocol) ? 開放最短路徑優(yōu)先 OSPF (Open Shortest Path First) ? 外部網關協議 EGP， BGP 路由選擇算法的幾個基本概念 理想的路由算法 ? 算法必須是正確的和完整的 。 ? 算法應是公平的 。 ? 不同的要求下 ， 各種因素的權值可能不同 。 ? 路由選擇是個非常復雜的問題 ? 它是網絡中的所有結點共同協調工作的結果 。 ? 兩種算法思路不同 ， 但得出的結果是相同的 。 ? 以網絡中的每一個節(jié)點作為源節(jié)點 ，分別使用最短路徑算法 ， 得出的結果就是全網的最短路徑 。 2， 直至所有網絡節(jié)點都在 N中為止 。 通過靜態(tài)路由的配置可以建立一個完整的網絡 。當表中沒有到達目標網絡的下一跳時，分組將被送到默認路由器。 ? 因特網的規(guī)模非常大 。 自治系統(tǒng) (Autonomous System) ? 因特網將整個互聯網劃分為許多較小的自治系統(tǒng) AS。 因特網有兩大類路由選擇協議 ? 內 部 網 關 協 議 IGP (Interior Gateway Protocol) 即在一個自治系統(tǒng)內部使用的路由選擇協議 。 在外部網關協議中目前使用最多的是 BGP4。 ? IGP 和 EGP 是協議類別的名稱 。 ? RIP 是一種分布式的基于 距離向量 的路由選擇協議。 ? 從一個路由器到非直接連接的網絡的距離定義為所經過的路由器數加 1。可見 RIP 只適用于小型互聯網 。 ? 交換的信息是當前本路由器所知道的全部信息 ， 即自己的路由表 。 ? 以后 ， 每一個路由器也只和數目非常有限的相鄰路由器交換并更新路由信息 。 (2) 對修改后的 RIP 報文中的每一個項目，重復以下步驟： 若項目中的目的網絡不在路由表中，則將該項目加到路由表中。 (4) 返回?！? 因此 B 現在也可以到網 1， 距離是 2，經過 A?！? 但 B 沒有必要繞道經過路由器 A 再到達網 3，因此這一項目不變?！? 因此 B 現在也可以到網 6， 距離是 2，經過 C。 ? RIPv2具有簡單鑒別功能 ， 支持多播 。 ? 路由標記填入自治系統(tǒng)的號碼 ， 這是考慮使 RIP 有可能收到本自治系統(tǒng)以外的路由選擇信息 。 ? RIP 限制了網絡的規(guī)模 ， 它能使用的最大距離為 15（ 16 表示不可達 ） 。” “1”表示“從本路由器到網 1” “2”表示“距離是 2” “R1”表示 經過 R1 壞消息傳得慢現象 R2 R1 網 1 網 3 網 2 R2 R1 網 1 網 3 網 2 網 1出了故障 正 常 情 況 1 1 ? 1 16 ? 1 2 R1 1 2 R1 R1 說：“我到網 1 的距離是 16 （表示無法到達）， 是直接交付。 1 3 R2 R2 R1 網 1 網 3 網 2 R2 R1 網 1 網 3 網 2 網 1出了故障 正 常 情 況 1 1 ? 1 16 ? 1 2 R1 1 2 R1 R2 以后又更新自己的路由表為 “ 1, 4, R1”， 表明 “ 我到網 1 距離是 4， 下一跳經過 R1”。 這是 RIP 的一個主要缺點 。（這里的“毒性”表示度量為 16，說明網絡出現故障）即已經從某個接口來的路由表項，在通過同樣的接口回送過去時，將其度量置為 16。 ? OSPF是分布式的 鏈路狀態(tài)協議 。 ? 只有當鏈路狀態(tài)發(fā)生變化時，路由器才用洪泛法向所有相鄰路由器發(fā)送此信息。 OSPF 的更新過程收斂得快是其重要優(yōu)點。 自治系統(tǒng) AS OSPF 劃分為兩種不同的區(qū)域 區(qū)域 區(qū)域 主干區(qū)域 至其他自治系統(tǒng) R9 R7 R6 R5 R4 R3 R2 R1 網 8 網 6 網 3 網 2 網 1 網 7 區(qū)域 網 4 網 5 R8 劃分區(qū)域 ? 劃分區(qū)域的好處就是將利用 洪泛法 交換鏈路狀態(tài)信息的范圍局限于每一個區(qū)域而不是整個的自治系統(tǒng)，這就減少了整個網絡上的通信量。主干區(qū)域的標識符規(guī)定為 。這樣做可減少路由信息的通信量。因此， OSPF 對于不同類型的業(yè)務可計算出不同的路由。 ? 支持可變長度的子網劃分和無分類編址 CIDR。因此當互聯網規(guī)模很大時， OSPF 協議要比距離向量協議 RIP 好得多。 ? 類型 3，鏈路狀態(tài)請求 (Link State Request)分組。 ? 指定的路由器代表該局域網上所有的鏈路向連接到該網絡上的各路由器發(fā)送狀態(tài)信息。 ? BGP 的較新版本是 1995 年發(fā)表的 BGP4（ BGP 的第 4 個版本）。 ? 自治系統(tǒng)之間的路由選擇必須考慮有關策略。 ? 使用 TCP 連