[發明專利]一種MPLS中快速查找目標節點的方法及裝置

有效

• 申請號: 201210006495.X
• 申請日: 2012-01-10
• 公開（公告）號: CN103200099A
• 公開（公告）日: 2013-07-10
• 發明（設計）人: 孟慶超
• 申請（專利權）人: 邁普通信技術股份有限公司
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L12/723
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 牛崢;王麗琴

1.一種多協議標簽交換MPLS中快速查找目標節點的方法，其特征在于，包括如下步驟：

A、初始化用于存儲標簽值的HASH結構，將HASH結構的每一條沖突鏈中的轉發表節點分為多個節點段，將每個節點段的首、尾節點指針、該節點段包含的轉發表節點數量記錄到節點段管理結構中；

B、將MPLS標簽分組報文攜帶的標簽作為鍵值找到目標轉發表節點所在的HASH結構的沖突鏈；

C、將所述鍵值同所述HASH沖突鏈對應的各個節點段管理結構中的首、尾節點的鍵值進行比較，找到目標轉發表節點所在的節點段，并從所述節點段中找到目標轉發表節點。

2.根據權利要求1所述的方法，其特征在于，所述HASH結構中的轉發表節點按照鍵值從小到大順序排列。

3.根據權利要求1所述的方法，其特征在于，所述步驟C包括：如果鍵值小于節點段的首節點的鍵值，則認為沒找到目標轉發表節點；如果鍵值在節點段所屬節點鍵值的范圍內，則認為目標節點在該節點段中，根據該節點段信息找到沖突鏈表的對應分段并開始查找；如果鍵值大于該節點段尾節點鍵值，則查詢下一節點段。

4.根據權利要求2所述的方法，其特征在于，步驟C之后進一步包括：

將轉發表節點按照鍵值從小到大的順序添加到沖突鏈對應的節點段中，并將節點段信息中的轉發表節點數量加1；

判斷新添加節點是否為節點段新的首節點或者尾節點，若是，則更新節點段對應的節點段管理結構。

5.根據權利要求4所述的方法，其特征在于，所述將轉發表節點按照鍵值從小到大的順序添加到沖突鏈對應的節點段中包括：如果所述鍵值大于節點段的尾節點鍵值，則認為該轉發表節點不屬于該節點段，轉至下一節點段繼續比較，否則認為該轉發表節點屬于該節點段；如果大于最后一個節點段首節點鍵值，則認為該轉發表節點屬于最后一個節點段。

6.根據權利要求2所述的方法，其特征在于，步驟C之后進一步包括：

從所述節點段中刪除所述目標轉發表節點；

判斷刪除的轉發表節點是否為節點段的首節點或者尾節點，若是，則更新節點段對應的節點段管理結構。

7.根據權利要求4或6所述的方法，其特征在于，所述將目標轉發表節點按照鍵值的順序添加到沖突鏈對應的分段中之后或所述從所述節點段中刪除所述目標轉發表節點之后，進一步包括：

比較所述節點段所在沖突鏈的各個節點段中的轉發表數量差值是否超過預先配置的最大差值，若是，根據沖突鏈中轉發表節點的數量和節點段的數量確定一個節點段包含的轉發表節點數目，根據所述轉發表節點數目重新劃分節點段，將重新劃分后的各個節點段的首節點和尾節點指針、節點段的轉發表個數等信息更新到節點段管理結構中。

8.根據權利要求1至6任一項所述的方法，其特征在于，該方法進一步包括：

根據外部事件或定時器觸發掃描所述HASH結構的沖突鏈，比較沖突鏈的各個節點段中的轉發表數量差值是否超過預先配置的最大差值，若是，根據沖突鏈中轉發表節點的數量和節點段的數量確定一個節點段包含的轉發表節點數目，根據所述轉發表節點數目重新劃分節點段，將重新劃分后的各個節點段的首節點和尾節點指針、節點段的轉發表個數等信息更新到節點段管理結構中。

9.一種多協議標簽交換MPLS中快速查找目標節點的裝置，其特征在于，包括：

標簽值存儲模塊，用于初始化用于存儲標簽值的HASH結構，將HASH結構的每一條沖突鏈分為多個節點段，將每個節點段的首、尾節點指針、該節點段包含的轉發表節點數量記錄到節點段管理結構中；

沖突鏈查找模塊，用于將MPLS標簽分組報文攜帶的標簽作為鍵值找到目標轉發表節點所在的HASH結構的沖突鏈；

節點查詢模塊，用于將所述鍵值同所述沖突鏈查找模塊所找到的HASH沖突鏈對應的各個節點段管理結構中的首、尾節點的鍵值進行比較，找到目標轉發表節點所在的節點段，并從所述節點段中找到目標轉發表節點。

10.根據權利要求9所述的裝置，其特征在于，該裝置進一步包括：

節點信息管理模塊，用于從存儲模塊中刪除節點查詢模塊所查找到的目標轉發表節點，和/或，將轉發表節點按照鍵值從小到大的順序添加到標簽值存儲模塊存儲的對應的節點段中。