黃 昆，羅臘詠，葛敬國，謝高崗

(1.中國科學(xué)院計算技術(shù)研究所，北京 100190;2.中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心，北京 100190)

0 引言

當(dāng)前互聯(lián)網(wǎng)采用基于TCP/IP協(xié)議的體系結(jié)構(gòu)［1］，即以IP協(xié)議為細(xì)腰的分層漏斗結(jié)構(gòu)。隨著物聯(lián)網(wǎng)、云計算、移動計算等新技術(shù)新應(yīng)用的不斷涌現(xiàn)、以及網(wǎng)絡(luò)規(guī)模的日益擴(kuò)大，TCP/IP體系結(jié)構(gòu)將面臨可擴(kuò)展性、移動性、安全性、可控可管等技術(shù)挑戰(zhàn)。針對上述挑戰(zhàn)，國內(nèi)外研究者已開展未來互聯(lián)網(wǎng)體系結(jié)構(gòu)研究，例如:美國 GENI［2］和 FIND［3］項目、歐盟 FIRE［4］項目、AsiaFI［5］項目、日本 NWGN［6］項目、韓國FIF［7］項目和中國CENI項目等。這些研究主要采用網(wǎng)絡(luò)虛擬化思想［8-10］，即在一個實際物理網(wǎng)絡(luò)基礎(chǔ)設(shè)施上構(gòu)建多個相互隔離的并行網(wǎng)絡(luò)切片(slice)［11］，每個網(wǎng)絡(luò)切片運(yùn)行一個具有不同體系結(jié)構(gòu)的虛擬化網(wǎng)絡(luò)。因此，基于網(wǎng)絡(luò)虛擬化的未來互聯(lián)網(wǎng)技術(shù)不僅兼容基于TCP/IP協(xié)議的互聯(lián)網(wǎng)演進(jìn)，而且支持新體系結(jié)構(gòu)、新協(xié)議和新算法。

可編程虛擬化路由器(programmable virtual router)是實現(xiàn)網(wǎng)絡(luò)虛擬化的關(guān)鍵部件，也是未來互聯(lián)網(wǎng)的核心網(wǎng)絡(luò)設(shè)備?？删幊烫摂M化路由器是在一個物理路由器平臺上并行實現(xiàn)多個相互獨立的虛擬路由器，且每個路由器采用自定義的路由協(xié)議和轉(zhuǎn)發(fā)算法。與傳統(tǒng)路由器不同，可編程虛擬化路由器采用數(shù)據(jù)平面與控制平面分離的思想［12］，即利用虛擬機(jī)技術(shù)來實現(xiàn)可編程的多個數(shù)據(jù)平面和多個控制平面，從而在同一個物理設(shè)備上動態(tài)構(gòu)建多個邏輯路由設(shè)備。例如，Cisco公司和Juniper公司的虛擬化路由器［13-14］分別采用虛擬機(jī) VMWare和Xen，在通用路由器硬件平臺上可實現(xiàn)128個虛擬路由器。可編程虛擬化路由器有利于ISP簡化網(wǎng)絡(luò)拓?fù)浜土髁抗芸亍p少網(wǎng)絡(luò)設(shè)備能耗和占地空間，從而降低網(wǎng)絡(luò)設(shè)備投資和網(wǎng)絡(luò)運(yùn)維成本。因此，可編程虛擬化路由器已廣泛應(yīng)用于網(wǎng)絡(luò)試驗床［15］、網(wǎng)絡(luò)管理［16］、用戶自定義的路由協(xié)議、基于策略的路由協(xié)議、以及多拓?fù)涞穆酚蓞f(xié)議等。

轉(zhuǎn)發(fā)表(forwarding table，F(xiàn)IB)查找技術(shù)是可編程虛擬化路由器性能的核心，即在一組路由規(guī)則中，查找出與輸入數(shù)據(jù)包匹配的路由規(guī)則，轉(zhuǎn)發(fā)到下一跳路由器。FIB查找技術(shù)可分為基于IP和基于非IP的查找技術(shù)。IP查找是當(dāng)前互聯(lián)網(wǎng)路由器的關(guān)鍵技術(shù)，即采用最長前綴匹配(longest prefix matching，LPM)算法［17］，查找出與數(shù)據(jù)包的目的 IP地址匹配的最長前綴規(guī)則。以內(nèi)容為中心的未來互聯(lián)網(wǎng)體系結(jié)構(gòu)，例如 NDN(named data networking)［18］，提出基于內(nèi)容名字的非IP查找技術(shù)，即采用最長名字前綴匹配(longest name prefix matching，LNPM)算法，查找出與內(nèi)容名字匹配的最長前綴規(guī)則。

可編程虛擬化路由器的FIB查找技術(shù)面臨性能與可伸縮性挑戰(zhàn)。首先，F(xiàn)IB查找是計算密集型操作，運(yùn)行在路由器的關(guān)鍵數(shù)據(jù)路徑上，需要檢查高速海量數(shù)據(jù)包，并與成千上萬條路由規(guī)則進(jìn)行匹配。其次，可編程虛擬化路由器需要并行運(yùn)行成百上千個虛擬路由器，并確保每個虛擬路由器的轉(zhuǎn)發(fā)性能，這將導(dǎo)致其存儲空間和并行處理等需求迅猛增大，難以動態(tài)擴(kuò)展支持更多虛擬路由器。最后，可編程虛擬化路由器要求支持非IP路由查找，靈活實現(xiàn)NDN等新型路由協(xié)議與轉(zhuǎn)發(fā)算法。因此，靈活高效的FIB查找技術(shù)成為可編程虛擬化路由器研究熱點。

1 可編程虛擬化路由器

近年來，研究者提出了多種支持未來互聯(lián)網(wǎng)的可編程虛擬化路由器，可分為基于軟件和基于硬件的虛擬化路由器。

在基于軟件的可編程虛擬化路由器方面，Egi等人［19］提出了vRouter，在x86多核處理器平臺上采用虛擬機(jī)Xen和OpenVZ，在數(shù)據(jù)平面實現(xiàn)并行軟件路由器Click［20］，其吞吐量可達(dá)7 Mbit/s;Dobrescu等人［21］提出了RouteBricks，在服務(wù)器集群和多核處理器平臺上采用并行路由器體系結(jié)構(gòu)實現(xiàn)Click，其吞吐量可達(dá)35 Gbit/s;Han等人［22］提出了Packet-Shader，利用GPU加速基于通用CPU的軟件路由器Click，其吞吐量可達(dá)39 Gbit/s。

在基于硬件的可編程虛擬化路由器方面，Turner等人［23］提出了 Supercharging PlanetLab，采用網(wǎng)絡(luò)處理器實現(xiàn)PlanetLab覆蓋網(wǎng)的高性能節(jié)點;Carli等人［24］提出了PLUG，采用高速芯片實現(xiàn)靈活模塊化路由查找模式，支持新路由協(xié)議的快速部署;Unnikrishnan等人［25］提出了基于FPGA的虛擬化路由器，利用可重構(gòu)FPGA實現(xiàn)數(shù)據(jù)包轉(zhuǎn)發(fā)，并采用虛擬機(jī)OpenVZ和軟件路由器Click實現(xiàn)路由查找，可支持15個并行虛擬邏輯路由器;McKeown等人［12］提出了OpenFlow，采用NetFPGA實現(xiàn)數(shù)據(jù)平面與控制平面分離的軟件定義路由器，多個虛擬化控制平面共享一個轉(zhuǎn)發(fā)數(shù)據(jù)平面;Xie等人［26］提出了PEARL，利用FPGA的多根I/O虛擬化技術(shù)實現(xiàn)多個虛擬化數(shù)據(jù)平面，結(jié)合多核處理器實現(xiàn)復(fù)雜路由查找和控制平面管理。Anwer等人［27-28］提出了SwitchBlade，采用可編程N(yùn)etFPGA實現(xiàn)多個并行數(shù)據(jù)平面，并確保每個數(shù)據(jù)平面的線速數(shù)據(jù)包路由查找。

為了實現(xiàn)目前互聯(lián)網(wǎng)平滑過渡以及未來互聯(lián)網(wǎng)快速部署，這些可編程虛擬化路由器要求達(dá)到商用路由器的高吞吐量等性能指標(biāo)。一方面，網(wǎng)絡(luò)帶寬迅猛增長，例如互聯(lián)網(wǎng)骨干帶寬將增至100 Gbit/s;另一方面，YouTube，F(xiàn)acebook，Twitter和微博等新型網(wǎng)絡(luò)業(yè)務(wù)，產(chǎn)生海量業(yè)務(wù)內(nèi)容和網(wǎng)絡(luò)流量。這些高速海量數(shù)據(jù)包給可編程虛擬化路由器的設(shè)計與實現(xiàn)帶來巨大挑戰(zhàn)。

2 性能與可伸縮性挑戰(zhàn)

為了支持互聯(lián)網(wǎng)演進(jìn)與創(chuàng)新，可編程虛擬化路由器要求滿足隔離性、性能和可編程性等需求［11］。隔離性要求同一物理設(shè)備上的多個虛擬路由器在CPU時間片、存儲空間、鏈路帶寬和路由規(guī)則等資源上相互獨立且互不干擾，實現(xiàn)對共享資源的動態(tài)分配和透明管理。性能要求每個虛擬路由器高效利用共享資源，實現(xiàn)線速數(shù)據(jù)包路由查找與轉(zhuǎn)發(fā)，并支持內(nèi)容緩存管理和路由規(guī)則更新。可編程性要求提供從底層到高層的多層次可編程接口，從而靈活實現(xiàn)自定義的數(shù)據(jù)包處理流程，兼容IP和非IP等體系結(jié)構(gòu)、路由協(xié)議和轉(zhuǎn)發(fā)算法。

可編程虛擬化路由器的隔離性、性能和可編程性是相互制約的，其主要區(qū)別體現(xiàn)在路由器資源的管理策略上。隔離性是采用資源分割策略，即每個虛擬路由器靜態(tài)占用設(shè)備資源;而性能和可編程性是采用資源共享策略，即每個虛擬路由器動態(tài)占用設(shè)備資源。性能要求緊耦合的高效數(shù)據(jù)包處理，而可編程性要求松耦合的靈活數(shù)據(jù)包處理。因此，為了實現(xiàn)未來互聯(lián)網(wǎng)的靈活高效FIB查找，可編程虛擬化路由器需要折衷考慮隔離性、性能和可編程性，即在隔離性和可編程性等約束條件下，提升其性能和可伸縮性，達(dá)到商用路由器的高吞吐量等指標(biāo)。

近年來，隨著互聯(lián)網(wǎng)帶寬和流量的迅猛增長、路由規(guī)則的日益增多、新型路由協(xié)議的不斷涌現(xiàn)，可編程虛擬化路由器的FIB查找技術(shù)面臨性能和可伸縮性挑戰(zhàn)，即如何滿足多個FIB查找的吞吐量、存儲空間和增量更新等需求。

1)高速網(wǎng)絡(luò)及應(yīng)用的迅猛發(fā)展要求可編程虛擬化路由器中的每個虛擬路由器實現(xiàn)線速FIB查找。未來互聯(lián)網(wǎng)的骨干鏈路帶寬將增至100 Gbit/s，每個數(shù)據(jù)包的平均FIB查找時間為3.2 ns。因此，F(xiàn)IB查找必須在高速存儲器(片上SRAM)上執(zhí)行，并減少慢速存儲器(片外DRAM)訪問次數(shù)，從而提高其吞吐量。

2)網(wǎng)絡(luò)業(yè)務(wù)及其路由規(guī)則的日益增多要求可編程虛擬化路由器支持更多并行虛擬路由器。FIB大小隨著網(wǎng)絡(luò)規(guī)模的增大而迅猛增大。例如，目前IP核心路由器包含約40萬條路由規(guī)則。每個虛擬路由器維護(hù)一個獨立的FIB，導(dǎo)致可編程虛擬化路由器的存儲空間開銷呈爆炸性增長，轉(zhuǎn)發(fā)表更新開銷高，可伸縮性差。這將不僅限制并行虛擬路由器個數(shù)，而且限制每個虛擬路由器的FIB查找性能。

3)新型未來互聯(lián)網(wǎng)體系結(jié)構(gòu)NDN要求可編程虛擬化路由器靈活支持基于非IP的FIB查找。與IP地址不同，NDN名字采用URL方式命名內(nèi)容，具有長度不確定且無限長等特點，采用LPNM算法查找最長名字匹配的前綴規(guī)則，導(dǎo)致存儲開銷高和查找效率低等問題。另外，為了減少請求數(shù)據(jù)包的響應(yīng)時延和數(shù)據(jù)傳輸流量，NDN要求在轉(zhuǎn)發(fā)路徑上支持緩存請求數(shù)據(jù)包和內(nèi)容，導(dǎo)致緩存查找和更新開銷大。

3 FIB查找技術(shù)

針對上述性能和可伸縮性挑戰(zhàn)，研究者主要從多FIB融合的IP查找算法和NDN名字查找算法等兩個方面，實現(xiàn)可編程虛擬化路由器的靈活高效FIB查找。

3.1 多FIB融合的IP查找算法

IP查找是在FIB中，查找出與輸入數(shù)據(jù)包的目的IP地址最長前綴匹配的轉(zhuǎn)發(fā)規(guī)則。轉(zhuǎn)發(fā)規(guī)則是由IP地址前綴和下一跳步信息(例如轉(zhuǎn)發(fā)端口號、路由器MAC地址)等構(gòu)成。在可編程虛擬化路由器中，每個虛擬路由器維護(hù)一個FIB，采用特里樹(Trie)表示每個FIB的IP地址前綴集。圖1給出了2個FIB及其二叉特里樹Trie1和Trie2。其中，帶陰影節(jié)點為前綴匹配節(jié)點。

圖1 兩個FIB及其二叉特里樹Fig.1 Two FIB and their binary tries

可編程虛擬化路由器的IP查找算法可采用分離和融合2種方式。分離方式是為每個FIB構(gòu)建一個獨立特里樹進(jìn)行IP查找，且為每個虛擬路由器分配相互隔離的計算和存儲資源。該方式的優(yōu)點是虛擬路由器之間的隔離性好，確保其互不干擾;其缺點是多個獨立特里樹的存儲空間需求高，且不同特里樹的存儲空間分配不均等。

針對分離方式中的單個FIB，研究者提出了許多IP查找算法，可分為基于TCAM、基于哈希和基于特里樹的IP查找算法?；赥CAM的IP查找算法［29-31］利用TCAM硬件在1個時鐘周期內(nèi)完成一次IP查找，提供確定性和高速IP查找，但是存在能耗高、價格昂貴等問題?；诠５?IP查找算法［32-37］利用片上SRAM的哈希表來加速IP查找性能，但是存在存儲器帶寬需求大等問題?；谔乩飿涞腎P查找算法包括葉推特里樹(leaf-pushed Trie)［38］、呂勒奧特里樹(Lulea Trie)［39］、樹位圖特里樹(tree bitmap Trie)［40］、形狀圖(shape graph)［41］和偏移編碼特里樹(offset encoded Trie)［42］等采用樹型數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)存儲高效的IP查找。為了提高該算法的吞吐量，研究者提出了流水線方法(pipelining)［45-49］，即在片上SRAM 的1個時鐘周期內(nèi)完成一次IP查找。

與分離方式相反，融合方式是多個虛擬路由器共享計算和存儲資源，將多個FIB融合表示成一個共享數(shù)據(jù)結(jié)構(gòu)進(jìn)行IP查找。該方式的優(yōu)點是共享數(shù)據(jù)結(jié)構(gòu)的存儲空間需求低，可動態(tài)擴(kuò)展支持更多虛擬路由器;其缺點是弱化虛擬路由器之間的隔離性，多個FIB融合后的更新開銷高。近年來，研究者提出了針對多FIB融合的IP查找算法。這些算法解決的共性問題是如何將多個FIB融合表示成一個高效的共享數(shù)據(jù)結(jié)構(gòu)，減少整個路由器的存儲空間開銷，以及如何支持多個FIB的快速增量更新。

Fu等人［50］提出了基于特里樹重疊(Trie overlay)的IP查找算法。該算法是利用重疊機(jī)制將多個FIB的IP前綴集進(jìn)行重疊融合，并采用一個融合特里樹表示這些重疊后的IP前綴集，從而減少多個獨立特里樹的存儲空間開銷。為了確保查找正確，該算法在融合特里樹的每個前綴匹配節(jié)點中增加一個位圖(bitmap)，用于指出匹配了哪個FIB的IP前綴。圖2給出了特里樹重疊方法示例，即將圖1的2個特里樹從根節(jié)點開始進(jìn)行重疊，從而構(gòu)建一個融合特里樹。例如，在融合特里樹中，根節(jié)點Aa是由Trie1和Trie2的根節(jié)點A和a重疊而成;類似地，其孩子節(jié)點Bb是由Trie1和Trie2的節(jié)點B和b重疊而成。當(dāng)給定數(shù)據(jù)包的FIB標(biāo)識符為Trie1和目的IP地址為1010，IP查找從根節(jié)點Aa開始，遍歷節(jié)點Cc，E和F。由于節(jié)點F是最長匹配前綴節(jié)點，查找結(jié)果為下一跳步信息P4。如果多個FIB具有相似結(jié)構(gòu)，該算法的存儲空間壓縮效果表現(xiàn)良好;否則，該算法無法減少多個FIB的存儲空間開銷。

圖2 特里樹重疊示例Fig.2 Trie overlay

Song等人［51］提出了基于特里樹編織(Trie braiding)的IP查找算法，即在上述特里樹重疊的基礎(chǔ)上，利用孩子節(jié)點旋轉(zhuǎn)機(jī)制來增加多個FIB的重疊度，進(jìn)一步減少融合特里樹的存儲空間開銷。該算法對每個特里樹節(jié)點的左右孩子進(jìn)行旋轉(zhuǎn)，采用編織比特(braiding bit)指示該特里樹的遍歷方向，從而確保查找正確。圖3給出了特里樹編織示例，即將圖1的2個特里樹從根節(jié)點開始進(jìn)行旋轉(zhuǎn)和重疊，從而構(gòu)建一個更加緊湊的融合特里樹。其中，每個節(jié)點采用2個編織比特表示Trie1和Trie2的遍歷方向。如果編織比特值為1，表示從其左分支遍歷右孩子，從其右分支遍歷左孩子。如果編織比特值為0，表示從其左分支遍歷左孩子，從其右分支遍歷右孩子。例如，節(jié)點Cc的編織比特為1，0，表示當(dāng)Trie1讀入字符0時遍歷其左孩子節(jié)點Ee，當(dāng)Trie2讀入字符1時遍歷其左孩子節(jié)點Ee。當(dāng)給定數(shù)據(jù)包的FIB標(biāo)識符為Trie1和目的IP地址為1010，IP查找從根節(jié)點Aa開始，遍歷節(jié)點Cc，Ee和Fg。由于節(jié)點Fg是最長匹配前綴節(jié)點，查找結(jié)果為下一跳步信息P4。該算法采用啟發(fā)式方法來最大化多個特里樹的重疊度，從而最小化融合特里樹的節(jié)點個數(shù)。但是，該算法僅減少融合特里樹的節(jié)點個數(shù)，卻不一定能減少其存儲空間開銷。其主要原因是特里樹實現(xiàn)不必為葉子節(jié)點分配存儲空間，因而由非葉子節(jié)點決定其存儲空間開銷。

上述研究主要關(guān)注可編程虛擬化路由器的存儲高效IP查找。由于多FIB融合的更新開銷高，如何在存儲高效的條件下支持快速增量更新成為可編程虛擬化路由器的快速IP查找算法的關(guān)鍵問題。

圖3 特里樹編織示例Fig.3 Trie braiding

Le等人［52］提出了基于集合分割(set partitioning)的IP查找算法，即利用集合分割機(jī)制將一個融合FIB分割成2個子表，采用2-3樹數(shù)據(jù)結(jié)構(gòu)表示每個子集，并執(zhí)行流水線并行IP地址查找。Luo等人［53］也提出了特里樹分割思想，將一個融合FIB分割成不相交前綴集和重疊前綴集;對于不相交前綴集，采用TCAM進(jìn)行快速查找，對于重疊前綴集，采用基于SRAM的流水線IP查找，從而實現(xiàn)快速查找和增量更新。圖4給出了特里樹分割示例，將圖4a中的一個特里樹分割成不相交前綴集(見圖4b)和重疊前綴集(見圖4c)。

圖4 特里樹分割示例Fig.4 Trie partitioning

Luo等人［54］提出了基于TCAM的存儲高效FIB查找算法，減少多FIB融合的TCAM存儲空間開銷。該算法通過挖掘不同IP前綴之間的相似性，提出了TCAM中共享前綴的數(shù)據(jù)結(jié)構(gòu)，如圖5所示。當(dāng)多個FIB共享相同的前綴時，在融合后的TCAM中僅保留一條表項，同時將多個下一跳步信息按照FIB的順序存儲在SRAM中?；谏鲜龊喜?shù)據(jù)結(jié)構(gòu)，可顯著降低TCAM存儲空間需求。但是，上述數(shù)據(jù)結(jié)構(gòu)會帶來前綴屏蔽問題，導(dǎo)致某些情況下不正確的最長前綴匹配。為了解決前綴屏蔽問題，該算法進(jìn)一步提出了FIB填充和FIB分割2種方法。

圖5 TCAM中共享前綴的數(shù)據(jù)結(jié)構(gòu)Fig.5 Shared prefix data structure in TCAM

Luo等人［55］提出了支持快速增量更新的特里樹合并方法。在已有特里樹合并的基礎(chǔ)上，該方法在特里樹節(jié)點數(shù)據(jù)結(jié)構(gòu)中引入前綴位圖，將節(jié)點和下一跳步分離，如圖6所示。當(dāng)增加一個虛擬路由器時，特里樹節(jié)點大小僅增加1比特，有效提高節(jié)點大小的可伸縮性;在特里樹合并過程中，避免采用葉推技術(shù)，從而在增加可伸縮性的同時，支持快速增量更新。另外，該方法采用IP查找流水線，其更新開銷為一次寫氣泡/每次更新，顯著減少更快開銷。

圖6 包含前綴位圖的特里樹節(jié)點數(shù)據(jù)結(jié)構(gòu)Fig.6 Trie node data structure with prefix bitmap

3.2 NDN名字查找算法

NDN是以內(nèi)容為中心的未來互聯(lián)網(wǎng)體系結(jié)構(gòu)，解決目前互聯(lián)網(wǎng)的地址空間爆炸、動態(tài)性、地址可擴(kuò)展等問題。NDN利用地址和標(biāo)識分離的思想，采用命名數(shù)據(jù)作為協(xié)議棧的細(xì)腰，并設(shè)計基于名字的路由協(xié)議和轉(zhuǎn)發(fā)算法。NDN采用類似URL的方式命名數(shù)據(jù)［18］，例如/cn/ac/ict/fi/index.html，表示網(wǎng)頁fi.ict.ac.cn/index.html。為了優(yōu)化流量和避免擁塞，NDN在路由器上緩存請求數(shù)據(jù)包及其響應(yīng)內(nèi)容，提升數(shù)據(jù)傳輸性能。

NDN路由器包含 FIB、興趣數(shù)據(jù)包緩存表(pending interest table，PIT)和內(nèi)容緩存表(content store，CS)［18］。圖7給出了NDN數(shù)據(jù)包轉(zhuǎn)發(fā)流程。客戶主機(jī)發(fā)送興趣(Interest)數(shù)據(jù)包，請求一個內(nèi)容(例如文件、電影或音樂);當(dāng)接收到興趣數(shù)據(jù)包后，服務(wù)器響應(yīng)數(shù)據(jù)(data)數(shù)據(jù)包給該客戶主機(jī)。因此，PIT是用于緩存未響應(yīng)的興趣數(shù)據(jù)包，而CS是用于緩存響應(yīng)的數(shù)據(jù)。

在NDN數(shù)據(jù)包轉(zhuǎn)發(fā)流程圖(見圖7)中，當(dāng)接收到一個興趣數(shù)據(jù)包時，NDN路由器首先在CS中查找，如果緩存了相應(yīng)的數(shù)據(jù)，直接返回該數(shù)據(jù);否則，在PIT中查找，如果緩存了相應(yīng)的興趣數(shù)據(jù)包，增加輸入端口到相應(yīng)的PIT表項中;否則，繼續(xù)在FIB中查找，如果查找成功，轉(zhuǎn)發(fā)該數(shù)據(jù)包到下一跳路由器;否則，丟棄該數(shù)據(jù)包，并返回NACK。當(dāng)接收到一個數(shù)據(jù)數(shù)據(jù)包時，NDN路由器在PIT中查找，從PIT表項中刪除對應(yīng)的興趣數(shù)據(jù)包，并在CS中緩存該數(shù)據(jù)，返回該數(shù)據(jù)給相應(yīng)的請求客戶主機(jī)。

圖7 NDN數(shù)據(jù)包轉(zhuǎn)發(fā)流程Fig.7 NDN packet forwarding procedure

為了支持NDN新型路由協(xié)議，可編程虛擬化路由器要求實現(xiàn)高效NDN命名查找算法。由于NDN名字具有長度不確定且無限長等特點，NDN命名查找采用LPNM算法查找最長名字匹配的前綴規(guī)則，導(dǎo)致FIB存儲開銷高和名字查找效率低等問題。另外，由于每個興趣數(shù)據(jù)包要求查找并更新PIT，NDN名字查找算法面臨快速增量更新等挑戰(zhàn)。

近年來，研究者提出了多種NDN命名查找算法，主要解決FIB/PIT/CS的存儲空間縮減和快速查找等問題。Wang等人［56］提出了一種NDN名字子串編碼方法來實現(xiàn)存儲高效的名字特里樹，以及提出了狀態(tài)遷移數(shù)組來實現(xiàn)快速LPNM。圖8給出NDN名字子串編碼及其狀態(tài)遷移數(shù)組。在圖8a的NDN名字特里樹中，每層為每個分支的名字子串依次分配整數(shù)編碼，例如＜yahoo，1＞和＜google，2＞表示yahoo和google的編碼分別為1和2。為了確保每層名字子串的編碼唯一性，圖8b合并了名字子串相同的編碼，例如合并＜google，2＞和＜google，3＞為＜google，4＞，即選擇每層編碼的最大整數(shù)值加1為其編碼。如圖8c所示，采用狀態(tài)遷移數(shù)組來查找子串特里樹和名字特里樹。由于采用特里樹查找NDN名字及其子串，該算法的查找性能是由特里樹的深度所決定，查找速率低且樹型數(shù)據(jù)結(jié)構(gòu)的更新開銷高。另外，由于狀態(tài)遷移數(shù)組采用指針來指示遍歷的節(jié)點位置，導(dǎo)致該算法的存儲空間開銷高。

圖8 NDN名字子串編碼及其狀態(tài)遷移數(shù)組Fig.8 NDN name component encoding and state transition arrays

Yuan等人［57］探討了NDN軟件實現(xiàn)CCNx的轉(zhuǎn)發(fā)數(shù)據(jù)結(jié)構(gòu)及其查找性能。圖9給出了CCNx的轉(zhuǎn)發(fā)數(shù)據(jù)結(jié)構(gòu)。為了支持快速查找和增量更新，CCNx采用哈希表在軟件上實現(xiàn)FIB，PIT和CS。如圖9所示，F(xiàn)IB，PIT和CS分別采用NPHT，PHT和CHT進(jìn)行查找，且這些哈希表采用鏈接方式來解決哈希沖突，即當(dāng)元素插入發(fā)生沖突時，該元素插入到該存儲桶的鏈接隊列中。FIB是基于最長名字前綴匹配的查找，而PIT和CS是基于精確匹配的查找。雖然CCNx可實現(xiàn)快速更新和查找，但是難以處理高速海量數(shù)據(jù)包轉(zhuǎn)發(fā)，特別是哈希表只適合PIT和CS的精確匹配，而難以有效支持FIB的最長名字前綴匹配。

圖9 CCNx的轉(zhuǎn)發(fā)數(shù)據(jù)結(jié)構(gòu)Fig.9 CCNx forwarding data structures

4 結(jié)論與展望

可編程虛擬化路由器是實現(xiàn)互聯(lián)網(wǎng)演進(jìn)與創(chuàng)新的核心網(wǎng)絡(luò)設(shè)備。本文綜述了可編程虛擬化路由器的FIB查找技術(shù)。首先，分析了FIB查找的性能與可伸縮性挑戰(zhàn)，要求解決多個FIB的吞吐量、存儲空間和增量更新等問題。其次，討論了多FIB融合的IP查找算法和基于NDN命名的非IP查找算法等研究進(jìn)展。

為了支持新型路由協(xié)議與轉(zhuǎn)發(fā)算法，可編程虛擬化路由器的FIB查找技術(shù)亟需解決以下問題。

1)多域 FIB查找。新型交換機(jī) OpenFlow［1］采用多域FIB查找算法，靈活支持?jǐn)?shù)據(jù)平面的轉(zhuǎn)發(fā)創(chuàng)新。該算法采用用戶自定義十元組定義FIB表項，并分割成多個子表進(jìn)行基于包分類(packet classification)的流水線查找。由于OpenFlow采用帶狀態(tài)(stateful)的FIB查找，即每個新到達(dá)數(shù)據(jù)包需要動態(tài)加載FIB表項，因此多域FIB查找算法面臨增量更新與快速查找之間折衷的問題。

2)NDN線速轉(zhuǎn)發(fā)。已有研究工作主要集中于基于軟件的NDN命名查找與轉(zhuǎn)發(fā)算法，難以實現(xiàn)10～40 Gbit/s線速數(shù)據(jù)包處理?；谟布腘DN命名查找與轉(zhuǎn)發(fā)是提升數(shù)據(jù)包處理性能的有效途徑，例如采用FPGA和TCAM相結(jié)合的實現(xiàn)方法。NDN名字長度不確定且無限長以及支持快速增量更新，因此基于硬件的算法面臨存儲空間縮減和快速更新等問題，即如何在存儲資源受限的硬件上實現(xiàn)存儲高效的NDN線速轉(zhuǎn)發(fā)，并支持快速更新。

［1］LEINER B M，KAHN R E，POSTEL J，et al.A brief history of the internet［J］.ACM SIGCOMM Computer Communication Review，2009，39(5):22-31.

［2］GENI［EB/OL］.［2012-10-11］.http://www.geni.org.

［3］FIND［EB/OL］.［2012-10-12］.http://www.nets-find.org.

［4］FIRE ［EB/OL］.［2012-10-12］.http://www.ict-firworks.eu.

［5］AisaFI［EB/OL］.［2012-10-12］.http://www.asiafi.net.

［6］NWGN［EB/OL］.［2012-10-12］.http://akari-project.nict.go.jp.

［7］FIF ［EB/OL］.［2012-10-12］.http://www.fif.kr.

［8］ANDERSON L，PETERSON L，SHENKER S，et al.Overcoming the internet impasse through virtualization［J］.Computer，2005，38(4):34-41.

［9］TURNER J S，TAYLOR D E.Diversifying the internet［C］//Global Telecommunications Conference，2005.GLOBECOM’05.IEEE.ST.Louis，MO:IEEE Conference Publications，2005(2):755-760.

［10］FEAMSTER N，CAO L，REXFORD J.How to lease the internet in your spare time［J］.ACM SIGCOMM Computer Communication Review，2007，37(1):61-64.

［11］CRHOWDHURY N，BOUTABA R.A survey of network virtualization［J］.Computer Networks，2010，54(5):862-876.

［12］MCKEOWN N，ANDERSON T，BALAKRISHNAN H，et al.OpenFlow:Enabling innovation in campus networks［J］.ACM SIGCOMM Computer Communication Review，2008，38(2):69-74.

［13］Cisco logical router［EB/OL］.［2012-09-18］.http://www.cisco.com.

［14］Juniper logical router［EB/OL］.［2012-10-08］.http://www.juniper.net.

［15］BAVIER A，F(xiàn)EAMSTER N，HUANG M，et al.In VINI veritas:Realistic and controlled network experimentation［J］.ACM SIGCOMM Computer Communication Review，2006，36(4):3-14.

［16］WANG Y，KELER E，BISKEBORN B，et al.Virtual routers on the move:Live router migration as a network management primitive［J］ACM SIGCOMM Computer Communication Review，2008，38(4):231-242.

［17］RUIZ-SANCHEZ M A，BIERSACK E W，DABBOUS W.Survey and taxonomy of IP address lookup algorithms［J］.IEEE Network，2001，15(2):8-23.

［18］ZHANG L，ESTRIN D，JACOBSON V，et al.Named data networking project［EB/OL］.［2012-10-08］.http://www.named-data.net/.

［19］EGI N，GREENHALGH A，HANDLEY M，et al.Towards high performance virtual routers on commodity hardware［C］//CoNEXT ＇08 Proceedings of the 2008 ACM CoNEXT Conference.New York，NY，USA:ACM，2008.

［20］KOHLER E，MORRIS R，CHEN B，et al.The click modular router［J］.ACM Transactions on Computer Systems，2000，18(3):263-297.

［21］DOBRESCU M，EGI N，ARGYRAKI K，et al.Route-Bricks:Exploiting parallelism to scale software routers［C］//SOSP ＇09，Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles.New York，NY，USA:ACM，2009:15-28.

［22］HAN S，JANG K，PARK K S，et al.PacketShader:A GPU-accelerated software router［C］//Proceedings of the ACM SIGCOMM 2010 conference.New York，NY，USA:ACM，2010:195-206.

［23］TURNER J，CROWLEY P，DEHART J，et al.Supercharging planetlab:A High performance，multi-applica-tion，overlay network platform［C］//Proceedings of the 2007 conference on Applications，technologies，architectures，and protocols for computer communications.New York，NY，USA:ACM，2007:85-96.

［24］CARLI L D，PAN Y，KUMAR A，et al.PLUG:Flexible lookup modules for rapid deployment of new protocols in high-speed routers［C］//Proceedings of the ACM SIGCOMM 2009 conference on Data communication.New York，NY，USA:ACM，2009:207-218.

［25］UNNIKRISHNAN D，VADLAMANI R，LIAO Y，A.et al.Scalable network virtualization using FPGAs［C］//Proceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays.New York，NY，USA:ACM，2010:219-228.

［26］XIE G，HE P，GUAN H，et al.PEARL:A programmable virtual router platform ［J］.IEEE Communication Magazine，Special Issue on Future Internet Architectures:Design and Deployment Perspectives，2011，49(7):71-77.

［27］ANWER M B，F(xiàn)EAMSTER N.Building a fast，virtualized data plane with programmable hardware［J］.ACM SIGCOMM Computer Communication Review，2010，40(1):75-82.

［28］ANWER M B，MOTIWALA M，TARIQ M，et al.SwitchBlade:A platform for rapid deployment of network protocols on programmable hardware［C］//Proceedings of the ACM SIGCOMM 2010 conference.New York，NY，USA:ACM，2010:183-194.

［29］ZANE F，NARLIKAR G，BASU A.CoolCAMs:Powerefficient TCAMs for forwarding engines［C］//INFOCOM 2003.Twenty-Second Annual Joint Conference of the IEEE Computer and Communications.IEEE Societies.［s.l.］:IEEE Conference Publications，2003(2):42-52.

［30］ZHENG K，HU C，LU H，et al.A TCAM-based distributed parallel IP lookup scheme and performance analysis［J］.IEEE/ACM Transactions on Networking，2006，14(4):863-875.

［31］LU W，SAHNI S.Low power TCAMs for very large forwarding tables ［J］.IEEE Transactions on Networking，2010，18(3):948-959.

［32］DHARMAPURIKAR S，KRISHNAMURTHY P，TAYLOR D E.Longest prefix matching using Bloom filters［C］//Proceedings of the 2003 conference on Applications，technologies，architectures，and protocols for computer communications.New York，NY，USA:ACM，2003:201-212.

［33］HASAN J，CADAMBI S，JAKKULA V，et al.Chisel:A storage-efficient collision-free hash-based network processing architecture［C］//Proceedings of the 33rd annual international symposium on Computer Architecture.New York，NY，USA:ACM，2006:203-215.

［34］YU H，MAHAPATRA R，BHUYAN L.A hash-based scalable IP lookup using Bloom and fingerprint filters［C］//Proceedings of the 17th annual IEEE International Conference on Network Protocols，2009.［s.l.］:IEEE Conference Publications，2009:264-273.

［35］BORDER A，MITZENMACHER M.Using multiple hash functions to improve IP lookups［C］//Proc INFOCOM.［s.l.］:IEEE Conference Publications，2001(3):1456-1463.

［36］SONG H，HAO F，KODIALAM M，et al.IPv6 lookups using distributed and load balanced bloom filters for 100Gbps core router line cards［C］//IEEE INFOCOM 2009 Proceeding.［s.l.］:IEEE Conference Publications，2009:2518-2526.

［37］BANDO M，CHAO H J.FlashTrie:hash-based prefixcompressed trie for IP route lookup beyond 100Gbps［C］//INFOCOM’01 Proceedings of the 29th conference on Information. Piscataway， NJ， USA:IEEE Press，2010:821-829.

［38］SRINIVASAN V，VARGHESE G.Fast address lookups using controlled prefix expansion［J］.ACM Transactions on Computing Systems，1999，17:1–40.

［39］DEGERMARK M，BRODNIK A，CARLSSON S，et al.Small forwarding tables for fast routing lookups［C］//SIGCOMM ＇97 Proceedings of the ACM SIGCOMM ＇97 conference on Applications，technologies，architectures，and protocols for computer communication.New York，NY，USA:ACM，1997:3-14.

［40］EATHERTON W，VARGHESE G，DITTIA Z.Tree bitmap:Hardware/software IP lookups with incremental updates［J］.ACM SIGCOMM Computer Communications.Review，2004，34(2):97-122.

［41］SONG H，TURNER J，LOCKWOOD J.Shape shifting tries for faster IP lookup［C］//ICNP’05 Proceeding of the 13th IEEE International Conference on Network Protocols.Woshington，DC，USA:IEEE Computer Society，2005:358-367.

［42］KUMAR S，TURNER J，CROWLEY P，et al.HEXA:Compact data structures for faster packet processing［C］//ICNP’07 Proceeding of the 15th IEEE International Conference on Network Protocol.Washington，DC，USA:IEEE Computer Society，2007:246-255.

［43］SONG H，KODIALAM M，HAO F，et al.Scalable IP lookups using shape graphs［C］//ICNP’09 Proceeding of the 17th IEEE International Conference on Network Protocol.Washington，DC，USA:IEEE Computer Socie-ty，2009:73-82.

［44］HUANG K，XIE G，LI Y，et al.Offset addressing approach to memory-efficient IP address lookup［C］//IEEE INFOCOM Mini-Conference.Shanghai:IEEE Conference Publications，2011:306-310.

［45］BASU A，NARLIKAR G.Fast incremental updates for pipelined forwarding engines［J］.IEEE/ACM Transactions on Networking(TON)，2005，13(3):690-703.

［46］HASAN J，VIJAYKUMAR T N.Dynamic pipelining:Making IP lookup truly scalable［C］//Proceedings of the 2005 conference on Applications，technologies，architectures，and protocols for computer communications.New York，NY，USA:ACM，2005:205-216.

［47］BABOESCU F，TULLSEN D M，ROSU G，et al.A tree based router search engine architecture with single port［C］//Proceedings of the 32nd annual international symposium on Computer Architecture. New York，NY，USA:ACM，2005:123-133.

［48］KUMAR S，BECCHI M，CROWLEY P，et al.CAMP:Fast and efficient IP lookup architecture［C］//Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems.New York，NY，USA:ACM，2006:51-60.

［49］JIANG W， WANG Q， PRASANNA V K.Beyond TCAMs:An SRAM-based Parallel multi-pipeline architecture for terabit IP lookup［C］//INFOCOM，2008.The 27th Conference on Computer Communications.IEEE.Phoenix，AX:IEEE Conference Publications，2008:1786-1794.

［50］FU J，REXFORD J.Efficient IP address lookup with a shared forwarding table for multiple virtual routers［C］//CoNEXT＇08 Proceedings of the 2008 ACM CoNEXT Conference.New York，NY，USA:ACM，2008.

［51］SONG H，KODIALAM M，HAO F，et al.Building scalable virtual routers with trie braiding［C］//INFOCOM＇10 Proceedings of the 29th conference on Information communications.Piscataway，NJ，USA:IEEE Press，2010:1442-1450.

［52］LE H，GANEGEDARA T，PRASANNA V K.Memoryefficient and scalable virtual routers using FPGA［C］//Proceedings of the 19th ACM/SIGDA international symposium on Field programmable gate array.New York，NY，USA:ACM，2011:257-266.

［53］LUO L，XIE G，XIE Y，et al.A hybrid IP lookup architecture with fast updates［C］//2012 Proceedings IEEE INFOCOM. Orland:IEEE ConferencePublications，2012:2435-2443.

［54］LUO L，XIE G，UHLIG S，et al.Towards TCAM-based scalable virtual routers［C］//Proceedings of the 8th international conference on Emerging networking experiments and technologies.New York，NY，USA:ACM，2012:73-84.

［55］LUO L，XIE G，SALAMATIAN K，et al.A trie merging approach with incremental updates for virtual routers［C］//IEEE INFOCOM，2013.(Accepted)

［56］WANG Y，HE K，DAI H，et al.Scalable name lookup in NDN using effective name component encoding［C］//Proceedings of the 2012 IEEE 32nd International Conference on Distributed Computing Systems.Washington，DC，USA:IEEE Computer Society，2012:688-697.

［57］YUAN H，SONG.T.CROWLEY P.Scalable NDN forwarding:Concepts，issues，and principles［C］//Computer Communications and Networks(ICCCN)，2012 21st International Conference on.［s.l.］:IEEE Conference Publications，2012.