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

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

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

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

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

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

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

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

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