摘 要：現(xiàn)代核心路由器對(duì)查找速率、表項(xiàng)更新速度、查找表容量等提出越來越高的要求。目前工業(yè)廠商大多采用基于TCAM（三態(tài)內(nèi)容關(guān)聯(lián)存儲(chǔ)器）的解決方案。TCAM最大特點(diǎn)是查找速度快，但其更新算法會(huì)浪費(fèi)很大的存儲(chǔ)空間。針對(duì)這個(gè)問題該文提出一種利用FPGA提供硬件支持的路由更新方法，增加新表項(xiàng)時(shí)，只需對(duì)新增表項(xiàng)進(jìn)行一次預(yù)處理，轉(zhuǎn)發(fā)表無需按前綴長度排序，消除了預(yù)留空閑表項(xiàng)造成的存儲(chǔ)空間浪費(fèi)。 關(guān)鍵詞：路由器;三態(tài)內(nèi)容關(guān)聯(lián)存儲(chǔ)器;前綴 ;轉(zhuǎn)發(fā)表 1 前言 　　快速路由查找一直是一個(gè)熱門研究項(xiàng)目。近年來人們提出很多基于軟件[1]或硬件[2-5]的實(shí)現(xiàn)方法，隨著路由器接口速度的不斷提高，使用軟件方法實(shí)現(xiàn)高速路由查找已經(jīng)越來越困難了。目前工業(yè)界使用最多的硬件路由查找方法是使用TCAM。TCAM的優(yōu)點(diǎn)是它所保留的表項(xiàng)在長度要求上非常靈活，可以在同一個(gè)TCAM芯片中保存任意長度的關(guān)鍵字表項(xiàng)[6]，因此TCAM非常適用于最長前綴路由的查找。但由于TCAM僅簡單地將地址最低的匹配表項(xiàng)的存儲(chǔ)地址作為結(jié)果（索引）輸出，要保障最長前綴匹配，表項(xiàng)的存儲(chǔ)必須按前綴長度相對(duì)地址降序排列，即低地址存儲(chǔ)前綴較長的表項(xiàng)，高地址存儲(chǔ)前綴較短的表項(xiàng)。這種存儲(chǔ)順序關(guān)系使得TCAM的更新操作變得復(fù)雜。當(dāng)加入一條新的前綴表項(xiàng)時(shí)，為了能仍然保持表項(xiàng)間的順序關(guān)系，就需要移動(dòng)一些前綴表項(xiàng)。現(xiàn)有的針對(duì)IPV4的PLO-OPT算法（prefix length ordering constraint algorithm）[5]是目前處理TCAM表項(xiàng)更新的最優(yōu)算法。該算法從低地址到高地址，依次存放由長到短的不同長度前綴的表項(xiàng)，并將空閑的TCAM表項(xiàng)集中于前綴表項(xiàng)所存儲(chǔ)地址區(qū)的中間位置，構(gòu)成一個(gè)空閑池，如圖1。當(dāng)有新表項(xiàng)加入時(shí)則加入位置以上或以下的各表項(xiàng)依次向中間的空閑池移動(dòng)一個(gè)地址，以創(chuàng)建一個(gè)空閑空間。假設(shè)TCAM中存儲(chǔ)了N條路由信息，則空閑空間的大小必須保持在N/2個(gè)表項(xiàng)，這在具有幾十萬個(gè)表項(xiàng)的骨干路由器上顯然代價(jià)過高。 2 更新表項(xiàng)預(yù)處理 　　為了提高TCAM存儲(chǔ)空間利用率，我們希望表項(xiàng)更新時(shí)無關(guān)項(xiàng)能避免移動(dòng)，以消除構(gòu)造空閑池的必要。如果低地址的表項(xiàng)能確保不包含高地址表項(xiàng)即低地址表項(xiàng)的前綴不是高地 　　址表項(xiàng)前綴的前綴，則搜索TCAM得到的結(jié)果就一定是具有最長前綴匹配的表項(xiàng)。為了使低地址表項(xiàng)不包含高地址表項(xiàng)，本文提出如下算法： 　　1，構(gòu)建一個(gè)存放前綴長度的RAM，深度與TCAM一致，寬度為5位（適合IPV4），當(dāng)表項(xiàng)插入時(shí)將其前綴長度保存在RAM中，存放位置與其在TCAM的位置一致，以方便查詢。 　　2，以更新表項(xiàng)中的地址部分（更新表項(xiàng)以〈地址、掩碼〉序偶形式出現(xiàn)）為關(guān)鍵字對(duì)TCAM進(jìn)行讀操作。 　　3，若有匹配項(xiàng)存在，則根據(jù)TCAM輸出結(jié)果讀取存放在RAM中的前綴長度，設(shè)為a。若無匹配項(xiàng)則可將更新表項(xiàng)寫入TCAM中最后一個(gè)表項(xiàng)的下一個(gè)地址。 　　4，在存在匹配項(xiàng)的情況下，設(shè)更新表項(xiàng)前綴長度為b（b>=a恒成立）則將匹配表項(xiàng)擴(kuò)展為2b-a個(gè)子項(xiàng)。例：若TCAM中有表項(xiàng)01011＊（5位前綴）插入表項(xiàng)為0101110＊（7位前綴）則01011＊為匹配表項(xiàng)，并擴(kuò)展為0101100＊、0101101＊、0101110＊、0101111＊4個(gè)子項(xiàng)。 　　5，將生成子項(xiàng)作為關(guān)鍵字對(duì)TCAM進(jìn)行查找操作，若某個(gè)子項(xiàng)找到匹配項(xiàng)，則該子項(xiàng)即覆蓋匹配項(xiàng)的存儲(chǔ)位置，若無匹配項(xiàng)則存入TCAM中最后一個(gè)表項(xiàng)。子項(xiàng)插入列表的過程中可能出現(xiàn)多個(gè)子項(xiàng)匹配同一個(gè)表項(xiàng)的情況，但只需一個(gè)子項(xiàng)覆蓋匹配項(xiàng)即可，且不需要再次進(jìn)行匹配項(xiàng)擴(kuò)展，因?yàn)橐宰禹?xiàng)為關(guān)鍵字進(jìn)行查詢后的匹配結(jié)果一定出現(xiàn)在第一個(gè)匹配項(xiàng)的低地址位置，再次進(jìn)行擴(kuò)展后生成的子項(xiàng)必定被包含在上一次擴(kuò)展的結(jié)果中。 　　經(jīng)過上述預(yù)處理，即可確保更新表項(xiàng)不會(huì)被低地址中任何一個(gè)表項(xiàng)所包含。通過這種方式組成的TCAM路由表在更新時(shí)不需要為更新項(xiàng)騰出表項(xiàng)空間，從而可避免構(gòu)造空閑池造成的空間損失。 3 前綴預(yù)處理電路原理 　　圖2是預(yù)處理電路的結(jié)構(gòu)示意圖，更新表項(xiàng)在輸入接口中被分離為地址部分和掩碼部分。先將地址部分與取反后的掩碼相與，然后作為關(guān)鍵字送入TCAM中。若無匹配，則直接將更新表項(xiàng)寫入TCAM中，同時(shí)將掩碼譯碼后得到的前綴長度b存入RAM中相同的位置。若有匹配，則根據(jù)匹配結(jié)果從RAM中讀出相應(yīng)表項(xiàng)的前綴長度a,將a編碼成掩碼并取反然后與更新表項(xiàng)中的地址部分相與，這個(gè)值即是所生成的第一個(gè)子項(xiàng)。再以此值為基數(shù)，做2b-a-1次加1運(yùn)算即得到所有子項(xiàng)。最后將所有子項(xiàng)作為關(guān)鍵字，在TCAM中查找匹配項(xiàng)，若某個(gè)子項(xiàng)搜索到匹配項(xiàng)，則以該子項(xiàng)覆蓋匹配項(xiàng)，若某子項(xiàng)未搜索到匹配項(xiàng)，則將此子項(xiàng)寫入地址寄存器所指向的地址即TCAM中最后一個(gè)表項(xiàng)的下一個(gè)地址，然后將該地址加1后寫回地址寄存器（Datain是TCAM查找關(guān)鍵字的輸入端口，wrx是TCAM更新的寫入端口，address是輸入TCAM更新的地址端口，matchaddress、 matchfound是TCAM輸出端口,TCAM的其他端口未一一列出）。 　　其中控制狀態(tài)機(jī)通過對(duì)數(shù)據(jù)路徑的控制，決定整個(gè)電路運(yùn)行狀態(tài),其狀態(tài)轉(zhuǎn)移如圖3所示。初始為idle狀態(tài);當(dāng)有更新表項(xiàng)到達(dá)時(shí)，狀態(tài)由idle進(jìn)入lookup1，在這個(gè)狀態(tài)下將更新表項(xiàng)的地址部分釋放到TCAM的datain端口進(jìn)行匹配查找;如果matchfound=0,表明無匹配項(xiàng)則進(jìn)入renew1狀態(tài)，釋放更新項(xiàng)到TCAM的wrx端口、釋放地址寄存器中的地址（初始化時(shí)寫入的TCAM中最后一個(gè)路由表項(xiàng)的地址）到TCAM的address端口;然后進(jìn)入writeram1狀態(tài)，將ram置為寫狀態(tài)，釋放地址寄存器中的地址到ram的addr端口，將前綴長度寫入ram中;若matchfound=1，表明存在匹配項(xiàng)，則進(jìn)入readram狀態(tài)，這個(gè)狀態(tài)下將ram置為讀狀態(tài)，釋放matchaddress到ram的addr端口讀出匹配項(xiàng)前綴長度a;然后進(jìn)入judge狀態(tài)，判斷2b-a-n是否為0，且將n加1;若2b-a-n不為0，則進(jìn)入lookup2狀態(tài)，否則進(jìn)入idle狀態(tài);lookup2狀態(tài)釋放生成的子項(xiàng)到TCAM的data端口進(jìn)行匹配查詢;若matchfound=1,則進(jìn)入renew2狀態(tài)否則進(jìn)入renew3狀態(tài);renew2狀態(tài)下控制狀態(tài)機(jī)釋放生成的子項(xiàng)到TCAM的wrx端口，釋放matchaddress到TCAM的address端口（生成的子項(xiàng)將覆蓋匹配項(xiàng)）;renew2狀態(tài)后進(jìn)入writeram2狀態(tài)，置ram為寫狀態(tài)，釋放matchaddress到ram的address端口（ram中這個(gè)地址的前綴長度將被改寫）;writeram2狀態(tài)后進(jìn)入judge狀態(tài)，繼續(xù)判斷;若進(jìn)入remew3狀態(tài)，狀態(tài)機(jī)釋放子項(xiàng)到TCAM的wrx端口，釋放地址寄存器中的地址到TCAM的address端口;接著進(jìn)入writeram3狀態(tài)，置ram為寫狀態(tài)，釋放地址寄存器中地址到ram的addr端口，并將地址寄存器中的數(shù)加1;隨后進(jìn)入judge狀態(tài)，繼續(xù)判斷。 4 用FPGA實(shí)現(xiàn)前綴預(yù)處理電路 　　隨著當(dāng)前互聯(lián)網(wǎng)的快速發(fā)展，路由器的端口速率從OC3（155.52Mbps）、OC12（622.08Mbps）、OC48（2.448Gbps）到OC192（10Gbps），甚至OC768（40Gbps）。路由器內(nèi)部對(duì)路由更新的處理速度也必須越來越快。本文中提出的前綴預(yù)處理電路做為路由器中的輔助設(shè)備同樣需要滿足一定的數(shù)據(jù)處理速度。FPGA由于具有速率高、面積小、性能可靠、費(fèi)用低廉且可移植性強(qiáng)等特點(diǎn)，成為高速數(shù)字電路設(shè)計(jì)的首選方案，本文即采用FPGA實(shí)現(xiàn)前綴預(yù)處理電路的設(shè)計(jì)。 　　設(shè)計(jì)中所用的硬件描述語言是Verilog HDL，在ModelSimXE5.7下進(jìn)行編譯仿真，綜合工具是Synplicity公司專用于FPGA/CPLD的邏輯綜合工具Synplify pro7.1。選用的器件是Xilinx公司的Virtex2系列，型號(hào)XC2V500，速度-6，封裝FG256。電路的描述語言編譯完成后，通過頂層文件建立一個(gè)測試平臺(tái)，平臺(tái)中包括預(yù)處理電路模塊、信號(hào)源模塊以及TCAM模塊，其中預(yù)處理電路模塊是可綜合的，信號(hào)源模塊和TCAM模塊是行為級(jí)虛擬模塊不可綜合為門級(jí)網(wǎng)表。仿真時(shí)，信號(hào)源模塊向預(yù)處理電路輸入需要更新的路由表項(xiàng)（地址/掩碼序偶），經(jīng)預(yù)處理電路處理后生成新的更新項(xiàng)（原前綴或者原前綴擴(kuò)展子項(xiàng)）并輸出到TCAM模塊中。TCAM模塊中路由前綴存放于存儲(chǔ)器中，仿真前存儲(chǔ)器本身無路由信息，仿真時(shí)首先需要通過$readmemb系統(tǒng)命令從本地磁盤中讀入一個(gè)路由表。如圖4是表項(xiàng)擴(kuò)展的仿真波形，由圖可見輸入的更新表項(xiàng)被擴(kuò)展為4個(gè)子項(xiàng)，其中有2個(gè)子項(xiàng)也在TCAM中查詢到匹配項(xiàng)。功能仿真和綜合后仿真通過后，使用Xilinx公司的布局布線工具ISE5.2對(duì)前綴預(yù)處理電路進(jìn)行布局布線。過程中采用的約束頻率為80MHz。由ISE靜態(tài)時(shí)序分析報(bào)告可知，所有路徑都滿足80MHz的約束。布局布線完成后，在ModelSim中將標(biāo)準(zhǔn)延時(shí)文件反標(biāo)注到仿真模型上，通過施加各種情況的激勵(lì)仿真可知，預(yù)處理電路完全符合設(shè)計(jì)要求。 結(jié)論 　　本文作者創(chuàng)新點(diǎn)：通過對(duì)更新的路由表項(xiàng)進(jìn)行預(yù)處理，保證了更新表項(xiàng)不被低地址的表項(xiàng)所包含，無需將所有表項(xiàng)按前綴長度排列，從而可避免POL-OPT算法中保持一個(gè)深度為N/2的空閑池的做法，節(jié)約了寶貴的TCAM存儲(chǔ)空間。整個(gè)電路方案合理可行，最高運(yùn)行頻率可達(dá)到80MHz。 參考文獻(xiàn) 　　[1]Miguel A, Ruiz-sanchez Survey and taxonomy of IP address lookup algorithms[J],IEEE Network,2001,（2）8-23 　　[2] Pankaj Gupta, Steven Lin, and Nick McKeown. Routing lookups in hardware at memory access speeds[A]. IEEE NFOCOM [C]. San Franciso: Prentice Hall,1998 1240-1247. 　　[3]Mcauley A J , Francis P. Fast routing table lookup using CAMs[A]. Proc IEEE NFOCOM[C] San Franciso.Prentice Hall, 1993.1382-1391. 　　[4] Kobayashi M, Murase T, Kuriyama A. A longest prefix match search engine for multi-gigabit IP processing [A]. Proceedings of ICC 2000[C]. New York: Cannes Hall, 2000 834-842 　　[5]Devavrat Shah, Pankaj Gupta Fast updating algorithms for TCAMs [J]. IEEE Micro, 2001, （1）:36-47. 　　[6]屠振,梁進(jìn)山,楊奎武.TCAM在高速度路由查找中的應(yīng)用及其FPGA實(shí)現(xiàn)[J].微計(jì)算機(jī)信息,2005,21（4）:208-209.