Huawei Technologies Co., Limited

Shijun Shen

Meng Li

Jun Liang

Jun Gong

Rui Hu

Juan Zhang

The present invention discloses a method and apparatus for longest prefix matching. The method includes (A) reading a current-level trie node (TNODE) in the trie, (B) determining whether an offset field of the TNODE indicates that a matched prefix exists in an upper level node and, if so, adding the offset field of the TNODE to a pointer that points to a leaf array in the upper level node, updating a current best match pointer with the computation result and executing block (C), otherwise, executing block (C), (C) determining whether the TNODE has a child node according to a child bitmap, when it is determined that a branch flag of the TNODE matches a corresponding bit of a search keyword, and (D) when it is determined that the TNODE has no child node, reading the internal bitmap of the TNODE, computing a longest matched prefix in the TNODE according to the internal bitmap and a pointer that points to a leaf array in the TNODE, updating the current best match pointer with the computation result, and computing an address of a leaf node (LNODE) associated with the current best match pointer.

Growing community of inventors

Shenzhen, China

Shijun Shen