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

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

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

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

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

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

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

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

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

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