计算机工程 ›› 2013, Vol. 39 ›› Issue (5): 5-11.doi: 10.3969/j.issn.1000-3428.2013.05.002

• 专栏 • 上一篇    下一篇

一种最优特里树合并算法

熊帅,常炳国,李睿   

  1. (湖南大学信息科学与工程学院,长沙 410082)
  • 收稿日期:2012-06-25 出版日期:2013-05-15 发布日期:2013-05-14
  • 作者简介:熊 帅(1987-),男,硕士研究生,主研方向:无线传感器网络,数据包分类;常炳国,副教授、博士;李 睿,讲师、博士
  • 基金项目:

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

An Optimal Trie Merging Algorithm

XIONG Shuai, CHANG Bing-guo, LI Rui   

  1. (College of Information Science and Engineering, Hunan University, Changsha 410082, China)
  • Received:2012-06-25 Online:2013-05-15 Published:2013-05-14

摘要:

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

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

Abstract:

Dozens or even hundreds of virtual routers may be deployed in a memory limited physical router. To save memory overhead, this paper proposes an algorithm named optimal trie merging algorithm. It adopts dynamic programming approach to find the nodes for initial merging of each trie, and computes the number of nodes of the optimal trie. The sub-node arrangements of any two nodes, which achieve optimal matching, are written down in the process of dynamic programming computation. Then, according to the three computation results, it constructs a data structure named optimal trie. Experimental results show that the algorithm saves 20%~90% memory overhead than simple trie merging algorithm.

Key words: virtual router, trie, memory overhead, dynamic programming, packet classification

中图分类号: