摘要
路由器的主要任务是转发IP分组,实现高速分组转发的关键是快速的路由查找算法。我们针对IPv4地址,首先建立前缀长度为8、16和24的3张hash表,在此基础上,再分别针对不同长度的前缀建立最多只涉及其余8比特的多分支Trie树。在这种结构中进行IP路由查找,其存储器访问次数最多为7次,而且还具有易于更新、易于扩展等特点。
The main task of a router is to forward the IP packet. The key to realize the high speed IP packet forwarding is the lookup algorithm. We buildup three hash tables of the prefix length belongs to 8,16 and 24 first,and then build up multibit-trie which deals with rest 8 bits. To lookup the IP routing in this data structures has at the worst seven times memory access,it also give facility for updating and expansive.
出处
《计算机应用与软件》
CSCD
北大核心
2005年第9期115-117,共3页
Computer Applications and Software
