命名數(shù)據(jù)網(wǎng)絡(luò)包處理流程性能改進(jìn)

于廣路

摘要：互聯(lián)網(wǎng)用戶(hù)對(duì)數(shù)據(jù)的內(nèi)容感興趣，而并不關(guān)心它的位置在什么地方。但是，當(dāng)前的客戶(hù)端/服務(wù)器架構(gòu)仍然需要一個(gè)請(qǐng)求被定向到特定的服務(wù)器來(lái)獲取響應(yīng)。命名數(shù)據(jù)網(wǎng)絡(luò)（NDN）是可以滿(mǎn)足這種以?xún)?nèi)容為需求的全新的網(wǎng)絡(luò)模式，這種網(wǎng)絡(luò)的轉(zhuǎn)發(fā)決策是基于內(nèi)容的名稱(chēng)而不是IP地址，并很好的解決了當(dāng)前TCP/IP網(wǎng)絡(luò)設(shè)計(jì)上的缺陷。本文將會(huì)從微觀(guān)架構(gòu)探索NDN網(wǎng)絡(luò)包處理流程中執(zhí)行流水線(xiàn)的執(zhí)行情況，并分析因?yàn)樵L(fǎng)存帶來(lái)的流水線(xiàn)暫停的性能瓶頸問(wèn)題，最終提出了兩種指令預(yù)取的策略來(lái)提高CPU緩存命中率和系統(tǒng)吞吐量。

關(guān)鍵詞：命名數(shù)據(jù)網(wǎng)絡(luò);NDN;指令流水;數(shù)據(jù)預(yù)取

一、命名數(shù)據(jù)網(wǎng)絡(luò)的意義。

命名數(shù)據(jù)網(wǎng)絡(luò)（Named Data Network，NDN）^[1]是將內(nèi)容的名字作為網(wǎng)絡(luò)轉(zhuǎn)發(fā)的核心信息，與當(dāng)前的IP網(wǎng)絡(luò)對(duì)比，NDN不再使用特定的IP地址，而是具有層次結(jié)構(gòu)的內(nèi)容的名字進(jìn)行數(shù)據(jù)的發(fā)送和獲取，NDN路由也不再按照IP地址進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)，而是根據(jù)名字進(jìn)行路由轉(zhuǎn)發(fā)，這種全新的網(wǎng)絡(luò)并不限制對(duì)于特定的名字是由哪個(gè)主機(jī)來(lái)提供數(shù)據(jù)，也不需要知道內(nèi)容的提供者是誰(shuí)，只需要將需要獲取的內(nèi)容以名字為核心封裝為興趣包發(fā)送到網(wǎng)絡(luò)中，然后等待數(shù)據(jù)的返回。通過(guò)這種與IP主機(jī)網(wǎng)絡(luò)完全不同的網(wǎng)絡(luò)架構(gòu)相比，可以獲取如下優(yōu)點(diǎn)：（i）路由節(jié)點(diǎn)緩存數(shù)據(jù)可以減少網(wǎng)絡(luò)負(fù)載和延遲;（ii）數(shù)據(jù)包經(jīng)過(guò)簽名更加安全;（iii）不再固定地址，具有更好的移動(dòng)性;（iv）減少了以?xún)?nèi)容的應(yīng)用層的通信復(fù)雜度。

命名數(shù)據(jù)網(wǎng)絡(luò)作為下一代的網(wǎng)絡(luò)架構(gòu)來(lái)設(shè)計(jì)，是要總結(jié)最近幾十年網(wǎng)絡(luò)模式實(shí)踐中出現(xiàn)的一些問(wèn)題并加以解決。其中該網(wǎng)絡(luò)最大的特點(diǎn)就是路由節(jié)點(diǎn)不再單純的只做存儲(chǔ)轉(zhuǎn)發(fā)，而且加入了數(shù)據(jù)包緩存的能力，這樣對(duì)于相同的請(qǐng)求，可以從距離請(qǐng)求方最近一個(gè)緩存了數(shù)據(jù)的路由節(jié)點(diǎn)返回請(qǐng)求的數(shù)據(jù)包，網(wǎng)絡(luò)請(qǐng)求可以立即結(jié)束，網(wǎng)絡(luò)鏈路短，提高了內(nèi)容資源的重用性，避免了網(wǎng)絡(luò)中傳輸大量相同的數(shù)據(jù)，因而可以提高整個(gè)網(wǎng)絡(luò)的吞吐量和資源的利用率。

盡管NDN這種全新的網(wǎng)絡(luò)架構(gòu)提供了非常好的好處，但是部署實(shí)施確是遇到了最大的挑戰(zhàn)，如何克服IP網(wǎng)絡(luò)向NDN網(wǎng)絡(luò)的過(guò)渡和轉(zhuǎn)換是不得不面對(duì)的問(wèn)題。雖然網(wǎng)絡(luò)功能虛擬化（NFV）給命名數(shù)據(jù)網(wǎng)絡(luò)的部署實(shí)施提供了一種機(jī)會(huì)^[2]，可以避免現(xiàn)有NDN網(wǎng)絡(luò)部署需要對(duì)大規(guī)?；A(chǔ)設(shè)施的升級(jí)，但是這種機(jī)會(huì)的前提是需要設(shè)計(jì)出一個(gè)高性能的，穩(wěn)健的命名數(shù)據(jù)網(wǎng)絡(luò)軟件路由，可以運(yùn)行在現(xiàn)有的商用硬件平臺(tái)上，并提供高效的路由轉(zhuǎn)發(fā)性能，使得NDN的實(shí)現(xiàn)不再只停留在實(shí)驗(yàn)的階段。

二、命名數(shù)據(jù)網(wǎng)絡(luò)的數(shù)據(jù)結(jié)構(gòu)和包處理流程。

命名數(shù)據(jù)網(wǎng)絡(luò)主要有興趣包（Interest package）和數(shù)據(jù)包（Data package）兩種數(shù)據(jù)報(bào)文類(lèi)型，其中，名字在興趣包和數(shù)據(jù)包是都存在的，相同名字的興趣包請(qǐng)求相同名字的數(shù)據(jù)包，一個(gè)是發(fā)起數(shù)據(jù)請(qǐng)求的時(shí)候由消費(fèi)方發(fā)送興趣包，另一個(gè)是由網(wǎng)絡(luò)中擁有相同名字?jǐn)?shù)據(jù)的節(jié)點(diǎn)進(jìn)行相應(yīng)的數(shù)據(jù)包。

NDN網(wǎng)絡(luò)的轉(zhuǎn)發(fā)機(jī)制相對(duì)比IP網(wǎng)絡(luò)單純的路由轉(zhuǎn)發(fā)機(jī)制是要復(fù)雜一些的，因?yàn)榭紤]到了數(shù)據(jù)的緩存。首先內(nèi)容的消費(fèi)者會(huì)根絕需要獲取的內(nèi)容名字來(lái)構(gòu)造興趣包，然后會(huì)將該興趣包在網(wǎng)絡(luò)內(nèi)進(jìn)行廣播，當(dāng)路由節(jié)點(diǎn)接收到該興趣包的時(shí)候，路由節(jié)點(diǎn)需要首先查詢(xún)興趣轉(zhuǎn)發(fā)表（Pending Interest Table，PIT），然后查詢(xún)內(nèi)容緩存（Content Store，CS），當(dāng)沒(méi)有緩存數(shù)據(jù)的時(shí)候，會(huì)通過(guò)查詢(xún)路由轉(zhuǎn)發(fā)表（Forwarding Information Base，F(xiàn)IB）來(lái)確定轉(zhuǎn)發(fā)端口。在NDN網(wǎng)絡(luò)中的FIB是與IP網(wǎng)絡(luò)中的FIB相類(lèi)似的，他們都包含了名字（IP地址）和轉(zhuǎn)發(fā)端口的映射關(guān)系，并根據(jù)路由協(xié)議來(lái)對(duì)FIB進(jìn)行生成和更新，該數(shù)據(jù)結(jié)構(gòu)是路由轉(zhuǎn)發(fā)的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，并且轉(zhuǎn)發(fā)端口并不限制單出口，可以像多個(gè)出口進(jìn)行路由的轉(zhuǎn)發(fā)。當(dāng)有數(shù)據(jù)包到達(dá)的時(shí)候，會(huì)按照一定的策略將數(shù)據(jù)緩存在內(nèi)容緩存（CS）中，這樣當(dāng)有大量請(qǐng)求相同名字的興趣包到達(dá)的時(shí)候可以第一時(shí)間將CS中緩存的數(shù)據(jù)發(fā)送給請(qǐng)求側(cè)，快速的完成網(wǎng)絡(luò)的請(qǐng)求，而不需要像IP網(wǎng)絡(luò)那樣，每一個(gè)請(qǐng)求都只限定在端對(duì)端的通信范圍內(nèi)，無(wú)法復(fù)用相同的相應(yīng)數(shù)據(jù)。

三、分析數(shù)據(jù)包處理流程的性能瓶頸。

指令預(yù)取是為了隱藏CPU指令周期中因?yàn)樾枰L(fǎng)問(wèn)內(nèi)存數(shù)據(jù)導(dǎo)致流水線(xiàn)中斷的關(guān)鍵技術(shù)。因此需要分析在網(wǎng)絡(luò)數(shù)據(jù)包處理流程中因?yàn)槟男┰L(fǎng)存操作導(dǎo)致了CPU流水線(xiàn)中斷的情況。

在NDN網(wǎng)絡(luò)中，存儲(chǔ)在內(nèi)存上的數(shù)據(jù)有PIT、CS存儲(chǔ)名字的哈希表，F(xiàn)IB中用于最長(zhǎng)前綴匹配而設(shè)計(jì)的布隆過(guò)濾器和哈希表，對(duì)內(nèi)存的訪(fǎng)問(wèn)主要就是哈希表自身和哈希表中的元素。因此知道轉(zhuǎn)發(fā)線(xiàn)程何時(shí)訪(fǎng)問(wèn)這些數(shù)據(jù)結(jié)構(gòu)地址就變得非常重要。圖1顯示了NDN網(wǎng)絡(luò)中興趣包和數(shù)據(jù)包的典型流程。在圖中所示的是興趣包和數(shù)據(jù)包前后到達(dá)的時(shí)候，CPU處理的指令流程。接下來(lái)使用序號(hào)1表示興趣包，序號(hào)2表示數(shù)據(jù)包。同時(shí)因?yàn)樘幚砼d趣包和數(shù)據(jù)包的指令流程是最長(zhǎng)的，因此選擇這2個(gè)包來(lái)進(jìn)行分析。從圖中可以看出，當(dāng)興趣包到達(dá)的時(shí)候，需要訪(fǎng)問(wèn)PIT、CS數(shù)據(jù)結(jié)構(gòu)的哈希表，F(xiàn)IB的哈希表也需要訪(fǎng)問(wèn)，但是需要在布隆過(guò)濾器計(jì)算之后才得出需要訪(fǎng)問(wèn)的哈希表的位置。接著根據(jù)數(shù)據(jù)包的名字搜索CS來(lái)判斷是否已經(jīng)緩存了該名字的數(shù)據(jù)，當(dāng)CS不會(huì)存的時(shí)候需要搜索PIT是否已經(jīng)存在該名字的記錄，然后會(huì)PIT進(jìn)行修改。如果通過(guò)FIB進(jìn)行名字前綴最長(zhǎng)匹配，找到輸出端口然后進(jìn)行轉(zhuǎn)發(fā)。同時(shí)，需要注意的是，當(dāng)PIT不存在指定名字的記錄的時(shí)候，還需要將插入一條記錄到PIT中。

從圖1中，很容易觀(guān)察到2處因?yàn)镃PU需要等待訪(fǎng)存從而導(dǎo)致流水線(xiàn)暫停的情況。首先，Cb1和Pb2都是不能預(yù)取的，因?yàn)檫@兩個(gè)訪(fǎng)存操作依賴(lài)前一步名字的哈希計(jì)算過(guò)程，這樣的情況下，地址計(jì)算和訪(fǎng)存之間沒(méi)有CPU的時(shí)間間隔，因此只能等待哈希計(jì)算完成后不得不停止當(dāng)前流水線(xiàn)的執(zhí)行等待Cb1和Pb2兩個(gè)訪(fǎng)存操作完成后才能進(jìn)行后續(xù)的處理過(guò)程。第二個(gè)就是在訪(fǎng)問(wèn)CS或者PIT之后，才能決定后續(xù)需要訪(fǎng)問(wèn)的哈希表，因此這種后續(xù)操作需要依賴(lài)之前操作結(jié)果的過(guò)程會(huì)導(dǎo)致CPU流水線(xiàn)的停頓。

四、通過(guò)指令預(yù)取策略來(lái)消除訪(fǎng)存導(dǎo)致的流水線(xiàn)阻塞。

本節(jié)設(shè)計(jì)了兩種預(yù)取策略，即預(yù)哈希計(jì)算和預(yù)測(cè)哈希表（HT）查找，假設(shè)如下：因?yàn)橄到y(tǒng)提供了四個(gè)內(nèi)存通道，內(nèi)存中的多個(gè)數(shù)據(jù)段被并行地獲取，即最多四個(gè)數(shù)據(jù)是可以同時(shí)獲取的。處理PIT、CS和FIB的邏輯流程所消耗的CPU周期比哈希表查找過(guò)程更多，這意味著完全可以在計(jì)算哈希值的過(guò)程中進(jìn)行數(shù)據(jù)的預(yù)取，這樣就達(dá)到了通過(guò)預(yù)取的方式來(lái)隱藏CPU流水停頓帶來(lái)的性能開(kāi)銷(xiāo)的目的。

下面根據(jù)圖5-8來(lái)描述這兩種策略。圖5-8中的序列是從圖5-7得來(lái)的，但是是基于應(yīng)用預(yù)取策略的前提下得出的。首先，預(yù)哈希計(jì)算指的是將哈希計(jì)算的過(guò)程提前，因?yàn)楣１聿檎业恼麄€(gè)流程中，查找的Key都是名字對(duì)應(yīng)的哈希值，而不是名字的自身，所有沒(méi)有必要等到需要查詢(xún)哈希表的時(shí)候再進(jìn)行哈希值的計(jì)算，所以只有對(duì)哈希進(jìn)行預(yù)計(jì)算，才可以對(duì)進(jìn)行后面的數(shù)據(jù)并行預(yù)取。

因?yàn)樵趯?duì)興趣包的名字哈希計(jì)算完成之后，需要進(jìn)行數(shù)據(jù)的預(yù)取，因此在此時(shí)，對(duì)第二個(gè)包，也就是數(shù)據(jù)的哈希值進(jìn)行計(jì)算，這樣就可以避免了CPU因等待訪(fǎng)存而引起的停頓。這種策略意味著在在多個(gè)數(shù)據(jù)包的情況下應(yīng)該重新考慮計(jì)算的順序。也就是說(shuō)，選取的兩個(gè)連續(xù)的數(shù)據(jù)包，在最壞的情況下，大量的數(shù)據(jù)包會(huì)導(dǎo)致同時(shí)處理多個(gè)數(shù)據(jù)包的狀態(tài)，而這些數(shù)據(jù)包可能會(huì)存儲(chǔ)在內(nèi)存上。因此采用了一種預(yù)計(jì)算的方法來(lái)對(duì)哈希計(jì)算進(jìn)行改進(jìn)，在計(jì)算完第一個(gè)數(shù)據(jù)包的哈希值之后，緊接著計(jì)算后續(xù)數(shù)據(jù)包的哈希值。同時(shí)，從內(nèi)存中獲取CS、PIT的哈希表項(xiàng)，如圖中的Cb1、Pb1所示步驟。哈希計(jì)算的過(guò)程隱藏了因?yàn)樘搨卧L(fǎng)存獲取哈希表項(xiàng)所導(dǎo)致的阻塞。

其次，計(jì)算了第一個(gè)包的哈希值后，該興趣包的所有哈希表（即CS、PIT和FIB）的哈希表項(xiàng)都可以從同時(shí)從內(nèi)存中獲取了。因此，所有哈希項(xiàng)，包括那些由于最長(zhǎng)前綴匹配結(jié)果而無(wú)法訪(fǎng)問(wèn)的哈希項(xiàng)，都是基于推測(cè)性地預(yù)獲取的，也就是說(shuō)獲取到的數(shù)據(jù)在后續(xù)的處理流程中可能根本用不到。這種策略被稱(chēng)為推測(cè)性的哈希查找。在獲取后續(xù)數(shù)據(jù)包的哈希項(xiàng)之后，推測(cè)性的哈希查找將應(yīng)用于該數(shù)據(jù)包的哈希項(xiàng)，需要注意的是，它適用于所有哈希表和哈希項(xiàng)。

對(duì)數(shù)據(jù)預(yù)取策略的實(shí)現(xiàn)結(jié)果顯示平均包處理的CPU周期可以降低20%以上，這將大大的提高了數(shù)據(jù)包轉(zhuǎn)發(fā)的速率。

五、總結(jié)。

為了解決通用平臺(tái)網(wǎng)絡(luò)包處理的性能瓶頸問(wèn)題，本文從微觀(guān)架構(gòu)層面分析NDN網(wǎng)絡(luò)處理流程中指令流水的執(zhí)行情況，然后提出了兩種數(shù)據(jù)預(yù)取的策略來(lái)降低訪(fǎng)存對(duì)系統(tǒng)吞吐量的影響。在高性能軟件的設(shè)計(jì)流程中，需要尤為注意內(nèi)存訪(fǎng)問(wèn)的操作，因此訪(fǎng)存的次數(shù)很大程度上影響了CPU流水線(xiàn)的執(zhí)行，導(dǎo)致性能降低，所以該數(shù)據(jù)預(yù)取策略同樣可以為其他對(duì)性能要求極高的軟件設(shè)計(jì)的提供參考。

參考文獻(xiàn)

[1] Zhang L，Estrin D，Burke J，et al. Named Data Networking（NDN）Project NDN-0001[J]. Acm ?Sigcomm Computer Communication Review，2010，44（3）：66-73.

[2]Van Adrichem N L M，Kuipers F A. Ndnflow：Software-Defined Named Data Networking[C]// Network Softwarization（Netsoft），2015 1st IEEE Conference，London：IEEE，2015：1-5.