張昕怡，潘恒，謝高崗,3

專題：新型網(wǎng)絡(luò)技術(shù)

可編程網(wǎng)絡(luò)數(shù)據(jù)平面技術(shù)進(jìn)展

張昕怡1，潘恒2，謝高崗1,3

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

網(wǎng)絡(luò)數(shù)據(jù)平面執(zhí)行數(shù)據(jù)包處理轉(zhuǎn)發(fā)，是網(wǎng)絡(luò)性能的決定性因素之一。大帶寬、低時延、可持續(xù)演進(jìn)的網(wǎng)絡(luò)基礎(chǔ)設(shè)施需要構(gòu)建高效可編程的網(wǎng)絡(luò)數(shù)據(jù)平面。首先，介紹數(shù)據(jù)包處理轉(zhuǎn)發(fā)模型，并以此為基礎(chǔ)概述網(wǎng)絡(luò)數(shù)據(jù)平面在性能與可編程性面臨的關(guān)鍵挑戰(zhàn)。然后，從數(shù)據(jù)包查找算法理論與軟/硬件協(xié)同實(shí)現(xiàn)機(jī)制出發(fā)，詳細(xì)論述其基本思路及關(guān)鍵核心技術(shù)進(jìn)展以應(yīng)對上述關(guān)鍵挑戰(zhàn)。最后，探討高效可編程數(shù)據(jù)平面的未來發(fā)展趨勢與技術(shù)演進(jìn)路線。

網(wǎng)絡(luò)可編程數(shù)據(jù)平面；軟/硬件協(xié)同設(shè)計；數(shù)據(jù)包處理；網(wǎng)絡(luò)內(nèi)計算

0 引言

互聯(lián)網(wǎng)已成為人類社會的基礎(chǔ)設(shè)施，通過數(shù)據(jù)包查找轉(zhuǎn)發(fā)，實(shí)現(xiàn)人機(jī)物互聯(lián)。數(shù)據(jù)平面執(zhí)行數(shù)據(jù)包查找轉(zhuǎn)發(fā)，是網(wǎng)絡(luò)性能的決定性因素之一。4K/8K超高清視頻點(diǎn)播、增強(qiáng)現(xiàn)實(shí)/虛擬現(xiàn)實(shí)（augmented reality/virtual reality，AR/VR）及物聯(lián)網(wǎng)等應(yīng)用[1-3]的發(fā)展，對網(wǎng)絡(luò)提出大帶寬、廣連接和低時延等性能需求。受限于芯片器件工藝，僅通過硬件升級和設(shè)備堆疊無法滿足服務(wù)質(zhì)量需求。為了解決上述問題，軟件定義網(wǎng)絡(luò)（software defined network，SDN）、網(wǎng)絡(luò)切片、算網(wǎng)融合及新型網(wǎng)絡(luò)體系結(jié)構(gòu)被廣泛研究與應(yīng)用[4-6]。上述技術(shù)要求數(shù)據(jù)平面在保障高效轉(zhuǎn)發(fā)的同時，提供查找規(guī)則、匹配運(yùn)算、轉(zhuǎn)發(fā)隊列可編程能力，因此，網(wǎng)絡(luò)數(shù)據(jù)平面查找算法與實(shí)現(xiàn)機(jī)制都面臨新挑戰(zhàn)。

1 數(shù)據(jù)包處理轉(zhuǎn)發(fā)模型

數(shù)據(jù)平面的基本操作是數(shù)據(jù)包查找轉(zhuǎn)發(fā)：接收端口收到數(shù)據(jù)包后，解析數(shù)據(jù)包相關(guān)字段，匹配規(guī)則表；根據(jù)精確匹配、最長前綴查找或正則表達(dá)式匹配結(jié)果，執(zhí)行數(shù)據(jù)包修改、轉(zhuǎn)發(fā)或者丟棄等操作。不同的網(wǎng)絡(luò)設(shè)備功能具有不同的規(guī)則表與匹配操作。例如，交換機(jī)由媒體訪問控制（media access control，MAC）表實(shí)現(xiàn)精確匹配，路由器查找路由表執(zhí)行最長前綴匹配，防火墻查找五元組實(shí)現(xiàn)數(shù)據(jù)包分類，SDN交換機(jī)查找多級流表實(shí)現(xiàn)轉(zhuǎn)發(fā)，5G云核心網(wǎng)通過報文檢測規(guī)則（packet detection rule，PDR）、統(tǒng)一資源定位符（uniform resource locator, URL）規(guī)則匹配實(shí)現(xiàn)流量計費(fèi)。

數(shù)據(jù)包查找轉(zhuǎn)發(fā)是典型的維空間點(diǎn)定位問題，構(gòu)造最優(yōu)的查找決策樹已被證明是多項式復(fù)雜程度的非確定性完全（non-deterministic polynomial complete，NPC）問題[7]。IPv6的廣泛部署、規(guī)則表條目增加、網(wǎng)絡(luò)切片與虛擬化轉(zhuǎn)發(fā)表增加、SDN流表字段增加與高頻更新，對數(shù)據(jù)平面性能與可編程性提出新需求，而可編程性也進(jìn)一步對性能提出新挑戰(zhàn)。

1.1 數(shù)據(jù)平面性能

數(shù)據(jù)包查找模塊轉(zhuǎn)發(fā)速度將決定網(wǎng)絡(luò)設(shè)備的轉(zhuǎn)發(fā)速率、隊列長度與丟包率，是網(wǎng)絡(luò)性能的決定性因素之一。在5G/B5G網(wǎng)絡(luò)環(huán)境中，雖然無線側(cè)空口傳輸?shù)男阅艿玫酱蠓忍嵘?，但核心網(wǎng)處理能力和效率受限于數(shù)據(jù)包處理轉(zhuǎn)發(fā)的性能，成為網(wǎng)絡(luò)傳輸?shù)男阅芷款i。面對當(dāng)前網(wǎng)絡(luò)環(huán)境中業(yè)務(wù)流量、系統(tǒng)規(guī)模以及功能復(fù)雜性的增長，數(shù)據(jù)平面性能面臨以下挑戰(zhàn)。

●查找速度方面，大帶寬網(wǎng)絡(luò)需要數(shù)據(jù)包高速查找轉(zhuǎn)發(fā)。當(dāng)鏈路帶寬為100 Gbit/s時，按照最小以太網(wǎng)幀計算，線速數(shù)據(jù)包轉(zhuǎn)發(fā)吞吐量需達(dá)到約150 Mbit/s，即幀間時延約為7 ns。實(shí)際上，末級緩存（last level cache， LLC）的訪問通常需要約40 ns，若LLC未命中，訪問內(nèi)存則需要約100 ns，通用處理平臺上的實(shí)現(xiàn)線速轉(zhuǎn)發(fā)成為挑戰(zhàn)。

●存儲容量方面，目前骨干網(wǎng)路由器IPv4路由表項達(dá)到百萬級，IPv6路由表項達(dá)到十萬級；云計算平臺虛擬路由表規(guī)模達(dá)到千萬級；云化5G核心網(wǎng)需為數(shù)十萬用戶的并發(fā)會話獨(dú)立配置用戶策略，將在數(shù)據(jù)平面產(chǎn)生千萬級的規(guī)則。大規(guī)模規(guī)則需要大存儲空間，增加設(shè)備制造成本與能耗，也會因內(nèi)存墻的存在誘發(fā)訪存瓶頸，使系統(tǒng)整體處理性能下降。

●更新速度方面，軟件定義網(wǎng)絡(luò)與網(wǎng)絡(luò)功能虛擬化為網(wǎng)絡(luò)帶來極大的靈活性與可編程性，同時，網(wǎng)絡(luò)狀態(tài)和網(wǎng)絡(luò)功能將頻繁動態(tài)變化。在5G核心網(wǎng)和云數(shù)據(jù)中心，業(yè)務(wù)的多樣性加劇了網(wǎng)絡(luò)的動態(tài)性和不確定性，系統(tǒng)中規(guī)則更新的頻率大幅提升。異步更新會產(chǎn)生大量的查找錯誤，從而使重傳等嚴(yán)重影響傳輸性能的問題；同步更新則會直接阻塞查找進(jìn)程，降低整體處理性能。基于決策樹數(shù)據(jù)包分類算法具有高更新時間復(fù)雜度，要在保持高速查找的同時實(shí)現(xiàn)動態(tài)增量更新，挑戰(zhàn)巨大。

1.2 數(shù)據(jù)平面可編程性

互聯(lián)網(wǎng)體系結(jié)構(gòu)、協(xié)議與業(yè)務(wù)的持續(xù)創(chuàng)新需要可編程數(shù)據(jù)面提供執(zhí)行、部署與驗(yàn)證環(huán)境。早期的可編程數(shù)據(jù)面主要基于通用處理器平臺，數(shù)據(jù)包處理邏輯以軟件方式部署執(zhí)行，具有良好的靈活性與可編程性。近年來，雖然高性能輸入/輸出（input/output，I/O）架構(gòu)（DPDK[8]、Netmap[9]、PF_RING ZX[10]等）取得進(jìn)展，但通用CPU的數(shù)據(jù)包處理性能有限。基于可編程交換芯片[11]的網(wǎng)絡(luò)數(shù)據(jù)面雖然可提供部分基礎(chǔ)編程能力與T級處理能力，使用戶通過特定編程語言構(gòu)建復(fù)雜的網(wǎng)絡(luò)應(yīng)用，但仍面臨以下挑戰(zhàn)。

（1）統(tǒng)一抽象

基于可編程交換芯片的網(wǎng)絡(luò)數(shù)據(jù)面通常采用“Match-Action”流水線的抽象結(jié)構(gòu)，可實(shí)現(xiàn)無狀態(tài)網(wǎng)絡(luò)功能，但難以完整實(shí)現(xiàn)帶狀態(tài)的網(wǎng)絡(luò)業(yè)務(wù)，導(dǎo)致應(yīng)用范圍受限。如何在現(xiàn)有數(shù)據(jù)面抽象基礎(chǔ)之上進(jìn)一步延伸擴(kuò)展，構(gòu)建統(tǒng)一、完整的抽象模型，支撐帶復(fù)雜狀態(tài)數(shù)據(jù)包運(yùn)算，需要設(shè)計新的數(shù)據(jù)包處理抽象與范式。

（2）資源受限

可編程交換芯片的計算能力、存儲資源、數(shù)據(jù)面流水線等多維資源受限，限制了數(shù)據(jù)面的數(shù)據(jù)包處理能力，無法支持復(fù)雜的數(shù)據(jù)包操作。如何在空間固定且受限的交換芯片上放置更多的計算邏輯、存儲器件以及流水線結(jié)構(gòu)，不僅是芯片制造工藝所面臨的巨大挑戰(zhàn)，更是交換芯片核心算法設(shè)計與實(shí)現(xiàn)的系統(tǒng)性難題。

（3）安全威脅

網(wǎng)絡(luò)的開放性與可編程性會引入“人”的因素，將增加出錯的風(fēng)險，影響網(wǎng)絡(luò)的可靠性與穩(wěn)定性；同時，管控分離架構(gòu)易造成拒絕服務(wù)攻擊，導(dǎo)致轉(zhuǎn)發(fā)性能下降。如何對數(shù)據(jù)面部署的網(wǎng)絡(luò)策略進(jìn)行實(shí)時異常檢測與功能驗(yàn)證，對惡意網(wǎng)絡(luò)流量進(jìn)行安全隔離與處理，保障網(wǎng)絡(luò)數(shù)據(jù)面安全是一個關(guān)鍵性挑戰(zhàn)。

2 高效數(shù)據(jù)包查找算法

網(wǎng)絡(luò)數(shù)據(jù)包查找轉(zhuǎn)發(fā)是網(wǎng)關(guān)、交換機(jī)、路由器、防火墻等關(guān)鍵網(wǎng)絡(luò)設(shè)備的核心功能，其性能直接決定了相關(guān)設(shè)備的處理能力、成本以及穩(wěn)定性。隨著網(wǎng)絡(luò)帶寬的增長、網(wǎng)絡(luò)規(guī)模的擴(kuò)大以及網(wǎng)絡(luò)動態(tài)性的增加，現(xiàn)有方案難以滿足大帶寬、大容量、靈活動態(tài)的新需求。因此，創(chuàng)新查找轉(zhuǎn)發(fā)關(guān)鍵算法和實(shí)現(xiàn)機(jī)制，突破現(xiàn)有技術(shù)性能瓶頸，是實(shí)現(xiàn)高效網(wǎng)絡(luò)數(shù)據(jù)平面?zhèn)鬏斉c計算的關(guān)鍵。

2.1 最長前綴查找算法

最長前綴查找是路由器的基本操作，隨著骨干路由轉(zhuǎn)發(fā)信息庫（forwarding information base，F(xiàn)IB）的規(guī)模不斷擴(kuò)大和網(wǎng)絡(luò)帶寬的迅速增長，單域最長前綴查找算法需要不斷提升查找速率并降低路由轉(zhuǎn)發(fā)表存儲開銷。云計算虛擬路由器平臺由于多個虛擬路由器共存，存在多個FIB，需要在保證低存儲開銷的同時，提升查找與更新速度。隨著IPv6技術(shù)的廣泛部署，IP地址前綴長度從IPv4中的32 bit變?yōu)?28 bit，查找時間與存儲開銷進(jìn)一步增加。提升路由查找性能，可以基于算法理論構(gòu)建低存儲開銷與查找時間復(fù)雜度的算法，還可以利用規(guī)則的分布和特征優(yōu)化查找結(jié)構(gòu)。對于IPv4最長前綴查找，可以利用IP地址前綴規(guī)則非均勻分布特征和片上/片外存儲的性能特點(diǎn)，通過對查找流程和規(guī)則存儲拆分，實(shí)現(xiàn)存儲空間高效利用的同時達(dá)到高速的查找速率[12]；對于多虛擬路由表，可以通過挖掘規(guī)則前綴特征，設(shè)計高效的數(shù)據(jù)結(jié)構(gòu)和合并方案，實(shí)現(xiàn)面向虛擬路由器的高性能、支持快速更新、可擴(kuò)展的IP地址查找方法[13]；對于IPv6最長前綴查找，同樣可以基于規(guī)則集的分布，優(yōu)化查找數(shù)據(jù)結(jié)構(gòu)降低訪存次數(shù)，提升查找速率[14]。

2.2 數(shù)據(jù)包分類算法

數(shù)據(jù)包分類算法基于多域規(guī)則集（如五元組）對數(shù)據(jù)包進(jìn)行查找匹配，是防火墻、入侵檢測、負(fù)載均衡系統(tǒng)、虛擬專用網(wǎng)絡(luò)（virtual private network，VPN）等網(wǎng)絡(luò)設(shè)備的基本操作。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大和網(wǎng)絡(luò)功能的復(fù)雜化，規(guī)則的急劇增加使數(shù)據(jù)包分類算法面臨的存儲壓力和性能挑戰(zhàn)更加嚴(yán)峻。通過預(yù)先設(shè)定的方案劃分整個規(guī)則空間并構(gòu)造決策樹，能夠?qū)崿F(xiàn)查找結(jié)構(gòu)體的快速構(gòu)建[15-16]，但是由于忽略了規(guī)則的特征，構(gòu)建決策樹的過程可能產(chǎn)生規(guī)則的大規(guī)模復(fù)制進(jìn)而增加存儲開銷；此外，不同的決策樹算法在不同的規(guī)則集會出現(xiàn)較大的性能波動和差異。通過設(shè)計估算不同算法存儲開銷的評估預(yù)測模型[17]，基于規(guī)則特征動態(tài)選擇最優(yōu)的方案構(gòu)造決策樹，能夠顯著減少規(guī)則復(fù)制，降低存儲開銷，同時提升查找性能。

2.3 流表查找算法

流表查找算法本質(zhì)屬于多域規(guī)則匹配，只因軟件定義網(wǎng)絡(luò)與網(wǎng)絡(luò)功能虛擬化場景規(guī)則更新頻繁，需要流表查找算法能夠支持規(guī)則集的快速增量更新。傳統(tǒng)的流表查找算法基于哈希表[18]實(shí)現(xiàn)規(guī)則的高速更新，但是數(shù)據(jù)包查詢時需要遍歷哈希表，因此查詢速率緩慢。雖然基于預(yù)先設(shè)定的策略對哈希表進(jìn)行合并[19]可以減少哈希表的數(shù)目，但由于忽略了規(guī)則的特征，可能會產(chǎn)生較多的哈希沖突數(shù)從而增加驗(yàn)證時間，影響查詢速率。因此，如何在有效地減少哈希表的數(shù)目同時降低哈希沖突數(shù)，是實(shí)現(xiàn)高效流表查找算法的關(guān)鍵。要解決上述問題，一方面可以將合并哈希表產(chǎn)生的沖突數(shù)轉(zhuǎn)化為合并概率（即沖突數(shù)越大合并的概率越小），進(jìn)而指導(dǎo)哈希表的合并[20]；另一方面，可以利用人工智能中監(jiān)督學(xué)習(xí)的方法，通過線下篩選合并方案并完成訓(xùn)練模型，指導(dǎo)線上基于哈希表的查找結(jié)構(gòu)體的構(gòu)建，在減少哈希表數(shù)目的同時，有效控制哈希沖突概率，實(shí)現(xiàn)規(guī)則的高速增量更新[21]。

雖然軟件算法的創(chuàng)新始終是實(shí)現(xiàn)高效數(shù)據(jù)平面的技術(shù)路線之一，但算法的執(zhí)行效率與硬件體系結(jié)構(gòu)密切相關(guān)?；谟布w系結(jié)構(gòu)設(shè)計算法，能夠高效充分利用硬件資源從而提升數(shù)據(jù)平面性能。因此，通過軟/硬協(xié)同的方式實(shí)現(xiàn)高效可編程的網(wǎng)絡(luò)數(shù)據(jù)平面成為當(dāng)前研究的熱點(diǎn)。

3 軟/硬件協(xié)同實(shí)現(xiàn)機(jī)制

專用硬件平臺受限于芯片處理邏輯的設(shè)計，不同平臺的可編程性通常與性能成反比，硬件實(shí)現(xiàn)的性能與可編程性如圖1所示。在CPU通用軟件平臺上，CPU高度靈活，能夠?qū)崿F(xiàn)復(fù)雜計算場景的需求，但是CPU沒有針對數(shù)據(jù)包處理設(shè)計實(shí)現(xiàn)專用的加速邏輯，性能較硬件轉(zhuǎn)發(fā)設(shè)備差。此外，云平臺中CPU及內(nèi)存等資源由多業(yè)務(wù)共享競爭，無法保障數(shù)據(jù)平面中負(fù)責(zé)數(shù)據(jù)包處理轉(zhuǎn)發(fā)程序的性能?，F(xiàn)場可編程邏輯門陣列（field programmable gate array，F(xiàn)PGA）芯片內(nèi)集成大量的基本門電路以及存儲器，用戶通過更新FPGA配置文件定義門電路以及存儲器之間的連線，被廣泛用作硬件可編程加速平臺。網(wǎng)絡(luò)處理器（network processor，NP）通常由若干微碼處理器和若干硬件協(xié)處理器組成，可以基于微碼編程，同時能夠?qū)崿F(xiàn)高速數(shù)據(jù)包的處理。專用集成電路（application specific integrated circuit，ASIC）作為定制加速平臺，其硬件電路不可改變，因此也不具備可編程的能力。但是ASIC面向特定應(yīng)用場景定制開發(fā)，因此僅能夠在對應(yīng)的應(yīng)用場景發(fā)揮硬件平臺強(qiáng)勁的性能。

圖1 硬件實(shí)現(xiàn)的性能與可編程性

通過上述分析可知，要實(shí)現(xiàn)高性能且可編程的數(shù)據(jù)平面，需要將通用平臺的靈活性和可編程性與專用硬件的高效性深度融合，軟/硬件協(xié)同加速。

3.1 數(shù)據(jù)平面可編程

基于不同的數(shù)據(jù)平面架構(gòu)，通過開發(fā)高級編程語言能夠降低網(wǎng)絡(luò)數(shù)據(jù)平面編程門檻，為網(wǎng)絡(luò)數(shù)據(jù)平面的研究和發(fā)展帶來更多契機(jī)。Click[22]基于C++實(shí)現(xiàn)數(shù)據(jù)包在CPU中的處理邏輯，PX[23]則是面向FGPA平臺的數(shù)據(jù)包處理語言，而可編程協(xié)議無關(guān)報文處理（programming protocol- independent packet processors，P4）[24]作為一種協(xié)議無關(guān)的高級編程語言，能夠屏蔽可編程交換芯片底層硬件邏輯，基于芯片提供的接口對網(wǎng)絡(luò)數(shù)據(jù)平面進(jìn)行編程，目前應(yīng)用最為廣泛。P4通過基于高層抽象語言對數(shù)據(jù)包處理流程進(jìn)行自定義，實(shí)現(xiàn)對數(shù)據(jù)包處理流程邏輯即時編程的可重配置性，基于自定義的數(shù)據(jù)處理邏輯實(shí)現(xiàn)協(xié)議無關(guān)性，并且在代碼編寫過程中，P4無須關(guān)心底層設(shè)備實(shí)現(xiàn)細(xì)節(jié)，因而具備目標(biāo)設(shè)備無關(guān)性。借助P4帶來的數(shù)據(jù)平面編程能力，網(wǎng)絡(luò)研究人員可以實(shí)現(xiàn)路由器、防火墻等網(wǎng)絡(luò)設(shè)備功能與網(wǎng)絡(luò)協(xié)議，加速網(wǎng)絡(luò)創(chuàng)新。

同時，基于可編程芯片和P4，網(wǎng)絡(luò)具備初步的計算能力，這使傳統(tǒng)以CPU/GPU為中心的計算模式逐漸轉(zhuǎn)變?yōu)橐詳?shù)據(jù)為中心的計算模式，網(wǎng)絡(luò)與計算進(jìn)一步深度融合，網(wǎng)絡(luò)內(nèi)計算（in-network computing）這一新型技術(shù)得以興起。網(wǎng)絡(luò)內(nèi)計算的核心思想在于通過網(wǎng)絡(luò)側(cè)與端側(cè)的協(xié)同，使網(wǎng)絡(luò)數(shù)據(jù)在傳輸?shù)倪^程中邊轉(zhuǎn)發(fā)邊計算，從而降低端側(cè)計算壓力，提升網(wǎng)絡(luò)傳輸?shù)耐?。?dāng)前，網(wǎng)絡(luò)內(nèi)計算技術(shù)的發(fā)展主要集中在兩個方面。其一是對網(wǎng)絡(luò)算力的增強(qiáng)，從而使網(wǎng)絡(luò)具備處理更為復(fù)雜業(yè)務(wù)與數(shù)據(jù)的能力。例如，NetFC[25]設(shè)計了基于多表查詢的在網(wǎng)浮點(diǎn)數(shù)計算方法；P4AES[26]使網(wǎng)絡(luò)具有數(shù)據(jù)加解密能力；而ZipLine[27]實(shí)現(xiàn)了網(wǎng)絡(luò)數(shù)據(jù)的在網(wǎng)壓縮/解壓縮。其二是通過網(wǎng)絡(luò)內(nèi)計算技術(shù)加速傳統(tǒng)網(wǎng)絡(luò)功能或典型分布式應(yīng)用。例如，Beamer[28]將負(fù)載均衡部分功能實(shí)現(xiàn)在可編程交換機(jī)上，從而能夠處理40 Gbit/s的HTTP流量；SwRL[29]在可編程交換機(jī)上實(shí)現(xiàn)了高性能可擴(kuò)展流量限速器；NetCache[30]利用可編程交換機(jī)對網(wǎng)絡(luò)的key-value存儲應(yīng)用進(jìn)行緩存及快速響應(yīng)，其性能可以達(dá)到每秒20億次查詢；SwitchML[31]和ATP[32]提出了基于可編程交換機(jī)的網(wǎng)絡(luò)內(nèi)梯度聚合機(jī)制，加速分布式訓(xùn)練效率；NetSHa[33]將分布式搜索中的答案約減卸載到可編程交換機(jī)完成，極大提升檢索效率。

3.2 高性能網(wǎng)絡(luò)處理

傳統(tǒng)的數(shù)據(jù)包處理方式基于CPU中斷，即網(wǎng)卡驅(qū)動接收數(shù)據(jù)包后通過中斷通知CPU處理，然后由CPU拷貝數(shù)據(jù)并交給協(xié)議棧。隨著網(wǎng)絡(luò)帶寬的增加，海量數(shù)據(jù)包的處理將產(chǎn)生大量CPU中斷，使系統(tǒng)時延上升、吞吐量下降，同時降低基礎(chǔ)架構(gòu)的整體效率。DPDK[8]、Netmap[9]、PF_RING ZX[10]等架構(gòu)基于內(nèi)核旁路（kernal bypass）技術(shù)實(shí)現(xiàn)高性能I/O。其中，DPDK可提供高性能的數(shù)據(jù)包處理庫和用戶空間驅(qū)動程序，是目前主流的高性能I/O架構(gòu)。不同于傳統(tǒng)數(shù)據(jù)包處理使用CPU中斷方式，DPDK采用輪詢方式實(shí)現(xiàn)數(shù)據(jù)包處理過程。DPDK重載了網(wǎng)卡驅(qū)動，該驅(qū)動在收到數(shù)據(jù)包后不產(chǎn)生中斷通知CPU，而是將數(shù)據(jù)包通過零拷貝技術(shù)存入內(nèi)存，應(yīng)用層程序通過DPDK提供的接口直接從內(nèi)存讀取數(shù)據(jù)包。這種處理方式節(jié)省了CPU中斷時間、內(nèi)存拷貝時間，并向應(yīng)用層提供了簡單易行且高效的數(shù)據(jù)包處理方式。

（1）CPU指令優(yōu)化算法

通用平臺上的網(wǎng)絡(luò)數(shù)據(jù)平面的查找算法由軟件實(shí)現(xiàn)。算法或者數(shù)據(jù)結(jié)構(gòu)的優(yōu)化可以提升算法查找性能，進(jìn)而優(yōu)化網(wǎng)絡(luò)數(shù)據(jù)平面的處理能力。而算法的高效性與體系結(jié)構(gòu)密切相關(guān)，利用體系結(jié)構(gòu)特性或CPU指令進(jìn)一步優(yōu)化軟件算法。針對數(shù)據(jù)平面中的單域最長前綴查找算法，可基于CPU體系結(jié)構(gòu)和緩存調(diào)度特點(diǎn)，利用訪存局部性實(shí)現(xiàn)高通量算法。對基于決策樹的數(shù)據(jù)包分類算法，可利用CPU比特位操控指令PEXT[34]對每個樹節(jié)點(diǎn)制定有效的切割規(guī)則，構(gòu)建高效的查找數(shù)據(jù)結(jié)構(gòu)并提升查找速率。

（2）網(wǎng)卡卸載

智能網(wǎng)卡（ smart network interface card，Smart NIC）[35-38]通過在傳統(tǒng)以太網(wǎng)接口和硬件總線之間，嵌入具有計算和存儲功能的網(wǎng)絡(luò)處理器或現(xiàn)場可編程邏輯門陣列，使其具有高度可編程化定制的特點(diǎn)，提升計算和存儲能力。通過使用智能網(wǎng)卡協(xié)助CPU處理網(wǎng)絡(luò)負(fù)載（包括TCP卸載、VxLAN/GRE隧道報文卸載、IPSec[39]加/解密的卸載、防火墻卸載等），能夠有效減輕宿主機(jī)CPU負(fù)載。以IPSec在智能網(wǎng)卡上的卸載為例，IPSec是一組基于網(wǎng)絡(luò)層的安全通信協(xié)議族。通過對IP的分組進(jìn)行加密和認(rèn)證來保護(hù)IP的網(wǎng)絡(luò)傳輸協(xié)議簇，已部署于VPN、無線網(wǎng)絡(luò)和安全網(wǎng)絡(luò)虛擬化隧道。當(dāng)開啟IPSec功能后，IPSec處理模塊會在收到的數(shù)據(jù)包IP頭和高層協(xié)議頭之間插入經(jīng)復(fù)雜計算得到的IPSec頭。而隨著網(wǎng)絡(luò)帶寬的增加，頻繁的加/解密操作會消耗大量CPU資源，嚴(yán)重影響系統(tǒng)性能。通過將IPSec中的加/解密任務(wù)卸載到智能網(wǎng)卡，雖然部分操作仍需要在軟件側(cè)完成，但是利用智能網(wǎng)卡硬件優(yōu)勢能夠顯著提升系統(tǒng)性能。

面向數(shù)據(jù)中心的專用處理器（data processing unit，DPU）最早由硅谷創(chuàng)業(yè)公司Fungible[40]提出，英偉達(dá)公司（NVIDIA）在收購邁勒羅斯科技公司（Mellanox Technologies）后，推出BlueField系列DPU[41]。BlueField DPU在傳統(tǒng)智能網(wǎng)卡上嵌入CPU，通過卸載控制平面的任務(wù)和一些靈活復(fù)雜的數(shù)據(jù)平面任務(wù)，達(dá)到釋放宿主CPU資源、提升網(wǎng)絡(luò)性能的目的。以DPU加速虛擬網(wǎng)絡(luò)交換機(jī)（open vSwitch，OVS）[42]為例，不同于Mellanox ConnectX-5[43]在智能網(wǎng)卡實(shí)現(xiàn)相對簡單的可編程數(shù)據(jù)路徑，控制平面仍需要在宿主CPU處理。即當(dāng)收到報文后，檢查是否在快速路徑已緩存該類報文的處理規(guī)則，命中則直接按照對應(yīng)的規(guī)則執(zhí)行操作，否則傳送至軟件虛擬交換機(jī)。BlueField DPU中OVS[44]直接部署在其上ARM（advanced RISC machine）架構(gòu)的CPU中，而OVS中的快速路徑可卸載到網(wǎng)絡(luò)硬件加速器eSwitch，該卸載方案可降低數(shù)據(jù)面和控制面之間通信的時延，加速網(wǎng)絡(luò)數(shù)據(jù)平面的處理。

4 發(fā)展趨勢

4.1 數(shù)據(jù)包匹配算法

對于高效數(shù)據(jù)平面算法的實(shí)現(xiàn)，可以分別從優(yōu)化算法實(shí)現(xiàn)與算法理論創(chuàng)新兩個方面開展。

在優(yōu)化算法實(shí)現(xiàn)方面，由于規(guī)則集分布特性和流量特征影響算法性能，通過深入挖掘規(guī)則分布特性與流量特征優(yōu)化算法，能夠極大提升算法性能。隨著人工智能技術(shù)的發(fā)展與進(jìn)步，基于人工智能的技術(shù)實(shí)現(xiàn)流量和規(guī)則特征提取及算法優(yōu)化，是實(shí)現(xiàn)高效算法的關(guān)鍵解決思路和研究方向。對于高效算法的實(shí)現(xiàn)，除了分別從時間復(fù)雜度和空間復(fù)雜度優(yōu)化代碼的執(zhí)行效率和空間存儲，由于算法的執(zhí)行效率與硬件體系結(jié)構(gòu)密切相關(guān)，還可以進(jìn)一步從體系結(jié)構(gòu)、CPU指令執(zhí)行的角度實(shí)現(xiàn)算法與系統(tǒng)的深度融合。

在算法理論創(chuàng)新方面，通過針對具體的應(yīng)用場景設(shè)計新型數(shù)據(jù)結(jié)構(gòu)，能夠進(jìn)一步提升網(wǎng)絡(luò)性能。Sketch[45-46]通常用于數(shù)據(jù)平面測量，能夠在高速網(wǎng)絡(luò)環(huán)境中實(shí)時地存儲流量特征信息，并且僅占用較小的存儲空間，具備在理論上可證明的估計精度與內(nèi)存的平衡特性。Learned index[47-48]通常用于索引查詢，通過利用機(jī)器學(xué)習(xí)技術(shù)得到更好的范圍索引，使用機(jī)器學(xué)習(xí)模型代替?zhèn)鹘y(tǒng)的B樹索引，從而在實(shí)現(xiàn)存儲高效壓縮的同時保證較高的查詢速率。

優(yōu)化創(chuàng)新數(shù)據(jù)包匹配算法是大幅提升網(wǎng)絡(luò)數(shù)據(jù)平面性能的關(guān)鍵。如何在使網(wǎng)絡(luò)更加智能化的基礎(chǔ)上，更高效準(zhǔn)確地提取流量和規(guī)則特征，基于具體應(yīng)用場景對關(guān)鍵數(shù)據(jù)結(jié)構(gòu)進(jìn)行創(chuàng)新，將是網(wǎng)絡(luò)數(shù)據(jù)平面算法的設(shè)計思路和研究方向。

4.2 計算內(nèi)網(wǎng)絡(luò)

隨著云數(shù)據(jù)中心、虛擬化等技術(shù)的日趨成熟，虛擬服務(wù)器逐漸替代裸金屬服務(wù)器為不同客戶提供計算、存儲等差異化服務(wù)，達(dá)到高效利用不同類型資源的目的。單物理機(jī)或多物理機(jī)中的不同虛擬服務(wù)器之間需要通過虛擬網(wǎng)絡(luò)進(jìn)行互聯(lián)互通、協(xié)同計算。虛擬網(wǎng)絡(luò)的性能已逐漸成為影響協(xié)同計算效率的關(guān)鍵因素。

高性能虛擬化網(wǎng)絡(luò)的構(gòu)建需要從算法與系統(tǒng)兩個層面分別考量與設(shè)計。在算法層面上，需要設(shè)計靈活高效可擴(kuò)展的查找轉(zhuǎn)發(fā)機(jī)制與數(shù)據(jù)結(jié)構(gòu)，可針對不同網(wǎng)絡(luò)業(yè)務(wù)類型，快速確定網(wǎng)絡(luò)數(shù)據(jù)包的虛擬轉(zhuǎn)發(fā)路徑與轉(zhuǎn)發(fā)端口，提升轉(zhuǎn)發(fā)效率；在系統(tǒng)方面，需要設(shè)計高效的虛擬I/O與緩存機(jī)制，減少網(wǎng)絡(luò)數(shù)據(jù)包在虛擬轉(zhuǎn)發(fā)過程中的數(shù)據(jù)拷貝，提升整體的緩存命中率，提高系統(tǒng)性能。但無論是算法還是系統(tǒng)，需要充分挖掘新型網(wǎng)絡(luò)硬件的性能潛力，通過軟/硬協(xié)同設(shè)計，提升計算設(shè)備中的虛擬網(wǎng)絡(luò)性能。虛擬轉(zhuǎn)發(fā)、高效可靠虛擬I/O以及軟/硬協(xié)同系統(tǒng)設(shè)計架構(gòu)與關(guān)鍵算法是未來需要解決的問題。

4.3 網(wǎng)絡(luò)內(nèi)計算

隨著可編程網(wǎng)絡(luò)設(shè)備的不斷演進(jìn)與革新，特別是Mellanox智能網(wǎng)卡、Intel Tofino可編程交換機(jī)的出現(xiàn)，數(shù)據(jù)包在網(wǎng)絡(luò)傳輸過程中被計算、處理和轉(zhuǎn)發(fā)。受限于物理極限，網(wǎng)絡(luò)內(nèi)單點(diǎn)設(shè)備的計算能力、片上存儲、流水線stage等多維資源受限，無法滿足復(fù)雜業(yè)務(wù)的網(wǎng)絡(luò)內(nèi)計算需求，網(wǎng)絡(luò)內(nèi)多點(diǎn)協(xié)同計算成為算網(wǎng)融合發(fā)展的一個重要趨勢。

網(wǎng)絡(luò)內(nèi)協(xié)同計算的核心在于自動確定數(shù)據(jù)包的計算內(nèi)容、邏輯與位置，在滿足靈活性的基礎(chǔ)上保障高性能。為此，構(gòu)建一個面向服務(wù)定制的數(shù)據(jù)包計算框架顯得尤為重要。該計算框架需要對差異化業(yè)務(wù)進(jìn)行全等級多粒度的分析與抽象，形成數(shù)據(jù)包計算基本操作單元能力集基于開放的編程接口及模板，不同網(wǎng)絡(luò)業(yè)務(wù)可通過數(shù)據(jù)包計算基本操作單元進(jìn)行靈活、快速構(gòu)建，利用框架的運(yùn)行時系統(tǒng)進(jìn)行編譯、解析，并將數(shù)據(jù)包計算基本操作單元精準(zhǔn)映射到底層異構(gòu)平臺進(jìn)行高效執(zhí)行。數(shù)據(jù)包計算統(tǒng)一編程模型與編程語言、數(shù)據(jù)包計算實(shí)時編譯系統(tǒng)以及異構(gòu)數(shù)據(jù)面高效實(shí)現(xiàn)機(jī)制等是亟待解決的問題。

5 結(jié)束語

高效可編程數(shù)據(jù)平面是重要的新型組網(wǎng)實(shí)現(xiàn)技術(shù)。本文介紹了可編程數(shù)據(jù)面的轉(zhuǎn)發(fā)模型及面臨的關(guān)鍵性挑戰(zhàn)，梳理了高效數(shù)據(jù)包查找算法與軟/硬件協(xié)同實(shí)現(xiàn)機(jī)制等不同解決途徑的技術(shù)路線及發(fā)展趨勢。隨著可編程網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)數(shù)據(jù)面能力得到極大提升，將從傳統(tǒng)“傳輸管道”逐漸向以“數(shù)據(jù)包計算”為核心的傳算一體執(zhí)行平臺演進(jìn)。因此，構(gòu)建統(tǒng)一的數(shù)據(jù)包計算模型、框架與實(shí)現(xiàn)機(jī)制，滿足數(shù)據(jù)包處理轉(zhuǎn)發(fā)按照業(yè)務(wù)負(fù)載在網(wǎng)絡(luò)與計算內(nèi)自適應(yīng)執(zhí)行是未來可編程數(shù)據(jù)面發(fā)展的重要方向之一。

[1] AGIWAL M, ROY A, SAXENA N. Next generation 5G wireless networks: a comprehensive survey[J]. IEEE Communications Surveys & Tutorials, 2016, 18(3): 1617-1655.

[2] NIGHTINGALE J, SALVA-GARCIA P, CALERO J M A, et al. 5G-QoE: QoE modelling for ultra-HD video streaming in 5G networks[J]. IEEE Transactions on Broadcasting, 2018, 64(2): 621-634.

[3] SIRIWARDHANA Y, PORAMBAGE P, LIYANAGE M, et al. A survey on mobile augmented reality with 5G mobile edge computing: architectures, applications, and technical aspects[J]. IEEE Communications Surveys & Tutorials, 2021, 23(2): 1160-1192.

[4] MCKEOWN N, ANDERSON T, BALAKRISHNAN H, et al. OpenFlow[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 69-74.

[5] HONG C Y, MANDAL S, AL-FARES M, et al. B4 and after: managing hierarchy, partitioning, and asymmetry for availability and scale in Google's software-defined WAN[C]// Proceedings of SIGCOMM '18: Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. [S.l:s.n.], 2018: 74-87.

[6] HAN B, GOPALAKRISHNAN V, JI L S, et al. Network function virtualization: challenges and opportunities for innovations[J]. IEEE Communications Magazine, 2015, 53(2): 90-97.

[7] HYAFIL L, RIVEST R L. Constructing optimal binary decision trees is NP-complete[J]. Information Processing Letters, 1976, 5(1): 15-17.

[8] DPDK. Developer quick start guide[EB]. 2022.

[9] RIZZO L. Netmap: a novel framework for fast packet I/O[C]// Proceedings of 21st USENIX Security Symposium. [S.l.:s.n.]. 2012:101-112.

[10] Ntop. PF_RING: high-speed packet capture, filtering and analysis[EB]. 2022.

[11] Intel. 探索英特爾? 智能結(jié)構(gòu)處理器的強(qiáng)大功能[EB]. 2022.

INTEI. Discover the power of the Intel? intellight fabric pracessor[EB]. 2022.

[12] YANG T, XIE G G, LI Y B, et al. Guarantee IP lookup performance with FIB explosion[C]//SIGCOMM '14: Proceedings of the 2014 ACM Conference on SIGCOMM. New York: ACM Press, 2014: 39-50.

[13] LUO L Y, XIE G G, SALAMATIAN K, et al. A trie merging approach with incremental updates for virtual routers[J]. 2013 Proceedings IEEE INFOCOM, 2013: 1222-1230.

[14] ZHANG C Y, XIE G G. Using XorOffsetTrie for high-performance IPv6 lookup in the backbone network[J]. Computer Communications, 2022(181): 438-445.

[15] VAMANAN B, VOSKUILEN G, VIJAYKUMAR T. EffiCuts: optimizing packet classification for memory and throughput[J]. ACM SIGCOMM Computer Communication Review, 2010, 40(4): 207-218.

[16] YINGCHAREONTHAWORNCHAI S, DALY J, LIU A X, et al. A sorted-partitioning approach to fast and scalable dynamic packet classification[J]. IEEE/ACM Transactions on Networking, 2018, 26(4): 1907-1920.

[17] HE P, XIE G G, SALAMATIAN K, et al. Meta-algorithms for software-based packet classification[C]//Proceedings of 2014 IEEE 22nd International Conference on Network Protocols. Piscataway: IEEE Press, 2014: 308-319.

[18] SRINIVASAN V, SURI S, VARGHESE G. Packet classification using tuple space search[C]//Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication - SIGCOMM '99. New York: ACM Press, 1999.

[19] DALY J, BRUSCHI V, LINGUAGLOSSA L, et al. TupleMerge: fast software packet processing for online packet classification[J]. IEEE/ACM Transactions on Networking, 2019, 27(4): 1417-1431.

[20] ZHANG X Y, SALAMATIAN K, XIE G G. Improving open virtual switch performance through tuple merge relaxation in software defined networks[J]. IEEE Transactions on Network and Service Management, 5592(99): 1.

[21] ZHANG X Y, XIE G G, WANG X, et al. Fast online packet classification with convolutional neural network[J]. IEEE/ACM Transactions on Networking, 2021, 29(6): 2765-2778.

[22] KOHLER E, MORRIS R, CHEN B J, et al. The click modular router[J]. ACM Transactions on Computer Systems, 2000, 18(3): 263-297.

[23] BREBNER G, JIANG W R. High-speed packet processing using reconfigurable computing[J]. IEEE Micro, 2014, 34(1): 8-18.

[24] BOSSHART P, DALY D, GIBB G, et al. p4[J]. ACM SIGCOMM Computer Communication Review, 2014, 44(3): 87-95.

[25] CUI P L, PAN H, LI Z Y, et al. NetFC: enabling accurate floating-point arithmetic on programmable switches[C]//Proceedings of 2021 IEEE 29th International Conference on Network Protocols. Piscataway: IEEE Press, 2021: 1-11.

[26] CHEN X Q. Implementing AES encryption on programmable switches via scrambled lookup tables[C]//SPIN '20: Proceedings of the Workshop on Secure Programmable Network Infrastructure. [S.l:s.n.], 2020: 8-14.

[27] VAUCHER S, YAZDANI N, FELBER P, et al. ZipLine: in-network compression at line speed[C]//Proceedings of the 16th International Conference on emerging Networking EXperiments and Technologies. [S.l.:s.n.], 2020: 399-405.

[28] OLTEANU V, AGACHE A, VOINESCU A, et al. Stateless datacenter load-balancing with beamer[C]//Proceedings of 15th USENIX Symposium on Networked Systems Design and Implementation. [S.l.:s.n.], 2018: 125-139.

[29] HE Y C, WU W F, WEN X M, et al. Scalable on-switch rate limiters for the cloud[C]//Proceedings of IEEE INFOCOM 2021 - IEEE Conference on Computer Communications. Piscataway: IEEE Press, 2021: 1-10.

[30] JIN X, LI X Z, ZHANG H Y, et al. NetCache: balancing key-value stores with fast in-network caching[C]//Proceedings of the 26th Symposium on Operating Systems Principles. New York: ACM Press, 2017.

[31] SAPIO A, CANINI M, HO C Y, et al. Scaling distributed machine learning with in-network aggregation[EB]. 2019.

[32] LAO C, LE Y F, MAHAJAN K, et al. ATP: In-network Aggregation for Multi-tenant Learning[C]//Proceedings of 18th USENIX Symposium on Networked Systems Design and Implementation. [S.l.:s.n.], 2021: 741-761.

[33] ZHANG P H, PAN H, LI Z Y, et al. Accelerating LSH-based distributed search with in-network computation[C]//Proceedings of IEEE INFOCOM 2021 - IEEE Conference on Computer Communications. Piscataway: IEEE Press, 2021: 1-10.

[34] INTEL. Development reference guides:_pext_u32/64[EB]. 2022.

[35] MA X X, YAN, F, WANG Z, et al. Survey on smart network interface card[J]. Journal of Computer Research and Development. 2022, 59(1): 1-21.

[36] INTEL.700 series network adapters[EB]. 2022.

[37] NETRONOME. Agilio open vSwitch TC user guide[EB]. 2022.

[38] NAPATECH. Napatech smart NIC solution for hardware offload[EB]. 2022.

[39] FRANKEL S, KRISHNAN S. IP security and internet key exchange document roadmap RFC 6071[EB]. 2011.

[40] FUNGIBLE . The Fungible data processing unit[EB]. 2022.

[41] NVIDIA. NVIDIA bluefield data processing units[EB]. 2022.

[42] PFAFF B, PETTIT J, KOPONEN T, et al. The design and implementation of open vswitch[C]//Proceedings of 12th USENIX Symposium on Networked Systems Design and Implementation. [S.l.:s.n.], 2015: 117-130.

[43] NVIDIA. OVS offload using ASAP2 direct[EB]. 2022.

[44] NVIDIA. Virtual switch on bluefield smart NIC[EB]. 2022.

[45] CORMODE G, MUTHUKRISHNAN S. An improved data stream summary: the count-Min sketch and its applications[J]. Journal of Algorithms, 2005, 55(1): 58-75.

[46] NAMKUNG H, LIU Z X, KIM D, et al. SketchLib: enabling efficient sketch-based monitoring on programmable switches[C]//Proceedings of 19th USENIX Symposium on Networked Systems Design and Implementation. [S.l.:s.n.], 2022: 743-759.

[47] KRASKA T, BEUTEL A, CHI E H, et al. The case for learned index structures[C]//Proceedings of the 2018 International Conference on Management of Data. New York: ACM Press, 2018.

[48] MARCUS R, ZHANG E, KRASKA T. CDFShop: exploring and optimizing learned index structures[C]//Proceedings of SIGMOD '20: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. New York: ACM Press, 2020: 2789-2792.

Progress in programmable network data plane

ZHANG Xinyi1, PAN Heng2, XIE Gaogang1,3

1. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190,China 2.Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190,China 3.University of Chinese Academy of Sciences, Beijing 100049,China

Network data plane performs packet processing and forwarding, which is one of the core factors determining the network performance. High bandwidth, low latency and rapid evolution of the network infrastructure require building an efficient and programmable network data plane. The packet processing and forwarding model was firstly introduced, and on this basis, the challenges of the network data plane in the performance and programmability were outlined. Then the basic ideas and core technology progress were elaborated to deal with the above challenges by analyzing the theory of packet processing algorithms and hardware-software codesign implementations. Finally, the trend and technical route of constructing an efficient programmable data plane were discussed.

programmable network data plane, hardware-software codesign, packet processing, in-network computing

The National Key Research and Development Program of China (No.2019YFB1802800)

TP393

A

10.11959/j.issn.1000?0801.2022131

2022?04?30；

2022?06?07

國家重點(diǎn)研發(fā)計劃項目（No.2019YFB1802800）

張昕怡（1992? ），女，博士，中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心在站博士后，主要研究方向?yàn)橛嬎銠C(jī)網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)、高性能網(wǎng)絡(luò)數(shù)據(jù)平面。

潘恒（1990?），男，博士，中國科學(xué)院計算技術(shù)研究所副研究員，主要研究方向?yàn)榭删幊叹W(wǎng)絡(luò)與系統(tǒng)。

謝高崗（1974?），男，博士，中國科學(xué)院計算機(jī)網(wǎng)絡(luò)信息中心研究員，中國科學(xué)院大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橛嬎銠C(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)與系統(tǒng)。