BGP路由的動態性研究

蘇申 方濱興

摘 要 BGP路由的不斷變化使得對協議策略的維護、定位路由故障、控制協議流量十分困難。本文從優化BGP路由策略配置、解釋產生路由更新的根本來源、預測BGP的路由行為等角度對BGP路由的動態特征的相關研究進行介紹，進而對不同研究進行比較分類，剖析其的優劣。

關鍵詞 BGP；路由動態性；路由策略

中圖法分類號 TP393 文獻標識碼：A 文章編號：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路由系統存在大量的更新報文，這導致BGP的路由表頻繁發生變化，從而增大了路由系統的開銷、并降低了網絡的可控性和穩定性。因此，如下研究營運而生：需要對BGP路由的動態特征進行描述、分析和解釋，而在此基礎上對BGP路由行為展開預測，進而為工業界提出改善BGP協議配置的指導方法。

1997年，Labovitz等人[1]系統地描述了BGP路由動態特征，指出BGP路由系統中大量的更新報文并不是由路由配置或者網絡拓撲的變化引起的，而是冗余的、病態的路由更新報文。同時，BGP路由的變化具有明顯的周期性，這與網絡的使用方式（network usage）相關。在后續研究中[2]，Labovitz等人發現通過對單一供應商的路由配置的優化，可以顯著減少冗余的BGP路由更新。2007年，文獻[3]對文獻[1]描述的BGP路由動態性重新進行了評價，指出BGP路由系統的冗余路由轉發已經大大減少了。另外，文獻[4]指出BGP更新報文的規模與Internet拓撲規模呈線性關系。文獻[5]指出Internet主體流量的路由很穩定，相比之下流量比較小的路由將會更加容易發生改變。

基于對BGP路由動態性的認識，相關研究大體可以分為：討論如何優化BGP路由策略配置，以減少冗余的路由更新[6-10]；從BGP路由行為出發，解釋產生路由更新的根本來源[11-18]；模型、預測BGP的路由行為[19-23]。鑒于目前BGP路由系統的冗余更新大大減少，第一類研究效果頗為可觀。由于BGP協議本身對路由的描述粒度限于AS級，后兩類研究的精度僅限于AS級。接下來，本文依次介紹上述3類研究工作。

1 BGP路由收斂問題

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

“路徑探索”表明BGP路由表會在特定情況下反復變化，即BGP對應特定的路由變化的收斂時間可能會很長，極端情況下，會出現持續的路由震蕩。文獻[7]從理論的角度對BGP的路由收斂問題進行了形式化論證，由此推得：BGP路由系統是否收斂等價于這個網絡的BGP路由配置是否存在一個“爭執輪”。

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

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

第二類方法強調在BGP基礎上增加全局的調度[11]。通過收集每個AS的路由配置策略，并從整體上檢查AS間是否存在相互沖突的路由策略。這類方法的缺點是BGP路由配置策略本身通常關乎商業運作內情，很多AS是難于主動提供這樣的數據，因而整個Internet的協作基本是不可能實現的。

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

2 定位BGP路由變化來源

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

3 AS路徑預測

為了控制網絡流量、優化網絡配置，AS管理員往往需要主動修改網絡配置。因此預測BGP路由（預測AS路徑），也是一個重要且熱門的研究課題。

traceroute可以探測流量在AS間的實際傳播路徑，因此這類研究中最為常見的討論方法就是利用traceroute主動探測IP級路徑，而后將IP地址轉化為AS號。這種方法存在不可小視的現實缺陷。首先，與拓撲測量的問題一樣，將IP地址映射為AS號的過程會帶來無法忽略的誤差。其次，流量經過的實際路徑與BGP路由頁并不是完全一致。最后，這種方法需要從預測起點發起traceroute探測，而實際情況下卻往往難以滿足，并且Internet的骨干網絡中很多路由器并不響應traceroute探測。

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

文獻[26]采用類似神經網絡的方法從BGP數據中抽取路由策略，通過迭代地調整網絡路由策略使得其路由輸出與訓練數據能夠達成現實一致，而后再用訓練獲得的路由策略進行AS路徑預測。文獻中將一個AS劃分成若干個“準路由器”，不同“準路由器”采取的路由策略頁隨即有所不同，因此該方法可以體現BGP路由的多樣性。但這種方法的缺點缺課分析表現在其中用于訓練的數據僅只考慮一副快照，而實際的網絡環境卻是變化補丁的，因而這種預測后得到的結果也是片面的。

4 結束語

對于BGP行為的理解，本質上是對經濟的行為的理解，更是對人的行為的理解。如果Internet的經濟結構發生改變，或者能夠從一個新的角度去觀察BGP行為，往往就會獲得某種全新的、甚至更進一步的理解。因此對BGP路由動態性的研究只能解說哪個更符合目前的Internet特征，而不能評說基礎事實是什么，因為基礎事實會隨著經濟規律變化。

本文從優化BGP路由策略配置，解釋產生路由更新的根本來源；模擬、預測BGP的路由行為3個角度對動態BGP路由的相關研究進行了詳細的探討與介紹。期待相關研究機構、運營商能夠提供更充分的數據來源，為BGP動態性的相關研究提供有利、且重要的研究環境和基礎。

參 考 文 獻：

[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.