碩士論文答辯選題依據(jù)→研究現(xiàn)狀-大學(xué)課件-

假設(shè)對(duì)數(shù)據(jù)包進(jìn)行d維分類(lèi)，用S表示包頭中d個(gè)域所形成的比特串的長(zhǎng)度，那么比特串的值應(yīng)在[0,2S

－1]中，共有2S種情況。如果將每種情況對(duì)應(yīng)一個(gè)等價(jià)類(lèi)（用eqID表示），分類(lèi)問(wèn)題就可以看成是根據(jù)包頭中長(zhǎng)為S的比特串的值來(lái)確定其對(duì)應(yīng)eqID的問(wèn)題；按照這種思想進(jìn)行分類(lèi)，最直觀的做法是預(yù)先計(jì)算出所有2S個(gè)不同的eqID，存入一個(gè)線性表中，在查找時(shí)根據(jù)到來(lái)的數(shù)據(jù)包頭S比特串的值只需一次內(nèi)存訪問(wèn)就可以查找到結(jié)果，但S一般很大，2S就會(huì)占用較大的內(nèi)存，RFC算法采用分階段遞歸實(shí)現(xiàn)上述的映射，將包頭S比特串進(jìn)行分塊，每一塊對(duì)應(yīng)包頭域的一部分，比如這里的分塊0對(duì)應(yīng)了源IP地址低16位，其他分塊也對(duì)應(yīng)了包頭域的不同部分，對(duì)于分塊0，它存儲(chǔ)的eqID的取值范圍就在[0,216－1]之間，這樣就可以用一個(gè)大小為216的線性表(我們稱(chēng)為預(yù)處理表)來(lái)存儲(chǔ)源IP地址低16位對(duì)應(yīng)的eqID，如果按照原來(lái)一次內(nèi)存映射的方法，則需要大小為2112的線性表，顯然不現(xiàn)實(shí)。這樣RFC通過(guò)分塊縮小了原來(lái)的取值空間，再對(duì)各個(gè)分塊內(nèi)的eqID進(jìn)行交叉乘積就可以得到下一階段交叉乘積表，依次遞歸得到最終的交叉乘積表。RFC構(gòu)成的數(shù)據(jù)結(jié)構(gòu)稱(chēng)為縮減樹(shù)。查找時(shí)，根據(jù)到來(lái)的數(shù)據(jù)包包頭分別索引不同的分塊，取出各自的eqID進(jìn)行交叉乘積，索引下一階段的交叉乘積表，最后就能找到匹配的eqID,完成查找。下面我們來(lái)看一個(gè)簡(jiǎn)化的例子。Packet

Classification碩士論文答辯選題依據(jù)→研究現(xiàn)狀·

RFC（Recursive

Flow

Classification）算法簡(jiǎn)介eq

IDChunk

No.04567PacketHeader

S

d

個(gè)域1[0,2112-1]eq

ID23[0,216-1]Chunk

0/1：源IP低/高16位Chunk

2/3：目的IP低/高16位Chunk

4：協(xié)議標(biāo)志Chunk

5/6：源/目的端口

Chunk

7：服務(wù)類(lèi)型[0,2S-1]計(jì)算機(jī)科學(xué)技術(shù)系1右圖的RFC縮減樹(shù)由左邊的4條規(guī)則構(gòu)建而成，由于我們的算法核心是對(duì)交叉乘積表的壓縮，因此這里我們只關(guān)心其中的交叉乘積表A，我們發(fā)現(xiàn)表A中存儲(chǔ)了多個(gè)相同的eqID序列，比如前9個(gè)表項(xiàng)中都存放了相同的eqID（0），造成內(nèi)存空間的浪費(fèi)。實(shí)際應(yīng)用中，這種eqID連續(xù)重復(fù)存儲(chǔ)的現(xiàn)象非常普遍，所以我們就需要避免交叉乘積表中eqID

的連續(xù)重復(fù)存儲(chǔ)，下面我們稱(chēng)不同的eqID為獨(dú)立元素。（第一階段，將規(guī)則集的3個(gè)域（F1-F3）分別映射到（分塊0-2）

3個(gè)預(yù)處理表中。預(yù)處理表的表項(xiàng)序號(hào)表示規(guī)則域的一種取值，比如分塊0的表項(xiàng)0表示規(guī)則中的F1域取值為“000”，表項(xiàng)內(nèi)容則為一個(gè)eqID。每個(gè)預(yù)處理表有一張相關(guān)聯(lián)的eqID表，其中CBM位串是用來(lái)輔助計(jì)算eqID的，它的長(zhǎng)度與規(guī)則數(shù)相同，每一位對(duì)應(yīng)一條規(guī)則（第一條規(guī)則對(duì)應(yīng)最高位，依次類(lèi)推），每個(gè)不同的CBM位串被賦予一個(gè)不同的eqID。確定預(yù)處理表中eqID的方法是：從預(yù)處理表的第一個(gè)表項(xiàng)開(kāi)始，計(jì)算每個(gè)表項(xiàng)對(duì)應(yīng)的CBM位串，例如分塊0的第一個(gè)表項(xiàng)0對(duì)應(yīng)的F1取值為000，只有R4的F1域與它匹配，那么該表項(xiàng)對(duì)應(yīng)的CBM位串為“0001”。該位串第一次出現(xiàn)，因而分配eqID為0。分塊0的表項(xiàng)1對(duì)應(yīng)的F1取值為001，R1、R2和R4的F1域與它匹配，那么該表項(xiàng)對(duì)應(yīng)的CBM位串為“1101”。該位串第一次出現(xiàn)，因而分配的eqID值加1。其他表項(xiàng)內(nèi)的eqID按照上述方法計(jì)算。當(dāng)計(jì)算出各分塊的eqID表后，就對(duì)這些eqID表進(jìn)行交叉乘積，得到了交叉乘積表A。）Packet

Classification碩士論文答辯選題依據(jù)→研究現(xiàn)狀·RFF1

C算法F2

簡(jiǎn)介FR1001010011PermitR2001100011DenyR301*100***PermitR4*********Permit計(jì)算機(jī)科學(xué)技術(shù)系1Packet

Classification碩士論文答辯提要選題依據(jù)Bitmap

RFC分類(lèi)算法4

基本出發(fā)點(diǎn)&研究意義4

設(shè)計(jì)思想4

數(shù)據(jù)結(jié)構(gòu)改進(jìn)的Bitmap

RFC算法基于Intel

IXP2800網(wǎng)絡(luò)處理器的仿真實(shí)驗(yàn)結(jié)論計(jì)算機(jī)科學(xué)技術(shù)系1處于同一階段的預(yù)處理表或交叉乘積表能夠被并行地索引，并且這些預(yù)處理表或交叉乘積表又各自獨(dú)立，能夠分布于不同的存儲(chǔ)單元中；處于不同階段的預(yù)處理表或交叉乘積表又能夠被互不干擾地并行地索引。Packet

Classification碩士論文答辯Bitmap

RFC分類(lèi)算法計(jì)算機(jī)科學(xué)技術(shù)系1·

基本出發(fā)點(diǎn)&研究意義4

RFC算法是目前較快的包分類(lèi)算法，并且有適合于網(wǎng)絡(luò)處理器實(shí)現(xiàn)的優(yōu)點(diǎn)；4

RFC占用內(nèi)存過(guò)大，當(dāng)前內(nèi)存仍然是比較昂貴的資源，減少內(nèi)存消耗可以降低應(yīng)用成本；4

用IXP2800實(shí)現(xiàn)算法時(shí)，當(dāng)所需內(nèi)存大大減小后，有可能用SRAM實(shí)現(xiàn)，從而大大加快分類(lèi)的速度；我們用一個(gè)稱(chēng)為Bitmap的0/1比特串記錄交叉乘積表中獨(dú)立元素的連續(xù)分布情況，其中每個(gè)比特位對(duì)應(yīng)交叉乘積表中的一個(gè)表項(xiàng)，當(dāng)某一位被置1，表示交叉乘積表中與該位對(duì)應(yīng)的表項(xiàng)存儲(chǔ)了一個(gè)與此前不同的相同獨(dú)立元素序列，我們只需要將序列的第一個(gè)獨(dú)立元素存儲(chǔ)到Element數(shù)組中就可以了，數(shù)組的各個(gè)單元與Bitmap中的每個(gè)1相對(duì)應(yīng)，這樣我們就避免了相同獨(dú)立元素的連續(xù)存儲(chǔ)。在查找時(shí)，比如索引值為16，這個(gè)表項(xiàng)對(duì)應(yīng)的Bitmap中相應(yīng)位為1，再統(tǒng)計(jì)該比特位是Bitmap中的第幾個(gè)1，我們統(tǒng)計(jì)出來(lái)它是第6個(gè)1，直接找Element數(shù)組中的第6個(gè)單元就可以了。下面請(qǐng)看算法的數(shù)據(jù)結(jié)構(gòu)Packet

Classification碩士論文答辯Bitmap

RFC分類(lèi)算法·

設(shè)計(jì)思想計(jì)算機(jī)科學(xué)技術(shù)系1算法數(shù)據(jù)結(jié)構(gòu)由一個(gè)壓縮表和附表組成，當(dāng)交叉乘積表中獨(dú)立元素的數(shù)量超超出了我們預(yù)定義的Element數(shù)組大小時(shí)，就要將多余的獨(dú)立元素存入附表中，并增加一個(gè)指針指向附表，因此為了提高算法的效率我們應(yīng)在合理的內(nèi)存范圍內(nèi)盡可能增大Element數(shù)組的容量，避免出現(xiàn)附表，以降低第二次的訪存概率。數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)也考慮到了基于ixp2800的實(shí)現(xiàn)，各個(gè)域的寬度都需要與ixp2800的內(nèi)存寬度相匹配Packet

Classification碩士論文答辯Bitmap

RFC分類(lèi)算法·

數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)科學(xué)技術(shù)系1開(kāi)發(fā)平臺(tái)：IXA

SDK

4.1

DevWorkBench＋Microengine

C；采用與真實(shí)規(guī)則集特征相似的仿真規(guī)則集；對(duì)IPv4數(shù)據(jù)包進(jìn)行4維分類(lèi)。Packet

Classification碩士論文答辯基于Intel

IXP2800網(wǎng)絡(luò)處理器的仿真實(shí)驗(yàn)·

Bitmap

RFC與RFC算法內(nèi)存空間比較71％68.6％72.2％68.7％計(jì)算機(jī)科學(xué)技術(shù)系1根據(jù)最小包長(zhǎng)計(jì)算出要達(dá)到線速分類(lèi)，算法應(yīng)具備25.5Mpps的分類(lèi)速度Packet

Classification碩士論文答辯基于Intel

IXP2800網(wǎng)絡(luò)處理器的仿真實(shí)驗(yàn)計(jì)算機(jī)科學(xué)技術(shù)系1·

相對(duì)加速比POP_Count能在3個(gè)時(shí)鐘周期內(nèi)計(jì)算出Bitmap位串中1的個(gè)數(shù)FFS的效率就比較低Packet

Classification碩士論文答辯基于Intel

IXP2800網(wǎng)絡(luò)處理器的仿真實(shí)驗(yàn)計(jì)算機(jī)科學(xué)技術(shù)系1·

指令選擇（POP_COUNT

vs.FFS）43％Packet

Classification碩士論文答辯基于Intel

IXP2800網(wǎng)絡(luò)處理器的仿真實(shí)驗(yàn)·

內(nèi)存分配計(jì)算機(jī)科學(xué)技術(shù)系1Packet

Classification碩士論文答辯基于Intel

IXP2800網(wǎng)絡(luò)處理器的仿真實(shí)驗(yàn)·

任務(wù)劃分（Multi-Processing

vs.Context-Pipelining）計(jì)算機(jī)科學(xué)技術(shù)系1實(shí)驗(yàn)結(jié)果Bitmap

RFC算法消除了RFC算法60％以上的冗余空間；

Bitmap

RFC算法用較少的ME就能達(dá)到10Gbps的分類(lèi)速度；可惜的是10Gbps的分類(lèi)速度是在SRAM配置下實(shí)現(xiàn)的，其它存儲(chǔ)方式還無(wú)法滿足要求；Multi-Processing任務(wù)劃分方式要優(yōu)于Context-Pipelining。Packet

Classification碩士論文答辯基于Intel

IXP2800網(wǎng)絡(luò)處理器的仿真實(shí)驗(yàn)計(jì)算機(jī)科學(xué)技術(shù)系1·

延遲隱藏1ME2MEs4MEs8MEsWithout

Pkt

Order6.5412.8525.6533.35