基于DMP-Tree的高速IP查找方案

### 基于DMP - Tree的高速IP查找方案 #### 1. 引言 IP查找问题一直是高速网络中的关键挑战。近年来，虽有诸多方案被提出，但多数在处理大规模前缀、长地址和高速需求时表现不佳。本文将介绍一种基于硬件的动态M路前缀树（DMP - Tree）方案，它在大规模数据集上具有良好的扩展性，有望解决高速IP查找的瓶颈问题。 #### 2. 相关工作 - **Trie树相关方案** - **二叉Trie树**：实现简单，但IPv4最坏情况下搜索时间为O(32)。 - **Patricia Trie树**：通过压缩路径和消除不必要节点改进二叉Trie树，已在BSD内核中实现。 - **层级压缩**：对二叉Trie树进行优化，如V.Srinivasan和G.Varghese应用动态规划技术压缩树高和优化内存使用。 - **DP - Trie**：尝试通过保留前缀和位位置索引来压缩Patricia Trie树。 - **多路树扩展**：一些方案从二叉树扩展到多路树，将前缀视为范围进行搜索。 - **哈希方案**：不利用地址的层次结构，不适合互联网应用，且骨干路由器缓存命中率低。 - **硬件方案** - **CAM方案**：使用内容可寻址存储器实现最佳匹配前缀，但成本高或尺寸大。 - **其他硬件方案**：如一些方案逻辑简单，但难以扩展到IPv6。 - **缓存方案**：在骨干路由器中效果不佳。 - **Lulea算法**：旨在最小化数据结构的存储需求，使其能适应通用处理器的L1缓存。 #### 3. DMP - Tree介绍 - **定义与比较规则** - **字符串比较规则**：假设两个字符串A = a1a2…an和B = b1b2…bm，以及特殊字符。若n = m，比较A和B的值；若n ≠ m（假设n < m），比较子串a1a2…an和b1b2…bn，若不相同，值大（小）的子串更大（小）；若相同，检查bn + 1字符，若bn + 1等于或在字符排序中先于，则B ≤ A，否则B > A。 - **封闭字符串定义**：若存在数据字符串A，使字符串S是A的前缀，则S称为封闭字符串，A称为封闭数据元素。 - **与B - Tree的关系**：DMP - Tree是B - Tree的泛化，区别在于索引树中数据元素不能高于其封闭字符串所在层级，这限制了节点分裂，使B - Tree成为DMP - Tree的特殊情况。当内部分支大且数据集大而随机时，DMP - Tree在搜索和内存利用上接近B - Tree。 #### 4. 实现 - **总体设计** - **架构**：使用内部和外部内存模块存储前缀，内部节点存储在片上内存，叶子存储在外部RAM。搜索和更新模块分别负责搜索和更新，插入和删除模块是更新模块的子模块。