未完成。。。
26. 报文框架
26.1. 设计目标
DPDK数据包框架的主要设计目标是：
- 提供标准方法来构建复杂的数据包处理流水线。 为常用的流水线功能模块提供可重复使用和可扩展的模板；
- 提供在同一流水线功能模块上在纯软件和硬件加速实现之间的切换能力；
- 提供灵活性和高性能之间的最佳权衡。 硬编码流水线通常提供最佳性能，但是不够灵活，而开发灵活的框架通常性能又较低；
- 提供一个逻辑上类似于Open Flow的框架。
26.2. 概述
报文处理应用程序通常被设计为多级流水线，每个阶段的逻辑围绕查找表进行。 对于每个传入的数据包，查找表定义了要应用于数据包的一组操作，以及数据包处理的下一个阶段。
DPDK数据包框架通过定义流水线开发的标准方法，以及为常用的流水线模块提供可重用的模板库来最大限度地减少 构建数据包流水线所需要的开发工作量。
将一组输入端口和一组输出端口通过树形拓扑中的一组查找表来连接以构成流水线。 作为当前报文查找表的查找结果，其中一个表条目（查找命中）或默认条目（查找缺失）提供了要对当前数据包应用的一组操作， 以及数据包的下一跳，可以是另一个表，输出端口或者是丢弃报文。
数据包处理流程的一个例子如下:
26.3. 端口库设计
26.3.1. 端口类型
下表是可以使用Packet Framework实现的端口的非穷尽列表。
| # | 端口类型 | 描述 |
|---|---|---|
| 1 | SW ring | 软件环形缓冲区用于应用程序之间的消息传递。使用DPDK的rte_ring。可能也是最常用的port类型 |
| 2 | HW ring | 用于与NIC、交换机或加速端口交互的缓冲区描述符队列。对于NIC端口，它使用rte_eth_rx_queue 或者rte_eth_tx_queue |
| 3 | IP reassembly | 输入数据包是完整的数据报或者片段。输出数据包则是完整的IP数据报。 |
| 4 | IP fragmentation | 输入数据包是Jumbo帧 (IP 数据报，长度大于 MTU) 或者非Jumbo帧。输出数据包是非Jumbo帧。 |
| 5 | Traffic manager | 连接到特定NIC输出端口的流量管理器，根据预定义的SLA执行拥塞管理和分级调度。 |
| 6 | KNI | 接收/发送数据包到/从Linux内核空间 |
| 7 | Source | 输入端口用作数据包生成器。 类似于Linux内核 /dev/zero 设备 |
| 8 | Sink | 输出端口，用于删除所有的输入数据包。类似于Linux内核的 /dev/null 字符设备。 |
26.3.2. 端口操作
每个端口是单向的，即输入端口或输出端口。 需要每个输入/输出端口来实现定义端口的初始化和运行时操作的抽象接口。 端口抽象接口描述于下表：
| # | 端口操作 | 描述 |
|---|---|---|
| 1 | Create | 创建低级端口对象 (如，队列)，可以内部分配内存。 |
| 2 | Free | 释放低级端口对象使用的资源 (如，内存) |
| 3 | RX | 读取一串输入数据包。只有输入端口才有这个操作。 |
| 4 | TX | 写一串输入数据包。非阻塞操作，只有输出端口有这个操作。 |
| 5 | Flush | 刷新输出缓冲区，只有输出端口有这个操作。 |
26.4. 表库设计
26.4.1. 表类型
下表是可以用Packet Framework实现的表类型的非穷举列表。
| # | 表类型 | 描述 |
|---|---|---|
| 1 | Hash table | 查找关键字是n-元组。通常，查找key使用哈希算法以产生用于标识查找结果的索引值。与每个数据包查找关键字相关的数据可以从数据包中读取（预先计算的），或者在表查找时计算。表查找、添加条目和删除条目操作，以及预先计算Key的任何流水线模块 都必须使用相同的哈希算法。哈希表通常用于实现流分类表、ARP缓存、隧道协议路由表等。 |
| 2 | Longest Prefix Match (LPM) | 查找键值是IP地址。表中的每个条目具有一个相关联的IP前缀。表查找操作选择由查找键值匹配的IP前缀；在多个匹配的情况下，具有最长前缀匹配的条目获胜。通常用于实现IP路由表。 |
| 3 | Access Control List (ACLs) | 查找键值是7-元组，包括两个 VLAN/MPLS 标签，目的IP，源IP，L4协议，L4目的端口，L4源端口。每个表条目具有相关联的ACL优先级。ACL包含VLAN/ MPLS标签的位掩码，IP目的地址的IP前缀，IP源地址的IP前缀，L4协议和位掩码，L4目的端口和位掩码，L4源端口和位掩码。表查找操作选择与查找键匹配的ACL; 在多个匹配的情况下，优先级最高的条目胜出。通常用于实现防火墙等规则数据库。 |
| 4 | Pattern matching search | 查找键值为报文负载。表示一个模式数据库，每个模式都有一个相关联的优先级。表查找操作选择与输入报文匹配的模式，在多个匹配的情况下，最高优先级匹配胜出 |
| 5 | Array | 查询键是表条目索引本身。 |
26.4.2. 表操作接口
每个表都需要实现一个定义表的初始化和运行时操作的抽象接口。 表的抽象接口如下表所述：
| # | 表操作 | 描述 |
|---|---|---|
| 1 | Create | 创建查找表的低级数据结构。 可以内部分配内存。 |
| 2 | Free | 释放查找表使用的所有资源。 |
| 3 | Add entry | 向查找表添加新条目。 |
| 4 | Delete entry | 从查找表中删除特定条目。 |
| 5 | Lookup | 查找一组输入数据包，并返回一个指定每个数据包的查找操作结果的位掩码。一个位表示相应数据包的查找命中，而一个清除位被查找错过 对于每个查找命中数据包，查找操作也返回指向被命中的表条目的指针，其中包含要应用于数据包的操作和任何关联的元数据。对于每个查找缺失数据包，要应用于数据包的操作和任何关联的元数据由预先配置为查找缺失的默认表条目指定 |
26.4.3. 哈希表设计
26.4.3.1. 哈希表概述
哈希表很重要，因为查找操作针对速度进行了优化：搜索操作仅限于表中的某个哈希桶，而不是在表中所有元素间进行线性查找。
关联数组
关联数组是一个可以被指定为一组（键，值）对的函数，每个键最多可以存在一个可能的输入键集合。 对于给定的一个关联数组，可能的操作如下：
- 添加 (key, value): 当没有value与当前 key相关联时，(key, value ) 关联将被创建。 当 key 已经关联了 value0，那么 (key, value0) 将被移除，并重新创建关联 (key, value) 。
- 删除 key: 假如当前没有value关联到 key，这个操作将不起作用。 当 key 已经关联了 value，那么 (key, value) 将被移除。
- 查找 key: 假如当前 key没有关联的value，那么这个操作返回查找缺失。 当 key 关联 value，那么这个操作将返回 value。 键值对 (key, value) 不做任何改变。
用于将输入key与关联数组中的key进行匹配的规则是 精确匹配，也就是说，key的大小及key值都必须精确匹配。
哈希函数
哈希函数确定性地将可变长度（密钥）的数据映射到固定大小的数据（散列值或密钥签名）。 通常地，key的大小要大于散列值的大小。 散列函数基本上将长key压缩成短哈希值。 几个key可以共享相同的哈希值，这就是哈希碰撞（哈希冲突）。
高质量散列函数可以做到均匀分布。 对于大量的key，当将哈希值的空间划分成固定数量的相等间隔（哈希桶）时，希望将哈希值均匀分布在这些间隔（均匀分布）上，而不是大多数哈希值 只分布在几个哈希桶中，其余的哈希桶在很大程度上没有使用（不均匀分布）。
哈希表
哈希表是使用散列函数进行操作的关联数组。 使用散列函数的原因是通过最小化必须与输入键进行比较的表键的数量来优化查找操作的性能。
哈希表不是将(key, value)对存储在单个链表中，而是保留多个链表（哈希桶）。 对于任意给定的key，存在单个哈希桶，并且该桶是基于key的哈希值唯一标识的。 一旦计算了哈希值，并且标识了哈希桶，key或者位于该桶中，或者根本不存在哈希表中，因此，根据key搜索可以从当前哈希表中唯一确认一个值。
哈希表查找的性能大大提高，前提是哈希表均匀分布在各个哈希桶之间，这个可以使用均匀分布的哈希函数来实现。 将key映射成哈希值的规则就是哈希函数，最简单的获取哈希桶的方式方式如下：
*bucket_id = f_hash(key) % n_buckets;*
通过选择桶的数量为2的幂，模运算符可以由按位AND逻辑来代替：
*bucket_id = f_hash(key) & (n_buckets - 1);*
为了减少哈希冲突，需要增加哈希表中哈希桶的数目。
在数据包处理上下文中，哈希表操作设计的操作顺序如下所示:
