[發明專利]路由振蕩檢測方法及自治系統

有效

• 申請號: 200910086979.8
• 申請日: 2009-06-12
• 公開（公告）號: CN101582847A
• 公開（公告）日: 2009-11-18
• 發明（設計）人: 張軍;張濤;胡字瀅
• 申請（專利權）人: 北京航空航天大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京同立鈞成知識產權代理有限公司
• 代理人: 劉 芳

技術領域

本發明涉及異構網絡路由傳輸領域，尤其涉及一種路由振蕩檢測方法及自治系統(Autonomous?System，簡稱AS)。?

背景技術

隨著Internet規模的迅速膨脹，整個Internet被劃分為不同的AS，由于商業或技術等原因，AS在拓撲結構、網絡性能或網絡策略等方面存在異構特性。各AS內部通過內部網關協議交換路由信息，例如，各AS內部通過選路信息協議(Routing?Information?Protocol，簡稱RIP)、開放式最短路徑優先協議(Open?Shortest?Path?First，簡稱OSPF)等交換路由信息。各AS間通過外部網關協議交換路由信息，邊界網關協議(Border?GatewayProtocol，簡稱BGP)已成為目前Internet事實上的外部網關協議。?

BGP是運行于Internet上用于AS之間相互交換路由信息的路徑向量路由協議。該協議允許AS獨立地定義自己的路由策略，這樣雖然保證了AS局部的合理性，但卻無法保證全局的合理性，可能引起AS間路由策略沖突，從而導致BGP不能收斂，產生路由振蕩(routing?oscillation)。路由振蕩是指多個AS之間不斷反復交換相同的路由信息，而不能建立一個穩定的路由。?

路由振蕩導致數據包在網絡的幾個路由器之間循環傳遞而不能及時到達目的地，還會導致數據包丟失和亂序以及網絡收斂延遲，從而加重網絡負擔，影響網絡性能和服務質量。?

針對BGP路由振蕩問題，現有技術提供了如下的技術方案：?

一類是靜態解決方案，即在沒有發生路由振蕩的情況下，對路由策略進行預先分析，檢測路由策略沖突是否存在，從而可以避免路由振蕩，例如路?由仲裁計劃。這類解決方案存在問題是：一方面是由于商業關系或出于安全保密的考慮，AS不便于公開其內部的路由策略信息和內部拓撲結構信息，或者AS提供的路由策略信息不能及時更新，也就是說路由策略信息的完備性和及時性缺乏；另一方面是，研究表明，即使能夠掌握全部的路由策略信息，分析路由策略沖突也是一個NP完全問題或NP難題(NP完全問題或NP難題是指理論信息學中計算復雜度理論領域里至今沒有解決的問題)，顯然，這類技術方案的可操作程度低。?

另一類是動態解決方案，即在協議中設計額外的路由振蕩檢測機制和評判標準，當發現路由振蕩時再去消除，例如，路由抖動抑制(RFD)算法或者Griffin等人提出的簡單路徑向量協議(Simple?Path?Vector?Protocol，簡稱SPVP)等。這類技術方案存在的問題是：這類方案在路由更新通告中增加了各AS路徑歷史信息，通過附加在路由更新通告中的路徑變化歷史信息，發現路由策略沖突的AS，并抑制相關的路由。這類解決方案存在的問題是需要各AS公開自身的路徑歷史信息，而路徑歷史信息也是各AS不便于公開的。?

綜上所述，現有的解決方案中需要各個AS相互合作，提供相關路由策略或路徑歷史信息，而僅根據單一AS路由信息并不能獨自檢測到路由振蕩，然而由于商業關系或出于安全保密的考慮，各AS的相關路由策略或路徑歷史信息是不便于公開的，因此現有技術的解決方案可操作性低，不利于準確檢測到路由振蕩。?

發明內容

本發明的目的是針對現有技術中存在的問題，提供一種路由振蕩檢測方法及自治系統，不需要各自治系統公開路由策略信息或路徑歷史信息，方法簡單，可操作性高，能夠準確檢測到路由振蕩。?

為實現上述目的，本發明提供了一種路由振蕩檢測方法，包括：?

接收相鄰自治系統發送的路由變化標記和路由更新通告，所述路由變化?標記包括發生路由變化的源自治系統的標識、路由更新信息和路由策略變化信息；?

判斷自身是否發生了被動路由變化事件，所述被動路由變化事件是指由于所述路由更新通告導致自身發生路由變化的事件；?

當自身發生被動路由變化事件時，?

(1)比較當前接收到的路由變化標記的源自治系統的標識是否與自身的標識相同；并且?

(2)比較當前接收到的路由變化標記的路由更新信息與自身的被動路由變化事件中的路由更新信息是否相同；?

如果所述(1)和(2)的比較結果均為相同，則確定發生了路由振蕩；如果所述(1)和(2)的比較結果中有一個為不相同，則確定沒有發生路由振蕩；?

當發生被動路由變化事件后，如果確定沒有發生路由振蕩，則將所接收到的所述路由變化標記隨同自身的路由更新通告一起發送給相鄰自治系統。?

本發明還提供了一種自治系統，包括：?