一种基于Trie转发表的虚拟路由I.pdfVIP

第２９卷第１１期　　　 计算机应用与软件 Ｖｏｌ２９Ｎｏ．１１ ２０１２年１１月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｎｏｖ．２０１２ 一种基于Ｔｒｉｅ转发表的虚拟路由ＩＰ查找方法 叶光辉　林亚平　王　刚 （湖南大学信息科学与工程学院　湖南长沙４１００８２） 摘　要　　为了使路由器在有限的存储资源中支持更多的虚拟路由实例，提出一种基于多分支Ｔｒｉｅ的动态共享转发表结构，并在 此结构上实现了相应的虚拟路由ＩＰ查找方法。该方法采用多比特位的ＩＰ查找，减少了转发表中结构性消耗及访存次数，同时该方 法具有自适应性，能够根据已有的ＩＰ规则集，通过动态规划构造空间最优的Ｔｒｉｅ。仿真结果表明，与已有的共享转发表结构相比， 该方法节约了大量的存储空间，并且能够实现快速的ＩＰ查找。 关键词　　多分支Ｔｒｉｅ　动态规划　ＩＰ查找　虚拟路由　共享转发表 中图分类号　ＴＰ３９３　　　　文献标识码　Ａ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１２．１１．０６６ ＩＰＡＤＤＲＥＳＳＬＯＯＫＵＰＦＯＲＶＩＲＴＵＡＬＲＯＵＴＥＲＳＷＩＴＨＴＲＩＥＢＡＳＥＤＦＯＲＷＡＲＤＩＮＧ ＴＡＢＬＥ ＹｅＧｕａｎｇｈｕｉ　ＬｉｎＹａｐｉｎｇ　ＷａｎｇＧａｎｇ （ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ，ＨｕｎａｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００８２，Ｈｕｎａｎ，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ｉｎｏｒｄｅｒｔｏｓｕｐｐｏｒｔｍｏｒｅｖｉｒｔｕａｌｒｏｕｔｉｎｇｉｎｓｔａｎｃｅｓｗｉｔｈｌｉｍｉｔｅｄｍｅｍｏｒｙｉｎｔｈｅｒｏｕｔｅｒ，ａｍｕｌｔｉｂｒａｎｃｈＴｒｉｅｂａｓｅｄｄｙｎａｍｉｃｓｈａｒｅｄ ｆｏｒｗａｒｄｉｎｇｔａｂｌｅｓｔｒｕｃｔｕｒｅｉｓｐｒｏｐｏｓｅｄｉｎｔｈｉｓｐａｐｅｒ．Ｂａｓｅｄｏｎｔｈｉｓｓｔｒｕｃｔｕｒｅ，ｃｏｒｒｅｓｐｏｎｄｉｎｇｖｉｒｔｕａｌｒｏｕｔｅｒＩＰｌｏｏｋｕｐｍｅｔｈｏｄｉｓｉｍｐｌｅｍｅｎｔｅｄ． ＴｈｉｓｍｅｔｈｏｄｕｓｅｓｍｕｌｔｉｂｉｔＩＰｌｏｏｋｕｐｔａｂｌｅｗｈｉｃｈｒｅｄｕｃｅｓｔｈｅｓｔｒｕｃｔｕｒａｌｃｏｎｓｕｍｐｔｉｏｎｉｎｆｏｒｗａｒｄｉｎｇｔａｂｌｅａｎｄｔｈｅａｃｃｅｓｓｔｉｍｅｓ．Ｂｅｓｉｄｅｓ，ｔｈｉｓ ｍｅｔｈｏｄｉｓｓｅｌｆａｄａｐｔｉｖｅ，ｉｔｃａｎｃｏｎｓｔｒｕｃｔｓｐａｃｅｏｐｔｉｍｉｓｅｄＴｒｉｅｂａｓｅｄｏｎｅｘｉｓｔｉｎｇＩＰｒｕｌｅｓｅｔ．Ｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏｗｔｈａｔ，ｃｏｍｐａｒｉｎｇｗｉｔｈｏｔｈｅｒ ｓｈａｒｅｄｆｏｒｗａｒｄｉｎｇｓｔｒｕｃｔｕｒｅｓ，ｔｈｉｓｍｅｔｈｏｄｓａｖｅｓａｌａｒｇｅａｍｏｕｎｔｏｆｓｔｏｒａｇｅｓｐａｃｅ，ａｎｄｃａｎａｃｈｉｅｖｅｔｈｅｆａｓｔＩＰｌｏｏｋｕｐ． Ｋｅｙｗｏｒｄｓ　　ＭｕｌｔｉｂｒａｎｃｈＴｒｉｅｔｒｅｅ　Ｄｙｎａｍｉｃｐｒｏｇｒａｍｍｉｎｇ　ＩＰｌｏｏｋｕｐ　Ｖｉｒｔｕａｌｒｏｕｔｉｎｇ　Ｓｈａｒｅｄｆｏｒｗａｒｄｉｎｇｔａｂｌｅ ０　引　言 １　背景及相关工作 随着Ｉｎｔｅｒｎｅｔ的发展，网络趋于复杂化，网络路由也变得越 ［２，３］ 当前，网络链路速度的提高（１００Ｇｂｐｓ的数据传输率 ） 来越复杂。虚拟路由技术是解决此难题的一种有效方案。虚拟 需要路由器有更高效的转发表结构和ＩＰ查找方法；转发规则集 路由是对一台物理路由器的扩展，是在一台物理路由器上运行 的膨胀扩张（骨干网上的核心路由器保存有３１００００条规则［４］） 多个虚拟路由实例（ｉｎｓｔａｎｃｅ）。虚拟路由之间的转发表是独立 需要路由器能够保存海量的