一種tcam表項優先級的分配方法
2023-05-01 09:09:46 2
專利名稱：一種tcam表項優先級的分配方法
技術領域：
本發明涉及網絡通信技術領域，尤其涉及乙太網中TCAM表項中優先級的分配方法。
背景技術：
TCAM (Ternary Content Addressable Memory,三態內容尋址存儲器)的表項始終是按照一個順序，從上往下查詢逐條匹配，如果匹配成功就立刻停止查詢。如果TCAM表中，只有一條表項是匹配的，那就只能是一個結果；如果存在多條表項匹配，那就只能是優先級高的匹配成功，而優先級低的就不會被匹配了。所以在乙太網應用中，比如ACL(AccessControl List，訪問控制列表)的訪問中，就有存在多個表項匹配的可能性，所以需要一種機制來管理表項的優先級。在整理TCAM表項優先級時，傳統的做法是根據給定的優先級，從高優先級往低優先級遍歷，找到該優先級恰當的存放位置。這個存放位置可能是空的，也可能已經讓別的表項佔了。如果是空的，那麼不需要搬移就能使用。如果被別的表項佔了，那需要先做搬移然後騰出一個空的位置再使用。這種方法雖然可以保證優先級排序的正確性，但是這種方案沒有考慮性能問題。假設第一條表項是放在TCAM的第一個索引位置，也就是優先級最高的位置，然後每次都加入一個優先級更高的表項，則需要每次都要搬移前面下過的所有表項。下N條表項，需要搬移1+2+...+(η-1)次。搬移TCAM的表項是一件耗時的工作，因此這種效率在實際應用過程中是非常低效的，尤其當N很大時，表項下的越多搬移耗時越長。
這種方法的第二個缺點是，搬移的方向不是根據搬移次數的多少，而是根據目標表項優先級變化的方向:優先級從低變成高時，搬移是往低的方向；優先級從高變成低時，搬移是往高的方向。現有技術方案固守一個方向，沒有權衡兩個方向的搬移次數，因此不是最優的。
發明內容
本發明的目的之一是通過優化TCAM中整理優先級的搬移方法，比較兩個搬移方向的搬移次數，找到最佳的搬移方向，從而簡化表項的搬移過程。本發明的另一目的是在表項的搬移次數達到預設的一定條件時，則對已有表項進行重新排序，使重新排序後的索引達到一種最優狀態，這種狀態可以使之後的搬移次數儘可能地減少。為實現上述目的，本發明提出如下技術方案:一種TCAM表項優先級的分配方法，在整理TCAM表項的優先級時，如果某一表項的目標位置為非空位置，則比較將所述表項搬移至所述目標位置通過向上搬移和向下搬移所需的表項搬移數，並選擇表項搬移數較少的搬移方向為所述表項的搬移方向。當所述搬移數較少的表項搬移數大於預先設定的觸發值時，則觸發表項優先級的重排算法，將TCAM中的所有表項進行重新排序，使每一表項到達最優位置。所述重新排序是將整個TCAM的所有表項儘可能地離散開。所述重排算法下，每一表項重排的最優位置為:(TCAM索引的個數/現有表項的個數)*當前表項在現有表項中的相對位置。所述預先設置的觸發條件根據軟體計算耗時及表項移動一次的耗時設定。在整理TCAM表項的優先級時，如果某一表項的目標位置為非空位置，則首先需要將所述目標位置的表項向上或向下搬移，使目的位置為空位置。在整理TCAM表項的優先級時，如果某一表項的目標位置為空位置，則直接將所述表項搬移至目標位置。與現有技術相比，本發明在搬移方向上不再拘泥於一個方向，而是考慮了雙向，為使目的索引變成空的，比較了向上搬移和向下搬移所需要的表項搬移次數，最後選取次數較少的那個方向。因為向上搬移和向下搬移的耗時是均等的，所以只要保證次數更少，就能保證搬移耗時更短。其次，本發明提出觸發重排的機制，即在搬移次數達到某個條件時，重排算法被觸發，將現有TCAM中的所有表項進行重新排序，使之達到一種最優的狀態。觸發的條件是一種實驗數據，需要權衡包括軟體計算耗時，表項移動一次的耗時等，其核心是將整個TCAM的所有表項儘可能地離散開來，因為越是離散的表項，搬移的可能性就越小，搬移的次數也越少。在極端條件下，每兩個表項之間都有一個空的索引，那麼任何優先級的改變最多只需要搬移一次。所以在重排算法下，每個表項都有它的最優位置，這個位置的計算方法即:(TCAM索引的個數/現有表項 的個數)*當前表項在現有表項中的相對位置。這個簡單算法計算速度快，表項的目的索引是唯一的，並儘可能地將現有表項離散開來，從而大大的提升了整理優先級的速度。
圖1是本發明TCAM表項中優先級分配方法的流程示意圖；圖2A C是本發明TCAM中進行雙向搬移表項的示意圖；圖3A C是本發明TCAM中當表項的搬移次數大於預設值時，表項重新排序的示意圖。
具體實施例方式下面將結合本發明的附圖，對本發明優選實施例中的技術方案進行清楚、完整的描述。本發明提出的TCAM中表項優先級的分配方法，如圖1所示，其在表項的搬移方向上通過比較向上、向下雙向搬移的次數後，選取搬移次數較少的方向為表項的搬移方向。如圖2A C所示TCAM表中，共有6條表項，其索引和優先級分別是索引I對應的優先級是100，索引2對應的優先級是90，索引3對應的優先級是80，索引4對應的優先級是30，索引5對應的優先級是20，索引7對應的優先級是5。現在將表項中索引5的優先級改為50，則該索引5的目標位置在優先級80和優先級30之間。如圖2A所示，在優先級為80的索引3和優先級為30的索引4間沒有空餘的位置，即索引5的目標位置為非空，因此，此時首先需要將目標位置的表項搬移至其他位置。如果採用向上搬移的方向，則需要搬移3個表項，如圖2B所示；如果採用向下搬移的方向，則需要搬移2個表項，如圖2C所示；將向上搬移的次數和向下搬移的係數相比較，得出向下搬移次數更少，所以採取將TCAM表項向下搬移的方式。對於表項的搬移次數達到預先設定的條件時，則表項重排算法被觸發，從而對現有TCAM中的所有表項進行重新排序，使其達到一種最優的狀態。重排算法的核心思想是將整個TCAM中的所有表項儘可能地離散開來，因為越是離散的表項，搬移的可能性就越小，搬移的次數也就越少。如圖3A C的TCAM中有5條表項，其索引和優先級分別是:索引O對應的優先級是100，索引I對應的優先級是90，索引2對應的優先級是80，索引3對應的優先級是70，索引4對應的優先級是60。現將優先級是60的表項改為優先級110，目標位置在索引0，因此需要將索引0、1、2、3、4分別向下移動一個位置，總共需要搬移5個表項。假設預先設定的條件為4次，因為這種搬移次數到達了預先設置的條件，因此觸發了重新排序。根據前面給定的公式，重新排序的結果是，所有表項都間隔一個位置存放，儘可能地離散開來，形成如圖3C所示的重排後的排列方式，大大提升了 TCAM中整理優先級的速度。本發明的技術內容及技術特徵已揭示如上，然而熟悉本領域的技術人員仍可能基於本發明的教示及揭示而作種種不背離本發明精神的替換及修飾，因此，本發明保護範圍應不限於實施例所揭示的內容，而應包括各種不背離本發明的替換及修飾，並為本專利申請權利要求所涵蓋。`
權利要求
1.一種TCAM表項優先級的分配方法，其特徵在於:在整理TCAM表項的優先級時，如果某一表項的目標位置為非空位置，則比較將所述表項搬移至所述目標位置通過向上搬移和向下搬移所需的表項搬移數，並選擇表項搬移數較少的搬移方向為所述表項的搬移方向。
2.根據權利要求1所述的TCAM表項優先級的分配方法，其特徵在於:當所述搬移數較少的表項搬移數大於預先設定的觸發值時，則觸發表項優先級的重排算法，將TCAM中的所有表項進行重新排序，使每一表項到達最優位置。
3.根據權利要求2所述的TCAM表項優先級的分配方法，其特徵在於:所述重新排序是將整個TCAM的所有表項儘可能地離散開。
4.根據權利要求2或3所述的TCAM表項優先級的分配方法，其特徵在於:所述重排算法下，每一表項重排的最優位置為: (TCAM索引的個數/現有表項的個數)*當前表項在現有表項中的相對位置。
5.根據權利要求2所述的TCAM表項優先級的分配方法，其特徵在於:所述預先設置的觸發條件根據軟體計算耗時及表項移動一次的耗時設定。
6.根據權利要求1所述的TCAM表項優先級的分配方法，其特徵在於:在整理TCAM表項的優先級時，如果某一表項的目標位置為非空位置，則首先需要將所述目標位置的表項向上或向下搬移，使目的位置為空位置。
7.根據權利要求1所述的TCAM表項優先級的分配方法，其特徵在於:在整理TCAM表項的優先級時，如果某一表項的目標位置為空位置，則直接將所述表項搬移至目標位置。
8.一種TCAM表項優先級的分配方法，其特徵在於:在整理TCAM表項的優先級時，如果某一表項的目標位置為非空位置，則比較將所述表項搬移至所述目標位置通過向上搬移和向下搬移所需的表項搬移數，且當比較後得到的較少的表項搬移數大於預先設定的觸發條件時，則觸發表項優先級的重排算法，將TCAM中的所有表項進行重新排序，使每一表項到達最優位置。`
9.根據權利要求8所述的TCAM表項優先級的分配方法，其特徵在於:所述重排算法下，每一表項重排的最優位置為: (TCAM索引的個數/現有表項的個數)*當前表項在現有表項中的相對位置。
10.根據權利要求2所述的TCAM表項優先級的分配方法，其特徵在於:所述預先設置的觸發條件根據軟體計算耗時及表項移動一次的耗時設定。
全文摘要
本發明揭示了一種TCAM表項優先級的分配方法，其在整理TCAM表項的優先級時，如果某一表項的目標位置為非空位置，則比較將所述表項搬移至所述目標位置通過向上搬移和向下搬移所需的表項搬移數，並選擇表項搬移數較少的搬移方向為所述表項的搬移方向，當所述搬移數較少的表項搬移數大於預先設定的觸發值時，則觸發表項優先級的重排算法，將TCAM中的所有表項進行重新排序，使每一表項到達最優位置，這樣大大提高了TCAM表項中優先級的整理速度。
文檔編號H04L12/741GK103248575SQ201310178660
公開日2013年8月14日 申請日期2013年5月14日 優先權日2013年5月14日
發明者周志洪, 陶秋平, 何志川, 趙茂聰 申請人:盛科網絡(蘇州)有限公司