基于集合分割的虛擬路由器轉(zhuǎn)發(fā)表查找的實現(xiàn)*

胡 穎，莊 雷

（1.鄭州大學(xué)信息工程學(xué)院 鄭州 450001；2.商丘師范學(xué)院計算機與信息技術(shù)學(xué)院 商丘 476000）

1 引言

虛擬網(wǎng) （virtual network）是指在一個實際基底網(wǎng)絡(luò)（substrate network）基礎(chǔ)設(shè)施上構(gòu)建多個相互隔離的并行網(wǎng)絡(luò)切片（slice），每個網(wǎng)絡(luò)切片運行一個具有不同體系結(jié)構(gòu)的虛擬化網(wǎng)絡(luò)。虛擬網(wǎng)是一種有應(yīng)用前景的網(wǎng)絡(luò)結(jié)構(gòu)，可以在不用改變網(wǎng)絡(luò)正常操作的情況下，支持協(xié)作、訂制路由、新網(wǎng)絡(luò)協(xié)議的實驗和部署?；诰W(wǎng)絡(luò)虛擬化的未來互聯(lián)網(wǎng)技術(shù)不僅支持新體系結(jié)構(gòu)、新協(xié)議和新算法，還應(yīng)兼容基于TCP/IP的互聯(lián)網(wǎng)。

虛擬路由器（virtual router）作為虛擬網(wǎng)的核心網(wǎng)絡(luò)設(shè)備，近年來引起了眾多關(guān)注[1～9]。虛擬路由器是在一個物理路由器平臺（physical router platform）上并行實現(xiàn)多個相互獨立的虛擬路由器實例（virtual router instance），每個虛擬路由器實例運行各自的路由協(xié)議和轉(zhuǎn)發(fā)算法，并使用各自的轉(zhuǎn)發(fā)表FIB（forwarding information base）。每個物理路由器平臺需支持幾十個甚至幾百個虛擬路由器實例。例如，Cisco公司和Juniper公司的虛擬路由器[10,11]分別采用虛擬機VMware和Xen，在通用路由器硬件平臺上可實現(xiàn)128個虛擬路由器實例。每個虛擬路由器實例對應(yīng)一個轉(zhuǎn)發(fā)表FIB。在轉(zhuǎn)發(fā)表查找技術(shù)上，新的結(jié)構(gòu)帶來了新的問題。

（1）FIB 的存儲問題

FIB大小隨著網(wǎng)絡(luò)規(guī)模的增大而迅速增大。例如，現(xiàn)有的大容量 TCAM（ternary content addressable memory，三態(tài)內(nèi)容尋址存儲器）可容納220條40 bit的路由規(guī)則[12]。如果每個虛擬路由器包含219條路由規(guī)則，且每個路由器維護一個獨立的FIB，將導(dǎo)致虛擬路由器的存儲空間開銷呈爆炸性增長，限制并行虛擬路由器實例的個數(shù)。

（2）FIB 的更新問題

目前Internet轉(zhuǎn)發(fā)表的更新頻率為每秒幾百次，更新頻率峰值超過每秒1萬次[13]。在虛擬路由器中，一個更新事件會引發(fā)對多張轉(zhuǎn)發(fā)表的同時更新，提高了更新頻率。為了減少存儲，通常將多張轉(zhuǎn)發(fā)表合并成復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，這給更新操作帶來更大的挑戰(zhàn)[14]。

（3）FIB的查找速度是共性問題

網(wǎng)絡(luò)鏈路速率已達到40 Gbit/s[15]，因此最長前綴匹配的IP地址查找速度成為網(wǎng)速的瓶頸。為使網(wǎng)絡(luò)達到40 Gbit/s的速率，對于分組長40 byte的查找時間就需要達到8 ns。

盡管最直接的解決方案是為每張轉(zhuǎn)發(fā)表分配單獨的空間，這樣就滿足了虛擬網(wǎng)的隔離性要求，但實際卻很難做到。一方面，由于不能事先確定各個虛擬路由器實例的轉(zhuǎn)發(fā)表大小，且虛擬路由器實例也是動態(tài)變化的，因此很難確定為每個實例轉(zhuǎn)發(fā)表分配多大的空間；另一方面，如前面所提到的，存儲空間開銷的約束，使得目前的技術(shù)很難同時隔離地維持幾十張甚至幾百張轉(zhuǎn)發(fā)表。

考慮到虛擬路由器中可存在幾十張到上百張轉(zhuǎn)發(fā)表，其中有基于IPv4的、IPv6的和非傳統(tǒng)路由方式 （如基于NDN的名字命名方式）的轉(zhuǎn)發(fā)表，可將轉(zhuǎn)發(fā)表按類型合并存儲。本文關(guān)注基于IP地址的轉(zhuǎn)發(fā)表存儲。

2 相關(guān)研究

目前關(guān)于解決轉(zhuǎn)發(fā)表的大容量存儲問題的研究主要包括以下幾點。

[5]提出將每個轉(zhuǎn)發(fā)表對應(yīng)的特里樹合并成一個特里樹，來自不同轉(zhuǎn)發(fā)表但相同前綴的表項合并為一項，如果各特里樹的結(jié)構(gòu)類似，即合并的表項居多，那么這種方案可以達到較好的效果。但如果各個特里樹結(jié)構(gòu)相差較大，該方案不能達到預(yù)期效果。

· 參考文獻[11，12]提出利用特里樹編織來解決結(jié)構(gòu)相差很大的問題。該算法對每個特里樹節(jié)點的左右孩子節(jié)點進行旋轉(zhuǎn)，通過編織比特指示該特里樹的遍歷方向，從而確保查找正確。這樣，利用孩子節(jié)點旋轉(zhuǎn)機制增加多個FIB的重疊度，進一步減少融合特里樹的存儲空間開銷。Ganegedara在參考文獻[16]中提到，在某些情況下，使用特里樹編織也很難有效地合并轉(zhuǎn)發(fā)表，比如同屬一個區(qū)域的邊緣路由器轉(zhuǎn)發(fā)表中大部分前綴是相同的，而來自不同邊緣路由器的轉(zhuǎn)發(fā)表相差就很大。于是Ganegedara提出了多根（multiroot）的解決辦法，不同區(qū)域且相差很多的轉(zhuǎn)發(fā)表分別使用各自的特里樹。還可以結(jié)合特里樹編織技術(shù)，減小特里樹結(jié)構(gòu)差距大所帶來的影響。本文假設(shè)各個轉(zhuǎn)發(fā)表是相似的，實際環(huán)境中，若不相似，可采用多根技術(shù)或特里樹編織技術(shù)。上述研究主要關(guān)注高效IP地址查找的存儲，由于多FIB融合的更新開銷高，如何在存儲高效的條件下支持快速更新成為快速IP地址查找算法的關(guān)鍵問題。

· 參考文獻[1，2，4]均是基于集合分割的IP地址查找算法。集合分割借助特里樹將前綴集合分割成兩個，其中不相交的集合大約包括90%的前綴；另一個重疊前綴的集合包括大約10%的前綴。這樣，大部分的更新操作只涉及不相交前綴集合，大大降低了更新速度。

· 參考文獻[4]采用并行的流水線結(jié)構(gòu)，并采用2-3樹數(shù)據(jù)結(jié)構(gòu)表示每個子集，與TCAM相比，查找和更新速度較慢。

·參考文獻[1]對于兩個子集分別采用TCAM技術(shù)和SRAM（static RAM，靜態(tài)隨機存儲器）技術(shù)，并使用虛擬路由器身份（virtual router ID，VID）的方式合并轉(zhuǎn)發(fā)表，使得合并轉(zhuǎn)發(fā)表的長度和轉(zhuǎn)發(fā)表的個數(shù)線性相關(guān)。當(dāng)需要合并上百張轉(zhuǎn)發(fā)表時，占用的存儲空間將是相當(dāng)大的。

· 參考文獻[2]采用TCAM分別存儲兩個子集，對于重疊前綴集合，采用VID的方式合并轉(zhuǎn)發(fā)表。盡管文中對于14個轉(zhuǎn)發(fā)表的情況進行了分析，結(jié)論是可行的，但虛擬路由器可能承載幾百個虛擬網(wǎng)，這種合并方式會占用過多的存儲量。另外，TCAM的價格和功耗都是很高的，而且查找和更新操作大都出現(xiàn)在不相交前綴集合，使用TCAM存儲重疊前綴集合的更新開銷也較大，因此，對于重疊前綴集合，使用TCAM的必要性不大。

3 相關(guān)技術(shù)

3.1 基于特里樹的集合分割

集合分割是指將一個融合的FIB映射到一棵特里樹，將所有葉子節(jié)點對應(yīng)的前綴組成一個集合，這個集合中所有前綴不相交，稱為不相交前綴集合；將內(nèi)部節(jié)點對應(yīng)的所有前綴組成一個集合，不能保證這個集合中的所有節(jié)點不相交，稱為重疊前綴集。

實驗結(jié)果表明，葉子節(jié)點約占90%，內(nèi)部節(jié)點約占10%。路由更新更多地體現(xiàn)在長前綴的增加或者刪除上，短的內(nèi)部節(jié)點前綴相對穩(wěn)定。

3.2 TCAM和SRAM

基于TCAM和基于SRAM的FIB查找技術(shù)都是常用的FIB查找技術(shù)，它們采用不同的方法。

在TCAM中，每個前綴與IP地址并行比較，并在一個時鐘周期完成。如果前綴集合是不相交的，那么每次最多有一個匹配項；如果前綴集合是重疊的，有可能一次匹配多個，通常是將前綴按長度排序，如較長的前綴存放在低地址，那么在匹配前綴中選取低地址前綴作為匹配結(jié)果。這樣，在更新時，為了保持順序，需要移動大量不相關(guān)的前綴項。

SRAM通常使用樹型數(shù)據(jù)結(jié)構(gòu)。但是，基于特里樹的結(jié)構(gòu)通常存儲量較大，更新開銷也較大。且由于前綴重疊，通常的遍歷樹算法不可用，F(xiàn)IB查找可能需要多次訪問內(nèi)存（以下簡稱訪存）。對于較大的轉(zhuǎn)發(fā)表，存儲空間的限制成為主要約束。

相比傳統(tǒng)需要多次訪存的基于軟件的路由查找操作來說，TCAM在一個時鐘周期內(nèi)可以完成一次路由查找，因此具有一定的時間性能優(yōu)勢。但是，TCAM的造價和功耗較大。

已知集合分割后，不相交前綴占90%，如果將其用TCAM存儲，查找快，占用存儲量較使用SRAM要小，并且由于是不相交的前綴集合，不需要保持順序存儲，更新時僅需要一次訪存操作，大大簡化了更新，因此，與參考文獻[15]和參考文獻[17]的做法一樣，這里使用TCAM存儲不相交前綴集合。

重疊前綴集合占10%，如果使用TCAM，那么為保持順序更新，需要多次訪存。針對TCAM增量更新問題，有許多解決方案，常被采納的有參考文獻[18]的兩個算法：PLO_OPT和CAO_OPT算法。但是，這些算法只是在一定程度上優(yōu)化了更新性能。SRAM耗費存儲空間較大，查找需要多次訪存，速度較TCAM慢，但由于使用新一代的FPGA，可以使得更新和查找操作同時進行，互不干擾，因此，這里使用SRAM存儲重疊前綴集合。

3.3 轉(zhuǎn)發(fā)表合并

轉(zhuǎn)發(fā)表合并存儲可以采用兩種方式：參考文獻[19]的合并方式記為合并方式1；參考文獻[20]的合并方式記為合并方式2。合并方式1中，給所有轉(zhuǎn)發(fā)表等長編號，將轉(zhuǎn)發(fā)表編號和前綴合并標識每個前綴，將轉(zhuǎn)發(fā)表縱向延伸；合并方式2中，將每張轉(zhuǎn)發(fā)表中前綴值相同的表項合并（如果相應(yīng)轉(zhuǎn)發(fā)表中沒有對應(yīng)前綴，可以將下一跳地址標識為0），將轉(zhuǎn)發(fā)表橫向延伸。如對于轉(zhuǎn)發(fā)表A的表項<0*，B>和轉(zhuǎn)發(fā)表 B的表項<0*，C>，可以合并為<0*，[B，C]>。

參考文獻[15]在TCAM和SRAM中合并轉(zhuǎn)發(fā)表時均采用合并方式1，這樣就不支持個數(shù)較多的轉(zhuǎn)發(fā)表，這里假定有100張轉(zhuǎn)發(fā)表，每個轉(zhuǎn)發(fā)表總記錄數(shù)為500 000個，對每個轉(zhuǎn)發(fā)表劃分出的不相交前綴個數(shù)大約為400 000個，容量較大的TCAM可容納220個40 bit的前綴，若采用合并方式1，容納重疊前綴就需要大約39（400 000×100/220≈38.15）個TCAM芯片，這是不可行的；若采用合并方式2，由于可以合并多個轉(zhuǎn)發(fā)表的記錄，以減少TCAM的使用，因此本文采用合并方式2來合并轉(zhuǎn)發(fā)表。

4 總體結(jié)構(gòu)

圖1（a）顯示了將兩張轉(zhuǎn)發(fā)表合并的結(jié)果，圖 1（b）是合并轉(zhuǎn)發(fā)表對應(yīng)的1 bit特里樹。

和參考文獻[15]的結(jié)構(gòu)類似，如圖2所示，這里有兩個并行的IP地址查找引擎。其中，較大的集合映射到基于TCAM的查找引擎，較小的集合映射到基于SRAM的查找引擎。分組頭解析器（head parser）將到來分組中的分組頭部分分離，提取出目的IP地址，并將此IP地址傳到并行結(jié)構(gòu)，使得它們同時啟動查找。同時，到來的分組緩存在buffer中，等待查找結(jié)果。兩個并行結(jié)構(gòu)分別產(chǎn)生下一跳信息，由于TCAM中存儲較長的前綴，所以優(yōu)先權(quán)仲裁器（priority arbiter）優(yōu)先使用TCAM產(chǎn)生的結(jié)果。由于兩個引擎都有可能匹配不到結(jié)果，優(yōu)先權(quán)仲裁器決定是否丟棄或最終的下一跳。將buffer中暫存的分組取出，并根據(jù)下一跳信息，由分組整形器（packet modifier）對分組整形，并將分組送到相應(yīng)的輸出接口。

圖1 轉(zhuǎn)發(fā)表合并結(jié)果及其對應(yīng)的特里樹

圖2 總體結(jié)構(gòu)

本文的 TCAM 和 SRAM 結(jié)構(gòu)如圖 3（a）、圖 3（b）所示。

由于已經(jīng)假設(shè)各轉(zhuǎn)發(fā)表數(shù)據(jù)集相似，所以基于TCAM的存儲結(jié)構(gòu)可以采用合并方式2。這種結(jié)構(gòu)會降低命中率，因此如果沒有前面的假設(shè)，應(yīng)對轉(zhuǎn)發(fā)表進行預(yù)處理（如采用多根技術(shù)），使得為0的表項較少。

對于基于SRAM的查找結(jié)構(gòu)，這里采用合并方式2合并轉(zhuǎn)發(fā)表，查找中出現(xiàn)了新的問題。已知對特里樹查找需要從根遍歷到葉子節(jié)點或?qū)⑶熬Y讀完，這個過程中一旦遇到匹配節(jié)點，需要記錄節(jié)點信息，最終返回的是最后一次匹配的節(jié)點。如果采用合并方式1，一個節(jié)點最多指向一個轉(zhuǎn)發(fā)表項，只要節(jié)點有指向下一級SRAM的指針，就說明該節(jié)點標識了一個前綴，記錄節(jié)點信息時不需要到下一級SRAM中查看該表項是否存在；若采用合并方式2，一個節(jié)點指向多個轉(zhuǎn)發(fā)表項（這里是13個），有些表項可能不存在 （圖3中標識為0），因此每匹配一個節(jié)點需要到下級SRAM查看，降低了查找效率。針對這個問題，在特里樹節(jié)點增加了標志位，0或1分別代表無或有表項，這樣每次查找僅需要最后一次訪問下級SRAM，如圖4所示。

5 快速增量更新

總的來講，快速增量更新分為3類：插入、刪除、更改。更改操作不需要改變特里樹的結(jié)構(gòu)，這里著重討論插入和刪除操作。

圖3 基于TCAM和基于SRAM的IP地址查找

圖4 特里樹節(jié)點和下一跳指針數(shù)組的數(shù)據(jù)結(jié)構(gòu)

更新操作分兩步進行：控制面確定在兩個集合中插入或刪除哪些項；數(shù)據(jù)面執(zhí)行確切的插入或刪除項的操作。對于第一步，控制面維持一棵1 bit特里樹，分割不相交前綴集合（S1）和重疊前綴集合（S2）。方案1、方案2和本文的方案是一樣的。在第二步中，執(zhí)行對S1或S2的插入或刪除項操作。其中，S1是不相交前綴集合，不需要保證順序，因此，對S1插入或刪除只需要一次寫操作即可。S2算法的具體過程如下。

輸入：更新前合并轉(zhuǎn)發(fā)表F0，待插入（刪除）記錄的前綴值P、所屬轉(zhuǎn)發(fā)表編號F及對應(yīng)下一條值N。

輸出：更新后合并轉(zhuǎn)發(fā)表F0′。

插入過程為：如果P在F0中，將P和F對應(yīng)項的值改為N，將P和F對應(yīng)標記項改為1；否則，在F0中插入記錄，其前綴項的值為P，P和F對應(yīng)項的值為N，P和F對應(yīng)標記項為1，該記錄中其余項置為0。

刪除過程為：將P和F對應(yīng)項置為0，將P和F對應(yīng)標記項置為0，如果該記錄對應(yīng)所有標記項都為0，刪除該條記錄。

6 實驗與分析

本次實驗數(shù)據(jù)是在項目RIS中收集的2013年9月12日16時的數(shù)據(jù)，13個路由轉(zhuǎn)發(fā)表的前綴總數(shù)以及葉子節(jié)點對應(yīng)前綴數(shù)見表1。采用本文提出的合并路由轉(zhuǎn)發(fā)表的方法，將13個路由轉(zhuǎn)發(fā)表合并為一個，并將其分解成兩個集合。

表1 對實際轉(zhuǎn)發(fā)表的分析

對于參考文獻[15]和參考文獻[17]所采用的合并方式1，原始前綴前附加代表轉(zhuǎn)發(fā)表的前綴均為4位（0000-1100）。參考文獻[15]中的存儲量減少明顯，而參考文獻[17]在合并13張轉(zhuǎn)發(fā)表時存儲量是可以的，但當(dāng)轉(zhuǎn)發(fā)表數(shù)量達到幾十張甚至幾百張時，存儲量將大大增加，這樣無論是TCAM的數(shù)量，還是更新效率，都不是理想的效果。本文的合并FIB方式，大大減少了存儲空間。

7 討論

TCAM中，對于合并后轉(zhuǎn)發(fā)表的每個前綴，不是所有原轉(zhuǎn)發(fā)表都有對應(yīng)前綴項（也就是標識為0的項）。造成這種現(xiàn)象的根源在于，控制面構(gòu)造特里樹時，其他轉(zhuǎn)發(fā)表的前綴可能覆蓋原轉(zhuǎn)發(fā)表的前綴，使得被覆蓋的前綴不再是葉子節(jié)點。因此，這種結(jié)構(gòu)會增加不命中的概率。于是，當(dāng)各前綴集合相差較大時，適宜使用合并方式1；當(dāng)相差不大時，采用合并方式2。

若將重疊前綴集合變?yōu)椴幌嘟坏模Ｓ萌~推（leaf-pushing）技術(shù)[20]。它存在兩個缺陷：第一，實施葉推技術(shù)會產(chǎn)生冗余節(jié)點，使節(jié)點個數(shù)增加6%左右，相對總的前綴個數(shù)而言，增量并不是很大（前綴個數(shù)增加大約0.6%）；第二，每次更新（如插入或刪除）操作，可能需要重建葉推特里樹，并需要和原葉推特里樹對比，從而得到需要改動的多個前綴項。這樣，不管在控制面還是數(shù)據(jù)面（尤其是控制面），需要耗費較多的空間和時間。這是致命的缺陷，因此這里不采用葉推技術(shù)處理重疊前綴集合。

多比特特里樹可以有效縮短查找時間，但是更新開銷很大。而在虛擬路由器中，一個更新事件會引發(fā)對多張轉(zhuǎn)發(fā)表的同時更新，更新頻率增加很多，所以這里采用1 bit特里樹的結(jié)構(gòu)存儲。

8 結(jié)束語

本文分析了基于集合分割的虛擬路由器轉(zhuǎn)發(fā)表的實現(xiàn)，對幾種可能采取的技術(shù)進行了闡述，并采用了合并方式2來合并兩個集合，實驗結(jié)果表明，這種合并方式大大減少了存儲空間。并針對合并方式2帶來的弊端，在第一級SRAM中使用標志位，使得在查找過程中訪問下級SRAM的次數(shù)降為1次。

參考文獻

1 Anderson T,Peterson L,Shenker S,et al.Overcoming the internet impasse through virtualization.Computer,2005,38(4):34～41

2 Turner J S,Taylor D E.Diversifying the internet.Proceedings of Global Telecommunications Conference,StLouis,MO,USA,2005

3 Feamster N,Gao L,Rexford J.How to lease the internet in your spare time.ACM SIGCOMM Computer Communication Review,2007,37(1):61～64

4 FIRE.http://www.ict-firworks.eu,2012

5 Zhang L,Estrin D,Burke J,et al.Named Data Networking(NDN)Project.Relatório Técnico NDN-0001,Xerox Palo Alto Research Center-PARC,2010

6 Egi N,Greenhalgh A,Handley M,et al.Towards high performance virtual routers on commodity hardware.Proceedings of the ACM CoNEXT Conference,New York,NY,USA,2008:1～12

7 NWGN.http://akari-project.nict.go.jp,2012

8 Han S, Jang K, Park K S,etal. PacketShader: a GPU-accelerated software router.ACM SIGCOMM Computer Communication Review,2010,40(4):195～206

9 FIF.http://www.fif.kr,2012

10 Cisco logical router.http://www.cisco.com,2012

11 Juniper logical router.http://www.juniper.net,2012

12 Netlogic.NL 9000 RA knowledge-based processors,2009

13 The BGP instability report. http://bgpupdates.potaroo.net/instability/bgpupd.html,2014

14 Huang K,Xie G,Li Y,et al.Offset addressing approach to memory-efficientIP address lookup.Proceedings ofIEEE INFOCOM,Shanghai,China,2011:306～310

15 Luo L,Xie G,Xie Y,et al.A hybrid IP lookup architecture with fast updates.Proceedings of IEEE INFOCOM,Orlando,FL,USA,2012:2435～2443

16 Ganegedara T,Jiang W,Prasanna V.Multiroot:towards memory-efficientrouter virtualization.Proceedings ofIEEE International Conference,Kyoto,Japan,2011:1～5

17 Luo L,Xie G,Uhlig S,et al.Towards TCAM-based scalable virtual routers.Proceedings of the 8th International Conference on Emerging Networking Experiments and Technologies,Nice,France,2012:73～84

18 Shah D,Gupta P.Fast incremental updates on ternary-CAMs for routing lookups and packet classification.Proceedings of Hot Interconnects-8,Stanford,CA,USA,2000:145～153

19 Fu J,Rexford J.Efficient IP-address lookup with a shared forwarding table for multiple virtual routers.Proceedings of the ACM CoNEXT Conference,New York,NY,USA,2008:1～12

20 Le H,Ganegedara T,Prasanna V K.Memory-efficient and scalable virtual routers using FPGA.Proceedings of the 19th ACM/SIGDA International Symposium on Field Programmable Gate Arrays,Monterey,California,USA,2011:257～266