Internet域間路由建模與分析研究.pdf

1、二十世紀(jì)九十年代以來，工業(yè)界基本沒有對邊界網(wǎng)關(guān)協(xié)議（Border Gateway Protocol，BGP）進(jìn)行改良，然而BGP協(xié)議服務(wù)的對象—Internet在人類社會生活中卻扮演著越來越重要的角色。隨著Internet的網(wǎng)絡(luò)規(guī)模、通信體量以及應(yīng)用種類的快速增長，那些在BGP設(shè)計之初并不重要的缺陷逐漸成為限制Internet發(fā)展的關(guān)鍵因素。因為BGP協(xié)議可擴(kuò)展性差、控制語義模糊，所以理解和預(yù)測BGP的路由行為十分困難，這導(dǎo)致網(wǎng)絡(luò)性能難

2、以優(yōu)化、路由故障難以定位、網(wǎng)絡(luò)應(yīng)用服務(wù)質(zhì)量難以保障。因為BGP協(xié)議不檢驗路由的可信性和有效性，所以無效的、甚至惡意篡改的路由內(nèi)容極易在BGP路由系統(tǒng)中擴(kuò)散，這導(dǎo)致網(wǎng)絡(luò)流量易被劫持，進(jìn)而給網(wǎng)絡(luò)用戶造成經(jīng)濟(jì)損失。此外，Internet和BGP協(xié)議都采用分布式控制，并以經(jīng)濟(jì)利益為驅(qū)動。無論Internet是否以地址為核心，這個運(yùn)作模式不會改變。因此，對于BGP協(xié)議的研究不但有助于改善目前BGP協(xié)議的性能，還對未來域間路由協(xié)議的開發(fā)具有指導(dǎo)意義

3、?；谏鲜鲈?，本文對BGP路由系統(tǒng)的拓?fù)浣Y(jié)構(gòu)、路由的決策過程、傳播過程和安全問題進(jìn)行研究，并在深化已有認(rèn)識和理解的基礎(chǔ)上，對現(xiàn)有研究的不足之處提出改進(jìn)。具體的，本文的主要工作和貢獻(xiàn)包括：
　　第一，評價AS（Autonomous System，自治域）級拓?fù)涞臏y量覆蓋范圍。被動測量是目前測量AS級拓?fù)涞闹饕椒?，其測量結(jié)果受限于每個測量點(diǎn)的位置。本文從理論角度分析并描述了測量點(diǎn)的在理論上的測量覆蓋結(jié)果上限，并比較實際測量結(jié)果與理

4、論測量上限的差距。發(fā)現(xiàn)實際測量結(jié)果覆蓋理論上限中大部分的C-P（Customer-Provider，客戶-供應(yīng)商）邊，但只覆蓋理論上限的大約30％的P-P（Peer-Peer，對等）邊。本文進(jìn)一步討論了測量點(diǎn)的測量覆蓋范圍與哪些因素有關(guān)，發(fā)現(xiàn)測量點(diǎn)對被測AS的拓?fù)涓采w率隨著被測AS與測量點(diǎn)間距離、測量點(diǎn)和被測AS鄰居數(shù)量的增大而降低，而且測量覆蓋率與測量點(diǎn)的路由策略沒有明顯關(guān)系?；谠u價結(jié)論，本文進(jìn)一步提出了優(yōu)化測量點(diǎn)部署算法，相比于目

5、前最優(yōu)的測量點(diǎn)部署算法，該算法測得P-P邊多11%，相比于隨機(jī)選點(diǎn)，該算法測得P-P邊多30%。
　　第二，量化BGP路由策略的變化。BGP路由策略的變化導(dǎo)致路由行為規(guī)律發(fā)生變化，這會導(dǎo)致相關(guān)研究的結(jié)論出現(xiàn)偏差。本文提出鄰居優(yōu)先級模型以對BGP路由策略進(jìn)行細(xì)粒度建模，并討論了該模型的正確性。基于鄰居優(yōu)先級模型，本文提出量化BGP路由策略動態(tài)性的算法，并將該算法應(yīng)用于2012年的Routeviews數(shù)據(jù)。進(jìn)一步的分析發(fā)現(xiàn)：至少20%

6、的前綴的選路策略在6個月內(nèi)至少發(fā)生了一次變化；一個AS的路由策略以恒定的速率變化，但是非頂級AS可能會經(jīng)歷大規(guī)模的路由策略突變；拓?fù)浣Y(jié)構(gòu)和AS商業(yè)關(guān)系的變化不是路由策略變化的主因。
　　第三，AS級路徑預(yù)測。預(yù)測一對AS間的路徑有助于網(wǎng)絡(luò)診斷、流量工程和協(xié)議行為分析，然而目前存在的解決方案只能預(yù)測最佳路徑，無法在網(wǎng)絡(luò)配置發(fā)生動態(tài)變化時預(yù)測相應(yīng)的路徑變化。為了預(yù)測在動態(tài)的網(wǎng)絡(luò)環(huán)境中的AS級路徑，本文基于鄰居優(yōu)先級模型提出從累積的BG

7、P路由數(shù)據(jù)中抽取網(wǎng)絡(luò)拓?fù)浜瓦x路配置，并討論了如何模擬動態(tài)網(wǎng)絡(luò)環(huán)境以進(jìn)行AS路徑預(yù)測。本文從理論上證明了本文構(gòu)建的模型網(wǎng)絡(luò)的路由是收斂的。進(jìn)一步的實驗評價表明，本文提出的方法能夠更準(zhǔn)確且更充分的預(yù)測AS路徑。
　　第四，BGP異常路由檢測。BGP路由系統(tǒng)在配置不當(dāng)時或者受到惡意攻擊時十分脆弱，因此需要實時檢測BGP路由系統(tǒng)的異常路由行為。如果異常路由檢測的誤報率很高，系統(tǒng)的使用者就需要通過其它方式進(jìn)一步驗證，這降低了異常路由的檢測的