基于优先级Trie树的动态IP匹配模型

摘要

本发明提供一种基于优先级Trie树的动态IP匹配模型，其包括：BIPT匹配模型的构建过程；BIPT树的前缀插入操作；BIPT树的前缀删除操作；BIPT树的IP匹配操作。与现有的方法相比，本发明提出了基于优先级Trie树的动态IP匹配模型，利用优先级Trie树在IP查找方面的优越性，提高它在更新方面的性能。利用B*树保证在更快定位到优先级Trie树分支，同时能以更小的概率分配索引结点。本发明提出的算法与已有的优先级Trie树相比，不仅减少了前缀更新时的开销，同时也保持了较高的查找效率。

主权项

一种基于优先级Trie树的动态IP匹配模型，其特征在于，包括以下步骤：步骤1：BIPT匹配模型的构建过程，具体包括：步骤11，划分前缀；设前缀P的长度为l，则该前缀P表示为P＝P₀P₁…P_l‑1*；以长度k(k＜l)对前缀P进行划分，分为长度大于划分点k的第一前缀集合和长度小于划分点k的第二前缀集合，赋予第一前缀集合内每个前缀一个索引值，赋予第二前缀集合内每个前缀一个索引后缀，且所有的索引后缀相同；以Pre_k(P)来表示有索引值的前缀，则Pre_k(P)＝(P₀P₁…P_k‑1)₂；以Par_k(P)表示有索引后缀的前缀，则Par_k(P)＝P_kP_k+1…P_l‑1*；步骤12，构建B*索引树；将第一前缀集合内的前缀P根据索引值挂载到B*索引树上相应的B*结点中，并用BIPT[i]表示，且0≤i≤2^k‑1；将第二前缀集合内的所有前缀挂载到B*索引树上的一个共同的B*结点中，并用BIPT[‑1]表示；步骤2：BIPT树的前缀插入操作；步骤21：对每一个前缀P，先求前缀P的长度，如果其长度大于划分点k，则设置起始查找结点为根结点并进行步骤22；否则将前缀插入BIPT[‑1]对应的优先级Trie树中并终止前缀插入操作；步骤22：在B*索引树的给定结点中进行查找，直到叶子结点；在索引结点中若Pre(p)＜k₁，则选择索引结点的第1个分支进行查找，并执行步骤23；若k_i≤Pre(p)≤k_i+1，则选择索引结点的第i个分支进行查找，并执行步骤23；若k_n(x)＜Pre(p)，则选择索引结点的第n(x)个分支进行查找，并执行步骤23；并记录查找路径中所搜索的给定结点以及给定结点中分支的选择；其中规定k_i(x)是结点x的第i个索引值，c_j(x)是结点x的第j个孩子指针，其中i和j满足1≤i≤n(x)并且1≤j≤n(x)。在结点中的索引值存在如下关系：k₁(x)＜k₂(x)＜…＜k_n(x)(x)步骤23：查找索引结点中是否有与B*索引树的给定结点的索引值相同的关键字，如果有，则直接在该B*索引树的给定结点优先级Trie树中插入索引后缀，并结束插入操作；否则执行步骤24；步骤24：判断B*索引树的给定结点中索引值数目是否已满，如果给定结点已满，则进行索引结点分裂，在新结点中的优先级Trie树中插入索引后缀；如果结点未满，则在该B*索引树的给定结点中插入索引值，并在优先级Trie树中插入索引后缀；步骤3：BIPT树的前缀删除操作；步骤31：对每一个前缀P，先求前缀P的长度，如果其长度小于划分点，则在BIPT[‑1]形成的优先级Trie树中删除前缀P，并终止前缀删除操作；否则进行步骤32；步骤32：在B*索引树的索引结点中进行查找，直到叶子结点；使得索引值在索引结点两个关键字之间，索引结点分别为左区间和右区间；步骤33，在左区间对应的优先级Trie树中移除索引后缀，释放相应的数据结点；然后记录搜索路径各结点指针以及左区间的位置；步骤34：释放数据结点后，若左区间对应的优先级Trie树为空，则在B*索引树中删除对应的索引值，并判断索引结点中的结点数小于执行步骤34，否则结束删除操作；步骤35若结点数小于则进行结点合并操作，否则结束删除操作；合并操作如下：步骤351：若索引结点为根结点，则结束合并操作，否则执行步骤352；步骤352：判断兄弟结点中的结点数是否小于若小于则结束合并操作，若大于则将兄弟结点中的结点移至该索引结点中，并更新父结点对这两个分支的索引值；若兄弟结点中的结点数等于则将这三个结点合并为两个结点，同时更新并删除父结点中对这两个分支的索引值，如果父结点中元素不足则结束合并操作；步骤4：BIPT树的IP匹配操作；根据给定的IP地址，将其前缀分为索引值以及索引后缀，根据索引值在B*索引树中定位到对应的优先级Trie树分支并进行查找，得到的结果为最长前缀；若未找到对应分支，或在优先级Trie树中未找到匹配结果，则在BIPT[‑1]中继续进行最长前缀匹配，直到找到最长前缀，结束BIPT最长前缀匹配过程。