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