[發明專利]BGP引導的實時自治系統級拓撲發現方法

有效

• 申請號: 200910044746.1
• 申請日: 2009-11-12
• 公開（公告）號: CN101714942A
• 公開（公告）日: 2010-05-26
• 發明（設計）人: 彭偉;盧澤新;張曉哲;王宏;胡曉峰;趙鋒;胡寧
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 國防科技大學專利服務中心 43202
• 代理人: 郭敏

1.一種域間路由協議BGP引導的實時自治系統AS級拓撲發現方法，其特征在于包括 以下步驟：

第一步，建立BGP引導的實時AS拓撲發現系統，該系統由BGP路由器-簡稱為路 由器、AS拓撲發現服務器-簡稱為服務器和AS拓撲發現探測器-簡稱為探測器組成； 所述AS是指自治系統；

BGP路由器是指運行域間路由協議BGP的路由器，位于AS的邊緣，與互聯網中其 他AS的路由器連接；

AS拓撲發現服務器是指進行AS拓撲發現的計算機，部署在BGP路由器所在自治系 統內，其上裝有AS拓撲發現服務程序，它從BGP路由器獲得BGP的路由信息，從AS 拓撲發現探測器獲得IP轉發路徑信息；AS拓撲發現服務器上設置有記錄所有AS拓撲 發現探測器的IP地址的數據結構-探測器IP地址列表；

AS拓撲發現探測器是分布在互聯網中的聯網計算機，其上運行探測器程序，每個探 測器程序有一個運行參數配置文件，其中包含AS拓撲發現服務器的域名或IP地址；運 行參數配置文件由用戶在建立BGP引導的實時AS拓撲發現系統創建；探測器程序內嵌 于點到點P2P即Peer-to-Peer系統的peer節點程序中；

AS拓撲發現服務器與BGP路由器通過局域網或Internet連通，AS拓撲發現服務器 通過Internet與AS拓撲發現探測器連通，AS拓撲發現服務器與BGP路由器之間的通信 基于傳輸控制協議TCP，AS拓撲發現服務器與AS拓撲發現探測器之間的通信基于用戶 數據報協議UDP；

第二步，分別啟動AS拓撲發現服務器程序和AS拓撲發現探測器程序，每個AS拓 撲發現探測器上的AS拓撲發現探測器程序啟動后，均向AS拓撲發現服務器注冊，注冊 過程為：

(2.1)AS拓撲發現探測器從運行參數配置文件獲得AS拓撲發現服務器的域名或IP 地址，用此域名或IP地址向AS拓撲發現服務器發送注冊請求消息，注冊請求消息包含 AS拓撲發現探測器的IP地址；在AS拓撲發現探測器中設置第一定時器，在發送了注冊 請求消息后，啟動第一定時器，第一定時器的超時時間為T1；

(2.2)AS拓撲發現服務器收到AS拓撲發現探測器送來的注冊請求消息后，將該 AS拓撲發現探測器的IP地址保存到探測器IP地址列表中，并向AS拓撲發現探測器發 送一個注冊確認消息；

(2.3)若AS拓撲發現探測器的第一定時器超時，即從發送注冊請求消息起，AS拓 撲發現探測器在等待時間T1內沒有收到注冊確認消息，則轉(2.1)步；若AS拓撲發現 探測器收到了從AS拓撲發現服務器發送來的注冊確認消息，則AS拓撲發現探測器開始 等待接收AS拓撲發現服務器發送來的探測請求消息，注冊過程結束；

第三步，AS拓撲發現服務器周期地進行AS拓撲發現，方法是：

在AS拓撲發現服務器中設置第二定時器，第二定時器以更新周期T2定時觸發進行 新一輪的AS拓撲發現，當第二定時器超時觸發時，執行第四步至第六步進行新一輪的 拓撲發現；

第四步，AS拓撲發現服務器建立到BGP路由器的會話，從BGP路由器得到BGP路 由信息：如果有多臺BGP路由器，則AS拓撲發現服務器分別與多臺BGP路由器建立連 接，并從這些BGP路由器接收BGP路由信息；BGP路由協議通過路由更新消息將本路 由器的IP網絡路由信息通告給鄰居，每一條BGP路由信息包含一個IP網絡地址和對應 該IP網絡地址的路由屬性；路由屬性中包含最短AS路徑屬性，AS路徑是指從BGP路 由器到達該IP網絡地址需要經過的AS序列，最短AS路徑是指從BGP路由器到達該IP 網絡地址需要經過的最少AS序列，所有BGP路由信息構成BGP路由信息庫；

第五步，AS拓撲發現服務器根據接收到的BGP路由信息進行計算，得到初始AS拓 撲以及IP網絡地址與AS號的對應關系，方法是：

(5.1)將AS拓撲用AS鄰接矩陣來表示，AS鄰接矩陣為N×N的0/1矩陣，N為 AS的個數，若第i行第j列的矩陣元素為0，則表示第i個AS與第j個AS之間不存在 鄰接關系；若為1，則表示它們之間存在鄰接關系，具體方法是：

(5.1.1)初始時，將AS鄰接矩陣所有元素設置為0；

(5.1.2)對任意一條AS路徑a₁，a₂，a₃，...，a_k，1≤i≤k-1，k為AS路徑長度，設自治系 統a_i在AS鄰接矩陣中的編號為x，對應AS鄰接矩陣的第x行，自治系統a_i+1在AS鄰 接矩陣中的編號為y，對應AS鄰接矩陣的第y列，則將a_i與a_i+1對應的矩陣元素即第x 行第y列的矩陣元素置為1；

(5.2)根據BGP路由信息計算IP網絡地址與AS號的對應關系，方法是：對每一項 BGP路由信息，若其IP網絡地址為Net1，AS路徑為a₁，a₂，a₃，...，a_m，其中m為AS路徑 長度，則a_m是網絡地址Net1所屬的AS；

第六步，AS拓撲發現服務器和AS拓撲發現探測器相互協作，進行AS鄰接關系的 探測和更新，方法是：

(6.1)在AS拓撲發現服務器中創建一個探測歷史記錄，記錄探測得到的AS轉發路 徑，探測歷史記錄初始時為空，AS轉發路徑是IP分組轉發經過的AS序列；

(6.2)由AS拓撲發現服務器根據當前的AS鄰接矩陣和探測歷史記錄選擇源AS號 和目標AS號；源AS號是待探測的AS轉發路徑的起始AS號，目標AS是待探測的AS 轉發路徑的終止AS號；

(6.3)若第(6.2)步不能得到源AS號和目標AS號，則本輪拓撲發現過程結束， 轉第三步；若第(6.2)步得到了源AS號和目標AS號，轉(6.4)步；

(6.4)根據IP網絡地址和AS號的對應關系、探測器IP地址列表，由AS拓撲發現 服務器從多個AS拓撲發現探測器中選擇出一個作為源AS拓撲發現探測器-簡稱源探測 器，并選擇一個IP地址作為探測目標IP地址，選擇方法為：

(6.4.1)如果探測器IP地址列表中某一個AS拓撲發現探測器的IP地址對應的AS 號就是源AS號，則直接選擇該AS拓撲發現探測器作為源探測器；否則，根據IP網絡 地址和AS號的對應關系以及AS最短路徑的長度，選擇一個IP地址與源AS最近的AS 拓撲發現探測器作為源探測器；

(6.4.2)如果探測器IP地址列表中某一個AS拓撲發現探測器的IP地址對應的AS 號為目標AS號，則直接選擇該AS拓撲發現探測器的IP地址作為探測目標IP地址；否 則，根據IP網絡地址和AS號的對應關系，從對應于目標AS號的IP網絡地址段中隨機 選擇一個有效的單播IP地址作為探測目標IP地址；

(6.4.3)若不能成功選擇出源探測器和探測目標IP地址，則轉(6.2)步；若選擇出 了源探測器和探測目標IP地址，轉(6.5)步；

(6.5)在AS拓撲發現服務器中為每個源探測器設置一個探測請求失敗次數的計數 器，初始時，探測請求失敗次數設置為0；

(6.6)由AS拓撲發現服務器向源探測器發送探測請求消息，探測請求消息中包含 探測目標IP地址；在AS拓撲發現服務器中為每個源探測器設置一個第三定時器，從發 送探測請求消息給某個源探測器開始，AS拓撲發現服務器啟動與該源探測器對應的第三 定時器；第三定時器的超時等待時間為T3；當等待時間達到T3時，定時器超時；

(6.7)源探測器接收到從AS拓撲發現服務器發送來的探測請求消息后，使用 traceroute探測方法獲得從源探測器IP地址到探測目標IP地址的IP轉發路徑；

(6.8)源探測器向AS拓撲發現服務器發送探測應答消息，探測應答消息中包含 traceroute探測方法的探測結果，即從源探測器IP地址到探測目標IP地址的IP轉發路徑；

(6.9)若在與源探測器對應的第三定時器超時之前，AS拓撲發現服務器接收到了源 探測器發來的探測應答消息，則轉第(6.10)步；若第三定時器超時，即在等待時間T3 內沒有收到從所述源探測器發送來的探測應答消息，則探測請求失敗，AS拓撲發現服務 器將該源探測器的探測請求失敗次數增加1；若探測請求失敗次數大于等于最大探測請求 次數K，則AS拓撲發現服務器認為該源探測器已不可用，AS拓撲發現服務器將該源探 測器的IP地址從探測器IP地址列表中刪除，轉步驟(6.4)；若探測請求失敗次數小于K， 則轉步驟(6.6)；

(6.10)AS拓撲發現服務器收到探測應答消息后，根據IP網絡地址與AS號的對應 關系，將源探測器發送來的探測應答消息中包含的從源探測器IP地址到探測目標IP地 址的IP轉發路徑轉換為AS轉發路徑；

(6.11)AS拓撲發現服務器遍歷探測歷史記錄，判斷當前得到的AS轉發路徑是否 是重復的信息，即判斷當前得到的AS轉發路徑是否被包含在探測歷史記錄中；若是重 復的AS轉發路徑信息，則丟棄這條AS轉發路徑，轉(6.2)步；若不是重復的信息， 則將該AS轉發路徑保存到探測歷史記錄中；

(6.12)AS拓撲發現服務器根據AS轉發路徑中的AS鄰接關系，更新AS拓撲圖， 方法為：對于第(6.10)步得到的AS轉發路徑a₁，a₂，a₃，...，a_k，設自治系統a_i在AS鄰接矩 陣中的編號為x，自治系統a_i+1在AS鄰接矩陣中的編號為y，則將a_i與a_i+1對應的矩陣 元素，即第x行第y列的矩陣元素置為1，AS連接信息添加結束后，轉(6.2)步。