公开(公告)号：CN112887212A

公开(公告)日：2021-06-01

申请号：CN202110214076.4

申请日：2021-02-25

Applicant: 清华大学

Inventor： 张雨轩 ,  杨芫 ,  徐明伟

IPC: H04L12/741 ,  H04L12/745

Abstract: 本发明提出一种基于可变步宽trie树的高速路由查找方法和装置，其中，方法包括：根据路由表中的所有前缀构建至少一个根节点；以每个根节点对应的预设步宽s，对所有前缀接下来的s位二进制数据匹配，得到2s个子节点；对内部节点重复执行上述步骤，直至子节点都为叶子节点完成对初始trie树的创建；根据初始trie树中的子节点的节点类型，构建与叶子节点对应的leaf_string和与内部节点对应的innode_string；根据预设的分段长度w分别对leaf_string和innode_string分段得到多个分段数据，通过计数器对每个分段数据计数得到对应的计数结果，以便于根据计数结果查询目的IP地址对应的路由。由此，在保证查找效率的基础上，通过对于可变步宽的支持，提高了算法的灵活性。

公开(公告)号：CN112887212B

公开(公告)日：2022-03-29

申请号：CN202110214076.4

申请日：2021-02-25

Applicant: 清华大学

Inventor： 张雨轩 ,  杨芫 ,  徐明伟

IPC: H04L45/745 ,  H04L45/748

Abstract: 本发明提出一种基于可变步宽trie树的高速路由查找方法和装置，其中，方法包括：根据路由表中的所有前缀构建至少一个根节点；以每个根节点对应的预设步宽s，对所有前缀接下来的s位二进制数据匹配，得到2s个子节点；对内部节点重复执行上述步骤，直至子节点都为叶子节点完成对初始trie树的创建；根据初始trie树中的子节点的节点类型，构建与叶子节点对应的leaf_string和与内部节点对应的innode_string；根据预设的分段长度w分别对leaf_string和innode_string分段得到多个分段数据，通过计数器对每个分段数据计数得到对应的计数结果，以便于根据计数结果查询目的IP地址对应的路由。由此，在保证查找效率的基础上，通过对于可变步宽的支持，提高了算法的灵活性。