扫二维码与项目经理沟通
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
写了两篇命题作文后，一发不可收拾了...要北京出差，走之前再搞两篇！(写于2015/03/21晚，次日进京)
我在描述数据包分类Dimension
Tree结构的时候，大量使用了二叉树结构，这就意味着我必须不断的左拐右拐，而到底哪里拐，免不了的是比较。我需要免除比较操作，这怎么可能？当然有可
能，空间换时间。并且，空间占用不能太大，以利于Cache的利用率。于是我想到了索引，就是类似MMU页表那样的。不可避免地，我再次遇到了空间复杂度
的问题...
如果能够直接索引区间，那么区间就可以用数组表示，进而，该区间上覆盖的规则则可以是一个位图，对于16bit的域来讲，直接做索引也不过2^16条索引项，每个索引项指向一个索引，即区间数组下标。整个结构如下图所示：
这几乎就是Dimension Tree并行模式的内部实现，而且特别适合硬件实现，它足够规则和简单。
非常直观，以至于没必要解释什么！然而这个结构是如何构建的呢？位图的构建非常简单，不必多讲，关键是索引表的构建，也不难，按照区间分割情况一个一个将
65535个表项填充，就像构建页目录，页表那样。然而值得解释的是，这里的每个匹配域只有16bit，如果再多的话，占用内存将会疯涨！比如如何匹配
32bit的IP地址！这确实是一个问题。
这是我一直考虑的问题，而在近日，我找到了方案！这要归功于我发现了上面的索引/位图匹配结构。
虽然这个结构只能匹配16bit的域大于16bit将会造成巨量内存占用...)，但是它包含了很多的思想。其中最重要的就是，数据如何通过第三张表来进
行压缩，即实现数据共享，这好像是数据库的范畴，但是思想是普遍的。如果解决了这个问题，我几乎就可以设计出一个新的IPv4路由查找表的结构了。我真的
设计出了，但这是下一篇文章的内容。
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
我们在微信上24小时期待你的声音
解答本文疑问/技术咨询/运营咨询/技术建议/互联网交流
微信二维码
移动版官网