一種獲取網絡中兩點間最短路由路徑的方法及裝置的製作方法
2023-05-18 15:46:46 4
專利名稱：一種獲取網絡中兩點間最短路由路徑的方法及裝置的製作方法
技術領域：
本發明涉及計算機網絡測量和分析技術，特別涉及一種基於路由更新信息 的獲取網絡中兩點間最短路由路徑的方法及裝置。
背景技術：
在網際網路中， 一個自治系統就是處於一個管理機構控制之下的路由器和
網絡群組。它可以是一個路由器直接連接到一個區域網(LAN)上，同時也連 到網際網路(Internet)上；它可以是一個由企業骨幹網互連的多個區域網。在 一個自治系統中的所有路由器必須相互連接，運行相同的路由協議，同時分配 同一個自治系統編號。
在開放最短路徑優先(Open Shortest Path First, 0SPF)協議的定義中， 可以將一個路由域或者一個自治系統(AS)劃分為幾個區域。在開放式最 短路徑優先(OSPF)協議中，由按照一定的開放最短路徑優先(OSPF)路由法 則組合在一起的一組網絡或路由器的集合稱為區域(AREA)。圖l是分為若 幹區域的開放式最短路徑優先(OSPF)協議自治系統的例子，其中表示出了 一 個自治系統分為3個區域，分別為區域0、區域1和區域2，每個區域中包括 多個路由器3，區域之間相鄰接的位置上的路由器是分別加入不同區域的，這 些路由器是區域邊界路由器4。自治系統邊界路由器是負責與其他自治系統連 接的路由器，其上通常運行邊界網關協議(BGP)。在開放式最短路徑優先(OSPF) 協議中，數據包從發送方路由器到達接收方路由器所經過的中間路由器的集合 就是最短路由路徑。
網際網路(Internet)和服務提供商(ISP)的網絡被劃分為多個自治系統，
自治系統定義了管理控制的區域和作用於自治系統的路由策略，所以路由一般 被分為區域內和區域間兩種。邊界網關協議(BGP)是目前的事實標準，它運 行在自治系統的邊界路由器上以交換網絡可達性信息；在區域內路由中，目前 使用最廣泛的是開放最短路徑優先(OSPF)協議。路由系統是一個網絡的核心，它決定了網絡中各種交通的流向。在網絡管 理和網絡規劃中，如果用戶想要了解自己感興趣的交通流量是否按照預期的網 絡路徑被傳送以驗證沒有出現網絡路由異常或者配置錯誤等，就需要掌握數據 包從發送方到達接收方的實際最短路由路徑。這樣從路由的角度對網絡運行監 測和管理，就如同調試程序時擁有能夠深入到每一行內核級原始碼中去的能 力，有助於迅速輕鬆的定位網絡故障，提供網絡管理人員系統級的網絡透視能 力，並對網絡規划具有現實的指導意義。
然而，現有的路由器無法將數據包從發送方到接收方的實際最短路由路徑 直接提供給用戶即網絡管理者來使用。現有的技術中，如果用戶要獲取最短路 由路徑，那麼用戶必須採取登錄到的各個路由器上或者以基於簡單網絡管理協 議(S麗P)的方式獲取相關各路由器的路由表來間接地獲得最短路由路徑，這 個過程不但非常耗時費力，而且容易出錯。
發明內容
本發明的目的是針對現有技術的上述不足，提供一種獲取網絡中兩點間最 短路由路徑的方法及裝置，能夠在不改變現有網絡路由器的情況下，方便地使 用戶獲得最短路由路徑。
為了上述目的，本發明採取如下技術方案
一種獲取網絡中兩點間最短路由路徑的裝置，包括
路由信息採集探針，該路由信息採集探針部署到至少一個自治系統的至少 一個開放式最短路徑優先協議區域中，用於實時採集每個開放式最短路徑優先 協議區域泛洪的鏈路狀態宣告報文；
存儲器，用於存儲所述路由信息採集探針為每個開放式最短路徑優先協議
區域維護的鏈路狀態信息資料庫；
處理器，用於根據所述鏈路狀態信息資料庫計算用戶輸入的網絡中兩點間
最短路由路徑；
輸出單元，用於輸出所述處理器的計算結果。
優選地，對所述路由信息採集探針進行的配置包括路由信息採集探針與 所處區域的接入路由器建立開放最短路徑優先協議鄰接關係採集本區域的開 放最短路徑優先協議鏈路狀態宣告報文信息，通過隧道的方式與本自治系統的其他區域或者其他自治系統的區域中的接入路由器相連並建立開放最短路徑 優先協議鄰接關係來採集相應區域的開放最短路徑優先協議鏈路狀態宣告報 文信息。
優選地，對所述路由信息採集探針進行的配置還包括通過傳輸控制協議 多跳的方式與需要監測的自治系統的邊界路由器建立邊界網關協議對等關係 來採集邊界網關協議路由更新報文。
一種獲取網絡中兩點間最短路由路徑的方法，用於獲取指定的源節點到目 的節點之間的最短路由路徑，其特徵是，包括如下步驟
步驟Sl，採集路由信息；所述路由信息包括為每個開放最短路徑優先協 議區域維護的鏈路狀態信息資料庫；
步驟S2，利用所述路由信息構造以所述源節點為根節點的最短路由路徑 優先樹，並遍歷所述最短路由路徑優先樹直到找到所述目的節點，以獲得所述 源節點到所述目的節點之間的最短路由路徑。
優選地，所述步驟S1中，所述路由信息還包括每個對等邊界網關協議的 ii界路由器所能到達的前綴信息資料庫；所述鏈路狀態信息資料庫包括在開放 式最短路徑優先協議區域泛洪的鏈路狀態宣告報文。
優選地，所述步驟S1具體包括如下步驟
步驟Sll，在至少一個自治系統的至少一個區域中部署路由信息採集探
針；
步驟S12，對所述路由信息採集探針進行配置；
步驟S13,採集每個開放式最短路徑優先協議區域泛洪的鏈路狀態宣告報文。
優選地，所述步驟S1.2中，對所述路由信息採集探針的配置包括路由
信息採集探針與所處區域的接入路由器建立開放最短路徑優先協議鄰接關係 採集本區域的開放最短路徑優先協議鏈路狀態宣告報文信息，通過隧道的方式 與本自治系統的其他區域或者其他自治系統的區域中的接入路由器相連並建 立開放最短路徑優先協議鄰接關係來採集相應區域的開放最短路徑優先協議 鏈路狀態宣告報文信息。
優選地，所述步驟S2中構造所述最短路由路徑優先樹具體包括如下步驟 步驟S21，以源節點為起點，從所述鏈路狀態信息資料庫中獲取該源節點
8的所有鏈路；
步驟S22，針對每個鏈路計算所有未加入所述最短路徑優先樹的節點到所
述根節點的距離，並選擇出最短路徑的一個節點，作為最短路由路徑優先樹的 下一個節點；
步驟S23，將所述下一個節點作為新的源節點，反覆執行步驟S21至S23， 直到最後一個節點停止。
優選地，步驟S2中，所述最短路由路徑優先樹的節點包括節點類型、 節點標識、節點所對應的鏈路狀態宣告報文、節點到最短路由路徑優先樹根節 點的最短路由路徑的距離值和該節點到所述根節點所經過的路由器有序集合。
優選地，步驟S2中在構造所述最短路由路徑優先樹之前還包括
位置判斷步驟根據源節點和目的節點的節點標識，判斷源節點和目的節 點的位置關係是否符合下列關係之一
第一種關係，源節點與目的節點在相同自治系統中的相同區域；
第二種關係，源節點與目的節點在相同自治系統的不同區域；
第三種關係，源節點與目的節點在不同自治系統；
如果源節點和目的節點符合第一種關係，則執行步驟S2。
優選地，如果源節點和目的節點符合第二種關係，還包括如下步驟
步驟S31，在源節點所在的區域中找出能夠到達目的節點的區域邊界路由
步驟S32,在所述區域邊界路由器集合中找到目的區域邊界路由器，該目 的區域邊界路由器是從源節點到區域邊界路由器集合的最短路由路徑權值為
最小的區域邊界路由器
步驟S33，以源節點、所述目的區域邊界路由器和該目的區域邊界路由器 所附著的子網作為源節點、目的節點和目的網段輸入,執行步驟S2，獲得從
源節點到目的節點最短路由路徑在源節點所在區域中的部分；
步驟S34，將所述目的區域邊界路由器作為新的源節點，重複執行步驟S31
到步驟S34，直到到達目的節點停止。
優選地，所述步驟S32具體包括如下步驟
遍歷所述區域邊界路由器集合中的所有區域邊界路由器，執行步驟S2; 找出從源節點到區域邊界路由器集合的最短路由路徑權值為最小的區域邊界路由器，作為目的區域邊界路由器。
優選地，如果源節點和目的節點符合第三種關係，還包括如下步驟 步驟S41，尋找能夠達到目的節點且路徑最短的自治系統邊界路由器集合.
步驟S42，在所述自治系統邊界路由器集合中找到目的自治系統邊界路由 器，該目的自治系統邊界路由器是從源節點到自治系統邊界路由器集合最短路 由路徑權值為最小的自治系統邊界路由器；
步驟S43，獲得從源節點到目的節點最短路由路徑在源節點所在系統中的 部分；
歩驟S44，將所述目的自治系統邊界路由器作為新的源節點，重複執行步 驟S41到步驟S44，直到到達目的節點停止。
優選地，在所述步驟S41中，通過從維護的邊界網關協議路由信息中尋找 宣告前綴為目的網段的路由信息，來尋找能夠達到目的節點且路徑最短的自治 系統邊界路由器集合。
優選地，所述步驟S42包括如下步驟
步驟S421，以源節點和所述自治系統邊界路由器為輸入，執行歩驟 S31至步驟S34，獲得源節點到所述自治系統邊界路由器的最短路由路徑；
步驟S422，反覆執行步驟S421直到遍歷所有自治系統邊界路由器， 通過比較源節點到各所述自治系統邊界路由器的最短路由路徑，獲得最短路由 路徑最短的自治系統邊界路由器作為目的自治系統邊界路由器。
優選地，所述步驟S43具體包括如下步驟
在源節點所在自治系統中找到所述目的自治系統邊界路由器附著的一個 子網；
以源節點標識、該目的自治系統邊界路由器和該目的自治系統邊界路由器 附著的一個子網分別作為源節點、目的節點和目的網段作為輸入，執行步驟 S31至步驟S34，獲得從源節點到目的節點最短路由路徑在源節點所在自治系 統中的部分。
與現有技術相比，本發明產生了如下技術效果
本發明是基於被動式路由信息採集技術，由採集設備集中式地計算網絡中 任意位置關係的兩路由器間最短路由路徑的方法和裝置，從而本發明在不改變
10現有網絡路由器的情況下，方便地使用戶獲得網絡中兩個節點之間的最短路由 路徑，不僅實現簡單而且節省時間。該發明可用於了解網絡中兩路由器間交通 流量的實際路徑，監測特定路由路徑，路由異常故障定位，保證特定路由路徑 安全等方面。
圖1是現有技術中的自治系統結構示意圖2是本發明一實施例中路由信息採集探針部署示意圖3是本發明的獲取網絡中兩點間最短路由路徑的方法流程圖4是本發明的獲取網絡中兩點間最短路由路徑的方法中步驟Sl的流程
圖5是本發明的獲取網絡中兩點間最短路由路徑的方法中步驟S2的流程
圖6是本發明的獲取網絡中兩點間最短路由路徑的方法中步驟S3的流程
圖7是本發明的獲取網絡中兩點間最短路由路徑的方法中步驟S4的流程圖。
具體實施例方式
下面結合附圖與具體實施方式
對本發明作進一步詳細描述。
本發明提供一種基於被動式路由信息採集來獲取網絡中任意兩節點路由 路徑的方法和裝置，所述節點是指網絡中的路由器和由多個路由器組成的網絡 類型節點。通過本發明的所述裝置來採集網絡路由信息，在採集到網絡路由信 息的情況下，所述裝置為開放式最短路徑優先(0SPF)協議每個區域維護一個 鏈路狀態信息資料庫(LSDB)。用戶選中網絡中的任意位置關係的兩個路由器， 所述裝置通過查詢鏈路狀態信息資料庫(LSDB)中的路由信息，採用本發明的 方法計算出兩點間最短路由路徑。
如圖2所示，作為具體實施例， 一種獲取網絡中兩點間最短路由路徑的裝 置，包括如下部分
路由信息採集探針11，該路由信息採集探針部署到至少一個自治系統的
ii至少一個開放式最短路徑優先(0SPF)協議區域中，實時採集每個開放式最短路徑優先(0SPF)協議區域(Area)泛洪的鏈路狀態宣告(LSA)報文。在網絡測量技術領域，通常把部署在網絡中、通過主動發包或者被動監聽方式獲取網絡中相關報文信息的軟體或者硬體稱為採集探針。路由信息採集探針模擬實現完整的邊界網關協議(BGP)和開放最短路徑優先(0SPF)協議，與真實路由器建立邊界網關協議(BGP)會話並交換邊界網關協議(BGP)路由更新報文，建立開放最短路徑優先(0SPF)協議鄰接關係並交互開放最短路徑優先(0SPF)協議鏈路狀態宣告(LSA)報文來採集路由信息。路由信息採集探針是本領域技術人員熟知的技術，例如軟體的路由信息採集探針可以通過現有的開源路由軟體GNU Zebra實現。
較佳地，如圖2所示，對所述路由信息採集探針的配置包括:路由信息採集探針11與所處區域的接入路由器建立開放最短路徑優先(0SPF)協議鄰接關係12採集本區域的開放最短路徑優先(0SPF)協議鏈路狀態宣告(LSA)報文信息，通過隧道的方式，例如通用路由封裝(GRE)，與本自治系統的其他區域或者其他自治系統的區域中的接入路由器相連並建立開放最短路徑優先(0SPF)協議鄰接關係12來採集相應區域的開放最短路徑優先(0SPF)協議鏈路狀態宣告(LSA)報文信息；通過傳輸控制協議(TCP)多跳的方式與需要監測的自治系統的邊界路由器建立邊界網關協議(BGP)對等關係13來採集邊界網關協議(BGP)路由更新報文。
存儲器(圖中未示出)，所述路由信息採集探針為每個開放式最短路徑優先(0SPF)協議區域(Area)維護一個鏈路狀態信息資料庫(LSDB)並存儲到存儲
器中；
處理器(圖中未示出)，用於根據用戶的輸入計算網絡中兩點間最短路由路徑；
輸出單元(圖中未示出)，用於輸出所述處理器的計算結果。與上述獲取網絡中兩點間最短路由路徑的裝置相對應地，作為具體實施例，本發明提供一種基於被動式路由信息採集的，獲取網絡中兩點間最短路由路徑的方法，在上面為每個開放式最短路徑優先(0SPF)協議區域(Area)維護--個鏈路狀態信息資料庫(LSDB)的基礎上，以用戶提供的源節點、目的節點和目的網段為輸入，給出從源節點到目的節點所經過的由中間路由器有序集合所組成的最短路由路徑。對輸入參數解釋如下源節點(SourceNode)為用戶決定作為最短路由路徑計算的起始路由器，編號為SourceNodeID;目的節點(TargetNode)為用戶決定作為最短路由路徑計算的終點路由器，編號為TargetNodeID;以及該終點路由器所附著的一個目的網段(TargetPref ix)(注因一個路由器通常會有多個網段附著，所以需要用戶確定具體是哪個目的網段)。本方法中，由源節點標識和目的節點標識，易得其所在的自治系統號，源節電所在自治系統為SourceAS，自治系統號為SourceASID;目的節點所在自治系統為TargetAS，自治系統號為TargetASID。下面對該方法進行詳細描述。
一種獲取網絡中兩點間最短路由路徑的方法，用於獲取指定的源節點到目的節點之間的最短路由路徑，如圖3所示，包括如下步驟
步驟Sl，採集路由信息的步驟；所述路由信息包括為每個開放最短路徑優先協議區域維護的鏈路狀態信息資料庫；
較佳地，所述路由信息還包括所監測的每個對等邊界網關協議(BGP)的邊界路由器所能到達的前綴信息資料庫；所述鏈路狀態信息資料庫包括在開放式最短路徑優先(0SPF)協議區域(Area)泛洪的鏈路狀態宣告(LSA)報文。
較佳地，如圖4所示，所述步驟S1具體包括如下步驟
步驟Sl.l，在至少一個自治系統的至少一個區域中部署路由信息採集探
針；
步驟Sl. 2，對所述路由信息採集探針進行配置；
較佳地，對所述路由信息採集探針的配置包括路由信息採集探針與所處區域的接入路由器建立開放最短路徑優先(0SPF)協議鄰接關係採集本區域的開放最短路徑優先(0SPF)協議鏈路狀態宣告(LSA)報文信息，通過隧道的方式，例如通用路由封裝(GRE)，與本自治系統的其他區域或者其他自治系統的區域中的接入路由器相連並建立開放最短路徑優先(0SPF)協議鄰接關係來採集相應區域的開放最短路徑優先(0SPF)協議鏈路狀態宣告(LSA)報文信息；通過傳輸控制協議(TCP)多跳的方式與需要監測的自治系統的邊界路由器建立邊界網關協議(BGP)對等關係來採集邊界網關協議(BGP)路由更新報文。
步驟SL3，採集每個開放式最短路徑優先(0SPF)協議區域(Area)泛洪
13的鏈路狀態宣告(LSA)報文。
步驟S2，利用所述路由信息構造以所述源節點為根節點的最短路由路徑優先樹，並遍歷所述最短路由路徑優先樹直到找到所述目的節點，以獲得所述源節點到所述目的節點之間的最短路由路徑；
較佳地，如圖5所示，所述步驟S2中構造所述最短路由路徑優先樹具體
包括如下步驟
步驟S21，以源節點為起點，從所述鏈路狀態信息資料庫中獲取該源節點的所有鏈路。
步驟S22，針對每個鏈路計算所有未加入所述最短路徑優先數的節點到所述根節點的距離，並選擇出最短路徑的一個節點，作為最短路由路徑優先樹的下一個節點；
步驟S23，將所述下一個節點作為新的源節點，反覆執行步驟S21-S23，直到最後一個節點停止。
作為-一種可實施的方式，下面以源節點和目的節點在同一個開放式最短路徑優先(0SPF)協議區域(Area)中為例來詳細介紹構造最短路由路徑優先樹(SPF tree)的步驟。本發明的步驟S20對現有技術的開放最短路徑優先路由(0SPF)協議中最短路由路徑優先樹(SPF tree)的構造進行了改進，改進內容包括相應數據結構的裁減、路由表操作的刪除、最短路由路徑優先樹(SPF tree)第二階段構造方法的裁減以及下一跳計算過程(Nexth叩Caculation)的刪除。具體描述為
首先，單開放式最短路徑優先(0SPF)協議區域(Area)中最短路由路徑優先樹(SPF tree)的構造方法定義其所構造的最短路由路徑優先樹由一系列節點構成，為了描述方便將該節點稱作Vertex節點，其中每個Vertex節點包含五個屬性
(a) VertexType: Vertex節點類型。最短路由路徑優先樹(SPF tree)中有兩種類型的Vertex節點路由器類型(RouterType)和網絡類型(NetworkType)。其中一個路由器類型的節點代表網絡中的一個路由器， 一個網絡類型的節點代表網絡中的一個廣播或者非廣播多路訪問網絡。
(b) VertexID: Vertex節點標識。最短路由路徑優先樹(SPF tree)中每個Vertex節點都有一個32位無符號整數作為節點標識。對於路由器類型的Vertex節點，使節點標識(VertexID)為該節點所代表的路由器的路由器標識(RouterID);對於網絡類型的Vertex節點，使節點標識(VertexID)為該節點所代表的廣播或者非廣播多路訪問網絡上指定路由器(DesignatedRouter)的IP位址；所述指定路由器是指在網絡類型的節點的多個路由器中，通過協議規範選舉出來的。
(c) VertexLSA: Vertex節點所對應的鏈路狀態宣告報文。最短路由路徑優先樹(SPF tree)中每個Vertex節點在鏈路狀態信息資料庫(LSDB)中都有一條鏈路狀態宣告(LSA)與之對應。每個鏈路狀態宣告(LSA)條目頭部信息包括鏈路狀態類型,宣告路由器的地址,鏈路耗費和序列號(版本號)等。對於路由器類型的Vertex節點，鏈路狀態宣告報文(VertexLSA)就是該節點所代表的路由器所發出的路由器鏈路狀態宣告報文(RouterLSA);對於網絡類型的Vertex節點，鏈路狀態宣告報文(VertexLSA)是該節點所代表的廣播或者非廣播多路訪問網絡上指定路由器(Designated Router)所發出的網絡鏈路狀態宣告報文(NetworkLSA)。
(d) Distance: Vertex節點到最短路由路徑優先樹(SPF tree)根的最短路由路徑的距離值。該距離值由該最短路由路徑上的每條邊的權值加和而得到，其中每條邊上的權值是在路由器鏈路狀態宣告報文(RouterLSA)和網絡鏈路狀態宣告報文(NetworkLSA)中包含的。這裡規定最短路由路徑優先樹(SPFtree)中，網絡類型Vertex節點到其所代表的廣播或者非廣播多路訪問網絡上的任何一個路由器類型Vertex節點的距離值為0。
(e) Path:源節點到Vertex節點的所經過的路由器有序集合。該集合是在構造最短路由路徑優先樹的過程中動態建立的，記錄從源節點到目的節點的
每一跳伯息。
本發明對現有技術的最短路由路徑優先樹(SPF tree)構造的好處在於路
由表操作和計算下一跳操作的刪除是因為本發明是給出兩點間的最短路由路徑而不是像路由器那樣來生成轉發表的；對於最短路由路徑優先樹第二階段構造方法的裁剪是因為這個第二階段主要是簡單處理當源節點和目的節點是在同一個自治系統但是不同區域的，而本發明處理這種情況的時候是採用迭代單區域的情形，來提高算法的速度和準確度等。
根據上述對最短路由路徑優先樹的節點的屬性的定義，作為一種可實施的方式，步驟S2具體包括如下步驟；
步驟S21，以源節點為起點，從所述鏈路狀態信息資料庫中獲取該源節 點的所有鏈路。
在將用戶指定的源節點為起點時，需要先初始化最短路由路徑優先樹
(SPF tree)的構造方法的數據結構，具體包括
步驟S211將最短路由路徑優先樹(SPF tree)和參選集合 (Candidate)置為空，其中最短路由路徑優先樹(SPF tree)與參選集合 (Candidate)中的元素均為Vertex節點。
步驟S212將選定的源節點所對應的Vertex節點放入參選集合 (Candidate)中，其中源節點所對應的Vertex節點的節點類型(VertexType) 為路由器類型(RouterType);節點標識(VertexID)為該源節點的路由器標 識(Router ID);節點的鏈路狀態宣告報文(VertexLSA)為該源節點路由器 所發出的路由器鏈路狀態宣告(RouterLSA)，可以通過查找為每個開放式最短 路徑優先(OSPF)協議區域(Area)維護的鏈路狀態信息資料庫(LSDB)獲得；節 點的距離屬性(Distance)為0。
在步驟S21中，當上述源節點是新加入最短路由路徑優先樹(SPF tree)中的、作為循環執行的新的源節點時，不需要再執行上述初始化步驟 S211和S212，這是本領域人員知道的。
步驟S22，針對每個鏈路計算所有未加入所述最短路徑優先數的節點到 所述根節點的距離，並選擇出最短路徑的一個節點，作為最短路由路徑優先樹 的下一個節點，即每次從參選集合(Candidate)中取出距離(Distance)最 小的Vertex節點，放入最短路由路徑優先樹(SPF tree)中。具體包括如下 歩驟
設此剛加入最短路由路徑優先樹(SPF tree)的節點為節點V (Vertex V)， 根據所判斷節點V的不同類型分別執行步驟S221和步驟S222:
步驟S221，如果節點V為路由器類型(RouterType),執行如下步驟 步驟S (221a),取節點V中的鏈路狀態宣告報文(VertexLSA)中 的下一條鏈路(Link)，如果遍歷完畢則返回步驟S22;
步驟S (221b)，如果該鏈路(Link)類型為1，由此鏈路(Link)的 鏈路標識(linkid)在該開放式最短路徑優先(OSPF)協議區域(Area)的鏈路
16狀態信息資料庫(LSDB)中查找對應的路由器鏈路狀態宣告報文(RouterLSA)， 為了描述的方便而設找到的該鏈路狀態宣告報文(LSA)為findLSA，轉步驟S
(221e);需要說明的是，關於鏈路類型是本領域技術人員熟知的，其中類型為 l表示點對點(point to point)的開放式最短路徑優先(0SPF)協議網絡類 型，類型為2表示臨時網絡(transient network)的開放式最短路徑優先
(OSPF)協議網絡類型，比如廣播網或者非廣播多路訪問網絡，類型為3表 示stub的運行開放最短路徑優先(OSPF)協議的網絡類型，即末梢網絡，類 型為4表示虛鏈路。
步驟S(221c)，如果該鏈路(Link)類型為2，由此鏈路(Link) 的鏈路標識(linkid)在該開放式最短路徑優先(OSPF)協議區域(Area)的鏈 路狀態信息資料庫(LSDB)中査找對應的網絡鏈路狀態宣告報文(NetworkLSA)， 為了描述的方便而設找到的該鏈路狀態宣告報文(LSA)為findLSA，轉步驟S
(221e);
步驟S (d)，如果該鏈路(Link)類型為3和4,轉步驟S (221a);
步驟S(e)，如果findLSA為空，或者findLSA的年齡(Age)為最 大年齡(MaxAge)，即findLSA的時間己經超過鏈路狀態宣告報文(LSA)中規 定的有效期，或者findLSA中沒有指回節點V的鏈路(Link)，轉步驟S(221a);
步驟S (f)， 由findLSA生成相應的Vertex節點，其中距離 (Distance)置為0。為了描述方便設該Vertex節點為節點W (Vertex W)。
步驟S (g)，如果節點W (Vertex W)已經存在於最短路由路徑優 先樹(SPF tree)中，轉步驟S (221a)
步驟S (h)， 計算節點W (Vertex W)的距離(Distance)。該距 離(Distance)等於節點V的距離(Distance)加上findLSA中所宣告的權值 (metric)。
步驟S (i)， 如果參選集合(Candiadate)中還尚未包含節點W (Vertex W)或者該節點W的距離(Distance)值小於參選集合(Candidate) 中節點W的距離(Distance)值，則更新參選集合(Candidate)，轉步驟S(221a): 否則不作任何處理轉步驟S (221a);所述更新包括將參選集合中尚未包含的 節點放入參選集合和/或對參選集合中的所有節點的路由器有序集合(Path) 屬性進行更新。
17步驟S222，如果節點V為網絡類型(NetworkType)，執行如下步驟: 步驟S (222a)，取節點V中的鏈路狀態宣告報文(VertexLSA) 中的下一個附著路由器(AttachedRouter)，如果遍歷完畢則返回步驟S22;
步驟S (222b)，由此附著路由器(AttachedRouter)在該開放式 最短路徑優先(0SPF)協議區域(Area)的鏈路狀態信息資料庫(LSDB)中查找對 應的路由器鏈路狀態宣告報文(RouterLSA)，為了描述的方便而設找到的該鏈 路狀態宣告報文(LSA)為findLSA;
步驟S (222c)，如果findLSA為空，或者findLSA的年齡(Age) 為最大年齡(MaxAge)，即findLSA的時間已經超過鏈路狀態宣告報文(LSA) 中規定的有效期，或者findLSA中沒有指回節點V的鏈路(Link)，轉步驟S (222a)
步驟S (222d)， 由findLSA生成路由器類型(RouterType)的 Vertex節點，其中距離(Distance)置為0，為了描述方便設該Vertex節點 為節點W (Vertex W)。
步驟S (222e)，如果節點W (Vertex W)已經存在於最短路由 路徑優先樹(SPF tree)中，轉步驟S (222a);
步驟S (222f)，計算節點W (Vertex W)的距離(Distance); 該距離(Distance)即等於節點V (Vertex V)的距離(Distance);
步驟S (222g)，如果參選集合(Candiadate)中還尚未包含節 點W(VertexW)或者該節點W的距離(Distance)值小於參選集合(Candidate) 中節點W (Vertex W)的距離(Distance)值，則更新參選集合(Candidate), 轉步驟S (222a);否則不作任何處理轉步驟S (222a);所述更新包括將參選集 合中尚未包含的節點放入參選集合和/或對參選集合中的所有節點的路由器有 序集合(Path)屬性進行更新。
步驟S23，將所述下一個節點作為新的源節點，反覆執行步驟 S21-S23，直到找到目的節點停止，獲得由源節點(SourceNode)作為起點， 目的節點(TargetNode)作為終點的一個有序路由器集合(RouterSet)，該集 合為從源節點到目的節點的最短路由路徑。
較佳地，本發明的獲取網絡中兩點間最短路由路徑的方法，其中步驟S2 中在構造所述最短路由路徑優先樹之前還包括
18位置判斷步驟根據源節點和目的節點的節點標識，判斷源節點和目的節 點的位置關係是否符合下列關係之一
(1) 源節點與目的節點在相同自治系統中的相同區域；如果源節點和目的 節點符合第一種關係，則執行步驟S2;
(2) 源節點與目的節點在相同自治系統的不同區域；
(3) 源節點與目的節點在不同自治系統。
較佳地，本發明的獲取網絡中兩點間最短路由路徑的方法，對於源節點和
目的節點在同一個自治系統(AS)的不同開放式最短路徑優先(0SPF)協議區域 (Area)中的最短路由路徑計算，如圖6所示，還包括
步驟S31，如果源節點和目的節點屬於同一個自治系統(AS)的不同開放式 最短路徑優先(0SPF)協議區域(Area)中，則在源節點所在的區域中找出能夠 到達目的節點的區域邊界路由器集合。具體來說，獲得源節點(SourceNode) 和目的節點(TargetNode)所在的區域號，其區域號分別是源節點區域號 (SourceAreaID)，和目的節點區域號(TargetAreaID)，若判斷源節點區域號 與目的節點區域號相等(SourceAreaID=TargetAreaID)為是，則轉向步驟S2; 若判斷源節點區域號與目的節點區域號相等(SourceAreaID二TargetAreaID) 為否，則搜索源節點所在自治系統(SourceAS)鏈路狀態信息資料庫(LSDB) 中的全部鏈路狀態宣告報文(SummaryLSA)，從中找到宣告前綴為目的網段 (TargetPrefix)的區域邊界路由器(ABR)集合(ABRSet)。
步驟S32，在所述區域邊界路由器集合中找到目的區域邊界路由器，該目 的區域邊界路由器是從源節點到區域邊界路由器集合的最短路由路徑權值為 最小的區域邊界路由器。具體包括如下步驟
步驟S321，設從源節點(SourceNode)到該區域邊界路由器集合 (ABRSet)中最短路由路徑權值為最小的區域邊界路由器為目的邊界路由器 (TargetABR)，為了描述方便將最短路由路徑權值稱為minCost，目的邊界路 由器(TargetABR)附著的子網為ABRPrefix，初始化其最短路由路徑權值 (minCost)為無窮大；
步驟S322，取區域邊界路由器集合(ABRSet)中的下一個區域邊界 路由器(eachABR)，如遍歷完畢，則執行步驟S32;
步驟S323,以源節點標識(SourceNodeID)的源節點，和該區域邊
19界路由器(eachABR)為目的節點作為輸入，執行步驟S2，計算源節點和該區 域邊界路由器之間最短路由路徑權值，稱該權值為cost,若權值cost小於 minCost，則更新目的邊界路由器(TargetABR)為該區域邊界路由器(eachABR)， 更新minCost為權值cost，轉向步驟S322;
步驟S33，獲得從源節點到目的節點最短路由路徑在源節點所在區域中的 部分。具體來說，以源節點(SourceNode)、目的區域邊界路由器(TargetABR) 和該目的區域邊界路由器所附著的子網(TargetPrefix)作為源節點、目的節 點和目的網段輸入，執行步驟S2，獲得從源節點(SourceNode)到目的節點 (TargetNode)最短路由路徑在源節點所在區域(SourceArea)中的部分；
步驟S34，將所述目的區域邊界路由器作為新的源節點，重複執行步驟S31 到步驟S34，直到到達目的節點停止，獲得由源節點(SourceNode)作為起點， 目的節點(TargetNode)作為終點的一個有序路由器集合(RouterSet)。該集 合為從源節點到目的節點的跨區域的最短路由路徑。
較佳地，本發明的獲取網絡中兩點間最短路由路徑的方法，對於源節點和 目的節點在不同自治系統(AS)中的最短路由路徑計算，如圖7所示，還包括
步驟S41，如果源節點和目的節點在不同自治系統，則尋找能夠達到目的 節點且路徑最短的自治系統邊界路由器集合。具體來說，若判斷源節點所在自 治系統號(SourceASID)與目的節點所在自治系統號(TargetASID)相等，轉 向歩驟S31至步驟S34;否則從維護的邊界網關協議(BGP)路由信息中尋找 宣告前綴為目的網段(TargetPrefix)的路由信息，通過該路由信息可獲得從 源節點所在自治系統(SourceAS)中可達目的網段的自治系統邊界路由器集合；
步驟S42，在所述自治系統邊界路由器集合中找到目的自治系統邊界路由 器，該目的自治系統邊界路由器是從源節點到自治系統邊界路由器集合最短路 由路徑權值為最小的自治系統邊界路由器。具體來說，包括如下步驟
步驟S421，以源節點和所述自治系統邊界路由器為輸入，執行步驟 S31至步驟S34，獲得源節點到所述自治系統邊界路由器的最短路由路徑；
步驟S422，反覆執行步驟S421直到遍歷所有自治系統邊界路由器， 通過比較源節點到各所述自治系統邊界路由器的最短路由路徑，獲得最短路由 路徑最短的自治系統邊界路由器作為目的自治系統邊界路由器(TargetASBR)。 步驟S43，獲得從源節點到目的節點最短路由路徑在源節點所在系統中的部分。具體來說，在源節點所在自治系統(SourceAS)中找到所述目的自治 系統邊界路由器(TargetASBR)附著的一個子網(TargetASBRPrefix)，以源 節點標識(SourceNodeID)、該目的自治系統邊界路由器(TargetASBR)和該 目的自治系統邊界路由器(TargetASBR)附著的一個子網(TargetASBRPrefix) 分別作為源節點、目的節點和目的網段作為輸入，執行步驟S31至34，獲得 從源節點(SourceNode)到目的節點最短路由路徑在源節點所在自治系統中的 部分。
步驟S44，將所述目的自治系統邊界路由器作為新的源節點，重複執行 步驟S41到步驟S44，直到到達目的節點停止，獲得由源節點(SourceNode) 作為起點，目的節點(TargetNode)作為終點的 一個有序路由器集合 (RouterSet)。該集合為從源節點到目的節點的跨過至少一個自治系統的最短 路由路徑。
本發明所產生的有益技術效果是本發明基於被動式路由信息採集，由採
集設備集中式地計算網絡中任意位置關係的兩路由器間最短路由路徑，從而在
不改變現有網絡路由器的情況下，方便地使用戶獲得網絡中兩個節點之間的最
短路由路徑，不僅實現簡單而且節省時間。
本發明可用於了解網絡中兩路由器間交通流量的實際路徑，監測特定路由
路徑，路由異常故障定位，保證特定路由路徑安全等方面。如果用戶想要了解
自己感興趣的交通流量是否按照預期的網絡路徑被傳送以驗證沒有出現網絡
路由異常或者配置錯誤等，就可以採用本發朋的技術方案獲得從數據包發送方
到接收方的實際最短路由路徑。這樣從路由的角度對網絡運行監測和管理，就
如同調試程序時擁有能夠深入到每一行內核級原始碼中去的能力，有助於迅速
輕鬆的定位網絡故障，提供網絡管理人員系統級的網絡透視能力，並對網絡規 划具有現實的指導意義。
以上所述內容，僅為本發明具體的實施方式，但本發明的保護範圍並不局 限於此，任何熟悉本技術領域的技術人員在本發明揭露的技術範圍內，可輕易 想到的變化或替換，都應涵蓋在本發明的保護範圍內。
權利要求
1、一種獲取網絡中兩點間最短路由路徑的裝置，其特徵是，包括路由信息採集探針，該路由信息採集探針部署到至少一個自治系統的至少一個開放式最短路徑優先協議區域中，用於實時採集每個開放式最短路徑優先協議區域泛洪的鏈路狀態宣告報文；存儲器，用於存儲所述路由信息採集探針為每個開放式最短路徑優先協議區域維護的鏈路狀態信息資料庫；處理器，用於根據所述鏈路狀態信息資料庫計算用戶輸入的網絡中兩點間最短路由路徑；輸出單元，用於輸出所述處理器的計算結果。
2、 根據權利要求1所述的獲取網絡中兩點伺最短路由路徑的裝置，其特 徵是，對所述路由信息採集探針進行的配置包括:路由信息採集探針與所處區 域的接入路由器建立開放最短路徑優先協議鄰接關係採集本區域的開放最短 路徑優先協議鏈路狀態宣告報文信息，通過隧道的方式與本自治系統的其他區 域或者其他自治系統的區域中的接入路由器相連並建立開放最短路徑優先協 議鄰接關係來採集相應區域的開放最短路徑優先協議鏈路狀態宣告報文信息。
3、 根據權利要求2所述的獲取網絡中兩點間最短路由路徑的裝置，其特徵是，對所述路由信息採集探針進行的配置還包括通過傳輸控制協議多跳的 方式與需要監測的自治系統的邊界路由器建立邊界網關協議對等關係來採集 邊界網關協議路由更新報文。
4、 一種獲取網絡中兩點間最短路由路徑的方法，用於獲取指定的源節點 到目的節點之間的最短路由路徑，其特徵是，包括如下步驟步驟Sl,採集路由信息；所述路由信息包括為每個開放最短路徑優先協 議區域維護的鏈路狀態信息資料庫；步驟S2，利用所述路由信息構造以所述源節點為根節點的最短路由路徑 優先樹，並遍歷所述最短路由路徑優先樹直到找到所述目的節點，以獲得所述 源節點到所述目的節點之間的最短路由路徑。
5、 根據權利要求4所述的獲取網絡中兩點間最短路由路徑的方法，其特 徵是，所述步驟S1中，所述路由信息還包括每個對等邊界網關協議的邊界路由器所能到達的前綴信息資料庫；所述鏈路狀態信息資料庫包括在開放式最短 路徑優先協議區域泛洪的鏈路狀態宣告報文。
6、 根據權利要求4或5所述的獲取網絡中兩點間最短路由路徑的方法， 其特徵是，所述步驟S1具體包括如下步驟步驟Sll，在至少一個自治系統的至少一個區域中部署路由信息採集探針；步驟S12，對所述路由信息採集探針進行配置；步驟S13，採集每個開放式最短路徑優先協議區域泛洪的鏈路狀態宣告報文。
7、 根據權利要求6所述的獲取網絡中兩點間最短路由路徑的方法，其特 徵是，所述步驟S12中，對所述路由信息採集探針的配置包括路由信息採集 探針與所處區域的接入路由器建立開放最短路徑優先協議鄰接關係採集本區 域的開放最短路徑優先協議鏈路狀態宣告報文信息，通過隧道的方式與本自治 系統的其他區域或者其他自治系統的區域中的接入路由器相連並建立開放最 短路徑優先協議鄰接關係來採集相應區域的開放最短路徑優先協議鏈路狀態 宣告報文信息。
8、 根據權利要求4所述的獲取網絡中兩點間最短路由路徑的方法，其特 徵是，所述步驟S2中構造所述最短路由路徑優先樹具體包括如下步驟步驟S21，以源節點為起點，從所述鏈路狀態信息資料庫中獲取該源節點 的所有鏈路；步驟S22，針對每個鏈路計算所有未加入所述最短路徑優先樹的節點到所 述根節點的距離，並選擇出最短路徑的一個節點，作為最短路由路徑優先樹的 下一個節點；步驟S23，將所述下一個節點作為新的源節點，反覆執行步驟S21至S23，直到最後一個節點停止。
9、 根據權利要求4所述的獲取網絡中兩點間最短路由路徑的方法，其特 徵是，步驟S2中，所述最短路由路徑優先樹的節點包括節點類型、節點標 識、節點所對應的鏈路狀態宣告報文、節點到最短路由路徑優先樹根節點的最 短路由路徑的距離值和該節點到所述根節點所經過的路由器有序集合。
10、 根據權利要求4或9所述的獲取網絡中兩點間最短路由路徑的方法，其特徵是，步驟S2中在構造所述最短路由路徑優先樹之前還包括位置判斷步驟根據源節點和目的節點的節點標識，判斷源節點和目的節點的位置關係是否符合下列關係之一第一種關係，源節點與目的節點在相同自治系統中的相同區域； 第二種關係，源節點與目的節點在相同自治系統的不同區域； 第三種關係，源節點與目的節點在不詞自治系統； 如果源節點和目的節點符合第一種關係，則執行步驟S2。
11、 根據權利要求IO所述的獲取網絡中兩點間最短路由路徑的方法，其 特徵是，如果源節點和目的節點符合第二種關係，還包括如下步驟-步驟S31，在源節點所在的區域中找出能夠到達目的節點的區域邊界路由 器集合；步驟S32，在所述區域邊界路由器集合中找到目的區域邊界路由器，該目 的區域邊界路由器是從源節點到區域邊界路由器集合的最短路由路徑權值為 最小的區域邊界路由器步驟S33，以源節點、所述百的區域邊界路由器和該目的區域邊界路由器 所附著的子網作為源節點、目的節點和目的網段輸入，執行步驟S2，獲得從 源節點到目的節點最短路由路徑在源節點所在區域中的部分；步驟S34，將所述目的區域邊界路由器作為新的源節點，重複執行步驟S31 到步驟S34，直到到達目的節點停止。
12、 根據權利要求11所述的獲取網絡中兩點間最短路由路徑的方法，其 特徵是，所述步驟S32具體包括如下步驟遍歷所述區域邊界路由器集合中的所有區域邊界路由器，執行步驟S2; 找出從源節點到區域邊界路由器集合的最短路由路徑權值為最小的區域 邊界路由器，作為目的區域邊界路由器。
13、 根據權利要求IO所述的獲取網絡中兩點間最短路由路徑的方法，其 特徵是，如果源節點和目的節點符合第三種關係，還包括如下步驟步驟S41，尋找能夠達到目的節點且路徑最短的自治系統邊界路由器集合.步驟S42，在所述自治系統邊界路由器集合中找到目的自治系統邊界路由 器，該目的自治系統邊界路由器是從源節點到自治系統邊界路由器集合最短路由路徑權值為最小的自治系統邊界路由器；步驟S43，獲得從源節點到目的節點最短路由路徑在源節點所在系統中的 部分；步驟S44，將所述目的自治系統邊界路由器作為新的源節點，重複執行步 驟S41到步驟S44，直到到達目的節點停止。
14、 根據權利要求13所述的獲取網絡中兩點間最短路由路徑的方法，其 特徵是，在所述步驟S41中，通過從維護的邊界網關協議路由信息中尋找宣告 前綴為目的網段的路由信息，來尋找能夠達到目的節點且路徑最短的自治系統 邊界路由器集合。
15、 根據權利要求13所述的獲取網絡中兩點間最短路由路徑的方法，其 特徵是，所述步驟S42包括如下步驟:.步驟S421，以源節點和所述自治系統邊界路由器為輸入，執行步驟 S31至步驟S34，獲得源節點到所述自治系統邊界路由器的最短路由路徑;步驟S422，反覆執行步驟S421直到遍歷所有自治系統邊界路由器， 通過比較源節點到各所述自治系統邊界路由器的最短路由路徑，獲得最短路由 路徑最短的自治系統邊界路由器作為目的自治系統邊界路由器。
16、 根據權利要求13所述的獲取網絡中兩點間最短路由路徑的方法，其 特徵是，所述步驟S43具體包括如下步驟在源節點所在自治系統中找到所述目的自治系統邊界路由器附著的一個 子網；以源節點標識、該目的自治系統邊界路由器和該目的自治系統邊界路由器附著 的一個子網分別作為源節點、目的節點和目的網段作為輸入，執行步驟S31 至步驟S34，獲得從源節點到目的節點最短路由路徑在源節點所在自治系統中 的部分。
全文摘要
本發明公開了一種獲取網絡中兩點間最短路由路徑的方法及裝置。所述裝置包括路由信息採集探針，用於實時採集每個開放式最短路徑優先協議區域泛洪的鏈路狀態宣告報文；存儲器，用於存儲所述路由信息採集探針為每個開放式最短路徑優先協議區域維護的鏈路狀態信息資料庫；處理器，用於根據所述鏈路狀態信息資料庫計算用戶輸入的網絡中兩點間最短路由路徑；輸出單元，用於輸出所述處理器的計算結果。所述方法包括採集路由信息的步驟；構造最短路由路徑優先樹的步驟。本發明的優點在於方便地使用戶獲得網絡中兩個節點之間的最短路由路徑，不僅實現簡單而且節省時間。本發明可用於監測特定路由路徑、路由異常故障定位、保證特定路由路徑安全等方面。
文檔編號H04L12/56GK101465793SQ20071017980
公開日2009年6月24日 申請日期2007年12月18日 優先權日2007年12月18日
發明者偉 梁, 畢經平, 旭 許, 沫 陳 申請人:中國科學院計算技術研究所