路由表的管理方法和裝置的製作方法

2023-07-04 15:40:06 2

專利名稱：：路由表的管理方法和裝置的製作方法
技術領域：
：本發明涉及通信領域，具體而言，涉及一種路由表的管理方法和裝置。
背景技術：
：路由器、交換機是組網的核心設備，而這些設備最基本的也是最核心的功能就是基本轉發。基本轉發是通過查找路由表來實現的，因此查找路由表的性能直接影響著路由器、交換機的性能。路由表的查找是按照最長前綴匹配的原則。常用的實現最長前綴匹配的方法有基於hash表的方法和基於Trie表的方法。這些方法的特點是查一次路由表需要進行若干次比較操作，而且比較操作的次數不是固定的。這就使得查表的性能不夠高，而且也不夠穩定。TCAM是一種專用三態內容可尋址存儲器，可以進行快速大量並行搜索，並且一次查找的時間是固定的。因此，在高端路由器中通常選用TCAM晶片來存放路由表。TCAM晶片在進行並行搜索時，如果有多個匹配項，一般都採用低地址優先的策略命中地址最低的那一項。因此，如果選用TCAM晶片來存儲路由表，在更新路由表時需要使IP前綴按照其長度降序排列。目前，常用的基於TCAM的IP前綴的排序方法的基本原理可以歸為兩類PL0J3PT算法和CAO_OPT算法。PLO_OPT算法在排序時基於兩個約束(1)前綴長的條目必須在前綴短的條目前面；(2)前綴長度相同的兩個條目沒有順序限制。CAO_OPT算法在排序時也是基於兩個約束(l)在一個前綴路徑上的條目必須按遞減序排列；(2)不在一個前綴路徑上的條目沒有順序限制。這兩種思想各有憂缺點，PLCLOPT算法便於實現，但是總體性能沒有CAO_OPT高，CAO_OPT算法性能較高，然而實現起來比較複雜。但是，在相關技術中，基於PL0J3PT算法和CACL0PT算法的路由表的管理方法在更新路由表中的表項時搬移次數較多，佔用了較多的資源和花費了相對長的時間。
發明內容針對相關技術中基於PLO_OPT算法和CAO_OPT算法的路由表的管理方法在更新路由表中的表項時搬移次數較多並佔用了較多的資源和花費了相對長的時間的問題而提出本發明，為此，本發明的主要目的在於提供一種路由表的管理方法和裝置，以解決上述問題至少之一。為了實現上述目的，根據本發明的一個方面，提供了一種路由表的管理方法。根據本發明的路由表的管理方法包括獲取待插入路由表的表項的前綴長度，其中，在上述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源；在上述路由表中找到與上述前綴長度對應的第一表項空間；將上述待插入的表項插入到上述第一表項空間內的空閒資源中。為了實現上述目的，根據本發明的另一方面，提供了一種路由表的管理裝置。4根據本發明的路由表的管理裝置包括獲取模塊，用於獲取待插入路由表的表項的前綴長度，其中，在上述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源；查找模塊，用於在上述路由表中找到與上述前綴長度對應的第一表項空間；插入模塊，用於將上述待插入的表項插入到上述第一表項空間內的空閒資源中。根據本發明，預先根據高斯分布模型為路由表中各個前綴長度的表項空間分配資源，在插入表項的過程中採用最鄰近法則來尋找空閒的資源，並且在刪除表項的過程中直接回收資源不做搬移操作。在這些策略基礎上建立的路由表管理系統在實際網絡應用中具有較高的性能和自適應能力，並減少了所佔用的資源和花費的時間。此處所說明的附圖用來提供對本發明的進一步理解，構成本申請的一部分，本發明的示意性實施例及其說明用於解釋本發明，並不構成對本發明的不當限定。在附圖中圖1是根據本發明實施例的路由表的管理方法的流程；圖2是根據本發明實施例的前綴長度二分線的示意圖；圖3是根據本發明實施例的直接插入表項的示意圖；圖4是根據本發明實施例的按最鄰近法則申請空閒的資源插入表項的示意圖；圖5是根據本發明實施例的路由表的管理裝置的結構框圖。具體實施例方式下文中將參考附圖並結合實施例來詳細說明本發明。需要說明的是，在不衝突的情況下，本申請中的實施例及實施例中的特徵可以相互組合。功能概述針對相關技術中基於PL0J3PT算法和CA0J3PT算法的路由表的管理方法在更新路由表中的表項時搬移次數較多並佔用了較多的資源和花費了相對長的時間的問題，本發明提供了路由表的管理方法和裝置。在根據本發明的方案中，預先根據高斯分布模型為路由表中各個前綴長度的表項空間分配資源，在插入表項的過程中採用最鄰近法則來尋找空閒的資源，並且在刪除表項的過程中直接回收資源不做搬移操作。在這些策略基礎上建立的路由表管理系統在實際網絡應用中具有較高的性能和自適應能力，並減少了所佔用的資源和花費的時間。根據本發明的實施例，提供了一種路由表的管理方法。圖l是根據本發明實施例的路由表的管理方法的流程。如圖1所示，該方法包括如下的步驟S102至步驟S106:S102，獲取待插入路由表的表項的前綴長度，其中，在上述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源。S104，在上述路由表中找到與上述前綴長度對應的第一表項空間。S106，將上述待插入的表項插入到上述第一表項空間內的空閒資源中。如果上述第一表項空間中存在空閒的資源，則確定上述第一表項空間在上述路由表中的位置，並按照確定的位置對應的方向查找空閒的資源，將上述表項插入到所查5找到的第一個空閒的資源中，其中，上述位置包括第一部分和第二部分，上述第一部分對應於第一方向，上述第二部分對應於第二方向，且上述第一方向和上述第二方向相反。優選的，根據上述高斯分布模型的均值將上述路由表劃分成上述第一部分和上述第二部分。如果上述第一表項空間不存在空閒的資源，則判斷與上述第一表項空間相鄰的表項空間是否存在空閒資源；在與上述第一表項空間相鄰的表項空間存在空閒資源的情況下，選擇一個存在空閒資源的表項空間；在上述選擇出的表項空間中沿該表項空間的位置對應的方向查找空閒資源；將所查找出的最一個空閒資源標識為上述第一表項空間的空閒資源，並將上述表項插入到該空閒資源中。優選的，上述選擇一個存在空閒資源的表項空間包括在與上述第一表項空間相鄰的表項空間中選擇空閒資源數目最多的表項空間。如果與上述第一表項空間相鄰的表項空間中都不存在空閒資源，則選擇與上述第一表項空間最近的、且存在空閒資源的表項空間；在上述選擇出的表項空間中沿該表項空間的位置對應的方向查找到最後一個空閒資源；將與上述第一表項空間最鄰近的、且與選擇的表項空間位於同一側的一個表項搬移到所查找到的最後一個空閒資源中，將該表項所對應的資源標記為上述第一表項空間的空閒資源，並將待插入的表項插入到該空閒資源中。上述選擇與上述第一表項空間最近的、且存在空閒資源的表項空間包括選擇與上述第一表項空間最近的、且存在空閒資源最多的表項空間。上述第一方向與上述第二方向均指向上述第一部分與上述第二部分的交界位置。隨後，在刪除表項時，獲取待刪除的表項的前綴長度；在上述路由表中找到與上述前綴長度對應的第二表項空間；刪除上述第二表項空間中與上述待刪除的表項對應的資源。下面將結合實例對本發明實施例的實現過程進行詳細描述。本發明提供了一種基於TCAM的路由表管理方法，該方法在實際的網絡環境中能夠獲得較高的更新性能，所以稱該方法具有網絡環境自適應能力。該方法基於PLCLOPT算法的基本原理，並根據網絡環境的特點加以改進，具體實現步驟為(a)初始化時為每個前綴長度預留一定的表空間，預留的策略採用高斯分布；(b)在插入表項時，如果表項的前綴長度對應的表空間存在空閒的資源則直接插入，如果不存在則依據最鄰近法則探尋一個空閒的資源，然後進行搬移操作，最後再插入表項；(C)在刪除表項時直接將表項刪除，對應的前綴管理單元回收該資源，不執行任何搬移操作，這樣設計的依據是，網絡環境在一定的時間內是穩定的，即網絡設備所在的網絡的拓撲結構在一定的時間內是不會改變的，或者改變很小，這就使得前綴長度的分布在一定時間內是穩定的，刪除時，不執行搬移操作，相當於記住了前綴長度的分布，這樣的設計使得刪除時沒有搬移操作，再次插入時搬移操作較少。本發明還在該方法的基礎之上建立了基於TCAM的高性能路由表管理系統，該系統由三部分組成系統啟動單元，系統停止單元，系統動態管理單元。本發明採用以下技術方案路由表管理方法可以以PLO_OPT算法的思想為基礎，基於兩個約束(a)前綴長的條目必須排在前綴短的條目前面；(b)前綴長度相同的兩個條目沒有順序限制。路由表管理系統核心部分由前綴管理單元，本地緩存表，初始化策略管理單元，更新策略管理單元四部分組成。在TCAM中一個路由表項由一個key和一個mask組成，例如255.255255of本發明將形如這樣的路由表項稱為IP前綴，前綴的長度是由mask來表示的，例子中的IP前綴的長度為24。每個前綴長度都對應一個管理單元，該管理單元中保存的主要信息有為該前綴長度預留的表項空間的大小、表項空間在表中的起始位置，表項空間的使用情況等。在插入一個IP前綴時，由於需要保證存放在TCAM中的所有前綴按前綴長度降序排列，這時可能需要對已經存入的前綴進行搬移，由於讀TCAM的操作比較耗時，因此，在本發明中為TCAM中的路由表建立一張本地緩存表，這樣每次搬移的時候就可以直接從本地緩存表中讀取數據。讀本地緩存表的速度比讀TCAM中路由表的速度快得多，這樣就能進一步提高路由表更新的性能。本發明的核心內容就是初始化時配置預留空間的策略，以及在更新表(包括插入表項和刪除表項)的過程中如何動態管理表項空間的策略。在初始化時按照高斯分布模型來配置預留空間的大小，在高斯分布模型中有兩個參數需要設定P(均值)和S(方差)。通常可以根據所處的網絡環境估計出這兩個參數的先驗值。如果沒有任何先驗值，可以這樣設置IPV4前綴長度的範圍為，長度小於8的前綴最多有256條(28=256)，因此可以為前綴長度為8的表項空間預留256個表項資源。然後將P設置為8和32兩者的中間值，設置6S=32-8。在插入前綴時首先根據前綴的長度找到其對應的表項空間，如果表項空間中有空閒的資源則直接插入，如果表項空間中已經沒有空閒的資源，並且路由表未滿，則按照最鄰近法則找到一個空閒的資源，然後將該資源搬移到該前綴長度對應的表項空間，插入該前綴。按照最鄰近法則探尋空閒空間時如果有兩個距離相等的鄰居都有空閒空間則選擇向擁有較多空閒的資源的鄰居空間申請資源。在刪除表項時，對應的前綴管理單元直接回收該資源，這樣的做法有兩個好處首先刪除表項時操作非常簡單，沒有搬移操作，其次當路由器所處的網絡環境(網絡的拓撲結構)穩定後，認為路由表的前綴長度分布也趨於穩定是合理的，刪除的時候直接回收資源不改變各個前綴長度對應的表項空間的大小，相當於保持了路由表前綴長度的分布模型。這樣的處理在實際的網絡應用中具有很好的效果。下面參照附圖，以IPv4路由表的更新為例子，對根據本發明實施例的技術方案作進一步的詳細描述在詳細描述技術方案之前，首先介紹相關的基本概念。l)表的大小在TCAM上創建的路由表的大小，用TableSize表示，在以下的介紹當中表的大小指表的邏輯大小，即可以存放的前綴的數目。2)表空間在表中佔據的範圍，用TableSpace[low，high]表示3)前綴管理單元每個前綴長度都對應著一個前綴管理單元，由兩部分信息組成，一是該長度的前綴對應的表空間，而是該長度的前綴已經寫入的條目數，記作formulaseeoriginaldocumentpage8i表不前綴的長度，對於IPv4路由表來說前綴長度的範圍。4)初始化策略管理單元在系統初始化的時候根據表空間預留策略為每個前綴長度配置一定大小的表空間。5)更新策略管理單元管理表的插入刪除操作，保證路由表始終按照前綴長度降序排列。6)前綴長度的二分線如附圖2所示，從附圖2可以看到前綴長度二分線，將整個前綴範圍分為兩個部分，從最小長度到分界線的範圍部分稱為下部，從分界線到最長前綴的部分稱為上部。下部和上部的最大區別是插入條目的方向。這裡，可以將前綴長度二分線的位置設置成與所述高斯分布模型的均值相對應，從而將所述路由表劃分成所述第一部分和所述第二部分。但本發明不僅限於此，例如，可以在將前綴長度二分線的位置設置成與所述高斯分布模型均值附近的值相對應。此外，下部和上部中插入條目的方向可以指向前綴長度二分線。路由表管理系統主要由三大模塊組成系統啟動單元、系統停止單元和系統動態管理單元。下面分別詳細介紹這三個單元的功能及實現細節。l)系統啟動單元系統啟動單元組由三個小的功能模塊組成TCAM表創建模塊，本地緩存表創建模塊，前綴管理單元初始化模塊。a)TCAM表創建模塊，調用TCAM表創建接口在TCAM晶片上創建一張路由表。b)本地緩存表創建模塊，在本地內存上申請一塊空間用於存放緩存表。c)前綴管理單元初始化模塊，為每個前綴長度申請一個對應的前綴管理單元；然後由初始化策略管理單元依據高斯分布模型為每個前綴長度配置初始的表空間大小。對於高斯模型來說，需要設置兩個參數P和S。如果有網絡環境的先驗知識則依據先驗知識來設置，如果沒有先驗知識可以按照默認方式來設置。2)系統停止單元系統停止單元主要完成銷毀TCAM晶片上的路由表，釋放本地緩存表所佔用的內存空間以及銷毀前綴管理單元。3)系統動態管理單元系統動態管理單元由兩個模塊組成表項插入模塊和表項刪除模塊。表項插入模塊的處理流程如下l)判斷表是否已滿，如果已滿則返回失敗2)調用更新策略管理單元來計算表項的插入位置，並完成對已存入表項的搬移操作和對新添加表項的插入工作，具體過程為獲取表項的前綴長度，然後找到對應的前綴管理單元，依據前綴管理單元中表項空間的信息判斷是否還有空閒的資源。如果有，則從這些空閒的資源中申請一個，然後插入該表項，如附圖3所示。優選的，根據該表項空間的位置所對應的方向來在該表項空間內查找是否有空閒資源，該位置可以包括上部和下部，其中，上部對應於第一方向，下部對應第二方向，且第一方向與第二方向相反，如圖2所示。例如，可以將表項插入到所查找到的第一個空閒資源中。如果沒有空閒的資源，則按照最鄰近法則向最鄰近的有空閒的資源的前綴管理單元的表空間申請一個空閒的資源，然後通過搬移操作將申請的空閒的資源搬移到自己的表空間，最後將表項插入，如附圖4所示。以圖4為例，根據本發明實施例的路由表的管理方法具體包括如下步驟1)獲取待插入路由表的表項的前綴長度為5。2)在路由表中查找與前綴長度對應的表項空間prefix5。3)判斷出表項空間prefix5已滿，沒有空閒資源。4)查找與表項空間prefix5相鄰的表項空間prefix4和prefix6，發現prefix4和prefix6同樣沒有空閒資源。此時，如果表項空間prefix4和prefix6均有空閒資源，則選擇其中一個作為待查找的表項空間，這裡，可以選擇空閒資源最多的那個表項空間。在上述選擇出的表項空間中沿該表項空間的位置對應的方向查找空閒資源，並將所查找出的最一個空閒資源標識為上述表項空間prefix5的空閒資源，並將待插入的表項插入到該空閒資源中。5)查找到與表項空間prefix5最近的、且存在空閒資源的表項空間prefix3和prefix7。查找到prefix7和prefix3都有空閒資源，由於prefix3有三個空閒資源，prefix7兩個空閒資源，這時，優選的，可以選擇向空閒資源較多的表項空間申請，即，確定向表項空間prefix3中請一個空閒資源。可以沿著prefix3的位置所對應的方向查找空閒資源，優選的，可以將查找到的最後一個空閒資源，例如索引號為19的空閒資源，作為待申請的空閒資源。6)搬移空閒資源。可以將與待插入的表項對應的表項空間(prefix5)最鄰近的、且與選擇的表項空間(表項空間prefix3)位於同一側的一個表項搬移到所查找到的最後一個空閒資源。例如，將prefix4中索引為13的資源上的表項搬移到prefix3的索引為19的資源處。7)將原prefix4的索引為13的資源標記為prefix5的空閒資源，並將待插入的表項插入到索引13的資源中。表項刪除模塊的處理流程如下l)獲取要刪除的表項的前綴長度，根據前綴長度找到對應的前綴管理單元，修改EntryNum值。2)將表項直接刪除在一個實際的網絡環境中，採集IPv4的路由表信息，下面用表1列出IP前綴長度的分布情況表1tableseeoriginaldocumentpage10tableseeoriginaldocumentpage11在網絡自適應能力方面，刪除路由表中所有的表項，然後再重新插入原來的數據，對應的結果如表3所示表3算法類型參數設置搬移次數原始的PLO—OPT算法無1184855次本發明的方法o次下面用等概率隨機數發生器產生實驗樣本來驗證本發明提出的方法的網絡自適應能力。1)第一次同步路由表，相應的實驗數據如表4所示表4tableseeoriginaldocumentpage112)第二次同步路由表(先將路由表中的條目全部刪除，再同步路由表)，相應的實驗數據如表5所示表5算法類型參數設置搬移次數原始的PLO—OPT算法無1725331次本發明的方法默認設置6160次3)第三次同步路由表(先將路由表中的條目全部刪除，再同步路由表)，相應的實驗數據如表6所示表6算法類型參數設置搬移次數原始的PLO—OPT算法無1723187次本發明的方法默認設置7717次從上面的實驗結果可以看到，只要前綴長度的分布保持穩定，則根據本發明實施例的方法在初次同步路由表之後的性能非常好。這也就驗證了本發明的方法可以記憶前綴長度的分布，從而具有網絡環境自適應能力。根據本發明實施例，預先根據高斯分布模型為路由表中各個前綴長度的表項空間分配資源，在插入表項的過程中採用最鄰近法則來尋找空閒的資源，並且在刪除表項的過程中直接回收資源不做搬移操作。在這些策略基礎上建立的路由表管理系統在實際網絡應用中具有較高的性能和自適應能力，並減少了所佔用的資源和花費的時間。根據本發明的實施例，提供了一種路由表的管理裝置。圖5是根據本發明實施例的路由表的管理裝置的結構框圖。如圖5所示，該裝置包括獲取模塊502，用於獲取待插入路由表的表項的前綴長度，其中，在所述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源；查找模塊504，用於在所述路由表中找到與所述前綴長度對應的第一表項空間；插入模塊506，用於將所述待插入的表項插入到所述第一表項空間內的空閒資源中。所述裝置還包括分配模塊508，用於根據高斯分布模型為各個前綴長度的表項空間分配資源。如果上述第一表項空間中存在空閒的資源，則確定上述第一表項空間在上述路由表中的位置，並且查找模塊504按照確定的位置對應的方向查找空閒的資源，插入模塊506將上述表項插入到所查找到的第一個空閒的資源中，其中，上述位置包括第一部分和第二部分，上述第一部分對應於第一方向，上述第二部分對應於第二方向，且上述第一方向和上述第二方向相反。優選的，分配模塊508根據上述高斯分布模型的均值將上述路由表劃分成上述第一部分和上述第二部分，如圖2所示。如果上述第一表項空間不存在空閒的資源，則判斷與上述第一表項空間相鄰的表項空間是否存在空閒資源；在與上述第一表項空間相鄰的表項空間存在空閒資源的情12況下，選擇一個存在空閒資源的表項空間；查找模塊504在上述選擇出的表項空間中沿該表項空間的位置對應的方向查找空閒資源；將所查找出的最一個空閒資源標識為上述第一表項空間的空閒資源，並且插入模塊506將上述表項插入到該空閒資源中。優選的，上述選擇一個存在空閒資源的表項空間包括在與上述第一表項空間相鄰的表項空間中選擇空閒資源數目最多的表項空間。如果與上述第一表項空間相鄰的表項空間中都不存在空閒資源，則選擇與上述第一表項空間最近的、且存在空閒資源的表項空間；查找模塊504在上述選擇出的表項空間中沿該表項空間的位置對應的方向查找到最後一個空閒資源；將與上述第一表項空間最鄰近的、且與選擇的表項空間位於同一側的一個表項搬移到所查找到的最後一個空閒資源中，將該表項所對應的資源標記為上述第一表項空間的空閒資源，並且插入模塊506將待插入的表項插入到該空閒資源中。上述選擇與上述第一表項空間最近的、且存在空閒資源的表項空間包括選擇與上述第一表項空間最近的、且存在空閒資源最多的表項空間。上述第一方向與上述第二方向均指向上述第一部分與上述第二部分的交界位置。隨後，在刪除表項時，獲取模塊502獲取待刪除的表項的前綴長度；查找模塊504在上述路由表中找到與上述前綴長度對應的第二表項空間；刪除模塊(未示出)刪除上述第二表項空間中與上述待刪除的表項對應的資源。根據本發明，預先根據高斯分布模型為路由表中各個前綴長度的表項空間分配資源，在插入表項的過程中採用最鄰近法則來尋找空閒的資源，並且在刪除表項的過程中直接回收資源不做搬移操作。在這些策略基礎上建立的路由表管理系統在實際網絡應用中具有較高的性能和自適應能力，並減少了所佔用的資源和花費的時間。需要說明的是，在附圖的流程圖示出的步驟可以在諸如一組計算機可執行指令的計算機系統中執行，並且，雖然在流程圖中示出了邏輯順序，但是在某些情況下，可以以不同於此處的順序執行所示出或描述的步驟。顯然，本領域的技術人員應該明白，上述的本發明的各模塊或各步驟可以用通用的計算裝置來實現，它們可以集中在單個的計算裝置上，或者分布在多個計算裝置所組成的網絡上，可選地，它們可以用計算裝置可執行的程序代碼來實現，從而，可以將它們存儲在存儲裝置中由計算裝置來執行，或者將它們分別製作成各個集成電路模塊，或者將它們中的多個模塊或步驟製作成單個集成電路模塊來實現。這樣，本發明不限制於任何特定的硬體和軟體結合。以上所述僅為本發明的優選實施例而已，並不用於限制本發明，對於本領域的技術人員來說，本發明可以有各種更改和變化。凡在本發明的精神和原則之內，所作的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。1權利要求一種路由表的管理方法，其特徵在於，包括獲取待插入路由表的表項的前綴長度，其中，在所述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源；在所述路由表中找到與所述前綴長度對應的第一表項空間；將所述待插入的表項插入到所述第一表項空間內的空閒資源中。2.根據權利要求1所述的方法，其特徵在於，所述將所述表項插入到所述第一表項空間內的空閒資源中包括如果所述第一表項空間中存在空閒的資源，則確定所述第一表項空間在所述路由表中的位置，並按照確定的位置對應的方向查找空閒的資源，將所述表項插入到所查找到的第一個空閒的資源中，其中，所述位置包括第一部分和第二部分，所述第一部分對應於第一方向，所述第二部分對應於第二方向，且所述第一方向和所述第二方向相反。3.根據權利要求2所述的方法，其特徵在於，其中，根據所述高斯分布模型的均值將所述路由表劃分成所述第一部分和所述第二部分。4.根據權利要求2所述的方法，其特徵在於，所述將所述表項插入到所述第一表項空間內的空閒資源中包括如果所述第一表項空間不存在空閒的資源，則判斷與所述第一表項空間相鄰的表項空間是否存在空閒資源；在與所述第一表項空間相鄰的表項空間存在空閒資源的情況下，選擇一個存在空閒資源的表項空間；在所述選擇出的表項空間中沿該表項空間的位置對應的方向查找空閒資源；將所查找出的最一個空閒資源標識為所述第一表項空間的空閒資源，並將所述表項插入到該空閒資源中。5.根據權利要求4所述的方法，其特徵在於，所述選擇一個存在空閒資源的表項空間包括在與所述第一表項空間相鄰的表項空間中選擇空閒資源數目最多的表項空間。6.根據權利要求4所述的方法，其特徵在於，所述將所述表項插入到所述第一表項空間中空閒的資源還包括如果與所述第一表項空間相鄰的表項空間中都不存在空閒資源，則選擇與所述第一表項空間最近的、且存在空閒資源的表項空間；在所述選擇出的表項空間中沿該表項空間的位置對應的方向查找到最後一個空閒資源；將與所述第一表項空間最鄰近的、且與所述選擇的表項空間位於同一側的一個表項搬移到所查找到的最後一個空閒資源中，將該表項所對應的資源標記為所述第一表項空間的空閒資源，並將待插入的表項插入到該空閒資源中。7.根據權利要求6所述的方法，其特徵在於，所述選擇與所述第一表項空間最近的、且存在空閒資源的表項空間包括選擇與所述第一表項空間最近的、且存在空閒資源最多的表項空間。8.根據權利要求2至7中任一項所述的方法，其特徵在於，所述第一方向與所述第二方向均指向所述第一部分與所述第二部分的交界位置。9.根據權利要求2至7中任一項所述的方法，其特徵在於，所述方法還包括在刪除表項時，獲取待刪除的表項的前綴長度；在所述路由表中找到與所述前綴長度對應的第二表項空間；刪除所述第二表項空間中與所述待刪除的表項對應的資源。10.—種路由表的管理裝置，其特徵在於，包括獲取模塊，用於獲取待插入路由表的表項的前綴長度，其中，在所述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源；查找模塊，用於在所述路由表中找到與所述前綴長度對應的第一表項空間；插入模塊，用於將所述待插入的表項插入到所述第一表項空間內的空閒資源中。11.根據權利要求10所述的裝置，其特徵在於，所述裝置還包括分配模塊，用於根據高斯分布模型為各個前綴長度的表項空間分配資源。全文摘要本發明公開了一種路由表的管理方法和裝置，其中，該路由表的管理方法包括獲取待插入路由表的表項的前綴長度，其中，在上述路由表中，根據高斯分布模型為各個前綴長度的表項空間分配資源；在上述路由表中找到與上述前綴長度對應的第一表項空間；將上述待插入的表項插入到上述第一表項空間內的空閒資源中。根據本發明，預先根據高斯分布模型為路由表中各個前綴長度的表項空間分配資源，在插入表項的過程中採用最鄰近法則來尋找空閒的資源，並且在刪除表項的過程中直接回收資源不做搬移操作。在這些策略基礎上建立的路由表管理系統在實際網絡應用中具有較高的性能和自適應能力，並減少了所佔用的資源和花費的時間。文檔編號H04L29/06GK101692653SQ20091017875公開日2010年4月7日申請日期2009年9月25日優先權日2009年9月25日發明者吳霞,尹旺中,徐雲川申請人:中興通訊股份有限公司