BGP路由穩(wěn)定性建模與分析.pdf

1、BGP(Border Gatewav Protocol)作為Internet路由體系結構的核心協(xié)議,其穩(wěn)定性己成為人們所關心的焦點。本文以BGP路由穩(wěn)定性作為研究對象,著重研究了影響B(tài)GP路由穩(wěn)定性的關鍵問題,并提出了相應的穩(wěn)定性解決方案,為Internet穩(wěn)定運行提供了可靠的數(shù)據(jù)分析方法和快速的故障解決方案。通過理論研究、仿真分析、實驗證實的研究方法,主要做了以下幾個方面的工作:
　　 BGP路由抽象模型的研究和建立。本文以I

2、nternet路由體系結構為研究對象,深入研究了Internet路由系統(tǒng)的基本理論和動態(tài)行為規(guī)律,基于靜態(tài)或動態(tài)數(shù)學模型,系統(tǒng)分析了BGP路由抖動、收斂延時、路由配置故障等影響B(tài)GP路由穩(wěn)定性的關鍵問題。結合圖論和拓撲學的已有知識給出BGP路由抽象模型,以簡化對BGP路由穩(wěn)定性問題的研究。
　　 BGP路由抖動的檢測和消除方法研究。要從根本上解決路由抖動問題,最實際的方法就是找到路由抖動的源頭并加以抑制。根據(jù)Griffin的BG

3、P路由模型提出了改進的穩(wěn)定路徑問題模型,運用競爭有向圖理論,用形式化方法詳細描述了BGP路由抖動問題的本質,建立了抖動路由到路由策略沖突的映射關系,提出了基于消除策略沖突的路由抖動檢測和消除方法,較好地解決了BGP路由策略所引發(fā)的路由抖動問題。
　　 BGP路由收斂性分析和改進。通過對BGP路由慢收斂現(xiàn)象的研究,發(fā)現(xiàn)造成BGP路由慢收斂的4個主要原因:1)鏈路或路由器失敗造成的BGP路由探索延時;2).BGP最小路由通告時間會推

4、遲BGP最佳路由的通告時間;3)AS(AutonomousSystem)問路由策略會影響B(tài)GP路由收斂時間;4)路由抖動抑制機制也會增加BGP路由收斂時間。研究發(fā)現(xiàn),隨著網(wǎng)絡規(guī)模和連接密度的增加,BGP路由的收斂時間和消息開銷都迅速增大,Tdown(路由失效)收斂時間上限達到O(n),其中n是AS節(jié)點數(shù),消息開銷上限達到|EN|·n,其中|EN|是AS間直連的鏈路數(shù)量。針對BGP路由慢收斂問題,本文提出了基于安全路徑向量協(xié)議模型的路由收

5、斂改進算法,通過檢測AS間失效鏈路的根源節(jié)點,并在路由更新消息中攜帶根源節(jié)點信息,使接收更新的節(jié)點可以迅速撤銷所有與根源節(jié)點相關的失效路由,從而提高收斂速度,減少路由更新消息開銷。改進算法克服了BGP路由普遍采用的路由抖動抑制技術引起的網(wǎng)絡收斂變慢問題,Tdown收斂時間上限下降為O(d),其中d是網(wǎng)絡直徑,更新消息開銷下降為|EN|,BGP路由收斂速度得到了顯著提高。
　　 在BGP路由配置故障檢測方法的研究中,本文主要針對路

6、由源配置故障和路由輸出配置故障進行分析。根據(jù)目前靜態(tài)和動態(tài)檢測方法中存在的問題,提出了兩種路由配置故障檢測方法:
　　 第一種方法,通過分析AS間關系和BGP路由通告原則,提出基于BGP路由輸出規(guī)則的路由配置故障檢測算法,該算法實現(xiàn)簡單,便于實施,整個算法的時間復雜度為O(n·d),適合部署在AS間關系較為簡單的BGP網(wǎng)絡中。
　　 第二種方法,采用數(shù)理統(tǒng)計中隨機變量的假設檢驗方法,通過分析一段時間內BGP對等體之間路由

7、更新消息的統(tǒng)計量變化,實現(xiàn)基于廣義似然比檢驗(Generalized Likelihood Ratio Test)的異常路由更新檢測,進而推斷BGP路由錯誤配置情況。該算法的結果不受AS之間的具體連接關系的影響,適合部署在AS間連接關系復雜的BGP網(wǎng)絡中。
　　 在仿真實驗過程中,本文使用美國Oregon大學Route View項目提供的在線BGP路由信息和歐洲IP資源網(wǎng)絡協(xié)調中心RIPE NCC的RIS(Routing Inf

8、ormationService)項目網(wǎng)站上提供的路由信息作為實驗數(shù)據(jù)。采用美國Michigan大學開發(fā)的MRT(Multi-threaded Routing Toolkit)來構造網(wǎng)絡檢測平臺,用MRT所提供的動態(tài)注入BGP路由的功能,構造了腳本驅動的故障注入工具,將實驗設定的路由故障注入到相應的仿真網(wǎng)絡中。采用SSFNet(Scalable Simulation FrameworkNetwork)進行仿真實驗,證實了本文所設計算法的仿