一种最优特里树合并算法

摘要：

在一个内存有限的物理路由器上,可能需要部署几十个甚至几百个虚拟路由器.为节省内存开销,提出一种最优特里树合并算法.采用动态规划方法求解每棵特里树的初始合并节点和最优特里树的节点数,在动态规划计算过程中记录任意2个节点达到最优匹配时的子节点排列,根据计算结果构造最优特里树.实验结果表明,与简单特里树合并算法相比,该算法能节省20％～90％的内存开销.

关键词：虚拟路由器、特里树、内存开销、动态规划、数据包分类

所属期刊栏目：39

分类号：TP393(计算技术、计算机技术)

资助基金：湖南省自然科学基金资助项目12JJ3068

在线出版日期：2013-11-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：5-11