[發明專利]遍歷樹表表項的方法及裝置

無效

• 申請號: 200710123961.1
• 申請日: 2007-10-16
• 公開（公告）號: CN101146038A
• 公開（公告）日: 2008-03-19
• 發明（設計）人: 於少峰
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L12/46
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及虛擬專用局域網業務(Virtual?Private?LAN?service，簡稱VPLS)，更具體地說，涉及一種VPLS中遍歷樹表表項的方法及裝置。

背景技術

目前，VPLS的二層、三層轉發設備多采用網絡處理器(Network?Processor，簡稱NP)作為底層的轉發模塊，路由協議和用戶管理等上層模塊主要通過表項告知NP如何轉發報文，因此NP在轉發報文時常會涉及到表項的遍歷處理，也就是對用戶表項、轉發表項等進行刪除、老化、添加等處理。

當這些表項為靜態表項時，通過上層模塊下發有效索引進行遍歷，操作方便。

當這些表項為樹表表項，發明人在實施本發明的過程中發現，對于樹表表項無法直接索引，需通過key值進行查找。然而，如果通過上層模塊下發key值來一條條的處理，則遍歷效率很低；而且，有的樹表表項的上層模塊沒有相應索引，只能由NP來進行處理。目前樹表表項的遍歷處理采用NP直接遍歷所有的樹表表項來檢查哪些表項有效而后對有效表項進行處理的方式，如圖1所示。這種方式由于在有效表項較少的情況下，NP也要完整地遍歷所有的樹表表項，故遍歷效率低下。進一步地，當大規格的樹表表項分配于低速內存中時，這種遍歷方式往往會導致對表項處理的超時。

例如，在二層或三層轉發設備中，VPLS的介質訪問控制(Media?AccessControl，簡稱MAC)表項記錄報文的源MAC地址和端口的關系。該MAC表項是樹表表項，且由NP中的微碼(pico?code)創建，上層模塊沒有相應索引和key值。因此該MAC表項的老化、刪除等操作由微碼遍歷，來判斷表項是否有效并處理。在有效MAC表項很少的情況下，NP仍需要遍歷所有的MAC表項進行老化或刪除操作，效率極低。特別是，重新啟動VPLS業務時，需要刪除所有MAC表項，這時由于處理時間較長會導致超時，上層模塊將重復下發刪除命令，使得原刪除還沒有處理完畢，又收到新的刪除命令，從而產生惡性循環，導致消息通道堵塞，出現業務異常。

發明內容

本發明實施例要解決的技術問題在于，針對現有技術存在的上述不足，提供一種高效的遍歷樹表表項的方法及裝置，可避免遍歷處理超時，保證業務正常進行。

本發明實施例解決其技術問題所采用的技術方案是：提供一種網絡處理器遍歷樹表表項的方法，包括以下步驟：

(1)查詢預先建立的樹表的樹表表項映射表，從該樹表表項映射表中獲取有效樹表表項的地址；

(2)根據所獲取的有效樹表表項的地址，處理所述樹表中對應該地址的有效樹表表項。

所述樹表表項映射表中與所述樹表的樹表表項一一對應設置標志位，各標志位標識其對應的樹表表項是否有效；所述網絡處理器通過標識其對應樹表表項有效的標志位在所述樹表表項映射表中的位置獲取該對應有效樹表表項的地址。

所述樹表表項映射表的標志位與所述樹表的樹表表項一一對應、依次設置，其中每一標志位在所述樹表表項映射表中的偏移與其對應樹表表項在所述樹表中的偏移相同；所述網絡處理器根據標識其對應樹表表項有效的標志位在所述樹表表項映射表中的偏移和所述樹表的表項基址得到該對應有效樹表表項的地址。

所述步驟(1)包括：

查詢所述樹表表項映射表，判斷該映射表中當前標志位標識其對應樹表表項是否為有效，若其標識對應樹表表項無效，則跳過，直到判斷得知當前標志位標識其對應樹表表項有效；

在判斷得知當前標志位標識其對應樹表表項有效時，根據該標志位在所述樹表表項映射表中的偏移與所述樹表的表項基址之和得到對應有效樹表表項的地址；

所述方法進一步在步驟(2)之后包括：

(3)判斷所述樹表表項映射表是否查詢完畢，如尚未查詢完畢，則返回步驟(1)，繼續查詢樹表表項映射表中下一個標志位；如映射表已查詢完畢，則結束遍歷。

所述網絡處理器在添加或刪除樹表表項時，對應修改該樹表表項對應的所述樹表表項映射表中的標志位。

所述樹表表項映射表存放于所述網絡處理器的高速內存中。

所述樹表表項為虛擬專用局域網業務的介質訪問控制表項。

本發明實施例還提供一種遍歷樹表表項的裝置，包括：

存儲裝置，存儲樹表及該樹表的樹表表項映射表；

查詢獲取裝置，查詢所述存儲裝置中存儲的樹表的樹表表項映射表，從該樹表表項映射表中獲取有效樹表表項的地址；

處理裝置，根據所獲取的有效樹表表項的地址，處理所述樹表中對應該地址的有效樹表表項。