[發明專利]流轉發表項的處理方法及裝置

有效

• 申請號: 201210428196.5
• 申請日: 2012-10-31
• 公開（公告）號: CN102930011A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: 楊逸
• 申請（專利權）人: 杭州華三通信技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;H04L12/741
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 謝安昆;宋志強

1.一種流轉發表項的處理方法，對于最多支持N條報文流的轉發系統，建立包含有M個連續存儲位置的哈希HASH表，M、N為自然數，M>N，每個存儲位置包含有多于1個的子存儲位置，其特征在于，該方法包括：

S1、接收到任一報文時，對所述報文的第一特征值進行第一HASH運算，將第一HASH運算的結果所指向的HASH表存儲位置記為B；

S2、遍歷B下的各個子存儲位置，當B下任一子存儲位置滿足要求時，查找到目的表項存儲位置；當B下所有子存儲位置均不滿足要求時，對所接收到的報文的第二特征值進行第二HASH運算，得到待查找的下一個存儲位置與當前存儲位置之間的步長H；

S3、更新B為B+H，遍歷B下的各個子存儲位置，當B下任一子存儲位置滿足要求時，查找到目的表項存儲位置；當B下所有子存儲位置均不滿足要求、且沖突次數小于預先設定的最大沖突次數時，重復執行步驟S3；每當B下所有子存儲位置均不滿足要求時，記為一次沖突。

2.根據權利要求1所述的方法，其特征在于，所述流轉發表項的處理方式為新建時，步驟S2、S3中，

所述B下任一子存儲位置滿足要求，包括：B下任一子存儲位置為空；

所述B下所有子存儲位置均不滿足要求，包括：B下所有子存儲位置均不為空。

3.根據權利要求1所述的方法，其特征在于，所述流轉發表項的處理方式為查找時，步驟S2、S3中，

所述B下任一子存儲位置滿足要求，包括：B下任一子存儲位置的流轉發表項的報文特征值與所述接收到的報文的特征值相同；

所述B下所有子存儲位置均不滿足要求，包括：B下所有子存儲位置中流轉發表項的報文特征值與所述接收到的報文的特征值均不相同。

4.根據權利要求3所述的方法，其特征在于，所述步驟S3中，當沖突次數大于或等于預先設定的最大沖突次數時，按照協議棧處理流程處理所述報文。

5.根據權利要求1所述的方法，其特征在于，所述第一HASH函數、第二HASH函數、報文的第一特征值及報文的第二特征值的設置滿足如下條件：

第二HASH運算得到的函數值H遠小于第一HASH運算得到的函數值。

6.根據權利要求1所述的方法，其特征在于，所述報文特征值包括源IP地址、目的IP地址、協議號、源端口號以及目的端口號中任意一項或幾項的組合。

7.一種流轉發表項的處理裝置，包括哈希表建立模塊，用于針對最多支持N條報文流的轉發系統，建立包含有M個連續存儲位置的哈希HASH表，M、N為自然數，M>N，其特征在于，所述裝置還包括：HASH運算模塊、流轉發表項定位模塊、沖突處理模塊，其中：

報文處理模塊，用于接收到任一報文時，對所述報文的第一特征值進行第一HASH運算，將第一HASH運算的結果所指向的HASH表存儲位置記為B；

流轉發表項定位模塊，用于遍歷B下預先分配的多于1個的子存儲位置，當B下任一子存儲位置滿足要求時，查找到目的表項存儲位置；當B下所有子存儲位置均不滿足要求時，對所接收到的報文的第二特征值進行第二HASH運算，得到待查找的下一個存儲位置與當前存儲位置之間的步長H；

沖突處理模塊，用于執行如下步驟K：更新存儲位置B為B+H，遍歷B下的各個子存儲位置，當B下任一子存儲位置滿足要求時，查找到目的表項存儲位置；當B下所有子存儲位置均不滿足要求、且沖突次數小于預先設定的最大沖突次數時，重復執行步驟K；每當B下所有子存儲位置均不滿足要求時，記為一次沖突。

8.根據權利要求7所述的裝置，其特征在于，所述流轉發表項的處理裝置用于新建流轉發表時，

所述流轉發表項定位模塊，具體用于當B下任一子存儲位置為空時，查找到目的表項存儲位置；當B下所有子存儲位置均不為空時，對所接收到的報文的第二特征值進行第二HASH運算，得到待查找的下一個存儲位置與當前存儲位置之間的步長H；

所述沖突處理模塊，具體用于當B下任一子存儲位置為空時，查找到目的表項存儲位置；當B下所有子存儲位置均不為空、且沖突次數小于預先設定的最大沖突次數時，重復執行步驟K。