互聯網域間路由系統動態(tài)行為研究與機制設計.pdf

1、域間路由系統是Internet的核心基礎設施，它不僅為全網范圍內實現互聯互通提供必要的路由信息，而且以其相對穩(wěn)定性成為了Internet持續(xù)演進的基石。作為一個動態(tài)分布式系統，系統內節(jié)點間相互交換路由信息是域間路由系統運行的基本形式。這種動態(tài)行為決定了域間路由系統所呈現的擴展性、穩(wěn)定性、收斂性和安全性等一系列特征。本文針對當前域間路由系統面臨的問題，從域間路由動態(tài)行為的角度，量化路由動態(tài)行為的特征、分析路由劫持的傳播機理、探索路由行為優(yōu)

2、化方法、設計實現路由優(yōu)化和安全機制，對改善域間路由系統的擴展性、穩(wěn)定性、收斂性和安全性有著積極意義。
　　本文的貢獻主要現在以下幾個方面：
　　一、基于Internet路由數據對域間路由動態(tài)行為進行測量和分析，發(fā)現了動態(tài)行為中存在的一些病態(tài)現象。具體地，路由變化成因分析發(fā)現產生路由更新的主要原因是COMMUNITY屬性和AS路徑屬性變化，并且域間路由系統中存在大量重復的路由更新；通過分析路由更新數量在網絡前綴粒度上的分布，發(fā)

3、現路由抖動是域間路由系統中存在過量路由更新的重要原因；對路由抖動的機理進一步分析，發(fā)現路徑探測(一個網絡事件在遠端路由器引發(fā)多個路由更新的現象)對路由更新數量具有顯著的放大作用，且路徑探測過程中使用的AS路徑具有局部性（路徑局部性原理）。上述發(fā)現不僅深化對當前域間路由動態(tài)行為特征的理解，而且為路由優(yōu)化方案的設計提供了思路。
　　二、對路由劫持在域間路由系統中的傳播機理進行分析和建模，揭示了域間路由系統中自治系統（Autonomou

4、s System，簡稱AS）對路由劫持免疫力低下的原因。將AS基于BGP路由信息自我發(fā)現路由劫持的概率定義為對路由劫持的免疫能力，通過求解AS實現自我免疫的充分條件和必要條件，給出了該免疫能力的上界。分析發(fā)現，在當前的域間路由系統中，80％以上的AS對路由劫持完全沒有免疫能力，僅有不超過0.26%的AS具有大于85%的免疫能力。進一步分析AS免疫過程，揭示了造成AS免疫能力低下的“提供商柵欄”現象——提供商優(yōu)先選擇客戶路由，阻止了劫持路

5、由向被劫持者的傳播，從而阻礙了被劫持者發(fā)現路由劫持。上述研究為理解路由劫持的危害和設計路由安全監(jiān)測系統提供了理論支持。
　　三、基于路徑局部性原理，設計并實現了路徑探測聚合機制 PEA(Path Exploration Aggregation)，以抑制路由抖動和路徑探測引發(fā)的多余路由更新。該機制對反復被探測的路徑實施路由聚合并向鄰居傳播，以阻止路由抖動擴散和保護下游客戶。同時，通過增加聚合路徑的長度，降低聚合路由在下游客戶路由決策

6、中的優(yōu)先級，以減少抖動路由對正常用戶的影響。實驗表明，該機制能夠減少多達63.1%的BGP路由更新數量和高達53.3%的收斂時間，將平均每個路由事件的持續(xù)時間減少了7.39秒，三項指標均優(yōu)于以RFD（Route Flap Damping）和PED（Path Exploration Damping）為代表的同類機制。
　　四、為了阻斷不穩(wěn)定路由在域間路由系統中的傳播，提出了基于虛擬路徑的路由抖動隔離方法BGP-VP(BGP-Virt

7、ual Path)。和PEA相比，BGP-VP做出了兩點改進：一是基于路由事件而不是路由變化的發(fā)生頻率來識別路由抖動，能有效避免誤判；二是當檢測到某個網絡前綴的路由發(fā)生抖動時，將觀察到的受路由抖動影響的AS關于此網絡前綴的路由拓撲抽象成一個“單源單匯”網絡，使用以“源”和“匯”為端點的虛路徑表示經過此網絡的所有已知路徑，從而實現對AS路徑頻繁變換的隔離，增強數據平面的穩(wěn)定性。理論證明，BGP-VP除了能阻止路由抖動的傳播之外，還具有解除

8、路由“爭執(zhí)環(huán)”的能力；給定任意路由“爭執(zhí)環(huán)”，該方法在其最小“爭執(zhí)環(huán)”所涉及節(jié)點上的部署能夠消除路由抖動。以上工作對消除域間路由系統中的持續(xù)震蕩具有重要的意義。
　　五、為解決“提供商柵欄”問題、提高AS對路由劫持的的免疫能力，設計了防范路由劫持的基于協同的路由安全監(jiān)測機制。定義了AS部署協同監(jiān)測能夠獲得的安全能力、協同監(jiān)測網絡的容錯能力，并評估了不同的協同鄰居選擇策略對其產生的影響。實驗結果表明，僅與25個自治系統進行協同就可以

9、將對EA型路由劫持（Export-to-All,攻擊者向所有直接鄰居傳播惡意路由實施攻擊）的免疫能力提高到高于95%的水平。研究了協同監(jiān)測中協同關系建立的條件，即在協同監(jiān)測這種“直接互惠”型的協同關系中，參與協同的AS能從對方獲得相近的效用?？紤]兩種不同的路由劫持策略，EA和EC(Export-to-Customer，只向客戶AS宣告攻擊路由)，實驗結果表明，盡管Tier1 AS和Transit AS在防范EA類型的路由劫持具有顯著的優(yōu)

10、勢，但它們仍然需要Stub AS的協作以防范EC類型的路由劫持。
　　六、在AS之間開展路由安全監(jiān)測的協同監(jiān)測器面臨兩方面的問題，一是如何從海量的路由事件向關鍵事件聚焦，二是如何檢測針對協同監(jiān)測器本身的路由劫持。針對問題一，提出了多維度信息關聯方法，該方法從發(fā)生時間、網絡前綴和觀測點等多個維度對檢測到的網絡變化進行聚合和過濾，產生告警的源AS變化、下一跳AS變化和網絡不可達事件數量和關聯前相比，分別減少了89.01%、96.02%

11、和99.86%。針對問題二，提出了路由劫持驗證方法，從BGP異常報文、BGP路由信息、特定方向數據包和主動探測四個層面驗證針對于監(jiān)測器的路由劫持是否發(fā)生。該方法具有很高的準確性，在六個月的實驗期間未引發(fā)任何誤判(False Positives)。在解決上述問題的基礎上，設計并實現了協同監(jiān)測器，實驗評估表明該設計具有較小的網絡開銷。
　　七、要實現有效路由安全監(jiān)測的關鍵在于檢測知識庫，但IP資源所有權和使用權的頻繁變化使IP前綴—源

12、AS映射關系難以有效獲取。從知識平面(David D. Clark提出的、未來網絡的一個構件，是用于指導網絡發(fā)展的普適系統)的角度，對參與Internet地址資源分配和使用的組織及組織間關系進行建模，建立了通用的組織模型框架，基于地區(qū)級Internet注冊機構(RIR)的注冊數據得到了Internet的組織關系圖，在此基礎上構建了IP前綴和源AS映射關系的知識庫，并用于對路由劫持的檢測，取得了良好的效果。該模型和方法的應用有助于增強運營