路由算法與路由協議
選擇轉發(fā)IP分組的過程叫做：路由選擇
路由選擇的核心：路由選擇算法
帶權無向圖
將網絡抽象為一個帶權無向圖G=(N, E)，N代表結點集合，E是邊的集合
網絡中的路由器抽象為G的結點，連接兩個路由器的網絡鏈路抽象為G的邊
網絡鏈接的費用（比如時延）抽象為G的權值
存在結點X、結點Y：
如果兩個結點間有邊，則費用為：X到Y的權值
如果兩個結點間沒有邊，費用為：無限
路由選擇算法的分類
分類標準
- 是否需要全局信息
- 靜態(tài)動態(tài)
- 是否敏感
依據 是否需要全局信息 進行的劃分
- 全局式 路由選擇算法，典型：鏈路狀態(tài) 路由選擇算法（LS算法）
- 分布式 路由選擇算法，典型：距離向量 路由選擇算法（DV算法）
依據 靜態(tài)動態(tài) 進行的劃分
- 靜態(tài)：人工干預
- 動態(tài)：LS算法、DV算法
鏈路狀態(tài)路由選擇算法（LS算法）
是一種全局式路由選擇算法，每個路由器在計算路由時，需要構建整個網絡的拓撲圖
利用 Dijkstra算法 求最短路徑
| 標識 | 含義 |
|---|---|
| D(v) | 到本次迭代為止，源結點到目的結點v的當前路徑距離 |
| P(v) | 到本次迭代為止，在源結點到目的結點v的當前路徑上，結點v的前序結點 |
| c(x,y) | 結點x到結點y之間直接鏈路的費用 |
| S | 結點的集合，用于存儲源結點到該結點的最短路徑已求出的終點集合 |
P(v)：如果路徑上只有兩個結點，則該值就是最后一個結點
例如：x->y P(y)=y
c(x,y)：如果x和y之間沒有鏈路相連，則c(x,y)=
距離向量路由選擇算法（DV算法）
基礎是 Bellman-Ford 方程（簡稱 B-F方程）
令 dx(y) 表示結點x到結點y的路徑的最低費用，根據 B-F 方程，有以下的公式：
dx(y) = min { c(x,v) + dv(y) }
例子：
x -- 2 -- y、y -- 3 -- z、x -- 7 -- z
計算結果：
dx(z) = min { c(x,z)+dz(z), c(x,y)+dy(z) } = min { 7+0, 2+3 } = 5
特點
- 路由器分別維護自己的轉發(fā)表（DV），并且接收鄰居（與本路由器直接相連）的通知
- 收到通知進行對比更新
層次化路由選擇
大規(guī)模網絡路由選擇 最有效可行的解決方案
層次化路由選擇原理
大規(guī)?；ヂ摼W的路由劃分為兩層：
- 自治系統 內 路由選擇：計算到達自治系統內目的網絡的路由
- 自治系統 間 路由選擇：負責其他自治系統網絡的可達性消息
自治系統：
autonomous system, AS，互聯網按組織邊界劃分為多個自治系統。每個自治系統由運行 相同 路由協議和路由選擇算法的路由器組成
網關路由器：
每個自治系統存在至少一個與其他自治系統互連的路由器
Internt路由選擇協議
根據層次化路由選擇劃分為：
- 內部網關協議（Interior Gateway Protocol, IGP），Internet自治系統 內 路由選擇協議
- 外部網關協議（Exterior Gateway Protocol, EGP），Internet自治系統 間 路由選擇協議
IGP的典型協議：
- 路由信息協議（Routing Information Protocol, RIP）
- 開放最短路徑優(yōu)先協議（Open Shortest Path First, OSPF）
EGP的典型協議：
- 邊界網關協議（Border Gateway Protocol, BGP）
RIP
適用于 較小 的自治系統（AS），基于 距離向量路由選擇算法 的IGP協議
RIP報文，封裝進 UDP 數據報
RIP特性：
- RIP在度量路徑時采用 跳數
- RIP的費用定義在源路由器和目的子網之間
- RIP被限制在網絡直徑不超過 15跳 的自治系統內部使用
OSPF
適用于 規(guī)模較大 的自治系統（AS），基于 鏈路狀態(tài)路由選擇算法 的IGP協議
直接封裝于 IP 數據報
OSPF的優(yōu)點：
- 安全
- 支持多條相同費用路徑
- 支持區(qū)別化費用度量
- 支持單播路由與多播路由
- 分層路由
BGP
實現跨自治系統的路由信息轉換。典型版本是BGP4
直接封裝于 TCP 報文段
BGP的4種報文：
- OPEN（打開）報文
- UPDATE（更新）報文
- KEEPALINE（?；睿﹫笪?/li>
- NOTIFICATION（通知）報文
