网络工程毕业设计论文-基于binarytrie的ip地址查找算法研究与实现(编辑修改稿)

网络工程毕业设计论文-基于binarytrie的ip地址查找算法研究与实现(编辑修改稿)内容摘要：

日 益膨胀和 IP地址的短缺，都预示着新一代网络协议 IPv6必然在不久的将来被实施，因为 IPv6协议不仅可提供充足的地址空间，还能对路由前缀实施更好的聚合，以减小路由表规模。 但是， IPv6协议的应用也将给路由查找带来很大的挑战，因为 IPv6的实施意味着 IP地址将从 32位迅速增加到 128位，而目前大多数成熟的算法都和 IP地址长度密切相关，有些算法根本无法适用于 IPv6。 路由查找现状 路由查找是寻找最长前缀匹配的问题，其难点在于不仅需要考虑与地址前缀相匹配，而且还需要考虑地址前缀的长度。 可以用基于硬件和软件 两种方法来实现路由查找。 基于硬件的查找算法分析 基于 RAM的路由查找方案是最简单的基于硬件的查找算法，该方案是在 RAM中为所有的 IP地址都建立一个对应的转发表项。 进行路由查找时，仅需要根据目的 IP地址进行检索，一次访存就可以找到对应的路由信息。 但这将造成转发表空间的极大浪费，因此，这种方案在实际中并不可行。 目前使用最多的硬件实现方式是在基于 RAM技术的改进：内容寻址存储器 (ContentAddressableMemory，简记 CAM)来进行快速的路由查找。 CAM能够在一个硬件时钟周期内完 成关键字的精确匹配查找。 常用的随机存储器通过输入地址来返回该地址所对应的数据信息，而 CAM的访问方式不同，只需输入关键字的内容， CAM就会将此关键字与 C胡中所有的表项同时进行匹配比较，最后返回匹配表项在 CAM中所对应的地址。 这种方法有一个明显的缺点，即在对地址前缀长度具体分布没有准确了解之前，为了保证能够存储 N个前缀表项，每个 CAM都需要有 N个表项的空间，因此，预留方案使得 CAM存储空间的利用率大大降低了，而且成本昂贵。 为了能够克服 CAM 方 法 的 缺 点 ， 又 有 一 种 CAM 实现机制 三态CAM(TernaryContent一 AddressableMemory，简记 TCAM)提出来。 TCAM一个特殊的CAM硬件设备，是 CAM实现机制的改进。 结构同 CAM一样，由一个二维阵列组成，阵列中的每一行对应存储器的一个槽，槽的大小依照不同的应用设置成 64bits、 72bits或 128bits及更高的比特位大小。 它能起到和完全相关联存储器一样的功用。 TCAM的优点是它保存的表项在长度要求上非常灵活，可以在同一个 TCAM芯片中保存任意长度的关键字表项。 TCAM具有实现简单、查找速度快的优点，它使用并行技术，查找复杂度仅为 O(1)， 但 TCAM最大的不足之处在于其造价昂贵、集成度低和高功耗。 基于软件的查找算法分析 基于 Binary Trie 的 IP 地址查找算法研究与实现 4 基于软件的路由查找算法有很多种，现按照算法实现的数学模型，对一些经典的路由查找算法做简要介绍。 基于线性查找：路由表内的表项按照简单的线性排列方式组织，查找将待查找的IP地址和数据库内的前缀逐一进行比较，直到匹配为止。 这种算法实现非常简单，而且存储代价也并不高，适用于低速要求下非常小规模的路由表实例。 然而，此算法不可能被广泛采用，特别是对于速度要求严苛的环境，因为其时间复杂度和路由表的规模成正比，其期望值是 N/2；其空间复杂度为 O(NW)(其中 W为最长前缀长度 )。 基于 Trie结构的查找：根据前缀的二进制比特值，构建二叉树或二的次叉树，根据前缀的二进制比特值将其关联的存储在分叉树上。 检索将待查找的 IP地址的二进制比特值作为索引，在 Trie树数据结构上索得到相应的前缀以及对应的下一跳路由信息。 二分 /多分查找：根据前缀的一些特性，例如前缀长度、前缀区间等，先将前缀进行预分割处理，并构造相应的决策树，将前缀存储在决策的不同分支。 查找时，利用待匹配目的 IP地址对应的属性值，在决策上进行搜索，得到与之匹配的最佳表 项。 基于哈希表结构的查找：根据前缀某个指定属性的哈希函数值，构造希表对前缀进行存储组织。 查找时根据待匹配目的 IP地址的哈希值进哈希索引，进而得到匹配结果。 由于哈希冲突的存在，基于哈希表的法通常需结合其它的算法思想，或常被融入到众多算法的思想精髓里。 规避查找技术：通过利用查找任务的某些局部性特征，或者对查找任进行特定的转化和重新分配，使得某些查找任务可以被简化或规避，而减小路由查找的压力，以满足高性能的需求。 基于 Trie 结构的路由算法的介绍 下面对基于 Trie结构的基于 Binary Trie的路由算法（在第二章重点介绍）、路径压缩（ PathCompressed） Trie算法、多比特 Trie算法、级压缩 Trie（ LCTrie）算法、位图压缩（ BitmapCompressed） Trie算法进行简要介绍。 Binary Trie 的路由算法 基于 Binary Trie 的 IP 地址查找算法研究与实现 5 图 13路由前缀集用例以及对应的二进制 Trie算法数据结构 基本的二进制 Trie 数据结构早在 20 世纪 70 年代就被提出，这种 Trie 的每个结点最多包含 2 个指针，分别指向他的左右孩子结点，代表前缀的某个比特位为‘ 0’和‘ 1’时两种情况 的搜索分支。 在 Trie 树中，处于第 L 层的结点实际上代表了一类地址前 L1 比特均相同的地址空间，如图 13 所示。 查找搜索时，根据待查找 IP 地址的比特位，从 Trie 树的根结点开始依次向其子孙结点进行，直到再无分支可搜索为止，其间记录的最后一个前缀结点对应的路由信息就是查找结果。 基本的二进制Trie 数据结构构造的 Trie 最多有 W+1 层，因此每次搜索的次数最多为 W 次，所以查找时间复杂度是 O(W)；存储一个前缀，最多可能产生 W 个 Trie 结点，因而该算法的存储复杂度为 O(WN)。 路径压缩 Trie 算法 要提 高查找速度、减少存储器访问操作的次数，必须降低 Trie树的高度。 降低 Trie树高度的一种方法是使用路径压缩技术。 路径压缩是 1968年 提出的一种叫做 PATRICIA的算术编码算法基础上，提出的一种称为路径压缩 Trie的最长前缀路由查找算法。 很明显，在二进制 trie树中存在着许多不含转发信息的中间结点。 从地址前缀分布的特点可知，到目前为止还没有长度小于 8比特的地址前缀，即便是长度介于 915比特之间的前缀也并不多，这就使得二进制 Trie树的前若干层主要是由那些不含转 发信息的中间结点组成。 路径压缩的 Trie树是对树的层次进行压缩，来减小树的深度。 由于某些结点被删除，查找过程中不是逐位对比，而是维护一个位变量指示下一个需要检查的比特位。 为了恢复原有信息，路径压缩 Trie树需要保存地址前缀的比特串。 基于 Binary Trie 的 IP 地址查找算法研究与实现 6 图 14路径压缩 Trie算法数据结构 当二进制 Trie树稀疏时，有许多内部结点具有单个的分支，当访问这样的结点时，没有分支决策，仅有的操作是当这个结点对应路由表中的一个前缀时记录下一跳信息，使得 Trie有一个高的空间复杂度和大的查找时间。 为了降低存储需求，缩短 Trie树的深度（查找时间），路径压缩 Trie中去掉了所有具有单个分支的内部结点（不包括含有前缀的结点）。 图 14给出了路径压缩 Trie算法的一个示例（采用与图 13中相同的前缀集）。 前缀结点 b和 e都处于一个“单分支并且内部不包含前缀结点的子 Trie结构”的末端，因而对应的单分支 Trie结构被压缩掉。 为了保证查找正确，在结点中增加两个域： Bitposition，表示下一个要比较的字符位； Bitstring，表示从根到该结点位置的路径对应的位串。 路径压缩 Trie的每一个叶子结点 含有一个路由前缀和一个下一跳信息指针。 当遍历一个路径压缩时间 Trie查找一个地址时，将结点中的位串与待查找的地址比较。 如果该位串是地址的一个前缀，则存储下一跳信息指针 (如果存在 )并且转向下一个结点。 当比较失败或者到达叶子结点时，查找终止。 此时，最近记录的下一跳信息指针作为结果被返回。 事实上，对于非前缀内部结点，路径压缩 Trie中的位串并不是必需的，增加这样的信息有助于尽早终止查找，从而提高平均查找性能。 路径压缩 Trie减少了对 Trie结构查找的平均次数，但最坏情况下，路径中可能不存在单分支结构，因此查找时 间复杂度仍为 O(W)；最坏情况下，没有分支被压缩，因而存储复杂度还是 O(NW)。 事实上，路径压缩 Trie仅当二进制 Trie树稀疏时其性能较优。 随着前缀个数的增加以及二进制 Trie树变得稠密，使用路径压缩 Trie的改进性能降低。 多比特 Trie 算法 基本二进制 Trie算法在查找时每次仅检查 IP地址的一个比特，查找速度较慢。 多比特 Trie算法在查找过程的每一步检查多个比特，加速查找的进程，其中每步检查的比特数定义为搜索步长。 如图 15所示，该多比特 Trie的第一层上有 8个分支，对应的搜索步长 为 3；而在第二层，每个结点有 4个分支，对应的搜索步长为 2。 我们看到，整个 Trie树仅有 2层，即最多仅需 2次多分支 Trie搜索就可以得到最终匹配结果，相比基于 Binary Trie 的 IP 地址查找算法研究与实现 7 基本二进制 Trie在性能上有了较大的改进。 一般的， k比特（即每层都有 2k个分支的）Trie的查找时间复杂度是 O(W/k)。 另一方面，我们注意到，多比特 Trie不能支持任意长度的地址前缀，如图 15的例子，该多比特 Trie仅支持长度为 3和 5的前缀，为了能够用多比特 Trie来进行前缀查找，路由表中的地址前缀需要被扩展成这两种长度。 这种扩展带来了存储的冗余度，增加 了存储复杂度。 最坏情况下，存储复杂度为 O(N 2k W/k)。 图 15多分支 Trie的数据结构示意 针对常规的多比特 Trie浪费存储空间的问题， 压缩 Trie（ LevelCompressed Trie）的算法。 该算法的主要思想是：灵活的为 Trie的各个层、各个分支按照前缀集分布特点自适应选定不同的搜索步长：当子 Trie结构分支是满 2L叉树时，才使用步长 L。 这样既能发挥多比特 Trie的优势，同时由于子 Trie结构本来就是满 2L叉树，不会产生结点复制。 但我们也注意到 ，层压缩 Trie仅在 Trie结点分布较为密集时才较为有效。 级压缩 Trie（ LCTrie）算法 如上所述，路径压缩 Trie适合于结点稀疏的情况。 Nilsson ET AL提出了一种级压缩技术用于结点稠密的情况。 这种技术被称为级压缩 Trie，简称 LC一 Trie。 LC一 Trie结合路径压缩和多位 Trie的特点进一步优化基本 Trie结构。 LC压缩树中每个内部结点的孩子结点都是连续存放的，父结点只存放左孩子指针，每个父结点还存放分支(branch)信息，如果父结点有 8个孩子结点，分支记录将是。