发明名称 |
Method and apparatus for storing sparse and dense subtrees in a longest prefix match lookup table |
摘要 |
We present a lookup table which allows sparse subtree descriptors and dense subtree descriptors to be stored in the same memory. A subtree entry in the memory stores a dense subtree descriptor for a dense subtree or a plurality of sparse subtree descriptors for sparse subtrees. The subtree entry is indexed by a leaf in the previous subtree. The sparse subtree descriptor stores at least one node descriptor. The node descriptor describes a set of leaves in the sparse subtree having a common value. The common value is encoded in the node descriptor using run length encoding.
|
申请公布号 |
US6539369(B2) |
申请公布日期 |
2003.03.25 |
申请号 |
US20000733761 |
申请日期 |
2000.12.08 |
申请人 |
MOSAID TECHNOLOGIES, INC. |
发明人 |
BROWN DAVID A. |
分类号 |
G06F17/30;G11C15/00;H04L12/56;(IPC1-7):G06F17/30 |
主分类号 |
G06F17/30 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|