路由演算法
路由演算法分類
-
靜態路由：
- 手工配置
- 路由更新慢
- 優先級高
-
動態路由：
- 路由更新快
- 定期更新
- 及時回應鏈路費用或網路拓撲變化
-
全域資訊：
- 所有路由器掌握完整的網路拓撲和鏈路費用資訊
- E.g. 鏈路狀態(LS) 路由演算法
-
分散(decentralized)資訊：
- 路由器只掌握物理相連的鄰居以及鏈路費用
- 鄰居間資訊交換、運算的迭代程序
- E.g. 距離向量(DV) 路由演算法
鏈路狀態路由演算法
Dijkstra 演算法
- 所有結點(路由器)掌握網路拓撲和鏈路費用
- 通過“鏈路狀態廣播”
- 所有結點擁有相同資訊
- 計算從一個結點(“源”)到達所有其他結點的最短路徑
- 獲得該結點的轉發表
- 迭代: k次迭代后，得到到達k個目的結點的最短路徑
符號:
- c(x,y): 結點x到結點y鏈路費用；如果x和y不直接相連，則=∞
- D(v): 從源到目的v的當前路徑費用值
- p(v): 沿從源到v的當前路徑，v的前序結點
- N’: 已經找到最小費用路徑的結點集合
Dijkstra 演算法:討論
- 演算法復雜性: n個結點
- 每次迭代: 需要檢測所有不在集合N’中的結點w
- n(n+1)/2次比較: O(n 2 )
- 更高效的實作: O(nlogn)
- 存在震蕩(oscillations)可能:
- e.g., 假設鏈路費用是該鏈路承載的通信量:
- e.g., 假設鏈路費用是該鏈路承載的通信量:
距離向量路由演算法
重點 ：結點獲得最短路徑的 下跳 一跳, 該資訊用于轉發表中
- 異步迭代:
- 引發每次區域迭代的因素
- 區域鏈路費用改變
- 來自鄰居的DV更新
- 分布式:
- 每個結點只當DV變化時才通告給鄰居
- 鄰居在必要時（其DV更新后發生改變）再通告它們的鄰居
鏈路費用變化:
- 結點檢測本地鏈路費用變化
- 更新路由資訊，重新計算距離向量
- 如果DV 改變，通告所有鄰居
- t 0 : y 檢測到鏈路費用改變 ，更新DV ，通告其鄰居.
- t 1 : z 收到y的 的DV 更新，更新其距離向量表，計算到達x 的最新其 最小費用，更新其DV ，并發送給其所有鄰居.
- t 2 : y 收到z的 的DV 更新， 更新其距離向量 表，重新計算y的 的DV， ，未發生改變，不再向z 發送DV.
好訊息傳播快！
毒性逆轉(poisoned reverse)
- 如果一個結點(e.g. Z)到達某目的(e.g.X)的最小費用路徑是通過某個鄰居(e.g.Y)，則：
- 通告給該鄰居結點到達該目的的距離為無窮大
無窮計數問題
層次路由
將任意規模網路抽象為一個圖計算路由- 過于理想化
- 標識所有路由器
- “扁平”網路
- 在實際網路（尤其是大規模網路）中， 不可行！
網路規模：考慮6億目的結點的網路 - 路由表幾乎無法存盤！
- 路由計算程序的資訊（e.g. 鏈路狀態分組、DV）交換量巨大，會淹沒鏈路！
- 管理自治：
- 每個網路的管理可能都期望自主控制其網內的路由
- 互聯網(internet) = 網路之網路(network of networks)
聚合路由器為一個區域：自治系統AS(autonomous systems)，同一AS內的路由器運行相同的路由協議(演算法)，自治系統內部路由協議(“intra-AS” routingprotocol)
不同自治系統內的路由器可以運行不同的AS內部路由協議
網關路由器(gatewayrouter): 位于AS“邊緣”， 通過鏈路連接其他AS的網關路由器
互連的AS
自治系統間(Inter-AS)
RIP協議簡介
AS 內部路由
RIP: 鏈路失效、恢復
如果180秒沒有收到通告→鄰居/鏈路失效
- 經過該鄰居的路由不可用
- 重新計算路由
- 向鄰居發送新的通告
- 鄰居再依次向外發送通告（如果轉發表改變）
- 鏈路失效資訊能否快速傳播到全網？
- 可能發生無窮計數問題
- 毒性逆轉技術用于預防乒乓(ping-pong)環路(另外：無窮大距離 = 16 hops)
RIP 路由表的處理
- RIP路由表是利用一個稱作route-d (daemon)的應用層行程進行管理
- 應用行程實作
- 通告報文周期性地通過UDP資料報發送
OSPF協議簡介
- ”開放”: 公眾可用
- 采用鏈路狀態路由演算法
- LS分組擴散（通告）
- 每個路由器構造完整的網路(AS)拓撲圖
- 利用Dijkstra演算法計算路由
- OSPF通告中每個入口對應一個鄰居
- OSPF通告在整個AS范圍泛洪
- OSPF報文直接封裝到IP資料報中
- 與OSPF極其相似的一個路由協議:IS-IS 路由協議
OSPF 優點(RIP 不具備)
- 安全(security): 所有OSPF報文可以被認證(預防惡意入侵)
- 允許使用多條相同費用的路徑 (RIP只能選一條)
- 對于每條鏈路，可以針對不同的TOS設定多個不同的費用度量 (e.g., 衛星鏈路可以針對“盡力”(best effort) ToS設定“低”費用；針對實時ToS設定“高”費用)
- 集成單播路由與多播路由
- 多播OSPF協議(MOSPF) 與OSPF利用相同的網路拓撲資料
- OSPF支持對大規模AS分層(hierarchical)
分層的OSPF
BGP 協議簡介
Internet AS 間路由協議
-
邊界網關協議BGP (Border GatewayProtocol): 事實上的標準域間路由協議
- 將Internet “粘合”為一個整體的關鍵
-
BGP為每個AS提供了一種手段:
- eBGP: 從鄰居AS獲取子網可達性資訊.
- iBGP: 向所有AS內部路由器傳播子網可達性資訊.
- 基于可達性資訊與策略，確定到達其他網路的 “好”路徑
-
容許子網向Internet其余部分通告它的存在：“ 我在這兒！”
-
BGP會話(session):
- 兩個BGP路由器 (“Peers”)
-
交換BGP報文:
- 通告去往不同目的前綴（prefix）的路徑 (“路徑向量(path vector)”協議)
- 報文交換基于半永久的TCP連接
-
BGP報文:
- OPEN: 與peer建立TCP連接，并認證發送方
- UPDATE: 通告新路徑 (或撤銷原路徑)
- KEEPALIVE: 在無UPDATE時，保活連接；也用于對OPEN請求的確認
- NOTIFICATION: 報告先前報文的差錯；也被用于關閉連接
BGP路由選擇
- 網關路由器收到路由通告后，利用其輸入策略(import policy)決策接受/拒絕該路由
- e.g., 從不將流量路由到AS x
- 基于策略(policy-based) 路由
- 路由器可能獲知到達某目的AS的多條路由，基于以下準則選擇：
- 本地偏好(preference)值屬性: 策略決策(policy
decision) - 最短AS-PATH
- 最近NEXT-HOP路由器: 熱土豆路由(hot potato
routing) - 附加準則
為什么采用不同的AS 內與AS 間路由協議
- 策略(policy):
- inter-AS: 期望能夠管理控制流量如何被路由，誰路由經過其網路等.
- intra-AS: 單一管理，無需策略決策
- 規模(scale):
- 層次路由節省路由表大小，減少路由更新流量
- 適應大規模互聯網
- 性能(performance):
- intra-AS: 側重性能
- inter-AS: 策略主導
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/77770.html
標籤：其他