[發(fā)明專利]一種路徑搜索方法及裝置

有效

• 申請?zhí)枺?/td>: 202110981740.8
• 申請日: 2021-08-25
• 公開（公告）號: CN113872863B
• 公開（公告）日: 2023-04-18
• 發(fā)明（設(shè)計）人: 吳俊彥;任志暉
• 申請（專利權(quán)）人: 優(yōu)刻得科技股份有限公司
• 主分類號: H04L45/74
• 分類號: H04L45/74;H04L45/745;H04L45/00;H04L45/24;H04L45/28
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司 11227
• 代理人: 周初冬

1.一種路徑搜索方法，其特征在于，應(yīng)用于目標(biāo)電子設(shè)備，所述方法包括：

獲得節(jié)點(diǎn)地址信息，其中，所述節(jié)點(diǎn)地址信息包括目標(biāo)路由節(jié)點(diǎn)的第一IP地址和目的地節(jié)點(diǎn)的第二IP地址，所述目標(biāo)路由節(jié)點(diǎn)為由源節(jié)點(diǎn)至所述目的地節(jié)點(diǎn)的路由路徑上的一個路由節(jié)點(diǎn)，所述源節(jié)點(diǎn)至所述目的地節(jié)點(diǎn)包括多重ECMP，每一重所述ECMP包括一個或多個路由節(jié)點(diǎn)；

在第一數(shù)據(jù)表中，查找與所述第一IP地址對應(yīng)的目標(biāo)路由掩碼集，所述第一數(shù)據(jù)表中對應(yīng)保存有節(jié)點(diǎn)IP地址和路由掩碼集；

利用布谷鳥過濾器，從所述目標(biāo)路由掩碼集中確定與所述節(jié)點(diǎn)地址信息相匹配的目標(biāo)路由掩碼；

基于所述第二IP地址和所述目標(biāo)路由掩碼確定相應(yīng)的目標(biāo)路由前綴；

基于所述第一IP地址、目標(biāo)路由前綴和所述目標(biāo)路由掩碼，在節(jié)點(diǎn)路由條目表中確定出所述目標(biāo)路由節(jié)點(diǎn)的下一跳節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識，所述節(jié)點(diǎn)路由條目表中保存有多條節(jié)點(diǎn)路由條目，各所述節(jié)點(diǎn)路由條目中均對應(yīng)保存有：節(jié)點(diǎn)IP地址、路由前綴、路由掩碼和下一跳節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，在所述在節(jié)點(diǎn)路由條目表中確定所述目標(biāo)路由節(jié)點(diǎn)的下一跳節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識之后，所述方法還包括：

將已確定的所述目標(biāo)路由節(jié)點(diǎn)的下一跳節(jié)點(diǎn)確定為新的目標(biāo)路由節(jié)點(diǎn)，返回執(zhí)行所述獲得節(jié)點(diǎn)地址信息的步驟，直至確定由所述源節(jié)點(diǎn)至所述目的地的所有路由路徑上的全部路由節(jié)點(diǎn)；

依據(jù)所述全部路由節(jié)點(diǎn)間的上下跳關(guān)系，確定由所述源節(jié)點(diǎn)至所述目的地的所有路由路徑。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述利用布谷鳥過濾器，從所述目標(biāo)路由掩碼集中確定與所述節(jié)點(diǎn)地址信息相匹配的目標(biāo)路由掩碼，包括：

利用布谷鳥過濾器，從所述目標(biāo)路由掩碼集中確定出與所述節(jié)點(diǎn)地址信息相匹配的至少一個路由掩碼；

按照路由掩碼最長匹配原則，在與所述節(jié)點(diǎn)地址信息相匹配的各路由掩碼中，將最長路由掩碼確定為所述目標(biāo)路由掩碼。

4.根據(jù)權(quán)利要求3所述的方法，其特征在于，所述利用布谷鳥過濾器，從所述目標(biāo)路由掩碼集中確定出與所述節(jié)點(diǎn)地址信息相匹配的至少一個路由掩碼，包括：

將所述目標(biāo)路由掩碼集中的一個路由掩碼確定為當(dāng)前處理掩碼；

基于所述第一IP地址和當(dāng)前處理掩碼，從第二數(shù)據(jù)表中確定出目標(biāo)布谷鳥過濾器的過濾器標(biāo)識，所述第二數(shù)據(jù)表中對應(yīng)保存有路由節(jié)點(diǎn)IP地址、路由掩碼和布谷鳥過濾器的過濾器標(biāo)識，所述目標(biāo)布谷鳥過濾器中保存有從目標(biāo)路由節(jié)點(diǎn)的北向接口中獲得的與當(dāng)前處理掩碼對應(yīng)的至少一條路由前綴；

指令所述目標(biāo)布谷鳥過濾器，以使得所述目標(biāo)布谷鳥過濾器查找自身保存的全部路由前綴中是否存在有對象路由前綴，如果是，則將當(dāng)前處理掩碼確定為與所述節(jié)點(diǎn)地址信息相匹配的一個路由掩碼，所述路由前綴為當(dāng)前掩碼，所述對象路由前綴為基于當(dāng)前處理掩碼和所述第二IP地址所獲得的路由前綴；

返回執(zhí)行所述將所述目標(biāo)路由掩碼集中的一個路由掩碼確定為當(dāng)前處理掩碼的步驟，直至確定出與所述節(jié)點(diǎn)地址信息相匹配的全部路由掩碼。

5.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法還包括：

分別從各節(jié)點(diǎn)的北向接口上獲得各節(jié)點(diǎn)的路由條目，各節(jié)點(diǎn)的路由條目中均對應(yīng)保存有：節(jié)點(diǎn)IP地址、路由前綴、路由掩碼和下一跳節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識；

基于已獲得的各節(jié)點(diǎn)的路由條目，創(chuàng)建所述節(jié)點(diǎn)路由條目表。

6.根據(jù)權(quán)利要求5所述的方法，其特征在于，所述方法還包括：

從所述節(jié)點(diǎn)路由條目表中，分別確定各節(jié)點(diǎn)IP地址對應(yīng)的路由掩碼；

分別在各節(jié)點(diǎn)IP地址對應(yīng)的路由掩碼中進(jìn)行去重處理，以分別確定各節(jié)點(diǎn)IP地址對應(yīng)的至少一個去重處理后掩碼；

分別將各節(jié)點(diǎn)IP地址對應(yīng)的所有去重處理后掩碼組合為一個路由掩碼集，以確定各節(jié)點(diǎn)IP地址對應(yīng)的路由掩碼集；

基于已確定的各節(jié)點(diǎn)IP地址對應(yīng)的路由掩碼集，創(chuàng)建所述第一數(shù)據(jù)表。