劉宗寶，趙 鑫，張 力，李之乾，張 琨

(中國(guó)航天科工集團(tuán)第二研究院 七〇六所，北京 100854)

0 引 言

信息技術(shù)的發(fā)展推動(dòng)核心路由器的線速轉(zhuǎn)發(fā)率達(dá)到40 Gbps以上[1]，路由查找是核心路由器實(shí)現(xiàn)高性能線速轉(zhuǎn)發(fā)的關(guān)鍵技術(shù)。目前路由查找算法主要有軟件查找算法和硬件查找算法，基于軟件的路由查找方法需要多次內(nèi)存操作才能完成路由查找，無法滿足高速接口線速轉(zhuǎn)發(fā)的要求?；谟布穆酚刹檎宜惴ù蠖嗷赥CAM(ternary content addressable memory)[2-4]技術(shù)實(shí)現(xiàn)，執(zhí)行速度快，可以在一個(gè)時(shí)鐘周期內(nèi)完成路由表項(xiàng)的匹配查詢，優(yōu)先級(jí)編碼器(priority encoder，PE)從多個(gè)匹配結(jié)果中選擇最長(zhǎng)前綴匹配(longest prefix match，LPM)作為查找結(jié)果，因此TCAM特別適合于高性能路由器，實(shí)現(xiàn)快速路由查找和轉(zhuǎn)發(fā)。但是，傳統(tǒng)TCAM的更新性能較差[5]：路由表是動(dòng)態(tài)變化的并且規(guī)模大幅增長(zhǎng)，TCAM中路由表項(xiàng)按照前綴長(zhǎng)度降序排列，為保證路由表項(xiàng)的優(yōu)先級(jí)，對(duì)路由表項(xiàng)的插入、刪除等更新操作會(huì)造成大量的內(nèi)存移動(dòng)[6]，最壞情況下的更新算法復(fù)雜度為O(N)(N為TCAM中的路由表項(xiàng)數(shù)量)，導(dǎo)致路由查找性能大幅下降，無法滿足高性能路由器線速查找轉(zhuǎn)發(fā)的要求。

針對(duì)TCAM路由表項(xiàng)的更新算法國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究，提出了許多性能優(yōu)化的算法，參見文獻(xiàn)[7-9]等。PLO-OPT更新算法是對(duì)選擇移動(dòng)更新算法的改進(jìn)，即空閑前綴表項(xiàng)從TCAM的底部移動(dòng)到了TCAM的中間，因此一次更新操作最多需要L/2次(L是路由前綴的長(zhǎng)度)路由表項(xiàng)移動(dòng)。CAO_OPT更新算法把路由表轉(zhuǎn)化為trie樹，只對(duì)同一條鏈路(從根節(jié)點(diǎn)到葉子節(jié)點(diǎn))上的規(guī)則排序[10]，一次更新操作最多需要D/2次(D是相互重疊的前綴的最大個(gè)數(shù))路由表項(xiàng)移動(dòng)。目前大部分基于TCAM的路由表項(xiàng)更新算法都要求前綴表項(xiàng)按照前綴長(zhǎng)度排序，時(shí)間復(fù)雜度高，影響了路由查找更新性能。為滿足高性能路由器數(shù)據(jù)交換對(duì)快速路由查找功能的需求，本文提出了一種基于分組TCAM的T比特高性能路由器查找更新方法。

1 T比特高性能路由器系統(tǒng)架構(gòu)

T比特高性能路由器的系統(tǒng)架構(gòu)為分布轉(zhuǎn)發(fā)、集中控制，如圖1所示，主要由熱備份主控板、交換網(wǎng)板和多個(gè)接口業(yè)務(wù)板組成，各板之間通過高速背板總線互聯(lián)。主控板是T比特高性能路由器的核心，完成以太網(wǎng)數(shù)據(jù)包處理、網(wǎng)絡(luò)管理等功能，并為其它各板提供高精度的時(shí)鐘源。交換網(wǎng)板具有高性能交換芯片，完成T比特級(jí)的高速數(shù)據(jù)包轉(zhuǎn)發(fā)。接口業(yè)務(wù)板具有單獨(dú)的控制系統(tǒng)，支持IPv4、IPv6、MPLSVPN、Qos/H-Qos、GRE、組播VPN等全業(yè)務(wù)功能。

圖1 T比特高性能路由器系統(tǒng)架構(gòu)

2 基于分組TCAM的路由查找更新

2.1 路由查找更新架構(gòu)

本文提出的基于分組TCAM的路由查找更新架構(gòu)如圖2(a)所示，TCAM被分成幾組TCAM1～TCAMmax，每組內(nèi)各TCAM表項(xiàng)的前綴互不相交，即TCAMi,j∪TCAMi,k=Ф，因此TCAMi(i∈{1,max})是互不相交路由表項(xiàng)的集合，TCAMi中最多只有一個(gè)匹配前綴。max為路由表項(xiàng)前綴的最大長(zhǎng)度，根據(jù)網(wǎng)絡(luò)環(huán)境的不同可動(dòng)態(tài)變化。由于在執(zhí)行某項(xiàng)前綴的插入、刪除等更新操作時(shí)，不需要對(duì)其它前綴進(jìn)行操作，因此相比于傳統(tǒng)TCAM，本文提出的路由查找更新架構(gòu)的操作執(zhí)行速度更快，算法復(fù)雜度低，高性能路由器的查找轉(zhuǎn)發(fā)效率更高。本文提出的架構(gòu)中還有一個(gè)TCAMex為傳統(tǒng)TCAM結(jié)構(gòu)，用于存儲(chǔ)無法放在TCAMi中的路由表項(xiàng)。選擇邏輯基于最長(zhǎng)前綴匹配算法(LPM)實(shí)現(xiàn)。

圖2 基于分組TCAM的高性能路由器查找更新架構(gòu)

TCAMi(i∈{1,max})和TCAMex采用基于統(tǒng)計(jì)預(yù)測(cè)的預(yù)留表項(xiàng)空間設(shè)計(jì)，如圖2(b)所示，灰色部分表示預(yù)留的空間，預(yù)留空間大小由前綴的概率密度函數(shù)確定，對(duì)于TCAMi,前綴長(zhǎng)度為m的表項(xiàng)預(yù)留空間為ni[m]=NTCAM×pdf[m]/(max+1)，前綴為k的表項(xiàng)預(yù)留空間為ni[k]=NTCAM×pdf[k]/(max+1)，詳細(xì)計(jì)算過程在2.2.2節(jié)。通過基于統(tǒng)計(jì)預(yù)測(cè)的預(yù)留表項(xiàng)空間設(shè)計(jì)，有效減少了路由表項(xiàng)前綴的插入操作引起的其它表項(xiàng)的移動(dòng)，路由表項(xiàng)更新效率大幅提升。

2.2 路由查找更新算法

2.2.1 搜索算法

搜索算法基于最長(zhǎng)前綴匹配(LMP)搜索技術(shù)，具體實(shí)現(xiàn)過程為：對(duì)于TCAM1～TCAMmax，每個(gè)TCAMi獨(dú)立地并行執(zhí)行前綴匹配過程match(TCAMi, ip_addr)，其中ip_addr為目的IP地址。由于TCAMi中的前綴互不相交，因此每個(gè)TCAMi中最多搜索到一個(gè)與ip_addr匹配的前綴；然后從多個(gè)匹配的前綴中選擇entry[k].length值最大的前綴，相應(yīng)的entry[k]即為ip_addr的路由查找結(jié)果，并返回路由轉(zhuǎn)發(fā)表中相應(yīng)的輸出端口號(hào)(entry[k].outport)。如果所有TCAMi中沒有匹配的前綴，前綴長(zhǎng)度entry[i].length值為0，根據(jù)路由轉(zhuǎn)發(fā)表中默認(rèn)的表項(xiàng)信息進(jìn)行轉(zhuǎn)發(fā)。搜索算法的步驟如下：

Search(ip_addr)

(1) fori= 1 to ex

(2) entry[i] = match(TCAMi, ip_addr)

(3) endfor

(4) 對(duì)于滿足上述條件的路由表項(xiàng)entry[i](i∈{1,ex})， 根據(jù)LMP原則， 尋找k∈i， 使得entry[k]. length值最大

(5) return entry[k].outport

2.2.2 基于統(tǒng)計(jì)預(yù)測(cè)的預(yù)留表項(xiàng)空間算法

對(duì)于骨干網(wǎng)絡(luò)，路由表項(xiàng)前綴的統(tǒng)計(jì)特性變化較小。基于統(tǒng)計(jì)預(yù)測(cè)的預(yù)留表項(xiàng)空間算法根據(jù)高性能路由器的歷史表項(xiàng)數(shù)據(jù)，計(jì)算路由表項(xiàng)前綴的統(tǒng)計(jì)分布特性，進(jìn)行預(yù)留表項(xiàng)空間的預(yù)測(cè)和分配，當(dāng)有新的表項(xiàng)插入時(shí)，直接添加在預(yù)留空閑位置。算法步驟如下：

(2)計(jì)算長(zhǎng)度為i的前綴的總預(yù)留空間大小n[i]=NTCAM×pdf[i]；

(3)TCAMi中為長(zhǎng)度為i的前綴預(yù)留大小為n[i]=NTCAM×pdf[i]/(max+1)的空間，路由表項(xiàng)動(dòng)態(tài)更新時(shí)，新的路由表項(xiàng)直接插入預(yù)留空間內(nèi)。

2.2.3 插入算法

路由轉(zhuǎn)發(fā)表中插入一個(gè)新的路由表項(xiàng)(前綴為p)的過程如下Insert(p)函數(shù)所示。首先，從TCAMi～TCAMmax中尋找出前綴p可以插入的所有TCAMi(i∈{1,max})，要求前綴p與TCAMi中的任意前綴互不相交；如果存在滿足上述條件的TCAMi，并且TCAMi中至少有一個(gè)空閑表項(xiàng)位置，標(biāo)志變量available[i]值為true；否則，前綴p的預(yù)留空間被占用，available[i]值為false。如果available[i]值為true并且存在多個(gè)TCAMi，插入函數(shù)insert_to_tcam()從可用的TCAMi中隨機(jī)選擇一個(gè)插入位置；如果available[i]值為false，則TCAM0～TCAM6中不存在可用的空閑表項(xiàng)位置，前綴p插入傳統(tǒng)TCAMex。

insert_to_tcam()函數(shù)對(duì)傳統(tǒng)TCAMex的插入操作需要滿足傳統(tǒng)TCAM的順序約束，插入過程需要進(jìn)行多次的內(nèi)存移動(dòng)；而TCAM1～TCAMmax中的路由表項(xiàng)無順序約束，因此對(duì)TCAM1～TCAMmax的插入操作可在任意空閑位置執(zhí)行。

Insert(p)

(1) fori= 1 to max

(2) Initialize available[i] = false

(3) If(對(duì)于任意的前綴ep∈TCAMi，p和ep是不相交的， 并且TCAMi中有空余位置)

(4) available[i] = true

(5) endif

(6) endfor

(7) if(available[i] = false, 對(duì)于任意的0≤i≤max)

(8) insert_to_tcam(p, TCAMex)

(9) else

(10) 從available[i]中任意選取k， insert_to_tcam(p, TCAMk)

(11) endif

2.2.4 刪除算法

從轉(zhuǎn)發(fā)表中刪除前綴p的過程如下Delete(p)函數(shù)所示。首先，需要尋找哪個(gè)TCAM含有前綴p(假設(shè)為k)；然后，前綴可從TCAMk中刪除。對(duì)于TCAM1～TCAMmax，刪除過程不需要任何內(nèi)存移動(dòng)。對(duì)于傳統(tǒng)TCAM，內(nèi)存移動(dòng)次數(shù)因更新算法的不同而有差異；如果相鄰位置是空閑的，每次刪除過程需要至少一次前綴移動(dòng)操作。

Delete(p)

(1) 尋找k，使得p∈TCAMk

(2) delete_from(p, TCAMk)

3 實(shí)驗(yàn)驗(yàn)證與分析

為驗(yàn)證本文提出算法的性能，搭建了測(cè)試驗(yàn)證環(huán)境，如圖3所示，由T比特高性能路由器、Spirent網(wǎng)絡(luò)測(cè)試儀、以太網(wǎng)交換機(jī)、便攜式PC機(jī)等組成。其中網(wǎng)絡(luò)性能測(cè)試軟件使用Spirent公司的TestCenter STP-N11U，版本為v4.33.0086。

圖3 測(cè)試驗(yàn)證環(huán)境

本文采用IPMA的MAE-WEST和MAE-EAST[11,12]路由表作為仿真數(shù)據(jù)來源，見表1。

表1 仿真數(shù)據(jù)統(tǒng)計(jì)

圖4是數(shù)據(jù)1和數(shù)據(jù)2的前綴數(shù)量和內(nèi)存移動(dòng)次數(shù)關(guān)系，可以看出，96%的前綴只需要1次內(nèi)存移動(dòng)，僅有不到4%的前綴需要2次以上的內(nèi)存移動(dòng)。

圖4 前綴數(shù)量和內(nèi)存移動(dòng)次數(shù)關(guān)系

分別采用本文提出的算法以及經(jīng)典的PLO_OPT算法、CAO_OPT算法，計(jì)算MAE-WEST和MAE-EAST路由表每次更新操作(插入、刪除)的平均內(nèi)存移動(dòng)次數(shù)，結(jié)果見表2和表3。從對(duì)比結(jié)果可以看出，由于本文算法的路由表項(xiàng)沒有順序約束和優(yōu)先級(jí)編碼器，并且進(jìn)行了預(yù)留表項(xiàng)空間的設(shè)計(jì)，對(duì)于插入和刪除操作，本文算法的平均內(nèi)存移動(dòng)次數(shù)遠(yuǎn)小于PLO_OPT算法和CAO_OPT算法。由于傳統(tǒng)TCAMex的存在，本文算法的插入操作和刪除操作所需的平均內(nèi)存移動(dòng)次數(shù)不相同。需要指出，該算法以計(jì)算概率密度函數(shù)為代價(jià)，通過減少內(nèi)存移動(dòng)次數(shù)降低了路由表項(xiàng)更新的時(shí)間復(fù)雜度， 但相比于頻繁的內(nèi)存移動(dòng)操作，概率密度函數(shù)的計(jì)算復(fù)雜度較小。

表2 不同算法每次更新操作的平均內(nèi)存移動(dòng)次數(shù)(MAE-WEST)

表3 不同算法每次更新操作的平均內(nèi)存移動(dòng)次數(shù)(MAE-EAST)

對(duì)采用本文提出的算法的T比特高性能路由器的轉(zhuǎn)發(fā)性能(吞吐量、時(shí)延)進(jìn)行測(cè)試，測(cè)試中選用的數(shù)據(jù)包長(zhǎng)分別為64、128、256、512、1024、1280、1518，測(cè)試時(shí)間為30 s，端口流量負(fù)載為100%，網(wǎng)絡(luò)的轉(zhuǎn)發(fā)方式選擇Full meshed全雙工對(duì)發(fā)。運(yùn)行Spirent公司的TestCenter RF2544測(cè)試集，測(cè)試界面如圖5所示。

測(cè)試的T比特高性能路由器的吞吐量及時(shí)延分別如圖6、圖7所示。可以看出，在以上7種數(shù)據(jù)包大小時(shí)，路由器的測(cè)試吞吐量與理論最大吞吐量吻合，包大小為1518 bytes時(shí)可達(dá)最大80 Gbps的線速轉(zhuǎn)發(fā)，報(bào)文的丟包率為0。路由器的轉(zhuǎn)發(fā)時(shí)延最大為6.12 μs(包大小1518 bytes)。測(cè)試結(jié)果表明，本文提出的算法可有效提高T比特高性能路由器的線速查找轉(zhuǎn)發(fā)性能。

4 結(jié)束語

針對(duì)傳統(tǒng)TCAM查找更新方法時(shí)間復(fù)雜度高、效率低的問題，以及T比特路由器對(duì)高性能查找轉(zhuǎn)發(fā)的需求，本文提出了一種基于分組TCAM的路由查找更新架構(gòu)，TCAM被分成幾組互不相交的路由表項(xiàng)的集合，路由表項(xiàng)不需要按優(yōu)先級(jí)進(jìn)行排序；提出了基于統(tǒng)計(jì)預(yù)測(cè)的預(yù)留表項(xiàng)空間算法，預(yù)留空間大小由前綴的概率密度函數(shù)確定，根據(jù)歷史表項(xiàng)數(shù)據(jù)分配相應(yīng)的空間大小。搭建了測(cè)試驗(yàn)證環(huán)境，測(cè)試結(jié)果表明，基于本文設(shè)計(jì)的TCAM的內(nèi)存移動(dòng)次數(shù)有效降低，T比特高性能路由器可達(dá)最大80 Gbps的線速轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)時(shí)延最大為6.12 μs。因此，本文提出的基于分組TCAM的T比特高性能路由器查找更新技術(shù)，可有效提高T比特路由器的查找轉(zhuǎn)發(fā)性能，支撐未來網(wǎng)絡(luò)發(fā)展的需要。

圖5 TestCenter測(cè)試界面

圖6 包轉(zhuǎn)發(fā)吞吐量測(cè)試比較

圖7 系統(tǒng)轉(zhuǎn)發(fā)時(shí)延比較

由于T比特路由器的動(dòng)態(tài)變化特性，基于時(shí)變概率密度函數(shù)的預(yù)留表項(xiàng)空間算法是下一步的研究方向。