面向未來互聯(lián)網(wǎng)的高性能路由查找技術(shù)研究.pdf

1、互聯(lián)網(wǎng)產(chǎn)生于19世紀60年代，發(fā)展至今早已超出其設(shè)計初衷。面對紛繁復(fù)雜的應(yīng)用和日益增長的需求，傳統(tǒng)的以TCP/IP為核心的互聯(lián)網(wǎng)架構(gòu)在可擴展性、安全性和移動性等方面暴露出越來越多的問題。為從根本上解決這些問題，一些新型互聯(lián)網(wǎng)協(xié)議和架構(gòu)應(yīng)運而生。但無論如何變革，互聯(lián)網(wǎng)服務(wù)于信息互聯(lián)互通的本質(zhì)不會改變，數(shù)據(jù)包轉(zhuǎn)發(fā)都是核心操作。這其中，路由查找又扮演著至關(guān)重要的角色。所謂路由查找，就是根據(jù)數(shù)據(jù)包攜帶的路由信息在一組預(yù)定義的轉(zhuǎn)發(fā)規(guī)則中查找匹配項

2、以指導(dǎo)該數(shù)據(jù)包的轉(zhuǎn)發(fā)。查找速度、存儲效率和可擴展性是主要挑戰(zhàn)。本文立足當下，面向未來，圍繞現(xiàn)有的TCP/IP網(wǎng)絡(luò)和網(wǎng)絡(luò)功能虛擬化、軟件定義網(wǎng)絡(luò)、命名數(shù)據(jù)網(wǎng)絡(luò)這三個具有代表性的新型應(yīng)用場景和網(wǎng)絡(luò)架構(gòu)，針對路由查找這一核心問題進行深入研究，開展了七個工作，致力于查找引擎綜合性能的提升。
　　本文首先圍繞TCP/IP網(wǎng)絡(luò)中的路由查找，即IP地址查找（簡稱IP查找）展開研究。針對現(xiàn)有方案在壓縮存儲時難以兼顧更新和查找優(yōu)化的現(xiàn)狀，本文深入到

3、模型層面進行探究，提出了一種基于前綴拆分的并行查找模型。不僅能利用IP前綴間的局部相似性從根本上壓縮存儲，還能在模型層面提供并行操作的支持。此外，路由更新被成功分流，能減少大量無用操作、降低更新開銷。實驗表明，拆分模型以犧牲一定的片外存儲為代價，可換取片上存儲超90％的壓縮比，還能實現(xiàn)更新效率和查找性能的顯著提升。
　　在IP查找引擎的硬件部署平臺方面，基于可編程門陣列(FPGA)的流水線結(jié)構(gòu)正逐步成為首選。其中，均衡各流水級的存

4、儲開銷和子流水線間的負載是關(guān)鍵挑戰(zhàn)。現(xiàn)有方案需要付出較高的代價才能實現(xiàn)理想的平衡度，在大規(guī)模轉(zhuǎn)發(fā)表或IPv6的場景下表現(xiàn)差強人意。鑒于此，本文基于前綴拆分、子樹旋轉(zhuǎn)、聯(lián)合最優(yōu)步長計算等一系列平衡優(yōu)化，提出了一種存儲高效且平衡的雙向流水線結(jié)構(gòu)，在獲得與現(xiàn)有方案同等理想的平衡度時所需流水級的數(shù)量減少了75％～85.7％。此外，在查找延時、單次查找平均訪存、存儲效率、更新開銷以及多流水間的負載均衡等方面也都表現(xiàn)出了明顯的優(yōu)勢。
　　在軟

5、件平臺方面，基于圖形處理單元(GPU)的并行計算架構(gòu)發(fā)展迅速。雖然現(xiàn)有方案已經(jīng)實現(xiàn)實現(xiàn)O(1)的查找算法，但僅支持IPv4，且難以實現(xiàn)批量更新的完全并行處理。這就限制了更新性能，同時也導(dǎo)致系統(tǒng)吞吐率的不穩(wěn)定。本文先提出一種線索化的線段樹結(jié)構(gòu)及相應(yīng)的更新機制以解決批量更新完全并行的瓶頸，同時最大限度地消除冗余訪存，使更新效率提升近9倍。當現(xiàn)有方案的查找吞吐率因更新頻率增加而下降超50％時，該方案的吞吐率甚至只下降了4％。接著，本文進一步探

6、索查找加速以及對IPv6的支持，提出了一種基于GPU加速的多步長前綴樹結(jié)構(gòu)。通過緊湊的編碼設(shè)計和步長優(yōu)化來調(diào)整樹形，配合高效的線下/線上協(xié)同更新機制，再借助多流流水線實現(xiàn)優(yōu)化，不僅可實現(xiàn)每秒10億和6.5億次的IPv4/IPv6地址查找速度，還能在高頻更新下保持穩(wěn)定。
　　虛擬化路由器是實現(xiàn)網(wǎng)絡(luò)功能虛擬化的基礎(chǔ)設(shè)施，也是其核心理念的體現(xiàn)。在虛擬化路由器中，路由查找需處理多個轉(zhuǎn)發(fā)表的維護和查找問題（簡稱多表查找）?，F(xiàn)有方案通過預(yù)留存

7、儲位來管理虛擬路由器實例號(VID)，存在擴展性瓶頸。另一方面，目前尚沒有研究工作專門討論GPU加速多表查找。鑒于此，本文針對GPU加速的場景提出了一種新型數(shù)據(jù)結(jié)構(gòu)——TailTrie。引入有限狀態(tài)機實現(xiàn)VID的動態(tài)管理，再采用雙數(shù)組前綴樹進行壓縮，不僅將存儲開銷的增長趨勢由線性優(yōu)化為亞線性，還支持動態(tài)插入實例。借助GPU可在控制查找延時低于100μs的前提下實現(xiàn)億次每秒級的IPv4/IPv6地址查找。
　　在軟件定義網(wǎng)絡(luò)中，Op

8、enFlow交換機是核心基礎(chǔ)設(shè)施，采用流表來維護包處理規(guī)則。路由查找（即流表查找）需解決的關(guān)鍵問題是多域規(guī)則匹配。針對現(xiàn)有方案在規(guī)則域或者規(guī)則數(shù)增多時難以同時保持高時、空效率的現(xiàn)狀，本文提出了迭代降維定理，并以此為基礎(chǔ)設(shè)計了迭代哈希算法，可實現(xiàn)時、空高效且可擴展的多域規(guī)則匹配。實驗表明，相比于現(xiàn)有的決策樹算法，該算法存儲開銷減少80％，執(zhí)行規(guī)則匹配時能提速5倍以上。
　　在命名數(shù)據(jù)網(wǎng)絡(luò)中，路由查找涉及兩種包、三張表，但核心操作都是

9、名字查找。現(xiàn)有方案借助GPU加速來滿足線速要求，但數(shù)據(jù)拷貝和批處理導(dǎo)致的查找延時較大。鑒于此，本文另辟蹊徑，首次嘗試利用FPGA來加速名字查找，提出了層次化的對齊遷移數(shù)組結(jié)構(gòu)。先將名字前綴樹逐層轉(zhuǎn)化為一系列狀態(tài)遷移以提升存儲效率，然后引入多點探測、并行驗證的機制實現(xiàn)進一步存儲壓縮，最后根據(jù)前綴長度的分布規(guī)律完成流水線映射。實驗表明，相比于現(xiàn)有的GPU加速方案，該方案的存儲開銷可減少90％。此外，查找吞吐率略有提升，而查找延時下降了近3個