基于信息熵的匹配域裁剪算法

发布时间：2018-11-04 11:31

【摘要】：随着网络功能日益多样化,分组分类技术对匹配域数量、表项深度等需求不断提高,加剧了硬件存储压力。为保证查表效率和硬件资源利用率,提出基于信息熵的匹配域裁剪算法。通过分析匹配域冗余信息,提出匹配域裁剪模型;通过分组头部信息熵的映射建模,将匹配域裁剪算法复杂度从NP难降为线性复杂度。实验结果表明,较现有方案,所提方案所需三态内容寻址存储器(TCAM,ternary content-addressable memory)存储空间能够进一步减少40%以上,或随着流表规模增长,所提案能够明显减少算法运行时间。
[Abstract]:With the increasing diversification of network functions, the number of matching fields and the depth of table items are increasingly required by the grouping classification technology, which intensifies the storage pressure of hardware. In order to ensure the efficiency of table searching and the utilization of hardware resources, a matching domain clipping algorithm based on information entropy is proposed. The matching domain clipping model is proposed by analyzing the redundant information in the matching domain, and the complexity of the matching domain clipping algorithm is reduced from NP to linear complexity by mapping the entropy of the header information. The experimental results show that the proposed scheme can further reduce the storage space of three-state content addressable memory (TCAM,ternary content-addressable memory) by more than 40%, or increase with the scale of stream table. The proposed algorithm can significantly reduce the running time of the algorithm.
【作者单位】：国家数字交换系统工程技术研究中心;
【基金】：国家重点基础研究发展计划(“973”计划)基金资助项目(No.2013CB329104) 国家自然科学基金资助项目(No.61521003) 国家高技术研究发展计划(“863”计划)基金资助项目(No.2015AA016102)~~
【分类号】：TP301.6

【相似文献】