路由查找裝置的製作方法
2023-10-29 14:42:32 1
專利名稱：路由查找裝置的製作方法
技術領域：
本發明涉及路由查找技術，更具體的說，本發明涉及一種應用於IPv6網絡中的路由查找裝置。
背景技術：
互連網協議路由轉發表線速查表技術是核心骨幹路由器關鍵技術之一。路由查找是指對每個到達的IP報文根據其目的IP位址確定其應轉發的輸出埠號和下一跳地址。為提高IPv4地址空間的利用率，減緩路由表中表項的增長速度，Internet工作組IETF在1993年提出了無類域間路由(ClasslessInter-domain Routing-CIDR)技術，地址前綴長度可為不超過IPv4地址寬度的任意長度。變長地址前綴的採用使得IP位址的層次性分配成為可能，但在路由轉發表查表時就有可能找到多個匹配的路由表項，因此需要在所有匹配的表項中選擇地址前綴長度最大的表項作為最終的查找結果，即進行最長前綴匹配(LPM-Longest Prefix Match)。
目前，隨著網絡規模不斷增長和服務質量的需求，網際網路逐漸向以IPv6網絡互聯協議為基礎的新一代網際網路過渡。IPv6與IPv4相比，在地址格式上發生了很大改變，地址長度由原來的32位變成了128位，在地址分配上也進行了改進。儘管IPv6的地址結構與IPv4相比有許多不同之處，但整個地址空間還是層次性結構，仍然存在類似於IPv4CIDR地址結構下的路由合併，IPv6路由查找同樣採用LPM，但隨著IPv6地址寬度的增加使得最長前綴匹配問題變得更加突出。隨著鏈路速度的提高和IPv6的應用，LPM日益成為實現IPv6高速路由查表線速轉發的瓶頸。
對IPv6骨幹路由器而言，查找速率、表項更新速度、查找連續性和更新預處理複雜性是衡量路由查找方法的最重要的性能指標。雖然人們提出了許多針對IPv4的路由查找算法，但不適應IPv6骨幹路由器的轉發需求。比如，即使採用搜索次數較少的對前綴長度的二分搜索算法，一次IPv6路由查找需要多達7步搜索，且因存在回溯問題難以硬體實現。
目前已有的支持IPv6快速路由查找的技術是單級內容可尋址存儲器(TCAM，Ternary Content Addressable Memory)方案。其採用的技術方案是採用單級TCAM存儲前綴，將前綴對應的輸出埠號和下一跳地址存儲在靜態隨機存取存儲器(SRAM)中。查表時將目的IP位址送入TCAM，TCAM將匹配項的最低地址輸出(優先編碼)作為後續查表索引，據此從SRAM中讀出相應的輸出埠號和下一跳地址，即為最長前綴匹配結果。由於實際應用中路由表項需要不斷更新，表項更新會中斷查表流程，而TCAM僅簡單地將地址最低的匹配表項的存儲地址作為結果(索引)輸出，所以要保障最長前綴匹配，表項的存儲必須按前綴長度相對存儲地址降序排列，因而一個表項插入TCAM有時需要數十次維序操作，即中斷路由查找流程數十次，不僅影響路由表項的及時更新，也使查表連續性能大幅下降。
為了克服所述缺點，現有技術採用減少按序插入表項所需的表項移動次數來進一步提高表項更新速度，雖對路由更新的平均效率有所改進，但預處理操作複雜，最差情況下更新開銷大。
發明內容
本發明解決的技術問題是提供一種快速更新表項的路由查找裝置。採用所述裝置，表項存儲不需要排序，一個表項更新只中斷路由查找流程一次，路由查找連續性強，且不需要表項更新預處理。
為解決上述問題，本發明的路由查找裝置，包括
第一級TCAM，用於根據16個地址長度範圍劃分的存儲區分別存儲相應的擴展為64位的IPv6地址前綴的轉發表，路由查找時，根據輸入的待查找地址進行最長前綴匹配，然後輸出第一最長前綴匹配結果I1；第一比較器，與所述第一級TCAM相連，用於將所述第一最長前綴匹配結果與第一界值比較，輸出第一附加前綴Q1；第二級TCAM，與所述第一比較器相連，用於根據4個地址長度範圍劃分以及增加相應的附加前綴的存儲區分別存儲相應的擴展為64位的IPv6地址前綴的轉發表，路由查找時，根據輸入的所述第一附加前綴Q1和待查找地址進行最長前綴匹配，然後輸出第二最長前綴匹配結果I2；第二比較器，與所述第二TCAM相連，用於將所述第二最長前綴匹配結果I2與第二界值比較，輸出第二附加前綴Q2；第三級TCAM，與所述第二比較器相連，用於1個地址長度範圍劃分以及增加相應的附加前綴的存儲區分別存儲相應的擴展為64位的IPv6地址前綴的轉發表，路由查找時，根據輸入的所述第一、第二附加前綴Q1、Q2和待查找地址進行最長前綴匹配，然後輸出第三最長前綴匹配結果I3；SRAM，與所述第三級TCAM相連，用於保存對應最長前綴匹配結果的轉發路由信息，路由查找時，根據所述第三最長前綴匹配結果I3輸出相應的轉發路由信息。
其中，所述第一級TCAM設置為5個存儲區，分別為S11存儲區、空表項區、S12存儲區、空表項區、S13存儲區，其中S11存儲區、S12存儲區和S13存儲區按照16個地址長度範圍劃分；所述第二級TCAM設置為5個存儲區，分別為S21存儲區、空表項區、S22存儲區、空表項區、S23存儲區，其中S21存儲區、S22存儲區和S23存儲區按照4個地址長度範圍劃分，且每4個地址長度範圍對應一個第一附加前綴；
所述第三級TCAM設置為7個存儲區，分別為S31存儲區、空表項區、S32存儲區、空表項區、S33存儲區、空表項區、S34存儲區，其中S31存儲區、S32存儲區、S33和S34存儲區按照1個地址長度範圍劃分，且每1個地址長度範圍對應一個第一及相應第二附加前綴。
其中，所述第一比較器輸入的第一界定值包括3個界定量位於S11存儲區和S12存儲區之間空表項區中的空表項地址b11、位於S12存儲區和S13存儲區之間空表項區中的空表項地址b12、最高存儲地址b13，第一附加前綴Q1包括4個可選的比較結果若I1＜b11 則Q1＝11；若b11＜I1＜b12則Q1＝10；若b12＜I1＜b13則Q1＝01；若I1＝b13 則Q1＝00；Q1作為第三級TCAM輸入的附加前綴的第1、2位。
第二比較器的第二界定值包括3個界定量位於S21存儲區和S22存儲區之間空表項區中的某一空表項地址b21、位於S22存儲區和S23存儲區之間空表項區中的某一空表項地址b22、最高存儲地址b23；第二附加前綴Q2包括4個可選的比較結果若I2＜b21 則Q2＝11；若b21＜I2＜b22則Q2＝10；若b22＜I2＜b23則Q2＝01；若I2＝b23 則Q2＝00Q2作為第三級TCAM輸入的附加前綴的第3、4位。
其中，採用奇擴偶方式或分布擴展方式將128位IPv6地址長度範圍擴展為64位地址長度範圍。
其中，轉發表更新時，當需更新的表項T到來時，第一拍將T送入第一級TCAM，第二拍將T送入第二級TCAM並將第一級TCAM轉為路由查找狀態，第三拍將T送入第三級TCAM並將第二級TCAM轉為路由查找狀態，第四拍將第三級TCAM轉為路由查找狀態。
與現有技術相比，本發明具有以下有益效果1、表項存儲不需要排序，表項更新速度快；現有技術單級TCAM路由查找方法則需要對表項排序，表項更新速度慢，本發明由於各級TCAM的各存儲區內的前綴存儲不需考慮長度順序，所以可進行快速表項更新。
2、一個表項更新只中斷路由查找流程一次，路由查找連續性強；現有技術單級TCAM路由查找方法則需要對表項排序，排序過程中要進行多次表項移動，每移動一次表項要中斷一次路由查找流程，其查找連續性差，本發明由於各級TCAM的各存儲區內的前綴存儲不需考慮長度順序，所以一個表項更新只需中斷路由查找流程一次。
3、不需要表項更新預處理。
現有技術單級TCAM路由查找方法，為提高減少表項排序過程中對表項的移動次數，需要複雜的表項更新預處理，本發明由於各級TCAM的各存儲區內的前綴存儲不需考慮長度順序，所以一個表項更新時只需直接存入確定的存儲區域，所以不需要表項更新預處理。
圖1是本發明路由查找裝置實施例組成示意圖；圖2是本發明三級流水結構存儲示意圖。
具體實施例方式
本發明的路由查找裝置採用三級流水操作實現路由查找，通過將轉發表經前綴擴展後再逐級四分，加上不同長度的附加前綴後存儲在對應的存儲區內。由於各存儲區內的前綴存儲可避免表項存儲排序，因此，可提高表項更新速度。
所述存儲區可採用公知的TCAM通用器件實現，下面以具體實施例進行說明。
圖1是本發明路由查找具體實施例組成示意圖。
本發明中採用3級流水操作進行路由查找，流水查找結構自左至右分別為第一級、第二級、第三級。第一、二級分別由一個TCAM和一個比較器組成，第三級為一個TCAM，後接存儲下一跳地址的SRAM。
第一級TCAM從低地址到高地址劃分為5個存儲區域，5個存儲區域分別為S11存儲區、空表項區、S12存儲區、空表項區、S13存儲區；第二級TCAM從低地址到高地址劃分為5個存儲區域，5個存儲區域分別為S21存儲區、空表項區、S22存儲區、空表項區、S23存儲區；第三級TCAM從低地址到高地址劃分為7個存儲區域，7個存儲區域分別為S31存儲區、空表項區、S32存儲區、空表項區、S33存儲區、空表項區、S34存儲區。
表一是本發明比較器運算規則。
比較器運算規則
表一本發明中所述第一比較器和第二比較器採用相同的比較器運算規則，比較器有四個輸入量，一個輸出量。
第一比較器的四個輸入量分別是位於S11存儲區和S12存儲區之間空表項區中的某一空表項地址b11、位於S12存儲區和S13存儲區之間空表項區中的某一空表項地址b12、最高存儲地址b13、第一級TCAM輸出的當前匹配結果I1(即第一最長前綴匹配結果)。其中b11、b12和b13作為界定值(即第一界定值)，一個輸出量是2比特的比較結果Q1作為第一附加前綴。
其中第一比較器的運算規則參考表一所示，根據以下規則輸出Q1若I1＜b11 則Q1＝11；若b11＜I1＜b12則Q1＝10；若b12＜I1＜b13則Q1＝01；若I1＝b13 則Q1＝00Q1作為第二級、第三級TCAM輸入的附加前綴的第1、2位。
第二比較器的四個輸入量分別是位於S21存儲區和S22存儲區之間空表項區中的某一空表項地址b21、位於S22存儲區和S23存儲區之間空表項區中的某一空表項地址b22、最高存儲地址b23、第二級TCAM輸出的當前匹配結果I2(即第二最長前綴匹配結果)。其中b21、b22和b23作為界定值(即第二界定值)，一個輸出量是2比特的比較結果Q2作為第二附加前綴。
同樣的，所述第二比較器的運算規則參考圖2所示，根據以下規則輸出Q2若I2＜b21 則Q2＝11；若b21＜I2＜b22則Q2＝10；若b22＜I2＜b23則Q2＝01；若I2＝b23 則Q2＝00
Q2作為第三級TCAM輸入的附加前綴的第3、4位。
這樣，根據輸入的所述第一、第二附加前綴Q1、Q2和待查找地址進行最長前綴匹配，然後輸出第三最長前綴匹配結果I3，即最終的最長前綴匹配結果，由所述第三最長前綴匹配結果I3即可通過SRAM查找輸出相應的轉發路由信息。
需要說明的是，為實現上述的3級流水操作，本發明中採用前綴擴展，即將IPv6的地址長度數目由128個減少為64個。前綴擴展可採用方法較多，本實施例僅介紹兩種比較簡單的方法，第一種是奇擴偶方式。即奇數長度前綴擴展1位後成為偶數長度前綴，例如範圍有兩個長度的前綴0110011/7，10111000/8，奇偶擴展後為01100110/8，01100111/8，10111000/8，只有一個長度了；第二種是分布擴展方式，即根據對轉發表中前綴長度的分布情況做不同的擴展。若某長度的前綴出現的頻率高，則不擴或少擴；若某些長度的前綴出現的頻率低則多擴。原前綴擴展後含有64個不同長度，64個長度分別按遞增順序標識為01～64，作為三級流水處理的前綴長度。
第一、二、三級TCAM的最高地址存儲相同的前綴統配符「*」_第一、二、三級TCAM除最高地址的其它存儲區存儲不同的、確定的前綴長度範圍和附加前綴，各存儲區內的前綴存儲不需考慮長度順序。
第一級TCAM存儲的前綴長度範圍和附加前綴分別是S13[17，32]S12[33，48]S11[49，64]第二級TCAM存儲的前綴長度範圍和附加前綴分別是S2300
、01[21，24]、10[37，40]、11[53，56]S2200
、01[25，28]、10[41，44]、11[57，60]S2100[13，16]、01[29，32]、10[45，48]、11[61，64]
第三級TCAM存儲的前綴長度範圍和附加前綴分別是S340000
、0100[17]、1000[33]、1100[49]、0001
、0101[21]、1001[37]、1101[53]、0010
、0110[25]、1010[41]、1110[57]、0011[13]、0111[29]、1011[45]、1111[61]S330000
、0100[18]、1000[34]、1100[50]、0001
、0101[22]、1001[38]、1101[54]、0010[10]、0110[26]、1010[42]、1110[58]、0011[14]、0111[30]、1011[46]、1111[62]S320000
、0100[19]、1000[35]、1100[51]、0001
、0101[23]、1001[37]、1101[55]、0010[11]、0110[27]、1010[43]、1110[59]、0011[15]、0111[31]、1011[47]、1111[63]S310000
、0100[20]、1000[36]、1100[52]、0001
、0101[24]、1001[40]、1101[56]、0010[12]、0110[28]、1010[44]、1110[60]、0011[16]、0111[32]、1011[48]、1111[64]下面說明路由查找過程第一、二、三級TCAM進行同步流水查找操作。當目的IPv6地址P到來時，第一拍直接送入第一級TCAM，第二拍將第一級TCAM輸出的結果送給第一比較器，第三拍將第一比較器產生的結果加在地址P前一同輸入給第二級TCAM，第四拍將第二級TCAM輸出的結果送給第二比較器，第五拍將第一比較器和第二比較器產生的結果加在P前一同輸入給第三級TCAM，第六拍將第三級TCAM的輸出送入SRAM，從中得到下一跳地址。
當需要更新表項時，可根據以下過程進行1、2、3級TCAM進行同步流水更新操作。當需更新的表項T到來時，第一拍將T送入第一級TCAM，第二拍將T送入第二級TCAM並將第一級TCAM轉為路由查找狀態，第三拍將T送入第三級TCAM並將第二級TCAM轉為路由查找狀態，第四拍將第三級TCAM轉為路由查找狀態。
綜上，本發明通過第一級TCAM將目的地址P的最長前綴匹配項所在的長度範圍由最初的64縮小為16，即將匹配項存在的範圍縮小至原範圍的1/4，比如可能是長度最短的範圍[1，16]，或次短的範圍[17，32]，或較長的範圍[33，48]，或最長的範圍[49，64]。然後由第一比較器判斷目的地址P的最長前綴匹配項所在的長度範圍。判斷的過程是用第一級TCAM的輸出(一個前綴/表現的存儲地址，確切地說是所有與P匹配的前綴中，存儲地址最小的那個前綴的存儲地址。這一功能是TCAM的基本功能)、與範圍S11與S12間空表項區的一個存儲地址、範圍S12與S13間空表項區的一個存儲地址、最高存儲地址比較，第一比較器產生4個不同的比較結果，對應指示四個不同的範圍，然後將比較結果送給第二級TCAM，第二級TCAM據此知道在哪個1/4範圍內繼續查找。例如，若第一比較器輸出11，則對應的範圍是[49，64]。
同理，第二級TCAM將目的地址P的最長前綴匹配項所在的長度範圍由最初的16縮小為4，即將匹配項存在的範圍縮小至原範圍的1/4，比如對範圍[49，64]，可能是長度最短的範圍[49，52]，或次短的範圍[53，56]，或較長的範圍[57，60]，或最長的範圍[61，64]。然後第二比較器進一步判斷目的地址P的最長前綴匹配項所在的長度範圍。判斷的過程是用第二級TCAM的輸出(一個前綴/表現的存儲地址，確切地說是所有與P匹配的前綴中，存儲地址最小的那個前綴的存儲地址。這一功能是TCAM的基本功能)、與範圍S21與S22間空表項區的一個存儲地址、範圍S22與S23間空表項區的一個存儲地址、最高存儲地址比較。第二比較器產生4個不同的比較結果，對應指示四個不同的範圍，比較結果送給第三級TCAM，結合第一級TCAM輸出的結果，第三級TCAM據此知道在哪個1/4範圍內繼續查找。例如，若第二比較器輸出00，則對應的範圍是[49，52]。
最後由第三級TCAM確定最終的最長匹配結果，例如將範圍[49，52]進一步縮小至原範圍的1/4。此時其輸出就是最長前綴匹配項的存儲地址了，最後據此從SRAM中取出下一跳地址。
以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域的普通技術人員來說，在不脫離本發明原理的前提下，還可以作出若干改進和潤飾，這些改進和潤飾也應視為本發明的保護範圍。
權利要求
1.一種路由查找裝置，用於IPv6網絡中，其特徵在於，包括第一級內容可尋址存儲器，用於根據16個地址長度範圍劃分的存儲區分別存儲相應的擴展為64個地址長度範圍的IPv6地址前綴的轉發表，路由查找時，根據輸入的待查找地址進行最長前綴匹配，然後輸出第一最長前綴匹配結果I1；第一比較器，與所述第一級內容可尋址存儲器相連，用於將所述第一最長前綴匹配結果與第一界值比較，輸出第一附加前綴Q1；第二級內容可尋址存儲器，與所述第一比較器相連，用於根據4個地址長度範圍劃分以及增加相應的附加前綴的存儲區分別存儲相應的擴展為64個地址長度範圍的IPv6地址前綴的轉發表，路由查找時，根據輸入的所述第一附加前綴Q1和待查找地址進行最長前綴匹配，然後輸出第二最長前綴匹配結果I2；第二比較器，與所述第二級內容可尋址存儲器相連，用於將所述第二最長前綴匹配結果I2與第二界值比較，輸出第二附加前綴Q2；第三級內容可尋址存儲器，與所述第二比較器相連，用於1個地址長度範圍劃分以及增加相應的附加前綴的存儲區分別存儲相應的擴展為64個地址長度範圍的IPv6地址前綴的轉發表，路由查找時，根據輸入的所述第一、第二附加前綴Q1、Q2和待查找地址進行最長前綴匹配，然後輸出第三最長前綴匹配結果I3；靜態隨機存取存儲器，與所述第三級內容可尋址存儲器相連，用於保存對應最長前綴匹配結果的轉發路由信息，路由查找時，根據所述第三最長前綴匹配結果I3輸出相應的轉發路由信息。
2.根據權利要求1所述的路由查找裝置，其特徵在於，所述第一級內容可尋址存儲器設置為5個存儲區，分別為S11存儲區、空表項區、S12存儲區、空表項區、S13存儲區，其中S11存儲區、S12存儲區和S13存儲區按照16個地址長度範圍劃分；所述第二級內容可尋址存儲器設置為5個存儲區，分別為S21存儲區、空表項區、S22存儲區、空表項區、S23存儲區，其中S21存儲區、S22存儲區和S23存儲區按照4個地址長度範圍劃分，且每4個地址長度範圍對應一個第一附加前綴；所述第三級內容可尋址存儲器設置為7個存儲區，分別為S31存儲區、空表項區、S32存儲區、空表項區、S33存儲區、空表項區、S34存儲區，其中S31存儲區、S32存儲區、S33和S34存儲區按照1個地址長度範圍劃分，且每1個地址長度範圍對應一個第一及相應第二附加前綴。
3.根據權利要求2所述的路由查找裝置，其特徵在於，所述第一比較器輸入的第一界定值包括3個界定量位於S11存儲區和S12存儲區之間空表項區中的空表項地址b11、位於S12存儲區和S13存儲區之間空表項區中的空表項地址b12、最高存儲地址b13，第一附加前綴Q1包括4個可選的比較結果若I1＜b11 則Q1＝11；若b11＜I1＜b12 則Q1＝10；若b12＜I1＜b13 則Q1＝01；若I1＝b13 則Q1＝00；Q1作為第三級內容可尋址存儲器輸入的附加前綴的第1、2位。第二比較器的第二界定值包括3個界定量位於S21存儲區和S22存儲區之間空表項區中的某一空表項地址b21、位於S22存儲區和S23存儲區之間空表項區中的某一空表項地址b22、最高存儲地址b23；第二附加前綴Q2包括4個可選的比較結果若I2＜b21 則Q2＝11；若b21＜I2＜b22 則Q2＝10；若b22＜I2＜b23 則Q2＝01；若I2＝b23 則Q2＝00Q2作為第三級內容可尋址存儲器輸入的附加前綴的第3、4位。
4.根據權利要求1所述的路由查找裝置，其特徵在於，採用奇擴偶方式或分布擴展方式將128個IPv6地址長度範圍擴展為64個地址長度範圍。
5.根據權利要求1-4任一項所述的路由查找裝置，其特徵在於，轉發表更新時，當需更新的表項T到來時，第一拍將T送入第一級內容可尋址存儲器，第二拍將T送入第二級內容可尋址存儲器並將第一級內容可尋址存儲器轉為路由查找狀態，第三拍將T送入第三級內容可尋址存儲器並將第二級內容可尋址存儲器轉為路由查找狀態，第四拍將第三級內容可尋址存儲器轉為路由查找狀態。
全文摘要
本發明公開一種路由查找裝置，用於IPv6網絡中，該裝置主要包括三級內容可尋址存儲器以及位於第一級內容可尋址存儲器和第二級內容可尋址存儲器之間的第一比較器，第二級內容可尋址存儲器和第三級內容可尋址存儲器之間的第二比較器。本發明由於各級內容可尋址存儲器的各存儲區內的前綴存儲不需考慮長度順序，所以可進行快速表項更新。另一方面，一個表項更新只中斷路由查找流程一次，路由查找連續性強。
文檔編號G06F12/00GK1728676SQ20041007104
公開日2006年2月1日 申請日期2004年7月28日 優先權日2004年7月28日
發明者蘭巨龍, 王振興, 張興明, 於婧, 李雲濤 申請人:國家數字交換系統工程技術研究中心