欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2020106846758
申请人: 长沙理工大学
专利类型:发明专利
专利状态:未下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种OpenFlow大规模流表弹性节能与高效查找系统,其特征在于,包括:

活跃精确流层,用于缓存网络中的活跃精确流表项,实现高速低功率的流表缓存查找;

所述活跃精确流层采用十字链表方式串连着缓存结点,形成类似于稀疏网格的流表缓存结构;所述稀疏网格的流表缓存结构中每个结点均由用于表项匹配的匹配域和用于记录该结点上一次成功匹配时间的时间戳组成,且每条活跃精确流链的头结点中均设有活跃结点计数器;

汇聚流层,用于存储通配流表项,并通过聚合算法进行合并,以缓解TCAM存储容量不足问题,提高TCAM缓存命中率;所述汇聚流层包括TCAM和DRAM;

个体流层,用于存储暂不满足聚合条件的精确流表项,以提升OpenFlow交换机的分组转发能力;所述个体流层包括SRAM和DRAM;

所述汇聚流层中TCAM存储流表项中的标识字段匹配域以及掩码,DRAM存储流表项剩余的内容字段动作集树以及时间戳;且TCAM储存具有汇聚能力的通配流表项,暂不满足汇聚条件的精确流表项则存储在SRAM中,通过实时使用流汇聚或者流拆分算法,对TCAM流表项进行适当的合并或者拆分;

所述个体流层中SRAM中存储有组织成哈希链表的精确流表项标识字段,DRAM存储有精确流表项的剩余内容字段;

所述动作集树用于保证数据分组进行正确转发处理,并使动作集不同的两条通配流表项能够合并。

2.一种基于权利要求1所述系统的OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,包括以下步骤:所述活跃精确流层首先通过哈希运算定位匹配流表项所处的哈希查找链,当此哈希查找链中存在匹配此数据分组的结点,则获取该结点所处活跃精确流链对应的TCAM索引值,定位到相应的DRAM流表项,从而绕过TCAM流表查找过程,直接执行DRAM流表项中的动作集;

所述汇聚流层在SDN下发新的通配规则时,若TCAM存储空间已满,则优先使用汇聚算法聚合TCAM中的流表项,并更新动作集树以保证正确的数组分组转发;若TCAM流表项无法聚合,则使用拆分算法分解稀疏网格中结点个数最少的活跃精确流链,拆分对应的TCAM流表项;

所述个体流层从个体流聚合条件出发,将为1比特位数量相同的流表项放入同一条个体流聚合链,使得相邻聚合链上的流表项汉明距离始终为1;当TCAM容量充足时,将SRAM中的精确流快速聚合成通配流存入TCAM;当TCAM容量不足时,其拆分后的精确流表项或SDN新下发的精确规则将存入SRAM中。

3.根据权利要求2所述的一种OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,所述高效查找方法包括以下操作:a、OpenFlow流表项分组转发;

通过对每个到达的数据分组查找OpenFlow流表,找到对应的流表项,进而执行相应的动作集;

b、OpenFlow流表项插入或删除;

OpenFlow流表项插入:当OpenFlow交换机接收到SDN下发的带ADD命令的flow‑mod消息时,从消息中的流匹配信息判断流规则的类型,最后根据类型选择存放位置或者安装位置;

OpenFlow流表项删除:当OpenFlow交换机收到SDN下发的带DELETE命令的flow‑mod消息时,根据消息中待删除的流规则类型,判断是删除TCAM流表项还是SRAM流表项;

c、OpenFlow流表项超时扫描;

根据当前时间戳以及DRAM中存储的时间戳的差值判断流表项是否过期,若差值大于超时间隔,则该流表项已过期并删除此流表项;

d、TCAM通配流表项聚合以及拆分;

TCAM通配流表项聚合:首先提取通配流表项中包含掩码的匹配域,查找TCAM中与之汉明距离为1的流表项;若查找成功,首先进行DRAM动作集树构建过程,获取其动作集树层数;

若合并后的动作集树层数大于门限值,则取消此次合并,继续寻找TCAM中下一条符合聚合条件的流表项;否则,合并两条流表项,更新动作集树,并合并其对应的缓存链表;聚合成功后,将生成一条新的通配流表项;此时,若动作集树层数仍低于门限值,继续进行通配流表项聚合操作,直到最新生成的流表项无法再进行合并;最后,删除被合并的流表项,将最终生成的通配流表项存入TCAM;

TCAM通配流表项拆分:根据缓存头结点数组中的计数器获取稀疏网格中最短的活跃精确流链,得到头结点中存储的TCAM索引值以定位到对应的TCAM流表项,并依次将该流表项对应的缓存结点存入SRAM,其对应的动作集存入DRAM;当所有活跃结点都存入SRAM后,根据TCAM索引值删除对应的动作集树,移除该活跃精确流链以及对应的待活跃精确流链,并将头结点中的计数器置为0,最后从TCAM中删除该流表项,其中,活跃精确流链采用循环双链表结构或者循环单链表结构,待活跃精确流链采用双链表结构或者单链表结构,且两条对应的活跃精确流链与待活跃精流链表共用一个头结点或者分开存储;

e、SRAM精确流表项聚合;

首先获取精确流表项匹配域中bit位为1的个数以定位到对应的个体流聚合链,然后遍历其相邻的两条个体流聚合链,查找与之汉明距离为1的流表项;若查找成功,则聚合成一条新的通配流表项,根据两条流表项对应的内容字段构建动作集树存入DRAM顺序表,然后删除SRAM与DRAM中的原流表项,将新生成的通配流表项存入TCAM;

f、稀疏网格缓存更新以及超时扫描;

稀疏网格缓存更新:首先查找缓存,若缓存查找失败,则继续查找TCAM;若该流直接命中缓存,更新匹配结点的时间戳即可;若该流未命中缓存而命中TCAM,需将其插入缓存或更新其活跃状态;

稀疏网格超时扫描:根据当前系统时间戳和流表项中的时间戳的差值来判断一个结点是否超时,如果差值大于超时间隔,则该结点判定为超时结点,从缓存中清除;

g、动作集树构建;

当两条通配流表项汇聚成功后,获取其相异的比特位存入新建结点,其左右孩子结点分别为两条汇聚流对应动作集树的根结点。

4.根据权利要求3所述的一种OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,所述OpenFlow流表分组转发具体为:首先分析分组头部信息,提取流关键字;然后通过哈希运算在稀疏网格中查找与流关键字相匹配的结点,查找成功则获取该结点对应的TCAM流表项索引值,定位到DRAM中对应的动作集树,进而获取正确的动作集,转发处理数据分组;分组转发成功后,需更新DRAM表项中的相关内容字段信息;

其中,当稀疏网格缓存预测失败,则需使用流关键字进一步查找TCAM,若查找成功,则定位DRAM顺序表中对应的动作集树,获取动作集后转发处理数据分组;分组转发成功后,需更新动作集树所在DRAM表项的计数器与时间戳,并更新稀疏网格缓存;

当查找TCAM失败,将查找SRAM,如果查找成功,则获取对应的DRAM流表项,执行相应的动作集以进行分组转发处理,并更新DRAM流表项中的计数器与时间戳;若查找失败,则意味着该数据分组属于一条新流,OpenFlow交换机将把该数据分组的头部信息打包成packet‑in消息上交给SDN,以请求SDN下发新的流规则。

5.根据权利要求3所述的一种OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,所述OpenFlow流表插入中根据类型选择存放位置或者安装位置具体为:若该流规则属于精确匹配规则,则将其标识字段与内容字段分别存入SRAM与DRAM;若此时TCAM容量充足,将部分精确流聚合成通配流存入TCAM,以利用TCAM查找速度极快的优势,加快个体流的处理过程;若SDN下发的是通配匹配规则,则该流规则应安装到TCAM中;当TCAM存储容量充足时,直接将该流规则安装到TCAM即可;否则,需优先对TCAM流表项进行合并,若合并失败,则选取TCAM中活跃度较低的通配流进行拆分,为新表项的安装腾出空间。

6.根据权利要求3所述的一种OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,所述OpenFlow流表项删除具体还包括:根据消息中待删除的流规则类型为通配匹配规则,则查找TCAM,查找成功则获取TCAM索引值,移除对应的缓存链表,并从DRAM顺序表中移除对应的动作集树,最后,移除此TCAM流表项;

根据消息中待删除的流规则类型为精确匹配规则,则查找SRAM,查找成功则删除对应的DRAM流表项以及SRAM流表项;

若查找TCAM与SRAM失败,则向SDN发送error消息,报告流规则删除失败结果。

7.根据权利要求3所述的一种OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,所述OpenFlow流表项超时扫描具体还包括:遍历TCAM流表,若发现过期流表项,首先根据TCAM索引值移除缓存中对应的缓存链表,然后从DRAM顺序表中移除对应的动作集树,最后删除此TCAM流表项;对于SRAM中存储的精确流表项,遍历各哈希查找链和哈希查找链中的所有流表项;若发现过期的结点,则删除对应的DRAM流表项和SRAM流表项。

8.根据权利要求3所述的一种OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,所述稀疏网格缓存更新具体还包括:首先,获取该流对应的TCAM索引值,查找对应的待活跃精确流链,如果待活跃精确流链中不存在结点匹配该数据分组,则将流关键字存入待活跃精确流链中;否则需进一步根据当前时间戳与结点中存储的时间戳的差值,判断该结点中的流表项是否进入活跃状态,如果进入了活跃状态,需将匹配结点移动到对应的活跃精确流链中,并更新匹配结点中的时间戳信息,其中,稀疏网格的存储介质采用SRAM、DRAM,DDR以及SDRAM。

9.根据权利要求3所述的一种OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,所述稀疏网格超时扫描具体还包括:首先遍历活跃精确流链,当这条活跃精确流链为空或者遍历完成,则继续遍历对应的待活跃精确流链,当待活跃精确流链为空或者遍历完成后,则遍历下一条活跃精确流链,依此类推,遍历过程中一旦发现超时结点则将之删除。

10.根据权利要求3所述的一种OpenFlow大规模流表弹性节能与高效查找方法,其特征在于,所述动作集树构建还包括:若其中通配流之前未经过聚合,对应的DRAM顺序表流表项只含有一个动作集,可将此动作集视为一棵只含有根结点的动作集树,然后进行动作集树的合并;为同时保证正确的分组转发操作与OpenFlow流表高效查找,当动作集树的层数大于门限值时,对应的TCAM流表项便不能再进行合并。