增强多位Trie树查找方法和装置

摘要

本发明涉及路由转发表的查找技术，特别是一种增强多位Trie树查找方法和装置。通过对多位Trie树的查找方法、树节点的数据结构，尤其是扩展位图以及上下级树节点之间的关系做出优化改进，以及对FPGA和DDRIISDRAM的采用，实现了大容量路由转发表的查找和20Gbps甚至40Gbps流量下的线速查找，在表项容量、成本等方面与商业三态内容可寻址存储器方案相比均有明显优势。

主权项

一种增强多位Trie树路由查找方法，其特征在于，该方法包括以下步骤：(1)从网络处理器获取查找关键字；(2)从动态随机访问存储器阵列中读取一个树节点；(3)以所述关键字为索引，从所述的树节点包含的扩展位图中取得位图值；(4)如果该位图值为M，那么根据该位图值在所述扩展位图中的偏移量和所述树节点中指向下一级子树节点的指针，重复步骤(2)与(3)，所述偏移量指该位图值在所述扩展位图中的位置；如果该位图值不为M，转步骤(5)；所述M是1或0；(5)根据步骤(4)所述位图值在所述扩展位图中的偏移量和所述树节点中指向下一级子树节点的指针取回下一级树节点，如果该下一级树节点不是支持节点合并的节点，转步骤(6)；如果该下一级树节点是支持节点合并的节点，转步骤(8)；(6)根据步骤(2)取得的前一级树节点指示的前缀节点信息取回该级的前缀节点，转步骤(7)；(7)根据当前正在查找的关键字和所述前缀节点中的前缀位图进行处理，如果有命中的前缀，根据指向结果节点数组的指针和命中前缀在所述前缀位图中的偏移量取回该命中前缀所对应的结果节点，转步骤(9)；如果没有命中的前缀，那么根据所述前缀节点中指向前一级的结果节点的指针，取回该结果节点，转步骤(9)；(8)根据当前正在查找的关键字和步骤(5)中取回的下一级树节点中存储的前缀信息，判断是否有命中的前缀，如果有命中的前缀，取回该命中前缀所对应的结果节点；如果没有命中的前缀，根据所述下一级树节点中指向前一级的结果节点的指针取回该结果节点，转步骤(9)；(9)回送查找结果给所述网络处理器。