基于索引和位图构建的高性能数据报匹配结构-创新互联

写了两篇命题作文后,一发不可收拾了...要北京出差,走之前再搞两篇!(写于2015/03/21晚,次日进京)
       我在描述数据包分类Dimension Tree结构的时候,大量使用了二叉树结构,这就意味着我必须不断的左拐右拐,而到底哪里拐,免不了的是比较。我需要免除比较操作,这怎么可能?当然有可 能,空间换时间。并且,空间占用不能太大,以利于Cache的利用率。于是我想到了索引,就是类似MMU页表那样的。不可避免地,我再次遇到了空间复杂度 的问题...

公司主营业务:成都网站设计、成都网站制作、移动网站开发等业务。帮助企业客户真正实现互联网宣传,提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化,感谢他们对我们的高要求,感谢他们从不同领域给我们带来的挑战,让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出伊犁免费做网站回馈大家。

区间/规则转为位图

如果能够直接索引区间,那么区间就可以用数组表示,进而,该区间上覆盖的规则则可以是一个位图,对于16bit的域来讲,直接做索引也不过2^16条索引项,每个索引项指向一个索引,即区间数组下标。整个结构如下图所示:

基于索引和位图构建的高性能数据报匹配结构

这几乎就是Dimension Tree并行模式的内部实现,而且特别适合硬件实现,它足够规则和简单。
       非常直观,以至于没必要解释什么!然而这个结构是如何构建的呢?位图的构建非常简单,不必多讲,关键是索引表的构建,也不难,按照区间分割情况一个一个将 65535个表项填充,就像构建页目录,页表那样。然而值得解释的是,这里的每个匹配域只有16bit,如果再多的话,占用内存将会疯涨!比如如何匹配 32bit的IP地址!这确实是一个问题。

32位IP地址的匹配

这是我一直考虑的问题,而在近日,我找到了方案!这要归功于我发现了上面的索引/位图匹配结构。
       虽然这个结构只能匹配16bit的域大于16bit将会造成巨量内存占用...),但是它包含了很多的思想。其中最重要的就是,数据如何通过第三张表来进 行压缩,即实现数据共享,这好像是数据库的范畴,但是思想是普遍的。如果解决了这个问题,我几乎就可以设计出一个新的IPv4路由查找表的结构了。我真的 设计出了,但这是下一篇文章的内容。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网页名称:基于索引和位图构建的高性能数据报匹配结构-创新互联
文章出自:http://myzitong.com/article/dijogh.html