多级索引路由查找算法及其实现

A Multi-level Index Lookup Algorithm and Its Implementation

路由查找是IP网络传输中或者基于IP构建的通信分组网中的重要组成部分。多分枝trie树查找算法是一种快速高效的路由查找算法,但同时也带来了巨大的内存开销。一种改进的多分枝trie树查找算法,即多级索引路由查找算法,将原有算法中的二级索引扩展为多级索引,并引入了标志位连续存储的方式,在基本不影响查找效率的前提下,极大地减小了路由索引表的内存开销。

Routing lookup is an important technology for IP transmission network and IP-based packet switching network. Although the multi-branch trie tree lookup algorithm is a fast and efficient routing lookup algorithm, it also makes large memory consuming. A multi-level index lookup algorithm, i,e., an improved multi-branch trie tree lookup algorithm, is proposed. It expands the original two-level index to multi-level index, and introduces a continuous flag bit storage method that is able to extremely reduce memory overhead of routing index table while not obviously affecting the lookup efficiency.