(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 20221019396 3.2 (22)申请日 2022.03.01 (71)申请人 长沙理工大 学 地址 410114 湖南省长 沙市天心区万家丽 南路二段96 0号 (72)发明人 熊兵　曾振国　周浩　 (51)Int.Cl. H04L 49/9005(2022.01) H04L 9/32(2006.01) (54)发明名称 一种流量感知的OpenFlow流表弹性节能查 找方法 (57)摘要 本发明公开了本发明提供一种流量感知的 OpenFlow流表弹性节能查找方法， 包括： 弹性节 能缓存， 由多个逻辑分段组成， 通过子哈希 算法， 将到达网络分组的流标识符经过一次哈希计算 即可得到 各个分段的候选位置， 显著降低了哈希 计算开销， 且通过并行匹配方式可快速完成缓存 查找。 同时， 利用网络流量局部性， 缓存采用低功 耗存储介质SRA M存储网络中的活跃精确流， 使大 多数分组命中缓存 直接转发， 从而绕过OpenFlow 流表查找过程， 显著降低TCAM能耗。 针对网络流 量波动性， 缓存实时感知活跃精确流数量的动态 变化并进行适应性伸缩， 在保证较高缓存装 载率 的同时， 保持高缓存命中率， 以实现OpenFlow流 表弹性节能查找。 权利要求书4页 说明书8页 附图9页 CN 114640641 A 2022.06.17 CN 114640641 A 1.一种流 量感知的OpenFl ow流表弹性节能查找 架构， 其特 征在于， 包括： 弹性节能缓存， 用于缓存 网络中的活跃精确流， 实现高速低功率的流表缓存查找； 缓存 由多个逻辑分段 组成， 依据活跃精确流的变化， 其容量适应性增加或减少。 其中弹性节能缓 存的存储介质优先采用SRAM； 弹性节能缓存， 用于降低TCAM流表查找能耗， 利用低能耗存储介质SRAM存储活跃精确 流， 使大部分网络流可通过缓存直接进 行转发。 当活跃精确流数量变化时， 缓存容量将适应 性地调整， 以容纳网络中绝大部分活跃精确流， 保证高缓存 命中率。 TCAM流表和DRAM流表， 将流表项进行拆分后， 匹配字段存入TCAM， 以保证流表查找性 能。 内容字段存入查找 开销小、 存储容量大的动态随机存 取存储器DRAM， 以缓解TCAM存储压 力。 所述弹性节能缓存由多个逻辑分段组成， 依据活跃精确流的变化， 其分段数适应性增 加或减少。 当活跃精确流数量明显增多时， 缓存动态增加一个分段， 以存储网络中新出现的 活跃精确流， 保证高缓存命中率。 当活跃精确 流数量显著减少时， 缓存自动缩减一个分段， 并将其中的流尽可能转存到剩余分段中， 以提高缓存利用率， 同时确保缓存命中率不会出 现明显的下滑。 随着活跃精确流数量的上下波动， 缓存也将进 行自适应地扩展与收缩， 以同 时取得较高的缓存 命中率与缓存利用率， 从而保证缓存整体性能。 所述弹性节能缓存分段中的每个缓存项包含流签名、 TCAM索引值和时间戳。 流签名由 流关键字输入签名函数计算而得， 通常为2或4个字节。 TCAM索引值指示当前活跃精确流对 应的TCAM流表项， 以便进一步读取对应的动作集。 时间戳记录该活跃精确流中最近一个数 据分组的到 达时间， 以便进行缓存替换和超时扫描操作。 所述TCAM流表存储流表项中的标识字段匹配域以及掩码， DRAM存储流表项剩余的内容 字段动作集 树以及时间戳， 通过TCAM索引值可直接 定位对应的DRAM流表项。 2.一种基于 权利要求1所述弹性节能缓存的索引方法， 其特 征在于， 包括： 所述弹性节能缓存为快速匹配网络分组， 从流签名中随机选取互不重复的比特进行随 机排列， 得到多个独立的子哈希函数， 进而 快速得到 分组在各个 分段的候选位置。 缓存新增 一个分段时， 将同时生成一个新的子哈希函数。 所述子哈希函数可通过子哈希矩阵存储， 在进行缓存流索引时， 首先需获取各分段对 应的子哈希函数， 以按序读取流签名中的相应比特， 进而快速得到流在各个分段中的索引 值。 在缓存分段动态新增与删除的过程中， 需获取的子哈希 函数的个数也会随之改变。 为避 免子哈希函数 的频繁生成与销毁， 可选择将部分子哈希函数存入子哈希矩阵中。 设当前分 段数为n， 则对应的n个子哈希函数存入矩阵A， 用于当前缓存流索引； 备用的子哈希函数存 入矩阵B。 当缓存新增分段时， 将矩阵B中的第一个子哈希函数移入矩阵A中， 而当缓存删除 分段时， 则将矩阵A的最后一个子哈希函数移入矩阵B中。 所述缓存流索引方法为： 子哈希矩阵第i(1≤i)行记录的比特及其顺序即为第i个子哈 希函数， 第j(1≤j≤m)列记录在进行子哈希 运算时， 按序从流签名中读取的比特位， 按照第 i行中的比特顺序读取流签名中的比特值bi,j， 计算2(j‑1)bi,j的值并进行累加， 然后对分段长 度取模。 3.根据权利要求2所述的方法， 其特 征在于， 所述高效查找方法包括以下操作： a、 OpenFl ow流表项分组转发；权　利　要　求　书 1/4 页 2 CN 114640641 A 2通过对每个到达的数据分组查找OpenFlow流表， 找到对应的流表项， 进而执行相应的 动作集； b、 OpenFl ow流表项插 入或删除； OpenFlow流表项插入： 当OpenFlow交换机接收到SDN控制 器下发的带ADD命令的flow ‑ mod消息时， 从消息中的流匹配信息判断流规则的所述类型， 最后根据类型选择存放位置或 者安装位置； OpenFlow流表项删除： 当OpenFlow交换机收到SDN控制器下发的带DELETE命令的flow ‑ mod消息时， 删除的TCAM流表和DRAM流表中的表项； c、 OpenFl ow流表项超时扫描； 根据当前时间戳以及DRAM 中存储的时间戳的差值判断流表项是否过期， 若差值大于超 时间隔， 则该流表项已过期并删除此流表项； d、 弹性节能缓存查找； 根据流关键字计算流签名。 然后读取子哈希矩阵， 根据流签名及子哈希函数计算该流 在各分段中的候选位置， 并行匹配各分段中的对应缓存项以快速 完成缓存查找； e、 弹性节能缓存 扩展与收缩操作； 弹性节能缓存扩展： 新生成一个子哈希函数(或将矩阵B中的第一个子哈希函数移入矩 阵A)， 并新增一个对应的缓存分段； 弹性节能缓存收缩： 删除最后一个分段， 并该分段中存储的活跃精确流移动到前端的 分段中； f、 弹性节能缓存 插入或删除； 弹性节能缓存插入： 通过子哈希函数得到所有候选位置， 将流签名插入到最前端分段 的空缓存项中， 缓存在进行插 入操作时， 若缓存 装载率较高， 则会触发缓存 扩展操作； 弹性节能缓存删除： 根据流签名与子哈希函数定位该流在缓存中的候选存储位置， 定 位并移除对应的缓存项， 缓存在 进行删除操作时， 若缓存装载率较低， 则会触发缓存收缩操 作； g、 弹性节能缓存 超时扫描； 弹性节能缓存超时扫描： 根据当前系统时间戳和流表项中的时间戳的差值来判断一个 结点是否超时， 如果差值大于超时间隔， 则该 结点判定为超时结点， 从 缓存中清除。 4.根据权利要求3所述的方法， 其特征在于， 所述OpenFlow流表分组转发具体为： 首先 解析其各层协议首部， 提取关键字段(如： 源/目的IP地址、 源/目的端口和协议类型等)生 成 流关键字key， 进而计算流签名以查找缓存。 若缓存查找成功则根据TCAM索引值直接定位对 应的DRAM表项， 执行其中的动作集以完成分组节能转 发。 之后， 更新 弹性节能缓存中匹配缓 存项中的时间戳以及DRAM流表项中的计数器与时间戳。 若缓存查找失败， 则需使用流关键 字key进一步查找TCAM流表。 若查找成功， 则根据TCAM索引值获取DRAM流表中对应的动作集 以进行分组转发。 分组转发成功后， 若该流转换为活跃状态， 需将之存入弹性节能缓存， 并 更新对应的DRAM表项的相关信息。 若查找TCAM流表失败， 则意味着该分组属于一条新流， OpenFlow交换机将把该数据分组的头部信息打包成Packet ‑in消息提交给SDN控制器， 请求 下发新的流 规则。 5.根据权利要求3所述的方法， 其特征在于， 所述OpenFlow流表插入和删除具体还包权　利　要　求　书 2/4 页 3 CN 114640641 A 3