未完成。。。
26. 報(bào)文框架
26.1. 設(shè)計(jì)目標(biāo)
DPDK數(shù)據(jù)包框架的主要設(shè)計(jì)目標(biāo)是：
- 提供標(biāo)準(zhǔn)方法來構(gòu)建復(fù)雜的數(shù)據(jù)包處理流水線。 為常用的流水線功能模塊提供可重復(fù)使用和可擴(kuò)展的模板；
- 提供在同一流水線功能模塊上在純軟件和硬件加速實(shí)現(xiàn)之間的切換能力；
- 提供靈活性和高性能之間的最佳權(quán)衡。 硬編碼流水線通常提供最佳性能，但是不夠靈活，而開發(fā)靈活的框架通常性能又較低；
- 提供一個(gè)邏輯上類似于Open Flow的框架。
26.2. 概述
報(bào)文處理應(yīng)用程序通常被設(shè)計(jì)為多級(jí)流水線，每個(gè)階段的邏輯圍繞查找表進(jìn)行。 對(duì)于每個(gè)傳入的數(shù)據(jù)包，查找表定義了要應(yīng)用于數(shù)據(jù)包的一組操作，以及數(shù)據(jù)包處理的下一個(gè)階段。
DPDK數(shù)據(jù)包框架通過定義流水線開發(fā)的標(biāo)準(zhǔn)方法，以及為常用的流水線模塊提供可重用的模板庫來最大限度地減少 構(gòu)建數(shù)據(jù)包流水線所需要的開發(fā)工作量。
將一組輸入端口和一組輸出端口通過樹形拓?fù)渲械囊唤M查找表來連接以構(gòu)成流水線。 作為當(dāng)前報(bào)文查找表的查找結(jié)果，其中一個(gè)表?xiàng)l目（查找命中）或默認(rèn)條目（查找缺失）提供了要對(duì)當(dāng)前數(shù)據(jù)包應(yīng)用的一組操作， 以及數(shù)據(jù)包的下一跳，可以是另一個(gè)表，輸出端口或者是丟棄報(bào)文。
數(shù)據(jù)包處理流程的一個(gè)例子如下:
26.3. 端口庫設(shè)計(jì)
26.3.1. 端口類型
下表是可以使用Packet Framework實(shí)現(xiàn)的端口的非窮盡列表。
| # | 端口類型 | 描述 |
|---|---|---|
| 1 | SW ring | 軟件環(huán)形緩沖區(qū)用于應(yīng)用程序之間的消息傳遞。使用DPDK的rte_ring。可能也是最常用的port類型 |
| 2 | HW ring | 用于與NIC、交換機(jī)或加速端口交互的緩沖區(qū)描述符隊(duì)列。對(duì)于NIC端口，它使用rte_eth_rx_queue 或者rte_eth_tx_queue |
| 3 | IP reassembly | 輸入數(shù)據(jù)包是完整的數(shù)據(jù)報(bào)或者片段。輸出數(shù)據(jù)包則是完整的IP數(shù)據(jù)報(bào)。 |
| 4 | IP fragmentation | 輸入數(shù)據(jù)包是Jumbo幀 (IP 數(shù)據(jù)報(bào)，長度大于 MTU) 或者非Jumbo幀。輸出數(shù)據(jù)包是非Jumbo幀。 |
| 5 | Traffic manager | 連接到特定NIC輸出端口的流量管理器，根據(jù)預(yù)定義的SLA執(zhí)行擁塞管理和分級(jí)調(diào)度。 |
| 6 | KNI | 接收/發(fā)送數(shù)據(jù)包到/從Linux內(nèi)核空間 |
| 7 | Source | 輸入端口用作數(shù)據(jù)包生成器。 類似于Linux內(nèi)核 /dev/zero 設(shè)備 |
| 8 | Sink | 輸出端口，用于刪除所有的輸入數(shù)據(jù)包。類似于Linux內(nèi)核的 /dev/null 字符設(shè)備。 |
26.3.2. 端口操作
每個(gè)端口是單向的，即輸入端口或輸出端口。 需要每個(gè)輸入/輸出端口來實(shí)現(xiàn)定義端口的初始化和運(yùn)行時(shí)操作的抽象接口。 端口抽象接口描述于下表：
| # | 端口操作 | 描述 |
|---|---|---|
| 1 | Create | 創(chuàng)建低級(jí)端口對(duì)象 (如，隊(duì)列)，可以內(nèi)部分配內(nèi)存。 |
| 2 | Free | 釋放低級(jí)端口對(duì)象使用的資源 (如，內(nèi)存) |
| 3 | RX | 讀取一串輸入數(shù)據(jù)包。只有輸入端口才有這個(gè)操作。 |
| 4 | TX | 寫一串輸入數(shù)據(jù)包。非阻塞操作，只有輸出端口有這個(gè)操作。 |
| 5 | Flush | 刷新輸出緩沖區(qū)，只有輸出端口有這個(gè)操作。 |
26.4. 表庫設(shè)計(jì)
26.4.1. 表類型
下表是可以用Packet Framework實(shí)現(xiàn)的表類型的非窮舉列表。
| # | 表類型 | 描述 |
|---|---|---|
| 1 | Hash table | 查找關(guān)鍵字是n-元組。通常，查找key使用哈希算法以產(chǎn)生用于標(biāo)識(shí)查找結(jié)果的索引值。與每個(gè)數(shù)據(jù)包查找關(guān)鍵字相關(guān)的數(shù)據(jù)可以從數(shù)據(jù)包中讀?。A(yù)先計(jì)算的），或者在表查找時(shí)計(jì)算。表查找、添加條目和刪除條目操作，以及預(yù)先計(jì)算Key的任何流水線模塊 都必須使用相同的哈希算法。哈希表通常用于實(shí)現(xiàn)流分類表、ARP緩存、隧道協(xié)議路由表等。 |
| 2 | Longest Prefix Match (LPM) | 查找鍵值是IP地址。表中的每個(gè)條目具有一個(gè)相關(guān)聯(lián)的IP前綴。表查找操作選擇由查找鍵值匹配的IP前綴；在多個(gè)匹配的情況下，具有最長前綴匹配的條目獲勝。通常用于實(shí)現(xiàn)IP路由表。 |
| 3 | Access Control List (ACLs) | 查找鍵值是7-元組，包括兩個(gè) VLAN/MPLS 標(biāo)簽，目的IP，源IP，L4協(xié)議，L4目的端口，L4源端口。每個(gè)表?xiàng)l目具有相關(guān)聯(lián)的ACL優(yōu)先級(jí)。ACL包含VLAN/ MPLS標(biāo)簽的位掩碼，IP目的地址的IP前綴，IP源地址的IP前綴，L4協(xié)議和位掩碼，L4目的端口和位掩碼，L4源端口和位掩碼。表查找操作選擇與查找鍵匹配的ACL; 在多個(gè)匹配的情況下，優(yōu)先級(jí)最高的條目勝出。通常用于實(shí)現(xiàn)防火墻等規(guī)則數(shù)據(jù)庫。 |
| 4 | Pattern matching search | 查找鍵值為報(bào)文負(fù)載。表示一個(gè)模式數(shù)據(jù)庫，每個(gè)模式都有一個(gè)相關(guān)聯(lián)的優(yōu)先級(jí)。表查找操作選擇與輸入報(bào)文匹配的模式，在多個(gè)匹配的情況下，最高優(yōu)先級(jí)匹配勝出 |
| 5 | Array | 查詢鍵是表?xiàng)l目索引本身。 |
26.4.2. 表操作接口
每個(gè)表都需要實(shí)現(xiàn)一個(gè)定義表的初始化和運(yùn)行時(shí)操作的抽象接口。 表的抽象接口如下表所述：
| # | 表操作 | 描述 |
|---|---|---|
| 1 | Create | 創(chuàng)建查找表的低級(jí)數(shù)據(jù)結(jié)構(gòu)。 可以內(nèi)部分配內(nèi)存。 |
| 2 | Free | 釋放查找表使用的所有資源。 |
| 3 | Add entry | 向查找表添加新條目。 |
| 4 | Delete entry | 從查找表中刪除特定條目。 |
| 5 | Lookup | 查找一組輸入數(shù)據(jù)包，并返回一個(gè)指定每個(gè)數(shù)據(jù)包的查找操作結(jié)果的位掩碼。一個(gè)位表示相應(yīng)數(shù)據(jù)包的查找命中，而一個(gè)清除位被查找錯(cuò)過 對(duì)于每個(gè)查找命中數(shù)據(jù)包，查找操作也返回指向被命中的表?xiàng)l目的指針，其中包含要應(yīng)用于數(shù)據(jù)包的操作和任何關(guān)聯(lián)的元數(shù)據(jù)。對(duì)于每個(gè)查找缺失數(shù)據(jù)包，要應(yīng)用于數(shù)據(jù)包的操作和任何關(guān)聯(lián)的元數(shù)據(jù)由預(yù)先配置為查找缺失的默認(rèn)表?xiàng)l目指定 |
26.4.3. 哈希表設(shè)計(jì)
26.4.3.1. 哈希表概述
哈希表很重要，因?yàn)椴檎也僮麽槍?duì)速度進(jìn)行了優(yōu)化：搜索操作僅限于表中的某個(gè)哈希桶，而不是在表中所有元素間進(jìn)行線性查找。
關(guān)聯(lián)數(shù)組
關(guān)聯(lián)數(shù)組是一個(gè)可以被指定為一組（鍵，值）對(duì)的函數(shù)，每個(gè)鍵最多可以存在一個(gè)可能的輸入鍵集合。 對(duì)于給定的一個(gè)關(guān)聯(lián)數(shù)組，可能的操作如下：
- 添加 (key, value): 當(dāng)沒有value與當(dāng)前 key相關(guān)聯(lián)時(shí)，(key, value ) 關(guān)聯(lián)將被創(chuàng)建。 當(dāng) key 已經(jīng)關(guān)聯(lián)了 value0，那么 (key, value0) 將被移除，并重新創(chuàng)建關(guān)聯(lián) (key, value) 。
- 刪除 key: 假如當(dāng)前沒有value關(guān)聯(lián)到 key，這個(gè)操作將不起作用。 當(dāng) key 已經(jīng)關(guān)聯(lián)了 value，那么 (key, value) 將被移除。
- 查找 key: 假如當(dāng)前 key沒有關(guān)聯(lián)的value，那么這個(gè)操作返回查找缺失。 當(dāng) key 關(guān)聯(lián) value，那么這個(gè)操作將返回 value。 鍵值對(duì) (key, value) 不做任何改變。
用于將輸入key與關(guān)聯(lián)數(shù)組中的key進(jìn)行匹配的規(guī)則是 精確匹配，也就是說，key的大小及key值都必須精確匹配。
哈希函數(shù)
哈希函數(shù)確定性地將可變長度（密鑰）的數(shù)據(jù)映射到固定大小的數(shù)據(jù)（散列值或密鑰簽名）。 通常地，key的大小要大于散列值的大小。 散列函數(shù)基本上將長key壓縮成短哈希值。 幾個(gè)key可以共享相同的哈希值，這就是哈希碰撞（哈希沖突）。
高質(zhì)量散列函數(shù)可以做到均勻分布。 對(duì)于大量的key，當(dāng)將哈希值的空間劃分成固定數(shù)量的相等間隔（哈希桶）時(shí)，希望將哈希值均勻分布在這些間隔（均勻分布）上，而不是大多數(shù)哈希值 只分布在幾個(gè)哈希桶中，其余的哈希桶在很大程度上沒有使用（不均勻分布）。
哈希表
哈希表是使用散列函數(shù)進(jìn)行操作的關(guān)聯(lián)數(shù)組。 使用散列函數(shù)的原因是通過最小化必須與輸入鍵進(jìn)行比較的表鍵的數(shù)量來優(yōu)化查找操作的性能。
哈希表不是將(key, value)對(duì)存儲(chǔ)在單個(gè)鏈表中，而是保留多個(gè)鏈表（哈希桶）。 對(duì)于任意給定的key，存在單個(gè)哈希桶，并且該桶是基于key的哈希值唯一標(biāo)識(shí)的。 一旦計(jì)算了哈希值，并且標(biāo)識(shí)了哈希桶，key或者位于該桶中，或者根本不存在哈希表中，因此，根據(jù)key搜索可以從當(dāng)前哈希表中唯一確認(rèn)一個(gè)值。
哈希表查找的性能大大提高，前提是哈希表均勻分布在各個(gè)哈希桶之間，這個(gè)可以使用均勻分布的哈希函數(shù)來實(shí)現(xiàn)。 將key映射成哈希值的規(guī)則就是哈希函數(shù)，最簡單的獲取哈希桶的方式方式如下：
*bucket_id = f_hash(key) % n_buckets;*
通過選擇桶的數(shù)量為2的冪，模運(yùn)算符可以由按位AND邏輯來代替：
*bucket_id = f_hash(key) & (n_buckets - 1);*
為了減少哈希沖突，需要增加哈希表中哈希桶的數(shù)目。
在數(shù)據(jù)包處理上下文中，哈希表操作設(shè)計(jì)的操作順序如下所示:
