中国钟学我术大草 信息网给与协议 UKIVERIT背OP SCIENC建D TECHNOLO0YO年Ca框NA 分类 ·基于Trie的算法 Binary Trie -Trie+Bitmap ·基于硬件的算法
信息网络与协议 分类• 基于Trie的算法 – Binary Trie – Trie+Bitmap • 基于硬件的算法
中国斜学我术大学 信息网给与协议 n/ERIITY OF SCIENC建AND TECHNOLO0YO年EN 基于Trie的算法 路由查找算法的关键是如何用一个高效的数据结构来 表示转发表，基于Trie的方法是用Trie来表示转发表 Trie:ReTrieval,一种树型结构，在路由查找算法 中，使用Tie来组织转发表，从根节点开始的路径对 应着转发表表项的前缀 在以下的叙述中，为了简单起见，在不影响算法的有效 性的情况下，转发表中的表项用其所对应的前缀来表示
信息网络与协议 基于Trie的算法 路由查找算法的关键是如何用一个高效的数据结构来 表示转发表，基于Trie的方法是用Trie来表示转发表 在以下的叙述中，为了简单起见，在不影响算法的有效 性的情况下，转发表中的表项用其所对应的前缀来表示 Trie：ReTrieval，一种树型结构，在路由查找算法 中，使用Trie来组织转发表，从根节点开始的路径对 应着转发表表项的前缀
® 中国钟学我术大草 信息网倍与协议 UKIVERIT背OP SCIENC建D TECHNOLOOY O年Ca框NA 基于Trie的算法 ·Binary Trie ·LC Trie Path-Compressed Trie -Multi-Bit Trie
信息网络与协议 基于Trie的算法 • Binary Trie • LC Trie – Path-Compressed Trie – Multi-Bit Trie
中国钟学我术大草 信息网给与协议 数据结构 、使用二进制Trie来组织转发表 P1 P2 Trie中的每个节点有两个指针 :0指针和1-指针，即每个节 点最多有两个子节点 从根开始到节点x的路径上的 比特串代表了X所对应的前缀P 对于节点X,如果其前缀对应 着前缀数据库中的某个表项， 则该节点称为前缀节点，前缀 节点包含了下一跳信息 前缀数据库：转发表中所有前缀的集合
信息网络与协议 数据结构 • 使用二进制Trie来组织转发表 – Trie中的每个节点有两个指针 ：0-指针和1-指针，即每个节 点最多有两个子节点 – 从根开始到节点X的路径上的 比特串代表了X所对应的前缀P – 对于节点X，如果其前缀对应 着前缀数据库中的某个表项， 则该节点称为前缀节点，前缀 节点包含了下一跳信息 前缀数据库：转发表中所有前缀的集合 P1 0 1 P2 0 P3 0 0 1 1 0 1 1 1 1 1 0 0 0 P4 P5 P6 P7 P8 P9
Prefix Database P1 火 P2 1* P3 00* P4 101* P5 111* P6 1000* 5 P7 11101* P8 111001* P9 1000011* Node Structure Next Hop Information P8 (If a prefix node) P9 0-Pointer 1-Pointer 从根到X的路径上的比特串代表了X所对应的前缀P 灰色节点为前缀节点，存储下一跳信息，用前缀P来表示
信息网络与协议 Next Hop Information (If a prefix node) 0-Pointer 1-Pointer Prefix Database P1 * P2 1* P3 00* P4 101* P5 111* P6 1000* P7 11101* P8 111001* P9 1000011* P1 0 1 P2 0 P3 0 0 1 1 0 1 1 1 1 1 0 0 0 P4 P5 P6 P7 P8 P9 Node Structure 从根到X的路径上的比特串代表了X所对应的前缀P 灰色节点为前缀节点，存储下一跳信息，用前缀P来表示