Patent ID: 7042884
Filing Date: 2006-05-09
Classification: H04L

Abstract:
1. A network address forwarding table lookup apparatus for identifying a 32-bit network address to determine a next-hop address to which data packets having the network address are forwarded, the apparatus comprising: a memory storing a five-level compression-tree forwarding table, the forwarding table having a first level module, a second level module, a third level module, a fourth level module, and a fifth level module; the first level module comprising a first compression bitmap having two first level index entries directly addressable by the 17 the second level module comprising second level primary entries directly addressable by the first level pointer and the first level index entries comprising the independent index, each of the second level primary entries alternatively comprising a next hop index indicating the next hop address for the data packets if the first to the 17 the third level module comprising third level primary entries directly addressable by the second level pointer and the second level index entries comprising the independent index, each of the third level primary entries alternatively comprising a next hop index indicating the next-hop address for the data packets if the first to the 24 the fourth level module comprising fourth level primary entries directly addressable by the third level pointer and the third level index entries comprising the independent index, each of the fourth level primary entries alternatively comprising a next hop index indicating the next-hop address for the data packets if the first to the 25 the fifth level module comprising fifth level primary entries directly addressable by the fourth level pointer and the fourth level index entries comprising the independent index, each of the fifth level primary entries comprising a next hop index indicating the next hop address for the data packets; wherein each of the first, second, third and fourth level index entries comprising the independent index directly corresponds to one of the next level primary entry in sequence, and each of the first, second, third and fourth level index entries comprising the dependent index associatively corresponds to the next level primary entry to which the previous same level index entry comprising the independent index directly corresponds.