| 摘要 |
A method is provided to improve the performance of dynamic router-table designs. Specifically, the invention relates to a method and system for partitioning prefixes at each node of a partitioning tree into 2<s>+1 partitions using the next s bits of the prefixes. Prefixes that have a length less than s are placed into partition -1, with the remaining prefixes falling into the remaining partitions that correspond to the value of their first s bits. Prefix partitioning may be controlled using either static rule tables or by dynamic rule tables. In one embodiment, binary tree on binary tree (BOB) data structures are applied to a partition of the present invention. In another embodiment, prefix binary tree on binary tree (PBOB) data structures are applied to a partition of the present invention. In a further embodiment, a dynamic longest-matching prefix binary tree on binary tree-table (LMPBOB) is applied to a partition of the present invention.
|
