[發明專利]一種路由遍歷搜索方法及裝置

有效

• 申請號: 201310482907.1
• 申請日: 2013-10-15
• 公開（公告）號: CN104579725B
• 公開（公告）日: 2018-03-23
• 發明（設計）人: 周泉
• 申請（專利權）人: 中國移動通信集團江蘇有限公司
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/701
• 代理公司: 北京中譽威圣知識產權代理有限公司11279
• 代理人: 郭振興,叢芳

技術領域

本發明涉及網管技術領域，尤其涉及一種路由遍歷搜索方法及裝置。

背景技術

在通信運營商為行業客戶開通專線業務時，需要為客戶調配一條光纖的通路，通過光纖實現客戶點到點的信息通信。在光纖通路的調配過程中，需要根據光纖的類型、必經點、路徑的深度來遍歷搜索所有的路由，由運營商專業網絡管理人員選擇其中的一條。目前對光路路由的遍歷搜索方法是通過單點出發，通過廣度優先或深度優先的算法來遍歷所有路由。

現有方案主要是在內存中構造光纜網絡抽象形成的無向圖，對此無向圖基于靜態最優路由搜索算法如Dijkstra算法、A*算法、Floyd算法等搜索路由，現有方案的缺點是當網絡規模龐大時內存中的無向圖結構也比較龐大，對內存要求高，算法性能低下，搜索速度慢。

發明內容

為了解決現有技術中路由搜索速度慢、性能低下的技術問題，本發明提出一種路由遍歷搜索方法及裝置。

本發明的一個方面，提供一種路由遍歷搜索方法，包括：

搜索與起始點關聯的第一路由及與終止點關聯的第二路由；

比較所述與起始點關聯的第一路由的尾節點和所述與終止點關聯的第二路由的尾節點；

當所述與起始點關聯的第一路由的尾節點和所述與終止點關聯的第二路由的尾節點相同時，將所述與起始點關聯的第一路由和終止點關聯的第二路由組合后形成從起始點到終止點的路由。

本發明的另一個方面，提供一種路由遍歷搜索裝置，包括：

搜索模塊，用于搜索與起始點關聯的第一路由及與終止點關聯的第二路由；

比較模塊，用于比較所述與起始點關聯的第一路由的尾節點和所述與終止點關聯的第二路由的尾節點；

組合模塊，用于當所述與起始點關聯的第一路由的尾節點和所述與終止點關聯的第二路由的尾節點相同時，將所述與起始點關聯的第一路由和終止點關聯的第二路由組合后形成從起始點到終止點的路由。

本發明的路由遍歷搜索方法及裝置，通過起始點和終止點進行雙向路徑搜索再合并的方式，從起始點和終止點同時開始遍歷，遍歷的層數總和為n。然后查看兩個遍歷結果中是否有相同的節點，路由搜索的時間復雜度為降低，可以更快的遍歷所有路由，提高業務開通的響應速度。

附圖說明

圖1是本發明路由遍歷搜索方法實施例的流程示意圖；

圖2是本發明路由遍歷搜索方法另一實施例的流程示意圖；

圖3是本發明路由遍歷搜索裝置實施例的結構示意圖；

圖4是本發明搜索模塊的結構示意圖。

具體實施方式

本發明實施例通過從起始點和終止點雙向搜索路由，再進行路由匹配的方式，利用了計算機的并發處理能力，極大的提高了搜索的效率，降低搜索需要花費的時間成本。以下結合附圖對本發明進行詳細說明。

如圖1所示，本發明實施例提供一種路由遍歷搜索方法，包括以下步驟：

步驟101，搜索與起始點關聯的第一路由及與終止點關聯的第二路由；

步驟102，比較與起始點關聯的第一路由的尾節點和與終止點關聯的第二路由的尾節點；

步驟103，當與起始點關聯的第一路由的尾節點和與終止點關聯的第二路由的尾節點相同時，將與起始點關聯的第一路由和終止點關聯的第二路由組合后形成從起始點到終止點的路由。

步驟101中，搜索與起始點關聯的第一路由包括：

搜索第一指定路由深度下所有以起始點起始的第一路由，第一指定路由深度i=1,2,3...(n+1)/2，其中，n為最大路由深度。

搜索與起始點關聯的第一路由還包括：對于第一路由深度下的以起始點起始的第一路由，查找第一路由的尾節點，查找與尾節點關聯的所有邊（“邊”指的是連接兩個節點的線，即光纜段）；將在邊上但不在第一路由上的節點加入到第一路由，得到第一路由深度下與起始點起始的第一路由。

步驟101中，搜索與終止點關聯的第二路由包括：

搜索第二指定路由深度下所有以起始點起始的第二路由，第二指定路由深度j=n,n-1,n-2...n/2，其中，n為最大路由深度。

搜索與終止點關聯的第二路由還包括：對于第二路由深度下的以終止點起始的第二路由，查找第二路由的尾節點，查找與尾節點關聯的所有邊；將在邊上但不在第二路由上的節點加入到第二路由，得到第二路由深度下與終止點起始的第二路由。

以下以具體的實例詳細描述本發明實施例的路由遍歷搜索方法，如圖2所示，該方法包括以下步驟：