互聯(lián)網(wǎng)域間路由系統(tǒng)動態(tài)行為研究與機制設計.pdf

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

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

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

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

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

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

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

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

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

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

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

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