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

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

2、以優(yōu)化、路由故障難以定位、網(wǎng)絡(luò)應(yīng)用服務(wù)質(zhì)量難以保障。因?yàn)锽GP協(xié)議不檢驗(yàn)路由的可信性和有效性，所以無(wú)效的、甚至惡意篡改的路由內(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ū)動(dòng)。無(wú)論Internet是否以地址為核心，這個(gè)運(yùn)作模式不會(huì)改變。因此，對(duì)于BGP協(xié)議的研究不但有助于改善目前BGP協(xié)議的性能，還對(duì)未來(lái)域間路由協(xié)議的開(kāi)發(fā)具有指導(dǎo)意義

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

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

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

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

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