[發明專利]流量拓撲生成方法和裝置

有效

• 申請號: 201010139656.3
• 申請日: 2010-04-01
• 公開（公告）號: CN102215136A
• 公開（公告）日: 2011-10-12
• 發明（設計）人: 馮曉林;郝帥;畢經平;黃雙明
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: H04L12/26
• 分類號: H04L12/26;H04L12/24;H04L12/56
• 代理公司: 北京泛華偉業知識產權代理有限公司 11280
• 代理人: 王勇

1.一種流量拓撲生成方法，包括：

步驟1)、在網絡上采集路由信息與流量信息；

步驟2)、從所述流量信息中讀取流量的源地址和目的地址，根據所述路由信息找出源路由器地址和目的路由器地址，進而計算源路由器與目的路由器之間的路徑，根據所述路徑遍歷網絡鏈路，將所述流量信息添加到鏈路中。

2.根據權利要求1所述的流量拓撲生成方法，其特征在于，所述的步驟2)包括：

步驟2-1)、判斷所述流量信息是否都已經被處理；

步驟2-2)、若所有的流量信息都已經被處理，則流量拓撲生成過程結束，否則提取一條未經處理的流量信息條目后執行下一步；

步驟2-3)、從待處理的流量信息條目中提取出該條目的源地址和目的地址，然后結合所述的路由信息找出源路由器地址和目的路由器地址；

步驟2-4)、查找所述源路由器地址和目的路由器地址間的路徑是否已知，若是已知，則執行步驟2-6)，否則，執行下一步；

步驟2-5)、根據所述的源路由器地址與目的路由器地址進行路徑計算，計算成功執行下一步，否則重新執行步驟2-1)；

步驟2-6)、按照所述路徑做鏈路遍歷，將所述流量條目中的流量信息添加到當前鏈路中，然后重新執行步驟2-1)。

3.根據權利要求2所述的流量拓撲生成方法，其特征在于，在所述的步驟2-5)中，所述的路徑計算包括：

步驟2-5-1)、將表示源路由器的節點放入候選組，并且查找源路由器宣告的RouterLSA作為表示源路由器的節點的LSA；

步驟2-5-2)、判斷所述候選組是否為空，如果為空則進入步驟2-5-8)，否則執行下一步；

步驟2-5-3)、從候選組中選擇距離值最小的節點放入選擇組，判斷該節點是否是目的路由器，如果是，則進入步驟2-5-7)，否則，執行下一步；

步驟2-5-4)、判斷該節點是路由器節點還是子網節點，如果是路由器節點則進入下一步，否則執行步驟2-5-6)；

步驟2-5-5)、取出該路由器的RouterLSA，遍歷該RouterLSA中宣告的所有鏈接，根據鏈接的類型判斷鏈接的鄰居節點，完成對所有鏈接的遍歷后，重新執行步驟2-5-2)；

步驟2-5-6)、取出該子網節點對應的NetworkLSA，然后遍歷該NetworkLSA中描述的該子網所鄰接的路由器，為每一個鄰接的路由器查找其RouterLSA，然后在候選組中查找是否已有該節點，如果有，則更新距離值和節點中的鏈表，如果沒有，則將這個新節點加入候選組，在完成對所述子網所鄰接的所有路由器的遍歷后，重新執行步驟2-5-2)。

步驟2-5-7)、將所述選擇組中的節點按進入的先后順序排列，得到從源路由器到目的路由器的路徑；

步驟2-5-8)、未找到路徑，計算結束。

4.根據權利要求3所述的流量拓撲生成方法，其特征在于，在所述的步驟2-5-5)中，根據鏈接的類型判斷鏈接的鄰居節點包括：

步驟a)、對于所述鏈接為類型1或類型4的鏈接，取得對端路由器的RouterID；

步驟b)、在選擇組中根據所述RouterID進行查找，如果發現選擇組有此節點，則不做任何處理，重新選擇一條未經處理的鏈路，否則執行下一步；

步驟c)、在候選組中根據所述RouterID進行查找，如果候選組已有該節點存在，則將剛剛加入候選組的節點的距離值加上該鏈接的鏈路度量值metric，利用所得到的結果更新節點的距離值，然后用更新后的節點距離值跟該節點在候選組中的距離值比較，取較小的值，并執行下一步；如果候選組中沒有該節點存在，則新建一個節點，將該節點的距離值設為剛剛加入候選組的節點的距離值與該鏈接的鏈路度量值metric的和，LSA設為剛剛取到的RouterLSA，然后將這個新節點加入所述候選組，然后重新選擇一條未經處理的鏈路；

步驟d)、節點的距離值被更新，將節點中存儲的鏈表替換為當前路徑，然后重新選擇一條未經處理的鏈路。