蘇申 方濱興

摘 要 BGP路由的不斷變化使得對(duì)協(xié)議策略的維護(hù)、定位路由故障、控制協(xié)議流量十分困難。本文從優(yōu)化BGP路由策略配置、解釋產(chǎn)生路由更新的根本來源、預(yù)測(cè)BGP的路由行為等角度對(duì)BGP路由的動(dòng)態(tài)特征的相關(guān)研究進(jìn)行介紹，進(jìn)而對(duì)不同研究進(jìn)行比較分類，剖析其的優(yōu)劣。

關(guān)鍵詞 BGP；路由動(dòng)態(tài)性；路由策略

中圖法分類號(hào) TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-2163（2016）02-

A survey on BGP routing dynamics

Su Shen， Fang Binxing

（Network and Information Security Research Center， Harbin Institute of Technology ， Harbin 150001）

Abstract BGPs routing table changes constantly， which makes routing policy decision， locating route instabilities， and engineering traffic very hard. This paper investigates the researches of BGP route dynamics from the point of route convergence， locating route instabilities， and predicting AS level paths. And the paper also explores their advantages and disadvantages.

Key words Border Gateway Protocol （BGP）； routing dynamics； routing policy

0 引言

Internet的BGP路由系統(tǒng)存在大量的更新報(bào)文，這導(dǎo)致BGP的路由表頻繁發(fā)生變化，從而增大了路由系統(tǒng)的開銷、并降低了網(wǎng)絡(luò)的可控性和穩(wěn)定性。因此，如下研究營(yíng)運(yùn)而生：需要對(duì)BGP路由的動(dòng)態(tài)特征進(jìn)行描述、分析和解釋，而在此基礎(chǔ)上對(duì)BGP路由行為展開預(yù)測(cè)，進(jìn)而為工業(yè)界提出改善BGP協(xié)議配置的指導(dǎo)方法。

1997年，Labovitz等人[1]系統(tǒng)地描述了BGP路由動(dòng)態(tài)特征，指出BGP路由系統(tǒng)中大量的更新報(bào)文并不是由路由配置或者網(wǎng)絡(luò)拓?fù)涞淖兓鸬?，而是冗余的、病態(tài)的路由更新報(bào)文。同時(shí)，BGP路由的變化具有明顯的周期性，這與網(wǎng)絡(luò)的使用方式（network usage）相關(guān)。在后續(xù)研究中[2]，Labovitz等人發(fā)現(xiàn)通過對(duì)單一供應(yīng)商的路由配置的優(yōu)化，可以顯著減少冗余的BGP路由更新。2007年，文獻(xiàn)[3]對(duì)文獻(xiàn)[1]描述的BGP路由動(dòng)態(tài)性重新進(jìn)行了評(píng)價(jià)，指出BGP路由系統(tǒng)的冗余路由轉(zhuǎn)發(fā)已經(jīng)大大減少了。另外，文獻(xiàn)[4]指出BGP更新報(bào)文的規(guī)模與Internet拓?fù)湟?guī)模呈線性關(guān)系。文獻(xiàn)[5]指出Internet主體流量的路由很穩(wěn)定，相比之下流量比較小的路由將會(huì)更加容易發(fā)生改變。

基于對(duì)BGP路由動(dòng)態(tài)性的認(rèn)識(shí)，相關(guān)研究大體可以分為：討論如何優(yōu)化BGP路由策略配置，以減少冗余的路由更新[6-10]；從BGP路由行為出發(fā)，解釋產(chǎn)生路由更新的根本來源[11-18]；模型、預(yù)測(cè)BGP的路由行為[19-23]。鑒于目前BGP路由系統(tǒng)的冗余更新大大減少，第一類研究效果頗為可觀。由于BGP協(xié)議本身對(duì)路由的描述粒度限于AS級(jí)，后兩類研究的精度僅限于AS級(jí)。接下來，本文依次介紹上述3類研究工作。

1 BGP路由收斂問題

冗余的BGP路由更新導(dǎo)致BGP路由表頻繁發(fā)生變化，一條BGP路由的AS路徑的變化通常都符合如下模式：一個(gè)長(zhǎng)時(shí)間存在的AS路徑在短時(shí)間內(nèi)頻繁地發(fā)生變化，最后變成某一個(gè)其它的AS路徑并繼續(xù)長(zhǎng)時(shí)間存在，這種現(xiàn)象稱為“路徑探索”（path exploration）。究其本質(zhì)就是在某一個(gè)網(wǎng)絡(luò)事件的影響下，某個(gè)AS改變其BGP路由表，由此而使得一定范圍內(nèi)與之連接的AS的路由表頁隨即發(fā)生震蕩。文獻(xiàn)[6]通過聲明和撤銷“種子前綴”（beacons）來觀察相應(yīng)的路由行為來研究“路徑探索”現(xiàn)象，進(jìn)一步發(fā)現(xiàn)“路徑探索”多會(huì)持續(xù)幾分鐘，而且這一現(xiàn)象在Internet核心網(wǎng)絡(luò)并不明顯，在邊緣網(wǎng)絡(luò)則表現(xiàn)更為突出。

“路徑探索”表明BGP路由表會(huì)在特定情況下反復(fù)變化，即BGP對(duì)應(yīng)特定的路由變化的收斂時(shí)間可能會(huì)很長(zhǎng)，極端情況下，會(huì)出現(xiàn)持續(xù)的路由震蕩。文獻(xiàn)[7]從理論的角度對(duì)BGP的路由收斂問題進(jìn)行了形式化論證，由此推得：BGP路由系統(tǒng)是否收斂等價(jià)于這個(gè)網(wǎng)絡(luò)的BGP路由配置是否存在一個(gè)“爭(zhēng)執(zhí)輪”。

雖然路由抖動(dòng)抑制可以加速BGP收斂，但是該方法并不能從根本上解決BGP協(xié)議的收斂問題，目前BGP收斂問題的研究實(shí)現(xiàn)方法大體分為3類。在此，對(duì)這3類方法給出如下應(yīng)用解析：

第一類方法采用實(shí)時(shí)的路由策略沖突檢查。通過累計(jì)收集歷史路由[9-10]，檢查哪些路由更新會(huì)導(dǎo)致循環(huán)的路由更新轉(zhuǎn)發(fā)，進(jìn)而調(diào)整路由策略以屏蔽這些病態(tài)的路由更新。這類方法的缺點(diǎn)在于通信開銷比較大；而且其解決方案也并非檢查是否存在“爭(zhēng)執(zhí)輪”，因而本可以收斂的路由策略也會(huì)發(fā)生一定修改。

第二類方法強(qiáng)調(diào)在BGP基礎(chǔ)上增加全局的調(diào)度[11]。通過收集每個(gè)AS的路由配置策略，并從整體上檢查AS間是否存在相互沖突的路由策略。這類方法的缺點(diǎn)是BGP路由配置策略本身通常關(guān)乎商業(yè)運(yùn)作內(nèi)情，很多AS是難于主動(dòng)提供這樣的數(shù)據(jù)，因而整個(gè)Internet的協(xié)作基本是不可能實(shí)現(xiàn)的。

第三類方法放棄全局協(xié)作，而對(duì)每個(gè)AS的BGP配置提出限制規(guī)則。文獻(xiàn)[24]指出，只要每個(gè)AS的BGP輸出過濾規(guī)則滿足：“對(duì)供應(yīng)商和對(duì)等AS只轉(zhuǎn)發(fā)本地或者來自客戶AS的路由”， Internet的全局BGP路由就可以保證收斂。然而，某些AS之間的商業(yè)關(guān)系定性復(fù)雜，不能用簡(jiǎn)單的“客戶、供應(yīng)商、對(duì)等AS”來進(jìn)行確切描述。同時(shí)，對(duì)于大規(guī)模ISP，其內(nèi)部客戶AS的路由數(shù)量趨多，且變化非常頻繁，想要讓BGP配置滿足上述規(guī)即已成為一項(xiàng)頗具難度的研究工作。

2 定位BGP路由變化來源

除了冗余的路由更新，BGP路由系統(tǒng)中的路由更新主要是由拓?fù)渥兓?、軟硬件故障或者路由策略的變化引起的[12]。定位這些路由更新的實(shí)際來源可以幫助AS管理員定位路由故障、提高網(wǎng)絡(luò)性能并避免路由震蕩，因此學(xué)術(shù)界對(duì)此開展了大量研究工作[13-19]，并將這類研究統(tǒng)稱為定位路由變化（Locating route instabilities）。其基本思路為：將路由更新按著前綴、時(shí)間、觀測(cè)點(diǎn)三個(gè)維度劃分成不同的路由事件，并根據(jù)同一個(gè)路由事件中的路由更新的特征推測(cè)路由事件的類型，進(jìn)而定位路由更新的來源。當(dāng)一條穩(wěn)定的路由經(jīng)過“路徑探索”過程變?yōu)榱硗庖粭l穩(wěn)定的路由，要么是舊的路由被撤銷，要么是新的優(yōu)先級(jí)更高的路由被聲明[13]。文獻(xiàn)[16]證明了該研究可以將70%的路由更新的來源精確定位到某一條AS邊上。雖然進(jìn)一步細(xì)化定位精度存在實(shí)施困難，文獻(xiàn)[17]則轉(zhuǎn)而討論了如何在定位路由故障以后，再通過修改路由配置以避免受到路由故障的影響。

3 AS路徑預(yù)測(cè)

為了控制網(wǎng)絡(luò)流量、優(yōu)化網(wǎng)絡(luò)配置，AS管理員往往需要主動(dòng)修改網(wǎng)絡(luò)配置。因此預(yù)測(cè)BGP路由（預(yù)測(cè)AS路徑），也是一個(gè)重要且熱門的研究課題。

traceroute可以探測(cè)流量在AS間的實(shí)際傳播路徑，因此這類研究中最為常見的討論方法就是利用traceroute主動(dòng)探測(cè)IP級(jí)路徑，而后將IP地址轉(zhuǎn)化為AS號(hào)。這種方法存在不可小視的現(xiàn)實(shí)缺陷。首先，與拓?fù)錅y(cè)量的問題一樣，將IP地址映射為AS號(hào)的過程會(huì)帶來無法忽略的誤差。其次，流量經(jīng)過的實(shí)際路徑與BGP路由頁并不是完全一致。最后，這種方法需要從預(yù)測(cè)起點(diǎn)發(fā)起traceroute探測(cè)，而實(shí)際情況下卻往往難以滿足，并且Internet的骨干網(wǎng)絡(luò)中很多路由器并不響應(yīng)traceroute探測(cè)。

基于所有AS的路由轉(zhuǎn)發(fā)都符合AS商業(yè)關(guān)系的路由策略這一基礎(chǔ)假設(shè)，文獻(xiàn)[22- 23]將預(yù)測(cè)AS間路徑轉(zhuǎn)化為計(jì)算一對(duì)AS間的符合“無谷底”模型的最短路徑。后續(xù)工作驗(yàn)證了這一方法的正確性[25]，然而該方法卻無法體現(xiàn)BGP路由的多樣性（即同一個(gè)AS的不同路由器到達(dá)特定目標(biāo)前綴的AS路徑可能會(huì)存在著不一致），而且最短的符合“無谷底”模型的AS路徑頁可能不止一條，因此這種方法的精確性還有待改善。

文獻(xiàn)[26]采用類似神經(jīng)網(wǎng)絡(luò)的方法從BGP數(shù)據(jù)中抽取路由策略，通過迭代地調(diào)整網(wǎng)絡(luò)路由策略使得其路由輸出與訓(xùn)練數(shù)據(jù)能夠達(dá)成現(xiàn)實(shí)一致，而后再用訓(xùn)練獲得的路由策略進(jìn)行AS路徑預(yù)測(cè)。文獻(xiàn)中將一個(gè)AS劃分成若干個(gè)“準(zhǔn)路由器”，不同“準(zhǔn)路由器”采取的路由策略頁隨即有所不同，因此該方法可以體現(xiàn)BGP路由的多樣性。但這種方法的缺點(diǎn)缺課分析表現(xiàn)在其中用于訓(xùn)練的數(shù)據(jù)僅只考慮一副快照，而實(shí)際的網(wǎng)絡(luò)環(huán)境卻是變化補(bǔ)丁的，因而這種預(yù)測(cè)后得到的結(jié)果也是片面的。

4 結(jié)束語

對(duì)于BGP行為的理解，本質(zhì)上是對(duì)經(jīng)濟(jì)的行為的理解，更是對(duì)人的行為的理解。如果Internet的經(jīng)濟(jì)結(jié)構(gòu)發(fā)生改變，或者能夠從一個(gè)新的角度去觀察BGP行為，往往就會(huì)獲得某種全新的、甚至更進(jìn)一步的理解。因此對(duì)BGP路由動(dòng)態(tài)性的研究只能解說哪個(gè)更符合目前的Internet特征，而不能評(píng)說基礎(chǔ)事實(shí)是什么，因?yàn)榛A(chǔ)事實(shí)會(huì)隨著經(jīng)濟(jì)規(guī)律變化。

本文從優(yōu)化BGP路由策略配置，解釋產(chǎn)生路由更新的根本來源；模擬、預(yù)測(cè)BGP的路由行為3個(gè)角度對(duì)動(dòng)態(tài)BGP路由的相關(guān)研究進(jìn)行了詳細(xì)的探討與介紹。期待相關(guān)研究機(jī)構(gòu)、運(yùn)營(yíng)商能夠提供更充分的數(shù)據(jù)來源，為BGP動(dòng)態(tài)性的相關(guān)研究提供有利、且重要的研究環(huán)境和基礎(chǔ)。

參 考 文 獻(xiàn)：

[1] LABOVITZ C， MALAN G， JAHANIAN F. Internet routing instability [J]. IEEE/ACM Transactions on Networking （TON）， 1998， 6（5）： 515- 528.

[2] LABOVITZ C， MALAN G， JAHANIAN F. Origins of Internet routing instability [C]// //Proceeding of IEEE INFOCOM， [S. l.]： IEEE 1999： 218-226.

[3] LI J， GUIDERO M， WU Z， et al. BGP Routing Dynamics Revisited [J]. ACM SIGCOMM Computer Communication Review， 2007， 37（2）： 5-16.

[4] ELMOKASHFI A， DHAMDHERE A. Revisiting BGP churn growth [J]. ACM SIGCOMM Computer Communication Review， 2014， 44（1）： 5- 12.

[5] REXFORDJ， WANG J， XIAO Z， et al. BGP routing stability of popular destinations [C] //ACM SIGCOMM Internet Measurement Workshop （IMW）， Pittsburgh： ACM， ， 2003：197-202.

[6] OLIVEIRA R， ZHANG B， PEI D， et al. Quantifying path exploration in the Internet [J]. IEEE/ACM Transaction on Networking， 2009， 17（2）： 445- 458.

[7] GRIFFIN T， SHEPHERD F， WILFONG G. The stable paths problem and inter domain routing [J]. IEEE/ACM Transaction on Networking， 2002， 10（2）： 232-243.

[8] Labovitz C， Ahuja A， Bose A， Jahanian F. An experimental study of Internet routing convergence [R]. Tech. Rep. MSR-TR-2000-08， Microsoft Research， 2000.

[9] Yilmaz S， Matta I. An Adaptive Policy Management Approach to BGP Convergence [D]. Boston， MA， USA： Boston University ， 2006.

1 [10] GRIFFIN T， WILFONG G. A safe path vector protocol [C]// Proceeding of IEEE INFOCOM， Tel Aviv， Israel

： ACM， 2000： 490-499.

[11] GOVINDAN R， ALAETTINOGLU C， EDDY G， et al. An architecture for stable， analyzable Internet routing [J]. IEEE Network： The Magazine of Global Internetworking， 1999， 13（1）： 29-35.

[12] MAHAJAN R， WETHERALL D， ANDERSON T. Understanding BGP misconfiguration [C]// SIGCOMM 2002： Proceedings of the 2002 conference on Applications， technologies， architectures， and protocols for computer communications， Pittsburgh： ACM，2002： 3-16.

[13] FELDMANN A， MAENNEL O， MAO Z. Locating internet routing instabilities [C]// proceeding of ACM SIGCOMM. Portland： ACM， 2004， 34（4）：205-218.

[14] LAD M， ZHANG L， MASSEY D. Link-Rank： A graphical tool for capturing BGP routing dynamics [J]. Network Operations and Management Symposium， 2004， 1： 617- 640.

[15] MAENNEL O， FELDMANN A. Realistic BGP traffic for test labs [C] // proceeding of ACM SIGCOMM. Pittsburgh： ACM， 2002， 32（4）：31-44.

[16] Caesar M， Subramanian L， Katz R. Towards Localizing Root Causes of BGP Dynamics [EB/OL]. （2003-11） http：//web.engr.illinois.edu/～caesar/papers/rootcause.pdf.

[17] JAVED U， CUNHA I， CHOFFINES D， et al. PoiRoot： Investigating the Root Cause of Interdomain Path Changes [C]//proceeding of ACM SIGCOMM， HongKong： ACM， 2013， 43（4）：183-194.

[18] Caesar M， Subramanian L， Katz R. Route cause analysis of Internet routing dynamics [R]. Tech. rep.， UC Berkeley UCB/CSD-04-1302， 2003.

[19] LAD M， NANAVATI A， MASSEY D， et al. An algorithmic approach to identifying link failures [C]// Proceeding of PRDC， Papeete， Tahiti：IEEE， 2004：：25 - 34.

[20] Quoitin B. C-BGP， an effcient BGP simulator [EB/OL][2003]. http：//cbgp.info.ucl.ac.be/

[21] QUOTIN B， UHLIG S. Modeling the routing of an autonomous system with C-BGP [J]. IEEE Network： The Magazine of Global Internetworking， 2005， 19（6）： 12- 19.

[22] WENPING D， MUHLBAUER W， YUEXIANG Y， et al. Shedding light on the use of AS relationships for path inference [J]. Communications and Networks， 2012， 14（3）： 336- 345.

[23] YANG G， DOU W. An efficient algorithm for AS path inferring [C]// ICHIT. Daejeon： ACM， 2009：151-154.

[24] GAO L， REXFORD J. Stable Internet routing without global coordination [J]. IEEE/ACM Transactions on Networking （TON）， 2001， 9（6）： 681- 692.

[25] MüHLBAUER W， UHLIG S， FU B， et al. In search for an appropriate granularity to model routing policies [C]// SIGCOMM 2007： Proceedings of the 2007 conference on Applications， technologies， architectures， and protocols for computer communications. Kyoto： ACM， 2007：145- 156.

[26] HLBAUER W， FELDMANN A， MAENNEL O， et al. Building an AS-topology model that captures route diversity [C]// SIGCOMM. Pisa： ACM， 2006：36（4）：195-206.