基于集合分割的虛擬路由器轉發表查找的實現*

胡 穎，莊 雷

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

1 引言

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

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

（1）FIB 的存儲問題

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

（2）FIB 的更新問題

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

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

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

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

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

2 相關研究

目前關于解決轉發表的大容量存儲問題的研究主要包括以下幾點。

[5]提出將每個轉發表對應的特里樹合并成一個特里樹，來自不同轉發表但相同前綴的表項合并為一項，如果各特里樹的結構類似，即合并的表項居多，那么這種方案可以達到較好的效果。但如果各個特里樹結構相差較大，該方案不能達到預期效果。

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

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

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

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

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

3 相關技術

3.1 基于特里樹的集合分割

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

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

3.2 TCAM和SRAM

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

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

SRAM通常使用樹型數據結構。但是，基于特里樹的結構通常存儲量較大，更新開銷也較大。且由于前綴重疊，通常的遍歷樹算法不可用，FIB查找可能需要多次訪問內存（以下簡稱訪存）。對于較大的轉發表，存儲空間的限制成為主要約束。

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

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

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

3.3 轉發表合并

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

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

4 總體結構

圖1（a）顯示了將兩張轉發表合并的結果，圖 1（b）是合并轉發表對應的1 bit特里樹。

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

圖1 轉發表合并結果及其對應的特里樹

圖2 總體結構

本文的 TCAM 和 SRAM 結構如圖 3（a）、圖 3（b）所示。

由于已經假設各轉發表數據集相似，所以基于TCAM的存儲結構可以采用合并方式2。這種結構會降低命中率，因此如果沒有前面的假設，應對轉發表進行預處理（如采用多根技術），使得為0的表項較少。

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

5 快速增量更新

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

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

圖4 特里樹節點和下一跳指針數組的數據結構

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

輸入：更新前合并轉發表F0，待插入（刪除）記錄的前綴值P、所屬轉發表編號F及對應下一條值N。

輸出：更新后合并轉發表F0′。

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

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

6 實驗與分析

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

表1 對實際轉發表的分析

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

7 討論

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

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

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

8 結束語

本文分析了基于集合分割的虛擬路由器轉發表的實現，對幾種可能采取的技術進行了闡述，并采用了合并方式2來合并兩個集合，實驗結果表明，這種合并方式大大減少了存儲空間。并針對合并方式2帶來的弊端，在第一級SRAM中使用標志位，使得在查找過程中訪問下級SRAM的次數降為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