一种基于Trie转发表的虚拟路由IP查找方法  

IP-ADDRESS LOOKUP FOR VIRTUAL ROUTERS WITH TRIE-BASED FORWARDING TABLE

作　　者：叶光辉[1] 林亚平[1] 王刚[1] 

机构地区：[1]湖南大学信息科学与工程学院,湖南长沙410082

出　　处：《计算机应用与软件》2012年第11期257-261,284,共6页Computer Applications and Software

摘　　要：为了使路由器在有限的存储资源中支持更多的虚拟路由实例,提出一种基于多分支Trie的动态共享转发表结构,并在此结构上实现了相应的虚拟路由IP查找方法。该方法采用多比特位的IP查找,减少了转发表中结构性消耗及访存次数,同时该方法具有自适应性,能够根据已有的IP规则集,通过动态规划构造空间最优的Trie。仿真结果表明,与已有的共享转发表结构相比,该方法节约了大量的存储空间,并且能够实现快速的IP查找。In order to support more virtual routing instances with limited memory in the router,a multi-branch Trie-based dynamic shared forwarding table structure is proposed in this paper.Based on this structure,corresponding virtual router IP look-up method is implemented.This method uses multi-bit IP lookup table which reduces the structural consumption in forwarding table and the access times.Besides,this method is self-adaptive,it can construct space optimised Trie based on existing IP rule set.Simulation results show that,comparing with other shared forwarding structures,this method saves a large amount of storage space,and can achieve the fast IP lookup.

关 键 词：多分支Trie 动态规划 IP查找 虚拟路由 共享转发表 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]